SummaHyperplonk
Last updated
Last updated
SummaHyperplonk circuit serves three main purposes:
Interpolating user entries and running sum as polynomials and committing to them.
Performing range check on the user balance values.
Calculating the running sum values and check its correctness
The interpolation and commitment come "for free" with the Halo2 frontend. The advice columns in HyperPlonk backend are interpolated as polynomials over the boolean hypercube during the proof generation. The Multilinear KZG commitment to each of the interpolated polynomials is then produced by the framework and recorded inside the proof transcript. This allows the prover to simply fill the advice columns with user entry values without performing any additional actions. An important detail to note here is that the cryptocurrency balance advice columns are unblinded columns, because blinding values would alter the polynomial total sum.
The range check is performed using the range check chip.
Range check chip constrains the input value to be within a range of 8 bytes. In the context of Proof of Reserves, performing the range check is necessary to avoid overflow during the polynomial total sum calculation. The chip performs a decomposition of the checked value into two-byte words and ensures that each of the word values is found in a lookup table. The lookup table is loaded with all the possible values that a word can take (0 to 2^16 - 1). Therefore, the chip is decomposing the 8-byte value into four words.
To prove that the 64-bit balance values would not cause the overflow of the total sum, let's consider the case at the limit in which we have 2^28 users and all their balances are the maximum possible (namely, ):
The resulting total sum is only 92 bits. Therefore, we can conclude that the range check of 64 bits on the user balances safely removes the risk of overflow in the total sum calculation.
It is important to note that the number of users, calculated as 2^28 in this example, is limited to 2^20 in the Summa V3-B variation due to the introduction of a concatenated user balance. For more information on this limitation, please refer to the documentation on the V3-B variation.
A significant change in V3 is the introduction of additional columns specifically for the running sum. This differs from the approach in V2, where the Univariate Grand Sum is was used to directly obtain total balances that met constraints through existing features. HyperPlonk required a different approach. To maintain functionality and ensure the accurate computation of total balances under the constraints defined by the HyperPlonk, these additional columns became essential.
The circuit of V3-A looks would be look like:
dxGaEAii
1,000
100
1,000
100
MBlfbBGI
2,000
200
3,000
300
...
...
...
...
AtwIxZHo
100
0
783,100
38,000
It's important to note that there is no range check for the values in the running sum columns like to username column. This is because the values are constrained by the running sum gate, which operates as follows: running_sum_A[0] + balance_A[1] - running_sum_A[1] == 0 .
Here, the number in brackets indicates the row number.
However, these running sum columns come with their own set of challenges. They increase the computational cost and commitment size compared to the previous version of Summa. In essence, this is another trade-off point that emerged while avoiding FFT from V2. To circumvent the need for running sum columns for total sum calculation, we implemented the e non-zero constraint that accumulates the total sum without the running sum columns. But this introduced a new attack vector known as the Rebalancing Attack.
The rebalancing attack allows the prover to manipulate the total sum of the currencies while maintaining the same sum of all values in the balance columns of the circuit, through the use of the 'non-zero constraint'.
To address these issues, we developed two variations of V3, namely V3-B and V3-C, to achieve better performance in scenarios that handle a few currencies in Summa. For a detailed comparison of these variations, refer to this article - Summa V3 variations analysis.
The circuit configuration allocates one advice column for the user ID values, N_CURRENCIES unblinded advice columns and (another) N_CURRENCIES advice columns for running sum for the user cryptocurrency balances. One fixed column is allocated for the lookup table of the range check chip. This fixed column is shared across all the range check chips. The circuit configures one range check chip per user per cryptocurrency. Each range check chip configuration allocates four advice columns to decompose the balance value into four two-byte words.
The circuit does not calculate any kind of public outputs because the desired results of the circuit operation are the multilinear KZG commitments to advice polynomials that Halo2 writes to the proof transcript during the proof generation.
The circuit synthesis begins with assigning the user entries. The user ID is assigned to the first advice column, and the N_CURRENCIES user balances are assigned to the corresponding unblinded advice columns. The running sum values are calculated and then assigned to additional advice columns. This assignment process occurs row by row while assigning user entry values.
Later, the circuit assigns the values 0...2^16 - 1 to the fixed column used for the range check chips.
Finally, the circuit fills the range check chip advice cells with the decomposed values for the corresponding user cryptocurrency balance.
The ZK circuit structure is shown in the figure below.
