Estimate rows needed for a block that of blake/sha256 maxed out

[ed255]

Follow up from #1798

Estimate the rows needed for a block that tries to max out the blake and sha256 precompiles in a block with N gas.

Sha256 is not integrated but we've had a PR for a long time with an implementation here #756
Blake is not implemented in halo2, but we can use the Chiquito implementation for reference.

Since these two precompiles are not integrated getting benchmarks would need a lot of work, so instead the idea is to just estimate the row usage of a maxed out block. Then we can compare that value against the average block from #1798 and get an estimation on the cost increase (by comparing the required k of average VS maxed out)

[zemse]

Since SHA256 follows Merkle–Damgård construction, the words are chained through the compression function, goal is to max out the SHA256's compression function invocations that could be done within 30M gas.

The following approach is used:

1. Allocate some words on memory.
2. Call to precompile using the memory slice as input.
3. Change the first word in memory.
4. Go to step 2.

JUMPDEST
JUMPDEST
# return size and offset
PUSH1 0x20 PUSH0
# input size and offset
PUSH3 0x025120 PUSH0
# precompile address
PUSH1 2
GAS
STATICCALL
# above also writes to first mem word
# jump to PC = 1
JUMP

The above evm code 5b5b60205f620251205f60025afa56 is sent to the NULL address which in this case keeps making SHA256 precompile calls until it runs into OOG. Even though this is a failed transaction, to prove it was indeed failed/OOG, zkEVM must perform SHA256 in the circuit.

Using evm-run, it is found that if we use hash length of 4746 words (0x025120 bytes) then it makes 525 successful unique SHA256 precompile calls (526 but last one that fails by OOG), this means 2,491,650 compressions.

$ evm-run 5b5b60205f620251205f60025afa56 --gasLimit 30000000 | grep "STATICCALL" | wc -l

526

This script is used to estimate that 4746 words x 525 calls maxes out sha256 usage within 30M gas (click to expand).

// gas cost for allocating num_words on EVM memory
function init_cost(num_words: number) {
  let mem_cost = num_words * 3 + Math.floor(num_words ** 2 / 512);
  let extra_gas = 1 + 2500; // jumpdest + first staticcall
  return mem_cost + extra_gas;
}

// gas cost for executing SHA256 precompile
function exec_cost(num_words: number) {
  let extra_gas = 24;
  return 100 + 60 + num_words * 12 + extra_gas;
}

function find_num_batches(num_words: number, target_gas: number) {
  target_gas -= init_cost(num_words);
  let single_exec_cost = exec_cost(num_words);

  // floor because last batch will fail
  let num_batches = Math.floor(target_gas / single_exec_cost);
  return num_batches;
}

function quantity(num_words: number, num_batches: number) {
  return num_words * num_batches;
}

function find_maxima(target_gas: number) {
  let best_case = {
    num_words: 1,
    num_batches: find_num_batches(1, target_gas),
    get quantity() {
      return quantity(this.num_words, this.num_batches);
    },
  };
  let new_num_words = 1;
  while (1) {
    new_num_words++;
    let new_num_batches = find_num_batches(new_num_words, target_gas);
    let new_quantity = quantity(new_num_words, new_num_batches);
    if (new_quantity > best_case.quantity) {
      best_case.num_batches = new_num_batches;
      best_case.num_words = new_num_words;
      console.log("best case update", best_case);
    }
    // stop once done
    if (new_num_batches === 0) {
      return best_case;
    }
  }
  return best_case;
}

console.log(find_maxima(30_000_000));

Similarly, it is found that for 300k gas maxes out to 24024 sha256 compression functions (27456 bytes memory x 29 precompile calls).

Using PR 756, it is found to take 897848 rows. That's $log_2{897848}=19.77$ hence $k=20$. I was not able to calculate rows for 30M gas because it took a lot of time on my system (> 2 hours).