Seascape of SNARKs

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.

YearSchemeSizeTransPreprocAlgebraicPQPublishedReferenceNote
2018Bulletproof (Group)polylogYesNoNoNoSP18link
2020LakoniapolylogYesNoNoNolink
2019Sonic1NoYesNoNoCCS19linkUniversal updatable CRS
2020Marlin1NoYesNoNoEC20linkUniversal updatable CRS
2020SpartansqrtYesYesNoNoC20link
2020SuperSonicpolylogYesYesNoNoEC20link
2020KopispolylogYesYesNoNolink
2020XiphospolylogYesYesNoNolink
2016Groth161NoYesYesNoEC16link
2018GKMMM181NoYesYesNoC18linkUniversal updatable CRS
2020Bulletproof (Lattice)polylogYesNoNoYesC20,C21BLNS20,AL21,ACK21
2017LigerosqrtYesNoNoYesCCS17link
2019AurorapolylogYesNoNoYesEC19link
2021BrakedownsqrtYesYesNoYeslink
2021ShockwavesqrtYesYesNoYeslink
2020FractalpolylogYesYesNoYesEC20link
Comparison of publicly-verifiable SNARKs for unstructured languages (e.g. circuit-SAT, R1CS)

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 13/03/2022.

Leave a Reply

Your email address will not be published. Required fields are marked *