Pay-to-sudoku Revisited

Sean Bowe | Jun 08, 2017

Last year, I created a project called pay-to-sudoku which was the world's first implementation of a zero-knowledge contingent payment (ZKCP). ZKCPs were invented in 2011 by Gregory Maxwell, and are a clever cryptographic trick that allows people to trade information and value atomically over a blockchain. Gregory was also kind enough to help me demonstrate it to Financial Cryptography 2016!

In pay-to-sudoku, one person (the "buyer") can pay another person (the "seller") to solve a Sudoku puzzle. The seller solves the puzzle and encrypts the solution with a key that is then hashed. Using a zero-knowledge proof ― in this case, a zk-SNARK using libsnark ― the seller constructs a proof that they have an encrypted solution to the puzzle, and that knowledge of a particular SHA256 hash will permit decryption.

The buyer proceeds to submit a payment to the blockchain that allows the seller to redeem some funds in exchange for revealing the SHA256 preimage (the key). When the seller does this, the buyer can decrypt.

In order to achieve this with a zk-SNARK, the buyer is responsible for constructing a common reference string (CRS) that allows the seller to evaluate a proof. Campanelli, Gennaro, Goldfeder and Nizzardo have just published a new paper that identifies a flaw in the way pay-to-sudoku uses the PGHR construction implemented in libsnark. In particular, it assumes that the CRS has correct algebraic structure, and as a result, the buyer has an opportunity to violate zero-knowledge to obtain information about the solution without paying for it.

Note that Zcash's public parameters are not vulnerable to this kind of malicious setup because the multi-party computation transcript guarantees the correctness of the CRS, even if all of the participants of the MPC were dishonest. This is pointed out by the paper as well.

There are several mitigating steps that can be taken when using a third-party CRS. Just as we did with Zcash's public parameters, it is sufficient to ensure the parameters are constructed correctly using a multi-party computation protocol. Not allowing incorrect structure in the CRS is sufficient to defend against the particular attacks described in the paper. As an additional precaution, verify the proof after you construct it!

The paper additionally proposes some other interesting ideas, such as an extension of the concept of a ZKCP to the purchase of digital services rather than digital goods (like sudoku solutions).

ZKCP, cryptography, zkSNARKs | View all tags