Polynomial and vector commitments
Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments.
Dan Boneh, Justin Drake, Ben Fisch, Ariel Gabizon.
Crypto 2021. PDF.
Polynomial commitment schemes (PCS) have recently been in the spotlight for their key role in building SNARKs. A PCS provides the ability to commit to a polynomial over a finite field and prove its evaluation at points. A succinct PCS has commitment and evaluation proof size sublinear in the degree of the polynomial. An efficient PCS has sublinear proof verification. Any efficient and succinct PCS can be used to construct a SNARK with similar security and efficiency characteristics (in the random oracle model).
Proof-carrying data (PCD) enables a set of parties to carry out an indefinitely long distributed computation where every step along the way is accompanied by a proof of correctness. It generalizes incrementally verifiable computation and can even be used to construct SNARKs. Until recently, however, the only known method for constructing PCD required expensive SNARK recursion. A system called Halo first demonstrated a new methodology for building PCD without SNARKs, exploiting an aggregation property of the Bulletproofs innerproduct argument. The construction was heuristic because it makes non-black-box use of a concrete instantiation of the Fiat-Shamir transform. We expand upon this methodology to show that PCD can be (heuristically) built from any homomorphic polynomial commitment scheme (PCS), even if the PCS evaluation proofs are neither succinct nor efficient. In fact, the Halo methodology extends to any PCS that has an even more general property, namely the ability to aggregate linear combinations of commitments into a new succinct commitment that can later be opened to this linear combination. Our results thus imply new constructions of SNARKs and PCD that were not previously described in the literature and serve as a blueprint for future constructions as well.
Aggregatable subvector commitments for stateless cryptocurrencies.
Alin Tomescu, Ittai Abraham, Vitalik Buterin, Justin Drake, Dankrad Feist, Dmitry Khovratovich.
SCN 2020. PDF.
An aggregatable subvector commitment (aSVC) scheme is a vector commitment (VC) scheme that can aggregate multiple proofs into a single, small subvector proof. In this paper, we formalize aSVCs and give a construction from constant-sized polynomial commitments. Our construction is unique in that it has linear-sized public parameters, it can compute all constant-sized proofs in quasilinear time, it updates proofs in constant time and it can aggregate multiple proofs into a constant-sized subvector proof. Furthermore, our concrete proof sizes are small due to our use of pairing-friendly groups. We use our aSVC to obtain a payments-only stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block's proof overhead to a single group element, which is optimal. Furthermore, our subvector proofs speed up block verification and our smaller public parameters further reduce block size.
Efficient polynomial commitment schemes for multiple points and polynomials.
Dan Boneh, Justin Drake, Ben Fisch, Ariel Gabizon.
We present an enhanced version of the Kate, Zaverucha and Goldberg polynomial commitment scheme [KZG10] where a single group element can be an opening proof for multiple polynomials each evaluated at a different arbitrary subset of points.
As a sample application we “plug in” this scheme into the PLONK proving system[GWC19] to obtain improved proof size and prover run time at the expense of additional verifier G2 operations and pairings, and additional G2 SRS elements.
We also present a second scheme where the proof consists of two group elements and the verifier complexity is better than previously known batched verification methods for [KZG10].
Verifiable delay functions and random beacons
Not So Slowth: Invertible VDF for Ethereum and others.
Dmitry Khovratovich, Mary Maller, Pratyush Ranjan Tiwari.
We give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand f≤n/3 faulty parties), has a constant expected number of rounds, has O~(n3) expected communication complexity, and assumes only the existence of a PKI. Prior to our work, the best A-DKG protocols required Ω(n) expected number of rounds, and Ω(n4) expected communication.
Our A-DKG protocol relies on several building blocks that are of independent interest. We define and design a Proposal Election (PE) protocol that allows parties to retrospectively agree on a valid proposal after enough proposals have been sent from different parties. With constant probability the elected proposal was proposed by a nonfaulty party. In building our PE protocol, we design a Verifiable Gather protocol which allows parties to communicate which proposals they have and have not seen in a verifiable manner. The final building block to our A-DKG is a Validated Asynchronous Byzantine Agreement (VABA) protocol. We use our PE protocol to construct a VABA protocol that does not require leaders or an asynchronous DKG setup. Our VABA protocol can be used more generally when it is not possible to use threshold signatures.
Aggregatable Distributed Key Generation.
Kobi Gurkan, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, Alin Tomescu.
Eurocrypt 2021. PDF.
In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from O(n2) to O(nlogn), where n denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity. We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. Finally, we experimentally evaluate our DKG and show that the perparty overheads scale linearly and are practical. For 64 parties, it takes 71 ms to share and 359 ms to verify the overall transcript, while for 8192 parties, it takes 8 s and 42.2 s respectively.
Verifiable Delay Functions from Supersingular Isogenies and Pairings.
Luca De Feo, Simon Masson, Christophe Petit, Antonio Sanso.
Asiacrypt 2019. PDF.
We present two new Verifiable Delay Functions (VDF) based on assumptions from elliptic curve cryptography. We discuss both the advantages and some drawbacks of our constructions, we study their security and we demonstrate their practicality with a proof-of-concept implementation.
Post-Quantum Verifiable Random Function from Symmetric Primitives in PoS Blockchain.
Maxime Buser, Rafael Dowsley, Muhammed F. Esgin, Shabnam Kasra Kermanshahi, Veronika Kuchta, Joseph K. Liu, Raphael Phan, and Zhenfei Zhang.
ESORICS 2022. PDF.
Verifiable Random Functions (VRFs) play a key role in Proof-of-Stake blockchains such as Algorand to achieve highly scalable consensus, but currently deployed VRFs lack post-quantum security, which is crucial for future-readiness of blockchain systems. This work presents the first quantum-safe VRF scheme based on symmetric primitives. Our main proposal is a practical many-time quantum-safe VRF construction, X-VRF, based on the XMSS signature scheme. An innovation of our work is to use the state of the blockchain to counter the undesired stateful nature of XMSS by constructing a blockchain-empowered VRF. While increasing the usability of XMSS, our technique also enforces honest behavior when creating an X-VRF output so as to satisfy the fundamental uniqueness property of VRFs. We show how X-VRF can be used in the Algorand setting to extend it to a quantum-safe blockchain and provide four instances of X-VRF with different key life-time. Our extensive performance evaluation, analysis and implementation indicate the effectiveness of our proposed constructions in practice. Particularly, we demonstrate that X-VRF is the most efficient quantum-safe VRF with a maximum proof size of 3 KB and a possible TPS of 449 for a network of thousand nodes.
SnarkPack: Practical SNARK Aggregation.
Nicolas Gailly, Mary Maller, Anca Nitulescu.
FC 2022. PDF.
Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short and efficiently verifiable proofs that do not reveal anything more than the correctness of the statement. zk-SNARKs are widely used in decentralised systems to address privacy and scalability concerns.
A major drawback of such proof systems in practice is the requirement to run a trusted setup for the public parameters. Moreover, these parameters set an upper bound to the size of the computations or statements to be proven, which results in new scalability problems.
We design and implement SnarkPack, a new argument that further reduces the size of SNARK proofs by means of aggregation. Our goal is to provide an off-the-shelf solution that is practical in the following sense: (1) it is compatible with existing deployed SNARK systems, (2) it does not require any extra trusted setup. SnarkPack is designed to work with Groth16 scheme and has logarithmic size proofs and a verifier that runs in logarithmic time in the number of proofs to be aggregated. Most importantly, SnarkPack reuses the public parameters from Groth16 system.
SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 163ms, yielding a verification mechanism that is exponentially faster than other solutions. SnarkPack can be used in blockchain applications that rely on many SNARK proofs such as Proof-of-Space or roll-up solutions.
Proofs for inner pairing products and applications.
Benedikt Bünz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, Psi Vesely.
Asiacrypt 2021. PDF.
We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of n source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by 6 log n target group exponentiations. Proofs are of size 6 log n target group elements, computed using 6n pairings and 4n exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification,O(d) prover complexity for degree d polynomials (not including the cost to evaluate the polynomial), and a CRS of size O(d). Concretely, this means that for d = 228, producing an evaluation proof in our protocol is 76× faster than doing so in the KZG [KZG10] commitment scheme, and the CRS in our protocol is 1,000× smaller: 13MB vs 13GB for KZG. This gap only grows as the degree increases. Our polynomial commitment scheme is applicable to both univariate and bivariate polynomials.
As a second application, we introduce an argument for aggregating n Groth16 zkSNARKs into an O(logn) sized proof. Our protocol is significantly more efficient than aggregating these SNARKs via recursive composition [BCGMMW20]: we can aggregate about 130,000 proofs in 25min, while in the same time recursive composition aggregates just 90 proofs.
Finally, we show how to apply our aggregation protocol to construct a low-memory SNARK for machine computations. For a computation that requires time T and space S, our SNARK produces proofs in space O~(S+T), which is significantly more space efficient than a monolithic SNARK, which requires space O~(S⋅T).
Markulf Kohlweiss, Mary Maller, Janno Siim, Mikhail Volkhov.
Asiacrypt 2021. PDF.
Succinct non-interactive arguments of knowledge (SNARKs) have found numerous applications in the blockchain setting and elsewhere. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). Our contributions are two-fold:
– We give a security framework for non-interactive zero-knowledge arguments with a ceremony protocol.
– We revisit the ceremony protocol of Groth's SNARK [Bowe et al., 2017]. We show that the original construction can be simplified and optimized, and then prove its security in our new framework. Importantly, our construction avoids the random beacon model used in the original work.
T5: Hashing Five Inputs with Three Compression Calls.
Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, Mridul Nandi.
ITC 2021. PDF.
We prove that this construction matches Stam’s bound, by providing O~(q2/2n) collision security and O(q3/22n+nq/2n) preimage security (the latter term dominates in the region of interest, when q≤2n/2). In particular, it provides birthday security for hashing 5 inputs using three 2n-to-n compression calls, instead of only 4 inputs in prior constructions.
Thus, we get a sequential variant of the Merkle-Damgard (MD) hashing, where t message blocks are hashed using only 3t/4 calls to the 2n-to-n compression functions; a 25% saving over traditional hash function constructions. This time reduces to t/4 (resp. t/2) sequential calls using 3 (resp. 2) parallel execution units; saving a factor of 4 (resp. 2) over the traditional MD-hashing, where parallelism does not help to process one message.
We also get a novel variant of a Merkle tree, where t message blocks can be processed using 0.75(t − 1) compression function calls and depth 0.86log2t, thereby saving 25% in the number of calls and 14% in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree.
For the aggressive variant, we reduce the proof length to a 29% overhead compared to Merkle trees (1.29log2t vs log2t), but the verification time is now 14% faster (0.86log2t vs log2t). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid t-block message.
How to Prove Schnorr Assuming Schnorr: Security of Multi-and Threshold Signatures.
Elizabeth Crites, Chelsea Komlo, Mary Maller.
In this paper, we present new techniques for proving the security of multi- and threshold signature schemes under discrete logarithm assumptions in the random oracle model. The purpose is to provide a simple framework for analyzing the relatively complex interactions of these schemes in a concurrent model, thereby reducing the risk of attacks. We make use of proofs of possession and prove that a Schnorr signature suffices as a proof of possession in the algebraic group model without any tightness loss. We introduce and prove the security of a simple, three-round multisignature SimpleMuSig.
Using our new techniques, we prove the concurrent security of a variant of the MuSig2 multisignature scheme that includes proofs of possession as well as the FROST threshold signature scheme. These are currently the most efficient schemes in the literature for generating Schnorr signatures in a multiparty setting. Our variant of MuSig2, which we call SpeedyMuSig, has faster key aggregation due to the proofs of possession.
Reputable List Curation from Decentralized Voting.
Elizabeth Crites, Mary Maller, Sarah Meiklejohn, Rebekah Mercer.
PETS 2020. PDF.
Token-curated registries (TCRs) are a mechanism by which a set of users are able to jointly curate a reputable list about real-world information. Entries in the registry may have any form, so this primitive has been proposed for use— and deployed— in a variety of decentralized applications, ranging from the simple joint creation of lists to helping to prevent the spread of misinformation online. Despite this interest, the security of this primitive is not well understood, and indeed existing constructions do not achieve strong or provable notions of security or privacy. In this paper, we provide a formal cryptographic treatment of TCRs as well as a construction that provably hides the votes cast by individual curators. Along the way, we provide a model and proof of security for an underlying voting scheme, which may be of independent interest.