search

TritonVM / tasm-lib

A collection of functions written in Triton VM assembly (tasm)
Apache License 2.0
10 stars 2 forks source link

Verifier optimizations #106

Open Sword-Smith opened 2 months ago

Sword-Smith commented 2 months ago

Some optimizations that we could do to the STARK verifier

Status snippet idea Proc Opstack RAM
✓ Done MerkleRoot Use recurse_or_return in inner loop 2.059 2.008 0
✓ Done BarycentricEvaluation Use recurse_or_return in inner loop 2.500 2.100 0
✓ Done BarycentricEvaluation Precalculate partial terms 7.300 4.200 -4.600
❌ Not planned All auth-path verifications merkle_walk 26.500 0 0
Not started FRI verifier Change FRI interface to get rid of a zip for return value 3.166 3.302 1.292
Not started FRI verifier Get rid of an two internal maps for verifying last codeword 3.000? 3.000? 500?
Not started STARK verifier Don't pad on hashing of rows, make column count a factor of 10 4.000 8000? 0
Not started SampleIndices Code looks a bit verbose. See if it can be improved. 2.000? 2.000?

All savings are calculated for a FRI expansion factor of 4 and an inner padded height of $2^{19}$ on triton-vm 0.42-alpha5. A negative value indicates an increase in the row count for this change.

For reference current row counts for the execution of the STARK verifier program are given below. Processor Opstack RAM Hash
Expansion factor 4 299.474 246.102 282.946 236.275
Expansion factor 8 236.744 210.030 206.096 185.812
Expansion factor 16 235.988 223.764 176.800 162.655

Introducing merkle_walk would get us very close to being RAM-table dominated[^0]. And when we are RAM dominated, I'm not sure further optimizations are that beneficial. But that depends on what program recursion is combined with.

Update After addressing the first three optimizations, we have: Processor Opstack RAM Hash
Expansion factor 4 287.710 237.970 287.554 236.263
Expansion factor 8 224.980 201.898 210.704 185.800
Expansion factor 16 212.446 207.444 186.016 162.643

[^0]: notice that the above-mentioned savings are for expansion factor 4, and that the savings introduced by merkle_walk decrease with a higher expansion factor.

Sword-Smith commented 2 months ago

Note that cd71bd2ea25c6cc21638876feb767848f1567226 can be reverted to save ~4.600 RAM table rows at the cost of 7.300 processor table rows. Twice that for EF 16.