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.
Verifying hidden Sudokus
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.
Decentralized Infrastructure for Project Euler problems
Project Euler is perhaps the site where I learned the most about programming. It submits problems mixing mathematics and computer science and of varying difficulty (the first problem was solved by a million people; some have only a dozen solutions at their output). To avoid brute-force attacks, which would consist of testing all possible solutions to a problem, the site uses a system of captchas. How could one decentralize Project Euler? The two main problems are
1. verifying solutions without revealing them in the smart contract, either in advance in the verification function or after the answer has been submitted;
2. discouraging brute-forceto attempts.
Zk-SNARKs are a perfect answer to the first problem, since they allow to check a solution without revealing it. For the second problem, we have chosen the following approach: each problem is provided with a nonce. The solution stored (but obfuscated by the zk-SNARKs) in the contract is actually :
SHA256¹⁰⁰⁰⁰⁰⁰(problem number | solution | nonce)
Computing one million iterations of SHA256 takes about 20 seconds, which in a way emulates the captcha. This does not, however, protect against a pre-computation of all possible solutions, hence the presence of the nonce and the problem number, which makes the attacker’s task much more difficult. With this simple trick, the Project Euler submission platform can be completely decentralized!
Recovering from a lost key using a passphrase
Our last use case of zk-SNARKs on FreeTON is more technical: it is to propose a backup solution to change the public key controlling a FreeTON wallet. A common solution to protect oneself from the loss of a private key is the multisig, and in fact the FreeTON wallets are multisig by default. It is then a question of keeping the recovery key in a safe place, typically in a bank safe (a paradox of the cryptocurrency world…). But this is a very slow solution, to which we propose an alternative: choose a password that allows to change the public key that controls a wallet. This solution should be avoided in the absence of zk-SNARKS: the password (or its hash) can always be intercepted and reused by an attacker to hijack the wallet to his advantage. In the framework of zk-SNARKs, the zero-knowledge proof attests to the knowledge of the password coupled with the public key, so that this proof is unusable with another public key.
Conclusion
Participating in this very fun contest allowed us to think about the different uses of zk-SNARKs on the blockchain. Although this first step is much simpler than the Z-cash applications, which are the subject of separate contests, we have already identified different categories:
1. Computation (a precise mathematical calculation is encoded in the zk-SNARK instance used): this is the case of Sudoku, it could have been the factorisation of an integer for example;
2. Static : the static answer is known, and we just check that the user knows it (possibly with a brute-force) : this is the case of Project Euler;
3. Protocol: The essential function of zk-SNARK can be a calculation or static, but the essential issue is to act at the protocol level by triggering transactions or modifying access rights: this is the case of Pincode.
It is easy to see that these categories are not isolated from one another, but they allow us to think about usage paradigms.
Wish us good luck for the upcoming vote and don’t hesitate to ask us questions in the comments section or on twitter!
—
If you want to know more about FreeTON, you can visit our website www.freeton.link and try our wallet in OCaml ft.
