Custody game checklist

[JustinDrake]

TODO

• 1. Merkleisation-friendly challenge records: Zero-out and over-write instead of remove() and append().
• 2. Worst-case key reveals: Increase MAX_CUSTODY_KEY_REVEALS and EPOCHS_PER_CUSTODY_PERIOD to deal with worst-case key reveal bandwidth.
• 3. Increase challenge bandwidth: Increase MAX_CUSTODY_CHUNK_CHALLENGES and MAX_CUSTODY_MIX_CHALLENGES.
• 4. Fix withdrawability: Validators need to regain withdrawability after responder.withdrawable_epoch = FAR_FUTURE_EPOCH.
• 5. MPC-friendly chunk bit: Move to something like the Legendre symbol.
• 6. Force timely key reveals: Similar to timely challenge responses.
• 7. Multiple challenges per validator: Only the first challenge that passes the waiting period rewards the challenger.
• 8. Stagger reveal periods: To avoid large key reveal bursts at period boundaries.
• 9. Remove max_reveal_lateness: Find cleaner alternative.
• 10. Redefine BYTES_PER_SHARD_BLOCK: Replace by BYTES_PER_SHARD_BLOCK = 2 * BYTES_PER_SHARD_BLOCK_BODY.
• 11. Economic review: Particularly around sizes and structure of rewards and penalties.
• 12. Review BYTES_PER_CUSTODY_CHUNK: There are pros and cons to increasing/decreasing.
• 13. Executable spec: Make custody game executable and add tests.
• 14. Chunk response delay: Add MIN_ACTIVATION_EXIT_DELAY for chunk responses. (To avoid proposers responding to their own challenges.)

Ideas to consider

• 1. G1 key reveals: 2x smaller key reveals.
• 2. Merge RANDAO and key reveals: Slightly reduced key reveal overhead.
• 3. Batched reveals: Batch reveals in case of lateness.
• 4. Separate reveal per epoch: Derive a new key per epoch from a single period reveal.
• 5. Forced responses: Force proposers to respond to their challenges.
• 6. Merkleise chunk_bits: Consider storing a Merkle root of chunk_bits intead of chunk_bits directly.
• 7. Multi-challenges: All attesters assigned random chunks to a single data root challenge.
• 8. Merge challenge records: Merge custody chunk and custody bit challenges.
• 9. Dynamic chunk size: Adjust chunk size to size of crosslink data.

[vbuterin]

10. Redefine BYTES_PER_SHARD_BLOCK: Replace by BYTES_PER_SHARD_BLOCK = 2 * BYTES_PER_SHARD_BLOCK_BODY.

I don't agree with this. I feel like the shard block data size is a more "fundamental" constant; it's closer to what users care about. The fact that there's a 2x overhead is more of a protocol-specific detail.

3. Batched reveals: Batch reveals in case of lateness.

Also don't think there's value to this. We still have to reveal each of the individual subkeys and verify them individually so there are no real savings.

Already started on some of the others (see open PRs).

[hwwhww]

@dankrad do you mind checking the checklist again? It looks like many issues are solved in #1705 🎉

[dankrad]

10 and 12 in the TODO seem outdated?

[JustinDrake]

10 and 12 in the TODO seem outdated?

May be worth starting a new checklist and closing this one :)