1_custody-game.md
1 # Ethereum 2.0 Phase 1 -- Custody Game 2 3 **NOTICE**: This spec is a work-in-progress for researchers and implementers. 4 5 ## Table of contents 6 7 <!-- TOC --> 8 9 - [Ethereum 2.0 Phase 1 -- Custody Game](#ethereum-20-phase-1----custody-game) 10 - [Table of contents](#table-of-contents) 11 - [Introduction](#introduction) 12 - [Terminology](#terminology) 13 - [Constants](#constants) 14 - [Misc](#misc) 15 - [Time parameters](#time-parameters) 16 - [Max operations per block](#max-operations-per-block) 17 - [Signature domains](#signature-domains) 18 - [Data structures](#data-structures) 19 - [Custody objects](#custody-objects) 20 - [`CustodyChunkChallenge`](#custodychunkchallenge) 21 - [`CustodyBitChallenge`](#custodybitchallenge) 22 - [`CustodyChunkChallengeRecord`](#custodychunkchallengerecord) 23 - [`CustodyBitChallengeRecord`](#custodybitchallengerecord) 24 - [`CustodyResponse`](#custodyresponse) 25 - [`CustodyKeyReveal`](#custodykeyreveal) 26 - [Phase 0 container updates](#phase-0-container-updates) 27 - [`Validator`](#validator) 28 - [`BeaconState`](#beaconstate) 29 - [`BeaconBlockBody`](#beaconblockbody) 30 - [Helpers](#helpers) 31 - [`typeof`](#typeof) 32 - [`empty`](#empty) 33 - [`get_crosslink_chunk_count`](#get_crosslink_chunk_count) 34 - [`get_custody_chunk_bit`](#get_custody_chunk_bit) 35 - [`epoch_to_custody_period`](#epoch_to_custody_period) 36 - [`replace_empty_or_append`](#replace_empty_or_append) 37 - [`verify_custody_key`](#verify_custody_key) 38 - [Per-block processing](#per-block-processing) 39 - [Operations](#operations) 40 - [Custody reveals](#custody-reveals) 41 - [Chunk challenges](#chunk-challenges) 42 - [Bit challenges](#bit-challenges) 43 - [Custody responses](#custody-responses) 44 - [Per-epoch processing](#per-epoch-processing) 45 46 <!-- /TOC --> 47 48 ## Introduction 49 50 This document details the beacon chain additions and changes in Phase 1 of Ethereum 2.0 to support the shard data custody game, building upon the [phase 0](0_beacon-chain.md) specification. 51 52 ## Terminology 53 54 * **Custody game**: 55 * **Custody period**: 56 * **Custody chunk**: 57 * **Custody chunk bit**: 58 * **Custody chunk challenge**: 59 * **Custody bit**: 60 * **Custody bit challenge**: 61 * **Custody key**: 62 * **Custody key reveal**: 63 * **Custody key mask**: 64 * **Custody response**: 65 * **Custody response deadline**: 66 67 ## Constants 68 69 ### Misc 70 71 | Name | Value | 72 | - | - | 73 | `BYTES_PER_SHARD_BLOCK` | `2**14` (= 16,384) | 74 | `BYTES_PER_CUSTODY_CHUNK` | `2**9` (= 512) | 75 | `MINOR_REWARD_QUOTIENT` | `2**8` (= 256) | 76 77 ### Time parameters 78 79 | Name | Value | Unit | Duration | 80 | - | - | :-: | :-: | 81 | `MAX_CHUNK_CHALLENGE_DELAY` | `2**11` (= 2,048) | epochs | ~9 days | 82 | `EPOCHS_PER_CUSTODY_PERIOD` | `2**11` (= 2,048) | epochs | ~9 days | 83 | `CUSTODY_RESPONSE_DEADLINE` | `2**14` (= 16,384) | epochs | ~73 days | 84 85 ### Max operations per block 86 87 | Name | Value | 88 | - | - | 89 | `MAX_CUSTODY_KEY_REVEALS` | `2**4` (= 16) | 90 | `MAX_CUSTODY_CHUNK_CHALLENGES` | `2**2` (= 4) | 91 | `MAX_CUSTODY_BIT_CHALLENGES` | `2**2` (= 4) | 92 | `MAX_CUSTODY_RESPONSES` | `2**5` (= 32) | 93 94 ### Signature domains 95 96 | Name | Value | 97 | - | - | 98 | `DOMAIN_CUSTODY_KEY_REVEAL` | `6` | 99 | `DOMAIN_CUSTODY_BIT_CHALLENGE` | `7` | 100 101 ## Data structures 102 103 ### Custody objects 104 105 #### `CustodyChunkChallenge` 106 107 ```python 108 { 109 'responder_index': ValidatorIndex, 110 'attestation': Attestation, 111 'chunk_index': 'uint64', 112 } 113 ``` 114 115 #### `CustodyBitChallenge` 116 117 ```python 118 { 119 'responder_index': ValidatorIndex, 120 'attestation': Attestation, 121 'challenger_index': ValidatorIndex, 122 'responder_key': BLSSignature, 123 'chunk_bits': Bitfield, 124 'signature': BLSSignature, 125 } 126 ``` 127 128 #### `CustodyChunkChallengeRecord` 129 130 ```python 131 { 132 'challenge_index': 'uint64', 133 'challenger_index': ValidatorIndex, 134 'responder_index': ValidatorIndex, 135 'deadline': Epoch, 136 'crosslink_data_root': Hash, 137 'depth': 'uint64', 138 'chunk_index': 'uint64', 139 } 140 ``` 141 142 #### `CustodyBitChallengeRecord` 143 144 ```python 145 { 146 'challenge_index': 'uint64', 147 'challenger_index': ValidatorIndex, 148 'responder_index': ValidatorIndex, 149 'deadline': Epoch, 150 'crosslink_data_root': Hash, 151 'chunk_bits': Bitfield, 152 'responder_key': BLSSignature, 153 } 154 ``` 155 156 #### `CustodyResponse` 157 158 ```python 159 { 160 'challenge_index': 'uint64', 161 'chunk_index': 'uint64', 162 'chunk': ['byte', BYTES_PER_CUSTODY_CHUNK], 163 'branch': [Hash], 164 } 165 ``` 166 167 #### `CustodyKeyReveal` 168 169 ```python 170 { 171 'revealer_index': ValidatorIndex, 172 'period': 'uint64', 173 'key': BLSSignature, 174 'masker_index': ValidatorIndex, 175 'mask': Hash, 176 } 177 ``` 178 179 ### Phase 0 container updates 180 181 Add the following fields to the end of the specified container objects. Fields with underlying type `uint64` are initialized to `0` and list fields are initialized to `[]`. 182 183 #### `Validator` 184 185 ```python 186 'custody_reveal_index': 'uint64', 187 'max_reveal_lateness': 'uint64', 188 ``` 189 190 #### `BeaconState` 191 192 ```python 193 'custody_chunk_challenge_records': [CustodyChunkChallengeRecord], 194 'custody_bit_challenge_records': [CustodyBitChallengeRecord], 195 'custody_challenge_index': 'uint64', 196 ``` 197 198 #### `BeaconBlockBody` 199 200 ```python 201 'custody_key_reveals': [CustodyKeyReveal], 202 'custody_chunk_challenges': [CustodyChunkChallenge], 203 'custody_bit_challenges': [CustodyBitChallenge], 204 'custody_responses': [CustodyResponse], 205 ``` 206 207 ## Helpers 208 209 ### `typeof` 210 211 The `typeof` function accepts and SSZ object as a single input and returns the corresponding SSZ type. 212 213 ### `empty` 214 215 The `empty` function accepts and SSZ type as input and returns an object of that type with all fields initialized to default values. 216 217 ### `get_crosslink_chunk_count` 218 219 ```python 220 def get_custody_chunk_count(attestation: Attestation) -> int: 221 crosslink_start_epoch = attestation.data.latest_crosslink.epoch 222 crosslink_end_epoch = slot_to_epoch(attestation.data.slot) 223 crosslink_crosslink_length = min(MAX_CROSSLINK_EPOCHS, end_epoch - start_epoch) 224 chunks_per_epoch = 2 * BYTES_PER_SHARD_BLOCK * SLOTS_PER_EPOCH // BYTES_PER_CUSTODY_CHUNK 225 return crosslink_crosslink_length * chunks_per_epoch 226 ``` 227 228 ### `get_custody_chunk_bit` 229 230 ```python 231 def get_custody_chunk_bit(key: BLSSignature, chunk: bytes) -> bool: 232 # TODO: Replace with something MPC-friendly, e.g. the Legendre symbol 233 return get_bitfield_bit(hash(challenge.responder_key + chunk), 0) 234 ``` 235 236 ### `epoch_to_custody_period` 237 238 ```python 239 def epoch_to_custody_period(epoch: Epoch) -> int: 240 return epoch // EPOCHS_PER_CUSTODY_PERIOD 241 ``` 242 243 ### `replace_empty_or_append` 244 245 ```python 246 def replace_empty_or_append(list: List[Any], new_element: Any) -> int: 247 for i in range(len(list)): 248 if list[i] == empty(typeof(new_element)): 249 list[i] = new_element 250 return i 251 list.append(new_element) 252 return len(list) - 1 253 ``` 254 255 ### `verify_custody_key` 256 257 ```python 258 def verify_custody_key(state: BeaconState, reveal: CustodyKeyReveal) -> bool: 259 # Case 1: non-masked non-punitive non-early reveal 260 pubkeys = [state.validator_registry[reveal.revealer_index].pubkey] 261 message_hashes = [hash_tree_root(reveal.period)] 262 263 # Case 2: masked punitive early reveal 264 # Masking prevents proposer stealing the whistleblower reward 265 # Secure under the aggregate extraction infeasibility assumption 266 # See pages 11-12 of https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf 267 if reveal.mask != ZERO_HASH: 268 pubkeys.append(state.validator_registry[reveal.masker_index].pubkey) 269 message_hashes.append(reveal.mask) 270 271 return bls_verify_multiple( 272 pubkeys=pubkeys, 273 message_hashes=message_hashes, 274 signature=reveal.key, 275 domain=get_domain( 276 fork=state.fork, 277 epoch=reveal.period * EPOCHS_PER_CUSTODY_PERIOD, 278 domain_type=DOMAIN_CUSTODY_KEY_REVEAL, 279 ), 280 ) 281 ``` 282 283 ## Per-block processing 284 285 ### Operations 286 287 Add the following operations to the per-block processing, in order the given below and after all other operations in phase 0. 288 289 #### Custody reveals 290 291 Verify that `len(block.body.custody_key_reveals) <= MAX_CUSTODY_KEY_REVEALS`. 292 293 For each `reveal` in `block.body.custody_key_reveals`, run the following function: 294 295 ```python 296 def process_custody_reveal(state: BeaconState, 297 reveal: CustodyKeyReveal) -> None: 298 assert verify_custody_key(state, reveal) 299 revealer = state.validator_registry[reveal.revealer_index] 300 current_custody_period = epoch_to_custody_period(get_current_epoch(state)) 301 302 # Case 1: non-masked non-punitive non-early reveal 303 if reveal.mask == ZERO_HASH: 304 assert reveal.period == epoch_to_custody_period(revealer.activation_epoch) + revealer.custody_reveal_index 305 # Revealer is active or exited 306 assert is_active_validator(revealer, get_current_epoch(state)) or revealer.exit_epoch > get_current_epoch(state) 307 revealer.custody_reveal_index += 1 308 revealer.max_reveal_lateness = max(revealer.max_reveal_lateness, current_custody_period - reveal.period) 309 proposer_index = get_beacon_proposer_index(state) 310 increase_balance(state, proposer_index, base_reward(state, index) // MINOR_REWARD_QUOTIENT) 311 312 # Case 2: masked punitive early reveal 313 else: 314 assert reveal.period > current_custody_period 315 assert revealer.slashed is False 316 slash_validator(state, reveal.revealer_index, reveal.masker_index) 317 ``` 318 319 #### Chunk challenges 320 321 Verify that `len(block.body.custody_chunk_challenges) <= MAX_CUSTODY_CHUNK_CHALLENGES`. 322 323 For each `challenge` in `block.body.custody_chunk_challenges`, run the following function: 324 325 ```python 326 def process_chunk_challenge(state: BeaconState, 327 challenge: CustodyChunkChallenge) -> None: 328 # Verify the attestation 329 assert verify_standalone_attestation(state, convert_to_standalone(state, challenge.attestation)) 330 # Verify it is not too late to challenge 331 assert slot_to_epoch(challenge.attestation.data.slot) >= get_current_epoch(state) - MAX_CHUNK_CHALLENGE_DELAY 332 responder = state.validator_registry[challenge.responder_index] 333 assert responder.exit_epoch >= get_current_epoch(state) - MAX_CHUNK_CHALLENGE_DELAY 334 # Verify the responder participated in the attestation 335 attesters = get_attesting_indices(state, attestation.data, attestation.aggregation_bitfield) 336 assert challenge.responder_index in attesters 337 # Verify the challenge is not a duplicate 338 for record in state.custody_chunk_challenge_records: 339 assert ( 340 record.crosslink_data_root != challenge.attestation.data.crosslink_data_root or 341 record.chunk_index != challenge.chunk_index 342 ) 343 # Verify depth 344 depth = math.log2(next_power_of_two(get_custody_chunk_count(challenge.attestation))) 345 assert challenge.chunk_index < 2**depth 346 # Add new chunk challenge record 347 new_record = CustodyChunkChallengeRecord( 348 challenge_index=state.custody_challenge_index, 349 challenger_index=get_beacon_proposer_index(state), 350 responder_index=challenge.responder_index 351 deadline=get_current_epoch(state) + CUSTODY_RESPONSE_DEADLINE, 352 crosslink_data_root=challenge.attestation.data.crosslink_data_root, 353 depth=depth, 354 chunk_index=challenge.chunk_index, 355 ) 356 replace_empty_or_append(state.custody_chunk_challenge_records, new_record) 357 358 state.custody_challenge_index += 1 359 # Postpone responder withdrawability 360 responder.withdrawable_epoch = FAR_FUTURE_EPOCH 361 ``` 362 363 #### Bit challenges 364 365 Verify that `len(block.body.custody_bit_challenges) <= MAX_CUSTODY_BIT_CHALLENGES`. 366 367 For each `challenge` in `block.body.custody_bit_challenges`, run the following function: 368 369 ```python 370 def process_bit_challenge(state: BeaconState, 371 challenge: CustodyBitChallenge) -> None: 372 # Verify challenge signature 373 challenger = state.validator_registry[challenge.challenger_index] 374 assert bls_verify( 375 pubkey=challenger.pubkey, 376 message_hash=signing_root(challenge), 377 signature=challenge.signature, 378 domain=get_domain(state, get_current_epoch(state), DOMAIN_CUSTODY_BIT_CHALLENGE), 379 ) 380 # Verify the challenger is not slashed 381 assert challenger.slashed is False 382 # Verify the attestation 383 assert verify_standalone_attestation(state, convert_to_standalone(state, challenge.attestation)) 384 # Verify the attestation is eligible for challenging 385 responder = state.validator_registry[challenge.responder_index] 386 min_challengeable_epoch = responder.exit_epoch - EPOCHS_PER_CUSTODY_PERIOD * (1 + responder.max_reveal_lateness) 387 assert min_challengeable_epoch <= slot_to_epoch(challenge.attestation.data.slot) 388 # Verify the responder participated in the attestation 389 attesters = get_attesting_indices(state, attestation.data, attestation.aggregation_bitfield) 390 assert challenge.responder_index in attesters 391 # A validator can be the challenger or responder for at most one challenge at a time 392 for record in state.custody_bit_challenge_records: 393 assert record.challenger_index != challenge.challenger_index 394 assert record.responder_index != challenge.responder_index 395 # Verify the responder key 396 assert verify_custody_key(state, CustodyKeyReveal( 397 revealer_index=challenge.responder_index, 398 period=epoch_to_custody_period(slot_to_epoch(attestation.data.slot)), 399 key=challenge.responder_key, 400 masker_index=0, 401 mask=ZERO_HASH, 402 )) 403 # Verify the chunk count 404 chunk_count = get_custody_chunk_count(challenge.attestation) 405 assert verify_bitfield(challenge.chunk_bits, chunk_count) 406 # Verify the xor of the chunk bits does not equal the custody bit 407 chunk_bits_xor = 0b0 408 for i in range(chunk_count): 409 chunk_bits_xor ^ get_bitfield_bit(challenge.chunk_bits, i) 410 custody_bit = get_bitfield_bit(attestation.custody_bitfield, attesters.index(responder_index)) 411 assert custody_bit != chunk_bits_xor 412 # Add new bit challenge record 413 new_record = CustodyBitChallengeRecord( 414 challenge_index=state.custody_challenge_index, 415 challenger_index=challenge.challenger_index, 416 responder_index=challenge.responder_index, 417 deadline=get_current_epoch(state) + CUSTODY_RESPONSE_DEADLINE 418 crosslink_data_root=challenge.attestation.crosslink_data_root, 419 chunk_bits=challenge.chunk_bits, 420 responder_key=challenge.responder_key, 421 ) 422 replace_empty_or_append(state.custody_bit_challenge_records, new_record) 423 state.custody_challenge_index += 1 424 # Postpone responder withdrawability 425 responder.withdrawable_epoch = FAR_FUTURE_EPOCH 426 ``` 427 428 #### Custody responses 429 430 Verify that `len(block.body.custody_responses) <= MAX_CUSTODY_RESPONSES`. 431 432 For each `response` in `block.body.custody_responses`, run the following function: 433 434 ```python 435 def process_custody_response(state: BeaconState, 436 response: CustodyResponse) -> None: 437 chunk_challenge = next(record for record in state.custody_chunk_challenge_records if record.challenge_index == response.challenge_index, None) 438 if chunk_challenge is not None: 439 return process_chunk_challenge_response(state, response, chunk_challenge) 440 441 bit_challenge = next(record for record in state.custody_bit_challenge_records if record.challenge_index == response.challenge_index, None) 442 if bit_challenge is not None: 443 return process_bit_challenge_response(state, response, bit_challenge) 444 445 assert False 446 ``` 447 448 ```python 449 def process_chunk_challenge_response(state: BeaconState, 450 response: CustodyResponse, 451 challenge: CustodyChunkChallengeRecord) -> None: 452 # Verify chunk index 453 assert response.chunk_index == challenge.chunk_index 454 # Verify the chunk matches the crosslink data root 455 assert verify_merkle_branch( 456 leaf=hash_tree_root(response.chunk), 457 branch=response.branch, 458 depth=challenge.depth, 459 index=response.chunk_index, 460 root=challenge.crosslink_data_root, 461 ) 462 # Clear the challenge 463 records = state.custody_chunk_challenge_records 464 records[records.index(challenge)] = CustodyChunkChallengeRecord() 465 # Reward the proposer 466 proposer_index = get_beacon_proposer_index(state) 467 increase_balance(state, proposer_index, base_reward(state, index) // MINOR_REWARD_QUOTIENT) 468 ``` 469 470 ```python 471 def process_bit_challenge_response(state: BeaconState, 472 response: CustodyResponse, 473 challenge: CustodyBitChallengeRecord) -> None: 474 # Verify chunk index 475 assert response.chunk_index < len(challenge.chunk_bits) 476 # Verify the chunk matches the crosslink data root 477 assert verify_merkle_branch( 478 leaf=hash_tree_root(response.chunk), 479 branch=response.branch, 480 depth=math.log2(next_power_of_two(len(challenge.chunk_bits))), 481 index=response.chunk_index, 482 root=challenge.crosslink_data_root, 483 ) 484 # Verify the chunk bit does not match the challenge chunk bit 485 assert get_custody_chunk_bit(challenge.responder_key, response.chunk) != get_bitfield_bit(challenge.chunk_bits, response.chunk_index) 486 # Clear the challenge 487 records = state.custody_bit_challenge_records 488 records[records.index(challenge)] = CustodyBitChallengeRecord() 489 # Slash challenger 490 slash_validator(state, challenge.challenger_index, challenge.responder_index) 491 ``` 492 493 ## Per-epoch processing 494 495 Run `process_challenge_deadlines(state)` immediately after `process_ejections(state)`: 496 497 ```python 498 def process_challenge_deadlines(state: BeaconState) -> None: 499 for challenge in state.custody_chunk_challenge_records: 500 if get_current_epoch(state) > challenge.deadline: 501 slash_validator(state, challenge.responder_index, challenge.challenger_index) 502 records = state.custody_chunk_challenge_records 503 records[records.index(challenge)] = CustodyChunkChallengeRecord() 504 505 for challenge in state.custody_bit_challenge_records: 506 if get_current_epoch(state) > challenge.deadline: 507 slash_validator(state, challenge.responder_index, challenge.challenger_index) 508 records = state.custody_bit_challenge_records 509 records[records.index(challenge)] = CustodyBitChallengeRecord() 510 ``` 511 512 In `process_penalties_and_exits`, change the definition of `eligible` to the following (note that it is not a pure function because `state` is declared in the surrounding scope): 513 514 ```python 515 def eligible(index): 516 validator = state.validator_registry[index] 517 # Cannot exit if there are still open chunk challenges 518 if len([record for record in state.custody_chunk_challenge_records if record.responder_index == index]) > 0: 519 return False 520 # Cannot exit if you have not revealed all of your custody keys 521 elif epoch_to_custody_period(revealer.activation_epoch) + validator.custody_reveal_index <= epoch_to_custody_period(validator.exit_epoch): 522 return False 523 # Cannot exit if you already have 524 elif validator.withdrawable_epoch < FAR_FUTURE_EPOCH: 525 return False 526 # Return minimum time 527 else: 528 return current_epoch >= validator.exit_epoch + MIN_VALIDATOR_WITHDRAWAL_EPOCHS 529 ```