Score:4

Which is the relation between Zero-Knowledge Proofs of Knowledge and circuits?

in flag

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?
Score:2
us flag

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.

Bean Guy avatar
in flag
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?
Bean Guy avatar
in flag
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](https://en.wikipedia.org/wiki/Proof_of_knowledge#Schnorr_protocol) in terms of circuits.
SEJPM avatar
us flag
@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...
Bean Guy avatar
in flag
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".
Geoffroy Couteau avatar
cn flag
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.
Bean Guy avatar
in flag
@GeoffroyCouteau Then, is there such a language in the case of *specific* ZKPoK, i.e., not rephrased as a circuit? Which is the language in those cases?
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.