Refactor Proving/Verifying Keys

[bhgomes]

This PR addresses some refactors and design changes to improve the development experience and extensibility of the library. Closes #14. Closes #48.

Design

This PR adds a new trait with the following signature:

trait GateConstraint<F>
where
    F: Field,
{
    fn constraints(separation_challenge: F, values: GateValues<F>) -> F;
}

where GateValues<F> is a struct of values available to a custom gate:

struct GateValues<F>
where
    F: Field,
{
    left: F,
    right: F,
    output: F,
    fourth: F,
    left_next: F,
    right_next: F,
    fourth_next: F,
    left_selector: F,
    right_selector: F,
    constant_selector: F,
}

GateConstraint provides a default implementation for the following methods:

fn quotient_term(
    selector: F,
    separation_challenge: F,
    values: GateValues<F>,
) -> F;

fn linearisation_term(
    selector_polynomial: &DensePolynomial<F>,
    separation_challenge: F,
    values: GateValues<F>,
) -> DensePolynomial<F>;

fn extend_linearisation_commitment<E>(
    selector_commitment: Commitment<E>,
    separation_challenge: E::Fr,
    evaluations: &ProofEvaluations<E::Fr>,
    scalars: &mut Vec<E::Fr>,
    points: &mut Vec<E::G1Affine>,
) where
    E: PairingEngine<Fr = F>;

which use the GateConstraint::constraints method to compute these.

To build a custom gate, say the Range gate, one should do the following:

1. Create a marker struct

struct Range<F>(PhantomData<F>)
where
    F: Field;

2. Implement GateConstraint<F> for that struct:

impl<F> GateConstraint<F> for Range<F>
where
    F: Field,
{
    #[inline]
    fn constraints(separation_challenge: F, values: GateValues<F>) -> F {
        let four = F::from(4u64);
        let kappa = separation_challenge.square();
        let kappa_sq = kappa.square();
        let kappa_cu = kappa_sq * kappa;
        let b_1 = delta(values.output - four * values.fourth);
        let b_2 = delta(values.right - four * values.output) * kappa;
        let b_3 = delta(values.left - four * values.right) * kappa_sq;
        let b_4 = delta(values.fourth_next - four * values.left) * kappa_cu;
        (b_1 + b_2 + b_3 + b_4) * separation_challenge
    }
}

/// Computes `f(f-1)(f-2)(f-3)`.
fn delta<F>(f: F) -> F
where
    F: Field,
{
    let f_1 = f - F::one();
    let f_2 = f - F::from(2_u64);
    let f_3 = f - F::from(3_u64);
    f * f_1 * f_2 * f_3
}

3. Add a range_selector to ProverKey
4. Add a range_selector_commitment to VerifierKey
5. Sample a range_separation_challenge during proving/verifying using the transcript.
6. Add the range_selector_commitment to the transcript during proving/verifying.
7. In the quotient polynomial, add the following term to the circuit-satisfiability section:

let range = Range::quotient_term(
    prover_key.range_selector.1[i],
    range_challenge,
    values,
);

which uses the default GateConstraint::quotient_term implementation.

8. In the linearisation polynomial, add the following term to the circuit-satisfiability section:

let range = Range::linearisation_term(
    &prover_key.range_selector.0,
    *range_separation_challenge,
    values,
);

which uses the default GateConstraint::linearisation_term implementation.

9. Add selector to StandardComposer.

Now you have a custom gate! This process can be streamlined even more and we can perform the above nine steps automatically, but this is left for future PRs.

Refactors

The new trait replaces the ProverKey/VerifierKey structs and files for every gate with a single file, single trait implementation. Each custom gate subdirectory in the src/proof_system/widget directory is now replaced with a single file (or a file-per-topic as in the ecc case) which implements the constraints as above.

Also, this PR tries to unify the formatting/documentation used across the library and reduce unnecessary complexity and noise.

Implementation Note

Because the arithmetic gate is treated differently than custom gates, it cannot take advantage of the above trait. This may not be a necessary restriction on the protocol and it could be possible to treat it as all other gates, but this PR does not attempt to address this.

Reviewing

To review this PR see the following list of changes and use the Files changed menu to ensure that these changes correspond to the list below and that they are satisfactory.

Notable Changes: 9, 22, 24, 25, 26, 28, 30, 34, 38, 44, 48, 51, 58

1. Cargo.toml:
   • Added derivative dependency
   • Fixed formatting
2. src/circuit.rs:
   • Updated interfaces for PublicInputValue and VerifierData (NB: Should add an issue to build better abstractions for these constructions.)
   • Fixed formatting/documentation
3. src/constraint_system/arithmetic.rs:
   • Fixed formatting/documentation
4. src/constraint_system/boolean.rs:
   • Fixed formatting/documentation
5. src/constraint_system/composer.rs:
   • Fixed derive semantics using derivative::Derivative
6. src/constraint_system/ecc/curve_addition/fixed_base_gate.rs:
   • Fixed derive semantics
7. src/constraint_system/ecc/curve_addition/mod.rs:
   • Fixed formatting/documentation
8. src/constraint_system/ecc/curve_addition/variable_base_gate.rs:
   • Fixed formatting/documentation
9. src/constraint_system/ecc/mod.rs:
   • Fixed derive semantics
   • Fixed issue with assert_equal_point
   • Fixed formatting
10. src/constraint_system/ecc/scalar_mul/fixed_base.rs:
    • Fixed formatting
11. src/constraint_system/ecc/scalar_mul/mod.rs:
    • Fixed formatting/documentation
12. src/constraint_system/ecc/scalar_mul/variable_base.rs:
    • Improved formatting/documentation
13. src/constraint_system/helper.rs:
    • Fixed formatting/documentation
14. src/constraint_system/logic.rs:
    • Fixed formatting/documentation
15. src/constraint_system/mod.rs:
    • Fixed formatting/documentation
16. src/constraint_system/range.rs:
    • Fixed formatting/documentation
17. src/constraint_system/variable.rs:
    • Fixed documentation
18. src/lib.rs:
    • Fixed formatting/documentation
19. src/permutation/mod.rs:
    • Moved src/permutation/permutation.rs here
20. src/permutation/permutation.rs:
    • Moved to src/permutation/mod.rs
21. src/prelude.rs:
    • Reduced code complexity
22. src/proof_system/linearisation_poly.rs:
    • Fixed derive semantics
    • Removed visibility redundancy
    • Removed PairingEngine constraint where unnecessary
    • Updated to new GateConstraint model
    • Fixed formatting/documentation
23. src/proof_system/mod.rs:
    • Reduced code complexity
24. src/proof_system/permutation.rs:
    • Moved permutation logic outside of widget since it is not a custom gate
    • Moved ProverKey and VerifierKey into one file, eventually, we can share some code between them to reduce repetition
    • Fixed derive semantics
    • Fixed formatting/documentation
25. src/proof_system/preprocess.rs:
    • Fixed ordering of some arguments (range should always come before logic to match the transcript)
    • Fixed formatting/documentation
26. src/proof_system/proof.rs:
    • Fixed derive semantics
    • Moved beta != alpha assertion to correct part of protocol
    • Updated to new GateConstraint model
    • Fixed formatting/documentation
27. src/proof_system/prover.rs:
    • Reduced code complexity
    • Fixed formatting/documentation
28. src/proof_system/quotient_poly.rs:
    • Updated to new GateConstraint model
    • Fixed formatting/documentation
29. src/proof_system/verifier.rs:
    • Fixed formatting/documentation
30. src/proof_system/widget/arithmetic.rs:
    • Moved ProverKey and VerifierKey into the same file
    • Fixed derive semantics
    • Reduced code complexity
31. src/proof_system/widget/arithmetic/mod.rs:
    • Removed in favor of src/proof_system/widget/arithmetic.rs
32. src/proof_system/widget/arithmetic/proverkey.rs:
    • Removed in favor of src/proof_system/widget/arithmetic.rs
33. src/proof_system/widget/arithmetic/verifierkey.rs:
    • Removed in favor of src/proof_system/widget/arithmetic.rs
34. src/proof_system/widget/ecc/curve_addition.rs:
    • Updated to new GateConstraint model
35. src/proof_system/widget/ecc/curve_addition/mod.rs:
    • Removed in favor of src/proof_system/widget/ecc/curve_addition.rs
36. src/proof_system/widget/ecc/curve_addition/proverkey.rs:
    • Removed in favor of src/proof_system/widget/ecc/curve_addition.rs
37. src/proof_system/widget/ecc/curve_addition/verifierkey.rs:
    • Removed in favor of src/proof_system/widget/ecc/curve_addition.rs
38. src/proof_system/widget/ecc/fixed_base_scalar_mul.rs:
    • Updated to new GateConstraint model
39. src/proof_system/widget/ecc/mod.rs:
    • Fixed formatting/documentation
40. src/proof_system/widget/ecc/scalar_mul/fixed_base/mod.rs:
    • Removed in favor of src/proof_system/widget/ecc/fixed_base_scalar_mul.rs
41. src/proof_system/widget/ecc/scalar_mul/fixed_base/proverkey.rs:
    • Removed in favor of src/proof_system/widget/ecc/fixed_base_scalar_mul.rs
42. src/proof_system/widget/ecc/scalar_mul/fixed_base/verifierkey.rs:
    • Removed in favor of src/proof_system/widget/ecc/fixed_base_scalar_mul.rs
43. src/proof_system/widget/ecc/scalar_mul/mod.rs:
    • Removed in favor of src/proof_system/widget/ecc/fixed_base_scalar_mul.rs
44. src/proof_system/widget/logic.rs:
    • Updated to new GateConstraint model
45. src/proof_system/widget/logic/mod.rs:
    • Removed in favor of src/proof_system/widget/logic.rs
46. src/proof_system/widget/logic/proverkey.rs:
    • Removed in favor of src/proof_system/widget/logic.rs
47. src/proof_system/widget/logic/verifierkey.rs:
    • Removed in favor of src/proof_system/widget/logic.rs
48. src/proof_system/widget/mod.rs:
    • Added GateValues and GateConstraint
    • Updated ProverKey and VerifierKey
    • Fixed derive semantics
    • Fixed ordering of some arguments (range should always come before logic to match the transcript)
    • Fixed formatting/documentation
49. src/proof_system/widget/permutation/mod.rs:
    • Removed in favor of src/proof_system/permutation.rs
50. src/proof_system/widget/permutation/verifierkey.rs:
    • Removed in favor of src/proof_system/permutation.rs
51. src/proof_system/widget/range.rs:
    • Updated to new GateConstraint model
52. src/proof_system/widget/range/mod.rs:
    • Removed in favor of src/proof_system/widget/range.rs
53. src/proof_system/widget/range/proverkey.rs:
    • Removed in favor of src/proof_system/widget/range.rs
54. src/proof_system/widget/range/verifierkey.rs:
    • Removed in favor of src/proof_system/widget/range.rs
55. src/test.rs:
    • Removed module nesting
56. src/tests.rs:
    • Renamed to src/test.rs to match the rest of the library
57. src/transcript.rs:
    • Fixed derive semantics
    • Fixed formatting/documentation
58. src/util.rs:
    • Updated powers_of to return an iterator instead of a vector to improve its interface safety
    • Fixed formatting/documentation

[CPerezz]

Will review this during the weekend.

Thanks for the amazing PR description BTW!!!

[bhgomes]

@davidnevadoc @LukePearson1 I can merge this whenever you're ready.

[LukePearson1]

@bhgomes, does the benches/plonk.rs compile on your machine?

[bhgomes]

1) Why removing the black_boxes from the benchmarks? They're useful to prevent compiler optimizations.

Black boxes are called around functions not function arguments and the "benchmark with input" automatically calls black box for you. See the criterion book/source.

My mistake, it appears that you do want to call black_box on some inputs (typically if the inputs themselves can be optimized away), but in this case, criterion handles it for us (but not needed).

[bhgomes]

2) The diff is much larger than what it should be. There are a lot of formatting changes which I'm not sure where are comming from. Are you using the same toolchain??

If you're referring to the permutation files, this is just some corner case of the git diff algorithm I guess, because it's not just a rename but also some code is changed. I've had this happen before, not sure how to set it up differently so that the diff is more reasonable.

If you're referring to the code formatting changes, I did that formatting by hand because rustfmt doesn't have handlers for those patterns. The patterns I use are more standard, more readable, easier to extend, and more diff-friendly. One common formatting pattern is for generics:

impl<E,P> StandardComposer<E,P>
where
    E: PairingEngine,
    P: TEModelParameters<BaseField = E::Fr>,
{}

is preferred over

impl<E: PairingEngine, P: TEModelParameters<BaseField = E::Fr>> StandardComposer<E,P> {}

So I changed the declarations over the code base, hopefully I didn't miss any.