4
$\begingroup$

With the risen popularity of Zero-Knowledge Proofs of Knowledge (ZKPoKs) such as Pinocchio, Groth16 and Sonic, to name some ZKPoKs that are popularly known as zk-SNARKs, I got engaged to understand what is going on behind the hood on these protocols.

The only problem that I encountered is that I do not clearly understand which is the relation ZKPoKs and the underlying scheme on zk-SNAKRKs: Arithmetic Circuits.

Let me ask several questions about it:

  1. Why are arithmetic circuits interesting in the zero-knowledge world?
  2. Why are circuit-based ZKPoK considered "generic"?
  3. Is any specific (a.k.a. not based on circuits) "practical" ZKPoK able to be performed by circuits?
  4. Are circuit-based ZKPoKs more efficient (in time or space) than specific ZKPoKs?
Improve this question
$\endgroup$
2
$\begingroup$

Why are arithmetic circuits interesting in the zero-knowledge world?

There are two main models of general computation: Circuits and Turing-Machines.
Describing the computation path of turing machines is what most mainstream programming languages try to do, however for cryptographic processing there are disadvantages associated with Turing-Machines. Namely, one has to deal with the memory and additionally, Turing-Machines are not exactly the most efficient programming model and all more efficient ones will usually add significantly more complexity, complicating the cryptographic protocols. So, instead, what people do is they use circuits which can express many immediately interesting statements rather easily and you typically only have to specify processing for a handful of operations, i.e. what to do when encountering a multiplication and when encountering an addition. These two operations suffice to describe all functions though some are less efficiently described than others and many functions of interest happen to be small.

Why are circuit-based ZKPoK considered "generic"?

Using the above considerations they allow you to formulate proofs like "I know $x$ for some public $v$ and some public circuit $C$ such that $C(x,v)=1$" which makes them fully generic in the proven statement.

Is any specific (a.k.a. not based on circuits) "practical" ZKPoK able to be performed by circuits?

Any ZKPoK can be re-formulated in terms of a circuit-based one, the question then becomes how big the efficiency losses are and if potential composition benefits are worth it.

Are circuit-based ZKPoKs more efficient (in time or space) than specific ZKPoKs?

Usually the point of specific ZKPoKs is that they can exploit constraints and structures the generic circuit-based ones cannot, making specialized ones usually more efficient. The exception of course being statements about circuits where the generic circuit-based ones and the specialized ones will likely coincide to a large degree.

Improve this answer
$\endgroup$
6
  • $\begingroup$ So, when we talk about "circuit-based ZKPoKs" we refer to protocols of the type that can be used for any circuit that we can think of. In contrast, specific ZKPoKs are protocols that can be used for an specific circuit (using the re-formulation that you commented). Am I right? $\endgroup$
    – Bean Guy
    Jul 12 at 9:53
  • $\begingroup$ Do you have any reference where I can see such a re-formulation for an easy example? I was thinking how I could formulate the Schnoor Protocol in terms of circuits. $\endgroup$
    – Bean Guy
    Jul 12 at 9:57
  • $\begingroup$ @BeanGuy Specific ZKPoKs prove statements over specific classes of circuits, e.g. $C(x,v)=g^x\stackrel{?}{=}v\bmod p$ for finite-field Schnorr proofs (and variants in other groups). I don't have a good reference at hand for a Schnorr comparison, though the circuit should be conceptually simple (see above) though of course actually formulating modular or ECC exponentiation with circuits can generate quite large circuits... $\endgroup$
    – SEJPM ♦
    Jul 12 at 11:22
  • $\begingroup$ Let me then understand something: as Schnorr protocol is a 3-step protocol, I was thinking that to formulate it in terms of circuits we would need 3 circuits, one for each step. But it looks like it is more like one circuit is able to compress the whole protocol. I suppose that this is true after applying the Fiat-Shamir heuristic and then looking at the protocol as a function. Otherwise, I can not see how you can formulate an interactive system to something (a circuit) thas has not "interaction". $\endgroup$
    – Bean Guy
    Jul 12 at 11:50
  • 2
    $\begingroup$ The circuit is not the protocol: the circuit is the language. That is, Schnorr protocol is a 3-step protocol for proving "I know $w$ such that $C(x,w) = 1$", where $C$ is the circuit that outputs 1 iff $g^w = x$ (over the appropriate group). "Circuit-based ZK" refers to ZK proofs that are described for all languages written "in circuit form" as above. For discrete log, standard circuit-based ZK will be quite inefficient since the circuit is large; here, using a dedicated protocol (e.g. Schnorr), which is tailored to this specific language, will be more efficient. $\endgroup$
    – Geoffroy Couteau
    Jul 12 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.