Bulletproofs pre-release

We’re excited to announce a pre-release version of our Bulletproofs implementation, providing a stable interface for creating and verifying range proofs, an important building block for a range of privacy-preserving protocols. For instance, range proofs are important for confidential transaction systems, such as Confidential Transactions for Bitcoin, Chain’s Confidential Assets, and many other protocols, because a verifier can check that secret values, such as asset amounts, are nonnegative.

As we described a few months ago, our implementation is implemented in pure Rust using the Ristretto group; our previous post has more detail and background information. Since then, we improved performance slightly, pushing verification performance down to 1040 µs for a 64-bit range proof. For comparison, this is:

• 1.83x faster than the libsecp implementation (with endomorphisms);
• 2.00x faster than the libsecp implementation (without endomorphisms);
• 4.63x faster than the Monero implementation.

In addition to better performance, we also provide a clean, safe, and extensible API for both single-party proving as well as multi-party computation of aggregated proofs. The single-party proving is actually implemented by self-MPC internally, to avoid code duplication.

This post shares some details of our design and says a few words about the next version of Bulletproofs, that will provide a constraint system API to allow proofs of arbitrary statements.

Composable proof transcripts

Our implementation performs the Fiat-Shamir transform using Merlin transcripts. This provides per-application domain separation, since constructing a transcript requires passing a domain separation label. It also means that it’s possible for users of our API to bind the Bulletproofs to arbitrary structured data (by committing it to the transcript prior to proving), or to compose the Bulletproofs with other proof statements (by using a common transcript for both proofs), all without any changes to our implementation.

But this also has benefits in the implementation internals. To create a range proof, Bulletproofs first performs a protocol which reduces the statement about ranges to a statement about inner-products, and then performs an inner-product proof. Instead of implementing these logically distinct components together, using Merlin transcripts allows us to implement them separately internally, and compose the two parts into a single proof returned to the user. This makes the implementation significantly cleaner and easier to understand, because the software components of the implementation correspond to the conceptual components of the protocol. You can learn more about Merlin in this overview, or in its docs.

Strongly-typed multiparty computation

As described in our previous post, we take advantage of Rust’s type system and ownership semantics to implement the multiparty computation (MPC) protocol, by encoding each state of the MPC protocol using a different Rust type, and using ownership semantics to enforce that state transitions are not reversible.

For instance, in the MPC protocol for aggregated range proof creation, each party constructs a vector polynomial and reveals the result of its evaluation at a single challenge point to construct its proof share. However, if the party could be tricked into revealing multiple evaluations of the same polynomial at different points, it would be possible to recover the original polynomial and reveal the party’s secrets.

But this is impossible in our implementation: evaluation is performed by the apply_challenge method of the PartyAwaitingPolyChallenge state, which consumes the state and returns a ProofShare. Because Rust’s ownership model prevents the use of moved values, it’s not possible to call apply_challenge twice, because the original PartyAwaitingPolyChallenge is already consumed. Similarly, because each state transition is performed by a method on a particular type, it’s not possible to perform the steps in the wrong order.

In other words, the type-checking and borrow-checking performed by the Rust compiler provide a compile-time proof that any instantiation of the MPC protocol components is one that performs the protocol steps correctly.

Extensible generator chains

The Bulletproofs paper describes the aggregated range proof protocol for m parties proving n-bit ranges as operating on two vectors of generators, G and H, both of size m*n. But implementing the proofs in this way would mean that the generators would be tied to both the aggregation size as well as the bitsize. And this approach isn’t extensible to the constraint system case, where the number of generators required depends on the number of constraints, which might not be known in advance.

Instead, we construct generators for each aggregation party separately, feeding a per-party domain separation label into the SHAKE extendable-output function (XOF), and passing the SHAKE output into the ristretto255 hash-to-group function. This provides an arbitrarily-long chain of orthogonal generators unique to each party. Instead of viewing G and H as vectors of size m*n, we view them as concatenations of m slices of the first n generators for each party. In other words, we construct the m*n generators by taking rectangular sections of a 2D array of generators, with the vertical axis corresponding to the number of parties and the horizontal axis corresponding to the size of each party’s proof share.

This means that a single cache of pre-computed Bulletproofs generators can be used with multiple choices of aggregation size and bitsize, and it’s also future-compatible with more flexible aggregation — for instance, there’s no need for the parties to be assigned contiguous rows in the grid.

For constraint system proofs, the number of generators required depends on the number of constraints. If the constraints are programmatically defined, it may not be convenient to specify the number of constraints up-front, but this construction allows the constraint system to just pull an appropriately-sized slice of generators from a pre-computed cache. And, because the generator chain is domain-separated by a per-party label, it also means that single-party constraint system proofs can be forward-compatible with a multiparty protocol for aggregated constraint system proofs (and even compatible with aggregation of proofs of different statements).

Finally, we also took care to ensure that the generators used for the inner-product argument in Bulletproofs are handled separately from the generators used for Pedersen commitments, so that the choice of Pedersen generators can be made per-application, in order to maximize reusability.

Next steps: arbitrary proofs via constraint systems

The building blocks we described above now allow us to extend the proving system from range proofs to arbitrary user-defined statements.

Bulletproofs are an optimization to an earlier paper by Bootle, Cerulli, Chaidos, Groth, and Petit, which showed that it was possible to prove arithmetic circuit satisfiability in the discrete log setting. Their paper introduced the logarithmic-sized inner-product argument, as well as a technique to convert an arithmetic circuit into a constraint system. The Bulletproofs paper optimizes the inner-product argument by a constant factor, and shows how to use Pedersen commitments as inputs to the circuit.

We’ve been working on an API for building Bulletproof constraint systems directly, inspired by the Bellman API used in Zcash, which allows both the prover and verifier to programmatically define a constraint system and then create a proof (or verification). We’ll have more to share in a future blog post, but we’d like to thank Sean Bowe, Daira Hopwood, and Jack Grigg from the Zcash team, as well as Mary Maller from University College of London, for their helpful suggestions and discussion.