TL;DR
At the L* milestone, BLS keys are retired. The current randao_reveal mechanism fails entirely. This post proposes the minimal, hash-based fix: a PRF-commitment VRF derived from the leanSig seed, proved with a standalone WHIR proof included in the BeaconBlockBody. The construction activates at I*, so RANDAO gains quantum resistance before L* rather than at it.
A reference implementation is at GitHub - aryaethn/leanEthereumPostQuantumVRF: Forked repo from "Minimal zkVM, targeting aggregation of hash-based signatures," to create a PQ VRF on top of it. · GitHub.
A companion paper is attached pq_vrf_ethereum.pdf (657.8 KB).
Pinging the EF PQ team for review: @JustinDrake @Khovratovich @benedikt-wagner @will-corcoran.
1. The Problem
EIP-7998 (co-authored by @aryaethn and @71104) strengthens RANDAO by requiring the block proposer to produce a BLS VRF output and proof each slot. This eliminates the last-revealer attack and enables Single Secret Leader Election.
At milestone L*, BLS keys are phased out and replaced with leanSig (XMSS-based) keys. At that point, EIP-7998 is cryptographically broken: there is no BLS key left to sign with, and no mechanism to replace the randao_reveal. No existing EIP addresses this gap.
Beyond L*, there is an immediate problem: BLS public keys are already on-chain. A cryptographically relevant quantum computer (CRQC) can recover any validator’s BLS private key from their registered public key using Shor’s algorithm, and use it to bias RANDAO from today. The hybrid I*-to-L* period, during which BLS keys remain live alongside newly registered leanSig keys, is the most dangerous window.
This EIP is not an optional enhancement to EIP-7998. It is a required migration. The question is only what it should look like and when it should activate.
2. Why This Construction
Before describing the proposal, it is worth explaining why the natural approaches do not work.
X-VRF (ESORICS 2022) is broken. The X-VRF construction treats XMSS/WOTS+ as a unique signature scheme and derives VRF uniqueness from that. FC 2024 showed that WOTS+ is not a unique signature scheme in the relevant sense: the chain structure admits multiple valid signatures for a given message. Any construction that inherits uniqueness from WOTS+ uniqueness is broken at the foundation.
Using leanSig directly for RANDAO does not give a VRF. A leanSig signature on (slot, prev_epoch_randao_mix) gives a proof of knowledge of the signing key, but not uniqueness of the output. The WOTS+ chain extension means a different leaf index, or a different chain traversal, can produce a different signature on the same message. Uniqueness of the RANDAO contribution cannot be derived from this.
The correct approach: PRF-commitment VRF. The proposer derives a VRF secret key vrf_sk from their leanSig seed via a domain-separated hash, then computes the VRF output as y = H(vrf_sk, x) for the slot’s VRF input x. Uniqueness holds from collision resistance of H, not from any signature-uniqueness property. The VRF proof is a zero-knowledge argument that y was computed honestly.
This approach is clean, correct by construction, and avoids the X-VRF flaw entirely.
3. The Construction
All hash calls use poseidon16_compress over the KoalaBear field (p = 2^31 - 2^24 + 1 = 2,130,706,433), with S-box degree 3 (Davies-Meyer, 8 full rounds, 20 partial rounds, output 8 field elements). Parameters are confirmed from leanMultisig source at commit 5a5e10dd.
3.1 Key Derivation
leanSig_seed uniform random 32 bytes
vrf_sk = compress([seed_fe[0..11], DOMAIN_VRF_DERIVE, 0, 0, 0, 0]) in F_p^8
pk_vrf = compress([vrf_sk[0..8], DOMAIN_VRF_PK, 0, 0, 0, 0, 0, 0, 0]) in F_p^8
seed_fe[0..11] is the leanSig seed encoded as 11 KoalaBear field elements using 3-bytes-per-element little-endian packing. DOMAIN_VRF_DERIVE = p - 3. No separate VRF key registration ceremony is needed: pk_vrf is derived deterministically from the leanSig seed already being registered at I*.
3.2 VRF Evaluation
For a given slot s and previous epoch RANDAO mix r:
x = encode(s, r) 15 field elements: [DOMAIN_VRF_INPUT, slot_fe[3], mix_fe[11]]
m = compress([x[0..15], DOMAIN_VRF_EVAL]) in F_p^8 (inner hash)
y = compress([vrf_sk[0..8], m[0..8]]) in F_p^8 (VRF output)
Domain separation constants (all exceed 2^24, so they cannot appear in 3-byte-packed input data):
| Constant | Value |
|---|---|
DOMAIN_VRF_INPUT |
p - 1 = 2,130,706,432 |
DOMAIN_VRF_PK |
p - 2 = 2,130,706,431 |
DOMAIN_VRF_DERIVE |
p - 3 = 2,130,706,430 |
DOMAIN_VRF_EVAL |
p - 4 = 2,130,706,429 |
Domain tag collision against leanSig internal tweaks (0x00, 0x01, 0x02) and leanMultisig SNARK domain separation (max element 2,063,844,858) has been checked and confirmed clear. Full analysis in crates/vrf/FINDINGS.md §0e.
3.3 VRF Proof
The proof pi is a WHIR proof (using the same lean_prover::prove_execution infrastructure as XMSS attestation aggregation) for the relation:
R = { (pk_vrf, slot, r, y ; vrf_sk) :
compress([vrf_sk, DOMAIN_VRF_PK, 0^7]) = pk_vrf
AND
compress([vrf_sk, compress([encode(slot, r), DOMAIN_VRF_EVAL])]) = y }
The circuit makes 3 poseidon16_compress calls with a shared 8-element private witness vrf_sk. The public statement is 31 field elements: pk_vrf[8] || encode(slot, r)[15] || y[8].
This is a standalone WHIR proof in the BeaconBlockBody, verified synchronously during process_randao. It is not embedded in the post-slot leanMultisig attestation aggregate.
3.4 Verification
def pq_vrf_verify(pk_vrf, slot, randao_mix, y, proof):
x = encode_vrf_input(slot, randao_mix) # 15 field elements
public_input = list(pk_vrf) + list(x) + list(y) # 31 field elements
return lean_prover.verify_execution(VRF_BYTECODE, public_input, proof)
4. Protocol Changes
4.1 Three-Phase process_randao
The transition is activated at I*, not L*, so RANDAO gains quantum resistance during the hybrid window.
Phase 0 (before I):* EIP-7998 unchanged.
Phase 1 (I to L, hybrid):**
def process_randao(state, body):
epoch = get_current_epoch(state)
proposer = state.validators[get_beacon_proposer_index(state)]
# EIP-7998 BLS path (unchanged until L*)
randao_data = RandaoRevealData(
slot=state.slot,
prev_epoch_randao_mix=get_randao_mix(state, epoch - 1)
)
assert bls.Verify(proposer.bls_pubkey,
compute_signing_root(randao_data, DOMAIN_RANDAO),
body.randao_reveal)
bls_contribution = hash(body.randao_reveal)
# PQ VRF path (this EIP, active from I*)
x = encode_vrf_input(state.slot, get_randao_mix(state, epoch - 1))
assert pq_vrf_verify(proposer.pk_vrf, x, body.pq_vrf_output, body.pq_vrf_proof)
pq_contribution = serialize_field_elements(body.pq_vrf_output) # 32 bytes
# XOR both contributions
mix = xor(get_randao_mix(state, epoch),
xor(bls_contribution, pq_contribution))
state.randao_mixes[epoch % EPOCHS_PER_HISTORICAL_VECTOR] = mix
Phase 2 (L onwards, PQ only):*
def process_randao(state, body):
epoch = get_current_epoch(state)
proposer = state.validators[get_beacon_proposer_index(state)]
x = encode_vrf_input(state.slot, get_randao_mix(state, epoch - 1))
assert pq_vrf_verify(proposer.pk_vrf, x, body.pq_vrf_output, body.pq_vrf_proof)
mix = xor(get_randao_mix(state, epoch),
serialize_field_elements(body.pq_vrf_output))
state.randao_mixes[epoch % EPOCHS_PER_HISTORICAL_VECTOR] = mix
The security argument for the hybrid phase: the XOR of a pseudorandom value with any other value is pseudorandom. If either VRF is secure, the combined RANDAO mix is pseudorandom. A CRQC that recovers a validator’s BLS key can bias the BLS contribution but cannot control the PQ contribution. RANDAO is therefore quantum-resistant from I* onwards.
4.2 Beacon Chain Modifications
BeaconBlockBody gains two new fields from I*:
pq_vrf_output: Bytes32(the 8-element field vectory, serialized little-endian)pq_vrf_proof: VRFProof(the serialized WHIR proof, ~116 KB)
Both fields are mandatory from I*. A block missing either field is invalid. Clients must upgrade before the I* activation epoch.
At L*, randao_reveal is removed from BeaconBlockBody.
Validator record gains one field at I*:
pk_vrf: Bytes32(the 8-element key commitmentcompress([vrf_sk, DOMAIN_VRF_PK, 0^7]), serialized)
Validators compute and register pk_vrf as part of the I* leanSig key registration. No additional ceremony is required.
4.3 Relationship to EIP-7998
This EIP is compatible with EIP-7998 from I* to L*. Both mechanisms run in parallel and their outputs are XOR’d into the RANDAO mix. At L*, this EIP supersedes EIP-7998. The EIP header will declare: “Supersedes EIP-7998 at milestone L*. Compatible with EIP-7998 from I* to L*.”
5. Security Properties
The security argument has four components. I state each with its model and assumptions explicitly.
5.1 Correctness
Unconditional, from WHIR completeness. An honest prover with a valid witness always produces a proof the honest verifier accepts.
5.2 Computational Uniqueness (ROM)
Claim: No PPT adversary can find (pk_vrf, x, y, pi, y', pi') with y != y' such that both proofs verify.
Proof sketch: Apply the WHIR knowledge extractor (which exists in the ROM under Fiat-Shamir) to extract vrf_sk from pi and vrf_sk' from pi'. If vrf_sk = vrf_sk', then y = compress([vrf_sk, m]) = y', contradicting y != y'. If vrf_sk != vrf_sk', then compress([vrf_sk, DOMAIN_VRF_PK, ...]) = compress([vrf_sk', DOMAIN_VRF_PK, ...]) = pk_vrf is a collision in poseidon16_compress. This breaks Poseidon1 collision resistance.
The construction avoids the X-VRF flaw (FC 2024) by design: uniqueness reduces to collision resistance of the hash function, not to any WOTS+ chain-uniqueness property.
5.3 Pseudorandomness (QROM)
Claim: No QPT adversary with quantum oracle access to H can distinguish y = H(vrf_sk, m) from a uniformly random value, given pk_vrf, VRF evaluations at other inputs, and their proofs.
Model: QROM. Assumption: Poseidon1 is a quantum random oracle.
Proof sketch: This is a direct application of Zhandry’s quantum PRF theorem (FOCS 2012, Theorem 3.1). Define F_k(m) = H(k, m). If H is a quantum random oracle and k = vrf_sk is effectively uniform (which it is, as the output of H applied to a fresh input in the QROM), then F_k is a quantum-secure PRF. The adversary is given one additional evaluation pk_vrf = H(vrf_sk, DOMAIN_VRF_PK), which is domain-separated from all VRF inputs. By Zhandry’s QPRF security, the value at any unqueried input is indistinguishable from uniform.
The 8-element secret key vrf_sk provides approximately 124 bits of quantum security (8 x 31-bit field elements, matching leanMultisig’s security level). The QPRF advantage bound is O(q^2 / 2^{124}) for a QPT adversary making q quantum queries, which is negligible for any realistic query budget.
This is the strongest result in this EIP. It holds even if the QROM soundness of the WHIR proof system is never formally established. A quantum adversary cannot bias RANDAO by forging a VRF output – they would need to break Poseidon1 one-wayness in the QROM.
5.4 Proof Soundness (ROM)
Claim: No PPT adversary can produce a verifying (pk_vrf, x, y, pi) where y is not the correct PRF output for vrf_sk.
Model: ROM. Assumption: WHIR soundness via Fiat-Shamir applied to the WHIR IOP.
Proof sketch: By the Fiat-Shamir theorem for public-coin IOPs, the non-interactive WHIR argument is sound in the ROM. A verifying proof for an incorrect y would break WHIR soundness.
QROM gap: Fiat-Shamir applied to WHIR has not been formally analyzed in the QROM. This mirrors leanMultisig’s own position on their attestation aggregation proofs. Importantly, the gap affects only proof soundness, not pseudorandomness – these properties are independent. A quantum adversary who exploits the gap to forge a proof for an incorrect y' still cannot make y' predictable or biased: it would be pseudorandom under the QPRF argument regardless. Closing the QROM gap formally is the primary target for the companion paper.
Summary
| Property | Model | Assumption | Status |
|---|---|---|---|
| Correctness | Unconditional | WHIR completeness | Established |
| Uniqueness | ROM | WHIR knowledge soundness + Poseidon1 collision resistance | Established (sketch) |
| Pseudorandomness | QROM | Poseidon1 as QROM (Zhandry 2012) | Established (sketch) |
| Proof soundness | ROM | WHIR + Fiat-Shamir | Established (sketch) |
| Proof soundness | QROM | WHIR QROM Fiat-Shamir | Open problem |
6. Benchmarks
Measured on MacBook Air (Apple M2, 8 cores, 8 GB RAM), Rust 1.88.0, release profile, target-cpu=native.
WHIR configuration: log_inv_rate = 2 (rate 1/4), approximately 124-bit security.
| Operation | Time (median) | Notes |
|---|---|---|
vrf_eval |
3.71 µs | PRF evaluation only (2x poseidon16_compress) |
vrf_prove |
81.4 ms | Full WHIR proof generation |
vrf_verify |
19.2 ms | Proof verification |
| Proof size | 116 KB | Serialized via postcard |
For comparison, the BLS-based EIP-7998 baseline is approximately 1 ms prove/verify and 96 bytes proof size. The 116 KB proof and 81 ms prover cost are the cost of post-quantum soundness.
Proposer cost: vrf_prove runs once per slot. On a 12-second slot, 81 ms is negligible.
Node cost: vrf_verify at 19.2 ms per block is the same order as BLS aggregate verification and well within the processing budget.
Proof size: 116 KB is larger than the initial estimate of 10-50 KB. This is the honest number, measured on the actual implementation. The proof contains WHIR polynomial commitments and IOP transcripts and does not grow with the number of validators. It is within the beacon block’s size budget.
The 116 KB is a standalone proof for 3 poseidon16_compress calls. For reference, leanMultisig aggregates approximately 1,400 XMSS signatures into a proof of 130-355 KB at the same WHIR rate – the VRF proof is a similar size for a dramatically simpler circuit.
7. Four Reasons This Is the Right Fix
1. Necessary. At L*, BLS keys are retired. The current randao_reveal fails entirely. There is no fallback. This EIP is not an optional VRF enhancement; it is a required migration before L* activates.
2. Cheap. The VRF circuit is 3 poseidon16_compress calls over the KoalaBear field – the same primitive already running inside the leanMultisig attestation aggregation circuit. No new precompile is needed. No new proof system is introduced. The leanMultisig aggregation circuit is unchanged. The validator key management burden is one additional 32-byte field in the validator record, derived deterministically from the leanSig seed already being registered.
3. Stronger than the BLS status quo. Uniqueness in EIP-7998 rests on the computational Diffie-Hellman assumption over BLS12-381. In this construction, uniqueness rests on Poseidon1 collision resistance, which is a more direct and better-understood assumption for a hash-based VRF. Pseudorandomness is established in the QROM, which EIP-7998 cannot claim at all. The X-VRF uniqueness flaw (FC 2024) is avoided by design.
4. Quantum resistance earlier. BLS public keys are already on-chain. A CRQC can recover BLS private keys from registered public keys today. From I* onwards, the PQ VRF contribution XOR’d into the RANDAO mix is quantum-resistant. A CRQC that recovers every validator’s BLS key can bias the BLS contribution but cannot predict or control the Poseidon-based contribution. RANDAO is quantum-resistant from I*, not from L*.
8. Open Questions
Two items remain open and are the primary targets for the companion paper and community feedback:
QROM proof soundness. Establishing Fiat-Shamir + WHIR soundness in the QROM with concrete security bounds. This mirrors the open problem in leanMultisig’s own security analysis.
Concrete pseudorandomness bounds. The Zhandry QPRF bound for our specific parameters (31-bit field elements, 8-element key, realistic Ethereum query budgets). The bound is comfortable at the 124-bit security level, but a concrete analysis with exact constants would strengthen the security argument.
9. What I Am Asking For
This is a pre-EIP discussion post. The EIP PR will be opened after community feedback. Specifically, I am looking for review on:
-
The security argument – is the QROM pseudorandomness claim (Section 5.3, Zhandry QPRF) being applied correctly? Is the ROM uniqueness reduction (Section 5.2) complete?
-
The leanMultisig circuit interface – is
prove_executionwith a 3-compress zkDSL program the correct way to integrate the VRF into the leanVM, or should this be expressed differently? -
The domain separation tags – is the use of
p - 1,p - 2,p - 3,p - 4as VRF domain constants compatible with leanSig and leanSpec’s internal conventions? -
The transition mechanics – is the three-phase
process_randao(hybrid XOR from I*, PQ-only from L*) the right approach, or is there a cleaner way to handle the I*-to-L* window? -
Proof size. 116 KB is the honest number from the implementation. Is this within the beacon chain’s block budget, or does it require a change to block size parameters?
The reference implementation, including tests, benchmarks, and the FINDINGS.md parameter derivation, is at [YOUR GITHUB LINK].
The companion paper (security proofs and formal bounds) is attached: [PAPER TITLE / LINK].
Looking forward to the discussion.