Skip to content

Latest commit

 

History

History
66 lines (53 loc) · 3.68 KB

snark.md

File metadata and controls

66 lines (53 loc) · 3.68 KB

SNARK Verifier in Bitcoin Script

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

Bitcoin Script Constraints

Fundamental Constraints

  • 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

Practical Constraints

  • 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)

Possible Proof Systems

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

All three can operate over the bn254 curve.

Example implementations:

Code Modules

  • 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

Complexity Analysis

  • 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.

General Ideas for Optimizations

  • 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