4) Spartan applies polynomial commitments to achieve improvement in verication complexity. Computations are presented as R1CS and zero-knowledge is based on existing compilers such as Libra . However, no trusted setup is needed. Non-interactivity transform. is implemented using the Fiat-Shamir The prover complexity is O(|C| log |C|) while both the proof length and the verier complexity are O(log2 |C|). VIII. SCHEMES BASED ON LINEAR PCPs AND THE DISCRETE LOGARITHM PROBLEM Ishai et al. suggested the possibility of applying additively homomorphic public-key cryptography to reduce the communication complexity of interactive linear PCPs. Recent results for the complexity of fully linear PCPs can be found in . Groth et al. suggested the rst NIZK schemes based on the discrete logarithm problem and bilinear pairings that achieves perfect completeness, computational soundness and perfect zero-knowledge . Similarly to

14 15Hyrax reference implementation: 227953 the PCP technique, the general construction at rst expresses the statement as an algebraic constraint satisfaction problem. However, cryptographic commitments similar to the Pedersen commitment scheme are applied to achieve sub-linear proof length and non-interactivity without the Fiat-Shamir heuristic. However, a large CRS is required and the protocol depends on a strong cryptographic assumption known as the knowledge-of-exponent. With a sufciently long CRS, a constant proof length can be achieved ultimately consisting of only three underlying group elements , . Proving and verication are costly due to exponentiations. For additional application scenarios, a stronger security model called simulation-extractability has been suggested .

The following schemes are based on linear PCPs and/or the discrete logarithm problem. None of these are post-quantum secure. 1) Groths Linear SNARK. The seminal work of Groth achieves communication complexity that is proportional to the square root of the size of the circuit. 2) BCCGP. Bootle et al. implemented the rst non-interactive zero-knowledge proof protocol based on the discrete logarithm problem and using the techniques of Groth , .

3) Bulletproofs is based on the techniques of BCCGP . The protocol is designed to provide communication-efcient proofs especially for condential transactions through range proofs which can be efciently aggregated. However, any NP-problem is supported and the protocol does not require trusted setup. The protocol can be extended to achieve post-quantum security and non-interactivity is provided through the Fiat-Shamir heuristic. The length of the proof is logarithmic in the number of multiplication gates of the verication circuit. The prover and verier complexities are linear in the size of the witness w. Bulletproofs has a full implementation using arithmetic circuits.