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
  • 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

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