In the second part of our Zero-Knowledge Bounty (ZKB) series, we apply it to solving hash collision puzzles. In such a puzzles, two distinct inputs hash to the same output. Such bounties can be used to:
- act as a canary in a coal mine and give us a valuable heads-up. Existence of collisions is a sign that a hash function is weak, so we can upgrade early on to alleviate damages.
- fund research to discover vulnerabilities in hash functions, especially for new ones such as MiMC.
History
Bitcoin bounties for finding collisions in a variety of hash functions were originally posted by Bitcoin developer Peter Todd in 2013. The SHA1 bounty was collected in 2017, shortly after Google broke it.
This primitive bounty has two drawbacks:
- Once someone broadcasts a collecting transaction containing the solution, miners can intercept it, extract the solution, and redirect the reward to themselves.
- The solution is made public, which can be exploited by malicious actors.
ZKB addresses both so that only the bounty collector, who finds the collisions, can redeem it and only the bounty maker can learn the solution.
Implementation
As in Part 1, we only have to replace the application specific circuit C to verify two preimages (i.e., inputs to the hash function) are different yet they produce the same hash. We use the Poseidon hash function as an example, a new ZK-friendly hash. Other hash functions can be used similarly. The two preimages get passed in as private inputs and are never revealed publicly.
The full code along with tests is available on GitHub, including a smart contract that verifies the proof and pays the bounty collector.
