> For the complete documentation index, see [llms.txt](https://docs.moduluszk.io/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.moduluszk.io/performance-the-prover-envelope/structure-instead-of-recurrence-sudoku-validity.md).

# Structure instead of recurrence: sudoku validity

A different shape of claim: no recurrence, only structure. Every row, column and box of the grid must be a permutation of the symbol set. 

The two sides prove different statements here, and that difference matters more than the timings. The comparator guests take a finished grid and commit it, proving that a public grid is valid. zkFOL proves that a grid exists satisfying the clues, and publishes none of it: zero public columns, an empty claim list. The privacy property described on the core-concepts pages is visible inside a benchmark. 

| **Workload: 9x9 sudoku validity**   | **Prove** | **Verify** | **Prover memory** |
| ----------------------------------- | --------- | ---------- | ----------------- |
| zkFOL, existence, nothing disclosed | 15.95 ms  | 3.38 ms    | \~25 MB           |
| RISC Zero, composite, grid public   | 7.252 s   | 12.46 ms   | 606 MB            |
| RISC Zero, succinct, grid public    | 18.040 s  | 12.44 ms   | 1.43 GB           |
| SP1, core, grid public              | 13.687 s  | 75.92 ms   | 9.57 GB           |
| SP1, compressed, grid public        | 50.329 s  | 33.21 ms   | 16.80 GB          |

Prove ratios at 9x9: 455x to 3,160x; memory 24x to 670x. At 16x16 zkFOL proves in 65.42 ms against 14.5 to 50.2 seconds, with one caveat: the 16x16 relation omits the range checks the 9x9 carries, so it understates the larger grid's true cost, and the 9x9 to 16x16 step is a direction rather than a factor. \[S, benchmark record] 

The record makes a structural point with a third grid size: comparator cost tracks the proof machinery's padding, not the puzzle. Guest cycle counts rise 6.9x from 4x4 to 16x16 while SP1 compressed moves under 1.4 percent, and RISC Zero composite is flat until its padding doubles. zkFOL is the only column that responds to the claim itself. \[S, benchmark record] 

Verification: zkFOL wins it on both grids, 3.4 to 3.5 ms against 12 to 78 ms, and does not win it on the linear fib route below. The verify advantage belongs to small claims. \[S, benchmark record]

<br>