[Resource Topic] 2022/1072: Recursion over Public-Coin Interactive Proof Systems; Faster Hash Verification

Resource Cryptographic protocols
#1

Welcome to the resource topic for 2022/1072

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

Authors: Alexandre Belling, Azam Soleimanian, Olivier Bégassat

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 - which are used in many applications. 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 for the Fiat-Shamir hashes have very short inputs. The technique we present is generic and can be applied to over most known SNARK scheme and any public-coin argument system in place of GKR. It outputs an augmented proof system combining the performances of the two.

ePrint: https://eprint.iacr.org/2022/1072

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .

#2

Funnily enough, I recently wrote a quick note about a similar idea: https://cronokirby.com/notes/2022/08/on-verifying-public-coin-protocols-inside-zk-proofs/

6 Likes
#3

Thanks for pointing this out,

To give you some context, this papers follows from a list of post we made on ethresearch attempting to speed-up the verification of hash functions within a circuit. The techniques have evolved quite a bit since we started working on it (following security issues we had in the earlier versions) end we ended up making them more generic as well.

From my understanding, both our idea tackles the same problem with the same philosophy. In a nutshell, avoiding doing FS inside a circuit, instead doing it outside and putting the FS back challenges in the circuit (as public inputs).

However, I think it is worth mentioning that the two approaches have some important differences as well, or at least from my understanding. Your proposal suggests verifying the commitment within the circuit, and ours suggests using a specific proof system for that (aside from the SNARK used to generate a proof for the circuit). I think the differences matter when taking the prover time into consideration.

I would also have one question regarding your idea. How do you check the decommitment inside the circuit? It seems to me that in order for the technique to be efficient, you would need a commitment scheme for which the decommitment is more efficient than hashing the secret. But I don’t know any commitment scheme having this property. Is it to avoid assuming the security of a SNARK-friendly hash function?

2 Likes
#4

Well, my idea was written very hastily and isn’t well polished, so some of the parts aren’t very clear. If you don’t care about the size of the commitments, and since you only require binding, and not hiding, you can have your commitment simply be the value itself. In this case there’s no more overhead at all.

1 Like