Link

This site uses Just the Docs, a documentation theme for Jekyll.

Search

ZKProof Wiki of Concrete ZKP Schemes

This wiki (ongoing work) is a resource complementary to the ZKProof Community Reference. The goal is to collect in one place many references about concrete ZKP schemes. For each scheme there is a summarized description and various references to available public resources.

Schemes described here should have a rigorous technical writeup which fully specifies the scheme; clearly states its security properties, model and assumptions; and proves its security (at least at the proof-sketch level).

The following is not an exhaustive list. It contains references listed in a previous version of the ZkpComRef, as well as others suggested during edits. Clearly there are more relevant entries to add — please send an email to [email protected] with your suggestions. Better yet, submit a pull request to the resources GitHub repo or submit a description at https://forms.gle/NGm9xpUJBDyy6UFr6, following the instructions further below.

Index

Described:

The descriptions are based on contributions obtained via https://forms.gle/NGm9xpUJBDyy6UFr6

To be described:

The following schemes are yet to be described in the template format provided below.

How to submit a description:

Described Schemes:

2021

TurboIKOS

  • Available resources: paper@IACR; code@GitHub;
  • Where presented: ACNS 2021 (June)
  • Kind of statements: General arithmetic circuits in low RAM settings, especially small circuits
  • Information theoretic (IT) system: MPC-in-the-Head
  • Cryptographic compiler: IKOS compiler from (semi-honest) MPC protocol to ZKP
  • Complexity/efficiency: Prover runtime: linear. Verifier runtime: linear. Communication: linear (2 field elements per mult gate per repetition achieving soundness in Theorem 3, plus log(parties) overhead). Round complexity: constant (5 rounds)
  • Models and assumptions: One-way functions. Smaller weak commitments use ROM (can be removed). Non-interactivity achieved via Fiat-Shamir.
  • Relation to other schemes: Focus is on concrete communication/proof size improvement within the setting of asymptotically linear MPC-in-the-head proofs. Shrinks Baum and Nof’s PKC 2020 scheme from 4 field elems per gate to 2 field elems per gate. Our scheme has competitive communication/size with Katz, Kolesnikov, and Wang’s CCS 2018 scheme with a different parameter tradeoff; our scheme is better for fewer emulated MPC parties (which would occur if lower runtime is desired compared to proof size).

BibTex citation

@inproceedings{ACNS:GHSVYZ21,
    title={TurboIKOS: Improved Non-Interactive Zero Knowledge and Post-Quantum Signatures},
    author={Yaron Gvili and Julie Ha and Sarah Scheffler and Mayank Varia and Ziling Yang and Xinyuan Zhang},
    editor = {Kazue Sako and Nils Ole Tippenhauer},
    booktitle = {Applied Cryptography and Network Security},
    volume = {12727},
    address = {Kamakura, Japan},
    month = {June},
    publisher = "Springer, Heidelberg",
    series = "Lecture Notes in Computer Science",
    year = 2021
}

BooLigero

  • Available resources: paper@IACR; No GitHub Code
  • Where presented: FC 2021 (March)
  • Kind of statements: Boolean circuits over “words”, especially those containing many (possibly different) subcircuits of linear operations that yield 0 over bits (such as bit masking, even parity testing, permutations of bits within or across words, or similar operations)
  • Information theoretic (IT) system: MPC-in-the-Head, Interactive Oracle Proofs (IOP)
  • Cryptographic compiler: BCS’16 (IOP), AHIV’17 (Ligero)
  • Complexity/efficiency: Prover runtime: $S \cdot log(S)$ where $S$ is circuit size. Verifier runtime: S*log(S) where S is circuit size. Communication: $\sqrt{S}$ where $S$ is circuit size. Round complexity: constant
  • Models and assumptions: Coding theoretic assumption (same as Ligero: AHIV’17 Lemma 4.2). Non-interactivity comes from Fiat-Shamir.
  • Relation to other schemes: Improves Boolean circuit proof size over original Ligero (Ames, Hazay, Ishai , Venkitasubramaniam CCS’17) by $\sqrt{log(|F|)}$ where $F$ is the field; $F$ has a minimum size for Ligero to function. In practice this tends to be about a 1-4x proof size reduction. Further improves upon Ligero by using highly batchable testing for Boolean relations such as a bit masking, even parity, permutations of bits, etc.

BibTex citation

@inproceedings{FC:GviSchVar21,
    title={BooLigero: Improved Sublinear Zero Knowledge Proofs for Boolean Circuits},
    author={Gvili, Yaron and Scheffler, Sarah and Varia, Mayank},
    booktitle = {Financial Cryptography and Data Security},
    month = {March},
    publisher = "Springer, Heidelberg",
    series = "Lecture Notes in Computer Science",
    year = 2021
}

2020

Marlin

  • Resources: paper@IACR; paper@Springer; code@GitHub; implementation diagram; video@Youtube.
  • Where presented: EUROCRYPT 2020
  • Kind of statements: General arithmetic circuits/R1CS
  • Information theoretic (IT) system: Interactive Oracle Proofs (IOP), Polynomial IOP
  • Cryptographic compiler: Polynomial commitment schemes
  • Complexity/efficiency: Efficiency depends on the maximum number of non-zero entries N across the matrices. When used with Marlin variant of KZG10, over BLS12-381: Proof size: 784 bytes. PK size: $3N$. VK size: 12 G1 + 2 G2. Verification time: < 8ms. Proving time: $O(N)$-sized MSMs over G1
  • Models and assumptions: ROM + AGM
  • Relation to other schemes: Alternative to Groth16 that provides universal setup. Alternative to standard that works with R1CS directly

BibTex citation

@inproceedings{ChiesaHMMVW20,
    author = {Chiesa, Alessandro and Hu, Yuncong and Maller, Mary and Mishra, Pratyush and Vesely, Noah and Ward, Nicholas},
title = {Marlin: Preprocessing {zkSNARKs} with Universal and Updatable {SRS}},
    booktitle = {Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques},
    series = {EUROCRYPT~'20},
    pages = {738--768},
    year = {2020},
}

Virgo

  • Available resources: paper@IACR; code@GitHub
  • Where presented: IEEE S&P 2020
  • Kind of statements: Layered arithmetic circuits
  • Information theoretic (IT) system: Interactive Oracle Proofs (IOP). Combines the IP in GKR with a polynomial commitment based on IOP
  • Cryptographic compiler: Polynomial commitments
  • Complexity/efficiency: Prover $O(C+n\log n)$; verifier $O(d\log C+\log^2 n)$; proof size $O(d \log C+\log^2 n)$; transparent setup with $O(1)$ RRS; non-interactive through Fiat-Shamir
  • Models and assumptions: Collision-resistant hash and ROM, Fiat-Shamir to remove interactivity
  • Relation to other schemes: It proposes a new polynomial commitment in IOP that removes the trusted setup.

BibTex citation

@inproceedings{zhang2020transparent,
    title={Transparent polynomial delegation and its applications to zero knowledge proof},
    author={Zhang, Jiaheng and Xie, Tiancheng and Zhang, Yupeng and Song, Dawn},
    booktitle={2020 IEEE Symposium on Security and Privacy (SP)},
    pages={859--876},
    year={2020},
    organization={IEEE}
}

Virgo++

  • Available resources: paper@IACR; code@GitHub
  • Where presented:
  • Kind of statements: General arithmetic circuits
  • Information theoretic (IT) system: Interactive Oracle Proofs (IOP). develops a new IP for general arithmetic circuits
  • Cryptographic compiler: Polynomial commitments
  • Complexity/efficiency: Prover $O(C+n\log n)$; verifier $O(d\log C+d^2+\log^n)$; proof size $O(d\log C+d^2+\log^n)$; transparent setup with $O(1)$ RRS; non-interactive through Fiat-Shamir
  • Models and assumptions: collision-resistant hash and ROM, Fiat-Shamir
  • Relation to other schemes: It generalizes the GKR protocol to general arithmetic circuits while keeping the prover time $O(C)$.

BibTex citation

@inproceedings{zhang2021doubly,
    author = {Jiaheng Zhang and Tianyi Liu and Weijie Wang and Yinuo Zhang and Dawn Song and Xiang Xie and Yupeng Zhang},
    title = {Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time},
    booktitle = {Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS)},
    year = {2021},
}

Ligero++

  • Available resources: paper@CCS2020
  • Where presented: CCS 2020
  • Kind of statements: R1CS
  • Information theoretic (IT) system: Interactive Oracle Proofs (IOP)
  • Cryptographic compiler: IOP. FRI
  • Complexity/efficiency: Prover $O(C\log C)$; verifier $O(\log^2 C)$; proof size $O(\log^2 C)$; transparent setup with $O(1)$ RRS; non-interactive through Fiat-Shamir.
  • Models and assumptions: collision resistant hash and ROM, Fiat-Shamir
  • Relation to other schemes: It improves the proof size of Ligero to $O(\log^C)$ using the IOP of Aurora and Virgo

BibTex citation

@inproceedings{bhadauria2020ligero++,
    title={Ligero++: a new optimized sublinear IOP},
    author={Bhadauria, Rishabh and Fang, Zhiyong and Hazay, Carmit and Venkitasubramaniam, Muthuramakrishnan and Xie, Tiancheng and Zhang, Yupeng},
    booktitle={Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security},
    pages={2025--2038},
    year={2020}
}

Mac’n’Cheese

  • Available resources: paper@IACR
  • Where presented:
  • Kind of statements: Circuits with disjunctions, General circuits
  • Information theoretic (IT) system: Linear PCP, Ideal Linear Commitment (ILC), IPs with Linear Oracle Verification. It uses basic homomorphic MACs (similar to ILCs) to commit to the witness and then verifies the witness using Linear IOP/ILC techniques
  • Cryptographic compiler: vOLEs to implement homomorphic MACs, inner product argument to verify product relations
  • Complexity/efficiency: Prover and verifier time as well as memory are linear in statement size. The online proof size is $1+\varepsilon$ field elements per multiplication for arbitrary circuits and decreases to $O(max(|C_i|) + log(m))$ for a disjunction over $m$ circuits $C_i$. The computation/communication cost for the preprocessing is linear as well, but communication is much lower: per vOLE in $\mathbb{F}_{2^{61}-1}$ the communication is $0.42$ bits using e.g. Wolverine.
  • Models and assumptions: LPN assumption to instantiate the vOLE, ROM (Fiat-Shamir) to reduce round complexity
  • Relation to other schemes: The protocol is related to the Wolverine protocol, although Mac’n’Cheese has a lower communication complexity. It has a comparable, although slightly worse, communication complexity than Quicksilver, and a comparable runtime to it. In comparison to Wolverine & Quicksilver, Mac’n’Cheese has a low communication overhead for disjunctions for which it is optimized.

BibTex citation

@inproceedings{C:BMRS21,
    author = {Carsten Baum and
              Alex J. Malozemoff and
              Marc B. Rosen and
              Peter Scholl},
    title = {Mac'n'Cheese: Zero-Knowledge Proofs for Boolean and Arithmetic Circuits with Nested Disjunctions},
  booktitle={Annual International Cryptology Conference},
  year={2021},
  organization={Springer}
}

2019

Sonic

  • Available resources: paper@CCS’19; paper@IACR; code@GitHub
  • Where presented: CCS’19
  • Kind of statements: General purpose circuits. Best when the same circuit (for different statements) is proven multiple times and there exists a “helper” to aggregate.
  • Information theoretic (IT) system: Polynomial IOP. Algebraic holographic proof. A polynomial IOP where the verifier can query on linear combinations of the polynomial oracles.
  • Cryptographic compiler: Polynomial commitments. Bilinear pairings.
  • Complexity/efficiency: Prover time = $O(n\log(n))$, prover memory $(n\log(n))$, proof size = $O(1)$, verifier time and memory = $O(1)$ aggregated or $O(n)$ non-aggregated, “post”-processing, non-interactive under Fiat-Shamir, aggregating time = $O(n)$.
  • Models and assumptions: ROM and (bilinear) algebraic group model.
  • Relation to other schemes: Preceeds Plonk and Marlin which are efficient with preprocessing
  • Other comments: Aggregator improves verifier time rather than proof size.

BibTex citation

@inproceedings{MallerBKM19,
  author    = {Mary Maller and
               Sean Bowe and
               Markulf Kohlweiss and
               Sarah Meiklejohn},
  title     = {Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable
               Structured Reference Strings},
  booktitle = {Proceedings of the 2019 {ACM} {SIGSAC} Conference on Computer and
               Communications Security, {CCS} 2019, London, UK, November 11-15, 2019},
  pages     = {2111--2128},
  year      = {2019},
}

Libra

  • Available resources: paper@IACR; code@GitHub
  • Where presented: Crypto 2019
  • Kind of statements: Layered arithmetic circuits
  • Information theoretic (IT) system: Linear IOP. It combines the IP of GKR with a polynomial commitment.
  • Cryptographic compiler: polynomial commitments
  • Complexity/efficiency: Prover $O(C)$; verifier $O(d\log C)$; proof size $O(d\log C)$; trusted setup with SRS of $O(C)$; non-interactive through Fiat-Shamir.
  • Models and assumptions: Extractability & KoE, ROM to remove interactivity
  • Relation to other schemes: Improves the prover time of the GKR protocol to linear in circuit size for any layered arithmetic circuit.

BibTex citation

@inproceedings{xie2019libra,
  title={Libra: Succinct zero-knowledge proofs with optimal prover computation},
  author={Xie, Tiacheng and Zhang, Jiaheng and Zhang, Yupeng and Papamanthou, Charalampos and Song, Dawn},
  booktitle={Annual International Cryptology Conference},
  pages={733--764},
  year={2019},
  organization={Springer}
}

kimleeoh

  • Available resources: paper@IEEE; paper@IACR
  • Where presented: IEEE Access Vol. 8
  • Kind of statements: quadratic arithmetic circuit
  • Information theoretic (IT) system: Linear PCP. is constructed from the quadratic arithmetic program (QAP), same as in Groth16.
  • Cryptographic compiler: Bi-linear pairings, same as in Groth16.
  • Complexity/efficiency: It is a Groth16 variant, which adds simulation extractability. The verification time and the proof size is equivalent to Groth16, and the proving time is similar to Groth16 (same complexity).
  • Models and assumptions: ROM, algebraic model, KoE
  • Relation to other schemes: It adds simulation-extractability to Groth16, without sacrificing the proof size and other general computations, by using the hash function.

BibTex citation

@article{kim2020simulation,
  title={Simulation-extractable zk-SNARK with a single verification},
  author={Kim, Jihye and Lee, Jiwon and Oh, Hyunok},
  journal={IEEE Access},
  volume={8},
  pages={156569--156581},
  year={2020},
  publisher={IEEE}
}

SAVER

  • Available resources: paper@IACR
  • Where presented: ???
  • Kind of statements: Quadratic arithmetic circuit
  • Information theoretic (IT) system: Linear PCP. It is constructed from quadratic arithmetic circuit.
  • Cryptographic compiler: Bi-linear pairings
  • Complexity/efficiency: It improves the efficiency of proving (public-key) encryption, compared with using existing ZKP schemes. It achieves the proving time of less than 1ms, while Groth16 requires 9s for proving RSA-OAEP-2048.
  • Models and assumptions: Algebraic model, KoE
  • Relation to other schemes: It takes the idea of commit-and-prove and extends it to encrypt-and-prove to improve the efficiency of encryption.

BibTex citation

@article{lee2019saver,
  title={SAVER: Snark-friendly, Additively-homomorphic, and Verifiable Encryption and decryption with Rerandomization.},
  author={Lee, Jiwon and Choi, Jaekyoung and Kim, Jihye and Oh, Hyunok},
  journal={IACR Cryptol. ePrint Arch.},
  volume={2019},
  pages={1270},
  year={2019}
}

2018

To be described.

2017

vSQL

  • Available resources: paper@IACR; paper@IACR; slides
  • Where presented: University presentation 2017
  • Kind of statements: Layered arithmetic circuits
  • Information theoretic (IT) system: Linear IOP. It proposes the first framework to lift the IP protocol of GKR to a (zero-knowledge) argument through a polynomial commitment.
  • Cryptographic compiler: Polynomial commitments
  • Complexity/efficiency: Prover $O(C \log C)$; verifier $O(d \log C)$; proof size $O(d \log C)$; trusted setup with SRS of $O(C)$; non-interactive through Fiat-Shamir
  • Models and assumptions: KoE and ROM
  • Relation to other schemes: It is the first to combine the GKR protocol with a polynomial commitment.

BibTex citation

@inproceedings{zhang2017vsql,
    title={vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases},
    author={Zhang, Yupeng and Genkin, Daniel and Katz, Jonathan and Papadopoulos, Dimitrios and Papamanthou, Charalampos},
    booktitle={2017 IEEE Symposium on Security and Privacy (SP)},
    pages={863--880},
    year={2017},
    organization={IEEE}
}

Template description

We’d like each concrete scheme to provide succinct information about the following aspects:

  • Available resources:
  • Where presented:
  • Kind of statements:
  • Information theoretic (IT) system:
  • Cryptographic compiler:
  • Complexity/efficiency:
  • Models and assumptions:
  • Relation to other schemes: [Follows which previous schemes? Has it been superseded?]

BibTex citation

insert bibtex entry

Please submit this information via the form: https://forms.gle/NGm9xpUJBDyy6UFr6 or submit a pull request to the resources GitHub repo.

The editors may make some editorial adjustments to the submitted content, to promote consistency. For comments , please send an email to [email protected].