Bulletproof++ as generic ZKP à la SNARKs?

Question

My understanding is that the primary usecase for Bulletproof (BP) & Bulletproof++ (BP++) in elements is for range proofs for confidential transactions/confidential assets.

There seems to be a lot of interest in validating Zero-knowledge proofs (ZKPs) in Script, usually to encumber some Bitcoin with the result of some offchain computation. People are playing with (Scalable, Transparent ARgument of Knowledge) STARK verifiers using OP_CAT, trying to do an optimistic verification of SNARKs with BitVM. Bulletproofs are much more compact, and are getting some exploration on Liquid. Could be interesting for Bitcoin if they're useful.

I haven't been able to get all the way through the BP++ paper yet, but it sounds like you could use it for doing arbitrary ZKPs for things like arithmetic circuits. If that's the case, could BP++ be a way to do non-interactive proofs for something like a rollup (the way snarks/starks are being used in other ecosystems)?

Answer 1

SNARKs

To build a zkrollup, we want the ability to verify SNARKs on bitcoin. There are broadly three families of SNARKs in real world use today: those based on pairings and using a trusted setup (Groth16, Plonk, etc.), those based merkle trees and error correcting codes (STARKs, Plonky2, etc.) and those based on Bulletproofs (Halo2). They vary on a bunch of different dimensions (proof size, prover performance, cryptographic assumptions, etc.), and most of this variance comes down to which Polynomial Commitment Scheme (PCS) the protocol uses.

The PCS used by pairing based schemes (ignoring Groth16 since it works differently) is typically KZG which has small constant proof size and verification time. The PCS used by STARKs and other code based SNARKs is typically FRI which has a very fast prover, large O(log^2 n) sized proofs, and similar verifier complexity. Bulletproofs (and BP++) is equivalent to a PCS and results in much smaller proofs than FRI, slightly larger than KZG, but unfortunately has O(n) verifier complexity. People sometimes describe this by saying that Bulletproofs are not "work saving." As a result people tend to use Bulletproofs for small statements, where we want small proofs but don't want a trusted setup (e.g. range proofs).

However, people do use Bulletproof based schemes to construct work saving SNARKs using either accumulation (Halo) or folding (Nova, ProtoStar, etc.). The technical details of how these differ is beyond the scope of the question (usually want folding), but in both cases they use recursion and the algebraic structure of the proofs to combine them so that their combination is valid only if the initial proofs were also valid. Since these SNARKs built out of Bulletproofs and accumulation/folding use recursion, we typically say that they are not "monolithic" SNARKs in order to distinguish them from e.g. Plonk and STARKs. There are no monolithic work saving SNARKs built using Bulletproofs and there are some impossibility results along these lines.

SNARKs on Bitcoin

So in short, yes it is possible to construct work saving SNARKs with Bulletproofs and we could verify these on bitcoin using BitVM. These proofs will have much smaller proofs than FRI based SNARKs and no trusted setup. Concretely, the verifier will be slower and more importantly the bitcoin script for the verifier will be much larger than the script for pairing based SNARKs or STARKs with OP_CAT.

This is because a Bulletproof verifier requires a very large amount of field arithmetic in a big field, which is ridiculously expensive in bitcoin script. We can get away with e.g. Groth16 or Plonk in BitVM because the amount of field arithmetic is simply very small. STARKs are more efficient in bitcoin script given OP_CAT because so much of the verifier complexity involves verifying merkle paths which become almost free given OP_CAT and because they can use small fields.

Apart from quantum resistance, a Bulletproof + Folding based SNARK would arguably be the best suited to bitcoin since it has small proofs, no trusted setup, and efficient batch verification, but unfortunately it is unlikely to be feasible without more softforks.