search

NilFoundation / zkLLVM

Zero-Knowledge Proof Systems Circuit Compiler
https://docs.nil.foundation/zkllvm
273 stars 44 forks source link

Selector columns must not depend on input #591

Open CblPOK-git opened 3 months ago

CblPOK-git commented 3 months ago

As far as selectors is a part of constraint system it must not be depend on the inputs. Now during handling brunch under false condition we manually disable corresponded selectors which is actually wrong behavior. Possible solution - introduce extra flag variable into each constraint under branch:

if (cond) {
    a = b + c;
} else {
    a = d + f;
}

Current constraints

w_0_0 + w_1_0 - w_2_0
w_0_1 + w_1_1 - w_2_1

Should be

(w_0_0 + w_1_0 - w_2_0) * w_3_0
(w_0_1 + w_1_1 - w_2_1) * w_3_1

where w_3_0 is (cond == true), w_3_1 is (cond == false)

But it's not avoid possible security issue till selectors are part of the public assignment table (any body can just set all 0 and proof will be successfully verified for any input)

akokoshn commented 2 months ago

Now selectors not depend on the inputs, they have same values for both (true/false) branches. It means we have to fully fill assignment table for both branches, so using bellow approach can speed up generation assignment table.