04-17-2025 
|
Getting your Trinity Audio player ready...
|
This post was first published on Medium.
We are excited to announce the first successful Zero-Knowledge Bounty on the Bitcoin network. We have applied Zero-Knowledge Bounty to solve a 9×9 Sudoku puzzle.
Compared to Pay-to-Sudoku using Zero-Knowledge Contingent Payment (ZKCP), a seller does not have to interact with the buyer, who only needs to post a single bounty transaction. More crucially, the buyer cannot abort after the seller has spent resources solving the puzzle and proven the solution is valid, and thus deprive 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.
| // Circuit for proving the knowledge of the solution to a sudoku puzzle. | |
| template Main(N, sqrtN, lCyphertext) { | |
| // Private inputs: | |
| signal input w[N][N]; // Solition to the specified puzzle. | |
| 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. | |
| // TODO: Could also be hardcoded into the circuit like the unsolved puzzle. | |
| signal input Qb[2][4]; // Seller (Bob) public key. | |
| signal input nonce; // Needed to encrypt/decrypt xy. | |
| signal input ew[lCyphertext]; // 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. | |
| // Unsolved sudoku board. This could also be passed as a public input. | |
| var unsolved[N][N] = [ | |
| [0, 0, 0, 0, 0, 6, 0, 0, 0], | |
| [0, 0, 7, 2, 0, 0, 8, 0, 0], | |
| [9, 0, 6, 8, 0, 0, 0, 1, 0], | |
| [3, 0, 0, 7, 0, 0, 0, 2, 9], | |
| [0, 0, 0, 0, 0, 0, 0, 0, 0], | |
| [4, 0, 0, 5, 0, 0, 0, 7, 0], | |
| [6, 5, 0, 1, 0, 0, 0, 0, 0], | |
| [8, 0, 1, 0, 5, 0, 3, 0, 0], | |
| [7, 9, 2, 0, 0, 0, 0, 0, 4] | |
| ]; | |
| // step 1 | |
| //// Assert w is a valid solution. ////////////////////////////////////////////// | |
| component sudokuVerify = Sudoku(sqrtN, N); | |
| for (var i = 0; i < N; i++) { | |
| for (var j = 0; j < N; j++) { | |
| sudokuVerify.unsolved[i][j] <== unsolved[i][j]; | |
| sudokuVerify.solved[i][j] <== w[i][j]; | |
| } | |
| } | |
| // step 2 | |
| //// Assert that (db * Qa) = Qs //////////////////////////////////////////////// | |
| // This will ensure that Bob actually derived Qs using Alices public key Qa. | |
| // This uses Circom code to emulate operations on secp256k1 by 0xPARC: | |
| // https://github.com/0xPARC/circom-ecdsa | |
| component privToPub0 = Secp256k1ScalarMult(64, 4); | |
| for (var i = 0; i < 4; i++) { | |
| privToPub0.scalar[i] <== db[i]; | |
| } | |
| for (var i = 0; i < 4; i++) { | |
| privToPub0.point[0][i] <== Qa[0][i]; | |
| privToPub0.point[1][i] <== Qa[1][i]; | |
| } | |
| signal Qs_x_diff[4]; | |
| signal Qs_y_diff[4]; | |
| for (var i = 0; i < 4; i++) { | |
| Qs_x_diff[i] <-- privToPub0.out[0][i] - Qs[0][i]; | |
| Qs_x_diff[i] === 0; | |
| Qs_y_diff[i] <-- privToPub0.out[1][i] - Qs[1][i]; | |
| Qs_y_diff[i] === 0; | |
| } | |
| // step 3 | |
| //// Assert that (db * G) = Qb ///////////////////////////////////////////////// | |
| // This makes sure that Qb is really the public key corresponding to db. | |
| component privToPub1 = ECDSAPrivToPub(64, 4); | |
| for (var i = 0; i < 4; i++) { | |
| privToPub1.privkey[i] <== db[i]; | |
| } | |
| signal Qb_x_diff[4]; | |
| signal Qb_y_diff[4]; | |
| for (var i = 0; i < 4; i++) { | |
| Qb_x_diff[i] <-- privToPub1.pubkey[0][i] - Qb[0][i]; | |
| Qb_x_diff[i] === 0; | |
| Qb_y_diff[i] <-- privToPub1.pubkey[1][i] - Qb[1][i]; | |
| Qb_y_diff[i] === 0; | |
| } | |
| // step 4 | |
| //// Assert that encrypting w with Qs produces ew. ///////////////////////////// | |
| component p = PoseidonEncryptCheck(N*N); | |
| for (var i = 0; i < lCyphertext; i++) { | |
| p.ciphertext[i] <== ew[i]; | |
| } | |
| for (var i = 0; i < N; i++) { | |
| for (var j = 0; j < N; j++) { | |
| p.message[i*N + j] <== w[i][j]; | |
| } | |
| } | |
| component sharedKey = FromatSharedKey(); | |
| sharedKey.pointX[0] <== Qs[0][0]; | |
| sharedKey.pointX[1] <== Qs[0][1]; | |
| sharedKey.pointX[2] <== Qs[0][2]; | |
| sharedKey.pointX[3] <== Qs[0][3]; | |
| p.nonce <== nonce; | |
| p.key[0] <== sharedKey.ks[0]; | |
| p.key[1] <== sharedKey.ks[1]; | |
| p.out === 1; | |
| } |
Smart Contract
The bounty contract simply verifies the ZK proof at Line 20. If it is valid, it sends the bounty reward to the buyer, using OP_PUSH_TX, from Line 25 to 30.
| contract SudokuBounty { | |
| ECPoint Qa; // Buyer's (Alice) public key. | |
| VerifyingKey vk; // Verifying key from the circuits setup. | |
| int satsReward; // Amount of satoshis to be handed as a reward for the solution. | |
| int expirationBlockN; // nLocktime of deadline when Alice can reclaim the reward. | |
| public function unlock( | |
| ECPoint Qb, // Bobs public key. | |
| int[82] ew, // Solution of puzzle, encrypted with shared key Qs. | |
| Sha256 Hpub, // Hash of public inputs. | |
| int nonce, // Nonce for encryption with shared key. Can be timestamp. | |
| Proof pi, // Proof of solution for the whole circuit C. | |
| SigHashPreimage preimage | |
| ) { | |
| // ... | |
| //// Verify the proof. //////////////////////////////////////////////////////////////////////////// | |
| bool proofCorrect = ZKSNARK.verifyOptimized(pubInputs, pi, this.vk); | |
| require(proofCorrect); | |
| //// Ensure next output will pay Qb. ////////////////////////////////////////////////////////////// | |
| require(Tx.checkPreimage(preimage)); | |
| Ripemd160 pkh = hash160(point2PubKey(Qb)); | |
| bytes outputScript = Utils.buildPublicKeyHashScript(pkh); | |
| bytes output = Utils.buildOutput(outputScript, this.satsReward); | |
| require(hash256(output) == SigHash.hashOutputs(preimage)); | |
| } | |
| public function refund(Sig aliceSig, SigHashPreimage preimage) { | |
| // ... | |
| } | |
| } |
Alice can reclaim the bounty if nobody claims it by the deadline at Line 33.
A working example
As in the general ZK bounty, there are three steps:
- Alice places a bounty transaction Tm 8e524b7de2f42cf45daf2851e00161ee6984780c464e484b88b34bb6c629911f for the Sudoku puzzle in Line 22–32 of the circuit.
- 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, containing the proof and the encrypted solution. - Using Tc, Alice derives the same shared key using her own private key and Bob’s public key in Tc’s output, decrypt the encrypted solution in Tc’s input to get the final solution.
Note there is no back-and-forth interaction between Alice and Bob and no trusted middleman involved. Also nobody else watching both transactions knows the solution since it is encrypted.
The full code can be found at this repo, with an end-to-end test and deployment.
Optimization: reduce number of public inputs
The on-chain ZKP verifier does a elliptic curve scalar multiplication for each public input of the circuit, which is rather expensive. We pass these inputs as private parameters to the circuit and only used their hash as a public input. Both the circuit and smart contract assert that hashing these inputs actually produces the specified hash. This approach reduces public inputs from 100 (each field of the Sudoku board needs its own input) down to only 2.
Watch: The BSV Global Blockchain Convention presentation, Smart Contracts and Computation on BSV
Recommended for you
