Make code to match the last Plonk paper

[xevisalle]

This PR makes the protocol to match the last version of the Plonk paper. Furthermore, it includes a document specifying our implementation of Plonk, which deviates from the original one to include custom gates.

Main changes

The main changes are:

• Make round 4 and 5 of the prover to match the paper.
• Update the computation of the linearization polynomial r.
  • The prover now adds the evaluation of the public inputs polynomial at z_challenge to r.
  • The prover now subtracts the factor multiplying the evaluation of the vanishing polynomial at z_challenge by the quotient polynomial from r. As such, the quotient polynomial is not needed to compute W_z(X).
  • The verifier now computes r_0_eval. As such, the verifier no longer needs to receive r_eval.
  • The verifier now subtracts the factor multiplying the evaluation of the vanishing polynomial at z_challenge by the quotient polynomial commitment from [D]_1. As such, the verifier doesn't need to compute t_eval, as it is not needed to compute [E]_1.
• The verifier adds u_challenge when computing the polynomial commitment [D]_1.

Minor changes

Some minor changes have been addressed:

• Rename some variables to match the paper, making it easier to assess the correctness of the protocol.
• Refactor the proof verification to improve the efficiency and to make the code more clear.
• Other minor fixes.

Collateral effects

The above changes have led to the following collateral effects:

• Proof verification is now 40% faster (~ from 6ms to 3.7ms on Apple M1).
• Proof size has been reduced by 1 BlsScalar.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 96.38298% with 17 lines in your changes missing coverage. Please review.

Project coverage is 85.44%. Comparing base (372319e) to head (883ace4).

Files	Patch %	Lines
src/composer/gate.rs	0.00%	5 Missing :warning:
src/composer/compress.rs	55.55%	4 Missing :warning:
src/commitment_scheme/kzg10/key.rs	90.00%	2 Missing :warning:
src/compiler/prover.rs	97.95%	2 Missing :warning:
src/proof_system/proof.rs	97.43%	2 Missing :warning:
src/proof_system/widget/arithmetic/verifierkey.rs	75.00%	1 Missing :warning:
...stem/widget/ecc/scalar_mul/fixed_base/proverkey.rs	88.88%	1 Missing :warning:

Additional details and impacted files

[](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network) ```diff @@ Coverage Diff @@ ## master #830 +/- ## ========================================== + Coverage 85.32% 85.44% +0.11% ========================================== Files 57 57 Lines 3687 3723 +36 ========================================== + Hits 3146 3181 +35 - Misses 541 542 +1 ``` | [Files](https://app.codecov.io/gh/dusk-network/plonk/pull/830?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network) | Coverage Δ | | |---|---|---| | [src/commitment\_scheme/kzg10/proof.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fcommitment_scheme%2Fkzg10%2Fproof.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2NvbW1pdG1lbnRfc2NoZW1lL2t6ZzEwL3Byb29mLnJz) | `31.57% <100.00%> (-5.27%)` | :arrow_down: | | [src/commitment\_scheme/kzg10/srs.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fcommitment_scheme%2Fkzg10%2Fsrs.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2NvbW1pdG1lbnRfc2NoZW1lL2t6ZzEwL3Nycy5ycw==) | `85.07% <100.00%> (ø)` | | | [src/compiler.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fcompiler.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2NvbXBpbGVyLnJz) | `98.83% <100.00%> (ø)` | | | [src/composer.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fcomposer.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2NvbXBvc2VyLnJz) | `90.36% <100.00%> (ø)` | | | [src/composer/constraint\_system/constraint.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fcomposer%2Fconstraint_system%2Fconstraint.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2NvbXBvc2VyL2NvbnN0cmFpbnRfc3lzdGVtL2NvbnN0cmFpbnQucnM=) | `63.46% <100.00%> (ø)` | | | [src/composer/permutation.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fcomposer%2Fpermutation.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2NvbXBvc2VyL3Blcm11dGF0aW9uLnJz) | `92.60% <100.00%> (ø)` | | | [src/debugger.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fdebugger.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2RlYnVnZ2VyLnJz) | `76.11% <100.00%> (ø)` | | | [src/fft/polynomial.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Ffft%2Fpolynomial.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL2ZmdC9wb2x5bm9taWFsLnJz) | `69.31% <100.00%> (-0.17%)` | :arrow_down: | | [src/proof\_system/linearization\_poly.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fproof_system%2Flinearization_poly.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL3Byb29mX3N5c3RlbS9saW5lYXJpemF0aW9uX3BvbHkucnM=) | `99.04% <100.00%> (-0.16%)` | :arrow_down: | | [src/proof\_system/quotient\_poly.rs](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree&filepath=src%2Fproof_system%2Fquotient_poly.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network#diff-c3JjL3Byb29mX3N5c3RlbS9xdW90aWVudF9wb2x5LnJz) | `100.00% <100.00%> (ø)` | | | ... and [19 more](https://app.codecov.io/gh/dusk-network/plonk/pull/830?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network) | | ------ [Continue to review full report in Codecov by Sentry](https://app.codecov.io/gh/dusk-network/plonk/pull/830?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network). > **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network) > `Δ = absolute (impact)`, `ø = not affected`, `? = missing data` > Powered by [Codecov](https://app.codecov.io/gh/dusk-network/plonk/pull/830?dropdown=coverage&src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network). Last update [372319e...883ace4](https://app.codecov.io/gh/dusk-network/plonk/pull/830?dropdown=coverage&src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dusk-network).