比特币 ZK 赏金系列：第 2 部分——查找哈希冲突

在我们的零知识赏金 (ZKB) 系列的第二部分中，我们将其应用于解决哈希冲突难题。在这样的谜题中，两个不同的输入散列到相同的输出。此类赏金可用于：

1. 充当煤矿中的金丝雀，给我们一个有价值的提醒。存在冲突是散列函数较弱的标志，因此我们可以尽早升级以减轻损失。

2. 资助研究以发现哈希函数中的漏洞，特别是对于 MiMC 等新函数。

碰撞攻击

历史

比特币开发者彼得托德于 2013 年最初发布了用于发现各种哈希函数中的冲突的比特币赏金。SHA1 赏金是在 2017 年收集的，在谷歌破解它后不久。

最初的哈希碰撞赏金

这种原始赏金有两个缺点：

1. 一旦有人广播包含解决方案的收集交易，矿工就可以拦截它，提取解决方案，并将奖励重定向到他们自己。

2. 该解决方案是公开的，可以被恶意行为者利用。

ZKB 解决了这两个问题，因此只有发现碰撞的赏金收集者才能赎回它，并且只有赏金制定者才能了解解决方案。

实现

与第 1 部分一样，我们只需替换特定于应用程序的电路 C 即可验证两个原像（即散列函数的输入）不同但它们产生相同的散列。我们以 Poseidon 哈希函数为例，一种新的 ZK 友好哈希。其他哈希函数可以使用类似方式。这两个原像作为私有输入传递进来，永远不会公开透露。

template Main() {    // Private inputs:    signal input preimage0[16];     signal input preimage1[16];    signal input db[4];                      // Seller (Bob) private key.    signal input Qs[2][4];                   // Shared (symmetric) key. Used to encrypt w.        // "Public" inputs that are still passed as private to reduce verifier size on chain:    signal input Qa[2][4];                   // Buyer (Alice) public key.    signal input Qb[2][4];                   // Seller (Bob) public key.    signal input nonce;                      // Needed to encrypt/decrypt xy.    signal input ew[34];                     // Encrypted solution to puzzle.    // Public inputs:    signal input Hpub[2];            // Hash of inputs that are supposed to be public.         // As we use SHA256 in this example, we need two field elements         // to acommodate all possible hash values.         Assert that public inputs hash to Hpub. ///    ...     Assert that preimages are a valid solution. //    // Check preimage0 and preimage1 are differend and that they produce the same hash.    var diff = 0;    for (var i = 0; i < 16; i++) {        diff += preimage0[i] ^ preimage1[i];    }    assert(diff != 0);    component h0 = Poseidon(16);    component h1 = Poseidon(16);    for (var i = 0; i < 16; i++) {        h0.inputs[i] <== preimage0[i];        h1.inputs[i] <== preimage1[i];    }    h0.out === h1.out;     Assert that (db * Qa) = Qs     ...     Assert that (db * G) = Qb /    ...     Assert that encrypting w with Qs produces ew. /    ...}

GitHub 上提供了完整的代码和测试，包括验证证明并支付赏金收集者的智能合约。

来源地址：https://blog.csdn.net/freedomhero/article/details/133072938