1 Introduction

Zero-knowledge proof systems, which allow a prover to convince a verifier of an NP statement \(\mathbf {R}(\mathsf {x},\mathsf {w})\) without revealing anything else about the witness \(\mathsf {w}\) have broad application in cryptography and theory of computation [7, 26, 33]. When restricted to computationally sound proof systems, also called argument systemsFootnote 1, proof size can be shorter than the size of the witness [16]. Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are zero-knowledge argument systems that additionally have two succinctness properties: small proof sizes and fast verification. Since their introduction in [47], zk-SNARKs have been a versatile design tool for secure cryptographic protocols. They became particularly relevant for blockchain applications that demand short proofs and fast verification for on-chain storage and processing. Starting with their deployment by Zcash [9], they have seen broad adoption, e.g., for privacy-preserving cryptocurrencies and scalable and private smart contracts in Ethereum.

While research on zkSNARKs has seen rapid progress [10, 12, 13, 31, 36, 37, 42, 43, 49] with many works proposing significant improvements in proof size, verifier and prover efficiency, and complexity of the public setup, less attention has been paid to non-malleable zkSNARKs and succinct signatures of knowledge [18, 20] (sometimes abbreviated SoK or referred to as SNARKY signatures [4, 39]).

Relevance of Simulation Extractability. Most zkSNARKs are shown only to satisfy a standard knowledge soundness property. Intuitively, this guarantees that a prover that creates a valid proof in isolation knows a valid witness. However, deployments of zkSNARKs in real-world applications, unless they are carefully designed to have application-specific malleability protection, e.g. [9], require a stronger property – simulation-extractability (SE) – that corresponds much more closely to existential unforgeability of signatures.

This correspondence is made precise by SoK, which uses an NP-language instance as the public verification key. Instead of signing with the secret key, SoK signing requires knowledge of the NP-witness. Intuitively, an SoK is thus a proof of knowledge (PoK) of a witness that is tied to a message. In fact, many signatures schemes, e.g., Schnorr, can be read as SoK for a specific hard relation, e.g., DL [23]. To model strong existential unforgeability of SoK signatures, even when given an oracle for obtaining signatures on different instances, an attacker must not be able to produce new signatures. Chase and Lysyanskaya [20] model this via the notion of simulation extractability which guarantees extraction of a witness even in the presence of simulated signatures.

In practice, an adversary against a zkSNARK system also has access to proofs computed by honest parties that should be modeled as simulated proofs. The definition of knowledge soundness (KS) ignores the ability of an adversary to see other valid proofs that may occur in real-world applications. For instance, in applications of zkSNARKs in privacy-preserving blockchains, proofs are posted on-chain for all blockchain participants to see. We thus argue that SE is a much more suitable notion for robust protocol design. We also claim that SE has primarily an intellectual cost, as it is harder to prove SE than KS—another analogy here is IND-CCA vs IND-CPA security for encryption. However, we will show that the proof systems we consider are SE out-of-the-box.

Fiat–Shamir-Based zkSNARKs. Most modern zkSNARK constructions follow a modular blueprint that involves the design of an information-theoretic interactive protocol, e.g. an Interactive Oracle Proof (IOP) [11], that is then compiled via cryptographic tools to obtain an interactive argument system. This is then turned into a zkSNARK using the Fiat-Shamir transform. By additionally hashing the message, the Fiat-Shamir transform is also a popular technique for constructing signatures. While well-understood for 3-message sigma protocols and justifiable in the ROM [6], Fiat–Shamir should be used with care because there are both counterexamples in theory [34] and real-world attacks in practice when implemented incorrectly [48].

In particular, several schemes such as Sonic [46], Plonk [28], Marlin [21] follow this approach where the information-theoretic object is a multi-message algebraic variant of IOP, and the cryptographic primitive in the compiler is a polynomial commitment scheme (PC) that requires a trusted setup. To date, this blueprint lacks an analysis in the ROM in terms of simulation extractability.

Updatable SRS zkSNARKs. One of the downsides of many efficient zkSNARKs [22, 31, 36, 37, 42, 43, 49] is that they rely on a trusted setup, where there is a structured reference string (SRS) that is assumed to be generated by a trusted party. In practice, however, this assumption is not well-founded; if the party that generates the SRS is not honest, they can produce proofs for false statements. If the trusted setup assumption does not hold, knowledge soundness breaks down. Groth et al. [38] propose a setting to tackle this challenge which allows parties – provers and verifiers – to update the SRS.Footnote 2 The update protocol takes an existing SRS and contributes to its randomness in a verifiable way to obtain a new SRS. The guarantee in this updatable setting is that knowledge soundness holds as long as one of the parties updating the SRS is honest. The SRS is also universal, in that it does not depend on the relation to be proved but only on an upper bound on the size of the statement’s circuit. Although inefficient, as the SRS size is quadratic in the size of the circuit, [38] set a new paradigm for designing zkSNARKs.

The first universal zkSNARK with updatable and linear size SRS was Sonic proposed by Maller et al. in [46]. Subsequently, Gabizon, Williamson, and Ciobotaru designed Plonk [28] which currently is the most efficient updatable universal zkSNARK. Independently, Chiesa et al. [21] proposed Marlin with comparable efficiency to Plonk.

The Challenge of SE in the Updatable Setting. The notion of simulation-extractability for zkSNARKs which is well motivated in practice, has not been studied in the updatable setting. Consider the following scenario: We assume a “rushing” adversary that starts off with a sequence of updates by malicious parties resulting in a subverted reference string \(\mathsf {srs}\). By combining their trapdoor contributions and employing the simulation algorithm, these parties can easily compute a proof to obtain a triple \((\mathsf {srs},\mathsf {x},\pi )\) that convinces the verifier of a statement \(\mathsf {x}\) without knowing a witness. Now, assume that at a later stage, a party produces a triple \((\mathsf {srs}',\mathsf {x},\pi ')\) for the same statement with respect to an updated \(\mathsf {srs}'\) that has an honest update contribution. We want the guarantee that this party must know a witness corresponding to \(\mathsf {x}\). The ability to “maul” the proof \(\pi \) from the old SRS to a proof \(\pi '\) for the new SRS without knowing a witness would clearly violate security. The natural idea is to require that honestly updated reference strings are indistinguishable from honestly generated reference strings even for parties that previously contributed updates. However, this is not sufficient as the adversary can also rush toward the end of the SRS generation ceremony to perform the last update.

A definition of SE in the updatable setting should take these additional powers of the adversary, which are not captured by existing definitions of SE, into consideration. While generic compilers [1, 41] can be applied to updatable SRS SNARKs to obtain SE, not only do they inevitably incur overheads and lead to efficiency loss, we contend that the standard definition of SE does not suffice in the updatable setting.

1.1 Our Contributions

We investigate the non-malleability properties of zkSNARK protocols obtained by FS-compiling multi-message protocols in the updatable SRS setting and give a modular approach to analyze their simulation-extractability. We make the following contributions:

  • Updatable simulation extractability (USE). We propose a definition of simulation extractability in the updatable SRS setting called USE, that captures the additional power the adversary gets by being able to update the SRS.

  • Theorem for USE of FS-compiled proof systems. We define three notions in the updatable SRS and ROM, trapdoor-less zero-knowledge, a unique response property, and rewinding-based knowledge soundness. Our main theorem shows that multi-message FS-compiled proof systems that satisfy these notions are USE out-of-the box.

  • USE for concrete zkSNARKs. We prove that the most efficient updatable SRS SNARKS – Plonk/Sonic/Marlin – satisfy the premises of our theorem. We thus show that these zkSNARKs are updatable simulation extractable.

  • SNARKY signatures in the updatable setting. Our results validate the folklore that the Fiat–Shamir transform is a natural means for constructing signatures of knowledge. This gives rise to the first SoK in the updatable setting and confirms that a much larger class of zkSNARKs, besides [39], can be lifted to SoK.

  • Broad applicability. The updatable SRS plus ROM includes both the trusted SRS and the ROM model as special cases. This implies the relevance of our theorem for transparent zkSNARKs such as Halo2 and Plonky2 that replace the polynomial commitments of Kate et al. [40] with commitments from Bulletproof [17] and STARKs [8], respectively.

1.2 Technical Overview

At a high level, the proof of our main theorem for updatable simulation extractability is along the lines of the simulation extractability proof for FS-compiled sigma protocols from [24]. However, our theorem introduces new notions that are more general to allow us to consider proof systems that are richer than sigma protocols and support an updatable setup. We discuss some of the technical challenges below.

\(\text {Plonk}\), \(\text {Sonic}\), and \(\text {Marlin}\) were originally presented as interactive proofs of knowledge that are made non-interactive via the Fiat–Shamir transform. In the following, we denote the underlying interactive protocols by \(\boldsymbol{\mathsf {P}}\) (for \(\text {Plonk}\)), \(\boldsymbol{\mathsf {S}}\) (for \({\text {Sonic}}\)), and \(\boldsymbol{\mathsf {M}}\) (for \(\text {Marlin}\)) and the resulting non-interactive proof systems by \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\), \(\boldsymbol{\mathsf {S}}_\mathsf {FS}\), \(\boldsymbol{\mathsf {M}}_\mathsf {FS}\) respectively.

Rewinding-Based Knowledge Soundness (RBKS). Following [24], one would have to show that for the protocols we consider, a witness can be extracted from sufficiently many valid transcripts with a common prefix. The standard definition of special soundness for sigma protocols requires the extraction of a witness from any two transcripts with the same first message. However, most zkSNARK protocols do not satisfy this notion. We put forth a notion analogous to special soundness that is more general and applicable to a wider class of protocols. Namely, protocols compiled using multi-round FS that rely on an (updatable) SRS. \(\boldsymbol{\mathsf {P}}\), \(\boldsymbol{\mathsf {S}}\), and \(\boldsymbol{\mathsf {M}}\) have more than three messages, and the number of transcripts required for extraction is more than two. Concretely, \((3 \mathsf {n}+ 6)\) for Plonk, \((\mathsf {n}+ 1)\) for Sonic, and \((2 \mathsf {n}+ 3)\) for Marlin, where \(\mathsf {n}\) is the number of constraints in the proven circuit. Hence, we do not have a pair of transcripts but a tree of transcripts.

Furthermore, the protocols we consider are arguments and rely on a SRS that comes with a trapdoor. An adversary in possession of the trapdoor can produce multiple valid proof transcripts potentially for false statements without knowing any witness. This is true even in the updatable setting, where a trapdoor still exists for any updated SRS. Recall that the standard special soundness definition requires witness extraction from any suitably structured tree of accepting transcripts. This means that there are no such trees for false statements.

Instead, we give a rewinding-based knowledge soundness definition with an extractor that proceeds in two steps. It first uses a tree building algorithm \(\mathcal {T}\) to obtain a tree of transcripts. In the second step, it uses a tree extraction algorithm \(\mathsf {Ext}_{\mathsf {ks}}\) to compute a witness from this tree. Tree-based knowledge soundness guarantees that it is possible to extract a witness from all (but negligibly many) trees of accepting transcripts produced by probabilistic polynomial time (PPT) adversaries. That is, if extraction from such a tree fails, then we break an underlying computational assumption. Moreover, this should hold even against adversaries that contribute to the SRS generation.

Unique Response Protocols (UR). Another property required to show simulation extractability is the unique response property which says that for 3-message sigma protocols, the response of the prover (3-rd message) is determined by the first message and the challenge [25] (intuitively, the prover can only employ fresh randomness in the first message of the protocol). We cannot use this definition since the protocols we consider have multiple rounds of randomized prover messages. In Plonk, both the first and the third messages are randomized. Although the Sonic prover is deterministic after it picks its first message, the protocol has more than 3 messages. The same holds for Marlin. We propose a generalization of the unique response property called \({k\text {-}\mathsf {UR}}\). It requires that the behavior of the prover be determined by the first k of its messages. For our proof, it is sufficient that Plonk is \({3\text {-}\mathsf {UR}}\), and Sonic and Marlin are \({2\text {-}\mathsf {UR}}\).

Trapdoor-Less Zero-Knowledge (TLZK). The premises of our main theorem include two computational properties that do not mention a simulator, RBKS and UR. The theorem states that together with a suitable property for the simulator of the zero-knowledge property, they imply USE. Our key technique is to simulate simulation queries when reducing to RBKS and UR. For this it is convenient that the zero-knowledge simulator be trapdoor-less, that is can produce proofs without relying on the knowledge of the trapdoor. Simulation is based purely on the simulators early control over the challenge. In the ROM this corresponds to a simulator that programs the random oracle and can be understood as a generalization of honest-verifier zero-knowledge for multi-message Fiat–Shamir transformed proof systems with an SRS. We say that such a proof system is k-TLZK, if the simulator only programs the k-th challenge and we construct such simulators for \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\), \(\boldsymbol{\mathsf {S}}_\mathsf {FS}\), and \(\boldsymbol{\mathsf {M}}_\mathsf {FS}\).

Technically we will make use of the k-UR property together with the k-TLZK property to bound the probability that the tree produced by the tree builder \(\mathcal {T}\) of RBKS contains any programmed random oracle queries.

1.3 Related Work

There are many results on simulation extractability for non-interactive zero-knowledge proofs (NIZKs). First, Groth [35] noticed that a (black-box) SE NIZK is universally-composable (UC) [19]. Then Dodis et al. [23] introduced a notion of (black-box) true simulation extractability (i.e., SE with simulation of true statements only) and showed that no NIZK can be UC-secure if it does not have this property.

In the context of zkSNARKs, the first SE zkSNARK was proposed by Groth and Maller [39] and a SE zkSNARK for QAP was designed by Lipmaa [44]. Kosba et al. [41] give a general transformation from a NIZK to a black-box SE NIZK. Although their transformation works for zkSNARKs as well, the succinctness of the proof system is not preserved by this transformation. Abdolmaleki et al. [1] showed another transformation that obtains non-black-box simulation extractability but also preserves the succinctness of the argument. The zkSNARK of [37] has been shown to be SE by introducing minor modifications to the construction and making stronger assumptions [2, 15]. Recently, [4] showed that the Groth’s original proof system from [37] is weakly SE and randomizable. None of these results are for zkSNARKs in the updatable SRS setting or for zkSNARKs obtained via the Fiat–Shamir transformation. The recent work of [30] shows that Fiat–Shamir transformed Bulletproofs are simulation extractable. While they show a general theorem for multi-round protocols, they do not consider a setting with an SRS, and are therefore inapplicable to zkSNARKs in the updatable SRS setting.

2 Definitions and Lemmas for Multi-message SRS-Based Protocols

Simulation-Extractability for Multi-message Protocols. Most recent SNARK schemes follow the same blueprint of constructing an interactive information-theoretic proof system that is then compiled into a public coin computationally sound scheme using cryptographic tools such as polynomial commitments, and finally made non-interactive via the Fiat–Shamir transformation. Existing results on simulation extractability (for proof systems and signatures of knowledge) for Fiat–Shamir transformed systems work for 3-message protocols without reference string that require two transcripts for standard model extraction, e.g., [24, 45, 50].

In this section, we define properties that are necessary for our analysis of multi-message protocols with a universal updatable SRS. In order to prove simulation-extractability for such protocols, we require more than just two transcripts for extraction. Moreover, in the updatable setting we consider protocols that rely on an SRS where the adversary gets to contribute to the SRS. We first recall the updatable SRS setting and the Fiat-Shamir transform for \((2\mu +1)\)-message protocols. Next, we define trapdoor-less zero-knowledge and simulation-extractability which we base on [24] adapted to the updatable SRS setting. Then, to support multi-message SRS-based protocols compiled using the Fiat–Shamir transform, we generalize the unique response property, and define a notion of computational special soundness called rewinding-based knowledge soundness.

Let \(\mathsf {P}\) and \(\mathsf {V}\) be \(\mathsf {PPT}\) algorithms, the former called the prover and the latter the verifier of a proof system. Both algorithms take a pre-agreed structured reference string \(\mathsf {srs}\) as input. The structured reference strings we consider are (potentially) updatable, a notion we recall shortly. We focus on proof systems made non-interactive via the multi-message Fiat–Shamir transform presented below where prover and verifier are provided with a random oracle \(\mathcal {H}\). We denote by \(\pi \) a proof created by \(\mathsf {P}\) on input \((\mathsf {srs}, \mathsf {x}, \mathsf {w})\). We say that proof is accepting if \(\mathsf {V}(\mathsf {srs}, \mathsf {x}, \pi )\) accepts it.

Let \(\mathsf {R}(\mathcal {A})\) denote the set of random tapes of correct length for adversary \(\mathcal {A}\) (assuming the given value of security parameter \(\lambda \)), and let \(r \,{\leftarrow \!\!{\$ }\,}\mathsf {R}(\mathcal {A})\) denote the random choice of tape r from \(\mathsf {R}(\mathcal {A})\).

2.1 Updatable SRS Setup Ceremonies

The definition of updatable SRS ceremonies of [38] requires the following algorithms.

  • \((\mathsf {srs},\rho ) \leftarrow \mathsf {GenSRS}(\mathbf {R})\) is a PPT algorithm that takes a relation \(\mathbf {R}\) and outputs a reference string \(\mathsf {srs}\), and correctness proof \(\rho \).

  • \( (\mathsf {srs}',\rho ') \leftarrow \mathsf {UpdSRS}(\mathsf {srs}, \{\rho _j \}_{j=1}^n)\) is a PPT algorithm that takes a \(\mathsf {srs}\), a list of update proofs and outputs an updated \(\mathsf {srs}'\) together with a proof of correct update \(\rho '\).

  • \(b \leftarrow \mathsf {VerifySRS}(\mathsf {srs}, \{\rho _j \}_{j=1}^n)\) takes a reference string \(\mathsf {srs}\), a list of update proofs, and outputs a bit indicating acceptance or not.Footnote 3

In the next section, we define security notions in the updatable setting by giving the adversary access to an SRS update oracle \(\mathsf {Upd}\mathsf {O}\), defined in Fig. 1. The oracle allows the adversary to control the SRS generation. A trusted setup can be expressed by the updatable setup definition simply by restricting the adversary to only call the oracle on \(\mathtt {intent}= \mathtt {setup}\) and \(\mathtt {intent}= \mathtt {final}\). Note that a soundness adversary now has access to both the random oracle \(\mathcal {H}\) and \(\mathsf {Upd}\mathsf {O}\): \((\mathsf {x}, \pi ) \leftarrow \mathcal {A}^{\mathsf {Upd}\mathsf {O},\mathcal {H}}(1^\lambda ; r)\).

Fig. 1.
figure 1

The oracle defines the notion of updatable SRS setup.

Full size image

Remark on Universality of the SRS. The proof systems we consider in this work are universal. This means that both the relation \(\mathbf {R}\) and the reference string \(\mathsf {srs}\) allows to prove arithmetic constraints defined over a particular field up to some size bound. The public instance \(\mathsf {x}\) must determine the constraints. If \(\mathbf {R}\) comes with any auxiliary input, the latter is benign. We elide public preprocessing of constraint specific proving and verification keys. While important for performance, this modeling is not critical for security.

Fig. 2.
figure 2

Updatable SRS scheme \(\mathsf {SRS}\) for \(\boldsymbol{\mathsf {PC}}_{\boldsymbol{\mathsf {P}}}\)

Full size image

2.2 Multi-message Fiat-Shamir Compiled Provers and Verifiers

Given interactive prover and (public coin) verifier \(\mathsf {P}', \mathsf {V}'\) that exchange messages resulting in transcript \(\tilde{\pi }= (a_1, c_1, \ldots , a_{\mu }, c_{\mu }, a_{\mu + 1})\), where \(a_i\) comes from \(\mathsf {P}'\) and \(c_i\) comes from \(\mathsf {V}'\), the \((2\mu + 1)\)-message Fiat-Shamir heuristic defines non-interactive provers and verifiers \(\mathsf {P}, \mathsf {V}\) as follows:

  • \(\mathsf {P}\) behaves as \(\mathsf {P}'\) except after sending message \(a_i\), \(i \in [1 \, .. \, \mu ]\), the prover does not wait for the message from the verifier but computes it locally setting \(c_i = \mathcal {H}(\tilde{\pi }[0..i])\), where \(\tilde{\pi }[0..j] = (\mathsf {x}, a_1, c_1, \ldots , a_{j - 1}, c_{j - 1}, a_j)\).Footnote 4 \(\mathsf {P}\) outputs the non-interactive proof \(\pi =(a_1,\ldots , a_{\mu }, a_{\mu + 1})\), that omits challenges as they can be recomputed using \(\mathcal {H}\).

  • \(\mathsf {V}\) takes \(\mathsf {x}\) and \(\pi \) as input and behaves as \(\mathsf {V}'\) would but does not provide challenges to the prover. Instead it computes the challenges locally as \(\mathsf {P}\) would, starting from \(\tilde{\pi }[0..1]=(\mathsf {x},a_1)\) which can be obtained from \(\mathsf {x}\) and \(\pi \). Then it verifies the resulting transcript \(\tilde{\pi }\) as the verifier \(\mathsf {V}'\) would.

We note that since the verifier can compute the challenges by querying the random oracle, they do not need to be sent by the prover. Thus the \(\pi \) - \(\tilde{\pi }\) notational distinction.

Notation for \((2\mu + 1)\)-message Fiat–Shamir transformed proof systems. Let \(\mathsf {SRS}= (\mathsf {GenSRS},\mathsf {UpdSRS}, \mathsf {VerifySRS})\) be the algorithm of an updatable SRS ceremony. All our definitions and theorems are about non-interactive proof systems \(\boldsymbol{\mathsf {\Psi }}= (\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) compiled via the \((2\mu + 1)\)-message FS transform. That is \(\pi = (a_1, \ldots , a_{\mu }, a_{\mu + 1})\) and \(\tilde{\pi }= (a_1, c_1, \ldots , a_{\mu }, c_{\mu }, a_{\mu + 1})\), with \(c_i = \mathcal {H}(\tilde{\pi }[0..i])\). We use \(\tilde{\pi }[0]\) for instance \(\mathsf {x}\) and \(\tilde{\pi }[i]\), \(\tilde{\pi }[i].\mathsf {ch}\) to denote prover message \(a_i\) and challenge \(c_i\) respectively.

Fig. 3.
figure 3

Simulation oracles: \(\mathsf {srs}\) is the finalized SRS, only \(\mathsf {Sim}\mathsf {O}.\mathsf {P}'\) allows for simulation of false statements

Full size image

2.3 Trapdoor-Less Zero-Knowledge (TLZK)

We call a protocol trapdoor-less zero-knowledge (TLZK) if there exists a simulator that does not require the trapdoor, and works by programming the random oracle. Moreover, the simulator may only be allowed to program the random oracle on point \(\tilde{\pi }[0,k]\), that is the simulator can only program the challenges that come after the k-th prover message. We call protocols which allow for such a simulation k-programmable trapdoor-less zero-knowledge.

Our definition of zero-knowledge for non-interactive arguments is in the programmable ROM. We model this using the oracles from Fig. 3 that provide a stateful wrapper around \(\mathsf {Sim}\). \(\mathsf {Sim}\mathsf {O}.\mathcal {H}(x)\) simulates \(\mathcal {H}\) using lazy sampling, \(\mathsf {Sim}\mathsf {O}.\mathsf {Prog}(x, h)\) allows for programming the simulated \(\mathcal {H}\) and is available only to \(\mathsf {Sim}\). \(\mathsf {Sim}\mathsf {O}.\mathsf {P}(\mathsf {x}, \mathsf {w})\) and \(\mathsf {Sim}\mathsf {O}.\mathsf {P}'(\mathsf {x})\) call the simulator. The former is used in the zero-knowledge definition and requires the statement and witness to be in the relation, the latter is used in the simulation extraction definition and does not require a witness input.

Definition 1

(Updatable k-Programmable Trapdoor-Less Zero-Knowledge). Let \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}= (\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) be a \((2\mu + 1)\)-message FS-transformed NIZK proof system with an updatable SRS setup. We call \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) trapdoor-less zero-knowledge with security \(\varepsilon _{\mathsf {zk}}\) if for any adversary \(\mathcal {A}\), \(|{\varepsilon _0(\lambda ) - \varepsilon _1(\lambda )}| \le \varepsilon _{\mathsf {zk}}(\lambda )\), where

$$\begin{aligned} \varepsilon _0 (\lambda ) = \Pr \left[ \mathcal {A}^{\mathsf {Upd}\mathsf {O}, \mathcal {H}, \mathsf {P}} (1^\lambda ) \right] ,\, \varepsilon _1 (\lambda )= \Pr \left[ \mathcal {A}^{\mathsf {Upd}\mathsf {O}, \mathsf {Sim}\mathsf {O}.\mathcal {H}, \mathsf {Sim}\mathsf {O}.\mathsf {P}} (1^\lambda ) \right] . \end{aligned}$$

If \(\varepsilon _{\mathsf {zk}}(\lambda )\) is negligible, we say \(\boldsymbol{\mathsf {\Psi }}_{\mathsf {FS}}\) is trapdoor-less zero-knowledge. Additionally, we say that \(\boldsymbol{\mathsf {\Psi }}_{\mathsf {FS}}\) is k-programmable, if \(\mathsf {Sim}\) before returning a proof \(\pi \) only calls \(\mathsf {Sim}\mathsf {O}.\mathsf {Prog}\) on \((\tilde{\pi }[0..k],h)\). That is, it only programs the k-th message.

Remark 1

(TLZK vs HVZK). We note that TLZK notion is closely related to honest-verifier zero-knowledge in the standard model. That is, if we consider an interactive proof system \(\boldsymbol{\mathsf {\Psi }}\) that is HVZK in the standard model then \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) is TLZK. This comes as the simulator \(\mathsf {Sim}\) in \(\boldsymbol{\mathsf {\Psi }}\) produces a valid simulated proof by picking verifier’s challenges according to a predefined distribution and \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\)’s simulator \(\mathsf {Sim}_\mathsf {FS}\) produces its proofs similarly by picking the challenges and additionally programming the random oracle to return the picked challenges. Importantly, in both \(\boldsymbol{\mathsf {\Psi }}\) and \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) success of the simulator does not depend on access to an SRS trapdoor.

We note that \(\text {Plonk}\) is 3-programmable TLZK, and \({\text {Sonic}}\) and \({\text {Marlin}}\) are 2-programmable TLZK. This follows directly from the proofs of their standard model zero-knowledge property in Lemma 5 and lemmas 11 and 14 in the full version [29].

2.4 Updatable Simulation Extractability (USE)

We note that the zero-knowledge property is only guaranteed for statements in the language. For simulation extractability where the simulator should be able to provide simulated proofs for false statements as well, we thus use the oracle \(\mathsf {Sim}\mathsf {O}.\mathsf {P}'\)Footnote 5.

Definition 2

(Updatable Simulation Extractability). Let \(\boldsymbol{\mathsf {\Psi }}_{\mathsf {NI}}= (\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) be a NIZK proof system with an updatable SRS setup. We say that \(\boldsymbol{\mathsf {\Psi }}_{\mathsf {NI}}\) is updatable simulation-extractable with security loss \(\varepsilon _{\mathsf {se}}(\lambda ,\mathsf {acc}, q)\) if for any \(\mathsf {PPT}\) adversary \(\mathcal {A}\) that is given oracle access to setup oracle \(\mathsf {Upd}\mathsf {O}\) and simulation oracle \(\mathsf {Sim}\mathsf {O}\) and that produces an accepting proof for \(\boldsymbol{\mathsf {\Psi }}_{\mathsf {NI}}\) with probability \(\mathsf {acc}\), where

figure a

there exists an expected PPT extractor \(\mathsf {Ext}_\mathsf {se}\) such that

figure b

Here, \(\mathsf {srs}\) is the finalized SRS. List \(Q_{\mathsf {srs}}\) contains all \((\mathsf {srs}, \rho )\) of update SRSs and their proofs, list \(Q_{\mathcal {H}}\) contains all \(\mathcal {A}\)’s queries to \(\mathsf {Sim}\mathsf {O}.\mathcal {H}\) and the (simulated) random oracle’s answers, \(|{Q_{\mathcal {H}}}|\le q\), and list Q contains all \((\mathsf {x}, \pi )\) pairs where \(\mathsf {x}\) is an instance queried to \(\mathsf {Sim}\mathsf {O}.\mathsf {P}'\) by the adversary and \(\pi \) is the simulator’s answer.

2.5 Unique Response (UR) Protocols

A technical hurdle identified by Faust et al. [24] for proving simulation extraction via the Fiat–Shamir transformation is that the transformed proof system satisfies a unique response property. The original formulation by Fischlin, although suitable for applications presented in [24, 25], does not suffice in our case. First, the property assumes that the protocol has three messages, with the second being the challenge from the verifier. That is not the case we consider here. Second, it is not entirely clear how to generalize the property. Should one require that after the first challenge from the verifier, the prover’s responses are fixed? That does not work since the prover needs to answer differently on different verifier’s challenges, as otherwise the protocol could have fewer messages. Another problem is that the protocol could have a message, beyond the first prover’s message, which is randomized. Unique response cannot hold in this case. Finally, the protocols we consider here are not in the standard model, but use an SRS.

We work around these obstacles by providing a generalized notion of the unique response property. More precisely, we say that a \((2\mu + 1)\)-message protocol has unique responses from k, and call it a \({k\text {-}\mathsf {UR}}\)-protocol, if it follows the definition below:

Definition 3

(Updatable k-Unique Response Protocol). Let \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}= (\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) be a \((2\mu + 1)\)-message FS-transformed NIZK proof system with an updatable SRS setup. Let \(\mathcal {H}\) be the random oracle. We say that \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) has unique responses for k with security \(\varepsilon _\mathsf {ur}(\lambda )\) if for any \(\mathsf {PPT}\) adversary \(\mathcal {A}_{\mathsf {ur}}\):

$$ \Pr \left[ \left. \begin{aligned}&\pi \ne \pi ', \tilde{\pi }[0..k] = \tilde{\pi }'[0..k], \\&\mathsf {V}' (\mathsf {srs}, \mathsf {x}, \pi ,c) = \mathsf {V}' (\mathsf {srs}, \mathsf {x}, \pi ',c) = 1 \\ \end{aligned} \,\right| \, \begin{aligned}&(\mathsf {x}, \pi , \pi ', c) \leftarrow \mathcal {A}_{\mathsf {ur}}^{\mathsf {Upd}\mathsf {O},\mathcal {H}}(1^\lambda ) \end{aligned} \right] \!{\le }\, \varepsilon _\mathsf {ur}(\lambda ) $$

where \(\mathsf {srs}\) is the finalized SRS and \(\mathsf {V}'(\mathsf {srs},\mathsf {x},\pi =(a_1, \dots , a_\mu ,a_{\mu +1}))\) behaves as \(\mathsf {V}(\mathsf {srs}, \mathsf {x}, \pi )\) except for using c as the k-th challenge instead of calling \(\mathcal {H}(\tilde{\pi }[0..k]) \). Thus, \(\mathcal {A}\) can program the k-th challenge. We say \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) is \({k\text {-}\mathsf {UR}}\), if \(\varepsilon _\mathsf {ur}(\lambda )\) is negligible.

Intuitively, a protocol is \({k\text {-}\mathsf {UR}}\) if it is infeasible for a \(\mathsf {PPT}\) adversary to produce a pair of accepting proofs \(\pi \ne \pi '\) that are the same on the first k messages of the prover.

The definition can be easily generalized to allow for programming the oracle on more than just a single point. We opted for this simplified presentation, since all the protocols analyzed in this paper require only single-point programming,

2.6 Rewinding-Based Knowledge Soundness (RBKS)

Before giving the definition of rewinding-based knowledge soundness for NIZK proof systems compiled via the \((2\mu + 1)\)-message FS transformation, we first recall the notion of a tree of transcripts.

Definition 4

(Tree of accepting transcripts, cf. [14]). A \((n_1, \ldots , n_\mu )\)-tree of accepting transcripts is a tree where each node on depth i, for \(i \in [1 \, .. \, \mu + 1]\), is an i-th prover’s message in an accepting transcript; edges between the nodes are labeled with challenges, such that no two edges on the same depth have the same label; and each node on depth i has \(n_{i} - 1\) siblings and \(n_{i + 1}\) children. The tree consists of \(N = \prod _{i = 1}^\mu n_i\) branches, where N is the number of accepting transcripts. We require \(N = \mathsf {poly}(\lambda )\). We refer to a \((1, \ldots , n_k=n, 1, \ldots , 1)\)-tree as a (k, n)-tree.

The existence of simulation trapdoor for \(\boldsymbol{\mathsf {P}}\), \(\boldsymbol{\mathsf {S}}\) and \(\boldsymbol{\mathsf {M}}\) means that they are not special sound in the standard sense. We therefore put forth the notion of rewinding-based knowledge soundness that is a computational notion. Note that in the definition below, it is implicit that each transcript in the tree is accepting with respect to a “local programming” of the random oracle. However, the verification of the proof output by the adversary is with respect to a non-programmed random oracle.

Definition 5

(Updatable Rewinding-Based Knowledge Soundness). Let \(n_1, \ldots , n_\mu \in \mathbb {N}\). Let \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}= (\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) be a \((2\mu + 1)\)-message FS-transformed NIZK proof system with an updatable SRS setup for relation \(\mathbf {R}\). Let \(\mathcal {H}\) be the random oracle. We require existence of an expected PPT tree builder \(\mathcal {T}\) that eventually outputs a \(\mathsf {T}\) which is either a \((n_1, \ldots , n_\mu )\)-tree of accepting transcript or \(\bot \) and a PPT extractor \(\mathsf {Ext}_{\mathsf {ks}}\). Let adversary \(\mathcal {A}_{\mathsf {ks}}\) be a PPT algorithm, that outputs a valid proof with probability at least \(\mathsf {acc}\), where

figure c

We say that \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) is \((n_1, \ldots , n_\mu )\)-rewinding-based knowledge sound with security loss \(\varepsilon _{\mathsf {ks}}(\lambda , \mathsf {acc}, q)\) if

figure d

Here, \(\mathsf {srs}\) is the finalized SRS. List \(Q_{\mathsf {srs}}\) contains all \((\mathsf {srs}, \rho )\) of updated SRSs and their proofs, and list \(Q_{\mathcal {H}}\) contains all of the adversaries queries to \(\mathcal {H}\) and the random oracle’s answers, \(|{Q_{\mathcal {H}}}|\le q\).

3 Simulation Extractability—The General Result

Equipped with the definitional framework of Sect. 2, we now present the main result of this paper: a proof of simulation extractability for multi-message Fiat–Shamir-transformed NIZK proof systems.

Without loss of generality, we assume that whenever the accepting proof contains a response to a challenge from a random oracle, then the adversary queried the oracle to get it. It is straightforward to transform any adversary that violates this condition into an adversary that makes these additional queries to the random oracle and wins with the same probability.

Fig. 4.
figure 4

Simulating random oracle calls.

Full size image

The core conceptual insight of the proof is that the k-unique response and k-programmable trapdoor-less zero-knowledge properties together ensures that the k-th move challenges in the trees of rewinding-based knowledge soundness are fresh and do not come from the simulator. This allows us to eliminate the simulation oracle in our rewinding argument and enables us to use the existing results of [3] in later sections.

Theorem 1

(Simulation-extractable multi-message protocols). Let \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}= (\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) be a \((2\mu + 1)\)-message FS-transformed NIZK proof system with an updatable SRS setup. If \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) is an updatable k-unique response protocol with security loss \(\varepsilon _\mathsf {ur}\), updatable k-programmable trapdoor-less zero-knowledge, and updatable rewinding-based knowledge sound with security loss \(\varepsilon _{\mathsf {ks}}\); Then \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) is updatable simulation-extractable with security loss

$$\begin{aligned} \varepsilon _{\mathsf {se}}(\lambda ,\mathsf {acc},q) \le \varepsilon _{\mathsf {ks}}(\lambda ,\mathsf {acc} - \varepsilon _{\mathsf {ur}}(\lambda ),q) \end{aligned}$$

against any \(\mathsf {PPT}\) adversary \(\mathcal {A}\) that makes up to q random oracle queries and returns an accepting proof with probability at least \(\mathsf {acc}\).

Proof

Let \((\mathsf {x}, \pi ) \leftarrow \mathcal {A}^{\mathsf {Upd}\mathsf {O}, \mathsf {Sim}\mathsf {O}.\mathcal {H}, \mathsf {Sim}\mathsf {O}.\mathsf {P}'}(r_{\mathcal {A}})\) be the USE adversary. We show how to build an extractor \(\mathsf {Ext}_\mathsf {se}(\mathsf {srs}, \mathcal {A}, r_{\mathcal {A}}, Q, Q_{\mathcal {H}}, Q_{\mathsf {srs}})\) that outputs a witness \(\mathsf {w}\), such that \(\mathbf {R}(\mathsf {x}, \mathsf {w})\) holds with high probability. To that end we define an algorithm \(\mathcal {A}_{\mathsf {ks}}^{\mathsf {Upd}\mathsf {O},\mathcal {H}}(r)\) against rewinding-based knowledge soundness of \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) that runs internally \(\mathcal {A}^{\mathsf {Upd}\mathsf {O}, \mathsf {Sim}\mathsf {O}.\mathcal {H}, \mathsf {Sim}\mathsf {O}.\mathsf {P}'}(r_{\mathcal {A}})\). Here \(r = (r_\mathsf {Sim}, r_{\mathcal {A}})\) with \(r_\mathsf {Sim}\) the randomness that will be used to simulate \(\mathsf {Sim}\mathsf {O}.\mathsf {P}'\).

The code of \(\mathcal {A}_{\mathsf {ks}}^{\mathsf {Upd}\mathsf {O},\mathcal {H}}(r)\) hardcodes \(Q\) such that it does not use any randomness for proofs in \(Q\) as long as statements are queried in order. In this case it simply returns a proof \(\pi _\mathsf {Sim}\) from \(Q\) but nevertheless queries \(\mathsf {Sim}\mathsf {O}.\mathsf {Prog}\) on \((\tilde{\pi }_\mathsf {Sim}[0..k],\tilde{\pi }_\mathsf {Sim}[k].ch)\), i.e. it programs the k-th challenge. While it is hard to construct such an adversary without knowing \(Q\), it clearly exists and \(\mathsf {Ext}_\mathsf {se}\) has the necessary inputs to construct \(\mathcal {A}_{\mathsf {ks}}\). This hardcoding guarantees that \(\mathcal {A}_{\mathsf {ks}}\) returns the same \((\mathsf {x},\pi )\) as \(\mathcal {A}\) in the experiment. Eventually, \(\mathsf {Ext}_\mathsf {se}\) uses the tree builder \(\mathcal {T}\) and extractor \(\mathsf {Ext}_{\mathsf {ks}}\) for \(\mathcal {A}_{\mathsf {ks}}\) to extract the witness for \(\mathsf {x}\). Both guaranteed to exist (and be successful with high probability) by rewinding-based knowledge soundness. This high-level argument shows that \(\mathsf {Ext}_\mathsf {se}\) exists as well.

We now give the details of the simulation that guarantees that \(\mathcal {A}_{\mathsf {ks}}\) is successful whenever \(\mathcal {A}\) is—except with a small security loss that we will bound later: Since \(\mathcal {A}_{\mathsf {ks}}\) runs \(\mathcal {A}\) internally, it needs to take care of \(\mathcal {A}\)’s oracle queries. \(\mathcal {A}_{\mathsf {ks}}\) passes on queries of \(\mathcal {A}\) to the update oracle \(\mathsf {Upd}\mathsf {O}\) to its own \(\mathsf {Upd}\mathsf {O}\) oracle and returns the result to \(\mathcal {A}\). \(\mathcal {A}_{\mathsf {ks}}\) internally simulates (non-hardcoded) queries to the simulator \(\mathsf {Sim}\mathsf {O}.\mathsf {P}'\) by running the \(\mathsf {Sim}\) algorithm on randomness \(r_\mathsf {Sim}\) of its tape. \(\mathsf {Sim}\) requires access to oracles \(\mathsf {Sim}\mathsf {O}.\mathcal {H}\) to compute a challenge honestly and \(\mathsf {Sim}\mathsf {O}.\mathsf {Prog}\) to program a challenge. Again \(\mathcal {A}_{\mathsf {ks}}\) simulates both of these oracles internally, cf. Fig. 4, this time using the \(\mathcal {H}\) oracle of \(\mathcal {A}_{\mathsf {ks}}\). Note that queries of \(\mathcal {A}\) to \(\mathsf {Sim}\mathsf {O}.\mathcal {H}\) are not programmed, but passed on to \(\mathcal {H}\).

Importantly, all challenges in simulated proofs, up to round k are also computed honestly, i.e. \(\tilde{\pi }[i].\mathsf {ch}= \mathcal {H}(\tilde{\pi }[0..i])\), for \(i < k\).

Eventually, \(\mathcal {A}\) outputs an instance and proof \((\mathsf {x}, \pi )\). \(\mathcal {A}_{\mathsf {ks}}\) returns the same values as long as \(\tilde{\pi }[0..i] \notin Q_{\mathsf {prog}}\), \(i\in [1,\mu ]\). This models that the proof output by \(\mathcal {A}_{\mathsf {ks}}\) must not contain any programmed queries as such a proof would not be consistent to \(\mathcal {H}\) in the RBKS experiment. If \(\mathcal {A}\) outputs a proof that does contain programmed challenges, then \(\mathcal {A}_{\mathsf {ks}}\) aborts. We denote this event by \(\mathsf {E}\).

Lemma 1

Probability that \(\mathsf {E}\) happens is upper-bounded by \(\varepsilon _\mathsf {ur}(\lambda )\).

Proof

We build an adversary \(\mathcal {A}_{\mathsf {ur}}^{\mathsf {Upd}\mathsf {O}, \mathcal {H}} (\lambda ; r)\) that has access to the random oracle \(\mathcal {H}\) and update oracle \(\mathsf {Upd}\mathsf {O}\). \(\mathcal {A}_{\mathsf {ur}}\) uses \(\mathcal {A}_{\mathsf {ks}}\) to break the \({k\text {-}\mathsf {UR}}\) property of \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\).

When \(\mathcal {A}_{\mathsf {ks}}\) outputs a proof \(\pi \) for \(\mathsf {x}\) such that \(\mathsf {E}\) holds, \(\mathcal {A}_{\mathsf {ur}}\) looks through lists Q and \(Q_{\mathcal {H}}\) until it finds \(\tilde{\pi }_\mathsf {Sim}[0..k]\) such that \(\tilde{\pi }[0..k] = \tilde{\pi }_\mathsf {Sim}[0..k]\) and a programmed random oracle query \(\tilde{\pi }_\mathsf {Sim}[k].\mathsf {ch}\) on \(\tilde{\pi }_\mathsf {Sim}[0..k]\). \(\mathcal {A}_{\mathsf {ur}}\) returns two proofs \(\pi \) and \(\pi _\mathsf {Sim}\) for \(\mathsf {x}\), and the challenge \(\tilde{\pi }_\mathsf {Sim}[k].\mathsf {ch}=\tilde{\pi }[k].\mathsf {ch}\). Importantly, both proofs are w.r.t the unique response verifier. The first, since it is a correctly computed simulated proof for which the unique response property definition allows any challenges at k. The latter, since it is an accepting proof produced by the adversary. We have that \(\pi \ne \pi _\mathsf {Sim}\) as otherwise \(\mathcal {A}\) does not win the simulation extractability game as \(\pi \in Q\). On the other hand, if the proofs are different, then \(\mathcal {A}_{\mathsf {ur}}\) breaks \({k\text {-}\mathsf {UR}}\)-ness of \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\). This happens only with probability \(\varepsilon _\mathsf {ur}(\lambda )\).    \(\square \)

We denote by \(\mathsf {\widetilde{acc}}\) the probability that \(\mathcal {A}_{\mathsf {ks}}\) outputs an accepting proof. We note that by up-to-bad reasoning \(\mathsf {\widetilde{acc}}\) is at most \(\varepsilon _\mathsf {ur}(\lambda )\) far from the probability that \(\mathcal {A}\) outputs an accepting proof. Thus, the probability that \(\mathcal {A}_{\mathsf {ks}}\) outputs an accepting proof is at least \(\mathsf {\widetilde{acc}}\ge \mathsf {acc}- \varepsilon _\mathsf {ur}(\lambda )\). Since \(\boldsymbol{\mathsf {\Psi }}_\mathsf {FS}\) is \(\varepsilon _{\mathsf {ks}}(\lambda , \mathsf {\widetilde{acc}},q)\) rewinding-based knowledge sound, there is a tree builder \(\mathcal {T}\) and extractor \(\mathsf {Ext}_{\mathsf {ks}}\) that rewinds \(\mathcal {A}_{\mathsf {ks}}\) to obtain a tree of accepting transcripts \(\mathsf {T}\) and fails to extract the witness with probability at most \(\varepsilon _{\mathsf {ks}}(\lambda , \mathsf {\widetilde{acc}}, q)\). The extractor \(\mathsf {Ext}_\mathsf {se}\) outputs the witness with the same probability.

Thus \(\varepsilon _{\mathsf {se}}(\lambda ,\mathsf {acc},q) = \varepsilon _{\mathsf {ks}}(\lambda , \mathsf {\widetilde{acc}},q) \le \varepsilon _{\mathsf {ks}}(\lambda ,\mathsf {acc}- \varepsilon _\mathsf {ur},q)\).    \(\square \)

Remark 2

Observe that our theorem does not depend on \(\varepsilon _{\mathsf {zk}}(\lambda )\). There is no real prover algorithm \(\mathsf {P}\) in the experiment. Only the k-programmability of TLZK matters.

Remark 3

Observe that the theorem does not prescribe a tree shape for the tree builder \(\mathcal {T}\). Interestingly, in our concrete results \(\mathcal {T}\) outputs a \((k, *)\)-tree of accepting transcripts.

4 Concrete SNARKs Preliminaries

Bilinear groups. A bilinear group generator \(\mathsf {Pgen}(1^\lambda )\) returns public parameters \( \mathsf {p}= (p, \mathbb {G}_1, \mathbb {G}_2, \mathbb {G}_T, \hat{e}, \left[ 1\right] _{1}, \left[ 1\right] _{2})\), where \(\mathbb {G}_1\), \(\mathbb {G}_2\), and \(\mathbb {G}_T\) are additive cyclic groups of prime order \(p = 2^{\varOmega (\lambda )}\), \(\left[ 1\right] _{1}, \left[ 1\right] _{2}\) are generators of \(\mathbb {G}_1\), \(\mathbb {G}_2\), resp., and \(\hat{e}: \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T\) is a non-degenerate \(\mathsf {PPT}\)-computable bilinear pairing. We assume the bilinear pairing to be Type-3, i.e., that there is no efficient isomorphism from \(\mathbb {G}_1\) to \(\mathbb {G}_2\) or from \(\mathbb {G}_2\) to \(\mathbb {G}_1\). We use the by now standard bracket notation, i.e., we write \(\left[ a\right] _{\iota }\) to denote \(a \left[ 1\right] _{\iota }\). We denote \(\hat{e}(\left[ a\right] _{1}, \left[ b\right] _{2})\) as \(\left[ a\right] _{1} \bullet \left[ b\right] _{2}\). Thus, \(\left[ a\right] _{1} \bullet \left[ b\right] _{2} = \left[ a b\right] _{T}\). Since every algorithm \(\mathcal {A}\) takes as input the public parameters we skip them when describing \(\mathcal {A}\)’s input. Similarly, we do not explicitly state that each protocol starts by running \(\mathsf {Pgen}\).

4.1 Algebraic Group Model

The algebraic group model (AGM) of Fuchsbauer, Kiltz, and Loss [27] lies somewhat between the standard and generic bilinear group model. In the AGM it is assumed that an adversary \(\mathcal {A}\) can output a group element \(\left[ y\right] \in \mathbb {G}\) if \(\left[ y\right] \) has been computed by applying group operations to group elements given to \(\mathcal {A}\) as input. It is further assumed, that \(\mathcal {A}\) knows how to “build” \(\left[ y\right] \) from those elements. More precisely, the AGM requires that whenever \(\mathcal {A}(\left[ \boldsymbol{x}\right] )\) outputs a group element \(\left[ y\right] \) then it also outputs \(\boldsymbol{c}\) such that \(\left[ y\right] = \boldsymbol{c}^\top \cdot \left[ \boldsymbol{x}\right] \). \(\text {Plonk}\), \({\text {Sonic}}\) and \({\text {Marlin}}\) have been shown secure using the AGM. An adversary that works in the AGM is called algebraic.

Ideal Verifier and Verification Equations. Let \((\mathsf {SRS}, \mathsf {P}, \mathsf {V}, \mathsf {Sim})\) be a proof system. Observe that the \(\mathsf {SRS}\) algorithms provide an SRS which can be interpreted as a set of group representation of polynomials evaluated at trapdoor elements. That is, for a trapdoor \(\chi \) the SRS contains \(\left[ \mathsf {p_1}(\chi ), \ldots , \mathsf {p_k}(\chi )\right] _{1}\), for some polynomials \(\mathsf {p_1}(X), \ldots , \mathsf {p_k}(X) \in \mathbb {F}_p[X]\). The verifier \(\mathsf {V}\) accepts a proof \(\pi \) for instance \(\mathsf {x}\) if (a set of) verification equation \(\mathsf {ve}_{\mathsf {x}, \pi }\) (which can also be interpreted as a polynomial in \(\mathbb {F}_p[X]\) whose coefficients depend on messages sent by the prover) zeroes at \(\chi \). Following [28] we call verifiers who check that \(\mathsf {ve}_{\mathsf {x}, \pi }(\chi ) = 0\) real verifiers as opposed to ideal verifiers who accept only when \(\mathsf {ve}_{\mathsf {x}, \pi }(X) = 0\). That is, while a real verifier accepts when a polynomial evaluates to zero, an ideal verifier accepts only when the polynomial is zero.

Although ideal verifiers are impractical, they are very useful in our proofs. More precisely, we show that the idealized verifier accepts an incorrect proof (what “incorrect” means depends on the situation) with at most negligible probability (and in many cases—never); when the real verifier accepts, but not the idealized one, then a malicious prover can be used to break the underlying security assumption (in our case—a variant of \(\mathsf {dlog}\).)

Analogously, idealized verifier can be defined for polynomial commitment schemes.

4.2 Dlog Assumptions in Standard and Updatable Setting

Definition 6

(\((q_1, q_2)\text {-}\mathsf {dlog}\) assumption). Let \(\mathcal {A}\) be a \(\mathsf {PPT}\) adversary that gets as input \(\left[ 1, \chi , \ldots , \chi ^{q_1}\right] _{1}, \left[ 1, \chi , \ldots , \chi ^{q_2}\right] _{2}\), for some randomly picked \(\chi \in \mathbb {F}_p\), the assumption requires that \(\mathcal {A}\) cannot compute \(\chi \). That is

$$ Pr {\left[ \chi = \mathcal {A}(\left[ 1, \chi , \ldots , \chi ^{q_1}\right] _{1}, \left[ 1, \chi , \ldots , \chi ^{q_2} \right] _{2})\,\left| \,\chi \,{\leftarrow \!\!{\$ }\,}\mathbb {F}_p\right. \right] } \le \mathsf {negl}(\lambda ). $$

Since all our protocols and security notions are in the updatable setting, it is natural to define the dlog assumptions also in the updatable setting. That is, instead of being given a dlog challenge the adversary \(\mathcal {A}\) is given access to an update oracle as defined in Fig. 1. The honestly generated SRS is set to be a dlog challenge and the update algorithm \(\mathsf {UpdSRS}\) re-randomizing the challenge. We define this assumptions and show a reduction between the assumptions in the updatable and standard setting.

Note that for clarity we here refer to the SRS by \(\mathsf {Ch}\). Further, to avoid cluttering notation, we do not make the update proofs explicit. They are generated in the same manner as the proofs in Fig. 2.

Definition 7

(\((q_1, q_2)\text {-}\mathsf {udlog}\) assumption). Let \(\mathcal {A}\) be a \(\mathsf {PPT}\) adversary that gets oracle access to \(\mathsf {Upd}\mathsf {O}\) with internal algorithms \((\mathsf {GenSRS}, \mathsf {UpdSRS}, \mathsf {VerifySRS})\), where \(\mathsf {GenSRS}\) and \(\mathsf {UpdSRS}\) are defined as follows:

  • \(\mathsf {GenSRS}(\lambda )\) samples \(\chi \,{\leftarrow \!\!{\$ }\,}\mathbb {F}_p\) and defines \(\mathsf {Ch}:=(\left[ 1, \chi , \ldots , \chi ^{q_1}\right] _{1}, \left[ 1, \chi , \ldots ,\right. \left. \chi ^{q_2}\right] _{2})\).

  • \(\mathsf {UpdSRS}(\mathsf {Ch}, \{\rho _j \}_{j=1}^n)\) parses \(\mathsf {Ch}\) as \(\left( \left[ \{A_i\}_{i = 0}^{q_1}\right] _{1}, \left[ \{B_i\}_{i = 0}^{q_2}\right] _{2} \right) \), samples \(\widetilde{\chi } \,{\leftarrow \!\!{\$ }\,}\mathbb {F}_p\), and defines \(\widetilde{\mathsf {Ch}} := \left( \left[ \{\widetilde{\chi }^i A_i\}_{i = 0}^{q_1}\right] _{1}, \left[ \{\widetilde{\chi }^i B_i\}_{i = 0}^{q_2}\right] _{2} \right) \).

Then \( Pr {\left[ \bar{\chi } \leftarrow \mathcal {A}^{\mathsf {Upd}\mathsf {O}}(\lambda )\right] } \le \mathsf {negl}(\lambda ), \) where \(\left( \left[ \{\bar{\chi }^i\}_{i = 0}^{q_1}\right] _{1}, \left[ \{\bar{\chi }^i\}_{i = 0}^{q_2}\right] _{2} \right) \) is the final \(\mathsf {Ch}\).

Remark 4

(Single adversarial updates after an honest setup.). As an alternative to the updatable setting defined in Fig. 1, one can consider a slightly different model of setup, where the adversary is given an initial honestly-generated SRS and is then allowed to perform a malicious update in one-shot fashion. Groth et al. show in [38] that the two definitions are equivalent for polynomial commitment based SNARKs. We use this simpler definition in our reductions.

In the full version [29], we show a reduction from \((q_1, q_2)\text {-}\mathsf {dlog}\) assumption to its variant in the updatable setting (with single adversarial update).

Generalized Forking Lemma. Although dubbed “general”, the forking lemma of [5] is not general enough for our purpose as it is useful only for protocols where a witness can be extracted from just two transcripts. To be able to extract a witness from, say, an execution of \(\boldsymbol{\mathsf {P}}\) we need at least \((3 \mathsf {n}+ 6)\) valid proofs (where \(\mathsf {n}\) is the number of constrains), \((\mathsf {n}+ 1)\) for \(\boldsymbol{\mathsf {S}}\), and \(2 \mathsf {n}+ 3\) for \(\boldsymbol{\mathsf {M}}\). Here we use a result by Attema et al. [3]Footnote 6 which lower-bounds the probability of generating a tree of accepting transcripts \(\mathsf {T}\). We restate their Proposition 2 in our notation:

Lemma 2

(Run Time and Success Probability). Let \(N = n_1 \cdot \cdots \cdot n_\mu \) and \(p = 2^{\varOmega (\lambda )}\). Let \(\varepsilon _{\mathsf {err}}(\lambda ) = 1 - \prod _{i=1}^{\mu }\left( 1 - \frac{n_i - 1}{p}\right) \). Assume adversary \(\mathcal {A}\) that makes up to q random oracle queries and outputs an accepting proof with probability at least \(\mathsf {acc}\). There exists a tree building algorithm \(\mathcal {T}\) for \((n_1, \ldots , n_\mu )\)-trees that succeeds in building a tree of accepting transcripts in expected running time \(N + q (N - 1)\) with probability at least

$$ \frac{\mathsf {acc}- (q + 1) \varepsilon _{\mathsf {err}}(\lambda )}{1 - \varepsilon _{\mathsf {err}}(\lambda )}. $$

Opening Uniqueness of Batched Polynomial Commitment Openings. To show the unique response property required by our main theorem we show that the polynomial commitment schemes employed by concrete proof systems have unique openings, which, intuitively, assures that there is only one valid opening for a given committed polynomial and evaluation point:

Definition 8

(Unique opening property). Let \(m \in \mathbb {N}\) be the number of committed polynomials, \(l \in \mathbb {N}\) number of evaluation points, \(\boldsymbol{c} \in \mathbb {G}^m\) be the commitments, \(\boldsymbol{z} \in \mathbb {F}_p^l\) be the arguments the polynomials are evaluated at, \(K_j\) set of indices of polynomials which are evaluated at \(z_j\), \(\boldsymbol{s_{i}}\) vector of evaluations of \(\mathsf {f_i}\), and \(\boldsymbol{o_j}, \boldsymbol{o'_j} \in \mathbb {F}_p^{K_j}\) be the commitment openings. Then for every \(\mathsf {PPT}\) adversary \(\mathcal {A}\)

figure e

We show that the polynomial commitment schemes of \(\text {Plonk}\), \({\text {Sonic}}\), and \({\text {Marlin}}\) satisfy this requirement in the full version [29].

Remark 5

In the full version [29], we presents efficient variants of KZG [40] polynomial commitment schemes used in \(\text {Plonk}\), \(\text {Sonic}\) and \(\text {Marlin}\) that support batched verification. Algorithms \(\mathsf {Com}\), \(\mathsf {Op}\), \(\mathsf {Verify}\) take vectors as input and receive an additional arbitrary auxiliary string. This adversarially chosen string only provides additional context for the computation of challenges and allows reconstruction of proof transcripts \(\tilde{\pi }[0..i]\) for batch challenge computations. We treat auxiliary input implicitly in the definition above.

5 Non-malleability of Plonk

In this section, we show that \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is simulation-extractable. To this end, we first use the unique opening property to show that \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) has the \({3\text {-}\mathsf {UR}}\) property, cf. Lemma 3. Next, we show that \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is rewinding-based knowledge sound. That is, given a number of accepting transcripts whose first 3 messages match, we can either extract a witness for the proven statement or use one of the transcripts to break the \(\mathsf {udlog}\) assumption. This result is shown in the AGM, cf. Lemma 4. We then show that \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is 3-programmable trapdoor-less ZK in the AGM, cf. Lemma 5.

Given rewinding-based knowledge soundness, \({3\text {-}\mathsf {UR}}\) and trapdoor-less zero-knowledge of \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\), we invoke Theorem 1 and conclude that \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is simulation-extractable.

5.1 Plonk Protocol Description

The Constraint System. Assume \(\mathsf {C}\) is a fan-in two arithmetic circuit, whose fan-out is unlimited and has \(\mathsf {n}\) gates and \(\mathsf {m}\) wires (\(\mathsf {n}\le \mathsf {m}\le 2\mathsf {n}\)). The constraint system of \(\text {Plonk}\) is defined as follows:

  • Let \(\boldsymbol{V} = (\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c})\), where \(\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c}\in [1 \, .. \, \mathsf {m}]^\mathsf {n}\). Entries \(\boldsymbol{a}_i, \boldsymbol{b}_i, \boldsymbol{c}_i\) represent indices of left, right and output wires of the circuit’s i-th gate.

  • Vectors \(\boldsymbol{Q} = (\boldsymbol{{{q}_{L}}}, \boldsymbol{{{q}_{R}}}, \boldsymbol{{{q}_{O}}}, \boldsymbol{{{q}_{M}}}, \boldsymbol{{{q}_{C}}}) \in (\mathbb {F}^\mathsf {n})^5\) are called selector vectors: (a) If the i-th gate is a multiplication gate then \(\boldsymbol{{{q}_{L}}}_i = \boldsymbol{{{q}_{R}}}_i = 0\), \(\boldsymbol{{{q}_{M}}}_i = 1\), and \(\boldsymbol{{{q}_{O}}}_i = -1\). (b) If the i-th gate is an addition gate then \(\boldsymbol{{{q}_{L}}}_i = \boldsymbol{{{q}_{R}}}_i = 1\), \(\boldsymbol{{{q}_{M}}}_i = 0\), and \(\boldsymbol{{{q}_{O}}}_i = -1\). (c) \(\boldsymbol{{{q}_{C}}}_i = 0\) for multiplication and addition gates.Footnote 7

We say that vector \(\boldsymbol{x}\in \mathbb {F}^\mathsf {m}\) satisfies constraint system if for all \(i \in [1 \, .. \, \mathsf {n}]\)

$$ \boldsymbol{{{q}_{L}}}_i \cdot \boldsymbol{x}_{\boldsymbol{a}_i} + \boldsymbol{{{q}_{R}}}_i \cdot \boldsymbol{x}_{\boldsymbol{b}_i} + \boldsymbol{{{q}_{O}}}\cdot \boldsymbol{x}_{\boldsymbol{c}_i} + \boldsymbol{{{q}_{M}}}_i \cdot (\boldsymbol{x}_{\boldsymbol{a}_i} \boldsymbol{x}_{\boldsymbol{b}_i}) + \boldsymbol{{{q}_{C}}}_i = 0. $$

Public inputs \(\left( \mathsf {x}_j\right) _{j = 1}^{\mathsf {\ell }}\) are enforced by adding the constrains

$$ \boldsymbol{a}_i = j, \boldsymbol{{{q}_{L}}}_i = 1, \boldsymbol{{{q}_{M}}}_i = \boldsymbol{{{q}_{R}}}_i = \boldsymbol{{{q}_{O}}}_i = 0, \boldsymbol{{{q}_{C}}}_i = -\mathsf {x}_j\,, $$

for some \(i \in [1 \, .. \, \mathsf {n}]\).

Algorithms Rolled Out. \(\text {Plonk}\) argument system is universal. That is, it allows to verify computation of any arithmetic circuit which has up to \(\mathsf {n}\) gates using a single SRS. However, to make computation efficient, for each circuit there is a preprocessing phase which extends the SRS with circuit-related polynomial evaluations.

For the sake of simplicity of the security reductions presented in this paper, we include in the SRS only these elements that cannot be computed without knowing the secret trapdoor \(\chi \). The rest of the preprocessed input can be computed using these SRS elements. We thus let them to be computed by the prover, verifier, and simulator separately.

\(\text {Plonk}\) SRS generating algorithm \(\mathsf {GenSRS}(\mathbf {R})\): The SRS generating algorithm picks at random \(\chi \,{\leftarrow \!\!{\$ }\,}\mathbb {F}_p\), computes and outputs \( \mathsf {srs}= \left( \left[ \{\chi ^i\}_{i = 0}^{\mathsf {n}+ 5}\right] _{1}, \left[ \chi \right] _{2} \right) . \)

Preprocessing: Let \(H = \{\omega ^i\}_{i = 1}^{\mathsf {n}}\) be a (multiplicative) \(\mathsf {n}\)-element subgroup of a field \(\mathbb {F}\) compound of \(\mathsf {n}\)-th roots of unity in \(\mathbb {F}\). Let \(\mathsf {L}_i(X)\) be the i-th element of an \(\mathsf {n}\)-elements Lagrange basis. During the preprocessing phase polynomials \(\mathsf {S_{id j}}, \mathsf {S_{\sigma j}}\), for \(\mathsf {j} \in [1 \, .. \, 3]\), are computed:

$$\begin{aligned} \begin{aligned} \mathsf {S_{id 1}}(X)&= X,\\ \mathsf {S_{id 2}}(X)&= k_1 \cdot X,\\ \mathsf {S_{id 3}}(X)&= k_2 \cdot X, \end{aligned} \qquad \begin{aligned} \mathsf {S_{\sigma 1}}(X)&= {\textstyle {\sum _{i = 1}^{\mathsf {n}} \sigma (i) \mathsf {L}_i(X)}},\\ \mathsf {S_{\sigma 2}}(X)&= {\textstyle \sum _{i = 1}^{\mathsf {n}} \sigma (\mathsf {n}+ i) \mathsf {L}_i(X)},\\ \mathsf {S_{\sigma 3}}(X)&={\textstyle \sum _{i = 1}^{\mathsf {n}} \sigma (2 \mathsf {n}+ i) \mathsf {L}_i(X)}. \end{aligned} \end{aligned}$$

Coefficients \(k_1\), \(k_2\) are such that \(H, k_1 \cdot H, k_2 \cdot H\) are different cosets of \(\mathbb {F}^*\), thus they define \(3 \cdot \mathsf {n}\) different elements. Gabizon et al. [28] notes that it is enough to set \(k_1\) to a quadratic residue and \(k_2\) to a quadratic non-residue.

Furthermore, we define polynomials \(\mathsf {q_L}, \mathsf {q_R}, \mathsf {q_O}, \mathsf {q_M}, \mathsf {q_C}\) such that

$$\begin{aligned} \begin{aligned} \mathsf {q_L}(X)&= {\textstyle \sum _{i = 1}^{\mathsf {n}}} \boldsymbol{{{q}_{L}}}_i \mathsf {L}_i(X), \\ \mathsf {q_R}(X)&= \textstyle \sum _{i = 1}^{\mathsf {n}} \boldsymbol{{{q}_{R}}}_i \mathsf {L}_i(X), \\ \mathsf {q_M}(X)&= \textstyle \sum _{i = 1}^{\mathsf {n}} \boldsymbol{{{q}_{M}}}_i \mathsf {L}_i(X), \end{aligned} \qquad \begin{aligned} \mathsf {q_O}(X)&= \textstyle \sum _{i = 1}^{\mathsf {n}} \boldsymbol{{{q}_{O}}}_i \mathsf {L}_i(X), \\ \mathsf {q_C}(X)&= \textstyle \sum _{i = 1}^{\mathsf {n}} \boldsymbol{{{q}_{C}}}_i \mathsf {L}_i(X). \\&\end{aligned} \end{aligned}$$

Proving Statements in \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\). We show how prover’s algorithm \(\mathsf {P}(\mathsf {srs}, \mathsf {x}=\left( \mathsf {w}'_i\right) _{i = 1}^\mathsf {\ell }, \mathsf {w}= \left( \mathsf {w}_i\right) _{i=1}^{3 \cdot \mathsf {n}})\) operates for the Fiat–Shamir transformed version of Plonk. Note that for notational convenience \(\mathsf {w}\) also contains the public input wires \(\mathsf {w}'_i=\mathsf {w}_i\), \(i\in [1 \, .. \, \ell ]\).

  • Message 1. Sample \(b_1, \ldots , b_9 \,{\leftarrow \!\!{\$ }\,}\mathbb {F}_p\); compute \(\mathsf {a}(X), \mathsf {b}(X), \mathsf {c}(X)\) as

    $$\begin{aligned} \mathsf {a}(X)&= (b_1 X + b_2)\mathsf {Z_H}(X) + \textstyle \sum _{i = 1}^{\mathsf {n}} \mathsf {w}_i \mathsf {L}_i(X) \\ \mathsf {b}(X)&= (b_3 X + b_4)\mathsf {Z_H}(X) + \textstyle \sum _{i = 1}^{\mathsf {n}} \mathsf {w}_{\mathsf {n}+ i} \mathsf {L}_i(X) \\ \mathsf {c}(X)&= (b_5 X + b_6)\mathsf {Z_H}(X) + \textstyle \sum _{i = 1}^{\mathsf {n}} \mathsf {w}_{2 \cdot \mathsf {n}+ i} \mathsf {L}_i(X) \end{aligned}$$

    Output polynomial commitments \(\left[ \mathsf {a}(\chi ), \mathsf {b}(\chi ), \mathsf {c}(\chi )\right] _{1}\).

  • Message 2. Compute challenges \(\beta , \gamma \in \mathbb {F}_p\) by querying random oracle on partial proof, that is, \( \beta = \mathcal {H}(\tilde{\pi }[0..1], 0)\,, \qquad \gamma = \mathcal {H}(\tilde{\pi }[0..1], 1)\,. \) Compute permutation polynomial \(\mathsf {z}(X)\)

    $$\begin{aligned}&\quad \,\, \mathsf {z}(X) = (b_7 X^2 + b_8 X + b_9)\mathsf {Z_H}(X) + \mathsf {L}_1(X) + \\&+ \sum _{i = 1}^{\mathsf {n}- 1} \left( \mathsf {L}_{i + 1} (X) \prod _{j = 1}^{i} \frac{ (\mathsf {w}_j +\beta \omega ^{j - 1} + \gamma )(\mathsf {w}_{\mathsf {n}+ j} + \beta k_1 \omega ^{j - 1} + \gamma )(\mathsf {w}_{2 \mathsf {n}+ j} +\beta k_2 \omega ^{j- 1} + \gamma )}{(\mathsf {w}_j+\sigma (j) \beta + \gamma )(\mathsf {w}_{\mathsf {n}+ j} + \sigma (\mathsf {n}+ j)\beta + \gamma )(\mathsf {w}_{2 \mathsf {n}+ j} + \sigma (2 \mathsf {n}+ j)\beta + \gamma )}\right) \end{aligned}$$

    Output polynomial commitment \(\left[ \mathsf {z}(\chi )\right] _{1}\)

  • Message 3. Compute the challenge \(\alpha = \mathcal {H}(\tilde{\pi }[0..2])\), compute the quotient polynomial

    $$\begin{aligned}&\mathsf {t}(X) = \\&(\mathsf {a}(X) \mathsf {b}(X) \mathsf {q_{M}}(X) + \mathsf {a}(X) \mathsf {q_{L}}(X) + \mathsf {b}(X)\mathsf {q_{R}}(X) + \mathsf {c}(X)\mathsf {q_{O}}(X) + \mathsf {PI}(X) + \mathsf {q_{C}}(X)) / \mathsf {Z_H}(X) +\\&+ ((\mathsf {a}(X) + \beta X + \gamma ) (\mathsf {b}(X) + \beta k_1 X + \gamma )(\mathsf {c}(X) + \beta k_2 X + \gamma )\mathsf {z}(X)) \alpha / \mathsf {Z_H}(X) \\&- (\mathsf {a}(X) + \beta \mathsf {S_{\sigma 1}}(X) + \gamma )(\mathsf {b}(X) + \beta \mathsf {S_{\sigma 2}}(X) + \gamma )(\mathsf {c}(X) + \beta \mathsf {S_{\sigma 3}}(X) + \gamma )\mathsf {z}(X \omega )) \alpha / \mathsf {Z_H}(X) \\&+ (\mathsf {z}(X) - 1) \mathsf {L}_1(X) \alpha ^2 / \mathsf {Z_H}(X) \end{aligned}$$

    Split \(\mathsf {t}(X)\) into degree less then \(\mathsf {n}\) polynomials \(\mathsf {t_{lo}}(X), \mathsf {t_{mid}}(X), \mathsf {t_{hi}}(X)\), such that \( \mathsf {t}(X) = \mathsf {t_{lo}}(X) + X^{\mathsf {n}} \mathsf {t_{mid}}(X) + X^{2 \mathsf {n}} \mathsf {t_{hi}}(X)\,. \) Output \(\left[ \mathsf {t_{lo}}(\chi ), \mathsf {t_{mid}}(\chi ), \mathsf {t_{hi}}(\chi )\right] _{1}\).

  • Message 4. Get the challenge \(\mathfrak {z}\in \mathbb {F}_p\), \(\mathfrak {z}= \mathcal {H}(\tilde{\pi }[0..3])\). Compute opening evaluations \( \mathsf {a}(\mathfrak {z}), \mathsf {b}(\mathfrak {z}), \mathsf {c}(\mathfrak {z}), \mathsf {S_{\sigma 1}}(\mathfrak {z}), \mathsf {S_{\sigma 2}}(\mathfrak {z}), \mathsf {t}(\mathfrak {z}), \mathsf {z}(\mathfrak {z}\omega ), \) Compute the linearization polynomial

    $$ \mathsf {r}(X) = \begin{aligned}&\mathsf {a}(\mathfrak {z}) \mathsf {b}(\mathfrak {z}) \mathsf {q_{M}}(X) + \mathsf {a}(\mathfrak {z}) \mathsf {q_{L}}(X) + \mathsf {b}(\mathfrak {z}) \mathsf {q_{R}}(X) + \mathsf {c}(\mathfrak {z}) \mathsf {q_{O}}(X) + \mathsf {q_{C}}(X) \\&+ \alpha \cdot \left( (\mathsf {a}(\mathfrak {z}) + \beta \mathfrak {z}+ \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta k_1 \mathfrak {z}+ \gamma )(\mathsf {c}(\mathfrak {z}) + \beta k_2 \mathfrak {z}+ \gamma ) \cdot \mathsf {z}(X)\right) \\&- \alpha \cdot \left( (\mathsf {a}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 1}}(\mathfrak {z}) + \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 2}}(\mathfrak {z}) + \gamma )\beta \mathsf {z}(\mathfrak {z}\omega ) \cdot \mathsf {S_{\sigma 3}}(X)\right) \\&+ \alpha ^2 \cdot \mathsf {L}_1(\mathfrak {z}) \cdot \mathsf {z}(X) \end{aligned} $$

    Output \(\mathsf {a}(\mathfrak {z}), \mathsf {b}(\mathfrak {z}), \mathsf {c}(\mathfrak {z}), \mathsf {S_{\sigma 1}}(\mathfrak {z}), \mathsf {S_{\sigma 2}}(\mathfrak {z}), \mathsf {t}(\mathfrak {z}), \mathsf {z}(\mathfrak {z}\omega ), \mathsf {r}(\mathfrak {z}).\)

  • Message 5. Compute the opening challenge \(v \in \mathbb {F}_p\), \(v = \mathcal {H}(\tilde{\pi }[0..4])\). Compute the openings for the polynomial commitment scheme

    $$\begin{aligned}&\mathsf {W_\mathfrak {z}}(X) = \frac{1}{X - \mathfrak {z}} \left( \begin{aligned}&\mathsf {t_{lo}}(X) + \mathfrak {z}^\mathsf {n}\mathsf {t_{mid}}(X) + \mathfrak {z}^{2 \mathsf {n}} \mathsf {t_{hi}}(X) - \mathsf {t}(\mathfrak {z}) + v(\mathsf {r}(X) - \mathsf {r}(\mathfrak {z})) + v^2 (\mathsf {a}(X) - \mathsf {a}(\mathfrak {z}))\\&+ v^3 (\mathsf {b}(X) - \mathsf {b}(\mathfrak {z})) + v^4 (\mathsf {c}(X) - \mathsf {c}(\mathfrak {z})) + v^5 (\mathsf {S_{\sigma 1}}(X) - \mathsf {S_{\sigma 1}}(\mathfrak {z})) \\&+ v^6 (\mathsf {S_{\sigma 2}}(X) - \mathsf {S_{\sigma 2}}(\mathfrak {z})) \end{aligned} \right) \\&\mathsf {W_{\mathfrak {z}\omega }}(X) = (\mathsf {z}(X) - \mathsf {z}(\mathfrak {z}\omega )) / (X - \mathfrak {z}\omega ) \end{aligned}$$

    Output \(\left[ \mathsf {W_{\mathfrak {z}}}(\chi ), \mathsf {W_{\mathfrak {z}\omega }}(\chi )\right] _{1}\).

Plonk verifier \(\mathsf {V}(\mathsf {srs}, \mathsf {x}, \pi )\): The \(\text {Plonk}\) verifier works as follows

  1. 1.

    Validate all obtained group elements.

  2. 2.

    Validate all obtained field elements.

  3. 3.

    Parse the instance as \(\{\mathsf {w}_i\}_{i = 1}^\mathsf {\ell }\leftarrow \mathsf {x}\).

  4. 4.

    Compute challenges \(\beta , \gamma , \alpha , \mathfrak {z}, v, u\) from the transcript.

  5. 5.

    Compute zero polynomial evaluation \(\mathsf {Z_H} (\mathfrak {z}) =\mathfrak {z}^\mathsf {n}- 1\).

  6. 6.

    Compute Lagrange polynomial evaluation \(\mathsf {L}_1 (\mathfrak {z}) = \frac{\mathfrak {z}^\mathsf {n}-1}{\mathsf {n}(\mathfrak {z}- 1)}\).

  7. 7.

    Compute public input polynomial evaluation \(\mathsf {PI}(\mathfrak {z}) = \sum _{i \in [1 \, .. \, \mathsf {\ell }]} \mathsf {w}_i \mathsf {L}_i(\mathfrak {z})\).

  8. 8.

    Compute quotient polynomials evaluations

    $$\begin{aligned} \mathsf {t} (\mathfrak {z}) = \Big ( \mathsf {r} (\mathfrak {z}) + \mathsf {PI}(\mathfrak {z}) - (\mathsf {a}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 1}}(\mathfrak {z}) + \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 2}}(\mathfrak {z}) + \gamma ) (\mathsf {c}(\mathfrak {z}) + \gamma )\mathsf {z}(\mathfrak {z}\omega ) \alpha - \mathsf {L}_1 (\mathfrak {z}) \alpha ^2 \Big ) / {\mathsf {Z_H}(\mathfrak {z})} \,. \end{aligned}$$
  9. 9.

    Compute batched polynomial commitment \(\left[ D\right] _{1} = v \left[ r\right] _{1} + u \left[ z\right] _{1}\) that is

    $$\begin{aligned} \left[ D\right] _{1}&= v \left( \begin{aligned}&\mathsf {a}(\mathfrak {z})\mathsf {b}(\mathfrak {z}) \cdot \left[ \mathsf {q_{M}}\right] _{1} + \mathsf {a}(\mathfrak {z}) \left[ \mathsf {q_{L}}\right] _{1} + \mathsf {b} \left[ \mathsf {q_{R}}\right] _{1} + \mathsf {c} \left[ \mathsf {q_{O}}\right] _{1} + \\&+ ( (\mathsf {a}(\mathfrak {z}) + \beta \mathfrak {z}+ \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta k_1 \mathfrak {z}+ \gamma ) (\mathsf {c} + \beta k_2 \mathfrak {z}+ \gamma ) \alpha + \mathsf {L}_1(\mathfrak {z}) \alpha ^2) + \\&- (\mathsf {a}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 1}}(\mathfrak {z}) + \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 2}}(\mathfrak {z}) + \gamma ) \alpha \beta \mathsf {z}(\mathfrak {z}\omega ) \left[ \mathsf {S_{\sigma 3}}(\chi )\right] _{1}) \end{aligned} \right) + \\&+ u \left[ \mathsf {z}(\chi )\right] _{1}\,. \end{aligned}$$
  10. 10.

    Computes full batched polynomial commitment \(\left[ F\right] _{1}\):

    $$\begin{aligned} \left[ F\right] _{1}&= \left( \left[ \mathsf {t_{lo}}(\chi )\right] _{1} + \mathfrak {z}^\mathsf {n}\left[ \mathsf {t_{mid}}(\chi )\right] _{1} + \mathfrak {z}^{2 \mathsf {n}} \left[ \mathsf {t_{hi}}(\chi )\right] _{1}\right) + u \left[ \mathsf {z}(\chi )\right] _{1} + \\&+ v \left( \begin{aligned}&\mathsf {a}(\mathfrak {z})\mathsf {b}(\mathfrak {z}) \cdot \left[ \mathsf {q_{M}}\right] _{1} + \mathsf {a}(\mathfrak {z}) \left[ \mathsf {q_{L}}\right] _{1} + \mathsf {b}(\mathfrak {z}) \left[ \mathsf {q_{R}}\right] _{1} + \mathsf {c}(\mathfrak {z}) \left[ \mathsf {q_{O}}\right] _{1} + \\&+ ( (\mathsf {a}(\mathfrak {z}) + \beta \mathfrak {z}+ \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta k_1 \mathfrak {z}+ \gamma ) (\mathsf {c}(\mathfrak {z}) + \beta k_2 \mathfrak {z}+ \gamma ) \alpha + \mathsf {L}_1(\mathfrak {z}) \alpha ^2) + \\&- (\mathsf {a}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 1}}(\mathfrak {z}) + \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 2}}(\mathfrak {z}) + \gamma ) \alpha \beta \mathsf {z}(\mathfrak {z}\omega ) \left[ \mathsf {S_{\sigma 3}}(\chi )\right] _{1}) \end{aligned} \right) \\&+ v^2 \left[ \mathsf {a}(\chi )\right] _{1} + v^3 \left[ \mathsf {b}(\chi )\right] _{1} + v^4 \left[ \mathsf {c}(\chi )\right] _{1} + v^5 \left[ \mathsf {S_{\sigma 1}(\chi )}\right] _{1} + v^6 \left[ \mathsf {S_{\sigma 2}}(\chi )\right] _{1}\,. \end{aligned}$$
  11. 11.

    Compute group-encoded batch evaluation \(\left[ E\right] _{1}\)

    $$\begin{aligned} \left[ E\right] _{1} = \frac{1}{\mathsf {Z_H}(\mathfrak {z})}&\left[ \begin{aligned}&\mathsf {r}(\mathfrak {z}) + \mathsf {PI}(\mathfrak {z}) + \alpha ^2 \mathsf {L}_1 (\mathfrak {z}) + \\&- \alpha \left( (\mathsf {a}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 1}} (\mathfrak {z}) + \gamma ) (\mathsf {b}(\mathfrak {z}) + \beta \mathsf {S_{\sigma 2}} (\mathfrak {z}) + \gamma ) (\mathsf {c}(\mathfrak {z}) + \gamma ) \mathsf {z}(\mathfrak {z}\omega ) \right) \end{aligned} \right] _{1}\\ +&\left[ v \mathsf {r}(\mathfrak {z}) + v^2 \mathsf {a}(\mathfrak {z}) + v^3 \mathsf {b}(\mathfrak {z}) + v^4 \mathsf {c}(\mathfrak {z}) + v^5 \mathsf {S_{\sigma 1}}(\mathfrak {z}) + v^6 \mathsf {S_{\sigma 2}}(\mathfrak {z}) + u \mathsf {z}(\mathfrak {z}\omega ) \right] _{1}\,. \end{aligned}$$
  12. 12.

    Check whether the verification equation holds

    $$\begin{aligned}&\left( \left[ \mathsf {W_{\mathfrak {z}}}(\chi )\right] _{1} + u \cdot \left[ \mathsf {W_{\mathfrak {z}\omega }}(\chi )\right] _{1} \right) \bullet \left[ \chi \right] _{2} -\nonumber \\&\qquad \qquad \quad \,\,\, \left( \mathfrak {z}\cdot \left[ \mathsf {W_{\mathfrak {z}}}(\chi )\right] _{1} + u \mathfrak {z}\omega \cdot \left[ \mathsf {W_{\mathfrak {z}\omega }}(\chi )\right] _{1} + \left[ F\right] _{1} - \left[ E\right] _{1} \right) \bullet \left[ 1\right] _{2} = 0\,. \end{aligned}$$
    (1)

    The verification equation is a batched version of the verification equation from [40] which allows the verifier to check openings of multiple polynomials in two points (instead of checking an opening of a single polynomial at one point).

Plonk simulator \(\mathsf {Sim}_\chi (\mathsf {srs}, \mathsf {td}= \chi , \mathsf {x})\): We describe the simulator in Lemma 5.

5.2 Simulation Extractability of \(\text {Plonk}\)

Due to lack of space, we provide here only theorem statements and intuition for why they hold. Full proofs are given in the full version [29].

Unique Response Property

Lemma 3

Let \(\boldsymbol{\mathsf {PC}}_{\boldsymbol{\mathsf {P}}}\) be a polynomial commitment that is \(\varepsilon _\mathsf {bind}(\lambda )\)-binding and has unique opening property with loss \(\varepsilon _\mathsf {op}(\lambda )\). Then \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is \({3\text {-}\mathsf {UR}}\) against algebraic adversaries, who makes up to q random oracle queries, with security loss \(\varepsilon _\mathsf {bind}(\lambda ) + \varepsilon _\mathsf {op}( \lambda )\).

Proof

(Intuition). We show that an adversary who can break the 3-unique response property of \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) can be either used to break the commitment scheme’s evaluation binding or unique opening property. The former happens with the probability upper-bounded by \(\varepsilon _\mathsf {bind}(\lambda )\), the latter with the probability upper bounded by \(\varepsilon _\mathsf {op}(\lambda )\).

Rewinding-Based Knowledge Soundness

Lemma 4

\(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is \((3, 3 \mathsf {n}+ 6)\)-rewinding-based knowledge sound against algebraic adversaries who make up to q random oracle queries with security loss

$$ \varepsilon _{\mathsf {ks}}(\lambda ,\mathsf {acc}, q) \le \left( 1 - \frac{\mathsf {acc}- (q + 1) \left( \frac{3 \mathsf {n}+ 5}{p} \right) }{1 - \frac{3 \mathsf {n}+ 5}{p}}\right) + (3 \mathsf {n}+ 6) \cdot \varepsilon _\mathsf {udlog}(\lambda ) \,, $$

Here \(\mathsf {acc}\) is a probability that the adversary outputs an accepting proof, and \(\varepsilon _\mathsf {udlog}(\lambda )\) is security of \((\mathsf {n}+ 5, 1)\)-\(\mathsf {udlog}\) assumption.

Proof

(Intuition). We use Attema et al. [3, Proposition 2] to bound the probability that an algorithm \(\mathcal {T}\) does not obtain a tree of accepting transcripts in an expected number of runs. This happens with probability at most

$$ 1 - \frac{\mathsf {acc}- (q + 1) \left( \frac{3 \mathsf {n}+ 5}{p} \right) }{1 - \frac{3 \mathsf {n}+ 5}{p}} $$

Then we analyze the case that one of the proofs in the tree \(\mathsf {T}\) outputted by \(\mathcal {T}\) is not accepting by the ideal verifier. This discrepancy can be used to break an instance of an updatable dlog assumption which happens with probability at most \((3 \mathsf {n}+ 6) \cdot \varepsilon _\mathsf {udlog}(\lambda )\).

Trapdoor-Less Zero-Knowledge of Plonk

Lemma 5

\(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is 3-programmable trapdoor-less zero-knowledge.

Proof

(Intuition). The simulator, that does not know the SRS trapdoor can make a simulated proof by programming the random oracle. It proceeds as follows. It picks a random witness and behaves as an honest prover up to the point when a commitment to the polynomial \(\mathsf {t}(X)\) is sent. Since the simulator picked a random witness and \(\mathsf {t}(X)\) is a polynomial only (modulo some negligible function) when the witness is correct, it cannot compute commitment to \(\mathsf {t}(X)\) as it is a rational function. However, the simulator can pick a random challenge \(\mathfrak {z}\) and a polynomial \(\mathsf {\tilde{t}}(X)\) such that \(\mathsf {t} (\mathfrak {z}) = \mathsf {\tilde{t}} (\mathfrak {z})\). Then the simulator continues behaving as an honest prover. We argue that such a simulated proof is indistinguishable from a real one.

Simulation Extractability of \({{\mathbf {\mathsf{{P}}}}}_{{\mathbf {\mathsf{{FS}}}}}\)

Since Lemmas 3 to 5 hold, \(\boldsymbol{\mathsf {P}}\) is \({3\text {-}\mathsf {UR}}\), rewinding-based knowledge sound and trapdoor-less zero-knowledge. We now make use of Theorem 1 and show that \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is simulation-extractable as defined in Definition 2.

Corollary 1

(Simulation extractability of \(\boldsymbol{\mathsf {P}}_\mathsf {FS}\)).\(\boldsymbol{\mathsf {P}}_\mathsf {FS}\) is updatable simulation-extractable against any \(\mathsf {PPT}\) adversary \(\mathcal {A}\) who makes up to q random oracle queries and returns an accepting proof with probability at least \(\mathsf {acc}\) with extraction failure probability

$$ \varepsilon _{\mathsf {se}}(\lambda , \mathsf {acc}, q) \le \left( 1 - \frac{\mathsf {acc}- \varepsilon _\mathsf {ur}(\lambda ) - (q + 1) \varepsilon _{\mathsf {err}}(\lambda )}{1 - \varepsilon _{\mathsf {err}}(\lambda )}\right) + (3 \mathsf {n}+ 6) \cdot \varepsilon _\mathsf {udlog}(\lambda ), $$

where \(\varepsilon _{\mathsf {err}}(\lambda ) = \frac{3 \mathsf {n}+ 5}{p}\), \(\varepsilon _\mathsf {ur}(\lambda ) \le \varepsilon _\mathsf {bind}(\lambda ) + \varepsilon _\mathsf {op}(\lambda )\), p is the size of the field, and \(\mathsf {n}\) is the number of constrains in the circuit.