This PR optimizes the compressor circuits used for the recursion to reduce the number of constraints and hence minimize the proving computation time. The following optimizations has been applied to the Goldilocks circuits:
A new custom gate TreeSelector8 has been added. This custom gate calculates the root of the tree given 8 values and a key of 3 bits, taking into account that in each level if the key is 0 we push the even positions and the odd ones otherwise.
CMulAdd custom gate is replaced by CMul. The additions are done directly in circom
A new custom gate CustPoseidon has been added. This custom gate is used when calculating a merkle root from a value and its sibling path. The idea here is that, instead of doing a multiplexor to determine which element (either value or sibling) is the left one, we sent the key as input of the custom gate along with the goldilocks field elements. Then, in the Poseidon custom gate there will be a first round in which we will order the inputs according to the key bit.
Poseidon custom gate verification is now done using the Neptune implementation, meaning there are only 8 full rounds and 22 partial ones.
From now on, there will be two different compressing PIL templates: C18 and C15 (which means 18 and 15 committed polynomials respectively). The first one will replace the current "c12a" and will also be used for recursive1 and recursive2. The C15 will be used only for the recursiveF. The reason is that the C18 requires more evaluations when verifying, enough to make the final circuit to jump to the next power of 2, which would double the time the final proof takes.
Both templates are very similar and uses the same custom gates, although inputs are set a bit differently.
In C15, Poseidon takes 11 rounds to verify: Initial Inputs -> Round 1 -> Round 2 -> Round 3 -> Round 4 -> Round 15 -> Round 26 -> Round 27 -> Round 28 -> Round 29 -> Outputs. Notice that all 22 partial rounds are verified in two rows, each one verifying 11 rounds at once. Poseidon custom gate only uses 12 out of 15 committed polynomials in each round. All other custom gates will use all 15 committed polynomials (and in some cases the next row). When it comes to plonk gates, the first 5 constants validate two sets of wires a[0], a[1], a[2] and a[3], a[4], a[5] while the second set of constants validates three sets of wires a[6], a[7], a[8] , a[10] a[11] a[11] and a[12], a[13], a[14]. If the custom gates have enough unused committed polynomials some plonk wires are also added there. For example FFT requires 24 values, which means two rows, but there are 6 values unused which are used to validate two plonk wires.
On the other hand, in the C18 Poseidon only takes 6 rounds to verify: Initial Inputs -> Round2 -> Round4 -> Round26 -> Round28 -> Outputs. At each row we are verifying 2 Poseidon steps. These results in higher degree intermediate polynomials, but allows us to reduce the number of constraints used. In this template, all custom gates (except for TreeSelector and CMul) uses only 12 columns of the committed polynomials. Committed polynomials from a[12] to a[17] are used to verify two plonk wires.
Compressor setup file has been split in a couple of different files to improve its readability. Additionally, a new argument called cols can be passed when calling main_compressor_setup.js to specify if the C15 or C18 has to be used. This new argument takes a number as an input, and currently it can only be either 15 or 18.
Compressor exec has been generalized.
Tests for the tree Selector circuit have been extended
Generation of the stark info is also improved by caching the intermediate expressions and the expressions dimension.
To summarize, the following custom gates have been added / changed:
CMulAdd -> CMul
Poseidon -> Verification is now done using Neptune optimizations
Poseidon -> Two different custom gates, one for Poseidon using 3 inputs (Linear Hash) and one for Poseidon using 2 inputs (VerifyMerkleHash). This last one has a previous round in which we apply the key to the inputs
TreeSelector: New custom gates
C12 -> Now we have two different compressor circuits: C15 and C18. The number basically stands for the number of committed polinomials. The reason for this extension is basically verifying more plonk constraints in the same row
This PR optimizes the compressor circuits used for the recursion to reduce the number of constraints and hence minimize the proving computation time. The following optimizations has been applied to the Goldilocks circuits:
TreeSelector8has been added. This custom gate calculates the root of the tree given 8 values and a key of 3 bits, taking into account that in each level if the key is 0 we push the even positions and the odd ones otherwise.CustPoseidonhas been added. This custom gate is used when calculating a merkle root from a value and its sibling path. The idea here is that, instead of doing a multiplexor to determine which element (either value or sibling) is the left one, we sent the key as input of the custom gate along with the goldilocks field elements. Then, in the Poseidon custom gate there will be a first round in which we will order the inputs according to the key bit.From now on, there will be two different compressing PIL templates: C18 and C15 (which means 18 and 15 committed polynomials respectively). The first one will replace the current "c12a" and will also be used for recursive1 and recursive2. The C15 will be used only for the recursiveF. The reason is that the C18 requires more evaluations when verifying, enough to make the final circuit to jump to the next power of 2, which would double the time the final proof takes. Both templates are very similar and uses the same custom gates, although inputs are set a bit differently.
In C15, Poseidon takes 11 rounds to verify: Initial Inputs -> Round 1 -> Round 2 -> Round 3 -> Round 4 -> Round 15 -> Round 26 -> Round 27 -> Round 28 -> Round 29 -> Outputs. Notice that all 22 partial rounds are verified in two rows, each one verifying 11 rounds at once. Poseidon custom gate only uses 12 out of 15 committed polynomials in each round. All other custom gates will use all 15 committed polynomials (and in some cases the next row). When it comes to plonk gates, the first 5 constants validate two sets of wires a[0], a[1], a[2] and a[3], a[4], a[5] while the second set of constants validates three sets of wires a[6], a[7], a[8] , a[10] a[11] a[11] and a[12], a[13], a[14]. If the custom gates have enough unused committed polynomials some plonk wires are also added there. For example FFT requires 24 values, which means two rows, but there are 6 values unused which are used to validate two plonk wires.
On the other hand, in the C18 Poseidon only takes 6 rounds to verify: Initial Inputs -> Round2 -> Round4 -> Round26 -> Round28 -> Outputs. At each row we are verifying 2 Poseidon steps. These results in higher degree intermediate polynomials, but allows us to reduce the number of constraints used. In this template, all custom gates (except for TreeSelector and CMul) uses only 12 columns of the committed polynomials. Committed polynomials from a[12] to a[17] are used to verify two plonk wires.
Compressor setup file has been split in a couple of different files to improve its readability. Additionally, a new argument called
colscan be passed when callingmain_compressor_setup.jsto specify if the C15 or C18 has to be used. This new argument takes a number as an input, and currently it can only be either 15 or 18.Compressor exec has been generalized.
Tests for the tree Selector circuit have been extended
Generation of the stark info is also improved by caching the intermediate expressions and the expressions dimension.
To summarize, the following custom gates have been added / changed: