**Workshop \#4 -- Home Edition**

# ZkpComRef: Concrete Schemes

Please start by reading the [**editorial disclaimer**](https://hackmd.io/@workshop4/zcr-disclaimer) to ensure proper expectations about the process.

**Goal:** Collect short descriptions of numerous concrete ZKP schemes (i.e., protocols), conveying their relation to a possible IT proof system type (PCP, Linear PCP, IOP, ...) (and sub-type), cryptographic compilers, and efficiency.

**Note on future integration:** The ZkpComRef will likely **not** incorporate all these descriptions. However, these descriptions will be tentatively useful when creating a table or diagram with many references to concrete schemes, differentiating them across various parameters (e.g., IT system type, efficiency type, ...).

**Existing material for comparison:**
- The "IT Proof Systems for ZKPs" mindmap below includes currently identified IT systems (there may be others).
- There is a draft document ([LaTeX](https://www.overleaf.com/read/tztmdfkdcqnq) in Overleaf ; and [PDF](https://drive.google.com/file/d/1oxxusr6s0qY86tra-f1Uc6IxPNxkykqW/view?usp=sharing) as of 2021-Apr-26 9:20am EDT) collecting descriptions of IT proof systems (Sec 2), crypto compilers (Sec. 3) and concrete schemes (Sec. 4). Note in particular that Section 2.4 already contains descriptions of a few concrete schemes. You can also [propose](https://www.overleaf.com/1853184269rsmvpdxxbwfn) edits to those.

:::success
**Email confirmation:** Once finishing your contributions, please send a brief email to [e-mail] to confirm what you added.
:::

## Template (content per description)

For each concrete scheme, in at most one paragraph describe the following:
- Title of the ZKP scheme
- Year and reference (doi, eprint, arxiv, ...)
- Relatable IT proof system (from the Paradigms draft or the image below):
- Cryptographic compiler (instantiations when going from an IT system to a real scheme)
- Efficiency at a high level: prover, verifier, communication, computation, ...
- Security (assumptions, model, setup), especially if it deviate from what's already implied by the "family" of IT/compilers used
- Notes of comparison to other concrete schemes (previous and subsequent)

---

## Concrete scheme 1: Groth16
> [name=Anca Nitulescu ([e-mail])]
\<
[Groth16](https://https://eprint.iacr.org/2016/260.pdf)
\>

Relatable IT proof system. This is a SNARKs for arithmetic circuits from Quadratic Arithmetic Programs (QAP). The cryptographic compiler uses bilinear groups an is proven secure under idealized assumptions on these.

This scheme is very succinct: the proof size is very small (only three group elements, close to the lower bound), and the verifier is very fast (regardless of constraint system size). The prover runtime is quasilinear in the constraint system size, and the SRS size is linear.

Efficiency wise, Groth16 works over asymmetrical bilinear groups $(p, G_1, G_2, G_T, e)$.
The proof size is 2 elements in $G_1$ and 1 element in $G_2$. For a statement of size $\ell$,
and a circuit of $m$ wires and $n$ multiplication gates, the common reference string contains a description of the relation,
$n$ elements in $Z_p$, $m + 2n + 3$ elements in $G_1$, and $n + 3$ elements in $G_2$.

The verification checks that the proof consists of three appropriate
group elements and checking a single pairing product equation. The verifier computes $\ell$ exponentiations in $G_1$, a small number of group multiplications, and 3 pairings.

Security of Groth16 holds in the Generic Group Model (GGM). Later, it was shown that security also holds in the algebraic group model AGM.
The GGM is an idealised cryptographic model, where algorithms do not exploit any special structure of the representation of the group elements and can
thus be applied in any cyclic group.

Q: what can be said more about the security?
Q: mention of succinctness?

---

## Concrete scheme 2: Marlin
> [name=Mary Maller ([e-mail])]
\<
[Marlin](https://eprint.iacr.org/2019/1047.pdf)
> \>

The IT is an "algebraic holographic proof" which is a specific type of IOP in which the verifier can query for linear combinations of the polynomials. It is compiled polynomial commitments.

Efficiency wise (assuming it is compiled with the KZG polynomial commitment scheme) the verifier is fast, the proof size is medium, the prover is medium, the SRS size is medium, the specialised SRS is small, the specialisation time is medium.

Security is either in the algebraic group model for best efficiency or under the q-PKE assumption. It also relies on the non-programmable random oracle model to be non-interactive. Setup is universal.

Marlin is very similar to Plonk however the constraints are based on R1CS whereas Plonk is based on a "selector polynomial" arithmetisation. Marlin is good for applications that require fast verifiers but cannot tolerate a fully trusted setup.

---
## Concrete scheme 3: Plonk
> [name=Mary Maller ([e-mail])]
\<
[Plonk](https://eprint.iacr.org/2019/953.pdf)
> \>

The IT is an "algebraic holographic proof" which is a specific type of IOP in which the verifier can query for linear combinations of the polynomials. It is compiled polynomial commitments.

Efficiency wise (assuming it is compiled with the KZG polynomial commitment scheme) the verifier is fast, the proof size is medium, the prover is medium, the SRS size is medium, the specialised SRS is small, the specialisation time is medium.

Security is either in the algebraic group model for best efficiency or under the q-PKE assumption. It also relies on the non-programmable random oracle model to be non-interactive. Setup is universal.

Plonk is very similar to Marlin; however the constraints are based on a "selector polynomial" arithmetisation whereas Marlin is based on R1CS.

The width is considered to be the number of wires available. fan-in 2 with a fan-out of 1, indicates that the width is 3.

**Regular PLONK**

This uses a width of 3 and it also encodes an arithmetic polynomial identity which allows you to prove multiplications and additions.

This arithmetic polynomial identity is added in what is known as the quotient polynomial.

This is the version that is shown in eprint and the most simplest.

**TurboPLONK**

This uses a width of 4. Moreover, the quotient polynomial is extended to also add in custom polynomial identities.

**UltraPLONK**

This also uses a width of 4. However, all of the custom polynomial identities are removed, and we use Plookup based polynomial identities.

In all variations of PLONK, the quotient polynomial is concretely degree bounded which means that you cannot arbitrarily add any polynomial identity. In theory it does not need to be.

> Extensions of constraint system:[TurboPlonk](https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf), [Plookup](https://eprint.iacr.org/2020/315.pdf).
> Extensions to other commitment schemes: [SuperSonic](https://eprint.iacr.org/2019/1229)
---
## Concrete scheme 4: Sonic
> [name=Mary Maller ([e-mail])]
\<[Sonic](https://eprint.iacr.org/2019/099.pdf)

The IT is an "algebraic holographic proof" which is a specific type of IOP in which the verifier can query for linear combinations of the polynomials. It is compiled polynomial commitments.

Efficiency wise there are two settings: where you can aggregate the proofs and where you cannot. The first case is fast, the second is a proof of concept (it was the first asymptotically efficient SNARK). In the first case the verifier is fast, the proof size is small, the prover is medium, the SRS size is medium, and there is no specialisation.

Security is in the algebraic group model. Setup is universal.

Sonic has slow prover time compared to Marlin or Plonk assuming there is means of aggregation. If you can aggregate then Sonic is faster. It would be good for an application where there exists an aggregator (e.g. blockchain miners).

\>

---
## Concrete scheme 5: Groth-Sahai Proofs
> [name=Carla Ràfols ([e-mail])]
\<
[Groth-Sahai proofs](https://eprint.iacr.org/2007/155)
> \>

The Groth-Sahai proof system allows to prove group dependent statements in bilinear groups. It can be used to prove any quadratic equation defined over a large finite field, or statements about multiexponentiations or pairing product equations. It can be formulated as a type-based commit-and-prove scheme (see [Escala and Groth 14](https://eprint.iacr.org/2013) The size of the commitment grows linearly with the number of variables and the proof size with the number of equations. One of the most interesting use cases for this proof system is structure-preserving cryptography.
The proof system can be instantiated under different (weak) assumptions in bilinear groups. The most efficient construction is based on the Decisional Diffie-Hellman assumption in both source groups.

> Stress that unlike most other schemes here, these are not general-purpose ZKPs for any statement. Once we have several such, group them in a dedicated subsection. See also Stern93 above. [name=Eran Tromer]

---
## Concrete scheme 6: Spartan
> [name=Mary Maller ([e-mail])]
\<
[Spartan](https://eprint.iacr.org/2019/550.pdf)
> \>

The IT is a polynomial IOP, compiled using polynomial commitments.

Efficiency wise (assuming it is compiled with the Bulletproofs polynomial commitment scheme) the verifier is medium, the proof size is medium, the prover is fast, the specialisation time is medium.

Security is under the discrete logarithm assumption in the interactive model. It can be compiled into a non-interactive proof in the algebraic group model with random oracles. Setup is public coin.

Spartan can cover any R1CS system whereas Hyrax can only cover constraint systems with special structure. Spartan is ideal for applications that require a faster prover and that can tolerate a moderate proof size and verifier time.

> extensions ([Cerberus](https://eprint.iacr.org/2021/030))

---
## Concrete scheme 7: Bulletproofs/Compressed Sigma Protocols
> [name=Jonathan Bootle ([e-mail])]
\<
[BCCGP16](https://eprint.iacr.org/2016/263)
[Bulletproofs](https://eprint.iacr.org/2017/1066)
[Compressed Sigma Protocols](https://eprint.iacr.org/2020/152)
> \>

Interactive arguments in the discrete-logarithm setting, where commitments are interactively "folded" to give commitments to shorter messages.

IT is a Linear IOP, where you have a secret committed vector and can query for linear combinations of the entries. Technically, the first two references here are for scalar-product arguments, between two secret vectors, but one of them can be made public (as in the third reference, which implicitly specifies a linear IOPs through "linear form evaluation").

Security of the interactive protocols is under the discrete-logarithm assumption. They can be made non-interactive using random oracles. The setup is public coin. These arguments generalise extensively to other cryptographic assumptions.

These proof systems can cover general languages like arithmetic circuits and R1CS.

Short proofs, but slow due to a linear number of group operations for prover and verifier. Can be implemented with [a quasilinear prover with limited memory space](https://eprint.iacr.org/2021/358).

---
## Concrete scheme 8: Post-Quantum SNARK from SSP
> [name=Anca Nitulescu ([e-mail])]
\<[Lattice-Based SNARK for SSP](https://eprint.iacr.org/2018/275.pdf)\>

These frameworks for post-quantum SNARKs with preprocessing (circuit-dependent setup) lead to **designated-verifier** schemes.

Relatable IT proof system. This is a SNARKs for arithmetic circuits from Square Span Programs (SSP).

Cryptographic Compiler.
Linear-only extractable encodings which can be realized from IND-CPA encryption schemes that are additively homomorphic.

Efficiency.
The lattice-based SNARK has proof size of 5 encodings, which can be instantiated with any linearly-homomorphic LWE encryption scheme that supports message spaces $Z_p$ for a prime $p$.
The verifier needs to decrypt these 5 ciphertexts and perform a small number of multiplications on plaintexts.

---
## ## Concrete scheme 9: Halo
> [name=Ariel Gabizon ([e-mail])]
[Halo](https://eprint.iacr.org/2019/1021) presented a new recursive aggregation method based on the bullet proofs commitment scheme. It was combined with the Sonic polynomial IOP to create a proof system with no trusted setup supporting unbounded recursion.

*Halo 2:* Halo 2 is a variation of the original construction of using the PLONK arithmetization.

> Discuss

---
## Concrete scheme 10: Stern's Protocol
> [name=Jonathan Bootle ([e-mail])]

[Stern93](https://link.springer.com/content/pdf/10.1007/3-540-48329-2_2.pdf)

A protocol for proving that you know a pre-image of a simple code-based (or lattice-based) hash function.

The protocol is a "cut-and-choose" protocol which could be seen as a PCP (like the graph three-colouring protocol).

Can be compiled using any commitment scheme. If a post-quantum commitment scheme is used, then leads to a post-quantum protocol (as the underlying languages are quantum-secure).

The basic protocol handles preimages, but subsequent works have used the same ideas to capture more complicated languages (see works of Benoit Libert, Khoa Nguyen, etc for group signatures, voting, etc).

Very fast, but have large proofs. Constant soundness error, so the protocols must be repeated many times.

> Stress that unlike most other schemes here, these are not general-purpose ZKPs for any statement. Once we have several such, group them in a dedicated subsection. See also Groth-Sahai above. [name=Eran Tromer]

> Schemes based on Stern-type protocols: Group sigs [[LLMNW16](https://eprint.iacr.org/2016/101.pdf)], Commitments (and arbitrary circuits on committed values) [[JKPT12](https://eprint.iacr.org/2012/513.pdf)], Identification schemes [[Ver97](https://link.springer.com/article/10.1007%2Fs002000050053)], Verifiable encryption [[LNSW12](https://eprint.iacr.org/2012/569.pdf)], ...
> Maybe mention that for syndrome decoding/LPN the computations are mainly XOR-ing of bit-vectors? Maybe also mention that even though they look quite different from Schnorr proofs, Stern-type proofs are still $\Sigma$-protocols? [name=Stephan Krenn]

---
## Concrete scheme 11
> [name=Edited by name here (email here)]
\<Description here\>

---
## Concrete scheme 12
> [name=Edited by name here (email here)]
\<Description here\>