Skip to main content

forge/cmd/
equivalence.rs

1use alloy_dyn_abi::DynSolValue;
2use alloy_json_abi::Function;
3use alloy_network::TransactionBuilder;
4use alloy_primitives::{
5    Address, B256, Bytes, KECCAK256_EMPTY, Log, TxKind, U256, hex, map::HashMap,
6};
7use clap::{Parser, ValueHint};
8use evm2::{EvmFeatures, bytecode::Bytecode, interpreter::InstrStop};
9use eyre::{Result, WrapErr, bail};
10use foundry_common::{sh_println, shell};
11use foundry_config::{Config, SymbolicStorageLayout};
12use foundry_evm::{
13    backend::Backend,
14    constants::{CALLER, TEST_CONTRACT_ADDRESS},
15    core::evm::EthEvmNetwork,
16    executors::{Executor, ExecutorBuilder},
17    opts::EvmOpts,
18};
19use foundry_evm_symbolic::{
20    ExecutorView, SymbolicEquivalenceEnv, SymbolicEquivalenceInput, SymbolicEquivalenceResult,
21    SymbolicExecutor, SymbolicStats, SymbolicStorageAssignment,
22};
23use serde_json::json;
24use std::{collections::BTreeSet, path::PathBuf};
25
26/// CLI arguments for `forge equivalence`.
27#[derive(Clone, Debug, Parser)]
28pub struct EquivalenceArgs {
29    /// Runtime bytecode of the first contract, as hex.
30    #[arg(long, value_name = "HEX", required_unless_present = "code_a_file")]
31    pub code_a: Option<String>,
32
33    /// File holding the runtime bytecode of the first contract, as hex.
34    #[arg(long, value_name = "PATH", value_hint = ValueHint::FilePath, conflicts_with = "code_a")]
35    pub code_a_file: Option<PathBuf>,
36
37    /// Runtime bytecode of the second contract, as hex.
38    #[arg(long, value_name = "HEX", required_unless_present = "code_b_file")]
39    pub code_b: Option<String>,
40
41    /// File holding the runtime bytecode of the second contract, as hex.
42    #[arg(long, value_name = "PATH", value_hint = ValueHint::FilePath, conflicts_with = "code_b")]
43    pub code_b_file: Option<PathBuf>,
44
45    /// Only explore ABI-encoded calls of this function, such as `transfer(address,uint256)`.
46    #[arg(long, value_name = "SIGNATURE")]
47    pub sig: Option<String>,
48
49    /// Explore raw calldata of exactly these lengths, in bytes, instead of a symbolic length.
50    #[arg(long, value_name = "LENGTHS", value_delimiter = ',', conflicts_with = "sig")]
51    pub calldata_lengths: Vec<usize>,
52
53    /// Largest symbolic calldata, in bytes.
54    #[arg(long, value_name = "BYTES", default_value_t = 1024)]
55    pub max_calldata: usize,
56
57    /// Largest return data of a call into unknown code, in bytes.
58    #[arg(long, value_name = "BYTES", default_value_t = 256)]
59    pub max_returndata: usize,
60
61    /// Start from empty storage instead of arbitrary symbolic storage.
62    #[arg(long)]
63    pub empty_storage: bool,
64
65    /// Fix the call value, in wei, instead of leaving it symbolic.
66    #[arg(long, value_name = "WEI")]
67    pub value: Option<U256>,
68
69    /// Assume calls into unknown code never call back into the contracts, so state-changing
70    /// calls into it are abstracted instead of stopping the check.
71    #[arg(long)]
72    pub promise_no_reent: bool,
73
74    /// Compare the contracts modulo gas, like hevm: leave out inputs on which either contract
75    /// runs out of gas instead of reporting them as a difference.
76    #[arg(long)]
77    pub ignore_out_of_gas: bool,
78
79    /// Solver to use, such as z3, cvc5, yices or bitwuzla. Defaults to `symbolic.solver`.
80    #[arg(long, value_name = "SOLVER")]
81    pub solver: Option<String>,
82
83    /// Timeout for the whole check, in seconds. Defaults to `symbolic.timeout`.
84    #[arg(long, value_name = "SECONDS")]
85    pub timeout: Option<u32>,
86}
87
88/// One concrete run of either contract on the counterexample.
89struct ConcreteRun {
90    success: bool,
91    output: Bytes,
92    /// Storage slots the run changed, of every account.
93    storage: HashMap<(Address, U256), U256>,
94    logs: Vec<Log>,
95    balances: HashMap<Address, U256>,
96    /// Nonce and code hash of every account the run touched.
97    accounts: HashMap<Address, (u64, B256)>,
98    /// Whether the run ran out of gas.
99    out_of_gas: bool,
100}
101
102impl EquivalenceArgs {
103    pub async fn run(self) -> Result<()> {
104        let code_a = read_code(self.code_a.as_deref(), self.code_a_file.as_ref(), "--code-a")?;
105        let code_b = read_code(self.code_b.as_deref(), self.code_b_file.as_ref(), "--code-b")?;
106        let function = self
107            .sig
108            .as_deref()
109            .map(|sig| Function::parse(sig).wrap_err_with(|| format!("invalid --sig `{sig}`")))
110            .transpose()?;
111
112        let config = Config::load()?;
113        let mut symbolic = config.symbolic.clone();
114        if let Some(solver) = self.solver {
115            symbolic.solver = solver;
116        }
117        if let Some(timeout) = self.timeout {
118            symbolic.timeout = Some(timeout);
119        }
120        symbolic.storage_layout = if self.empty_storage {
121            SymbolicStorageLayout::ZeroInit
122        } else {
123            SymbolicStorageLayout::Generic
124        };
125        symbolic.max_calldata_bytes = symbolic.max_calldata_bytes.max(self.max_calldata as u32);
126
127        let evm_opts = Config::figment().extract::<EvmOpts>()?;
128        let (evm_env, tx_env, _) = evm_opts.env_with_fork_context::<EthEvmNetwork>().await?;
129        let backend = Backend::<EthEvmNetwork>::spawn(None, evm_env)?;
130        let mut executor = ExecutorBuilder::<EthEvmNetwork>::new()
131            .inspectors(|stack| stack.logs(false))
132            .gas_limit(evm_opts.gas_limit())
133            .build(evm_env, tx_env, backend, evm_opts.networks);
134        executor.set_code(TEST_CONTRACT_ADDRESS, Bytecode::new_raw(code_a.clone()))?;
135
136        let result = SymbolicExecutor::new(symbolic).run_equivalence(SymbolicEquivalenceInput {
137            executor: ExecutorView::new(&executor),
138            address: TEST_CONTRACT_ADDRESS,
139            code_a: code_a.clone(),
140            code_b: code_b.clone(),
141            sender: CALLER,
142            value: self.value,
143            function: function.as_ref(),
144            calldata_lengths: self.calldata_lengths.clone(),
145            max_calldata: self.max_calldata,
146            max_returndata: self.max_returndata,
147            promise_no_reent: self.promise_no_reent,
148            ignore_out_of_gas: self.ignore_out_of_gas,
149        });
150
151        let (calldata, args, storage, env, unknown_calls, reads_gas, stats) = match result {
152            SymbolicEquivalenceResult::Equivalent { stats } => {
153                if shell::is_json() {
154                    sh_println!("{}", json!({ "status": "equivalent", "stats": stats }))?;
155                } else {
156                    sh_println!("Equivalent: no explored input distinguishes the two contracts.")?;
157                    print_stats(&stats)?;
158                }
159                return Ok(());
160            }
161            SymbolicEquivalenceResult::Incomplete { kind, reason, .. } => {
162                bail!("equivalence check incomplete ({kind:?}): {reason}")
163            }
164            SymbolicEquivalenceResult::Counterexample {
165                calldata,
166                args,
167                storage,
168                env,
169                unknown_calls,
170                reads_gas,
171                stats,
172            } => (calldata, args, storage, env, unknown_calls, reads_gas, stats),
173        };
174
175        let accounts = AccountMap { address: env.address, caller: env.caller };
176        prepare_replay(&mut executor, &env, &storage, &accounts)?;
177        let run_a = replay(&mut executor, &env, &code_a, &calldata)?;
178        let run_b = replay(&mut executor, &env, &code_b, &calldata)?;
179        let slots = run_a
180            .storage
181            .keys()
182            .chain(run_b.storage.keys())
183            .copied()
184            .collect::<BTreeSet<_>>()
185            .into_iter()
186            .map(|slot| {
187                Ok((
188                    slot,
189                    final_slot(&executor, &run_a, slot)?,
190                    final_slot(&executor, &run_b, slot)?,
191                ))
192            })
193            .collect::<Result<Vec<_>>>()?
194            .into_iter()
195            .filter(|(_, a, b)| a != b)
196            .collect::<Vec<_>>();
197        let balances = run_a
198            .balances
199            .keys()
200            .chain(run_b.balances.keys())
201            .copied()
202            .collect::<BTreeSet<_>>()
203            .into_iter()
204            .map(|account| {
205                Ok((
206                    account,
207                    final_balance(&executor, &run_a, account)?,
208                    final_balance(&executor, &run_b, account)?,
209                ))
210            })
211            .collect::<Result<Vec<_>>>()?
212            .into_iter()
213            .filter(|(_, a, b)| a != b)
214            .collect::<Vec<_>>();
215        let accounts_differ = run_a
216            .accounts
217            .keys()
218            .chain(run_b.accounts.keys())
219            .copied()
220            .collect::<BTreeSet<_>>()
221            .into_iter()
222            .map(|account| {
223                Ok((
224                    account,
225                    final_account(&executor, &run_a, account)?,
226                    final_account(&executor, &run_b, account)?,
227                ))
228            })
229            .collect::<Result<Vec<_>>>()?
230            .into_iter()
231            // The contracts' own code differs by construction, and the sender's nonce is the
232            // transaction's.
233            .filter(|(account, (nonce_a, code_a), (nonce_b, code_b))| {
234                (nonce_a != nonce_b && *account != env.caller)
235                    || (code_a != code_b && *account != env.address)
236            })
237            .collect::<Vec<_>>();
238        let both_succeeded = run_a.success && run_b.success;
239        let logs_differ = both_succeeded && run_a.logs != run_b.logs;
240        let replayed = run_a.success != run_b.success
241            || run_a.output != run_b.output
242            || (both_succeeded
243                && (!slots.is_empty() || !balances.is_empty() || !accounts_differ.is_empty()))
244            || logs_differ;
245        // Only a model that replays concretely is a counterexample. One that answers calls into
246        // unknown code, reads `GAS` or picks a separate origin may not, so say why.
247        if !replayed {
248            let mut reasons = Vec::new();
249            if unknown_calls > 0 {
250                reasons.push(format!("answers {unknown_calls} calls into unknown code"));
251            }
252            if reads_gas {
253                reasons.push("depends on GAS".to_string());
254            }
255            if env.origin != env.caller {
256                reasons.push("needs tx.origin to differ from the sender".to_string());
257            }
258            let reasons = if reasons.is_empty() {
259                String::new()
260            } else {
261                format!("; it {}", reasons.join(", "))
262            };
263            bail!(
264                "equivalence check incomplete (Error): the solver's counterexample {calldata} did \
265                 not replay concretely{reasons}"
266            );
267        }
268
269        if shell::is_json() {
270            let side = |run: &ConcreteRun| {
271                json!({
272                    "success": run.success,
273                    "output": run.output,
274                    "logs": run.logs.iter().map(log_json).collect::<Vec<_>>(),
275                })
276            };
277            let storage = slots
278                .iter()
279                .map(|((address, slot), a, b)| {
280                    json!({ "address": address, "slot": slot, "code_a": a, "code_b": b })
281                })
282                .collect::<Vec<_>>();
283            let balances = balances
284                .iter()
285                .map(|(account, a, b)| json!({ "address": account, "code_a": a, "code_b": b }))
286                .collect::<Vec<_>>();
287            sh_println!(
288                "{}",
289                json!({
290                    "status": "not_equivalent",
291                    "out_of_gas": run_a.out_of_gas != run_b.out_of_gas,
292                    "calldata": calldata,
293                    "args": args.iter().map(format_value).collect::<Vec<_>>(),
294                    "env": env_json(&env),
295                    "code_a": side(&run_a),
296                    "code_b": side(&run_b),
297                    "storage": storage,
298                    "balances": balances,
299                    "accounts": accounts_differ
300                        .iter()
301                        .map(|(account, (nonce_a, code_a), (nonce_b, code_b))| json!({
302                            "address": account,
303                            "code_a": { "nonce": nonce_a, "code_hash": code_a },
304                            "code_b": { "nonce": nonce_b, "code_hash": code_b },
305                        }))
306                        .collect::<Vec<_>>(),
307                    "stats": stats,
308                })
309            )?;
310        } else {
311            sh_println!("Not equivalent: the contracts differ on calldata {calldata}")?;
312            if function.is_some() {
313                let args = args.iter().map(format_value).collect::<Vec<_>>().join(", ");
314                sh_println!("  args:   ({args})")?;
315            }
316            sh_println!(
317                "  sender {}, value {}, block {}, timestamp {}",
318                env.caller,
319                env.value,
320                env.number,
321                env.timestamp
322            )?;
323            if run_a.out_of_gas != run_b.out_of_gas {
324                sh_println!(
325                    "  Only one contract runs out of gas here; pass --ignore-out-of-gas to \
326                     compare them modulo gas, as hevm does."
327                )?;
328            }
329            sh_println!("  code-a: {}", describe(&run_a))?;
330            sh_println!("  code-b: {}", describe(&run_b))?;
331            for ((address, slot), a, b) in &slots {
332                if *address == env.address {
333                    sh_println!("  storage slot {slot:#x}: code-a {a:#x}, code-b {b:#x}")?;
334                } else {
335                    sh_println!(
336                        "  storage slot {slot:#x} of {address}: code-a {a:#x}, code-b {b:#x}"
337                    )?;
338                }
339            }
340            for (account, a, b) in &balances {
341                sh_println!("  balance of {account}: code-a {a}, code-b {b}")?;
342            }
343            for (account, (nonce_a, code_a), (nonce_b, code_b)) in
344                accounts_differ.iter().filter(|_| both_succeeded)
345            {
346                sh_println!(
347                    "  account {account}: code-a nonce {nonce_a} code {code_a}, code-b nonce \
348                     {nonce_b} code {code_b}"
349                )?;
350            }
351            if logs_differ {
352                sh_println!("  code-a logs:")?;
353                print_logs(&run_a.logs)?;
354                sh_println!("  code-b logs:")?;
355                print_logs(&run_b.logs)?;
356            }
357            print_stats(&stats)?;
358        }
359        bail!("contracts are not equivalent")
360    }
361}
362
363/// Maps the accounts that stand for the symbolic address and sender to the model's choices.
364struct AccountMap {
365    address: Address,
366    caller: Address,
367}
368
369impl AccountMap {
370    fn map(&self, account: Address) -> Address {
371        if account == TEST_CONTRACT_ADDRESS {
372            self.address
373        } else if account == CALLER {
374            self.caller
375        } else {
376            account
377        }
378    }
379}
380
381/// Reads hex bytecode from a flag or a file.
382fn read_code(hex_code: Option<&str>, file: Option<&PathBuf>, flag: &str) -> Result<Bytes> {
383    let text = match (hex_code, file) {
384        (Some(code), _) => code.to_string(),
385        (None, Some(path)) => std::fs::read_to_string(path)
386            .wrap_err_with(|| format!("failed to read {flag}-file {}", path.display()))?,
387        (None, None) => bail!("{flag} or {flag}-file is required"),
388    };
389    let text = text.split_whitespace().collect::<String>();
390    hex::decode(&text).map(Bytes::from).wrap_err_with(|| format!("{flag} is not valid hex"))
391}
392
393/// Puts the counterexample's pre-state and block environment into the concrete executor.
394fn prepare_replay(
395    executor: &mut Executor<EthEvmNetwork>,
396    env: &SymbolicEquivalenceEnv,
397    storage: &[SymbolicStorageAssignment],
398    accounts: &AccountMap,
399) -> Result<()> {
400    for (account, balance) in &env.balances {
401        executor.set_balance(accounts.map(*account), *balance)?;
402    }
403    for assignment in storage {
404        executor.set_storage_slot(
405            accounts.map(assignment.address),
406            assignment.slot,
407            assignment.value,
408        )?;
409    }
410    let evm_env = executor.evm_env_mut();
411    evm_env.set_chain_id(env.chain_id.saturating_to());
412    // Gas is not priced in the symbolic model, so the replay charges no fees either. The model
413    // already requires the sender to hold the call value.
414    evm_env.set_feature(EvmFeatures::FEE_CHARGE, false);
415    evm_env.set_feature(EvmFeatures::BALANCE_CHECK, false);
416    evm_env.set_feature(EvmFeatures::BALANCE_TOP_UP, false);
417    evm_env.set_feature(EvmFeatures::BASE_FEE_CHECK, false);
418    let block = &mut evm_env.block;
419    block.number = env.number;
420    block.timestamp = env.timestamp;
421    block.beneficiary = env.coinbase;
422    block.difficulty = env.prevrandao;
423    block.prevrandao = env.prevrandao;
424    block.blob_basefee = env.blob_basefee;
425    Ok(())
426}
427
428/// Runs `code` at the counterexample's address on `calldata` without committing state.
429///
430/// Fees are not charged, so balances only move by value transfers and self-destructs, as in the
431/// symbolic model.
432fn replay(
433    executor: &mut Executor<EthEvmNetwork>,
434    env: &SymbolicEquivalenceEnv,
435    code: &Bytes,
436    calldata: &Bytes,
437) -> Result<ConcreteRun> {
438    executor.set_code(env.address, Bytecode::new_raw(code.clone()))?;
439    let (mut evm_env, mut tx_env) = executor.prepare_call_env(
440        env.caller,
441        TxKind::Call(env.address),
442        calldata.clone(),
443        env.value,
444    );
445    evm_env.block.basefee = env.basefee;
446    tx_env.set_gas_price(env.gas_price.saturating_to());
447    let result = executor.call_with_env(evm_env, tx_env)?;
448    let storage = result
449        .state_changeset
450        .account_changes()
451        .flat_map(|account| {
452            account
453                .storage
454                .changed_slots()
455                .map(move |(key, slot)| ((account.address, *key), slot.current))
456        })
457        .collect();
458    let balances = result
459        .state_changeset
460        .account_changes()
461        .filter(|account| account.touched)
462        .map(|account| (account.address, account.current.map_or(U256::ZERO, |info| info.balance)))
463        .collect();
464    let accounts = result
465        .state_changeset
466        .account_changes()
467        .filter(|account| account.touched)
468        .map(|account| {
469            let state =
470                account.current.map_or((0, KECCAK256_EMPTY), |info| (info.nonce, info.code_hash));
471            (account.address, state)
472        })
473        .collect();
474    Ok(ConcreteRun {
475        success: !result.reverted,
476        output: result.result,
477        storage,
478        logs: result.logs,
479        balances,
480        accounts,
481        out_of_gas: result.exit_reason.is_some_and(InstrStop::is_out_of_gas),
482    })
483}
484
485/// Returns a slot's value after `run`, falling back to the shared pre-state.
486fn final_slot(
487    executor: &Executor<EthEvmNetwork>,
488    run: &ConcreteRun,
489    (address, slot): (Address, U256),
490) -> Result<U256> {
491    match run.storage.get(&(address, slot)) {
492        Some(value) if run.success => Ok(*value),
493        _ => Ok(executor.backend().storage(address, slot)?),
494    }
495}
496
497/// Returns an account's balance after `run`, falling back to the shared pre-state.
498fn final_balance(
499    executor: &Executor<EthEvmNetwork>,
500    run: &ConcreteRun,
501    account: Address,
502) -> Result<U256> {
503    match run.balances.get(&account) {
504        Some(balance) if run.success => Ok(*balance),
505        _ => Ok(executor.get_balance(account)?),
506    }
507}
508
509/// Returns an account's nonce and code hash after `run`, falling back to the shared pre-state.
510fn final_account(
511    executor: &Executor<EthEvmNetwork>,
512    run: &ConcreteRun,
513    account: Address,
514) -> Result<(u64, B256)> {
515    match run.accounts.get(&account) {
516        Some(state) if run.success => Ok(*state),
517        _ => Ok(executor
518            .backend()
519            .basic(account)?
520            .map_or((0, KECCAK256_EMPTY), |info| (info.nonce, info.code_hash))),
521    }
522}
523
524fn env_json(env: &SymbolicEquivalenceEnv) -> serde_json::Value {
525    json!({
526        "address": env.address,
527        "caller": env.caller,
528        "origin": env.origin,
529        "value": env.value,
530        "timestamp": env.timestamp,
531        "number": env.number,
532        "prevrandao": env.prevrandao,
533        "gas_limit": env.gas_limit,
534        "basefee": env.basefee,
535        "chain_id": env.chain_id,
536        "coinbase": env.coinbase,
537        "gas_price": env.gas_price,
538    })
539}
540
541fn log_json(log: &Log) -> serde_json::Value {
542    json!({ "address": log.address, "topics": log.topics(), "data": log.data.data })
543}
544
545fn print_logs(logs: &[Log]) -> Result<()> {
546    if logs.is_empty() {
547        sh_println!("    (none)")?;
548    }
549    for log in logs {
550        let topics = log.topics().iter().map(ToString::to_string).collect::<Vec<_>>().join(", ");
551        sh_println!("    {} topics [{topics}] data {}", log.address, log.data.data)?;
552    }
553    Ok(())
554}
555
556fn describe(run: &ConcreteRun) -> String {
557    if run.out_of_gas {
558        return "ran out of gas".to_string();
559    }
560    let verb = if run.success { "returned" } else { "reverted with" };
561    if run.output.is_empty() { format!("{verb} no data") } else { format!("{verb} {}", run.output) }
562}
563
564fn format_value(value: &DynSolValue) -> String {
565    foundry_common::fmt::format_token(value)
566}
567
568fn print_stats(stats: &SymbolicStats) -> Result<()> {
569    sh_println!("Explored {} paths with {} solver queries.", stats.paths, stats.solver_queries)?;
570    Ok(())
571}