4th Annual ZKProof WorkshopHome Edition

Amid the continuing health concerns surrounding the coronavirus (COVID-19), the ZKProof Steering Committee has decided to hold the 4th ZKProof Workshop as an online conference.

The goals of the ZKProof initiative are to promote the standardization of zero-knowledge proof cryptography and to increase the engagement of companies and researchers worldwide. We are aware that a virtual event limits the personal interaction that is desirable for strengthening any community, especially in the cryptography community, which benefits greatly from these interactions.

Our immersive online workshop experience encompasses our goals, focusing on productive interactions and the high-quality discussions. This virtual format will make the workshop accessible and enable even more community members to take an active role in the standardization initiative. We strongly encourage everyone to join us in every session, because we value community participation and many of the discussions will continue from one session to another. Furthermore, we are hosting networking sessions throughout the event where you will be able to meet your peers, have tea with a friend, and more.

We thank our sponsors for their support.

Important Information

Dates: April 19 – April 29
Registration: Register here
Location: Zoom conference room – participants will receive a link for the event.
Schedule: See here for the schedule

Info for Registered Participants

We encourage everyone to participate in discussions both online and offline, and as such we have set up three different types of tools

• Zoom for talks and live discussions
• The community forum and our Telegram group for offline discussions and chats
• Collaborative tools for simultaneous work: (1) hackmd for writing and note-taking; (2) Miro for visuals and diagrams

The accepted papers are now published and we encourage all participants to review them before the discussions.

Week 1: Monday, April 19

Session Chairs & Moderators: Eran Tromer

3:00 PM (UTC)
Intro
Welcoming Remarks
Daniel Benarroch
3:15 PM (UTC)
Keynote
Pushing the Limits of Zero Knowledge Applications
Joshua Baron

Josh will discuss interim results of the DARPA Securing Information for Encrypted Verification and Evaluation (SIEVE) program. The SIEVE program seeks to advance the state of the art in ZK proofs to enable complex, defense-relevant applications. SIEVE will use ZK proofs to enable the verification of capabilities relevant to the US Department of Defense without revealing the sensitive details associated with those capabilities. SIEVE will aim to accomplish this goal by dramatically increasing the expressivity of problem statements for which ZK proofs can be constructed. SIEVE will also focus on increasing the efficiency of ZK proof technology to enable large, complex proof statements (e.g., billions of gates or more).

4:00 PM (UTC)
Break
Coffee & Short Networking

4:20 PM (UTC)
Paper Discussion
Proposal: Leo: A Programming Language for Formally Verified, Zero-Knowledge Applications
Howard Wu & Collin Chin

Authors: Collin Chin, Howard Wu, Raymond Chu, Alessandro Coglio, Eric McCarthy and Eric Smith

Decentralized ledgers that support rich applications suffer from three limitations. First, applications are provisioned tiny execution environments with limited running time, minimal stack size, and restrictive instruction sets. Second, applications must reveal their state transition, enabling miner front running attacks and consensus instability. Third, applications offer weak guarantees of correctness and safety. We design, implement, and evaluate LEO, a new programming language designed for formally verified, zero-knowledge applications. LEO provisions a powerful execution environment that is not restricted in running time, stack size, or instruction sets. Besides offering application privacy and mitigating miner-extractable value (MEV),LEO achieves two fundamental properties. First, applications are formally verified with respect to their high-level specification. Second, applications can be succinctly verified by anyone, regardless of the size of application. LEOis the first known programming language to introduce a testing framework, package registry, import resolver, remote compiler, and theorem prover for general-purpose, zero-knowledge applications.

5:20 PM (UTC)
Paper Discussion
Proposal: Σ-protocols
Michele Orrù

Authors: Stephan Krenn and Michele Orrù

Over the last years, zero-knowledge proofs of knowledge based on Σ-protocols have found numerous applications. However, up to date there is still a lack of standardization of such protocols, potentially hindering even broader deployment, and increasing the risk of insecure implementations. This document proposes a standardization effort for non-interactive Σ-protocols in prime order groups, allowing for AND and OR composition, either in compact (challenge, response) or batchable form(commitment, response). The document provides the necessary formal background, specifies the protocols in full details, provides examples, suggests concrete instantiations (e.g., regarding the selection of elliptic curves or hash functions), and provides guidelines to ease the secure and compatible implementation of Σ-protocols.

6:30 PM (UTC)
End of Day

Week 1: Tuesday, April 20

Session Chairs & Moderators: Mary Maller & Daniel Benarroch

3:00 PM (UTC)
Paper Discussion
Proposal: An Algebraic Framework for Universal and Updatable zkSNARKs
Arantxa Zapico

Authors: Carla Ràfols and Arantxa Zapico

We introduce Verifiable Subspace Sampling Arguments, a new information theoretic interactive proof system in which the prover shows that a vector has been sampled in a subspace according to the verifier’s coins. We show that this primitive provides a unifying view that explains the technical core of most of the constructions of universal and updatable pairing-based zkSNARKs.

4:00 PM (UTC)
Paper Discussion
Proposal: Rinocchio: SNARKs for Ring Arithmetic

Authors: Chaya Ganesh, Anca Nituescu and Eduardo Soria-Vazquez

Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields. For most constructions, the choice of the prime field F_p is limited by the existence of groups of matching order for which secure bilinear maps exist. In this work we overcome such restrictions and enable verifying computations over rings. We construct the first designated-verifier SNARK for statements which are represented as circuits over a broader kind of commutative rings, namely those containing big enough exceptional sets. Exceptional sets consist of elements such that their pairwise differences are invertible. Our contribution is threefold: We fist introduce Quadratic Ring Programs (QRPs) as a characterization of NP where the arithmetic is overa ring. Second, inspired by the framework in Gennaro, Gentry, Parno and Raykova (EUROCRYPT2013), we design SNARKs over rings in a modular way. We generalize pre-existent assumptions employed in field-restricted SNARKs to encoding schemes over rings. As our encoding notion is generic in the choice of the ring, it amenable to different settings. Finally, we propose two applications for our SNARKs. In the first one, we instantiate our construction for the Galois RingGR(2^k,d), i.e. the degree-d Galois extension of Z_{2^k}. This allows us to naturally prove statements about circuits over e.g. Z_{2^64}, which closely matches real-life computer architectures such as standard CPUs. Our second application is verifiable computation over encrypted data, specifically for evaluations of Ring-LWE-based homomorphic encryption schemes.

5:00 PM (UTC)
Break
Coffee & Short Networking

5:20 PM (UTC)
Invited Talks
SNARKs from the sum-check protocol
Justin Thaler

The sum-check protocol is an essential tool for designing highly scalable succinct arguments, especially without a trusted setup. This talk will explain the protocol and its use in SNARK design, unifying a large number of succinct arguments along the way.

5:40 PM (UTC)
Invited Talks
Proofs of proofs: incremental verifiability from recursion and accumulation
Nick Spooner
6:30 PM (UTC)
End of Day

Week 1: Thursday, April 22

3:00 PM (UTC)
Intro
Aleo, Horizen Labs & IOHK
3:15 PM (UTC)
Keynote
Distributed Zero-Knowledge Proofs and Applications to Secure Computation
Elette Boyle

Distributed zero-knowledge (D-ZK) proofs give a means for proving statements on data held distributedly across multiple parties. Concretely, there are multiple verifiers who each hold pieces of the input x, and zero knowledge must additionally guarantee that subsets of verifiers do not learn about x beyond their original knowledge. In this talk, we will introduce the notion of D-ZK proofs, briefly survey known constructions, and present recent developments using information-theoretic D-ZK machinery to achieve low-overhead compilers for attaining general secure computation with security against malicious adversaries. Based on joint works with Dan Boneh, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai, and Ariel Nof.

4:00 PM (UTC)
Panel Discussion
The Challenges and Best Practices of Deploying Zero-Knowledge Proofs
Pratyush Mishra (UC Berkeley), Jordi Baylina (Hermez Protocol), Zachary Williamson (Aztec Protocol), Daira Hopwood (Electric Coin Company), Izaak Meckler (O(1) Labs); Moderated by Georgios Konstantopoulos (Paradigm)

5:30 PM (UTC)
Co-Hosted Event
Zero-Knowledge Job Fair
A ZKProof and ZK Podcast Collaboration

This one-day social event is a satellite to the ZKProofs workshops and is the 3rd installment of the zkSessions online event series, hosted by Anna Rose from Zero Knowledge Podcast. If you are looking for talent and serious about hiring, then this should be a great opportunity to meet potential candidates and also to learn more from them about what they are looking for in an employer.

6:30 PM (UTC)
End of Day

Week 2: Monday, April 26

Session Chairs & Moderators: Anna Rose

3:00 PM (UTC)
Intro
Welcome to the Writathon & Tutorial Day
3:00 PM (UTC)
ZkpComRef
Latest Developments on the ZKProof Community Reference Document
Luis Brandao, Eran Tromer & Daniel Benarroch
3:25 PM (UTC)
ZK Tutorial
An Introduction to Zero-Knowledge Development
Pratyush Mishra

3:50 PM (UTC)
Breakout Rooms
Writathon & Tutorial Parallel Sessions #1

4:35 PM (UTC)
Break
Coffee & Short Networking

4:50 PM (UTC)
Invited Talks
High-speed zkSNARKs without trusted setup
Srinath Setty

A zkSNARK is a cryptographic primitive that enables a prover to prove to a verifier the knowledge of a satisfying witness to an NP statement by producing a proof such that: (1) the proof reveals no information beyond what is implied by the validity of the NP statement; and (2) the size of the proof and the cost to verify it are both sub-linear (ideally, at most polylogarithmic) in the size of the statement. Given these properties, zkSNARKs are a core building block for various forms of delegation of computation to untrusted platforms. Two key problems in this research area are: (1) achieving excellent asymptotic and concrete efficiency for the prover, verifier, and proof sizes; and (2) avoiding a trusted setup. This talk will describe our recent progress in constructing high-speed zkSNARKs without trusted setup. A core building block in our construction is an highly-efficient information-theoretic proof system for R1CS that achieves a linear-time prover, and logarithmic proof sizes and verification times in the polynomial IOP proof model. We then describe how to compile such an information-theoretic proof system into a zkSNARK using polynomial commitments (with extensions to efficiently handle sparse multilinear polynomials). We will also touch upon a polynomial commitment scheme with a linear-time prover, which when used with the aforementioned linear-time polynomial IOP leads to a linear-time SNARK for R1CS.

5:10 PM (UTC)
Breakout Rooms
Writathon & Tutorial Parallel Sessions #2

6:00 PM (UTC)
Breakout Rooms Debrief
ZkpComRef Contributions Presentations

6:30 PM (UTC)
End of Day

Week 2: Tuesday, April 27

Session Chairs & Moderators: Abhi Shelat

3:00 PM (UTC)
Invited Talks
Scalable Zero-Knowledge Protocols From Vector-OLE
Peter Scholl

In this talk, I will discuss a recent paradigm of using vector oblivious linear evaluation (VOLE) to construct efficient zero-knowledge protocols. The basic approach follows the commit-and-prove paradigm, using VOLE to obtain homomorphic commitments based on information-theoretic MACs. This allows supporting very large circuits with low computational resources, while having communication linear in the circuit size. I will then discuss some optimizations, including (1) an OR proof transformation for proving the disjunction of m statements with communication complexity proportional only to the longest statement, and (2) using the Fiat-Shamir transform to obtain non-interactive proofs to a designated verifier, with a constant memory overhead.

3:20 PM (UTC)
Invited Talks
Inner Product Arguments
Mary Maller

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(log n) 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.

3:40 PM (UTC)
Invited Talks
Emmanuela Orsini

In this talk we will describe recent advances on the concrete efficiency of MPC-in-the-Head based protocols. The ZK systems derived from this powerful framework share some interesting features such as transparency and public coin, so that they can be made non-interactive in the random oracle model using Fiat-Shamir. Furthermore, they do not require computational assumption and are plausibly post-quantum secure.

4:00 PM (UTC)
Break
Coffee & Short Networking

4:20 PM (UTC)
Paper Discussion
Proposal: Framework for Snarky Ceremonies

Authors: Markulf Kohlweiss, Mary Maller, Mikhail Volkhov and Janno Siim

Succinct non-interactive arguments of knowledge (SNARKs) have found wide-scale adoption in recent years. The most efficient SNARKs require a distributed ceremony protocol to generate public parameters, also known as a structured reference string (SRS). We propose a general security framework for non-interactive zero-knowledge (NIZK) arguments with a ceremony protocol. In particular, our framework generalizes the notion of updatable reference strings, proposed by Groth, Kohlweiss, Maller, Meiklejohn, and Miers[Crypto, 2018], to multiple independent update phases. Importantly, this allows us to also capture existing setup ceremonies as performed for Groth16 SNARKs.

5:20 PM (UTC)
Paper Discussion
SoK: Formal security analysis of MPC-in-the-head zero-knowledge protocols

Authors: Nikolaj Sidorenco, Sabine Oechsner and Bas Spitters

Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai etal.,STOC ’07) which use secure multiparty computation (MPC) protocols as basis. Efficient instances of this paradigm has emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al.,USENIX ’16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.

6:30 PM (UTC)
End of Day

Thursday, April 29

3:00 PM (UTC)
Intro
Algorand Foundation, Protocol Labs, QEDIT & Zcash Foundation
3:15 PM (UTC)
Intro
Proposal: Commit-and-Prove Zero-Knowledge Proof Systems and Extensions
Jiwon Lee

Authors: Daniel Benarroch, Matteo Campanelli, Dario Fiore, Jihye Kim, Jiwon Lee, Hyunok Oh and Anaïs Querol

Commit-and-Prove Zero-Knowledge Proof systems (CP-ZKPs) [Kil89, CLOS02] generalize zero-knowledge proofs where we prove statements about values that are committed. In this document we propose this notion and its variants. It can be useful as a lingua franca framework because: it emerges in a wide variety of practical applications; it may unify abstractions and simplify proofs in cryptographic technical reports; although the notion is defined as a special case of NIZKs, some of its efficient constructions are non-trivial. While previous editions of the ZKProof workshop have confirmed interest in the formalization in this document, there is still significant work ahead in terms of: refining the content of the proposal, and describing existing candidate constructions as well as general design approaches.

4:15 PM (UTC)
Keynote
Verification Dilemmas, Law, and the Promise of Zero-Knowledge Proofs
Shafi Goldwasser

Individuals expose personally identifying information to access a website or qualify for a loan, undermining privacy and security. Firms share proprietary information in dealmaking negotiations; if the deal fails, the negotiating partner may use that information to compete. Regulators that comply with public transparency and oversight requirements can risk subjecting algorithmic governance tools to gaming that destroys their efficacy. Litigants might have to reveal trade secrets in court proceedings to prove a claim or defense. Such “verification dilemmas,” or costly choices between opportunities that require the verification of some fact, and risks of exposing sensitive information in order to perform verification, appear across the legal landscape. Yet, existing legal responses to them are imperfect. Legal responses often depend on ex post litigation that are prohibitively expensive for those most in need, or that fail to address abuses of information entirely. Zero-knowledge proofs (ZKPs)—a class of cryptographic protocols that allow one party to verify a fact or characteristic of secret information without revealing the actual secret—can help solve these verification dilemmas. ZKPs have recently demonstrated their mettle, for example, by providing the privacy backbone for the blockchain. Yet they have received scant notice in the legal literature. This Article fills that gap by providing the first deep dive into ZKPs’ broad relevance for law. It explains ZKPs’ conceptual power and technical operation to a legal audience. It then demonstrates how, and that, ZKPs can be applied as a governance tool to transform verification dilemmas in multiple legal contexts. Finally, the Article surfaces, and provides a framework to address, the policy issues implicated by the potential substitution of ZKP governance tools in place of existing law and practice.

4:00 PM (UTC)
Break
Coffee Break

5:20 PM (UTC)
Paper Discussion
Proposal: Practical Groth16 Aggregation

Authors: Nicolas Gailly, Mary Maller and Anca Nitulescu

Groth16 arguments of knowledge have become a de-facto standard used in several blockchain projects due to the constant size of their proofs and their appealing verifier time. In this context, all nodes verify proofs posted on each block individually. Given an upper bound on the number of proofs allowed per blocks this solution doesn’t scale further. [BMM+19] presents a way to create an aggregate proof fromnGroth16 proofs with a O(log n) size and verifier time. However, the protocol requires a custom trusted setup, different than the Groth16 one. In this work, we modify the previous construction with a different commitment scheme that allows to aggregate existing Groth16 proofs by re-using existing powers of tau ceremonies transcript. Our protocol can aggregate1024 proofs in 2s and verifies them in 23ms, yielding an exponentially faster verification mechanism than batching.

6:20 PM (UTC)
Closing Ceremony
Closing Ceremony of the 4th ZKProof Workshop

6:30 PM (UTC)
End of Day

Accepted Papers

Proposal: Leo: A Programming Language for Formally Verified, Zero-Knowledge Applications – Collin Chin, Howard Wu, Raymond Chu, Alessandro Coglio, Eric McCarthy and Eric Smith

Proposal: Commit-and-Prove Zero-Knowledge Proof Systems and Extensions – Daniel Benarroch, Matteo Campanelli, Dario Fiore, Jihye Kim, Jiwon Lee, Hyunok Oh and Anaïs Querol

Proposal: $\Sigma$-protocols – Stephan Krenn and Michele Orrù

Proposal: Rinocchio: SNARKs for Ring Arithmetic – Chaya Ganesh, Anca Nituescu and Eduardo Soria-Vazquez

Proposal: Framework for Snarky Ceremonies – Markulf Kohlweiss, Mary Maller, Mikhail Volkhov and Janno Siim

Proposal: Practical Groth16 Aggregation – Nicolas Gailly, Mary Maller and Anca Nitulescu

SoK: Formal Security Analysis of MPC-in-the-Head Zero-Knowledge Protocols – Nikolaj Sidorenco, Sabine Oechsner and Bas Spitters

Call for Papers

The Call for Papers is now closed! Here you can find the accepted papers.