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:

• \(\textbf{Lifetime}\ L = 2^{20}\)
• \(\textbf{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: Log 1/rate T: Threads PT: Proving time TP: Throughput (sig/s) PS: Proof size PM: Peak proving memory VT: Verifying time