Programmable Constraint Systems for Bulletproofs

Published in

Interstellar

7 min readNov 19, 2018

We are excited to share our progress on extending our Bulletproofs implementation with a constraint system API which enables zero-knowledge proofs of arbitrary statements.

In our previous article, we announced a pre-release of Bulletproofs 1.0, the Rust implementation of range proofs. We (Cathie Yun, Henry de Valence and Oleg Andreev) have been working on extending it to support proving arbitrary statements in zero knowledge using a constraint system, which we would like to share with you today. We are also excited to publish our work on the next generation of Chain’s Confidential Assets protocol called Cloak, which builds directly on top of these Bulletproofs constraint system proofs.

Constraint System

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 rank-1 constraint system (R1CS). The Bulletproofs paper optimizes the inner-product argument by a constant factor, and shows how to use Pedersen commitments as inputs to the constraint system.

R1CS expresses linear combinations of various variables and their multiplications. The Bulletproofs paper uses the following format for the constraint system: an array of n multiplications that gives 3*n low-level variables: left, right and output “wires” of each multiplication “gate”, and an array of q linear constraints between these variables and additional m high-level variables that represent external facts.

We realized that it is more efficient to bypass arithmetic circuits altogether and provide the API for building a constraint system directly. This way we do not have to construct the graph or arithmetic expressions and then transform them into constraints: higher-level protocols can often keep that graph represented statically by their source code and build constraints on the fly.

Moreover, since the matrices representing the constraints are usually very sparse, we only store the non-zero terms. The only operation that needs to be done on the constraints is flattening with a challenge variable, and the result is defined solely by the non-zero terms.

Variables

The constraint system has three kinds of variables: high-level witness variables, low-level witness variables, and instance variables.

Instance variables are public parameters, known to both the prover and the verifier. In other proving systems that require a setup for each constraint system, this allows public inputs to the circuit. In Bulletproofs, no setup is required, so there’s no difference between a constraint system with public inputs and a family of constraint systems parameterized by those inputs. This means we can internally fold all instance variables into a single constant parameter.

High-level witness variables are known only to the prover, and represent external inputs to the constraint system. In Bulletproofs, these are represented as individual Pedersen commitments to the external variables, for which we construct and prove some relation. For instance, in the Cloak protocol (described below), the transacted amounts are represented as commitments to high-level variables.

Low-level witness variables are known only to the prover, and are internal to the constraint system, representing the inputs and outputs of the multiplication gates. For instance, in Cloak these represent bits inside a range proof or intermediate amounts as they are passed through shuffle, merge and split stages. Low-level variables are computed per-proof and committed using a single vector Pedersen commitment.

Challenges

As noted above, instance variables can select the constraint system out of a family for each proof. This enables a novel approach: by generating some of them as a challenge from a verifier to a prover, the constraint system itself can be thought of as a challenge from a verifier to a prover, where some constraints are generated randomly in response to the prover’s commitments.

The use of challenges to parametrize constraint systems can enable significantly fewer multipliers, which makes the resulting proof smaller. For instance, a verifiable shuffle may require O(n²) multiplications in a static constraint system, but by using challenges we reduce the overhead to O(n) multiplications — inputs and outputs can be used as permuted roots of the polynomials that are randomly sampled at a challenge point and constrained to be equal:

{a,b} = {c,d} ⟺ (a−x)⋅(b−x)=(c−x)⋅(d−x)

Our implementation performs the Fiat-Shamir transform using Merlin transcripts to generate such challenges. The challenges are bound to the high-level variable commitments which are added to the transcript before any of the constraints are created. Then, the prover and verifier can compute weights for some constraints with the use of the challenges.

The use of challenges comes with an important caveat: the challenges are bound only to the high-level witness variables (the external inputs to the constraint system), not the low-level ones, so it requires careful analysis to ensure that the construction is safe. That said, we are working on an improvement to the protocol that would allow challenges to be bound to a subset of the low-level witness variables, and have a safer API using features of Rust’s type system.

Gadgets

The resulting API is largely inspired by the Bellman API used in Zcash: there is a single code path used by both the prover and verifier to allocate variables and define constraints, organized into a hierarchy of task-specific “gadgets”. This way the allocation, assignment and constraints on the variables all happen in one place, providing assurance that variables are not accidentally left unconstrained. In other words, each gadget can be verified independently, without having to analyze correctness of the entire constraint system as a whole (see also the caveat about challenges in the previous section).

Each gadget is a function that interacts with a mutable “constraint system” object represented by a trait. The prover and verifier use their specific implementations of this trait respectively. The gadget receives secret variables and public parameters, allocates and assigns variables, generates challenges and adds constraints to the constraint system object.

Gadgets can be composed. For instance, in the Cloak protocol, a “merge” gadget takes M inputs and M outputs and calls a sequence of M-1 “mix” gadgets that operate on pairs of values. Then, the whole collection of gadgets in Cloak is abstracted away with a single “transaction” gadget that takes all input and output values, which could be used either directly or as a part of a higher-level protocol.

The Bulletproofs library does not provide any standard gadgets, but only an API for the constraint system. It is the job of each protocol on top of it to create a collection of gadgets for its use and build a complete constraint system out of them. For an example of a protocol built using a collection of gadgets, see our Cloak implementation (described below).

Cloak

Cloak is the redesign of the Chain’s Confidential Assets scheme using Bulletproofs. We are making its implementation open source and calling it Spacesuit as in interstellar cloak.

Cloak is focused on one thing: proving that some number of values with different asset types is correctly transferred from inputs to outputs. Cloak ensures that values are balanced per asset type (so that one type is not transmuted to any other), that quantities do not overflow the group order (in other words, negative quantities are forbidden) and that both quantities and asset types are kept secret. Cloak does not specify how the transfers are authenticated or what kind of ledger represents those transfers: these are left to be defined in a protocol built around Cloak.

Cloak builds a constraint system using a collection of gadgets like “shuffle”, “merge”, “split” and “range proof” all combined together under a single gadget called a “cloaked transaction”. The layout of all the gadgets is determined only by the number of inputs and outputs and not affected by actual values of the assets. This way, all transactions of the same size are indistinguishable.

Bulletproofs constraint system turns out surprisingly efficient: compared to a single-asset transaction (such as the Confidential Transactions proposal for Bitcoin) where only range proofs are necessary, the additional constraints and gadgets needed to support the issued assets add less than 20% of the multipliers. And thanks to the inner product proof, the impact on the proof size is close to zero.

The work on Cloak and Spacesuit is far from complete, and now will continue in the open in our repository. To learn more about Cloak check out its specification.

Next steps

The work on constraint systems and Cloak is still ongoing. For the R1CS implementation, there are two major improvements that we will focus on:

First, we would like to extend the Bulletproofs protocol slightly, to enable committing to a portion of low-level variables using a single vector Pedersen commitment without an overhead of additional individual high-level Pedersen commitments. This will also come with a change in the API that would ensure that challenge-based variables cannot be inspected, preventing the user from accidentally breaking soundness of their gadgets.

Second, we want to enable multi-party proving of a single constraint system. This is different from the existing aggregation MPC that we’ve done for the range proofs: instead of aggregating proofs of distinct statements purely to make proofs smaller, we want to enable building a joint proof of a single constraint system by multiple parties, without sharing their secret inputs with each other. This not only makes the proofs smaller, but could also improve privacy in Cloak by enabling a zero-knowledge version of a CoinJoin protocol.

Thanks

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.