Nervos Researcher Alan Szepieniec’s Paper Accepted by the International Association for Cryptologic Research (IACR)
Cryptography researcher of the Nervos Foundation Alan Szepieniec ‘s paper “Transparent SNARKs from DARK Compilers” was recently accepted by the International Association for Cryptologic Research (IACR) and delivered as a presentation at the Eurocrypt 2020 conference.
Alan Szepieniec is a cryptography researcher for the Nervos Foundation and holds a PhD in cryptography from the COSIC laboratory of the University of Leuven, Belgium. Research directions include post-quantum cryptography, especially quadratic multi-component cryptosystems, zero-knowledge proofs, quantum-resistant cryptographic algorithms and quantum-resistant cryptographic analysis, cryptographic theory and provable security, mathematical theory and complexity theory in public-key cryptography.
The paper “Transparent SNARKs from DARK Compilers” accepted by Eurocrypt 2020 was co-authored by Alan with Stanford University and Findora researchers Benedikt Bünz and Ben Fisch and published in May.
This basic work has contributed a new universal tool without Trusted Setup to the field of zero-knowledge proofs, moving the research work of Nervos in 2020 a solid step forward.
Alan Szepieniec’s last paper was “Eaglesong: an ARX Hash with Fast Diffusion”, which was completed in May 2019 with Tomer Ashur. The paper proposed a new hash algorithm Eaglesong and was awarded the fifth Romanian Cryptology Days Conference reception and presentation.
In the future, Nervos researchers will also continue to conduct in-depth research in the field of cryptography, laying a solid foundation for Nervos to become the infrastructure of the cryptoeconomic world.
About Eurocrypt
Eurocrypt is one of the three flagship conferences hosted by the International Association of Cryptological Research (IACR), the most famous academic conference in cryptography. The Annual International Conference on the Theory and Applications of Cryptographic Techniques is held every spring in Europe. This series of conferences was first held in 1982 and Eurocrypt 2020 is the 39th International Conference on Cryptography Theory and Application, which was run as a virtual conference for the first time.
Birth of this Paper
One of the obvious and immediate predecessors of this work is the paper entitled “Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains”, by Dan Boneh, Benedikt Bünz and Ben Fisch. In this paper, the authors develop tools based on groups of unknown order to generate cryptographic schemes like accumulators and vector commitments. Alan Szepieniec had studied these tools and in an initially unrelated research effort was looking for ways to improve the STARK proof system by relying on more potent cryptographic tools than mere hashes.
At an event shortly after Eurocrypt 2019, Alan approached Benedikt with a question about applying tools for groups of unknown order to STARK-like proof systems. The first version of the main protocol dates back to a follow-up email written shortly after that conversation. A couple of weeks later, Ben had joined the team, the main protocol had evolved into something almost unrecognizable from its first version, and the project’s appropriate goal had been recalibrated to not just producing a new tool in the SNARK toolbox, nor to producing a new standalone transparent SNARK, but to re-evaluate the entire field of SNARKs in light of the DARK Compilers that can make them Transparent.
Academic Background
Non-interactive proof systems produce a string of cryptographic data attesting to the honest execution of a computation, called a proof. The prover, the party running the computation and generating the proof, is subject to alternate resource constraints from the verifier, the part who verifies the proof’s correctness. The nature of this resource disparity gives rise to many questions of theoretical and practical interest. However, in the context of cryptography, we generally focus on two types of resource disparities. First, when the prover is allowed much more time than the verifier, the latter is characterized as succinct and the proof system as a whole as a Succinct Non-interactive Argument of Knowledge (SNARK). Second, when the prover is allowed access to secret information and the verifier is not, then the proof system is said to provide zero-knowledge (ZK).
SNARKs and zero-knowledge proof systems (as well as zk-SNARKs, which feature the best of both worlds) have immediate applications to blockchains because their achieved properties, succinctness and zero-knowledge, translate to scalability and privacy. Rather than process a large number of blocks, a succinct node can verify that the claimed output of this processing is indeed valid, with much less work; or rather than verifying a bunch of signatures, a succinct node can verify a small proof that attests to the validity of all signatures in one go. Likewise, rather than expose sensitive information crucial to modify or act on a smart contract, the owner can simply provide the requisite update along with a zk-SNARK that enables the rest of the network to verify the correctness of the update.
Up until now, there were only two cryptographic foundations to generate SNARKs from. The first method, which traces its origin back to the original PCP theorem, is through Merkle trees of Reed-Solomon codewords and is best represented in the STARK proof system. While the resulting proofs are quick to verify, they are over hundreds of kilobytes in size. The second method is through elliptic curves equipped with cryptographic bilinear maps, also known as pairings. While the proof size here is tiny — hundreds of bytes — the drawback is that this size can only be achieved at the expense of a trusted setup procedure.
Abstract of the paper
We construct a new polynomial commitment scheme for univariate and multivariate polynomials over finite fields, with logarithmic size evaluation proofs and verification time, measured in the number of coefficients of the polynomial. The underlying technique is a Diophantine Argument of Knowledge (DARK), leveraging integer representations of polynomials and groups of unknown order. Security is shown from the strong RSA and the adaptive root assumptions. Moreover, the scheme does not require a trusted setup if instantiated with class groups. We apply this new cryptographic compiler to a restricted class of algebraic linear IOPs, which we call Polynomial IOPs, to obtain doubly-efficient public-coin interactive arguments of knowledge for any NP relation with succinct communication. With linear preprocessing, the online verifier’s work is logarithmic in the circuit complexity of the relation.
There are many existing examples of Polynomial IOPs (PIOPs) dating back to the first PCP (BFLS, STOC’91). We present a generic compilation of any PIOP using our DARK polynomial commitment scheme. In particular, compiling the PIOP from PLONK (GWC, ePrint’19), an improvement on Sonic (MBKM, CCS’19), yields a public-coin interactive argument with quasi-linear preprocessing, quasi-linear (online) prover time, logarithmic communication, and logarithmic (online) verification time in the circuit size. Applying Fiat-Shamir results in a SNARK, which we call Supersonic.
Supersonic is also concretely efficient with 10KB proofs and under 100ms verification time for circuits with 1 million gates (estimated for 120-bit security). Most importantly, this SNARK is transparent: it does not require a trusted setup. We obtain zk-SNARKs by applying a hiding variant of our polynomial commitment scheme with zero-knowledge evaluations. Supersonic is the first complete zk-SNARK system that has both a practical prover time as well as asymptotically （strictly）logarithmic proof size and verification time.
For more information about this paper:
https://eprint.iacr.org/2019/1229.pdf
For more papers published by Dr. Alan Szepieniec:
https://www.esat.kuleuven.be/cosic/people/alan-szepieniec/
For more information about Eurocrypt 2020, please check the official website:
https://eurocrypt.iacr.org/2020/
Nervos Researcher Alan Szepieniec’s Paper Accepted by the International Association for… was originally published in Nervos Network on Medium, where people are continuing the conversation by highlighting and responding to this story.