Error in evaluation of proof inequalities

[cargodog]

According to the paper, the verifier should assert that equations (1), (2), (3), (4), & (5) all equal 0. To improve performance, I combined these evaluations into one single inequality, so as to perform only one large multiexponentiation. Unfortunately, this breaks the proof guarantees. It is possible to choose inputs which satisfy the combined inequality, while not satisfying one or more of the individual inequalites mandated by the proof protocol.

To illustrate, consider two inequalities:

(a) 2x - 6 = 0
(b) y - 8 = 0

Next, consider joining the two inequalities (a) & (b), to create a new inequality (c):

(c) 2x + y - 14 = 0

It is possible to choose x & y such that (c) is satisfied, but not (a) and/or (b). For example, choosing x == 7 & y == 0 would satisfy (c), but not satisfy (a) or (b). Thus, a verifier which only tests (c) does not actually guarantee that (a) and (b) hold.

[cargodog]

The solution, obviously, is to evaluate each inequality independently.

[SarangNoether]

There is an efficient safe way to do this with a single equality check-to-zero. The verifier chooses random (that is, unknown to the prover) scalars and uses them to weight the left-hand side of each equation before summing.

In your example, the verifier chooses random scalar weights w_a and w_b, and then checks:

w_a(2x-6) + w_b(y-8) = (2*w_a)x - 6*w_z + w_b*y - 8*w_b == 0

Further, if the equations have any group elements (in the previous example, we might assume x and y) in common, they need appear only once in the resulting single equation. You can read more about this idea in Section 6.2 of the Bulletproofs preprint.

[cargodog]

Ah, indeed! Thanks for straightening me out. Too many late nights :stuck_out_tongue: