Paper 2022/1072

Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification

Alexandre Belling, Consensys R&D
Azam Soleimanian, Consensys R&D
Olivier Bégassat, Consensys R&D
Abstract

SNARK is a well-known family of cryptographic tools that is increasingly used in the field of computation integrity at scale. In this area, multiple works have introduced SNARK-friendly cryptographic primitives: hashing, but also encryption, and signature verification. Despite all the efforts to create cryptographic primitives that can be proved faster, it remains a major performance hole in practice. In this paper, we present a recursive technique that can improve the efficiency of the prover by an order of magnitude compared to proving MiMC hashes (a SNARK-friendly hash function, Albrecht et al. 2016) with a Groth16 (Eurocrypt 2016) proof. We use GKR (a well-known public-coin argument system by Goldwasser et al., STOC 2008) to prove the integrity of hash computations and embed the GKR verifier inside a SNARK circuit. The challenge comes from the fact that GKR is a public-coin interactive protocol, and applying Fiat-Shamir naively may result in worse performances than applying existing techniques directly. This is because Fiat-Shamir itself is involved with hash computation over a large string. We take advantage of a property that SNARK schemes commonly have, to build a protocol in which the Fiat-Shamir hashes have very short inputs. The technique we present is generic and can be applied over any SNARK-friendly hash, most known SNARK schemes, and any public-coin argument system in place of GKR.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
SNARK Hash Verification Proof Recursion Proof Composition GKR Public-Coin Fiat Shamir So-Far Digest Model
Contact author(s)
alexandre belling @ consensys net
azam soleimanian @ consensys net
olivier begassat @ consensys net
History
2022-11-30: revised
2022-08-18: received
See all versions
Short URL
https://ia.cr/2022/1072
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/1072,
      author = {Alexandre Belling and Azam Soleimanian and Olivier Bégassat},
      title = {Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1072},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1072}},
      url = {https://eprint.iacr.org/2022/1072}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.