Sync Committee

/// The block root and state root for every slot are stored in the state for `SLOTS_PER_HISTORICAL_ROOT` slots.
/// When that list is full, both lists are Merkleized into a single Merkle root,
/// which is added to the ever-growing state.historical_roots list.
/// [source](https://eth2book.info/bellatrix/part3/config/preset/#slots_per_historical_root)
const SLOTS_PER_HISTORICAL_ROOT: u64 = 2.pow(13); // 8,192
 
/// Every `SLOTS_PER_HISTORICAL_ROOT` slots, the list of block roots and the list of state roots in the beacon state
/// are Merkleized and added to state.historical_roots list. Although state.historical_roots is in principle unbounded,
/// all SSZ lists must have maximum sizes specified.
///
/// The size `HISTORICAL_ROOTS_LIMIT` will be fine for the next few millennia, after which it will be somebody else's problem.
/// The list grows at less than 10 KB per year. Storing past roots like this allows Merkle proofs to be constructed
/// about anything in the beacon chain's history if required.
/// [source](https://eth2book.info/bellatrix/part3/config/preset/#historical_roots_limit)
const HISTORICAL_ROOTS_LIMIT: u64 = 2.pow(24); // 16,777,216
 
/// Generalized merkle tree index for the latest finalized header
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/light-client/sync-protocol.md#constants)
const FINALIZED_ROOT_INDEX: u64 = 105;
 
/// Generalized merkle tree index for the block_roots in [`BeaconState`]
const BLOCK_ROOTS_INDEX: u64 = 37;
 
/// Generalized merkle tree index for the historical_roots in [`BeaconState`]
const HISTORICAL_ROOTS_INDEX: u64 = 39;
 
/// Generalized merkle tree index for the execution_payload in [`BeaconBlockBody`]
const EXECUTION_PAYLOAD_INDEX: u64 = 25;
 
/// Generalized merkle tree index for the state_root in [`ExecutionPayload`]
const EXECUTION_PAYLOAD_STATE_ROOT_INDEX: u64 = 18;
 
/// Generalized merkle tree index for the block_number in [`ExecutionPayload`]
const EXECUTION_PAYLOAD_BLOCK_NUMBER_INDEX: u64 = 22;
 
/// Generalized merkle tree index for the next sync committee
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/light-client/sync-protocol.md#constants)
const NEXT_SYNC_COMMITTEE_INDEX: u64 = 55;
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md#domain-types)
const DOMAIN_SYNC_COMMITTEE: [u8; 4] = [7, 0, 0, 0];
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md#sync-committee)
const EPOCHS_PER_SYNC_COMMITTEE_PERIOD: u64 = 2.pow(8);
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#time-parameters)
const SLOTS_PER_EPOCH: u64 = 2.pow(5);
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/fork.md#configuration)
const ALTAIR_FORK_EPOCH: u64 = 74240;
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/fork.md#configuration)
const ALTAIR_FORK_VERSION: [u8; 4] = [1, 0, 0, 0];
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#genesis-settings)
const GENESIS_FORK_VERSION: [u8; 4] = [0, 0, 0, 0];
 
// from eth/v1/beacon/genesis
const GENESIS_VALIDATORS_ROOT: H256 = H256(hex!("4b363db94e286120d76eb905340fdd4e54bfe9f06bf33ff6cf5ad27f511bfe95"));
 
// from eth/v1/beacon/genesis
const GENESIS_TIMESTAMP: u64 = 1606824023;
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/bellatrix/beacon-chain.md#execution)
const BYTES_PER_LOGS_BLOOM: u64 = 2.pow(8);
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/bellatrix/beacon-chain.md#execution)
const MAX_EXTRA_DATA_BYTES: u64: 2.pow(5);
 
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/bellatrix/beacon-chain.md#execution)
const MAX_TRANSACTIONS_PER_PAYLOAD: u64 = 2.pow(20);

/// The beacon block header
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#beaconblockheader)
struct BeaconBlockHeader {
  /// current slot for this block
  slot: u64,
  /// validator index
  proposer_index: ValidatorIndex,
  /// ssz root of parent block
  parent_root: H256,
  /// ssz root of associated [`BeaconState`]
  state_root: H256,
  /// ssz root of associated [`BeaconBlockBody`]
  body_root: H256,
}
 
/// The beacon block body
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md#beaconblockbody)
struct BeaconBlockBody {
  randao_reveal: BLSSignature,
  eth1_data: Eth1Data, // Eth1 data vote
  graffiti: Bytes32,   // Arbitrary data
  // Operations
  proposer_slashings: [ProposerSlashing; MAX_PROPOSER_SLASHINGS],
  attester_slashings: [AttesterSlashing; MAX_ATTESTER_SLASHINGS],
  attestations: [Attestation; MAX_ATTESTATIONS],
  deposits: [Deposit; MAX_DEPOSITS],
  voluntary_exits: [SignedVoluntaryExit; MAX_VOLUNTARY_EXITS],
  sync_aggregate: SyncAggregate,
  execution_payload: ExecutionPayload,
}
 
/// The beacon state
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md#synccommittee)
struct BeaconState {
  genesis_time: u64,
  genesis_validators_root: H256,
  slot: Slot,
  fork: Fork,
  latest_block_header: BeaconBlockHeader,
  block_roots: [H256; SLOTS_PER_HISTORICAL_ROOT],
  state_roots: [H256; SLOTS_PER_HISTORICAL_ROOT],
  // historical roots contains a list of the root hash of the block_roots & state_roots of every
  // 256 epochs [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#historical-roots-updates)
  historical_roots: [H256; HISTORICAL_ROOTS_LIMIT],
  eth1_data: Eth1Data,
  eth1_data_votes: [Eth1Data; EPOCHS_PER_ETH1_VOTING_PERIOD * SLOTS_PER_EPOCH],
  eth1_deposit_index: u64,
  validators: [Validator; VALIDATOR_REGISTRY_LIMIT],
  balances: [Gwei; VALIDATOR_REGISTRY_LIMIT],
  randao_mixes: [H256; EPOCHS_PER_HISTORICAL_VECTOR],
  slashings: [Gwei; EPOCHS_PER_SLASHINGS_VECTOR],
  previous_epoch_participation: [ParticipationFlags; VALIDATOR_REGISTRY_LIMIT],
  current_epoch_participation: [ParticipationFlags; VALIDATOR_REGISTRY_LIMIT],
  justification_bits: Bitvector<JUSTIFICATION_BITS_LENGTH>,
  previous_justified_checkpoint: Checkpoint,
  current_justified_checkpoint: Checkpoint,
  finalized_checkpoint: Checkpoint,
  inactivity_scores: [u64; VALIDATOR_REGISTRY_LIMIT],
  current_sync_committee: SyncCommittee,
  next_sync_committee: SyncCommittee,
}
 
/// Associated execution block for the beacon chain header
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/bellatrix/beacon-chain.md#executionpayload)
struct ExecutionPayload {
  // Execution block header fields
  parent_hash: H256,
  // 'beneficiary' in the yellow paper
  fee_recipient: ExecutionAddress,
  state_root: H256,
  receipts_root: H256,
  logs_bloom: [u8; BYTES_PER_LOGS_BLOOM],
  // 'difficulty' in the yellow paper
  prev_randao: H256,
  // 'number' in the yellow paper
  block_number: u64,
  gas_limit: u64,
  gas_used: u64,
  // todo: is this same value we'd arrive at by deriving the timestamp from the beacon chain
  // header slot number?
  timestamp: u64,
  extra_data: [u8; MAX_EXTRA_DATA_BYTES],
  base_fee_per_gas: U256,
  // Extra payload fields
  // Hash of execution block
  block_hash: H256,
  transactions: [Transaction; MAX_TRANSACTIONS_PER_PAYLOAD],
}
 
/// The sync aggregate;
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md#syncaggregate)
struct SyncAggregate {
  sync_committee_bits: [SYNC_COMMITTEE_SIZE; u8],
  sync_committee_signature: BLSSignature,
}
 
/// The sync committee responsible for signing blocks
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/altair/beacon-chain.md#synccommittee)
struct SyncCommittee {
  pubkeys: [BLSPubkey; SYNC_COMMITTEE_SIZE],
  aggregate_pubkey: BLSPubkey,
}
 
/// The historical roots accumulator object.
/// [source](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#historicalbatch)
/// The `historical_roots` field on [`BeaconState`] is updated using this struct as defined by
/// https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#historical-roots-updates
struct HistoricalBatch {
  block_roots: [H256; SLOTS_PER_HISTORICAL_ROOT],
  state_roots: [H256; SLOTS_PER_HISTORICAL_ROOT],
}
 
/// This holds the relevant data required to prove the state root in the execution payload.
struct ExecutionPayloadProof {
  /// The state root in the `ExecutionPayload` which represents the commitment to
  /// the ethereum world state in the yellow paper.
  state_root: H256,
  /// the block number of the execution header.
  block_number: u64,
  /// merkle mutli proof for the state_root & block_number in the [`ExecutionPayload`].
  multi_proof: Vec<H256>,
  /// merkle proof for the `ExecutionPayload` in the [`BeaconBlockBody`].
  execution_payload_branch: Vec<H256>,
}
 
/// Holds the neccessary proofs required to verify a header in the `block_roots` field
/// either in [`BeaconState`] or [`HistoricalBatch`].
struct BlockRootsProof {
  /// Generalized index of the header in the `block_roots` list.
  block_header_index: u64,
  /// The proof for the header, needed to reconstruct `hash_tree_root(state.block_roots)`
  block_header_branch: Vec<H256>,
}
 
/// The block header ancestry proof, this is an enum because the header may either exist in
/// `state.block_roots` or `state.historical_roots`.
enum AncestryProof {
  /// This variant defines the proof data for a beacon chain header in the `state.block_roots`
  BlockRoots {
    /// Proof for the header in `state.block_roots`
    block_roots_proof: BlockRootsProof,
    /// The proof for the reconstructed `hash_tree_root(state.block_roots)` in [`BeaconState`]
    block_roots_branch: Vec<H256>,
  },
  /// This variant defines the neccessary proofs for a beacon chain header in the
  /// `state.historical_roots`.
  HistoricalRoots {
    /// Proof for the header in `historical_batch.block_roots`
    block_roots_proof: BlockRootsProof,
    /// The proof for the `historical_batch.block_roots`, needed to reconstruct
    /// `hash_tree_root(historical_batch)`
    historical_batch_proof: Vec<H256>,
    /// The proof for the `hash_tree_root(historical_batch)` in `state.historical_roots`
    historical_roots_proof: Vec<H256>,
    /// The generalized index for the historical_batch in `state.historical_roots`.
    historical_roots_index: u64,
    /// The proof for the reconstructed `hash_tree_root(state.historical_roots)` in
    /// [`BeaconState`]
    historical_roots_branch: Vec<H256>,
  },
}
 
/// This defines the neccesary data needed to prove ancestor blocks, relative to the finalized
/// header.
struct AncestorBlock {
  /// The actual beacon chain header
  header: BeaconBlockHeader,
  /// Associated execution header proofs
  execution_payload: ExecutionPayloadProof,
  /// Ancestry proofs of the beacon chain header.
  ancestry_proof: AncenstryProof,
}
 
/// Holds the latest sync committee as well as an ssz proof for it's existence
/// in a finalized header.
struct SyncCommitteeUpdate {
  // actual sync committee
  next_sync_committee: SyncCommittee,
  // sync committee, ssz merkle proof.
  next_sync_committee_branch: [H256; NEXT_SYNC_COMMITTEE_INDEX.floor_log2()],
}
 
/// Minimum state required by the light client to validate new sync committee attestations
struct ConsensusState {
  /// The latest recorded finalized header
  finalized_header: BeaconBlockHeader,
  // Sync committees corresponding to the finalized header
  current_sync_committee: SyncCommittee,
  next_sync_committee: SyncCommittee,
}
 
/// Data required to advance the state of the light client.
struct ConsenusProof {
  /// the header that the sync committee signed
  attested_header: BeaconBlockHeader,
  /// the sync committee has potentially changed, here's an ssz proof for that.
  sync_committee_update: Option<SyncCommitteeUpdate>,
  /// the actual header which was finalized by the ethereum attestation protocol.
  finalized_header: BeaconBlockHeader,
  /// execution payload of the finalized header
  execution_payload: ExecutionPayloadProof,
  /// the ssz merkle proof for this header in the attested header, finalized headers lag by 2 epochs.
  finality_branch: [H256; FINALIZED_ROOT_INDEX.floor_log2()],
  /// signature & participation bits
  sync_aggregate: SyncAggregate,
  /// slot at which signature was produced
  signature_slot: Slot,
  /// ancestors of the finalized block to be verified, may be empty.
  ancestor_blocks: Vec<AncestorBlock>,
}

/// This function simply verifies a sync committee's attestation & it's finalized counterpart.
fn verify_sync_committee_attestation(
  state: ConsensusState,
  update: ConsenusProof,
) -> Result<(), Error> {
  // Verify sync committee has super majority participants
  let sync_committee_bits = update.sync_aggregate.sync_committee_bits;
  let sync_aggregate_participants = sync_committee_bits.iter().sum();
  if sync_aggregate_participants * 3 >= sync_committee_bits.clone().len() as u64 * 2 {
    Err(Error::SyncCommitteeParticiapntsTooLow)?
  }
 
  // Verify update does not skip a sync committee period
  let is_valid_update = update.signature_slot > update.attested_header.slot &&
    update.attested_header.slot >= update.finalized_header.slot;
  if !is_valid_update {
    Err(Error::InvalidUpdate)?
  }
 
  let state_period = compute_sync_committee_period_at_slot(state.finalized_header.slot);
  let update_signature_period = compute_sync_committee_period_at_slot(update.signature_slot);
  if !(state_period..=state_period + 1).contains(update_signature_period) {
    Err(Error::InvalidUpdate)?
  }
 
  // Verify update is relevant
  let update_attested_period = compute_sync_committee_period_at_slot(update.attested_header.slot);
  let update_has_next_sync_committee =
    update.sync_committee_update.is_some() && update_attested_period == state_period;
 
  if !(update.attested_header.slot > state.finalized_header.slot || update_has_next_sync_committee)
  {
    Err(Error::InvalidUpdate)?
  }
 
  // Verify sync committee aggregate signature
  let sync_committee = if update_signature_period == state_period {
    state.current_sync_committee
  } else {
    state.next_sync_committee
  };
 
  let participant_pubkeys = sync_committee_bits
    .iter()
    .zip(sync_committee_pubkeys.iter())
    .filter_map(|(bit, key)| if bit == 1 { Some(key) } else { None })
    .collect::<Vec<_>>();
 
  let fork_version = compute_fork_version(compute_epoch_at_slot(update.signature_slot));
  let domain = compute_domain(DOMAIN_SYNC_COMMITTEE, fork_version, GENESIS_VALIDATORS_ROOT);
  let signing_root = compute_signing_root(update.attested_header, domain);
 
  bls::fast_aggregate_verify(
    participant_pubkeys,
    signing_root,
    sync_aggregate.sync_committee_signature,
  )?;
 
  // Verify that the `finality_branch` confirms `finalized_header`
  // to match the finalized checkpoint root saved in the state of `attested_header`.
  // Note that the genesis finalized checkpoint root is represented as a zero hash.
  let finalized_root = hash_tree_root(update.finalized_header);
  is_valid_merkle_branch(
    finalized_root,
    update.finality_branch,
    FINALIZED_ROOT_INDEX.floor_log2(),
    get_subtree_index(FINALIZED_ROOT_INDEX),
    update.attested_header.state_root,
  )?;
 
  // verify the associated execution header of the finalized beacon header.
  let execution_payload = update.execution_payload;
  let execution_payload_root = calculate_multi_merkle_root(
    &[execution_payload.state_root, hash_tree_root(execution_payload.block_number)],
    execution_payload.multi_proof,
    &[EXECUTION_PAYLOAD_STATE_ROOT_INDEX, EXECUTION_PAYLOAD_BLOCK_NUMBER_INDEX],
  );
 
  is_valid_merkle_branch(
    execution_payload_root,
    execution_payload.execution_payload_branch,
    EXECUTION_PAYLOAD_INDEX.floor_log2(),
    get_subtree_index(EXECUTION_PAYLOAD_INDEX),
    update.finalized_header.body_root,
  )?;
 
  if let Some(sync_committee_update) = update.sync_committee_update {
    if update_attested_period == state_period {
      if sync_committee_update.next_sync_committee != state.next_sync_committee {
        Err(Error::InvalidUpdate)?
      }
    }
    is_valid_merkle_branch(
      hash_tree_root(sync_committee_update.next_sync_committee),
      sync_committee_update.next_sync_committee_branch,
      NEXT_SYNC_COMMITTEE_INDEX.floor_log2(),
      get_subtree_index(NEXT_SYNC_COMMITTEE_INDEX),
      update.attested_header.state_root,
    )?;
  }
 
  // verify the ancestry proofs
  for ancestor in update.ancestor_blocks {
    match ancestor.ancestry_proof {
      AncestryProof::BlockRoots { block_roots_proof, block_roots_branch } => {
        let block_roots_root = calculate_merkle_root(
          hash_tree_root(ancestor.header),
          block_roots_proof.block_header_branch,
          block_roots_proof.block_header_index,
        );
 
        is_valid_merkle_branch(
          block_roots_root,
          block_roots_branch,
          BLOCK_ROOTS_INDEX.floor_log2(),
          get_subtree_index(BLOCK_ROOTS_INDEX),
          update.finalized_header.state_root,
        )?;
      },
      AncestryProof::HistoricalRoots {
        block_roots_proof,
        historical_batch_proof,
        historical_roots_proof,
        historical_roots_index,
        historical_roots_branch,
      } => {
        let block_roots_root = calculate_merkle_root(
          hash_tree_root(ancestor.header),
          block_roots_proof.block_header_branch,
          block_roots_proof.block_header_index,
        );
 
        let historical_batch_root = calculate_merkle_root(
          block_roots_root,
          historical_batch_proof,
          HISTORICAL_BATCH_BLOCK_ROOTS_INDEX,
        );
 
        let historical_roots_root = calculate_merkle_root(
          historical_batch_root,
          historical_roots_proof,
          historical_roots_index,
        );
 
        is_valid_merkle_branch(
          historical_roots_root,
          historical_roots_branch,
          HISTORICAL_ROOTS_INDEX.floor_log2(),
          get_subtree_index(HISTORICAL_ROOTS_INDEX),
          update.finalized_header.state_root,
        )?;
      },
    };
 
    // verify the associated execution paylaod header.
    let execution_payload = ancestor.execution_payload;
    let execution_payload_root = calculate_multi_merkle_root(
      &[execution_payload.state_root, hash_tree_root(execution_payload.block_number)],
      execution_payload.multi_proof,
      &[EXECUTION_PAYLOAD_STATE_ROOT_INDEX, EXECUTION_PAYLOAD_BLOCK_NUMBER_INDEX],
    );
 
    is_valid_merkle_branch(
      execution_payload_root,
      execution_payload.execution_payload_branch,
      EXECUTION_PAYLOAD_INDEX.floor_log2(),
      get_subtree_index(EXECUTION_PAYLOAD_INDEX),
      ancestor.header.body_root,
    )?;
  }
 
  Ok(())
}