Special thanks to Emile, Potuz, Anders Elowsson for initial feedback and review.
The goal of this post will be to show how the Ethereum consensus chain, in the context of “Lean” upgrades (single-slot finality, recursive-STARK-based quantum-resistant signature aggregation…) can be designed to aggressively minimize state requirements, by pushing responsibility to stakers to manage and occasionally ZK-prove their state. This removes the burdens of “end-of-epoch processing” (which in few-slot finality may need to happen eg. every 16 seconds), and may allow consensus to scale to millions of validators if needed. Advanced versions of this also give you validator re-anonymization “for free”.
State accounting in the “status quo” chain
Beacon chain state currently includes the following, for each validator:
| Field | Size |
|---|---|
| Pubkey | 48 bytes |
| Withdrawal credentials | 32 bytes |
| Effective balance | 1 byte |
| Slashed? | 1 bit |
| Epoch numbers for various phases (activation eligibility, activation, exit, withdrawable) | 8 × 4 bytes |
| Active balance | 8 bytes |
Beacon chain state changes, per epoch, are a very expensive operation. Almost all have to do with changes to active balance resulting from validators participating or not participating.
Phase 1A: eliding the pubkey tree
One major benefit of STARK-based aggregation is that we have much more freedom in what the internal logic of the signatures and aggregation method is. We already intend to use this for aggregation, with the result that bitfield-merge aggregation will be possible. But we can also use this for signatures, to remove validator pubkeys from state.
Notice that when a validator deposits, their pubkey is stored in a fixed location in the deposit tree. Furthermore, no one is required to store the deposit tree: the deposit contract only stores the right-side branch, which is all you need to append the next value:
Instead of storing a validator’s pubkey (48 bytes) in the beacon chain state, we simply store their index in the deposit tree (5 bytes). The base signature algorithm (leanWOTS) is adjusted so that the pubkey is included in the signature along with the Merkle proof through the deposit tree, and the signature verification function treats the index as a pubkey and takes a recent (eg. start-of-current-day) root of the deposit tree as an auxiliary public input.
The validator would be required to track an updated Merkle proof of their deposit to be able to continue signing. This is easy to do if the validator has the right-side branch at the time their deposit was included, and they process the chain and adjust the branch every time there is a deposit since then.
When a validator deposits, the withdrawal credentials are beside the pubkey, and so we can just use the same proof to withdraw (and hence do not need to store withdrawal credentials in the beacon chain state).
Phase 1B: ZK-proving balances
We remove all logic related to reward and penalty processing from the beacon chain state transition function. Attestations are simply included into blocks if their validity checks out (with a STARK), and in real time no processing happens at all.
At the end of each day, a validator is required to generate a STARK that walks through the chain since the previous day, provides Merkle branches of their index in each attestation bitfield that was included onchain, uses this to determine how many times they did and did not participate, and computes their new balance. They submit this STARK into the protocol. This updates the validator’s balance, which remains effective for the next day.
For practicality, we need one clarification to the above design: the effective balance for the period [T, T + 1 day] needs to get compute only based on blocks up to T - 0.5 days. This gives the validators half a day of time to get their proofs included without their ability to participate being interrupted. It also ensures that the proof publications can be spread throughout half a day, avoiding periods of sudden congestion (assuming validators randomize their branch publishing times somewhat; if needed, we can force this by assigning staggered minimum publishing times, eg. T_min(validator) = global_T_min + (1/4 day) * validator.pubkey_hash / 2**256).
Notes
-
If a validator is late submitting their balance update proof, they do not get slashed or kicked out. Rather, they can still submit at any time. The validator’s only loss is that they will not be able to attest until they submit their balance update proof.
-
We only need to prove Merkle branches of participation, not non-participation.
-
For now slashing happens outside this STARK mechanism, to allow it to take effect instantly.
-
We also adjust how exits work. You exit by submitting an “I want to exit” STARK in place of your next day’s balance update STARK. You partially withdraw by adding a “I want to partially withdraw” message to your next day’s balance update STARK.
-
We require each attestation (bitfield) to point to either the previous attestation for the same block, or the block itself, and include it in its STARK merge. Hence, each attestation’s bitfield is the most up-to-date bitfield for the object it’s applying to, OR’ing together any previous attestations and the new ones.
-
The proposer must prove a “total effective balance” for any objects in attestations included in their block, so that blocks can be justified, notarized, finalized, etc. if needed.
-
We can also slightly adjust how effective balances work to optimize. Use an fp8 format without a sign bit (eg. 3 bits exponent, 5 bits mantissa, lowest value 16 covers 16…4032 ETH) to make it roughly equally lossy at different balances. We overload this value, representing
slashedas 0 effective balance (we track total balance separately, and do not subtract slashed balance from there). -
The maximum daily loss in an inactivity leak is roughly the same as the granularity level of effective balance, so there is no large degradation of the inactivity leak mechanism from this. Also, if we redesign effective balance, we may as well add hysteresis.
New accounting
Per-validator state is:
| Field | Size |
|---|---|
| Effective balance | 1 byte |
| Pubkey index | 5 bytes |
Everything else does not need to be stored. Each balance update proof connects to the validator’s previous onchain balance update proof, so lower-order digits of their balance get threaded through the proof without entering the effective balance. We do not need to track deposit epoch, exit epoch, etc, because that tracking gets subsumed into the balance update proof mechanism.
Note that a validator’s N-1’th balance update proof is a deterministic function of (i) their N-2’th balance update proof, (ii) onchain data since then. This means that recovery from a fixed backup seed is still feasible.
State updates are:
- One write per slashing
- One write per validator per day
Cost of proving
To make a balance update proof, the validator needs to prove at most one Merkle branch per object (the latest attestation of that object) since the previous day. “Object” here means block; almost always there is at most one block per finality slot.
With day-long periods and 16s epochs, this means ~5400 Merkle branches. With STARKs (much cheaper to prove than SNARKs), this is doable well within an hour even on weak hardware. In case of a fork, attestations for one side of the fork only get included on that side, and so each validator will only need to prove branches for the side of the fork they are participating in; the proof to keep updated on other sides of the fork will be much cheaper.
The cost of proving total effective balance is higher because it walks over an entire bitfield and over the whole set of effective balances (note: to optimize, the pubkey indices and effective balances should be stored in separate trees, so that the proof need only walk over the latter, one byte per validator).
The non-hashing part of this is “just” a subset-sum, so the cost will be dominated by Merkle-treeing the bitfield (128 kB per million validators) and the effective balance tree (1 MB per million validators). Today, high-end laptops can prove over 500k hashes/sec (ie. prove Merkle-treeing 16 MB/sec), so this is not a problem; even lower-end laptops should be able to handle this.
Onchain, this mechanism assumes one STARK per validator per day. At 1 million validators, this would be >100 STARKs per slot, which is too much. Hence, these proofs also need to be aggregated, just like signatures are aggregated.
This is already a highly effective and optimized design. The next step is that we will add privacy.
Phase 2: Privacy
We make several major adjustments to the beacon chain design.
First, the “active validator registry” becomes a separate structure per day. There is no concept of long-term validator index. From the system’s point of view, validators appear de-novo each day, declaring and proving their effective balance, and they are all active. In particular, note that any committee assignment must come from the current day’s pubkey.
Second, we move pubkey registration to the balance proving step. Each validator provides a fresh pubkey each day. This also means that the concept of a pubkey index can be removed, since the index is just that validator’s position in that day’s tree.
Third, we assume a form of BFT consensus where validators send a message per-round. There are no “surround slashings”.
We also adjust the claim that is being proven in the balance update proof. The validator is proving over:chain of previous N onchain registrations, back to either a deposit or a registration more than [weak subjectivity period] days old.
- Its previous onchain registration (maybe a deposit)
- All attestations that have happened onchain since then
- All slashings that have happened onchain since then
We require slashings in a block to be in order of pubkey, to enable merkle-branch-sized proofs, so the overhead of scanning slashings is at most the same as the overhead of scanning attestations (and normally, blocks have zero slashings).
Additionally, make sure that the STARK being used is a ZK-STARK.
We also make partial withdrawals a separate ZK-STARK, to avoid attaching the exact excess balance (which a partial withdrawal inevitably leaks, but effective balance does not leak because it is coarse-grained) to the next day’s key and hence linking the next day’s key to the previous day’s key.
We also need to do one of the following to enable slashing previous pubkeys:
- Require pubkeys to be deterministically generated from a seed fixed at deposit time; this allows the proof to generate the pubkeys from the previous
[weak subjectivity period]days and check for slashings among all of them. - Require the proof to walk through previous slashings onchain up to
[weak subjectivity period]days ago.
The former is simpler and cheaper. The latter is more intensive and more complex, but it has two advantages:
- It enables key rotation without a withdraw-and-deposit loop
- It allows validators to delete keys older than
[weak subjectivity period](except the withdrawal credential), increasing privacy in exceptional cases where devices get compromised, though note that actually doing this comes at the cost of complicating the backup procedure.
Slashings on the currently-active pubkey apply instantly (by setting effective balance to zero), slashings on previous pubkeys apply only after a day of delay.
This gives us fairly strong validator anonymity: each validator identity completely re-randomizes each day, only the validator themselves knows the link between their present and past identities, and re-proves over this link only to reveal two items of information: (i) their balance changes since the last proof, (ii) whether or not they have been slashed.
Finally, make sure that deposits don’t publish the withdrawal address in the clear; instead, they make a hiding commitment hash(withdrawal_address, secret). Only someone who knows the withdrawal address and the secret will be able to make a withdrawal. The daily proof must thus also prove that a withdrawal has not taken place (this requires the state to have a daily accumulator of withdrawal events). This does expose the withdrawal address (which is unavoidable, as it’s an in-the-clear ETH transfer on the execution layer side), but this does not leak anything publicly beyond “this address now received X ETH” - the withdrawal address is never publicly linked to a deposit or any onchain activity.
SSLE
The machinery introduced by this post in some sense gives you single secret leader election (SSLE) almost “for free”. The concept of a publicly tracked permanent validator set ceases to exist, so the only place to select proposers is the re-anonymized daily validator set. Indeed, if a validator does not attest until they propose, this already satisfies the core properties of SSLE. The design can be extended to also provide SSLE properties even if a validator does attest before they propose.
Choice of period length
Most of the cost of making a proof is amortized - it’s “walking over the chain” from the previous checkpoint to the current checkpoint, so above a very low threshold, it’s equally expensive no matter the period length.
The main onchain cost is that a balance update proof requires a 32 byte commitment onchain. This is 256 times more expensive than an attestation (1 bit). Hence, if we want the cost to not more than double, the minimum balance update period is 256 finality periods. If a finality period is 16 sec, this implies a balance update period of 4096 sec (~1.1 hours). Such very aggressive parameters would also require updates to be staggered throughout the entire period and not just in a 1/4 long range as the above post suggested, somewhat increasing the latency of updates.
Hence, 1 hour is the lower limit, and 1 day is conservative.
Longer periods reduce the effectiveness of validator anonymity.