Zk-SNARKs, FreeTON and OCamlPro
You may have heard of zk-SNARKs, the mathematical black magic enabling you, under certain conditions, to prove that you know a solution to a problem without revealing any information about that solution. Such a proof is called a zero-knowledge proof. It used to be a (mostly) theoretical amusement for cryptographers; since Zcash, it has become a very real application on blockchains. Many projects are integrating some form of zk-SNARKs, such as Ethereum, Tezos or Concordium. The Mina project is even building its entire blockchain from zk-SNARKs!
Last year, thanks to our in-house Liquidity programming language, we had started to adapt and extend zk-SNARKs on Tezos in the Dune Network project which is in the process of merging with FreeTON. With the introduction of zk-SNARKs on FreeTON by the Nil Foundation, it was time to get back to it! We participated in the last few weeks in Contest 18, where we had to propose applications of this technology on FreeTON smart contracts. The results are not yet known, but we are proud to tell you about our submission which contains three different applications.
The first one consists in a smart contract for solving Sudokus. The Sudoku is to zero-knowledge proofs what the Rock-Paper-Scissors game is to smart contracts: a simple example, useful to explain the concept at hand, but already sufficiently annoying to pose some technical problems. In particular, we need to find an encoding of the Sudoku constraints in the form of a quadratic program (details in our submission for the curious). Then, the principle is simple: a Sudoku instance is proposed by the contract, and the user must find a solution, generate a local zero-knowledge proof that he has found it, and submit it to the contract.
