# Summa V3 variations analysis

## Introduction

This technical report explores the advancements in the third major iteration of Summa, known as Version 3 (V3), which aims to enhance performance over its predecessors. The previous version, V2, retained the underlying architecture of Halo2's Plonk, which presented bottlenecks, particularly during the discrete Fourier Transform (dFT) process, where polynomial coefficients are transformed into evaluation points. To address these inefficiencies, we transitioned to using the HyperPlonk backend, a shift necessary to improve performance by avoiding the use of dFT.

However, this adaptation also uncovered a new vulnerability known as the "rebalancing attack" while optimizing circuit design in V3. In response to this challenge, we developed variations of V3 to provide solutions for safety concerns:

- **V3-A** is the initial version using HyperPlonk, focusing on integrating and assessing the capabilities of this new backend. It includes additional columns for the running sum compared to the V2 circuit.
- **V3-B** addresses scalability of **V3-C** by concatenating balances into a single balance column, thereby avoiding a newly discovered attacking vector(referred to as the "rebalancing attack") on the modified HyperPlonk backend.
- **V3-C** modifies the circuit structure to exclude the running sum column from **V3-A**, safely handling a single currency and avoiding the newly discovered attacking vector(referred to as the "rebalancing attack") on the modified HyperPlonk backend.

This report will detail the technical developments, implementation experiences, and performance evaluations of these three variants.

## V3 Implementations
### V3-A: Transition to HyperPlonk

In the initial implementation of Version 3, known as V3-A, our team addressed the challenge of transitioning the backend from Plonk, as used in Halo2, to HyperPlonk.

A crucial adaptation in V3-A was the introduction of additional columns specifically for the running sum. Unlike in V2, where the V2 implementation could directly obtain total balances that met constraints through special feature, 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:
| username | balance_A | balance_B | sum_A | sum_B |
| -------- | --------- | --------- | -------:| ------:|
| dxGaEAii | 1,000 | 100 | 1,000 | 100 |
| MBlfbBGI | 2,000 | 200 | 3,000 | 300 |
| ... | ... | ... | ... | |
| AtwIxZHo | 100 | 0 | 783,100 | 38,000 |

When we want to add more currencies in a single proof, it requires adding another column for the running sum, such as "Sum_A". This makes the commitment size almost double compared to V2. Therefore, Alex brought forward the idea of handling total balances without using the running sum column(s).

### Introducing Non-Zero Constraints

Following the development of V3-A, the team aimed to refine the design further by addressing the increase in proof size due to the additional running sum columns. To achieve this, a key modification was made to the HyperPlonk backend through the introduction of the non-zero constraint feature[^pr_1], which Alex played a significant role in developing.

This adjustment enables the inclusion of an extra row within the circuit design at the end of user balances during the sumcheck process. While it is possible to add an extra row without the non-zero constraint feature, this implementation ensures that such additions are effectively incorporated, guaranteeing that all balances are accurately computed in accordance with the non-zero constraint. We might structure the circuit as follows:

| username | balance_A | balance_B |
| -------- | -----------:| ----------:|
| dxGaEAii | 1,000 | 100 |
| MBlfbBGI | 2,000 | 200 |
| ... | ... | ... |
| AtwIxZHo | 100 | 0 |
| | **783,100** | **38,000** |

This configuration ensure that when balances are summed like an example: $$ 1,000 + 2,000 + ... + 100 - 783,100 + 100 + 200 + ... + 0 - 38,000 = 0$$
However, it introduces an attack vector that allows the prover to understate one asset balance and overstate another by the same amount. For example, inputting a total balance of 821,100 for Sum of `balance_A` and 0 for Sum of `balance_B` would still appear valid:

| username | balance_A | balance_B |
| -------- | -----------:| ---------:|
| dxGaEAii | 1,000 | 100 |
| MBlfbBGI | 2,000 | 200 |
| ... | ... | ... |
| AtwIxZHo | 100 | 0 |
| | **821,100** | **0** |

We named this attacking vector as "rebalancing attack". and We have to mitigate this.

### V3-C: Handling a Single Currency

One straightforward approach to avoid the rebalancing attack is to handle only a single currency, utilizing the non-zero constraint feature. While this method is safe, it offers less scalability.
The circuit might be structured as follows:

| username | balance |
| -------- | ---------:|
| dxGaEAii | 1,000 |
| MBlfbBGI | 2,000 |
| ... | ... |
| AtwIxZHo | 100 |
| | 783,100 |

In this configuration, there is no incentive to manipulate the total balance when only one currency is handled.

### V3-B: Scaling with Concatenating balance

Like in **V3-C**, where it is safe to use only one column for the non-zero constraint feature, we sought to enhance scalability. In V3-B, we achieve this by encoding multiple balance values within a single column. Unfortunately, each cell in the finite field Bn254 can encode a value up to 254 bits, and the balance value is limited to 64 bits due to the range check chip allowance. Thus, we can split one cell to accommodate up to three currencies (84 * 3 = 252, which is less than 254).

The concatenated balance for three currencies would appear as follows in a single cell:

0x00000000000003FFFFFFF00000000000002FFFFFFF00000000000001FFFFFFF

This format concatenates the three values:

A: 0x3FFFFFFF
B: 0x2FFFFFFF
C: 0x1FFFFFFF

Through this concatenated balance column, V3-B can handle up to three currencies using a single column with the non-zero constraint. Each balance is allocated 84 bits within the finite field Bn254, totaling 252 bits for three currencies.

Furthermore, this concatenated balance also sums up each row using a non-zero constraint. This means that the 20 bits (20 = 84 - 64 bits) can be used for separation and summation of all balances. For example, if all users hold `balance_A` at the value of 0xFFFFFFFF, which is the maximum value for 64 bits, the 20 bits of the concatenated balance would be used as a running sum for one currency. This implies that the user base cannot exceed $2^{20}$. If the prover uses this for over $2^{20}$ users, it could potentially affect the totals of subsequent currencies in the concatenated balance.

Moreover, it's crucial to understand that when multiple balances, such as balance_A and balance_B, are combined into one field, the concatenated balance naturally exceeds 64 bits. This necessitates the establishment of a new constraint for unconcatenated values to ensure that each balance within the concatenated field is verified accurately during the range checking process.

The circuit would look like:
| username | concatenated balance | balance_A | balance_B |
|----------|----------------------|-----------|-----------|
| dxGaEAii | 0x0000..03e8..0064 | 0x3e8 | 0x64 |
| MBlfbBGI | 0x0000..07d0..00c8 | 0x7d0 | 0xc8 |
| ... | ... | ... | ... |
| AtwIxZHo | 0x0000..00c8..0000 | 0xc8 | 0 |
| | 0x000..bf2fc..9470 | | |

`balance_A` and `balance_B` are used not only for range checks but also to verify that they are consistent with the concatenated balance.

## Performance Comparison by V3x

Comparing the V3 variations to each other is challenging due to the limited number of currencies in `V3-B` and `V3-C`. However, we can examine cases with either three or one currency. `V3-B` can be compared with `V3-A` in a three-currency configuration, and `V3-C` can be compared with `V3-A` in a one-currency setup.

**V3-A and V3-B performances with three currencies**

| Version | Commitment generation time | Inclusion generation time |
|:-------:| -----------------------------:| -----------------------------:|
| V3-A | 16,219.3 ms | 124.0 ms |
| V3-B | 16,254.2 ms | 114.5 ms |

- V3-B improved the inclusion generation time by 7.6% (a reduction of 9.5 ms) while showing a 0.2% increase in commitment generation time, adding 34.85 ms. Reducing inclusion time is more critical than commitment time because it is a key factor in shortening the intervals between rounds if the custodian generates all inclusion proofs for users.

**V3-A and V3-C performance with one currency**

| Version | Commitment generation time | Inclusion generation time |
|:-------:| -----------------------------:| -----------------------------:|
| V3-A | 5,703.4 ms | 111.2 ms |
| V3-C | 5,506.4 ms | 109.25 ms |

- With one currency, V3-C decreased the commitment generation time by 3% (a reduction of 197.1 ms), which is an improvement over V3-A. However, the gain in the inclusion proof generation time is minimal at 0.17% (a reduction of 1.95 ms).
- The results indicate that `V3-C` does not offer significant benefits when the custodian generates proofs for more than one currency, compared to `V3-A`. This is because `V3-A` can generate inclusion proofs in less than 200 ms for 100 currencies case - [Performance Comparison - Inclusion proof(V3a)](https://hackmd.io/wt4NkeUWSWi2ym6DNcsT-Q?view#Performance-Comparison-by-Summa-versions).

## Conclusion

This report has detailed the advancements in Summa’s Version 3, focusing particularly on the unique attributes of **V3-B** and **V3-C**. These versions are optimized for specific use cases involving a limited number of currencies.

**V3-B** excels when operating with up to three currencies, effectively balancing the trade-offs between the number of balance columns required and the constraints involved. This balance is achieved through the use of concatenated balances, which allow for efficient processing while maintaining security. In operational scenarios requiring the handling of three or fewer currencies, **V3-B** optimizes the circuit's efficiency by eliminating the need for running sum columns and introducing more specific constraints, avoiding additional circuit complexity.

For custodians managing just one currency, **V3-C** offers a slight performance gain and is the optimal choice due to its streamlined circuit design. This design simplifies the constraints and enhances performance, making it well-suited for simpler setups where a single currency is involved.

[^pr_1]: https://github.com/summa-dev/plonkish/pull/2