EIP-7939: Create a new opcode for counting leading zeros (CLZ)

EIPs
11

TL;DR: This instruction is useful in software and straight-forward to implement in EVM.

Language & Hardware support

The CLZ-like instruction is supported in many system programming languages.

The CLZ-like instruction is usually available in modern hardware.

  • x86-64: partial
  • x86-64-v3: yes
  • armv8: yes
  • rv64im: no
  • rv64imzbb: yes

EVM implementation context

  1. This hardware instruction is probably already used in EVM implementations, e.g. in division related opcodes: DIV, MOD, ADDMOD, MULMOD or in EXP.
  2. This EVM instruction should also help with EVM implementation of expmod or EC point multiplication precompiles.
  3. Implementation should be straight forward and linear in number of words (4). The best approach seems to be to look for the non-zero most significant word and apply the native clz operation to it. This is optimal for architectures having no/partial clz.

Gas cost

EIPs proposing new features to EVM (including this one) usually select the gas cost which is consistent with the current gas model but don’t necessarily reflect the actual execution performance. In this case, the comparison to the ADD instruction is a bit off because ADD pops two items from the stack while CLZ only one. Better comparison would be with the NOT instruction. However, because both ADD and NOT have the gas cost of 3, the same proposed gas cost for CLZ looks right.

On the other hand, in the context of EIP-7904: General Repricing, the gas cost of CLZ should be 1.

My recommendation is to keep the proposed gas cost of 3 and change it only in case the EIP-7904 is activated before or at the same time as this EIP.

Nit picks

Adding a clz opcode will also lead to cheaper ZK proving costs.

The CLZ instruction will be available only for newly deployed contract (at least 2 years from now). And it is unlikely to see big migrations just because there is a new instruction available.

We have benchmarked the clz implementation against the add implementation in the intx library.

If you have done any benchmarks please publish the source code anyhow.

Questions

  1. Should we consider adding the sibling instruction CTZ (count tailing zeros)?
1 Like