bal_source/
proof.rs

1//! Merkle-proof verification for bootstrap values. This is what turns an
2//! `eth_getProof` answer from "the RPC said so" into a value anchored to a
3//! block header's `state_root` — promise #2 for the only records that do not
4//! come from a BAL.
5
6use crate::AccountProof;
7use alloy_primitives::{keccak256, B256, U256};
8use alloy_trie::{proof::verify_proof, Nibbles, TrieAccount, EMPTY_ROOT_HASH};
9
10/// Why a proof was rejected. Any of these means the value must not be stored.
11#[derive(Debug, thiserror::Error)]
12pub enum ProofError {
13    /// The account leaf does not hash up to the header's state root.
14    #[error("account proof invalid against state_root {root}: {reason}")]
15    Account {
16        /// State root the proof was checked against.
17        root: B256,
18        /// Trie verifier's reason.
19        reason: String,
20    },
21    /// A storage leaf does not hash up to the account's storage root.
22    #[error("storage proof for slot {slot} invalid against storage_root {root}: {reason}")]
23    Storage {
24        /// Slot whose proof failed.
25        slot: B256,
26        /// Storage root the proof was checked against.
27        root: B256,
28        /// Trie verifier's reason.
29        reason: String,
30    },
31    /// The response omitted a requested slot.
32    #[error("proof did not include slot {0}")]
33    MissingSlot(B256),
34    /// The response carried a slot that was not requested.
35    #[error("proof included unrequested slot {0}")]
36    UnexpectedSlot(B256),
37}
38
39/// Check that a proof answers exactly the `requested` slots (any order, no
40/// extras). A node that answers for other slots must not be able to plant
41/// values under the wrong key.
42pub fn check_requested(requested: &[B256], proof: &AccountProof) -> Result<(), ProofError> {
43    let got: std::collections::HashSet<B256> = proof.storage_proofs.iter().map(|p| p.key).collect();
44    for r in requested {
45        if !got.contains(r) {
46            return Err(ProofError::MissingSlot(*r));
47        }
48    }
49    let want: std::collections::HashSet<B256> = requested.iter().copied().collect();
50    for g in &got {
51        if !want.contains(g) {
52            return Err(ProofError::UnexpectedSlot(*g));
53        }
54    }
55    Ok(())
56}
57
58/// Verify the account leaf against `state_root`, then every storage proof
59/// against the account's `storage_hash`. Returns `(slot, value)` pairs in the
60/// order they appear in the proof. A zero value is proven by *absence*
61/// (exclusion proof), which is exactly the distinction promise #3 needs.
62pub fn verify_account_proof(
63    state_root: B256,
64    proof: &AccountProof,
65) -> Result<Vec<(B256, U256)>, ProofError> {
66    let account = TrieAccount {
67        nonce: proof.nonce,
68        balance: proof.balance,
69        storage_root: proof.storage_hash,
70        code_hash: proof.code_hash,
71    };
72    // A non-existent account is proven by exclusion; its storage root is empty.
73    let account_exists = !(proof.nonce == 0
74        && proof.balance.is_zero()
75        && proof.storage_hash == EMPTY_ROOT_HASH
76        && proof.code_hash == alloy_primitives::KECCAK256_EMPTY);
77    let expected_account = account_exists.then(|| alloy_rlp::encode(account));
78    verify_proof(
79        state_root,
80        Nibbles::unpack(keccak256(proof.address)),
81        expected_account,
82        proof.account_proof.iter(),
83    )
84    .map_err(|e| ProofError::Account {
85        root: state_root,
86        reason: e.to_string(),
87    })?;
88
89    let mut out = Vec::with_capacity(proof.storage_proofs.len());
90    for sp in &proof.storage_proofs {
91        let expected = (!sp.value.is_zero()).then(|| alloy_rlp::encode(sp.value));
92        verify_proof(
93            proof.storage_hash,
94            Nibbles::unpack(keccak256(sp.key)),
95            expected,
96            sp.proof.iter(),
97        )
98        .map_err(|e| ProofError::Storage {
99            slot: sp.key,
100            root: proof.storage_hash,
101            reason: e.to_string(),
102        })?;
103        out.push((sp.key, sp.value));
104    }
105    Ok(out)
106}
bal_source/proof.rs

bal_source/
proof.rs
