Completeness issue for some out-of-gas cases for MCOPY
Description
Reverts due to being out of gas during memory copy operations are handled by the EVM circuit's ErrorOOGMemoryCopyGadget. However, the gas costs of MCOPY instructions are not calculated correctly.
In the MCopyGadget, the gas cost is calculated as follows:
let memory_expansion = MemoryExpansionGadget::construct(
cb,
[
memory_src_address.end_offset(),
memory_dest_address.end_offset(),
],
);
let memory_copier_gas = MemoryCopierGasGadget::construct(
cb,
memory_src_address.length(),
memory_expansion.gas_cost(),
);
// dynamic cost + constant cost
let gas_cost = memory_copier_gas.gas_cost() + OpcodeId::MCOPY.constant_gas_cost().expr();The above gas-cost calculation corresponds to the Ethereum specification. However, in the ErrorOOGMemoryCopyGadget, we have this:
! let memory_expansion = MemoryExpansionGadget::construct(cb, [dst_memory_addr.end_offset()]);
let memory_copier_gas = MemoryCopierGasGadget::construct(
cb,
dst_memory_addr.length(),
memory_expansion.gas_cost(),
);
let constant_gas_cost = select::expr(
is_extcodecopy.expr(),
// According to EIP-2929, EXTCODECOPY constant gas cost is different for cold and warm
// accounts.
select::expr(
is_warm.expr(),
GasCost::WARM_ACCESS.expr(),
GasCost::COLD_ACCOUNT_ACCESS.expr(),
),
// Constant gas cost is same for CALLDATACOPY, CODECOPY and RETURNDATACOPY.
OpcodeId::CALLDATACOPY.constant_gas_cost().expr(),
);
let insufficient_gas = LtGadget::construct(
cb,
cb.curr.state.gas_left.expr(),
constant_gas_cost + memory_copier_gas.gas_cost(),
);
cb.require_equal(
// for mcopy, both dst_memory_addr and dst_memory_addr likely overflow.
"Memory address is overflow or gas left is less than cost",
or::expr([
dst_memory_addr.overflow(),
src_memory_addr.overflow(),
insufficient_gas.expr(),
]),
1.expr(),
);Note that memory expansion only takes into account the destination, not the source. According to the Ethereum specification, not only writes but also reads cause memory expansion. An MCOPY operation of nonzero length from a very high memory address to a low memory address will thus cause memory expansion, causing an out-of-gas error (as long as the source address was high enough). However, the ErrorOOGMemoryCopyGadget will not consider this memory expansion and thereby calculate a too small memory_copier_gas.gas_cost(), which then makes insufficient_gas false, making it impossible to satisfy the constraint at the end of the snippet above, unless the addresses are so large to also overflow.
We confirmed this issue with the following test:
#[test]
fn zellic_mcopy_out_of_gas() {
let src_offset = Word::from(0x1000000);
let dest_offset = Word::from(0x0);
let length = Word::from(0x20);
let mut code = Bytecode::default();
code.append(&bytecode! {
PUSH32(length)
PUSH32(src_offset)
PUSH32(dest_offset)
MCOPY
STOP
});
let ctx = TestContext::<3, 1>::new(
None,
|accs| {
accs[0]
.address(address!("0x000000000000000000000000000000000000cafe"))
.code(code);
accs[1]
.address(address!("0x0000000000000000000000000000000000000010"))
.balance(Word::from(1u64 << 20));
},
|mut txs, accs| {
txs[0]
.to(accs[0].address)
.from(accs[1].address)
.gas(1_000_000.into());
},
|block, _tx| block.number(0x1111111),
)
.unwrap();
CircuitTestBuilder::new_from_test_ctx(ctx)
.params(CircuitsParams {
max_copy_rows: 1750,
..Default::default()
})
.run();
}As expected, trying to run this test fails because of the Memory address is overflow or gas left is less than cost constraint:
[2024-05-27T20:49:00Z INFO halo2_proofs::dev] MockProver synthesize took 245.328931ms
[2024-05-27T20:49:00Z DEBUG halo2_proofs::dev] regions.len() = 18
thread 'evm_circuit::execution::mcopy::test::zellic_mcopy_out_of_gas' panicked at zkevm-circuits/src/test_util.rs:99:17:
assertion `left == right` failed
left: Err([ConstraintCaseDebug {
constraint: Constraint {
gate: Gate {
index: 381,
name: "ErrorOutOfGasMemoryCopy",
},
index: 51,
name: "ErrorOutOfGasMemoryCopy: Memory address is overflow or gas left is less than cost",
},
location: InRegion {
region: Region 15 ('Execution step region1_0'),
offset: 22,
},
cell_values: [
(
DebugVirtualCell {
name: "",
column: DebugColumn {
column_type: Advice,
index: 71,
annotation: "EVM_q_step",
},
rotation: 0,
},
"1",
),
(
DebugVirtualCell {
name: "",
column: DebugColumn {
column_type: Fixed,
index: 20,
annotation: "",
},
rotation: 0,
},
"1",
),
],
}])
right: Ok(())Impact
It will not be possible to prove blocks in which an MCOPY reverts due to an out of gas error that was solely caused by memory expansion caused by the reads from the source. While it appears unlikely that such reverts appear in benign transactions, it cannot be ruled out that such a completeness issue could be used as a denial-of-service vector.
Recommendations
In the MCOPY case, make the calculation of memory_expansion in ErrorOOGMemoryCopyGadget::configure correspond to the calculation done in MCopyGadget::configure by extending the list passed as the addresses argument to MemoryExpansionGadget::construct with src_memory_addr.end_offset().
Remediation
This issue has been acknowledged by Scroll, and fixes were implemented in the following commits: