a16z’s Aerie Targets a Key Bottleneck in Post-Quantum Blockchain Design

a16z crypto researcher Justin Thaler and co-authors have introduced Aerie, a proof system designed to aggregate large batches of post-quantum digital signatures into a single proof.

In an October 16 thread on X, Thaler said Aerie aggregated 32,768 Falcon-512 signatures in 0.65 seconds on an Apple M4 Max laptop CPU. The research addresses a challenge for proof-of-stake blockchains exploring quantum-resistant cryptography: post-quantum signatures are generally larger than current signatures and cannot be aggregated using the same method as Ethereum’s BLS signatures.

The team published a research paper hosted by LayerZero Labs and released the implementation code on GitHub.

Post-quantum signatures pose an aggregation challenge

Proof-of-stake blockchains use digital signatures to verify validator participation. Ethereum aggregates validator BLS signatures into a single signature for each slot, reducing the data required to verify participation.

BLS signatures rely on elliptic-curve cryptography, which is considered vulnerable to sufficiently powerful quantum computers. Post-quantum signature schemes are designed to resist such attacks, but their larger signatures can increase bandwidth requirements and verification costs.

The paper identifies Falcon as one option for post-quantum blockchain applications. A Falcon-512 signature occupies 666 bytes, compared with approximately 64 bytes for the elliptic-curve signatures commonly used today.

Without an effective aggregation method, including large numbers of post-quantum signatures in blockchain blocks could increase data requirements and the costs of operating a node.

Aerie uses lattice-based proofs

Aerie combines Falcon signatures with a lattice-based proof system. This differs from approaches that use hash-based signatures and hash-based proofs, including the approach associated with Ethereum’s leanVM.

According to Thaler’s X thread, Aerie uses Akita, a lattice-based commitment scheme developed with LayerZero Labs, alongside sum-check proving techniques associated with Lattice Jolt.

Thaler said hash-based signatures can require hundreds of hash calculations to verify, making them expensive to prove within a zero-knowledge proof system. Falcon’s verification process involves less hashing, allowing Aerie’s verifier to calculate message hashes directly using a short salt attached to each signature.

According to the authors, this allows Aerie to prove the remaining algebraic checks without proving the hash computations. Unlike some alternative systems, Aerie does not use recursive proof merging.

Authors report faster proving in benchmarks

The paper reports that Aerie’s Falcon-512 aggregate measured approximately 42.1 bytes per signature, making it around 16 times smaller than the original signatures.

For Falcon-1024, a stronger parameter variant, the authors report aggregating 16,384 signatures in 0.63 seconds, with a 29-fold reduction in size.

The researchers also compared Aerie with Ethereum’s leanVM approach and Orthus, a previous Falcon signature aggregator. Their reported results include:

• Against leanVM: Aerie was approximately 29 times faster in the authors’ comparison involving XMSS-based consensus signatures and 60 times faster in a comparison involving stateless transaction signatures.
• Against Orthus: Aerie’s proving was 1.5 times faster, while verification was 38 times faster in the reported tests.

The authors said Orthus does not prove every requirement of the Falcon specification, including its byte-format rules. This qualification matters when interpreting the comparison.

The authors also said Aerie exceeded the 1,000-signatures-per-second target cited for Ethereum’s lean consensus effort. These results come from the researchers’ own tests and have not been independently reproduced. Performance comparisons depend on the hardware, configurations, and workloads used.

Proof merging and memory remain limitations

Aerie’s design has trade-offs. Its prover must hold all signatures in a batch, and separate Aerie proofs cannot currently be merged. This limits its use in networks that collect signatures across multiple machines.

Recursive systems such as leanVM can distribute work across machines and combine proofs into a final proof. The paper reports that Aerie’s verification takes approximately 54 milliseconds on one CPU core, compared with about 6 milliseconds for leanVM in the authors’ comparison.

Proving a batch of 32,768 signatures required approximately 2.1 GiB of peak memory. The short public salts account for most of the aggregate’s size. According to the paper, using one shared salt could reduce the aggregate from approximately 1.3 MiB to 66 KiB, but that approach relies on an additional security assumption the authors have not proved.

These constraints mean that proving speed alone does not establish whether Aerie is suitable for replacing existing aggregation systems in blockchain consensus.

What does Aerie mean for Ethereum’s quantum security?

Ethereum’s long-term roadmap includes replacing cryptographic components that could become vulnerable to future quantum computers. One approach under development uses hash-based signatures and leanVM, a zero-knowledge virtual machine designed to help aggregate those signatures efficiently.

However, the a16z researchers argue that relying exclusively on hash-based cryptography could introduce additional computational costs and technical complexity.

Thaler argued that lattice-based cryptography should remain under consideration as blockchains develop post-quantum systems. He said lattice-based proofs could reduce reliance on recursive proofs and custom hash-based signatures. He also argued that these design considerations should be weighed against the possibility of future attacks on established lattice assumptions.

The researcher referred to the Ethereum Foundation’s strawmap, which includes a hash-based layer-one approach and plans for native private transfers. He argued that public-key encryption for private transfers cannot be built from hash functions alone, so avoiding lattices in signatures and proofs would not eliminate every potential reliance on lattice cryptography.

Bitcoin proposal explores 96-byte post-quantum transactions

A separate proposal covered by The Crypto Times on October 14 explores how Bitcoin transactions could use post-quantum cryptography while limiting the amount of data stored on-chain. The proposal uses a mechanism called a degriefer to distinguish legitimate transactions from conflicting spends. Its stated goal is to reduce on-chain data storage, with a proposed transaction size of 96 bytes.

Unlike the Bitcoin proposal, which focuses on the size of individual transactions, Aerie aggregates batches of signatures into a single proof.

Paper discloses AI use and security assumptions

The authors said Aerie’s security relies on Falcon and Module-SIS, a lattice-based computational problem. They also reported that part of the system’s soundness proof was checked using the Lean 4 theorem prover.

The paper discloses that AI models from OpenAI and Anthropic assisted with implementation, benchmarking, protocol development, and security proofs. The authors said they take responsibility for the paper’s accuracy. It also discloses that Thaler is an investor in blockchain-based platforms through a16z.

Falcon is being standardized by the U.S. National Institute of Standards and Technology as FN-DSA. Changes to the final standard could affect aspects of Aerie’s design, including message hashing.

The authors identify GPU acceleration, smaller aggregates through hidden salts, and proof merging as areas for further research. Further evaluation will be needed to assess Aerie’s suitability for distributed blockchain consensus.

Also Read: Aztec Sets 2030 Target for Full Post-Quantum Blockchain Migration