Write extcodecopy circuit

[DoHoonKim8]

I wrote the circuit for verifying extcodecopy opcode and added some tests.

• I implemented bus-mapping for extcodecopy and added some tests too.

Spec link: spec

Give me many comments, Thanks!

[DoHoonKim8]

@ChihChengLiang Would you please review this PR? :)🙏

[ChihChengLiang]

Yeah sure, sorry for the delay. Let me also tag @ed255 and @roynalnaruto because they've reviewed the spec.

[DoHoonKim8]

@roynalnaruto @ed255 Would you please review this PR? :) 🙏

[DoHoonKim8]

Could you add the test case in copy_circuit.rs for EXTCODECOPY?

I think some tests are failing due to the changes in ea63957dab1c9613f17c961e50d9cc687383f5db. I'll resolve this and let you know again :)

[DoHoonKim8]

@roynalnaruto Sorry for being quite late for this. I still cannot find out why EXTCODECOPY test case is failing in copy_circuit.rs. Can you help me for this issue? The error message is following:

thread 'copy_circuit::tests::copy_circuit_valid_extcodecopy' panicked at 'assertion failed: `(left == right)`
  left: `Err([Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 0 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 2 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 4 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 6 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 8 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 10 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 12 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 14 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 16 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 18 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 20 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 22 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 24 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 26 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 28 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 30 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 32 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 34 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 36 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 38 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 40 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 42 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 44 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 46 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 48 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 50 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 52 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 54 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 56 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 58 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 60 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 62 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 64 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 66 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 68 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 70 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 72 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 74 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 76 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 78 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 80 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 82 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 84 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 86 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 88 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 90 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 92 } }, Lookup { name: "Bytecode lookup", lookup_index: 2, location: InRegion { region: Region { index: 3, name: "assign copy table" }, offset: 94 } }])`,
 right: `Ok(())`', zkevm-circuits/src/copy_circuit.rs:856:9

[ChihChengLiang]

@DoHoonKim8 I checked and reproduced the testing error. It looks like the external_address is not written into the CopyTable, so the lookup failed. I traced the assign_block function, and the related CopyEvent for external_address was not there.

I think accs[1] in the test_ctx, which corresponds to the external_address was ignored. The block builder didn't generate the corresponding CopyEvent for it. We might need to add the CopyEvent somewhere.

[roynalnaruto]

@ChihChengLiang @DoHoonKim8 Since the bytecode lookup is failing, I believe we can start debugging from here:

• Only block.bytecodes is populated into the bytecode table.

The witness block is constructed here:

• Which means it is only considering the code_hash of each call in the block's transactions. It does not take into consideration the bytecode at the external_address.

One possible solution is to:

• Add a field ext_code_hashes: Vec<Hash> to the circuit_input_builder::block and:
• Populate it during the bus-mapping implementation of EXTCODECOPY

    state.add_ext_code_hash(ext_code_hash)?;

which adds this to the block:

    /// Push code hash at an address accessed through `EXTCOPYCOPY` to the block.
    pub fn add_ext_code_hash(&mut self, code_hash: Hash) {
        self.block.add_ext_code_hash(code_hash);
    }

• We can then also populate the bytecode table during witness generation:

        bytecodes: block
            .txs()
            .iter()
            .flat_map(|tx| {
                tx.calls()
                    .iter()
                    .map(|call| call.code_hash)
                    .unique()
                    .into_iter()
                    .map(|code_hash| {
                        let bytecode =
                            Bytecode::new(code_db.0.get(&code_hash).cloned().unwrap_or_default());
                        (bytecode.hash, bytecode)
                    })
            })
            .chain(block.ext_code_hashes.iter().unique().map(|code_hash| {
                let bytecode =
                    Bytecode::new(code_db.0.get(&code_hash).cloned().unwrap_or_default());
                (bytecode.hash, bytecode)
            }))
            .collect(),

There might be other ways to do this as well, let me know what you guys think :)

[roynalnaruto]

Also, with regards to the code here: https://github.com/DoHoonKim8/zkevm-circuits/blob/main/bus-mapping/src/evm/opcodes/extcodecopy.rs#L27-L29

EVM should allow EXTCODECOPY from an address that doesn't exist in the state or that doesn't have code. The copy size should be all 0 bytes. So those cases should be handled through bus-mapping.

[ChihChengLiang]

@roynalnaruto, the approach of populating bytecode to the table looks great. Thank you for the proposal!

[aguzmant103]

Hey @DoHoonKim8 just following up, is this PR still in progress?

[DoHoonKim8]

Hey @DoHoonKim8 just following up, is this PR still in progress?

Yup, I will gonna resolve all the comments in the next week.

[DoHoonKim8]

@ChihChengLiang @DoHoonKim8 Since the bytecode lookup is failing, I believe we can start debugging from here:

• Only block.bytecodes is populated into the bytecode table.

The witness block is constructed here:

• Which means it is only considering the code_hash of each call in the block's transactions. It does not take into consideration the bytecode at the external_address.

One possible solution is to:

• Add a field ext_code_hashes: Vec<Hash> to the circuit_input_builder::block and:
• Populate it during the bus-mapping implementation of EXTCODECOPY

    state.add_ext_code_hash(ext_code_hash)?;

which adds this to the block:

    /// Push code hash at an address accessed through `EXTCOPYCOPY` to the block.
    pub fn add_ext_code_hash(&mut self, code_hash: Hash) {
        self.block.add_ext_code_hash(code_hash);
    }

• We can then also populate the bytecode table during witness generation:

        bytecodes: block
            .txs()
            .iter()
            .flat_map(|tx| {
                tx.calls()
                    .iter()
                    .map(|call| call.code_hash)
                    .unique()
                    .into_iter()
                    .map(|code_hash| {
                        let bytecode =
                            Bytecode::new(code_db.0.get(&code_hash).cloned().unwrap_or_default());
                        (bytecode.hash, bytecode)
                    })
            })
            .chain(block.ext_code_hashes.iter().unique().map(|code_hash| {
                let bytecode =
                    Bytecode::new(code_db.0.get(&code_hash).cloned().unwrap_or_default());
                (bytecode.hash, bytecode)
            }))
            .collect(),

There might be other ways to do this as well, let me know what you guys think :)

Hey thanks for your suggestion! I updated witness::block::block_convert function to populate bytecode table in witness block with external code hashes. Would you check the patch?

[DoHoonKim8]

As in https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/1014#discussion_r1058391676, the whole bytecode in code_db is populated in block now(also the external bytecode too).

As Han commented, if code_db is used for caching bytecodes of the future block in the future, then we should follow https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/720#issuecomment-1325853263 at that moment.

[aguzmant103]

Hey @roynalnaruto based on last comment I think this is ready for review whenever you can

[roynalnaruto]

Hey @roynalnaruto based on last comment I think this is ready for review whenever you can

@DoHoonKim8 I was on leave. I'm back to work this week and will review the PR by end of the week :)

[DoHoonKim8]

Thanks for your kind review!! 👍 @roynalnaruto

[lispc]

@DoHoonKim8 oh there is one thing missing.. After https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/1020, we should no longer write let code_hash = block.rws[step.rw_indices[8]] .table_assignment_aux(block.randomness) .value;, it should be changed like self.code_hash .assign(region, offset, region.word_rlc(code_hash))?; . you can have a look at extcodesize gagdet.

[lispc]

another problem is the non exist proof refactor like this https://github.com/privacy-scaling-explorations/zkevm-circuits/commit/aaaf13ee3020661e048484776bd88686d1659042. @ed255

[lispc]

oh i enabled RUST_LOG=trace for this gadget, can i believe ErrorOutOfGasEXTCODECOPY is triggered.. The extcodecopy gadget may not be tested at all.. @DoHoonKim8