A plan to implement a SNARK verifier in Bitcoin Script to run it in BitVM2.

- Max script size: 4 MB
- Max stack size: altstack + stack < 1000 items
- Max stack item size: 520 bytes
- Max input size for arithmetic opcodes: 32-bit words

- Max script input in form of 32-bit words:
`1000 items * 32-bit/item = 32 kB`

- Overhead of transferring state between Scripts
- 26 bytes per bit (using Winternitz signatures)
- 1 stack item for every 4 bits (each item 20 bytes)
- Maximum input state size per Script:
`1000 items * 4 bit/item = 4000 bits = 500 bytes`

(requires 20 kB of signature data)

- Groth16 ( 22000 Fq multiplications )
- FFlonk ( 14000 Fq multiplications + hash function )
- FFlonk + slonk

All three can operate over the bn254 curve.

Example implementations:

- Lamport signatures / Winternitz signatures
- u256 arithmetic
- addition, multiplication, Karatsuba multiplication

- bn254 field arithmetic
- addition, multiplication, inversion
- Montgomery reduction

- bn254 curve operations
- point addition, inversion, scalar multiplication

- bn254 degree-2, degree-6, and degree-12 extensions
- bn254 pairings
- constant vs variable inputs

- The Groth16 proof size is about 300 bytes. The public inputs are roughly another 100 bytes.
- Currently, a full block of space costs less than 0.3 BTC ~ $20000 in fees.
- The assertTx may commit to up to 16 KB of trace data.
- A degree-12 extension field element is about 3 KB. Thus, naively, the assertTx may commit to only about 5 intermediate results. Verifiers could choose only from up 6 disproveTx Tapscripts, and the combined size of all Tapscripts is up to
`6 x 4 MB = 24 MB`

. Using hash commitments, we can compress the signatures commitments at the expense of more overhead in the disprove scripts.- A full block can commit to about
`4 MB / block * 26 bytes / bit = 16 kB / block`

of signed data. - That’s about
`( (4mb / 26 byte) bits ) / 20 bytes = 960`

20-byte hashes. Thus, we could chunk the computation into about 960 Scripts of 4 MB each. Considering a communication overhead of about 1 - 2 MB, we can run computations of up to 2 - 3 GB in total. - We can run maybe 4 instances in parallel, enabling 8 - 12 GB of computation.

- A full block can commit to about

- The prover can make another large commitment in his kickoffTx.
- We can use a sequence of commit transactions, effectively spreading out the commitment over multiple blocks.
- The chunks f1, f2, f3, … don’t have to be in sequence. Their inputs and outputs can form any kind of DAG. So we don’t need to send global information along each step.
- The commitment script can make use of conditionals. E.g., “if z3 == 1 then commit to z11 else commit to z17”
- We can use hints / auxiliary inputs to the f_i / E.g., provide an inverse and then verify it using multiplication
- We can pre-parse script inputs into the right format. E.g., provide a value as bits on the stack instead of 30-bit limbs
- Wrap a STARK into a SNARK. One-time setup enabling fast and compact universal computation.
- The disproveTx can be quite large because only a dishonest prover would have to pay for it
- We can hash intermediate results, compressing the assertTx, at the expense of having to compute a hash function in the disproveTx