Blog: https://www.alpenlabs.io/blog/state-of-snark-verification-with-bitvm2
We break down each of the curve and field operations in the Miller’s algorithm to estimate their cost in terms of script size and max run time stack use. The goal is to align the entire program such that we obtain the least number of bit-commitments of intermediate hashes.
To achieve such result, we can have cases where we need to break a single field or group operation into multiple tapscripts. The only such case with our breakdown is with, “point doubling and evaluation plus sparse multiplication with Fp12 accumulator” tapscript which doesn’t fit inside the block limit albeit by a very small amount. To resolve this we perform a small portion of this computation in the script immediately preceding it, which is squaring the Fp12 accumulator. Such breakdown of operation makes it difficult to have clean separations but they are still doable with some overhead.
Terms Used in Tabulation:
Statements ← Operation
Drop ← elements dropped from stack after this op (prefixed by +/- shows change)
Add ← elements added to stack after this op
Cost ← opcode count of this op
Before/After ← stack used before/after this op
MaxUse ← Max Stack used during the execution of this op
Following diagram shows interconnection between different cryptographic operations in the groth16 proof. Understanding this relation helps have an idea on how the bit-committed values are linked.
bc ← bit commitments of 32 byte elems (field elem or hash)
nx ← block repeated n times
For the entire groth16 proof verification, we require bit-commiting 611 hashes (32-byte elements) which equates to around 4.8 MB of on-chain data.
We assume the available script size per tapscript is enough to accommodate costs of operations that have been neglected for being small during this design. What is not included here (and also in the bitvm repo) is subgroup membership test for G2 element of groth16 proof. This shouldn’t incur a significant increase in number of bit-commitments because point scalar multiplication is over a constant 64 bit scalar which we intend to fit in existing tapscripts that have low script size use.
Changelog: