Solve the Back-to-Genesis Problem using recursive SNARKs — This is an implementation of nChain’s solution¹. The Back-to-Genesis Problem Tokens on Bitcoin are typically stored in UTXOs. When a supposed token transaction is received, a user needs a way to efficiently and quickly check its authenticity. A major part is to decide if it links to certain genesis transaction, where the token…

Proof of a proof of a proof … — We present recursive Zero-Knowledge Proofs (ZKPs), where a proof attests to the validity of another proof. We show its benefits over standard non-recursive ZKPs and showcases its power by applying it to proving Fibonacci sequences. What is a recursive ZKP Suppose Peggy wants to prove to Victor that she will spend next week in a…

A practical step-by-step guide — Zokrates is a toolbox for zkSNARKs, hiding significant complexity inherent to zero-knowledge proofs (ZKP). It provides a python-like higher-level language for developers to code the computational problem they want to prove. We extend it to generate and verify proofs on Bitcoin. Install Zokrates From binary Run the following command to install released binaries: curl…

Solving Blockchain Privacy Dilemma Using Zero Knowledge — We show how to develop games with incomplete information on Bitcoin using Zero Knowledge Proof (ZKP), which is generally regarded unsuitable on a transparent blockchain. We use two games to exemplify the key processes. Paradox There are two categories of games: Complete information games. All players know everything about the game…

ZK Key-Statement Proof — Previously, we have showed how to construct zero-knowledge proof (ZKP) for the following statement, using a technique called ZK Key-Statement Proof (ZKKSP). Basically, it proves not only the prover knows a secret key to a given public key, but also the secret hashes to a given…

Prove Group Membership Without Ring Signatures — In Part 1, we have demonstrated zk-SNARK turns cryptographic problems into programming problems. As an example, we “programmed” elliptic curve point multiplication to prove knowledge of a private key for a given public key, the equivalent of a digital signature. Today, we show how to implement another otherwise sophisticated cryptographic…

Prove Knowledge of a Private Key Without Signatures — In theory, a zero-knowledge proof (ZKP) can be constructed for any mathematical problem¹, without revealing this solution. In practice, developing a ZKP for a problem often requires the invention of a whole new cryptographic algorithm. It has no standard recipe and requires extensive and in-depth knowledge of cryptography. For example…

MiMC is a “ZK-friendly” hash function, for which efficient Zero Knowledge Proofs (ZKP) can be generated. Previously, we discussed ZKP can be applied to any mathematical function using zk-SNARK. Internally, the function needs to be converted to a circuit, where only addition and multiplication operations are allowed. While all functions…

Way More Scalable than on Ethereum — ZK-Rollup is considered as the holy grail of Ethereum Layer 2 scaling solution. In general, my own view is that in the short term, optimistic rollups are likely to win out for general-purpose EVM computation and ZK rollups are likely to win out for simple payments, exchange and other application-specific…