2
$\begingroup$

For example, If I wanted to prove that:

$$x^2 + x^3 = 45$$

This cost of this would be calculated by counting the number of multiplications that need to be done, and not the addition of $x$ squared and $x$ cubed.

$\endgroup$
  • 1
    $\begingroup$ The reference? as long as the number of additions is not excessive, in big O notation, the multiplication is dominant. $\endgroup$ – kelalaka Feb 23 '19 at 21:59
  • $\begingroup$ There was no reference, just something I usually see in rank-1 constraint systems $\endgroup$ – WeCanBeFriends Feb 23 '19 at 22:00
  • 2
    $\begingroup$ that you see where? We cannot guess which kind of papers you are thinking about when mentioning "constraint systems for zk". $\endgroup$ – Geoffroy Couteau Feb 23 '19 at 22:28
  • 1
    $\begingroup$ Bulletproofs, for example, have this property. $\endgroup$ – Ruben De Smet Feb 24 '19 at 9:23
1
$\begingroup$

Your question seems to assume this is true for any constraint proof system. I'm quite confident that this property is on a case-by-case basis. Bulletproofs, for example, have this property: proof size is $\log(n)$, with $n$ the amount of multipliers in the arithmetic circuit. In the rest of my answer, I'll talk about how a bulletproof achieves this.

I'll give a very condensed sketch of how bulletproofs achieve this property. For a more in-depth explanation, I suggest to read the above paper, or the (in my opinion) simpler notes of the good folks at dalek-cryptography.

Bulletproofs writes their constraint system in a single vector equation like follows:

\begin{aligned} \mathbf{W}_L \cdot \mathbf{a}_L + \mathbf{W}_R \cdot \mathbf{a}_R + \mathbf{W}_O \cdot \mathbf{a}_O = \mathbf{W}_V \cdot \mathbf{v} + \mathbf{c} \end{aligned}

Here, the $\mathbf{W}_{\{L,R,O,V\}}$ are weight matrices: they map secrets from their right hand side to constraints. $\mathbf{v}$ are the input secrets. Note that this equation contains the linear constraints, not the multipliers. In what follows, they combine it with the multipliers ($\mathbf{a}_L\circ \mathbf{a}_R=\mathbf{a}_O$), and then this equation is molded into a form $t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle$, in which $x$ is a challenge of the verifier. Here's the first clue: $\mathbf{l}(x)$ and $\mathbf{r}(x)$ are of length $n$, the amount of multiplication gates.

The proof process links $t(x)$ and the two vectors $\mathbf{l}(x)$ and $\mathbf{r}(x)$ to the secret input commitments (in constant size), and then goes on to prove that their inner product relation holds: the inner product proof. This was introduced by Bootle et al., in Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting, and improved upon in the bulletproofs paper. This is your second clue: this inner product argument that proves something of the form $t=\langle \mathbf{l}, \mathbf{r}\rangle$ needs $\log(|l|)=\log(|r|)$ communication.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Would the downvoter care to explain themselves? $\endgroup$ – Ruben De Smet Feb 27 '19 at 14:09
  • $\begingroup$ You say that the Ws are weight matrices? so the aL, aR and aO are unit vectors? I wrote a recent question that relates to this; how does this link to circuits? Not sure, here in the comments would be appropriate to answer the latter question, please check latest question. Thanks for the help $\endgroup$ – WeCanBeFriends Mar 7 '19 at 23:43
  • $\begingroup$ I'm not sure, you've answered why bulletproof for example have chosen to ignore the addition in arithmetic circuits? BTW I was not the downvoter :D $\endgroup$ – WeCanBeFriends Mar 7 '19 at 23:45
  • 1
    $\begingroup$ It's not that they ignore, them, it's that the math makes it so that additions don't contribute to the proof size! I'll have a look at what I can do with your latest question. $\endgroup$ – Ruben De Smet Mar 8 '19 at 7:50

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.