Hash-based Signature Aggregation

• Hash-based Signature Aggregation
  • 1. Hash-based Signature Parameter
  • 2. Approach - zkVM
    • 2.1. With succinctlabs/sp1 (based on plonky3)
    • 2.2. With openvm-org/openvm (based on plonky3)
  • 3. Approach - Circuit
    • 3.1. With plonky3

1. Hash-based Signature Parameter

We use Poseidon2 instantiation with the following parameter:

• $\mathbf{\text{Lifetime}}L=2^{20}$
• $\mathbf{\text{Encoding}}=\mathsf{TSW}$
• $w=2$
• $\delta =1$

The implementation of this specific instantiation could be found here.

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
(((values[4] * P) + values[3]) * P + ...) * P + values[0], then decompose it into base 2w 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 0..212 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

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.10 s	1607.76	1.68 MB	6.96 GB	106.29 ms
1	8	3.04 s	2693.43	1.68 MB	7.14 GB	97.61 ms
1	16	2.56 s	3200.80	1.68 MB	7.17 GB	94.19 ms
1	24	1.87 s	4377.18	1.68 MB	6.82 GB	86.38 ms
2	4	7.73 s	1059.11	932.94 kB	10.16 GB	50.58 ms
2	8	4.46 s	1836.99	932.94 kB	10.66 GB	49.80 ms
2	16	3.67 s	2230.50	932.94 kB	10.25 GB	62.66 ms
2	24	2.95 s	2774.11	932.94 kB	10.81 GB	43.62 ms
3	4	12.94 s	632.99	670.54 kB	18.32 GB	42.56 ms
3	8	7.45 s	1099.65	670.54 kB	18.35 GB	44.90 ms
3	16	5.71 s	1433.46	670.54 kB	18.37 GB	30.09 ms
3	24	4.92 s	1666.33	670.54 kB	20.16 GB	30.44 ms

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