Simulating Bulletproofs Under Adaptive Corruptions

A zero-knowledge proof [GMR85] allows a prover to convince a verifier that a public statement $\stmt$ of an NP-relation is true without revealing the corresponding witness $\wit$. For example, $\stmt$ may be a public key $\stmt=g^\wit$, where $g$ generates a group of prime order $p$ and $\wit$ is the secret key. A zero-knowledge proof could then convince the verifier that the prover knows the secret key, without revealing any information besides the already known public key $\stmt$. In this post we are particularly interested in non-interactive zero-knowledge proofs, or NIZK [BFM88], which allow the prover to generate such a proof $\pi$ without interacting with the verifier.

In cryptography, we formalize the promise that a proof ‘‘reveals no additional information’’ through simulation. We say a proof is zero-knowledge if an efficient algorithm (called a simulator) that only knows a statement $\stmt$ but does not know the witness $\wit$ can produce valid proofs that no efficient verifier can distinguish from an honest proof. Whatever the verifier learns from an honest proof, it could then also have learned from a simulated proof, which carries no information about the witness to begin with.

At first glance, this definition seems paradoxical, since if a simulator can produce valid proofs without knowing the witness, why should a proof convince a verifier? The answer to this question is called a trapdoor, a piece of secret information that the simulator in a security proof knows and lets it simulate proofs. At the same time, no real prover has access to the trapdoor, so proofs from a real prover are sound (can only be computed when knowing a valid witness). For Fiat–Shamir-based proofs [FS86], which are the subject of this post, the simulator’s trapdoor is the power to program the random oracle [BR93], which is of course not possible in real instantiations.

This simulation property is useful when proving the security of a larger protocol, where NIZKs are used as a building block. Throughout the security proof of such a higher-level protocol, the reduction can first use the NIZK’s simulator to generate proofs without knowing a valid witness, and then embed a challenge element in the NIZK’s statement. With our example NIZK of secret-key knowledge, this would allow the reduction to embed a discrete-logarithm (DLog) challenge element into the public key while still producing accepting proofs of knowledge of the secret key. If the adversary breaks the modified protocol, the reduction uses this break to compute the discrete logarithm of the embedded element. Since replacing honest proofs with simulated ones results in an indistinguishable view for the adversary, any adversary that breaks the real protocol can also be used to break the modified protocol, which in turn allows solving DLog. Because DLog is assumed to be hard, no such adversary can exist.

This proof technique is standard in cryptographic literature and yields secure higher-level protocols under static corruptions, where the adversary chooses which parties to corrupt before the protocol starts. Under static corruptions, the reduction must only simulate the remaining honest parties. Additionally, these honest parties stay uncorrupted throughout the execution and the reduction never has to reveal the internal state behind their simulated proofs. For this part of the security argument, producing indistinguishable proofs is sufficient.

However, static corruptions are not a very realistic corruption model, as in practice adversaries typically do not announce prior to a protocol start which parties they eventually will corrupt. Therefore, as a more realistic corruption model, cryptographers use adaptive corruptions [CGJKR99], where the adversary can choose parties to corrupt during the execution of a protocol, based on the protocol messages it has already seen. If the adversary decides to corrupt such a party, then the reduction has to provide all secret information in the state of this party (including all the randomness used so far). The gap between static and adaptive corruptions might seem small at first sight, but adaptive corruptions have a big impact on the way we can do security proofs. For example, an adversary could wait until all honest parties have published a NIZK, and then decide to corrupt a random party afterwards.

While this might not necessarily help the adversary to break the protocol, it can give it the power to complicate our proof. For example, if we want to use the proof strategy discussed above, we cannot simply replace all honest proofs by simulated ones, since the reduction has to reveal the randomness behind a simulated proof as soon as its prover is corrupted. The adversary can check that this randomness is consistent with the public transcript by running the honest prover again. A simulated proof, however, was produced without the witness, and the random choices of the simulator need not be valid coins for the honest prover. Even if the witness becomes available upon corruption, the proof is already fixed and cannot be replaced. Thus, indistinguishability of the proof alone no longer suffices.

There are three ways around this problem. First, the reduction can guess in advance which parties the adversary will corrupt. It then computes the proofs of these parties honestly (it knows their witnesses, since it embeds the challenge only in the statements of the others) and simulates the remaining proofs. If the guess turns out to be wrong, the reduction aborts. For a single corruption among $n$ parties, this costs a factor of $n$ in the success probability of the reduction, which is still polynomial. Threshold protocols, however, allow the adversary to corrupt up to $t$ of the $n$ parties, and if it corrupts $t$ of them at random, a guess of this set is correct only with probability $1/\binom{n}{t}$. For $n=100$ and $t=50$, the reduction thus loses a factor larger than $2^{96}$, which makes the security bound meaningless.

Second, honest parties can use secure erasures [CGJKR99] and delete the randomness of a proof directly after sending it. A later corruption then no longer reveals this randomness. This, however, is an additional assumption on how honest parties are implemented.

Third, the reduction can simulate all proofs anyway and, once the witness becomes available upon corruption, try to reconstruct randomness that makes the honest prover output exactly the proof it already published. For this post we can simply assume that the reduction obtains a valid witness for the statement of a corrupted party, since upon corruption the reduction must hand over the witness as part of the party’s state anyway.

Reconstructing the prover’s state#

Because we do not want to additionally assume secure erasures, and also cannot efficiently guess which parties the adversary will corrupt, we take the third way. This means that we want to reconstruct randomness for a simulated proof given a valid witness.

If a reduction is able to reconstruct the prover’s state behind a simulated proof, this fixes the gap in the sketched adaptive security proof of the higher-level protocol. Throughout the security proof of the higher-level protocol, the reduction can again first use the NIZK’s simulator to generate proofs without knowing a valid witness, and then embed a challenge element in the NIZK’s statement. When the adversary corrupts a party, the reduction obtains this party’s witness, uses it to reconstruct the randomness behind every proof the party has published, and returns this randomness as part of the party’s internal state.

We formalize this property as honest prover state reconstruction, following Groth, Ostrovsky and Sahai [GOS06].

Note that in the simulated experiment the witness reaches only $\mathrm{Rec}$, after $\mathrm{Sim}$ has already fixed the proof, which is what happens in our sketched security proof upon a corruption. In addition, besides reproducing the proof, the reconstructed randomness must also be distributed like honest coins, to ensure that the adversary’s view with reconstructed randomness is indistinguishable from a real view.
For Fiat–Shamir proofs, the adversary re-runs the prover against the same random oracle, so the randomness has to reproduce the proof under the answers the simulator programmed. Additionally, we allow the reconstruction algorithm to use the simulator’s retained state, which includes every random-oracle answer the simulator chose, and ask it to reconstruct randomness only for proofs that this simulator produced.

State reconstruction for Schnorr proofs#

The goal of this post is to show that Bulletproofs have honest prover state reconstruction. As a warm-up example, we first recall how to reconstruct the prover’s state for Schnorr proofs [Sch91], again for a Schnorr proof of knowledge of the secret key $\wit$ for a public key $\stmt=g^\wit$. Recall that to compute such a Schnorr proof, the prover samples a random element $r\sample\ZZ_p$, sends $A=g^r$, and answers the challenge $c=H(\stmt,A)$ with $z=r+c\wit$. To simulate such a proof, the simulator samples $(c,z) \sample \ZZ_p^2$ uniformly and sets $A=g^z\stmt^{-c}$, which satisfies the verification equation $g^z=A\stmt^c$. It then programs the random oracle to return $c$ on input $(\stmt,A)$, provided that this input has not already been queried.

Our argument naturally generalizes to other Schnorr-type proofs whose responses are linear in the witness, such as proofs of equality of discrete logarithms or of knowledge of a Pedersen opening, where the reconstruction algorithm subtracts the challenge times the witness from each response.

For Schnorr proofs, randomness reconstruction is possible, so they can be simulated in adaptive protocols without assuming secure erasures upon corruption. However, a Schnorr proof sends one response per secret value, so the proof size grows linearly with the witness. To make protocols that use NIZKs for large witnesses more efficient, one can use Bulletproofs [BBB+18] instead of Schnorr proofs. In contrast to Schnorr, Bulletproofs grow only logarithmically in the witness size, but similar to Schnorr, need no trusted setup and rely only on the discrete-logarithm assumption.

Pedersen commitments#

Before we turn to Bulletproofs, we need one more building block, namely Pedersen commitments [Ped91]. Intuitively, a commitment scheme works like a sealed envelope. In the commit phase, a committer puts a value $m$ into the envelope and hands it to a receiver, who cannot look inside. In the opening phase, the committer reveals $m$, and the receiver checks that this is indeed the value in the envelope, so the committer cannot change its mind in between. Proof systems use commitments to let the prover fix a value before it sees the verifier’s challenge, without revealing the value already.

To compute a Pedersen commitment to a single value, we need a second generator $h$ of our group. To commit to $m\in\ZZ_p$, the committer samples a random $\rho\sample\ZZ_p$ and sends $C=g^mh^\rho$. To open the commitment, it reveals $m$ and $\rho$, and the receiver checks that $C=g^mh^\rho$.

A commitment should satisfy two properties. First, it should be hiding, which means that $C$ reveals no information about $m$. For Pedersen commitments, this holds since for every pair of values $m \neq m'$ and every $\rho$, there is exactly one $\rho'$ with $g^mh^\rho=g^{m'}h^{\rho'}$. Every commitment could thus equally well contain any other value, and since $\rho$ is uniformly random, $C$ has the same distribution no matter which value it contains. Second, it should be binding, which means that the committer cannot open $C$ to a different value later. If it could, it would know two openings $(m,\rho)$ and $(m',\rho')$ with $m\neq m'$ and $g^mh^\rho=g^{m'}h^{\rho'}$, from which it could compute the discrete logarithm $\log_h g=(\rho'-\rho)/(m-m')$. Pedersen commitments are thus binding as long as the discrete-logarithm assumption between $g$ and $h$ holds.

On the other hand, Pedersen commitments are equivocable. This means that anyone who knows $\nu=\log_h g$ can compute the randomness $\rho'=\rho+\nu(m-m')$ from the hiding property, and thus open a commitment $C=g^mh^\rho$ to any other value $m'$. We call $\nu$ the trapdoor of the commitment. Just like the simulator’s trapdoor for proofs, this trapdoor will become important later. Another interesting property of Pedersen commitments is that they allow us to commit to whole vectors $\mathbf m\in\ZZ_p^n$ at once in a single group element. This works by using one generator per entry via $C=h^\rho\prod_ig_i^{m_i}$. Such a vector commitment is binding as long as nobody knows a discrete-logarithm relation between the generators, and anyone who knows the discrete logarithms of all generators to the base $h$ can again open it to any vector. To make sure that only a security reduction, but no real protocol participant knows such a relation, one typically derives all generators through the random oracle by hashing public labels [BBB+18].

Bulletproofs#

At their core, Bulletproofs use an inner-product argument (IPA), which proves that two committed vectors have a given inner product. More formally, for generators $\mathbf g=(g_1,\ldots,g_n)$, $\mathbf h=(h_1,\ldots,h_n)$ and $u$, and writing $\mathbf g^{\mathbf a}=\prod_i g_i^{a_i}$, the prover of an IPA shows that it knows vectors $\mathbf a,\mathbf b\in\ZZ_p^n$ with $P=\mathbf g^{\mathbf a}\mathbf h^{\mathbf b}u^{\langle\mathbf a,\mathbf b\rangle}$ for a public group element $P$. Inner-product arguments are a powerful tool for NIZKs, because many statements are inner products. Evaluating a committed polynomial with coefficient vector $\mathbf a$ at a point $z$, for instance, is the inner product $\langle\mathbf a,(1,z,\ldots,z^{n-1})\rangle$, and the constraints of an arithmetic circuit can be checked all at once through a random linear combination that collapses them into a single inner product [BCC+16].

To prove an inner product without sending $2n$ field elements, Bulletproofs use the split-and-fold technique of [BCC+16, BBB+18]. It splits both vectors into halves $\mathbf a_1,\mathbf a_2$ and $\mathbf b_1,\mathbf b_2$ and, for a challenge $x$, folds them into $\mathbf a'=x\mathbf a_1+x^{-1}\mathbf a_2$ and $\mathbf b'=x^{-1}\mathbf b_1+x\mathbf b_2$ of half the length, whose inner product is $\langle\mathbf a',\mathbf b'\rangle=\langle\mathbf a,\mathbf b\rangle+x^2\langle\mathbf a_1,\mathbf b_2\rangle+x^{-2}\langle\mathbf a_2,\mathbf b_1\rangle$. The folded vectors thus satisfy the same relation once the two cross terms $\langle\mathbf a_1,\mathbf b_2\rangle$ and $\langle\mathbf a_2,\mathbf b_1\rangle$ are accounted for. To account for these cross terms, the prover computes the two group elements $L=\mathbf g_2^{\mathbf a_1}\mathbf h_1^{\mathbf b_2}u^{\langle\mathbf a_1,\mathbf b_2\rangle}$ and $R=\mathbf g_1^{\mathbf a_2}\mathbf h_2^{\mathbf b_1}u^{\langle\mathbf a_2,\mathbf b_1\rangle}$.

Given the two group elements $L$ and $R$, both parties can fold the generators to half the length and set $P'=L^{x^2}PR^{x^{-2}}$, whose extra factors add exactly the two cross terms. Because Fiat–Shamir derives $x$ only after $L$ and $R$ are fixed, the prover cannot choose them to hide a wrong inner product. The result $P'$ is again an instance of the same relation, but of half the length. To proceed, the prover applies this step recursively, until after $\log_2 n$ rounds each vector is a single scalar. With this technique, the proof consists of $2\log_2 n$ group elements and two scalars. Apart from $\mathbf a$ and $\mathbf b$ this prover uses no randomness.

The protocol we described so far is not zero-knowledge, since $P$ and the final scalars are functions of the vectors. To make it zero-knowledge, Bulletproofs+ [CHJ+22] use the hiding property of Pedersen commitments and add a random power of $h$ to every group element. (Bulletproofs+ actually prove weighted inner products, but for this post we set all weights to $1$.) First, the statement itself becomes a hiding commitment $P=\mathbf g^{\mathbf a}\mathbf h^{\mathbf b}u^{\langle\mathbf a,\mathbf b\rangle}h^{\alpha}$ with a random blinding exponent $\alpha$. Then, in every round, the prover samples two fresh exponents $d_L,d_R\sample\ZZ_p$ and sends the blinded cross terms

Since $h^{d_L}$ and $h^{d_R}$ are uniformly random, $L$ and $R$ now reveal no information about the witness vectors. Folding works as before, but the prover additionally keeps track of the blinding exponent of the folded commitment $P'=L^{x^2}PR^{x^{-2}}$, which is $\alpha'=\alpha+x^2d_L+x^{-2}d_R$.

In the last round, in which the prover would send the scalars $a$ and $b$ in the clear, it now proves that it knows $a$, $b$ and $\alpha$ with a Schnorr-like step. It samples $r,s,\delta,\eta\sample\ZZ_p$, sends the two commitments

for the folded generators $g_\ast$ and $h_\ast$, and answers the challenge $e$ with

Just like in a Schnorr proof, the random $r$ and $s$ hide $a$ and $b$ in the responses. The verifier then checks that $P^{e^2}A^eB=g_\ast^{r'e}h_\ast^{s'e}u^{r's'}h^{\delta'}$, where $A$ and $B$ provide the cross terms $rb+sa$ and $rs$ that show up in $u^{r's'}$.

Put together, the Bulletproof inner-product argument for vectors of length $n$ consists of the blinded cross terms of all $k=\log_2 n$ rounds and the messages of the final Schnorr-like step,

With Fiat–Shamir, the challenge $x_j$ of round $j$ and the last challenge $e$ are hashes of $P$ and all previous messages, so the verifier can recompute them from $\pi$ and fold the generators and $P$ itself.

With these changes, we get a zero-knowledge argument that the prover knows $\mathbf a$, $\mathbf b$ and $\alpha$ with $P=\mathbf g^{\mathbf a}\mathbf h^{\mathbf b}u^{\langle\mathbf a,\mathbf b\rangle}h^{\alpha}$. Compared to the plain argument, it costs only two more group elements and one more scalar. The original Bulletproofs [BBB+18] make the argument zero-knowledge in a different way, by running it on randomly masked vectors. In this post we focus on the approach of Bulletproofs+, and come back to the original one in Corollary 1.

Simulating Bulletproofs#

To simulate Bulletproofs without knowing a valid witness, the simulator can follow a strategy similar to the one for Schnorr proofs. In the rounds of the argument, the simulator samples every $L$ and $R$ as a uniformly random group element. These are distributed exactly like the blinded cross terms of an honest prover. The round challenges come from the random oracle as usual. For the last step, the simulator samples the responses $r',s',\delta'$ and the challenge $e$ uniformly, together with a random group element $B$, and then computes $A$ such that the verification equation holds. Finally, similar to the Schnorr simulation, the simulator programs the random oracle to return $e$ on the transcript ending with $A$ and $B$, provided that this input has not already been queried.

Let us now try to reconstruct the prover’s randomness for such a simulated proof, once we know the witness $\mathbf a$, $\mathbf b$ and $\alpha$. We do this in the opposite order in which the simulator computed the proof. For the last step, we can apply the Schnorr trick from above, computing $r=r'-ae$ and $s=s'-be$. For the blinding exponents, however, we run into a problem. Since the simulator sampled $L$ as a random group element, we need a $d_L$ for which the honest prover would have sent the same $L$, namely

The same holds for $d_R$ in every round and for $\eta$ in $B$. Finding such a $d_L$ means computing a discrete logarithm. However, it can also be found with the trapdoor of the Pedersen commitments involved, which consists of the discrete logarithms of all generators to the base $h$.

Our simulator can obtain this trapdoor because the generators come from the random oracle. In the simulated experiment of Definition 1, the simulator answers all random-oracle queries itself, so it also decides what the generators are. It answers the query for $h$ honestly, but every other generator query with $h^{\theta}$ for a fresh uniform exponent $\theta$. Since $h^\theta$ is again a uniformly random group element, the adversary cannot notice this change. This way, the simulator knows scalars $\boldsymbol\kappa,\boldsymbol\lambda,\nu,\omega$ with

which we call the generator trapdoor. Once the simulator knows the generator trapdoor, it also knows the discrete logarithms of all folded generators, since folding only raises the generators to known powers of the challenges and multiplies them. For example, $\log_h g'_i=x^{-1}\kappa_i+x\,\kappa_{i+n/2}$. In the same way, it samples every $L$, $R$ and $B$ as a power of $h$ and remembers the exponents, which we denote by $\theta_L$, $\theta_R$ and $\theta_B$. Note that this needs no additional assumption, since the simulator already programs the random oracle for the Fiat–Shamir challenges.

With the generator trapdoor, every commitment of the form $C=h^{\rho}\mathbf g^{\mathbf m}\mathbf h^{\mathbf m'}u^{m''}$ is simply a power of $h$,

So if the simulator sampled $C$ itself as a power of $h$, it can open $C$ to any messages by setting

Opening a commitment thus costs only one subtraction, just like reconstructing the Schnorr prover’s randomness in Theorem 1.

Warning

If a security proof relies on the generator trapdoor, it can no longer rely on the binding property of the Pedersen commitments, since the reduction can equivocate the commitments.
If the surrounding protocol needs binding, its security proof therefore has to establish binding before it switches to the generator trapdoor. This adds two experiments to the sequence from the introduction, which sit between the honest execution and the experiment with simulated NIZK proofs.

In the first experiment, the random oracle still answers the generator queries honestly, but the experiment aborts as soon as the adversary opens a commitment to two different values. This experiment differs from the honest execution only if the abort happens, and an adversary that causes it reveals a discrete-logarithm relation between the honest generators, so the abort happens only with negligible probability under DLog.

In the second experiment, the random oracle answers the generator queries with powers of $h$ whose exponents the reduction knows. This switch does not change the distribution of the generators, so the adversary cannot distinguish the second experiment from the first. From now on, the reduction no longer needs binding, since every binding break already leads to an abort. Extraction from adversarial Bulletproofs [GOP+22, DG23] is unaffected, because the adversary never learns the trapdoor.

State reconstruction for Bulletproofs#

With the generator trapdoor and the exponents $\theta_L$, $\theta_R$ and $\theta_B$, the reconstruction algorithm can now compute all blinding exponents, which gives our main result.

For every random value of the honest prover, the simulated proof contains a value that this randomness has to reproduce. The table lists these pairs, in the order in which the reconstruction algorithm computes them.

The last message $A$ needs no row of its own, because once all other values agree, the verification equation leaves only one choice for $A$. The honest prover uses $2k+4$ random values for the $k=\log_2 n$ rounds, and the simulator samples exactly as many values, one for each random value of the honest prover.

Conclusion#

Simulating NIZK proofs is a standard step in security proofs, but it becomes much harder once the adversary can corrupt parties adaptively. Upon a corruption, the reduction has to reveal the randomness behind every proof of the corrupted party, including the proofs that it simulated without a witness. Since guessing the corrupted parties in advance is too costly in general, the reduction either relies on secure erasures or has to reconstruct randomness that is consistent with the simulated proofs. For Schnorr proofs, this reconstruction was already established and takes a single subtraction, but for Bulletproofs it was left as an open problem [BLSW24].

In this post, we showed that Bulletproofs have honest prover state reconstruction, both the zero-knowledge argument of Bulletproofs+ [CHJ+22] and the range proof and circuit protocol of the original Bulletproofs [BBB+18]. The key observation is that every group element of a Bulletproof is a Pedersen commitment. A simulator that programs the generators through the random oracle knows their discrete logarithms and can therefore open each of these commitments to the witness it learns upon corruption. Protocols that simulate Bulletproofs in their security proof therefore no longer need to assume secure erasures for the randomness of these proofs.