Beacon chain fraud proofs

[dankrad]

Without beacon chain fraud proofs, light clients cannot be protected against incorrect beacon chain state transitions. This means a dishonest majority of validators can create a beacon chain with an incorrect state transition, for example creating lots of Ether and giving it to some validators.

In addition, since signing incorrect beacon blocks cannot be made slashable without a fraud proof mechanism, it means that validators can do this in parallel to building on the "honest" beacon chain without risk, even creating a justified (but not a finalized) alternative chain. All they need to do is miss a few attestations on the valid chain to build an attack chain with an incorrect state transition.

Also, not having beacon block fraud proofs creates an incentive problem where the dominant strategy is signing without validating blocks.

[unixpi]

I'm still trying to grasp all the moving parts, but i guess my main concern right now is the following:

If ethereum truly aspires to be the base layer of the new financial system, then we can expect most users will interact with eth2 using light clients, and probably from areas with bad coverage (rural south america, parts of africa, etc) -- if this is true, then acquiring the data, rather than the actual crypto verification, may well be the bottleneck.

From what i understand so far, it just seems like light-client security isn't all that good if we only rely on on-chain fraud-proofs (and that this is particularly true in the dishonest majority case) because it may take a while for the light-client to realise that the network is under attack (and very long rollbacks are possible).**

So i guess I see two problems:

1. Data as a bottleneck
2. Long rollbacks of transactions performed by unaware users

I don't have any good ideas to address the first (although i do think it's something we need to think harder about).

To try and address the second, I suggest we consider gossiping fraud proofs (while this won't prevent rollbacks, it will at least allow clients to be aware that the network is under attack).

---

**To elaborate a little here, if the majority of full nodes are dishonest, then the majority of block producers are dishonest, so you might have to wait a while for a fraud-proof to be included on-chain. In the meantime, light-clients are transacting as if nothing has happened. I think it's important to minimise the time delay between the attack and users being aware that the attack is happening so they don't perform potentially irreversible (or hard-to-reverse) transactions in the non-crypto world. In sum, if a light-client can be made aware of an attack quicker, it can help prevent users from shooting themselves in the foot.

Resources

• Fraud proofs — Secure on-chain scalability
• Compact Fraud Proofs for UTXO Chains Without Intermediate State Serialization
• Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
• Bitcoin: A Peer-to-Peer Electronic Cash System (section 8)

(Thank you @adiasg for your infinite patience, and for helping me better understand my own concerns :)

[dankrad]

To try and address the second, I suggest we consider gossiping fraud proofs (while this won't prevent rollbacks, it will at least allow clients to be aware that the network is under attack).

Absolutely -- it is essential that fraud proofs are gossiped and respected without being on chain. The on-chain exclusion is only for punishment. And since in this case it's on an invalid chain, it would actually not matter whether it's included on that chain. It's included on the "honest" chain to remove the stake of the attackers.

To elaborate a little here, if the majority of full nodes are dishonest, then the majority of block producers are dishonest, so you might have to wait a while for a fraud-proof to be included on-chain.

Much worse that this, since the malicious nodes are in the majority, they can easily stop the fraud proof from ever being included.

[unixpi]

Happy to hear :) Trying to get a better handle on the size of the proofs.

Are we planning on using intermediate states (outlined in this paper)?

If so, how do we handle the problem articulated here:

If P [the interval between intermediate states] is too large, then fraud proofs quickly become unwieldy for light clients in practice despite identical asymptotic costs. If P is too small, state serialization costs grow. It turns out there’s no good way of picking P...

if not, do we have a design that ensures fraud proofs don't become too unwieldy for light clients?

[dankrad]

(Note that for shard chains, this will not be a problem -- since we are constructing them to be stateless, the shard block itself is already a suitable fraud proof).

For the beacon chain, we haven't considered the problem that much in the past. There are some operations that require large parts of the state:

1. The balance updates at the end of every epoch.
2. Checking attestations requires the state of many validators (key, effective balance, slashed). (There may be more that can't think off right now).

The simplest way to make these fraud-proof-friendly would be to turn each of these operations into smaller steps, and commit to the state after every step. This guarantees fraud proofs of reasonable size exist, but actually constructing them will be quite complex. However, there are some other ideas that could achieve this in more elegant ways:

1. For the balance updates, we could make them probabilistic -- say only update 1/100th of the balances each block (and give those 100x the reward). This is ok, since validators are expected to be in the game for much more than 100 epochs.
2. Change some of the commitments to linear ones -- for example, if we make the balances Kate commitments, then a large number of updates could just become a vector addition (however, there would still be the problem of creating the difference vector, which could be done more iteratively in the beacon blocks before the update).

Currently we don't know yet how difficult this will be for beacon blocks. Next step would be fore someone to make a construction and see how much work it actually is :)

[unixpi]

This guarantees fraud proofs of reasonable size exist, but actually constructing them will be quite complex.

Could you elaborate a little on this?

[dankrad]

Could you elaborate a little on this?

Basically, all of the spec logic would have to be extremely modularized so that it can be run on small diffs of the state. Additionally, some operations will currently read almost all of the state, and we would need to find more elaborate data structures that make caches of computations so that they can be broken up into smaller steps that don't access too much of the state.

All of this is possible but it's a deep rabbit hole. If the spec logic were "inspectable" (like VM code), then some of this could be automated, but it isn't, so I expect this to be a rather laborious process. [Yes, it's specified as python code and you could see that as a form of inspectable code -- the problem is that concrete client implementations don't use this form and could have a very different logic]