The First Successful Zero-Knowledge Pay-to-Sudoku Bounty on Bitcoin

This post was first published on Medium.

We are pleased to announce the first successful Zero-Knowledge Bounty on the Bitcoin network. We have used the Zero-Knowledge Bounty to solve a 9×9 Sudoku puzzle.

Compared to Pay-to-Sudoku which uses Zero-Knowledge Contingent Payment (ZKCP), a seller does not need to interact with the buyer, who only needs to post a single bounty transaction. More crucially, the buyer cannot cancel after the seller has spent resources solving the puzzle and proven that the solution is valid, thereby depriving the seller of payment by refusing to post a bounty transaction.

Circuit

The circuit is an instantiation of the generic ZK bounty circuit. In step 1, the subcircuit C validates the Sudoku solution. In step 4, the ZKP-friendly Poseidon encryption is used.

Smart contract

The bounty contract simply validates the ZK proof on line 20. If valid, it sends the bounty reward to the buyer, using OP_PUSH_TX, from lines 25 to 30.

SudokuBounty contract

Alice can reclaim the bounty if no one claims it within the deadline on line 33.

A working example

As in the general ZK bounty, there are three steps:

1. Alice places a bounty transaction Tm 8e524b7de2f42cf45daf2851e00161ee6984780c464e484b88b34bb6c629911f for the Sudoku puzzle in lines 22–32 of the circuit.
2. Bob solves the puzzle and encrypts the solution with a shared ECDH key. He generates a ZK proof and submits a transaction
   Tc 32b3b9906d4cdfe2aa5fe6aeec31d39d7b3040bf3d8548296cd7ad04f288fab1 to claim the bounty, which contains the proof and the encrypted solution.
3. Using TcAlice retrieves the same shared key using her own private key and Bob’s public key Tcits output, decrypts the encrypted solution in Tc’s input to get the final solution.

Note that there is no back-and-forth interaction between Alice and Bob and no trusted intermediary involved. Also no one else looking at both transactions knows the solution since it is encrypted.

The complete code can be found in this repo, with an end-to-end test and deployment.

Optimization: reduce the number of public inputs

The chained ZKP verifier does an elliptic curve scalar multiplication for each public input to the circuit, which is quite expensive. We pass these inputs as private parameters to the circuit and just used their hash as a public input. Both the circuit and the smart contract assert that hashing these inputs actually produces the specified hash. This approach reduces public input from 100 (each field on the Sudoku board needs its own input) down to just 2.

See: The presentation of the BSV Global Blockchain Convention, Smart Contracts and Computation on BSV

width=”560″ height=”315″ frameborder=”0″ allowfullscreen=”allowfullscreen”>

New to Bitcoin? Check out CoinGeeks Bitcoin for beginners section, the ultimate resource guide for learning more about Bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.