A Practical Data Trading Protocol for Sudoku Solutions

Abstract

Developing a fair, efficient, and scalable data trading protocol in decentralized networks has attracted much research effort recently. Zero-knowledge contingent payments (ZKCP) allows sellers and buyers to complete their trade fairly over the blockchain using zero-knowledge proofs. However, it suffers from memory-intensive requirements and scalability limitations. In this paper, we propose a practical data trading protocol tailored for Sudoku solutions, which is fair, efficient, and scalable. The core component of our protocol is a zero-knowledge argument for the correctness of a Sudoku solution of homomorphic encryption. This argument achieves sublinear communication complexity and the number of group exponentiations for both proving and verification is linear in the size of Sudoku solutions. The security of our protocol can be proven in the random oracle model under the Decision Diffie-Hellman assumption. In addition, we devise a mechanism that allows buyers to recover the private key through two zero-knowledge proofs and prevents the direct exposure of the decryption key. Furthermore, we implement the proposed protocol on the Ethereum testnet, and the experimental results show a significant improvement in overall efficiency.