Introduce BF-STARK
30 May 2024
1) Bitlayer research team is proud to announce our latest breakthrough in ZK proof verification on Bitcoin - a new FRI gadget that is not only straightforward but also Bitcoin-friendly.
This thread gives a brief introduction to the basic ideas:
- Why STARK and nothing else
- Key hurdles verifying STARK on Bitcoin L1
- How to verify Merkle proof without OP_CAT
- Practical verifier by splitting verifier into segments
2) Bitlayer is a Bitcoin rollup with BitVM2 paradigm. One rollup node (operator) aggregates and executes L2 transactions, generates state transition proof, and submits new state root and proof to Bitcoin L1 for public verification. Other nodes watch the progress and verify the published data. One of the 2 branches is taken depending on the verification result:
Happy branch: all nodes agree with the claim, and L2 transactions are finalized after a timelock.
Unhappy branch: at least one node doesn’t agree with the claim. A challenge game will be kicked off and ZKP verifier will be executed onchain to act as the referee.
3) It’s not trivial to implement a ZKP verifier on Bitcoin due to the limited programmability. Bitcoin script is deliberately designed to be Turing incomplete:
only basic primitives such as signatures, timelocks, and hashlocks are provided scripts are stateless and can’t call each other
Script engine also imposes other limitations:
script size of 400KB
stack depth of 1000
As a common understanding, it’s not feasible to directly run ZKP verifier on Bitcoin L1.
4) However, thanks to Robin’s BitVM2 paradigm, it’s now possible to verify ZKP proof on Bitcoin:
The optimistic way: only run the ZKP verifier when someone doesn’t agree with rollup operator’s claims; this makes Bitcoin rollup affordable when operator is honest most of time.
The onchain verifier is split into multiple segments, and each segment can run on Bitcoin without breaking resource limitation.
The next question is, SNARK or STARK?
5) STARK is Bitlayer’s first choice since day one. STARK has some advantages that we cherish:
shorter proving time
no trust setup
post-quantum security
Moreover, STARK is evolving fast - the next generation STARKs (e.g. Circle STARK) may achieve over one hundred fold performance compared to previous generation. The small fields (< 2^31) in STARK make arithmetic emulation with Bitcoin opcode affordable. Quoted from Delphi Digital’s report: “STARKs are much suited for verification on BTC than SNARKs due to them being hash based and relying on smaller fields like M31”.
6) FRI is the core component of STARK, and the commit phase in FRI leverages the Merkle tree to commit polynomial. To verify STARK proof onchain, verifying Merkle inclusion proof is a MUST.
However, verifying Merkle inclusion proof, without OP_CAT, is a mission impossible.
Some projects tried to wrap STARK proof in a SNARK wrapper to work around this hurdle. Apparently, it eliminates most of the advantages of STARK.
After an in-depth study, the Bitlayer research team proposes a new idea - to use Bitcoin’s low level taptree to commit polynomial, rather than application layer Merkle tree.
7) Taptree is a Bitcoin native utility we can use to commit a polynomial and its folding.
Note that the taptree requires the hash of the left node to be less than the hash of the right node, necessitating an index reference from the Merkle tree to the taptree.
8) After all polynomials from the FRI folding process are committed with taptree, we can continue to build the complete onchain FRI verifier. The verifier is comprised of 2 taptrees:
Bitcommitment Taptree: for operator to reveal all intermediate values shared by segments Verifier Taptree: each leaf represents a segment that can be run with intermediate values as input
In order to ease engineering effort, we extract several reusable primitives that can be embedded in segments:
- FRI folding checker
- Fiat-Shamir Transformation checker
- Inclusion checker
Note that the onchain verifier won’t be run as long as the rollup operator keeps submitting correct data to Bitcoin L1.
9) A challenge game is designed to discourage rollup operator to claim bad rollup state. If one of the watch nodes disagrees with the operator’s claim, this node then kicks off a challenge game instance. The game involves two roles:
GR = Game Responder = Rollup operator node
GC = Game Challenger = Watch node
To respond to a challenge, GR does the following:
Onchain: publish all intermediate values of all segments by revealing bitcommitment pre-images
To disprove one of the segments, GC does the following:
Offchain: inject the intermediate values to Verifier Taptree and check the correctness of each segment
Onchain: for the incorrect segment, run the segment onchain and take GR’s deposit if the challenge succeeds.
10) Please note BF-FRI is not a full-fledged STARK, it will take some time to implement an end-to-end STARK verifier. We are working very hard to bring up a PoC to demonstrate the whole idea. Stay tuned!
Follow us to stay updated on everything Bitlayer:
