or
or
By clicking below, you agree to our terms of service.
Sign in with Wallet
New to HackMD? Sign up
| Syntax | Example | Reference | |
|---|---|---|---|
| # Header | Header | 基本排版 | |
| - Unordered List |
|
||
| 1. Ordered List |
|
||
| - [ ] Todo List |
|
||
| > Blockquote | Blockquote |
||
| **Bold font** | Bold font | ||
| *Italics font* | Italics font | ||
| ~~Strikethrough~~ | |||
| 19^th^ | 19th | ||
| H~2~O | H2O | ||
| ++Inserted text++ | Inserted text | ||
| ==Marked text== | Marked text | ||
| [link text](https:// "title") | Link | ||
|  | Image | ||
| `Code` | Code |
在筆記中貼入程式碼 | |
| ```javascript var i = 0; ``` |
|
||
| :smile: |  |
Emoji list | |
| {%youtube youtube_id %} | Externals | ||
| $L^aT_eX$ | LaTeX | ||
| :::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →ZkpComRef: Concrete Schemes
Please start by reading the editorial 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:
Email confirmation: Once finishing your contributions, please send a brief email to editors@zkproof.org to confirm what you added.
Template (content per description)
For each concrete scheme, in at most one paragraph describe the following:
Concrete scheme 1: Groth16
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
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
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.
Concrete scheme 4: Sonic
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
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 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.
Concrete scheme 6: Spartan
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.
Concrete scheme 7: Bulletproofs/Compressed Sigma Protocols
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.
Concrete scheme 8: Post-Quantum SNARK from SSP
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
Halo 2: Halo 2 is a variation of the original construction of using the PLONK arithmetization.
Concrete scheme 10: Stern's Protocol
Stern93
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.
Concrete scheme 11
Concrete scheme 12