# In constraint systems for ZK proofs, why are multiplications counted but are additions not?

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.

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

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.

• Would the downvoter care to explain themselves? – Ruben De Smet Feb 27 '19 at 14:09
• 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 – WeCanBeFriends Mar 7 '19 at 23:43
• 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 – WeCanBeFriends Mar 7 '19 at 23:45
• 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. – Ruben De Smet Mar 8 '19 at 7:50