As a global broadcast consensus system, bitcoin is designed to verify computation — not execute arbitrary computation. The bitcoin blockchain provides the most available global settlement system and the most valuable digital currency, but its functionality is constrained by the limited expressivity of Script. The ability to verify SNARKs efficiently on bitcoin overcomes the existing limitations of Script in a way that’s consistent with the design tradeoffs of bitcoin. Concretely, it lets us create bridging smart contracts on bitcoin which enable moving BTC into and out of offchain (”Layer 2”) systems like rollups that offer significantly improved expressivity, privacy, and scalability.
Typically, bridging BTC relies trusting a majority of signers in a multi-sig, but recent breakthrough line of work starting with BitVM has shown that it is possible to verify general computation on bitcoin under weaker assumptions. Specifically, that it is possible to optimistically verify computation if at least 1 of a set of n validators is honest. This is not equivalent to verifying a SNARK directly on bitcoin, but it is by far the closest thing to this that is currently achievable.
Continuing this line of work we introduce SNARKnado, a new bisection protocol based on BitVM and BitVM2 for verifying SNARKs on bitcoin. We replace the RISC-V abstraction of BitVM with a more circuit-like protocol based on SNARKs, and specifically PLONK. With this optimization, we estimate reducing the number of challenge-response rounds with the SNARKnado bisection protocol to four, offering over an eight-fold improvement to the existing BitVM RISC-V design. However, unlike BitVM2, it does not support permissionless challenging, although the techniques and primitives used in SNARKnado have considerable overlap with BitVM2, and we believe will be relevant in helping resolve some open challenges in the BitVM2 implementation effort.
We aim to first briefly explain BitVM and BitVM2 and their tradeoffs. Then, we introduce SNARKnado which is intended to overcome the two significant limitations of BitVM and BitVM2: the long running time for bisection and the significant onchain costs respectively. Then we discuss some of the tools we need to build SNARKnado. This section is also very relevant for BitVM2.
Overview
BitVM
BitVM refers to both the permissioned bisection protocol introduced by Robin Linus as well as an instantiation of this protocol for a RISC-V virtual machine. It is intended to enable arbitrary optimistic circuit verification “on bitcoin” to overcome the extreme limitations of bitcoin script. The protocol is most naturally described as a two party protocol between a prover and a challenger. This can be generalized to some larger set of challengers, but for simplicity we will consider a single challenger.
In the happy path (normal mode of operation), as with all optimistic protocols, the prover behaves honestly and the challenger does not challenge. Depending on the higher level protocol, the prover may post a relatively small amount of data onchain, for example a Lamport signature of a SNARK, but no interaction between the prover and challenger occurs.
In the unhappy path, the challenger challenges the prover. In this case, one of the two parties has committed fraud: either the prover has lied and the challenger is honest, or the prover is honest and the challenger has lied. If the prover has lied, then they must have carried out some step in the computational trace incorrectly. The bisection protocol essentially allows the challenger to perform a binary search over the trace to identify precisely the first location where the prover has lied. If the prover is honest, this will be impossible for the challenger and the prover will be able to prove their innocence.
The two main shortcomings of BitVM are 1) only a relatively small, predetermined set of parties can initiate a challenge and 2) the bisection protocol can take a large (> 32) number of rounds to terminate. Each of these rounds is subject to a delay, to ensure that the counterparty cannot DoS the bitcoin mempool to prevent the next phase of the protocol. If each round takes a week, running BitVM on a RISC-V program for verifying a SNARK will take over half a year.
BitVM2
BitVM2 is a loosely related protocol to BitVM for accomplishing the same goal: proving arbitrary circuit satisfiability on bitcoin. It also overcomes BitVM’s primary limitation in that it allows permissionless challenging. It does not use bisection, thus reducing the number of rounds as well. In its current instantiation it also does not implement a RISC-V virtual machine. BitVM2 is under active development, but faces significant practical challenges which must be resolved before it can be deployed for SNARK verification.
In BitVM2, a single large bitcoin script is broken down into a number of smaller scripts that fit within bitcoin’s limitations on script size and stack size. Each of these scripts must somehow share state with the other scripts. BitVM2 accomplishes this by having a Lamport signature for all the data input and output from each script. If two scripts equivocate about their inputs and outputs with respect to the rest of the scripts, anyone can provide a fraud proof of this. This is how BitVM2 avoids the permissioned challenger limitation of BitVM.
BitVM2 is able to avoid putting all the scripts onchain by putting them in the leaves of a TapTree. Unfortunately, it is necessary to put all the Lamport signature data onchain, which is an amount of data linear in the number of chunks we break the trace into. There are a number of variables one can tune to try to optimize BitVM2, but ultimately we are left with the following tradeoffs:
- Onchain data costs scale linearly with the number of chunks (vs log for BitVM)
- Chunks cannot be > 4mb and cannot accept more than 1000 “inputs”
- Each input is limited to a relatively small (< 4) number of bits because onchain costs grow exponentially with the number of bits of each input. This is a consequence of the OTS schemes
- Robin’s solution to reduce onchain cost increases set up cost exponentially in the factor of reduction
Together, these limitations seem to require an extraordinarily large amount of onchain communication to verify a pairing based SNARK or to verify a STARK with certain parameters (i.e. large amounts of grinding). See here for some more discussion of this parameter space.
SNARKnado
To address these issues, we present a new protocol: SNARKnado. This protocol uses the same primitives and has the same trust model as BitVM, but removes the RISC-V abstraction. We replace it with an abstraction based on Polynomial Interactive Oracle Proofs (PIOPs) which underly many popular SNARK constructions like STARKs and PLONK. This lets us drastically reduce the number of rounds of the protocol compared to BitVM and likely has implications for BitVM2.
Basing our protocol on PIOPs has several advantages. Firstly, PIOPs are defined over finite fields which aligns better with SNARK verifiers. Rather than attempting to implement finite field operations in a higher level language, compile the implementation to RISC-V, and then verify the instructions in Script, we can just verify the field operations in Script directly.
We could stop there and use a VM with e.g. big integer arithmetic primitive operations, as is done in BitSNARK. However, PIOPs have another advantage: they are in some sense closer to circuits than VMs like RISC-V or BitSNARK. In a VM, any operation can read or write from any memory location, whereas in a circuit the topology is fixed in advance. Intuitively, this should yield some benefit in bisection since each operation is more local. While fixing the topology seems like it would dramatically complicate concrete implementations, we are able to borrow techniques from SNARKs like PLONK to overcome this.
Specifically, we can use random challenges in designing the protocol. Random challenges are ubiquitous in SNARK construction, for example in constructing permutation and lookup arguments. These protocols specifically allow us to completely avoid hardcoding any circuit topology into the bisection protocol. In fact, the only thing we need to bisect over is polynomial evaluation. This simplifies the onchain protocol as well as the implementation effort.
What is a PIOP?
By “PIOP” we mean that the prover will represent the statement that they wish to prove using relations of polynomials. See here for some more details and references. This is in contrast to a sequence of opcodes as in a VM or directly as a circuit. Then, given a univariate polynomial relation, we will check that it holds at a random point. This is sound if the point is drawn from a sufficiently large domain.
As a simple example, which should be pretty familiar if you have investigated how SNARKs work, if we wanted to check that \( a_i b_i = c_i \) for a sequence of values, we would construct polynomials \( a(\omega^i) = a_i, b(\omega^i) = b_i, c(\omega^i) = c_i, z(\omega^i) = 0 \), and \( q(X) = \frac{a(X) b(X) - c(X)}{z(X)} \). To check that \( a(X) b(X) - c(X) = z(X) q(X) \) it is sufficient to check it at a random challenge which we can compute by hashing the polynomials. In our case, this challenge can be computed from the Merkle tree that commits to the witness.
Given the evaluations the challenger checks two things: that the polynomial relation holds and that the polynomial evaluations were carried out correctly. The former is relatively simple as it does not scale with the degree of the polynomials involved. The latter is where one would usually use a Polynomial Commitment Scheme (PCS) and where we will use bisection.
This technique is basically exactly the same as how SNARKs are constructed from (univariate) polynomial commitment schemes. In fact, given a SNARK built using a generic univariate polynomial commitment scheme, we can transform it into an optimistic bitcoin compatible bisection protocol.
Bisecting Polynomials
Bisection for polynomial evaluation is extremely straightforward. Given a Merkle tree committing to the coefficients of a polynomial \( f(X) = \sum_{i=0}^{2^n-1} c_i X^i \) and a purported evaluation \( y \overset{?}{=} f(x) \) the bisection proceeds by splitting the polynomial into its even and odd components. That is, we split \( f(X) = f_0(X) + X f_1(X) \) where \( f_b(X) = \sum_{i=0}^{2^{n-1} - 1} c_{2 i + b} X^{2 i + b} \). The prover will commit to \( y_0 = f_0(x^2) \) and \( y_1 = f_1(x^2) \). If \( y \neq f(x) \) then either \( y \neq y_0 + x y_1 \), \( y_0 \neq f_0(x) \), or \( y_1 \neq f_1(x) \). In the case of \( y_b \) being incorrect, the protocol will recurse on \( f_b(X) \) until the even part is a constant and the odd part is zero. This protocol straightforwardly generalizes to arbitrary reduction factor.
SNARKs in SNARKnado
SNARKnado will be used to verify SNARKs with small proof sizes on bitcoin. Minimizing proof size is important because we need to bit-commit to the proof onchain. In practice, two SNARKs are used for onchain verification: Groth16 and fflonk. These are both pairing based SNARKs with trusted setups and very small proof sizes.
Of the two, Groth16 is smaller (~200 bytes in BN254) but more computationally expensive to verify and fflonk is larger (~600 bytes) but cheaper to verify. Both are based on pairings and require a trusted setup, but fflonk is able to use a universal, updatable trusted setup. This affords greater flexibility and plausibly better security if we update an existing trusted setup. Since BitVM already requires a 1-of-n trust assumption, so long as all the n parties participate in the setup there is no additional trust required beyond what BitVM(2) currently demands.
In-circuit pairing verification is fairly expensive, although recent work has helped to bring that cost down. Specifically the protocol of On Proving Pairings eliminates the final exponentiation and proposes an optimization for more efficient pairing verification when the second argument is fixed, as is the case in fflonk but not Groth16. These optimizations are implemented as part of BitVM2. It additionally builds on the work of Garaga to simplify extension field arithmetic using randomized challenges, which we much more easily use because of the PIOP abstraction.
Pairing and SNARK Overview
We will briefly review the structure of pairing verification and how this is used in fflonk. For more details on pairings, and for details on the specific protocol we will use, see On Proving Pairings.
Pairings are defined over elliptic curves with certain special structure (pairings are actually always defined but are in general prohibitively expensive to compute). They allow us to “multiply” curve points once, where ordinarily we would only be able to add them. This turns out to be incredibly powerful and is the basis for a number of powerful cryptographic protocols like BLS signatures and various SNARKs.
Pairings consist of two parts: the Miller loop and the final exponentiation. In “On Proving Pairings,” the authors are able to almost completely eliminate the cost of verifying the final exponentiation, so we will not discuss it. The Miller loop consists of evaluating a collection of lines and multiplying the results. When computing the pairing \( e(P, Q) \) the lines depend only on \( Q \), and we always evaluate them at \( P \). This means that when \( Q \) is fixed we can precompute all the lines.
All of these multiplications in the Miller loop occur over an “extension field.” This is analogous to the how the complex numbers extend the real numbers. We say the complexes have degree 2 because \( i^2 = -1 \) but in the case of pairings our extension is of degree 12. However, because we are working in the PIOP model, we are able to simplify most of this extension field arithmetic using a random challenge.
Putting it all Together
To prove fflonk using SNARKnado, the prover will first commit to the proof onchain along with a hash of the SNARKnado “witness.” Given a SNARK protocol, e.g. Plonk, this witness consists of a set of Merkle roots for the polynomials, challenges, and polynomial opening values.
When the prover is challenged, they will open this hash revealing all the openings, challenges, and potentially some levels of the polynomial tree. The prover will also provide the sub-polynomial evaluations. The consistency of this level is satisfied if the gate equation for the SNARK is satisfied, if challenges are all correctly constructed, and if the polynomial tree levels are consistent. We can generate the challenges using the Fiat-Shamir transformation using the polynomial merkle roots as prover messages.
Then, the protocol will continue bisecting the polynomial evaluations until it reaches an inconsistent level or a leaf. Once we have reached a leaf, the polynomial evaluation must fail or the challenger was fraudulent. As in all bisection protocols, the challenger is assumed to know the witness, which in this case is a deterministic function of the original proof, so they can tell where any errors in the polynomial evaluation lie.
Estimates
So how much does this actually cost? There are two parts to this question: 1) how much does in-circuit pairing verification cost and 2) how much does the bisection protocol cost. Currently implementation efforts are underway for “On Proving Pairings,” but rough estimates suggest that the multi-pairing verification will cost approximately \( 20-50,000 \) field multiplications. There are degrees of freedom that may let us bring this number lower, but conservatively we can estimate that the whole SNARK verifier will use on the order of hundreds of thousands of gates in the PIOP.
This translates into a bisection protocol over a tree of no more than \( 2^{20} \) leaves. Using a very reasonably sized branching factor \( 32 \), this would require four rounds of bisection and each round would commit to \( (256 + 32) \times 32 \approx 5000 \) bits of leaf data per level. In total, we require double this amount to verify faults in the leaves, which brings the total amount to \( 200,000 \) bytes per level. With a one week round time, this would bring the total time for bisection to under one month if one party is malicious.
Why Not Just Use BitVM2?
Given the similarities, it is natural to ask why we don’t just use BitVM2. In some sense, SNARKnado is like an intermediate protocol between BitVM and BitVM2. In fact, if we used a bisection tree of depth 1 we would actually recover a version of the BitVM2 protocol.
The answer is that BitVM2 is much more sensitive to implementation details like exactly how much computation one can fit into a leaf script. This is because the onchain costs of BitVM2 are linear in the trace length. Having the ability to introduce even a single round of interaction brings this linear scaling down to square root scaling, which in turn gives much more slack in terms of leaf sizes. As the number of rounds increases, the onchain costs decrease with \( O( r n^{1/r}) \) to \( O(\log n) \).
However, we believe the techniques of SNARKnado and development effort will be useful for BitVM2. The set of primitive operations needed for SNARK verification is the same in both protocols, and structuring the computation as a PIOP should also yield simple and efficient instantiations in BitVM2. In this sense, using SNARKnado and BitVM2 are not mutually exclusive. If we can get the in circuit pairing verification cheap enough and onchain costs low enough we can get permissionless challenging with SNARKnado. BitVM2 + SNARKnado = SNARKnado2?!
