While working on the piece that describes attestations in Ethereum I wrote the entire write-up with a wrong assumptions that all attestations are used, not just the largest-slot-number from each attester. In that understanding I also didn’t use the concept of skip-blocks at all.
After Justin confirming the proper fork choice rule and the skip-blocks I rewrote the write-up, but I think my old understanding still provides a rather legitimate fork choice rule, so I’m keeping it here for history.
Later Vitalik mentioned that it was the original intent to use all attestations from an attester and not just the latest one, such an approach is called IMD. It has slightly better forkfulness properties, but has some other drawback, e.g. the last post here.
Each time slot has a particular validator who is assigned to create a block at that time slot. Such a validator is called a proposer. Each other validator in the committee is encourated to “attest” to the block by signing it. The signatures are accumulated using BLS signatures aggregation, which prevents the block size from exploding with the number of attesters.
Fork choice rule
To get the selected chain, one starts at the genesis block, and at each step if there’s a fork chooses the block that has the most unique attesters attesting to either that block, or any block in that block’s branch.
Consider the example above. Letters in each block indicate the names of the attesters on the block. There’s a fork early on, and Alice (A), Bob (B), Carol ©, Dave (D), Elaine (E) have attested to some blocks in the lower branch, while Victor (V), Xavier (X), Yasmine (Y) and Zach (Z) have attested to some blocks in the upper branch.
To find out the selected chain, one starts at the genesis block (slot 1) and moves to the right. At the block in slot 2 the participant has to choose between the upper branch and the lower branch. The fork choice says that the branch with more unique attesters across all the blocks in the branch shall be selected. The lower branch has five unique attesters (Alice, Bob, Carol, Dave and Elaine), while the upper branch only has four (Victor, Xavier, Yasmine and Zach), so the lower branch is chosen. Note that there’s no actual chain in the lower branch that has five attesters attesting to the blocks in it, moreover there’s no chain in the lower branch that has even four unique attesters attesting the blocks in it (the chain that ends in the block at slot 7 has only attestations from Alice, Bob and Carol, while the chain that ends in the block at slot 8 has only attestations from Alice, Dave and Elaine). But accumulated across all the blocks in the lower branch the number of attesters is higher than in the upper branch, and thus the lower branch is chosen.
Similarly, at block in slot 6 one would have to choose between two branches, with the upper branch having attestations from 3 unique attesters (Alice, Bob and Carol) and the lower from only two (Dave and Elaine), thus one would go to the upper branch eventually choosing the chain with blocks in slots 1, 2, 4, 6, 7.
An honest attester must only attest to a block if the following conditions are met:
- The block extends the chain that the attester considers to be the currently selected chain;
- The block was received by the attester within the time slot in which the block was created. If the block was received later (e.g. due to network delay), the attester will still consider it to be valid, but shall not attest to it. It will become important when we discuss censorship below;
- The attester hasn’t attested to any other block for the same time slot. Note that honest proposers would never propose two blocks for the same slot, so this rule only kicks in if a malicious proposer attempted to create a fork by producing multiple blocks for the same slot, a condition that is immediately slashable.
Unlike the family of BFT consensus algorithms, the approach discussed above continues to operate even if more than ⅓ of all the validators are offline. The participants in the network will observe that the blocks do not get ⅔ of attestations, and will be more cautious about the finality of the blocks, waiting for additional security (for example by waiting until the block is cross-linked to the beacon chain and is finalized by Casper FFG there, topics outside the scope of this write-up), but importantly, the blocks will continue to be published, and the system doesn’t stall.
First observe that of the two censorship scenarios discussed above, the one in which two validators that have two consecutive slots censor out the block in the slot immediately preceding them is no longer valid, since the length of the chain doesn’t affect the fork choice rule any longer.
The second scenario (in which the proposer for a block delays it until the next block is published), would still be possible if the attesters were not required to only attest if the block was received during the time frame for the corresponding slot: a malicious proposer in time slot X could delay their block until the block X+1 is published, and then publish theirs. The attesters couldn’t distinguish between malicious intent and mere network delay, and without a specific requirement not to attest unless received within the time window could still attest to block for slot X, effectively censoring X+1.
The requirement to attest within the time frame completely solves the problem if the clocks among all the participants are perfectly synchronized. If the clocks are not synchronized, some sorts of timing attacks are possible, though are extremely unlikely.
First let’s observe that once a block B (or its branch) has more than ⅔ of attestations, unless at least ⅓ of the attesters are malicious, the reversal of B is practically impossible. To understand why recall that the attester would only attest to B if B was received within the time slot for it, and was built on what the attester considered to be the selected chain at that moment. If B has more than ⅔ of the attestations then from perspective of all the honest validators among those ⅔ B was on the selected chain at the moment it was attested to. Let’s say that at some later time another chain that does not contain B became the selected chain. For that to happen that chain needs to have more than ⅔ of attestations. The attesters who didn’t attest to B and dishonest attesters among the ⅔ who attested to B combined comprise less than ⅔ of validators, meaning that at least some honest validators from those who attested to B also attested to a block in that fork chain. Clearly such attestations couldn’t have appeared after B was published, since for such attestation to appear the other block had to be on the selected chain, but that block being on the selected chain itself is conditioned on appearance of such attestation. This means that the attestations on the competing chain from the honest validators who attested to B had to exist before B was published. Such event requires a series of unlikely events and probably some level of control over the network communications.
While unlikely, it is worth observing that in principle a reversal of a block with ⅔ of attestations is in theory possible. Consider the following figure:
Assume there are 7 validators, Alice (A), Bob (B), Carol ©, Dave (D) and Elaine (E) are honest, while Xavier (X) and Yasmine (Y) are malicious.
(i) There’s a fork with producers for time slot 2 and 3 both building on top of the block in slot 1. Alice and Bob both saw the block in time slot 2 during the time it was published and attested to it;
(ii) Carol saw the block in time slot 3 when it was published, but hasn’t seen the block in slot 2 and its attestations yet, and thus attested to block in slot 3, so did Xavier and Yasmine;
(iii) Now that the block in time slot 3 has three attestations, Alice and Bob consider it to be the selected block and also attest to it (assuming the time for the attestations hasn’t expired yet); The block in time slot 3 at this point has more than ⅔ of all the validators attesting to it and ideally shall not be reversible.
(iv) Unknown to other attesters Dave and Elaine also attested to block in slot 2 back when it was still legal, but their attestations were delayed due to slow network, and were not seen by Alice and Bob previously;
(v) Xavier and Yasmine exercise a malicious intent and attest to block in time slot 2. At this point block in time slot 2 has more attestations than the block in time slot 3.
(vi) The honest proposer in time slot 4 builds on top of block in time slot 2, since it has more attestations, effectively reversing a block in time slot 3 that had more than ⅔ attestations on it.
Note that this scenario requires a multitude of unlikely events (such as attestations from Dave and Elaine being delayed, which with hundreds of validators becomes extremely unlikely unless the adversaries control the network communication) and resorting to malicious behavior (Xavier and Yasmine attesting to a block they know is not on the selected chain after the timeframe for it has passed), but still shows that the attestation framework doesn’t provide theoretical guarantees as strong as the family of BFT consensus algorithms.