# Hash-based Signature Aggregation

[toc]

## 1. Hash-based Signature Parameter

We use Poseidon2 instantiation with the following parameter:

- $\textbf{Lifetime}\ L = 2^{20}$
- $\textbf{Encoding}\ = \mathsf{TSW}$
- $w = 2$
- $\delta = 1$

The implementation of this specific instantiation could be found [here](https://github.com/b-wagn/hash-sig/blob/5121db48534fcc4cd5cd18a7fd03987021c4c338/src/signature/generalized_xmss/instantiations_poseidon.rs#L678C18-L679).

## 2. Approach - zkVM

### 2.1. With `succinctlabs/sp1` (based on `plonky3`)

- Source code: https://github.com/han0110/hash-sig-agg/tree/main/zkvm/sp1

### 2.2. With `openvm-org/openvm` (based on `plonky3`)

- Source code: https://github.com/han0110/hash-sig-agg/tree/main/zkvm/openvm

## 3. Approach - Circuit

### 3.1. With `plonky3`

- Source code: https://github.com/han0110/hash-sig-agg/tree/feature/use-p3-uni-stark-ext/circuit

#### 3.1.1. Introduction

In order to handle non-uniform computations efficiently, we split the circuit into multiple AIR traces and use lookup to connect input/output between each other.

AIR traces are:

- `Main`
- `Chain`
- `MerkleTree`
- `Decomposition`
- `RangeCheck`


##### 3.1.1.1. `Main`

The `Main` is mainly used to synchronize other AIR traces, it does 3 things:

1. Send `(sig_idx, msg_hash)` to `Decomposition` to make sure the `x` are decomposed from `msg_hash`.
2. Send `(sig_idx, parameter)` to `Chain` to make sure it's using the same `parameter` as others.
3. Send `(sig_idx, parameter, msg_hash, merkle_root)` to `MerkleTree` to make sure the `msg_hash` is computed from the same `parameter` as others, and at the same time send to expected `merkle_root` to be checked for `sigs[sig_idx]`.

And `parameter` and `merkle_root` parts are the statement of this aggregation circuit, verifier can calculate their polynomial evaluations in $O(n\log n)$ tiem by FFT.


##### 3.1.1.2. `Chain`

The `Chain` receives `x` (`msg_hash` chunks) from `Decomposition`, computes rest of the chain if the `one_time_sig_i` of `i`-th chain is not yet the end, then sends the `one_time_pk_i` to `MerkleTree`.

We ignore the chain if it's already in the end, so the number of rows for a signature could be constant (equal to the target sum).

A sample trace with `x = (0, 2, 1, 3, 3, 0, ..., 1, 3, 3)` might look like:


##### 3.1.1.3. `MerkleTree`

The `MerkleTree` receives 2 things:

1. It receives `one_time_pk_i` where `x_i` is not yet end from `Chain`, and hashes them with `one_time_pk_i` where `x_i` is already end into `merkle_leaf_hash`, and then computes the `merkle_root` to be used latter.
2. It receives `(parameter, merkle_root, msg_hash)` as synchronization, where the `merkle_root` is computed from `merkle_leaf_hash` and `siblings`, `parameter` is used in all tweakable hashes, and `msg_hash` is computed separately in the next adjacent row.

A sample trace with `epoch = 0b0...01` might look like:


##### 3.1.1.4. `Decomposition`

The `Decomposition` receives `msg_hash` as `values`, and calculates <br> `(((values[4] * P) + values[3]) * P + ...) * P + values[0]`, then decompose it into base <code>2^w</code> chunks and send non-ending chunk to `Chain`.

A sample trace with `x = (0, 2, 1, 3, 3, 0, ..., 1, 3, 3)` might look like:


##### 3.1.1.5. `RangeCheck`

The `RangeCheck` is filled by range <code>0..2¹²</code> to receives `limb` from `Decomposition` as range check.

##### 3.1.1.6. Other gadgets used in the chips

See https://hackmd.io/@tcoratger/SyWbmVPckx for more details.

#### 3.1.2. Benchmark

- Machine spec
- CPU: i9-13900K
- RAM: 64GB (2x Crucial DDR5 5600 32GB Dual Channel)
- OS: Linux 5.15.0-124-generic x86-64
- FRI Parameter:
- Extension field bits: `124` (degree-4 extension of KoalaBear)
- Number of queries: `256 / R`
- Merkle tree hash: Poseidon2

The benchmark aggregates 8192 signatures, to reproduce please run the following script in `<repo>/circuit`:

sh bench.sh
python3 render_table.py

| `R` | `T` | `PT` | `TP` | `PS` | `PM` | `VT` |
| - | - | - | - | - | - | - |
| `1` | `4` | `5.33 s` | `1536` | `1.68 MB` | `5.76 GB` | `94.04 ms` |
| `1` | `8` | `3.00 s` | `2729` | `1.68 MB` | `5.78 GB` | `99.68 ms` |
| `1` | `16` | `2.65 s` | `3086` | `1.68 MB` | `5.17 GB` | `94.55 ms` |
| `1` | `24` | `2.19 s` | `3745` | `1.68 MB` | `5.93 GB` | `96.09 ms` |
| | | | | | | |
| `2` | `4` | `8.59 s` | `953` | `930.96 kB` | `8.91 GB` | `49.09 ms` |
| `2` | `8` | `4.98 s` | `1644` | `933.96 kB` | `8.81 GB` | `59.41 ms` |
| `2` | `16` | `4.24 s` | `1932` | `933.71 kB` | `8.97 GB` | `72.45 ms` |
| `2` | `24` | `3.36 s` | `2439` | `933.96 kB` | `12.48 GB` | `50.08 ms` |
| | | | | | | |
| `3` | `4` | `14.99 s` | `546` | `672.30 kB` | `16.07 GB` | `53.88 ms` |
| `3` | `8` | `8.75 s` | `936` | `671.24 kB` | `16.27 GB` | `35.08 ms` |
| `3` | `16` | `7.22 s` | `1134` | `670.96 kB` | `16.18 GB` | `40.86 ms` |
| `3` | `24` | `6.17 s` | `1327` | `671.02 kB` | `16.21 GB` | `34.79 ms` |

<small>`R`: Log 1/rate `T`: Threads `PT`: Proving time `TP`: Throughput (sig/s) `PS`: Proof size `PM`: Peak proving memory `VT`: Verifying time</small>