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

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.

Available format(s)
Cryptographic protocols
Publication info
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
2022-11-30: revised
2022-08-18: received
See all versions
Short URL
No rights reserved


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.