In this article, we will discuss the current state of SNARK verification using BitVM2. We'll begin with an introduction to SNARK verification in bitcoin and explain how BitVM2 fits into this context. Then, we'll explore the main cost drivers of this design and provide concrete numbers on the costs. We'll put these costs into perspective by examining a BitVM2 bridge design, exploring known limitations, and considering possible improvements.
SNARK verification in bitcoin
SNARKs allow us to represent a large set of statements with concise proofs that are small in size and quick to verify. This is particularly beneficial for bitcoin, where transaction fees scale with the size of the transaction in bytes—the larger the transaction, the higher the fee. While SNARKs like Groth16 offer short CRS, small proofs, and fast verification, translating a Groth16 verifier into bitcoin Script for miners to natively verify these proofs presents a challenge. For instance, mapping a Groth16 verifier over the bn-254 field generates a massive script, roughly 1.2 GB in size. This large script size stems mainly from two reasons:
- Lack of native big integer arithmetic: bitcoin operates over large finite fields. However, bitcoin Script does not natively support big integer operations. This makes it difficult to directly perform the field arithmetic required for SNARK verification.
- Limited script capabilities: bitcoin Script is deliberately not Turing-complete, and its limited set of opcodes restricts the complexity of operations.
Since bitcoin has a block size limit of 4 MB, such a large script must be executed over multiple transactions. These challenges make direct SNARK verification on bitcoin highly impractical. This is where BitVM2 offers a solution, significantly reducing the onchain footprint by introducing interactivity and offchain computation!
Introducing BitVM2
The BitVM2 protocol enables the optimistic verification of arbitrary computations on bitcoin. The protocol operates under the assumption that the prover is honest unless proven otherwise. If a prover makes a false claim, a challenger—in a permissionless manner—is incentivized to submit a fault proof. The validity of the claim is then determined through a few rounds of interaction between the prover and the challenger.
BitVM2 begins by generating a SNARK of an arbitrary computation. The protocol then efficiently encodes the SNARK verifier in bitcoin Script using Taproot trees. By shifting some of the computational burden to the challenger during the challenge-response game, the onchain footprint is significantly reduced. Our estimates suggest the following onchain costs for the prover and the challenger:
- Prover's onchain commitment: ~4.8 MB
- Challenger's onchain commitment: ~4 MB
This is substantially smaller than executing a ~1.2 GB script directly onchain. Importantly, these on chain costs are only incurred if the prover has made an incorrect claim; otherwise, the claim is accepted without contest.
To better understand this, let's dig deeper into how the challenge-response game is set up in BitVM2 and how it plays out during the optimistic SNARK verification.
There are four core steps of the BitVM2 protocol:
- Claim Transaction (Claim Tx): The prover makes a claim by committing to the correct execution of the SNARK verifier. It also includes a stake to incentivize disproving the claim if it's false. At a minimum, the stake should cover the cost of disproving.
- Challenge Transaction (Challenge Tx): A challenger who believes the claim is incorrect can submit a challenge. This forces the prover to reveal intermediate values of the SNARK verification to assert that their claim is valid. The challenger includes compensation to cover at least the cost for the prover to submit this data. Otherwise, a malicious challenger could cause an honest prover to pay fees even for honest claims.
- Assert Transaction (Assert Tx): The prover submits intermediate values of the SNARK verification to demonstrate the validity of their claim. If these values are correct, no one can disprove the assertion.
- Disprove Transaction (Disprove Tx): If the prover made a false claim, then one of those intermediate values must be invalid. Anyone can find that value and submit a fault proof claiming that the execution of the SNARK verifier is invalid.
The stake that the prover must put up in the Claim transaction should be greater than the cost of submitting a fault proof in the Disprove transaction, while the stake that the challenger must put up in the Challenge transaction must be greater than the cost of submitting intermediate values in the Assert transaction. Note that the stake in the Claim transaction must be provided even if the prover is not challenged, unlike the stake in the Challenge transaction.
Cost drivers in BitVM2
The main cost drivers in the BitVM2 protocol are the costs of the Assert and Disprove transactions during the challenge-response game. These costs directly depend on the bitcoin Script implementation of the SNARK verifier program. Over the last few months, we have seen a tremendous amount of work being done to reduce the script size for these transactions. Major improvements have come on two fronts:
- SNARK protocol optimizations: Our On Proving Pairings paper showed several optimizations, including replacing the final exponentiation with an efficient residue check, using affine coordinates efficiently, and using precomputed line coefficients when second pairing argument is fixed. Together, these changes have dramatically reduced the script size.
- Improved cryptographic primitives: Optimizations in field multiplication (our TMUL) and hashing algorithms have also significantly decreased the overall script size.
Thanks to the collective work of the community—including many teams and individual contributors—the size of the Groth16 verifier has dramatically decreased from around 7 GB to ~1.2 GB in just a few months.
Besides the SNARK verifier script size, another critical factor influencing costs in the BitVM2 protocol is how the script is divided into chunks. Our goal is to split the script into chunks of size less than 4 MB in a manner that minimizes the number of intermediate values while adhering to stack and script limitations. We conducted a detailed breakdown of the Groth16 verifier script for the BitVM2 protocol, setting a concrete baseline for future improvements.
Although we are continuously reviewing and refining these estimates, the current onchain costs associated with the BitVM2 protocol, as of October 3, 2024, are as follows:
- Number of bit-commitments: 611
- Assert Transaction size: ~4.8 MB (using 4-bit script-optimized WOTS)
- Disprove Transaction size: 3.5–4 MB (using 4-bit stack-optimized WOTS)
For a complete breakdown of how these numbers were obtained, please refer to our detailed document.
Given these numbers—which, to the best of our knowledge, represent the current state of the art—let's see how the BitVM2 protocol fits into one of its prominent use cases: a BTC bridge.
BitVM2 Bridge
In a BitVM2 bridge, the bridge operator initially processes a user's withdrawal request by making a front payment. To be reimbursed for this service, the operator submits a claim specifying the transaction ID used to pay the user. Observers can monitor the blockchain and challenge the operator's claim if it is invalid—either because no payment was made or the L2's state does not reflect a valid withdrawal request. The BitVM2 framework enables anyone to dispute the operator's reimbursement request.
Assert transaction is compensated from an altruistic source
Reducing the size of the verifier program and its intermediates helps decrease the size of the Assert transaction. This is important because the Challenge transaction, which compensates for the cost of the Assert transaction, is assumed to be provided by an altruistic source. That is, the challenger receives nothing unless they can disprove the operator's claim. A smaller cost makes this altruistic challenge assumption more acceptable.
This assumption is reasonable because the Challenge–Assert–Disprove path only begins if the operator is faulty. The incentives are aligned so that the cost of making an incorrect claim is substantial.
Disprove transaction is compensated by the upfront cost
The cost of submitting a Disprove transaction is staked in the Claim transaction by the prover. This applies to a single withdrawal request. Multiple operators must be able to serve this withdrawal request as fallback operators. Therefore, the total amount that must be staked for serving W withdrawal requests with N operators is N × W times the cost of a single Disprove transaction.
This staking occurs when a user makes a bridge-in (deposit) request and cannot be freed until a bridge-out (withdrawal) fulfillment is reimbursed. This results in a large liquidity requirement for the operator over an extended period. Solving this capital overhead problem remains an active area of research.
BitVM2 bridge improvement considerations
We have discussed how optimizing the Script implementation of the Groth16 verifier allows us to build a more cost-efficient bridge. However, there are several other design paths we can explore to further enhance bridge construction.
1. Balancing Disprove and Assert transactions
Reducing the size of the Disprove transaction below the current 4 MB assumption could lead to a substantial increase in the Assert transaction size. Achieving an efficient balance between these transactions is challenging because reducing chunk sizes increases the number of intermediate values that require bit-commitment.
For example, halving the size of the Disprove transaction (from 4 MB to 2 MB) may more than double the number of bit-commitments. We encountered similar issues when offloading computation in the Point Doubling tapscript to the Squaring tapscript. Therefore, decreasing the size of the Disprove transaction may not provide significant benefits in this case.
2. GKR proof of Groth16 verifier
The Groth16 verifier is primarily composed of pairing checks, which can be represented as a layered arithmetic circuit with repeated local structures. This helps reduce the cost of wiring predicates and makes it possible to represent the circuit as a data parallel structure.
This approach avoids hashing intermediate values and requires fewer multiplications per tapscript, resulting in a smaller Disprove transaction that fits within bitcoin's standard transaction size limit (<400 KB). However, the downside is a larger non-deterministic proof, which increases the Assert transaction size. Current estimates suggest:
- Assert transaction bit-commitments using GKR: ~3,000 (potentially reducible to ~1,000 with further optimization)
- Assert transaction bit-commitments using Groth16: ~500
The Disprove transaction must always be covered by the Claim transaction stake, regardless of challenges, while the Assert transaction incurs costs only if challenged. This approach can reduce capital overhead by 90% in common, unchallenged cases at the expense of doubling the L1 footprint in the rare event of a challenge.
3. Throttling withdrawals
Another way to reduce high staking requirements is to rate-limit the number of withdrawals an operator can process within a specified time frame. This method uses a chain of transactions that carry over stake from one claim to the next. With many operators, each limited to, for example, one withdrawal per month, the overall processed volume grows with the number of operators.
Although the liquidity requirement has been reduced, it introduces an artificial constraint on the number of deposits that can be processed in parallel at any given time.
4. Claim/Withdrawal Trees
This method proposes eliminating capital requirements per deposit by introducing Claim and Withdrawal transaction trees. Instead of requiring operators to stake funds proportional to deposits, the tree structure efficiently handles challenges, reducing the challenge cost from linear to logarithmic relative to the number of deposits. This approach removes per-deposit staking requirements and fosters a competitive fee market for processing withdrawals, allowing any operator to initiate withdrawals at any time.
Outlook
Over the past few months, we've witnessed significant progress with the BitVM2 protocol, driven by a collective community effort. We are proud to be at the forefront of these advancements in both research and engineering. We hope this blog has provided you with a clearer understanding of SNARK verification with BitVM2 and its implications for bitcoin bridge designs. Your feedback and contributions are invaluable as we work towards an even more efficient and secure BitVM2 protocol.
References
- BitVM2: Bridging Bitcoin to Second Layers
https://bitvm.org/bitvm_bridge.pdf - On Proving Pairings
https://eprint.iacr.org/2024/640.pdf - Optimized Field Multiplication (TMUL)
https://github.com/BitVM/BitVM/pull/87 - Groth16 Verifier Breakdown
https://www.notion.so/122d103273eb4a5f9f09a25fcfe9440c
