EIP-7939: CLZ Opcode for Efficient Bit Manipulation and ZK Cost Savings

EIP-7939 proposes a new opcode to count leading zero bits in a 256-bit word. This is a widely used primitive in modern processor architectures, and its addition to the EVM opens the door to cheaper compute, smaller bytecode, and significant savings in zero-knowledge proof generation.

TL;DR: CLZ is a foundational building block that makes low-level math and cryptographic proofs more efficient, especially in onchain ZK circuits.

What is the CLZ Opcode?

CLZ stands for "Count Leading Zeros." The proposed opcode CLZ(x) pops a 256-bit word x from the EVM stack and pushes the number of zero bits before the most significant 1 bit. If x == 0, it pushes 256.

Example:

• CLZ(0x0000...0001) → 255
• CLZ(0x8000...0000) → 0
• CLZ(0x0) → 256

The opcode number is 0x1e, and its gas cost is set to 5 (same as MUL), balancing performance and DoS resistance.

Why It Matters

The CLZ operation is a key building block across many domains:

• Math primitives: sqrt, cbrt, lnWad, powWad, and Lambert W0 functions
• Byte string manipulation: For locating meaningful bits or trimming
• Data compression: Faster bit packing and string encoding
• Bitmaps: Finding next or previous set/unset bits
• Calldata parsing: Compressing or decompressing structured calldata
• ZK Proving: Reduces proving cost by avoiding dynamic shr operations

Real Use Cases

CLZ is already heavily used in libraries like:

• prb-math
• solady
• intx

Adding it natively lets these libraries avoid large inlined assembly routines, leading to smaller bytecode and faster execution.

Solidity Implementation

The fastest known CLZ implementation in Solidity uses about 184 gas:

function clz(uint256 x) internal pure returns (uint256 r) {
    assembly {
        r := shl(7, lt(0xffffffffffffffffffffffffffffffff, x))
        r := or(r, shl(6, lt(0xffffffffffffffff, shr(r, x))))
        r := or(r, shl(5, lt(0xffffffff, shr(r, x))))
        r := or(r, shl(4, lt(0xffff, shr(r, x))))
        r := or(r, shl(3, lt(0xff, shr(r, x))))
        r := add(xor(r, byte(
            and(0x1f, shr(shr(r, x), 0x8421084210842108cc6318c6db6d54be)),
            0xf8f9f9faf9fdfafbf9fdfcfdfafbfcfef9fafdfafcfcfbfefafafcfbffffffff
        )), iszero(x))
    }
}

But this approach inflates bytecode size and is hard to prove in ZK circuits. Replacing it with a single opcode saves gas and simplifies verification.

Cheaper ZK Circuits

Zero-knowledge circuits must simulate EVM opcodes. Dynamic shr operations are especially expensive to prove in ZK backends like SP1. CLZ avoids this overhead, making it more prover-friendly.

• In SP1 rv32im, right shift costs 1.6x more than mul
• CLZ in the same setting is cheaper than add

This makes CLZ ideal for ZK rollups, onchain games, or protocols using privacy-preserving proofs.

Specification Summary

• Opcode: CLZ (0x1e)
• Input: x (256-bit word)
• Output: Number of leading zero bits in x
• Special case: If x == 0, returns 256
• Gas Cost: 5

Test Cases

Comparison: CLZ vs CTZ

Some may wonder: why not implement CTZ (Count Trailing Zeros)? Here's the reasoning:

• CLZ is more universal. CTZ can be partially simulated by isolating the least significant bit and calling CLZ.
• CTZ is harder to implement using CLZ, but not vice versa.
• CLZ is widely supported in CPUs and compilers like GCC, LLVM, and WebAssembly.

Security Considerations

• CLZ is stateless, with no memory or storage implications
• Low and predictable gas cost
• Safe for proving in zkVMs
• Not prone to DoS vectors due to its constant-time nature

Conclusion

EIP-7939 introduces a highly efficient primitive to the EVM that will make low-level math, data manipulation, and ZK proving significantly cheaper. Developers can replace gas-heavy inline assembly with a single opcode, reducing both gas and bytecode size.

This change benefits:

• Smart contract libraries like Solady and PRB Math
• ZK rollups and zkEVM chains
• Any protocol doing heavy bit-level computation

We recommend tracking the status of this EIP and adopting CLZ where possible once it is finalized. For more details, visit the EIP-7939 discussion.