Meta: Keccak hashing impl proposal fom Circuit Input Builder

[CPerezz]

Bus mapping Keccak-hashing accountant

Rationale

During witness generation, we will need to prepare a list that contains all the keccak hashes performed during an entire block and that need to be proven inside of the ZKEVM circuits.

That, is required since is easier to collect all them from a centralized source like we do with the Operations with the execution traces.

Once all of them are collected, we can more easily feed the keccak circuit with all the witnesses required.

Keccak production sources

• EVM circuit
  • SLOAD (0x54) (Taken care via State circuit)
  • SSTORE (0x55) (Taken care via State circuit)
  • BALANCE (0x31) (Taken care via State circuit)
  • SELFBALANCE (0x347) (Taken care via State circuit)
  • SHA3 (0x20) (Directly feed into keccak circuit)
  • CODESIZE (0x38) (Taken care via State + Bytecode circuit)
  • EXTCODESIZE (0x3B) (Taken care via State + Bytecode circuit)
  • EXTCODECOPY (0x3C) (Taken care via State + Bytecode circuit)
  • EXTCODEHASH (0x3F) (Taken care via State + Bytecode circuit)
  • CREATE (0xF0) (Taken care via State + Bytecode circuit)
  • CALLCODE (0xF2)
  • CREATE2(0xF5) (Taken care via State + Bytecode circuit) (I leave BlockHash as doubt. I think should be handled via PI not via hashing).
• State circuit For each account which had modified storage, we need to compute the MTPath. Which means:
  • Storage Root check for each account updated in the block.
  • Global storage root check after all the accounts are updated.

[name=Miha Stopar]Just a remark: the number of keccaks in MPT proof is the level of account proof + the level of storage proof.

• Bytecode circuit For each opcode that requires hashing of bytecode, the Bytecode circuit will need to copy the bytecode and hash it to be sure that it's the original one.

• Tx circuit

  • Tx Receipts tree hashing.
  • Transactions tree hashing.
  • Block hash computation.

Impl design

For each source of hashing we find during the parsing of all of the EVM opcodes, we need to feed the hashing_container included with the ExecutionTrace object and add entries for each of the hashes that will need to be performed so that it behaves kinda like:

struct ExecutonTrace {
    block_ctants: BlockConstants,
    steps: Vec<ExecutionStep>,
    op_container: OperationContainer,
    // Note that the RLC of the input and output will not be computed
    // as it's not possible until Synthesize time.
    hash_container: HashMap<Vec<u8>, [u8;32]>,
}

That will also trigger an update on the CircuitInputBuilder and inside the zkevm-crcuts crate where we wll need to be able to get the HashingContainer instance produced by the bus-mapping and be able to get from it all of the hashes required to be computed by each circuit at each point (so that they can assign RLC(input), RLC(output)) and also so that KeccakCircuit can include one entry inside of its lookup table for each one of the container instances.

Allowing the lookup:

RLC(input)	input_len	RLC(output)
Entry_1_inp	X	Entry_1_out
Entry_2_inp	Y	Entry_2_out

Sub-tasks:

• [ ] https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/696
• [x] https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/697

[ed255]

In the SuperCircuit PR I added some functions to the TxCircuit and BytecodeCircuit that return the list of keccak inputs that they need. We could do a similar thing for the rest of the circuits. See: https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/7b711b1e32a6338d0bc6daf24cbea015ca195bf1/zkevm-circuits/src/tx_circuit.rs#L88-L101

[ed255]

The only missing part for this tasks is to handle the keccak inputs required by MPT circuit. This will be unblocked with https://github.com/privacy-scaling-explorations/zkevm-circuits/issues/1416