KeccakCollision, explained: why finding four matching hashes beats finding one

If you have ever explained Bitcoin mining to a non-technical friend, you have probably said something like: “miners try lots of nonces until they get a hash that starts with a bunch of zeros.” It is a useful metaphor. It is also the wrong shape of problem for an asset that wants to settle on Ethereum.

This post explains what shape of problem KeccakCollision actually is, why we chose it, and how the on-chain verifier stays under 100 gas-paying lines.

The shape of Bitcoin’s problem

In Bitcoin, the miner is solving a one-dimensional inequality:

SHA256(block_header || nonce) < target

You vary nonce, you hash, you compare. The problem is “embarrassingly parallel” in the literal CS sense: every nonce attempt is independent of every other nonce attempt. There is no useful state to carry between attempts. There is no memory pressure. The hot path is one SHA-256 round.

This is exactly the workload that custom silicon (ASICs) excels at. You build a pipelined SHA-256 engine, you tape it out at 5nm, you fab a million of them, you sell them to data centres. Performance per dollar of an ASIC is roughly four orders of magnitude better than a general-purpose GPU at this workload.

The shape of KeccakCollision’s problem

EVMORE’s miner is solving a search-and-store problem instead:

Find K distinct 32-byte values v_1, v_2, v_3, v_4 such that
keccak256(challenge || v_i) & ((1 << N) - 1) == same_pattern
for all i in [1..K]

With K=4 and N=16 (the defaults), the miner must find four random 32-byte values whose Keccak hashes all share the same lowest 16 bits.

The naive algorithm is:

1. Pick a random 32-byte candidate v.
2. Compute h = keccak256(challenge || v).
3. Extract pattern = h & 0xFFFF.
4. Store v in a hash table keyed by pattern.
5. If the bucket for pattern now contains 4 entries, you have a solution.
6. Sort the 4 entries in ascending order. That’s the 128-byte proof.

The expected number of attempts before you find a 4-collision in a 16-bit space is statistically straightforward. The lower bits of a cryptographic hash are uniformly distributed, so you have a 1-in-65,536 chance per candidate to hit any given bucket. By the birthday-paradox-style analysis you need somewhere in the low hundreds of thousands of hashes to expect a 4-collision in any bucket — but the variance is high and the workload is “scan the table, find a 4-bucket.”

Why this is memory-hard

The naive algorithm above tells you almost everything. The miner must:

• Allocate memory. A practical implementation keeps the table at a fixed size per bucket and rolls candidates through it. The table needs to be big enough to capture collisions before they age out, and small enough to fit in fast memory.
• Do random access into that memory. Every hash result indexes into a different bucket. The access pattern is, by construction, scattered.
• Sustain bandwidth more than throughput. The work is Keccak + lookup + store, dominated by the lookup.

This is the workload signature of “memory-hard.” It is the opposite of Bitcoin’s workload signature.

ASICs are bad at random memory access because the economics of taping out silicon optimised for high-bandwidth random DRAM access ends up looking like… a GPU. The advantage of custom silicon collapses when the bottleneck is memory throughput rather than compute.

GPUs are good at this. CPUs with fast DRAM are also good at this. The cost-of-entry to mine EVMORE is a gaming-class machine.

The collision-width difficulty knob

The difficulty parameter is N, the number of bits that must match. At N=16, finding a 4-collision is straightforward on a single GPU. At N=32, you need 65,536x more hash computations on average. The contract retargets every 2,016 blocks (just like Bitcoin’s 2-week retarget cadence), nudging N up or down within the range [8, 32] and capping per-retarget changes at 4x to prevent instability.

This gives the network the smooth ~10-minute block time targeting that Bitcoin has, without giving up the memory-hardness property.

The on-chain verifier

Here is where the design pays off. The contract does not need to find solutions; it only needs to verify them. Given a 128-byte solution (4 x 32 bytes), the verifier does this:

# KeccakCollisionVerifier.vy (paraphrased)
def verify_solution(
    challenge: bytes32,
    difficulty: uint256,
    solution: Bytes[128]
) -> bool:
    mask = (1 << difficulty) - 1
    target_pattern = keccak256(challenge + solution[0:32]) & mask
    prev = solution[0:32]

    for i in range(1, 4):
        chunk = solution[i*32 : (i+1)*32]
        # ascending order requirement -- prevents trivial replays
        assert chunk > prev
        # all hashes share the same lowest-N bits
        assert (keccak256(challenge + chunk) & mask) == target_pattern
        prev = chunk

    return True

That is the whole algorithm. Four Keccak operations, a mask, three comparisons. The gas budget per submission is small enough that you can verify proofs on every block without choking throughput.

The real contract precomputes masks for the common difficulty levels (8, 16, 24, 32) so that the mask computation is a single SLOAD instead of an arithmetic shift. It also enforces global solution uniqueness across all epochs, blocking replay of a known-valid quad in a future round.

Why ascending order

The strict ascending-order requirement on the 4 values does two things:

1. Canonicalisation. There are 4! = 24 ways to order any 4-tuple. Without canonicalisation, a miner could submit the same set 24 times for one reward. Sorting collapses this to one valid encoding per unique set.
2. Cheap distinctness check. If v_2 > v_1, then v_2 != v_1. You get a “the four values are distinct” check for the price of a comparison.

It costs the miner nothing (sort 4 things) and saves the contract two storage reads.

Why on-chain verification matters

The fact that the verifier is a smart contract is the part that changes what’s possible.

Consider: a contract on Ethereum can verify, in its own logic, whether a given 128-byte proof would be a valid EVMORE mining solution. That means you can build, for example:

• A mining-pool contract that escrows rewards and pays out by proof attribution.
• A derivative that pays a yield based on observed mining throughput.
• A lending market that prices collateral against historical mining cost.
• A hashrate futures market.

None of these compose against Bitcoin without an oracle or a bridge. They compose against EVMORE because the validity of the underlying work is an EVM-callable function.

The footnote on Keccak

We picked Keccak-256 specifically because it is the Ethereum-native hash. Solidity’s keccak256() and Vyper’s keccak256() map directly to the SHA-3-family round function that the EVM has had since launch. The opcode is well-priced, well-tested, and ubiquitous. Picking SHA-256 (Bitcoin’s hash) would have made every verifier call wildly more expensive because the EVM does not have a native SHA-256 round opcode (only an expensive precompile).

The choice of Keccak is, in other words, the cost-aware choice for “verify the proof on Ethereum at low gas cost.”

Try it

The reference miner is in the evmore repository. The Vyper verifier is in contracts/KeccakCollisionVerifier.vy. The test suite exercises the corners (wrong order, non-distinct values, wrong difficulty, replay) in 718 lines of pytest. A solo miner on a single 4070 can expect to find their first solution in single-digit minutes at the launch difficulty.

The algorithm is not exotic. It is exactly as exotic as you need it to be to evict ASICs and stay verifiable on-chain. Everything else is an unnecessary complication.