In practice, the circuit need to be proved always has a large size, maybe nearly billion gates, when turns such circuit to QAP, it will generate a large polynomial, which is a high cost to use zkSNARK. So, could the circuit be decomposed into different sub-circuit to reduce the scale of the circuit and also the scale of the polynomial?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Welcome to Crypto.SE! I think this may be an interesting question, but requires a bit of extra explanation or context, and some aid in grammar. How would you see the sub-circuits? Would you see them as separate proofs, for example? $\endgroup$– Ruben De SmetSep 25, 2020 at 16:07
-
$\begingroup$ I have seen the word of sub-circuits from the code of Bellman, which is a implementation of zkSNARK in rust, the link is link. From the comment, I thought them are not separate proofs, cause they can finally be merged into a complete proof. I don’t know if my understanding is correct :p $\endgroup$– MkotoriSep 27, 2020 at 2:35
-
$\begingroup$ I think your understanding is correct, but as far as I can tell, the sub-circuits are only a programming construct: all the sub-circuits (also called "gadgets") are merged together into a large circuit for proving. I'm not too acquainted with the zkSNARKs that you link, but at least in Bulletproofs this does not reduce the scale of the circuit nor the cost. If this answers your question, I'll happily reformat it into An Answer. $\endgroup$– Ruben De SmetSep 28, 2020 at 8:49
-
$\begingroup$ Thanks for your help, you can definitely reformat it. $\endgroup$– MkotoriSep 29, 2020 at 2:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Large circuits are definitely a bottleneck for proof systems. Splitting them into sub-circuits (often reffered to as "gadgets") is mainly a programming construct: gadgets are the equivalent of functions, methods or classes in circuits.
To illustrate, imagine the (informal) statement "The data I am sending to you decrypts to something that is a picture". Proving that statement involves multiple steps, and you can decompose it into
- Decrypt the data (prove that you know the decryption key)
- Typecheck the data (prove that the decrypted data is in fact a picture)
The first step involves a circuit that is equivalent with the decryption and the authentication (which demonstrates the knowledge of the key), and the output of that sub-circuit can be fed into the second sub-circuit, which checks that the output is in fact a picture.
To come back to your question: no, this does not allow for more compact circuits (at least not in the proof systems that I know), since it is merely a programming construct, an abstraction for the programmer. It does however allow to investigate the performance of the gadgets separately, and perhaps optimize them.
Depending on the problem at hand, you might be interested in recursive proof composition (e.g. [1]), which allows you to recursively nest a circuit. This is especially useful if you are thinking about incrementally verifiable computation (IVC) or proof-carrying data (PCD).
[1] Bowe, Sean, Jack Grigg, and Daira Hopwood. "Halo: Recursive Proof Composition without a Trusted Setup." IACR Cryptol. ePrint Arch. 2019 (2019): 1021.
