lean Ethereum Part 2: PQ Signatures and Poseidon with Dmitry and Benedikt

In this episode of "Zero Knowledge," Anna Rose hosts Benedict Wagner and Dmitri Korvatovich from the Ethereum Foundation, focusing on Lean Ethereum and post-quantum signatures, particularly LeanSig. They discuss LeanSig as a hash-based multi-signature scheme intended to replace BLS signatures, which are vulnerable to quantum attacks. The researchers highlight the security trade-offs and encoding challenges of LeanSig, as well as the ongoing cryptanalysis of Poseidon, the hash function integral to LeanSig's design.

LeanSig aims to create digital signatures from one-way functions, utilizing a one-time signature scheme where a secret key is used only once. The proposed scheme is designed for Ethereum's consensus mechanism, allowing for a single signature per slot, with a maximum of 2^32 signatures, sufficient for hundreds of years. They explore trade-offs between signature size and performance, noting that longer hash chains yield smaller signatures but require more computation.

The conversation introduces multi-signature schemes, which aggregate signatures into shorter certificates. While BLS is noted for its aggregation capabilities, no current post-quantum scheme matches its features. The researchers discuss using a generic snark to aggregate any signature scheme, emphasizing the importance of expressing the verifier as a circuit to enhance proving performance and efficiency.

Dmitri and Benedikt also discuss the "Watts" signature scheme, which sets parameters for security based on hash functions, and their efforts to create smaller, faster-to-verify signatures. They mention a new paper titled "Aborting Random Oracles," which presents a cryptographic model for analyzing encodings and addresses challenges with big integer arithmetic. The encoding maps messages and random salts to hash chain positions, requiring optimization for generic snark implementation.

Concerns about hash functions with smaller outputs are raised, as they could compromise security and increase collision risks. The need for tighter security analysis is emphasized, particularly for multi-signatures and the challenges of circuits performing random oracle calls. Transitioning to Poseidon, the speakers discuss its two versions and the ongoing analysis of a modified version for small prime fields. The Poseidon Initiative aims to engage global cryptanalysts to assess its security, with upcoming workshops focusing on specific properties relevant in snark contexts.

Finally, they touch on the paper "The Billion Dollar Merkle Tree," which relates to generic snarks and CKVMs in Ethereum layer one, highlighting the need for formal verification of security. Throughout the discussion, both guests express appreciation for the opportunity to share their insights on enhancing security and efficiency within the Ethereum ecosystem.