Miscellaneous beacon chain changes—take 2

[JustinDrake]

(See #128 for take 1.)

• 1. Slot-based state transition function: Add slot to the state. See Add slot number to state and make state transition function per slot #212.
• 2. Merge attestations and specials: Make attestations a kind of special. Simplifies data structures and logic. (For example, the MAX_ATTESTATIONS_PER_BLOCK logic can be encapsulated in the per-kind caps.) Also cleanly separates beacon block "headers" and "bodies".
• 3. Preserve deposit ordering: Require that deposits on Ethereum 2.0 be consumed in the order they were created in Ethereum 1.0. Addresses various attacks (double-spend, censorship, prioritisation).
• 4. Remove ancestor hashes from blocks: The ancestor_hashes is 1kB and consists of redundant data that clients can build for themselves. Smaller blocks, simpler consensus logic. Potentially put ancestor_hashes in the state. Add parent_root to blocks in its place.
• 5. Historical block accumulator: Add a double-batched Merkle accumulator for beacon blocks. More light-client-friendly infrastructure.
• 6. Stick with SHA3: The performance benefits of Blake cannot be relied upon because STARK/SNARK-friendly hashes will likely be no faster than SHA3. Also fixes sha3/blake mismatch in deposit merkle tree #151 and makes it easier for Ethereum 1.0 to be a light client for Ethereum 2.0.
• 7. Use tree hashing everywhere: Use SSZTreeHash for everything. For objects it's much cleaner. For one-level-deep fixed size objects it's equivalent to hash.

[djrtwo]

I'm not certain [2] is as clean a simplification has advertised. Attestations still need to be added to state.latest_attestations to be processed at the turn of an EPOCH. This data is slightly different than the data within the block so we'd still need a distinct data structure.

[JustinDrake]

Attestations still need to be added to state.latest_attestations to be processed at the turn of an EPOCH.

Right. The merging is purely in the beacon blocks. state.latest_attestations stays as is.

Was the purpose of ancestor_hashes not to be able to serve light clients information about past blocks?

That's one reason, and [5] addresses that in a better way (IMO).

[vbuterin]

I'm not certain [2] is as clean a simplification has advertised. Attestations still need to be added to state.latest_attestations to be processed at the turn of an EPOCH. This data is slightly different than the data within the block so we'd still need a distinct data structure.

I would say the right implementation of [2] would be to remove the concept of "specials" entirely, and instead explicitly have lists of attestations, deposits, voluntary exits, attester slashing messages, etc etc.

This would also remove the weird de-facto dynamic typing of the list 😄

[djrtwo]

Generally agreed @vbuterin.
One downside of having explicit lists is that we might have to add a list in phase 2 or something that we didn't expect, thus changing the BeaconState datastructure. Think this is worth it though

[arnetheduck]

One downside of having explicit lists is that we might have to add a list

this is for upgrades outside of forks? for forks, the fork versioning should be enough, but if we want to do this generally, it would be nice to do more generally than just specials

[vbuterin]

Here's an explicit proposal for the ancestor hashes / accumulator @JustinDrake.

Add two lists into the state:

• power_of_2_ancestor_hashes[16], where power_of_2_ancestor_hashes[i] is the hash of the block at the most recent slot whose height is a multiple of `2**i
• old_ancestor_hashes[], where old_ancestor_hashes[i] is the hash of the block at slot 2**16 * i

Question: how is this concretely different from a DBMA? Is the difference that we should be building up a plain binary Merkle tree of hashes rather than power-of-2 hashes in the state, to make the witnesses at that point 32 bytes per tree level?

[JustinDrake]

how is this concretely different from a DBMA?

Two differences:

1. power_of_2_ancestor_hashes[16] is replaced by recent_ancestor_hashes[2**13], where recent_ancestor_hashes[i] is the block hash of the ith most recent ancestor
2. old_ancestor_hashes is replaced by old_ancestor_roots, where old_ancestor_roots[i] is the Merkleisation of the block hashes at slots [2**13 * i, 2**13 * (i +1) - 1].

(With 6-second slots, and after 32 years, recent_ancestor_hashes and old_ancestor_roots combined will consume 2**13*32b + 32*365.25*24*60*60/6/2**13*32b = 920kB of storage.)

Two advantages of DBMAs:

1. The witnesses are fixed-size. As specified above they are 392 bytes: one uint64 to specify the root (the i above) plus 12 hashes for the intermediate Merkle path nodes.
2. The witnesses are permanent.

One disadvantage with DBMAs is that the permanent witness takes 2**13 slots (~14 minutes) to generate in the worst case. The good news is that within 2**13 slots you don't need the permanent witness as you can simply perform a lookup in recent_ancestor_hashes, i.e. the block hash is itself the witness.

[djrtwo]

checked off number 7 in favor of #286

closing.. great work!