I want to summarize a modification of this proposal that combines the idea with A 0.001 bit proof of custody. Basically, as suggested in the proposal by @JustinDrake above, we make data availability sampling deterministic using the BLS signature vrf construction. Each chunk is then used to compute one custody but according to the 0.001 bit proof of custody construction; if any of the bits is one, the validator cannot sign an attestation in the next epoch or they become slashable. We adjust the number of bits in the construction so that the probability of the bit being one in any of the chunks is approximately 1/1000.
This addresses the “lazy validator dilemma” that the rational behaviour is to not check any chunks as it’s overhead with no reward. It does however not guarantee that a large fraction of validators will get slashed if a data availability fault occurs. However, I argue that we get properties that are nearly as good:
-
One attack vector are temporary withholding attacks which can be leveraged through lazy validators. The attacker has less than 67% stake but is able to produce blocks with withheld data that get finalized due to lazy validators. They later publish this data and thus the fork choice rule can suddenly change for honest nodes that have previously ignored the finalized block.
This attack becomes much less likely as rational validators will now do data availability sampling, since the penalty for missing a custody-1 chunk is very high. -
A dishonest majority validator can permanently withhold some piece of information on the finalized chain. Honest and rational validators will start building an alternative chain as the finalized chain is invalid on data availability grounds. Note that the attacker cannot switch to the honest chain without getting slashed, as they would have to make a vote that violates the FFG rules to do so. They are thus stuck on their chain at least until the honest chain finalized, and will thus lose most of their deposit from inactivity leaks on the honest chain.