Todd/is eq gate

[GhostOfGauss]

Adds some gates that can be useful in combination with conditional selection.  They are 

• is-zero-gate Has one input variable and one output variable.  The output variable is constrained to have the value 1 if the input is zero and to have the value 0 if the input is non-zero.
• is-eq-gate has two input variables and an output variable which is constrained to have the value 1 if the two inputs have equal values and 0 otherwise.

The gates were added in the boolean submodule of the constraint_system module.  This seemed logical to me but should be checked.  

closes #76

[lopeetall]

Ok, this is weird. I'm looking into it. All I know so far is that the q_arith vector is all 1s, so it's polynomial representation is constant. Then ark poly commit refuses to commit with KZG bc the poly is degree 0.

On Thu, Dec 30, 2021 at 6:12 AM Todd Norton @.***> wrote:

@.**** commented on this pull request.

In src/constraint_system/boolean.rs https://github.com/ZK-Garage/plonk/pull/77#discussion_r776680177:

     //This has value 1 if input value is zero, value 0 otherwise

     let result_value = E::Fr::one() - *a_value * a_inv_value;

     let a_inv = self.add_input(a_inv_value);

     let result = self.add_input(result_value);

     // Enforce constraints

• let a_times_result = self.arithmetic_gate(|gate| gate.witness(a, result, None).mul(E::Fr::one()));

• let a_times_result = self.arithmetic_gate(|gate| {

• gate.witness(a, result, None).mul(E::Fr::one())

• });

   self.assert_equal(a_times_result, self.zero_var());

Thanks for the tip, I see how to use the w_o option correctly now. Unfortunately doing so causes my tests to fail. The error seems to occur here https://github.com/arkworks-rs/algebra/blob/7657bcb7280ffb112056d59f2817c484ee4a6a6d/poly/src/polynomial/univariate/dense.rs#L35

when getting the degree of a polynomial during proof generation. Any idea why using w_o : None and assert_equal works but combining them as you suggested wouldn't? The exact change I made is to replace lines 68-70 with let a_times_result = self.arithmetic_gate(|gate| { gate.witness(a, result, Some(zero)).mul(E::Fr::one())});

where zero is self.zero_var()

Could the problem be that this creates a variable a_times_result which is never used by the circuit?

— Reply to this email directly, view it on GitHub https://github.com/ZK-Garage/plonk/pull/77#discussion_r776680177, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAL2AEBNOYRAT3J4XU7D6RDUTQ5AVANCNFSM5K4QFEDA . You are receiving this because your review was requested.Message ID: @.***>

[lopeetall]

Ok, mystery solved. This is because: add_dummy_constraints adds 2 arith gates to every circuit, and your circuit contains 6 more arith gates. This creates a circuit with 8 gates, all arith. This circuit is never padded out with zeros because it has a length of a power of 2 already. So the q_arith selector ends up as all 1s and its polynomial representation is degree 0 which triggers an error in KZG.

The original circuit had length 9. So it gets padded out to 16 with 0s and q_arith does not end up constant, so it works.

Indeed, if you make all the changes I suggested the total circuit length drops to 6. Then the test passes again!

I'll file an issue for the dummy constraint problem. It should be an easy fix.

[GhostOfGauss]

@lopeetall Thanks so much for getting to the bottom of that!  I wouldn't have thought of that.  It explains why I could get one of the two tests to pass but not both.  

I must be having trouble counting gates, because even when implementing your suggestions I still receive this error.  My current workaround is to add additional dummy constraints in the is_eq part of the gadget.  I suppose these can be removed once the 2^k bug is worked out.

[lopeetall]

Oh boy. This goes deeper. Now it is q_4 that is throwing the commit error, even though it is not the zero polynomial. I did some experimenting and believe the bug is in ark-poly-commit.

The monomial basis form for q_4 has a lower degree than expected for the domain and so it's leading coefficient is 0. This should be fine. However ark-poly-commit doesn't like this when it checks the degree and it throws an error. This is an oversight from ark-poly-commit and the way they check polynomial degree.

[lopeetall]

The gates themselves look good to me. The 2^k problem only happens in your tests of the circuit, each of which add an extra constraint.

The add_dummy_constraints() hack to get around the ark-poly-commit bug is only really needed in the tests. If you add the dummy constraints to the gadget composer inside the failing tests they will pass again. Then at least we can keep the gates themselves free from any hacks that we will have to remember to remove later.

[LukePearson1]

This is proving to have an interesting bug. Issue #78 explains the problem. @CPerezz