axiom_eth/storage/
mod.rs

1use ethers_core::types::Chain;
2use getset::Getters;
3use halo2_base::{
4    gates::{flex_gate::threads::parallelize_core, GateChip, RangeChip},
5    safe_types::{SafeAddress, SafeBytes32, SafeTypeChip},
6    AssignedValue, Context,
7};
8use itertools::Itertools;
9
10use crate::{
11    block_header::{EthBlockHeaderChip, EthBlockHeaderTrace, EthBlockHeaderWitness},
12    keccak::KeccakChip,
13    mpt::{MPTChip, MPTProof, MPTProofWitness},
14    rlc::{
15        chip::RlcChip,
16        circuit::builder::{RlcCircuitBuilder, RlcContextPair},
17        types::RlcTrace,
18        FIRST_PHASE,
19    },
20    rlp::{
21        types::{RlpArrayWitness, RlpFieldWitness},
22        RlpChip,
23    },
24    utils::{bytes_be_to_u128, uint_to_bytes_be, AssignedH256},
25    Field,
26};
27
28pub mod circuit;
29#[cfg(all(test, feature = "providers"))]
30mod tests;
31
32/*
33| Account State Field     | Max bytes   |
34|-------------------------|-------------|
35| nonce                   | ≤8          |
36| balance                 | ≤12         |
37| storageRoot             | 32          |
38| codeHash                | 32          |
39
40account nonce is uint64 by https://eips.ethereum.org/EIPS/eip-2681
41*/
42pub const NUM_ACCOUNT_STATE_FIELDS: usize = 4;
43pub const ACCOUNT_STATE_FIELDS_MAX_BYTES: [usize; NUM_ACCOUNT_STATE_FIELDS] = [8, 12, 32, 32];
44#[allow(dead_code)]
45pub const ACCOUNT_STATE_FIELD_IS_VAR_LEN: [bool; NUM_ACCOUNT_STATE_FIELDS] =
46    [true, true, false, false];
47pub(crate) const ACCOUNT_PROOF_VALUE_MAX_BYTE_LEN: usize = 90;
48pub(crate) const STORAGE_PROOF_VALUE_MAX_BYTE_LEN: usize = 33;
49#[allow(dead_code)]
50pub(crate) const STORAGE_PROOF_KEY_MAX_BYTE_LEN: usize = 32;
51
52/// Stores Account rlcs to be used in later functions. Is returned by `parse_account_proof_phase1`.
53#[derive(Clone, Debug)]
54pub struct EthAccountTrace<F: Field> {
55    pub nonce_trace: RlcTrace<F>,
56    pub balance_trace: RlcTrace<F>,
57    pub storage_root_trace: RlcTrace<F>,
58    pub code_hash_trace: RlcTrace<F>,
59}
60
61/// Stores Account information to be used in later functions. Is returned by `parse_account_proof_phase0`.
62#[derive(Clone, Debug, Getters)]
63pub struct EthAccountWitness<F: Field> {
64    pub address: SafeAddress<F>,
65    #[getset(get = "pub")]
66    pub(crate) array_witness: RlpArrayWitness<F>,
67    #[getset(get = "pub")]
68    pub(crate) mpt_witness: MPTProofWitness<F>,
69}
70
71impl<F: Field> EthAccountWitness<F> {
72    pub fn get_nonce(&self) -> &RlpFieldWitness<F> {
73        &self.array_witness.field_witness[0]
74    }
75    pub fn get_balance(&self) -> &RlpFieldWitness<F> {
76        &self.array_witness.field_witness[1]
77    }
78    pub fn get_storage_root(&self) -> &RlpFieldWitness<F> {
79        &self.array_witness.field_witness[2]
80    }
81    pub fn get_code_hash(&self) -> &RlpFieldWitness<F> {
82        &self.array_witness.field_witness[3]
83    }
84}
85
86/// Stores the rlc of a value in a storage slot. Is returned by `parse_storage_proof_phase1`.
87#[derive(Clone, Debug)]
88pub struct EthStorageTrace<F: Field> {
89    pub value_trace: RlcTrace<F>,
90}
91
92/// Stores storage slot information as well as a proof of inclusion to be verified in parse_storage_phase1. Is returned
93/// by `parse_storage_phase0`.
94#[derive(Clone, Debug, Getters)]
95pub struct EthStorageWitness<F: Field> {
96    pub slot: SafeBytes32<F>,
97    #[getset(get = "pub")]
98    pub(crate) value_witness: RlpFieldWitness<F>,
99    #[getset(get = "pub")]
100    pub(crate) mpt_witness: MPTProofWitness<F>,
101}
102
103///  Stores the rlcs for an account in a block, and the rlcs of slots in the account. Is returned by `parse_eip1186_proofs_from_block_phase1`.
104#[derive(Clone, Debug)]
105pub struct EthBlockAccountStorageTrace<F: Field> {
106    pub block_trace: EthBlockHeaderTrace<F>,
107    pub acct_trace: EthAccountTrace<F>,
108    pub storage_trace: Vec<EthStorageTrace<F>>,
109}
110
111///  Stores a block, an account, and multiple storage witnesses. Is returned by `parse_eip1186_proofs_from_block_phase0`.
112#[derive(Clone, Debug)]
113pub struct EthBlockAccountStorageWitness<F: Field> {
114    pub block_witness: EthBlockHeaderWitness<F>,
115    pub acct_witness: EthAccountWitness<F>,
116    pub storage_witness: Vec<EthStorageWitness<F>>,
117}
118
119/// Returns public instances from `parse_eip1186_proofs_from_block_phase0`.
120#[derive(Clone, Debug)]
121pub struct EIP1186ResponseDigest<F: Field> {
122    pub block_hash: AssignedH256<F>,
123    pub block_number: AssignedValue<F>,
124    pub address: AssignedValue<F>,
125    // the value U256 is interpreted as H256 (padded with 0s on left)
126    /// Pairs of (slot, value) where value is a left padded with 0s to fixed width 32 bytes
127    pub slots_values: Vec<(AssignedH256<F>, AssignedH256<F>)>,
128    pub address_is_empty: AssignedValue<F>,
129    pub slot_is_empty: Vec<AssignedValue<F>>,
130}
131
132/// Chip to prove correctness of account and storage proofs
133pub struct EthStorageChip<'chip, F: Field> {
134    pub mpt: &'chip MPTChip<'chip, F>,
135    /// The network to use for block header decoding. Must be provided if using functions that prove into block header (as opposed to state / storage root)
136    pub network: Option<Chain>,
137}
138
139impl<'chip, F: Field> EthStorageChip<'chip, F> {
140    pub fn new(mpt: &'chip MPTChip<'chip, F>, network: Option<Chain>) -> Self {
141        Self { mpt, network }
142    }
143
144    pub fn gate(&self) -> &GateChip<F> {
145        self.mpt.gate()
146    }
147
148    pub fn range(&self) -> &RangeChip<F> {
149        self.mpt.range()
150    }
151
152    pub fn rlc(&self) -> &RlcChip<F> {
153        self.mpt.rlc()
154    }
155
156    pub fn rlp(&self) -> RlpChip<F> {
157        self.mpt.rlp()
158    }
159
160    pub fn keccak(&self) -> &KeccakChip<F> {
161        self.mpt.keccak()
162    }
163    /// Does inclusion/exclusion proof of `key = keccak(addr)` into an alleged MPT state trie. Alleged means the proof is with respect to an alleged stateRoot.
164    /// RLP decodes the ethereumAccount.
165    ///
166    /// There is one global state trie, and it is updated every time a client processes a block. In it, a path is always: keccak256(ethereumAddress) and a value is always: rlp(ethereumAccount). More specifically an ethereum account is a 4 item array of [nonce,balance,storageRoot,codeHash].
167    ///
168    /// Does input validation of `proof` (e.g., checking witnesses are bytes).
169    pub fn parse_account_proof_phase0(
170        &self,
171        ctx: &mut Context<F>,
172        address: SafeAddress<F>,
173        proof: MPTProof<F>,
174    ) -> EthAccountWitness<F> {
175        assert_eq!(32, proof.key_bytes.len());
176
177        // check key is keccak(addr)
178        let hash_query = self.keccak().keccak_fixed_len(ctx, address.as_ref().to_vec());
179        let hash_addr = hash_query.output_bytes.as_ref();
180
181        for (byte, key) in hash_addr.iter().zip_eq(proof.key_bytes.iter()) {
182            ctx.constrain_equal(byte, key);
183        }
184
185        // parse value RLP([nonce, balance, storage_root, code_hash])
186        let array_witness = self.rlp().decompose_rlp_array_phase0(
187            ctx,
188            proof.value_bytes.clone(),
189            &ACCOUNT_STATE_FIELDS_MAX_BYTES,
190            false,
191        );
192        // Check MPT inclusion for:
193        // keccak(addr) => RLP([nonce, balance, storage_root, code_hash])
194        let mpt_witness = self.mpt.parse_mpt_inclusion_phase0(ctx, proof);
195
196        EthAccountWitness { address, array_witness, mpt_witness }
197    }
198
199    /// SecondPhase of account proof parsing.
200    pub fn parse_account_proof_phase1(
201        &self,
202        (ctx_gate, ctx_rlc): RlcContextPair<F>,
203        witness: EthAccountWitness<F>,
204    ) -> EthAccountTrace<F> {
205        // Comments below just to log what load_rlc_cache calls are done in the internal functions:
206        // load_rlc_cache bit_length(2*mpt_witness.key_byte_len)
207        self.mpt.parse_mpt_inclusion_phase1((ctx_gate, ctx_rlc), witness.mpt_witness);
208        // load rlc_cache bit_length(array_witness.rlp_array.len())
209        let array_trace: [_; 4] = self
210            .rlp()
211            .decompose_rlp_array_phase1((ctx_gate, ctx_rlc), witness.array_witness, false)
212            .field_trace
213            .try_into()
214            .unwrap();
215        let [nonce_trace, balance_trace, storage_root_trace, code_hash_trace] =
216            array_trace.map(|trace| trace.field_trace);
217        EthAccountTrace { nonce_trace, balance_trace, storage_root_trace, code_hash_trace }
218    }
219
220    /// Does multiple calls to [`parse_account_proof_phase0`] in parallel.
221    pub fn parse_account_proofs_phase0(
222        &self,
223        builder: &mut RlcCircuitBuilder<F>,
224        addr_proofs: Vec<(SafeAddress<F>, MPTProof<F>)>,
225    ) -> Vec<EthAccountWitness<F>> {
226        parallelize_core(builder.base.pool(0), addr_proofs, |ctx, (addr, proof)| {
227            self.parse_account_proof_phase0(ctx, addr, proof)
228        })
229    }
230
231    /// SecondPhase of account proofs parsing.
232    pub fn parse_account_proofs_phase1(
233        &self,
234        builder: &mut RlcCircuitBuilder<F>,
235        acct_witness: Vec<EthAccountWitness<F>>,
236    ) -> Vec<EthAccountTrace<F>> {
237        // rlc cache is loaded globally when `builder` was constructed; no longer done here to avoid concurrency issues
238        builder.parallelize_phase1(acct_witness, |(ctx_gate, ctx_rlc), witness| {
239            self.parse_account_proof_phase1((ctx_gate, ctx_rlc), witness)
240        })
241    }
242
243    /// Does inclusion/exclusion proof of `keccak(slot)` into an alleged MPT storage trie. Alleged means the proof is with respect to an alleged storageRoot.
244    ///
245    /// storageRoot: A 256-bit hash of the root node of a Merkle Patricia tree that encodes the storage contents of the account (a mapping between 256-bit integer values), encoded into the trie as a mapping from the Keccak 256-bit hash of the 256-bit integer keys to the RLP-encoded 256-bit integer values. The hash is formally denoted σ[a]_s.
246    ///
247    /// Will do input validation on `proof` (e.g., checking witnesses are bytes).
248    pub fn parse_storage_proof_phase0(
249        &self,
250        ctx: &mut Context<F>,
251        slot: SafeBytes32<F>,
252        proof: MPTProof<F>,
253    ) -> EthStorageWitness<F> {
254        assert_eq!(32, proof.key_bytes.len());
255
256        // check key is keccak(slot)
257        let hash_query = self.keccak().keccak_fixed_len(ctx, slot.as_ref().to_vec());
258        let hash_bytes = hash_query.output_bytes.as_ref();
259
260        for (hash, key) in hash_bytes.iter().zip_eq(proof.key_bytes.iter()) {
261            ctx.constrain_equal(hash, key);
262        }
263
264        // parse slot value
265        let value_witness =
266            self.rlp().decompose_rlp_field_phase0(ctx, proof.value_bytes.clone(), 32);
267        // check MPT inclusion
268        let mpt_witness = self.mpt.parse_mpt_inclusion_phase0(ctx, proof);
269        EthStorageWitness { slot, value_witness, mpt_witness }
270    }
271
272    /// SecondPhase of storage proof parsing.
273    pub fn parse_storage_proof_phase1(
274        &self,
275        (ctx_gate, ctx_rlc): RlcContextPair<F>,
276        witness: EthStorageWitness<F>,
277    ) -> EthStorageTrace<F> {
278        // Comments below just to log what load_rlc_cache calls are done in the internal functions:
279        // load_rlc_cache bit_length(2*mpt_witness.key_byte_len)
280        self.mpt.parse_mpt_inclusion_phase1((ctx_gate, ctx_rlc), witness.mpt_witness);
281        // load rlc_cache bit_length(value_witness.rlp_field.len())
282        let value_trace =
283            self.rlp().decompose_rlp_field_phase1((ctx_gate, ctx_rlc), witness.value_witness);
284        let value_trace = value_trace.field_trace;
285        debug_assert_eq!(value_trace.max_len, 32);
286        EthStorageTrace { value_trace }
287    }
288
289    /// Does multiple calls to [`parse_storage_proof_phase0`] in parallel.
290    pub fn parse_storage_proofs_phase0(
291        &self,
292        builder: &mut RlcCircuitBuilder<F>,
293        slot_proofs: Vec<(SafeBytes32<F>, MPTProof<F>)>,
294    ) -> Vec<EthStorageWitness<F>> {
295        parallelize_core(builder.base.pool(0), slot_proofs, |ctx, (slot, proof)| {
296            self.parse_storage_proof_phase0(ctx, slot, proof)
297        })
298    }
299
300    /// SecondPhase of account proofs parsing.
301    pub fn parse_storage_proofs_phase1(
302        &self,
303        builder: &mut RlcCircuitBuilder<F>,
304        storage_witness: Vec<EthStorageWitness<F>>,
305    ) -> Vec<EthStorageTrace<F>> {
306        // rlc cache is loaded globally when `builder` was constructed; no longer done here to avoid concurrency issues
307        builder.parallelize_phase1(storage_witness, |(ctx_gate, ctx_rlc), witness| {
308            self.parse_storage_proof_phase1((ctx_gate, ctx_rlc), witness)
309        })
310    }
311
312    /// Does inclusion/exclusion proof of `key = keccak(addr)` into an alleged MPT state trie. Alleged means the proof is with respect to an alleged stateRoot.
313    ///
314    /// RLP decodes the ethereumAccount, which in particular gives the storageRoot.
315    ///
316    /// Does (multiple) inclusion/exclusion proof of `keccak(slot)` into the MPT storage trie with root storageRoot.
317    pub fn parse_eip1186_proofs_phase0(
318        &self,
319        builder: &mut RlcCircuitBuilder<F>,
320        addr: SafeAddress<F>,
321        acct_pf: MPTProof<F>,
322        storage_pfs: Vec<(SafeBytes32<F>, MPTProof<F>)>, // (slot_bytes, storage_proof)
323    ) -> (EthAccountWitness<F>, Vec<EthStorageWitness<F>>) {
324        // TODO: spawn separate thread for account proof; just need to get storage_root first somehow
325        let ctx = builder.base.main(FIRST_PHASE);
326        let acct_trace = self.parse_account_proof_phase0(ctx, addr, acct_pf);
327        // ctx dropped
328        let storage_root = &acct_trace.get_storage_root().field_cells;
329        let storage_trace =
330            parallelize_core(builder.base.pool(0), storage_pfs, |ctx, (slot, storage_pf)| {
331                let witness = self.parse_storage_proof_phase0(ctx, slot, storage_pf);
332                // check MPT root is storage_root
333                for (pf_byte, byte) in
334                    witness.mpt_witness.root_hash_bytes.iter().zip_eq(storage_root.iter())
335                {
336                    ctx.constrain_equal(pf_byte, byte);
337                }
338                witness
339            });
340        (acct_trace, storage_trace)
341    }
342
343    /// SecondPhase of `parse_eip1186_proofs_phase0`
344    pub fn parse_eip1186_proofs_phase1(
345        &self,
346        builder: &mut RlcCircuitBuilder<F>,
347        (acct_witness, storage_witness): (EthAccountWitness<F>, Vec<EthStorageWitness<F>>),
348    ) -> (EthAccountTrace<F>, Vec<EthStorageTrace<F>>) {
349        let (ctx_gate, ctx_rlc) = builder.rlc_ctx_pair();
350        let acct_trace = self.parse_account_proof_phase1((ctx_gate, ctx_rlc), acct_witness);
351        let storage_trace = self.parse_storage_proofs_phase1(builder, storage_witness);
352
353        (acct_trace, storage_trace)
354    }
355
356    /// Proves (multiple) storage proofs into storageRoot, prove account proof of storageRoot into stateRoot, and proves stateRoot is an RLP decoded block header.
357    /// Computes the block hash by hashing the RLP encoded block header.
358    /// In other words, proves block, account, storage with respect to an alleged block hash.
359    // inputs have H256 represented in (hi,lo) format as two u128s
360    // block number and slot values can be derived from the final trace output
361    pub fn parse_eip1186_proofs_from_block_phase0(
362        &self,
363        builder: &mut RlcCircuitBuilder<F>,
364        input: EthBlockStorageInputAssigned<F>,
365    ) -> (EthBlockAccountStorageWitness<F>, EIP1186ResponseDigest<F>) {
366        let ctx = builder.base.main(FIRST_PHASE);
367        let address = input.storage.address;
368        let block_header = input.block_header;
369        let block_witness = {
370            let block_header_chip =
371                EthBlockHeaderChip::new_from_network(self.rlp(), self.network.unwrap());
372            block_header_chip.decompose_block_header_phase0(ctx, self.keccak(), &block_header)
373        };
374
375        let state_root = &block_witness.get_state_root().field_cells;
376        let block_hash_hi_lo = block_witness.get_block_hash_hi_lo();
377
378        // compute block number from big-endian bytes
379        let block_number = block_witness.get_number_value(ctx, self.gate());
380
381        // verify account + storage proof
382        let addr_bytes = uint_to_bytes_be(ctx, self.range(), &address, 20);
383        let (slots, storage_pfs): (Vec<_>, Vec<_>) = input
384            .storage
385            .storage_pfs
386            .into_iter()
387            .map(|(slot, storage_pf)| {
388                let slot_bytes =
389                    slot.iter().map(|u128| uint_to_bytes_be(ctx, self.range(), u128, 16)).concat();
390                (slot, (slot_bytes.try_into().unwrap(), storage_pf))
391            })
392            .unzip();
393        // drop ctx
394        let (acct_witness, storage_witness) = self.parse_eip1186_proofs_phase0(
395            builder,
396            addr_bytes.try_into().unwrap(),
397            input.storage.acct_pf,
398            storage_pfs,
399        );
400
401        let ctx = builder.base.main(FIRST_PHASE);
402        // check MPT root of acct_witness is state root
403        for (pf_byte, byte) in
404            acct_witness.mpt_witness.root_hash_bytes.iter().zip_eq(state_root.iter())
405        {
406            ctx.constrain_equal(pf_byte, byte);
407        }
408
409        let slots_values = slots
410            .into_iter()
411            .zip(storage_witness.iter())
412            .map(|(slot, witness)| {
413                // get value as U256 from RLP decoding, convert to H256, then to hi-lo
414                let value_bytes = witness.value_witness.field_cells.clone();
415                let value_bytes_len = witness.value_witness.field_len;
416                let var_bytes =
417                    SafeTypeChip::unsafe_to_var_len_bytes_vec(value_bytes, value_bytes_len, 32);
418                let value_bytes = var_bytes.left_pad_to_fixed(ctx, self.gate());
419                let value: [_; 2] =
420                    bytes_be_to_u128(ctx, self.gate(), value_bytes.bytes()).try_into().unwrap();
421                (slot, value)
422            })
423            .collect_vec();
424        let digest = EIP1186ResponseDigest {
425            block_hash: block_hash_hi_lo,
426            block_number,
427            address,
428            slots_values,
429            address_is_empty: acct_witness.mpt_witness.slot_is_empty,
430            slot_is_empty: storage_witness
431                .iter()
432                .map(|witness| witness.mpt_witness.slot_is_empty)
433                .collect_vec(),
434        };
435        (EthBlockAccountStorageWitness { block_witness, acct_witness, storage_witness }, digest)
436    }
437
438    pub fn parse_eip1186_proofs_from_block_phase1(
439        &self,
440        builder: &mut RlcCircuitBuilder<F>,
441        witness: EthBlockAccountStorageWitness<F>,
442    ) -> EthBlockAccountStorageTrace<F> {
443        let block_trace = {
444            let block_header_chip =
445                EthBlockHeaderChip::new_from_network(self.rlp(), self.network.unwrap());
446            block_header_chip
447                .decompose_block_header_phase1(builder.rlc_ctx_pair(), witness.block_witness)
448        };
449        let (acct_trace, storage_trace) = self
450            .parse_eip1186_proofs_phase1(builder, (witness.acct_witness, witness.storage_witness));
451        EthBlockAccountStorageTrace { block_trace, acct_trace, storage_trace }
452    }
453}
454
455/// Account and storage proof inputs in compressed form
456#[derive(Clone, Debug)]
457pub struct EthStorageInputAssigned<F: Field> {
458    pub address: AssignedValue<F>, // U160
459    pub acct_pf: MPTProof<F>,
460    pub storage_pfs: Vec<(AssignedH256<F>, MPTProof<F>)>, // (slot, proof) where slot is H256 as (u128, u128)
461}
462
463#[derive(Clone, Debug)]
464pub struct EthBlockStorageInputAssigned<F: Field> {
465    // block_hash: AssignedH256<F>, // H256 as (u128, u128)
466    /// The RLP encoded block header for the block that alleged contains the stateRoot from `storage`.
467    pub block_header: Vec<AssignedValue<F>>,
468    /// Account proof and (multiple) storage proofs, with respect to an alleged stateRoot.
469    pub storage: EthStorageInputAssigned<F>,
470}
axiom_eth/storage/mod.rs

axiom_eth/storage/
mod.rs
