There are a lot of constructions of succinct non-interactive arguments of knowledge out there, even after filtering out those which are publicly verifiable and support proving unstructured languages such as Boolean or arithmetic circuit satisfiability (circuit-SAT) or rank-1 constraint satisfiability (R1CS). The table below is a quick, not necessarily accurate, summary of what is available at the moment.
Year | Scheme | Size | Trans | Preproc | Algebraic | PQ | Published | Reference | Note |
---|---|---|---|---|---|---|---|---|---|
2018 | Bulletproof (Group) | polylog | Yes | No | No | No | SP18 | link | |
2020 | Lakonia | polylog | Yes | No | No | No | – | link | |
2019 | Sonic | 1 | No | Yes | No | No | CCS19 | link | Universal updatable CRS |
2020 | Marlin | 1 | No | Yes | No | No | EC20 | link | Universal updatable CRS |
2020 | Spartan | sqrt | Yes | Yes | No | No | C20 | link | |
2020 | SuperSonic | polylog | Yes | Yes | No | No | EC20 | link | |
2020 | Kopis | polylog | Yes | Yes | No | No | – | link | |
2020 | Xiphos | polylog | Yes | Yes | No | No | – | link | |
2016 | Groth16 | 1 | No | Yes | Yes | No | EC16 | link | |
2018 | GKMMM18 | 1 | No | Yes | Yes | No | C18 | link | Universal updatable CRS |
2020 | Bulletproof (Lattice) | polylog | Yes | No | No | Yes | C20,C21 | BLNS20,AL21,ACK21 | |
2017 | Ligero | sqrt | Yes | No | No | Yes | CCS17 | link | |
2019 | Aurora | polylog | Yes | No | No | Yes | EC19 | link | |
2021 | Brakedown | sqrt | Yes | Yes | No | Yes | – | link | |
2021 | Shockwave | sqrt | Yes | Yes | No | Yes | – | link | |
2020 | Fractal | polylog | Yes | Yes | No | Yes | EC20 | link |
Size: Proof size as a function of statement size, fixed multiplicative factor polynomial in security parameter omitted
Trans: Transparent setup, i.e. lack of a trusted setup
Preproc: Verifier can preprocess the statement to make verification time sublinear in statement size
Algebraic: Only uses low-degree algebraic operations over the underlying group/ring/field, does not use random oracles or hash functions (which could be seen as high-degree operations)
PQ: Post-quantum in the most liberal sense, i.e. as long as it is not based on groups
Last Updated on 11/07/2022.