codenlighten/scrypt

1---2sidebar_position: 53---4 5# Tutorial 5: Zero Knowledge Proofs6 7## Overview 8 9In this tutorial we will go over how to create a zero-knowledge proof (ZKP) and verify it on Bitcoin using sCrypt.10 11### What are zk-SNARKS?12 13SNARK (zero-knowledge Succinct Non-interactive ARguments of Knowledge) is a type of ZKP that is amenable for blockchains. The generated proof is “succinct” and “non-interactive”: a proof is only a few hundred bytes and can be verified in constant time and within a few milliseconds, without needing to ask additional questions of the prover. Together, these properties make zk-SNARK especially suitable for blockchains, where on-chain storage and computation can be expensive and senders often go offline after sending a transaction. 14 15A proof is constructed off-chain by a prover who generates the proof using a secret input (often referred to as the "witness") and a public input. The prover can then use this proof as an input for an sCrypt smart contract, which can verify the validity of the proof using a verification key and the public input.16 17![](../../static/img/zksnark-verifier.png)18 19[Credit: altoros](https://www.altoros.com/blog/securing-a-blockchain-with-a-noninteractive-zero-knowledge-proof/)20 21 22There are many tools for creating such proofs, [ZoKrates](https://github.com/sCrypt-Inc/zokrates) and [SnarkJS](https://github.com/sCrypt-Inc/snarkjs) are among the most popular. 23 24In this example we will use ZoKrates. It provides a python-like higher-level language for developers to code the computational problem they want to prove.25 26For a more comprehensive explanation of zk-SNARKS and how they work, we recommend reading [this blog post](https://xiaohuiliu.medium.com/zk-snarks-on-bitcoin-239d96d182bd).27 28## Install ZoKrates29 30Run the following command to install [released binaries](https://github.com/sCrypt-Inc/zokrates/releases):31 32```sh33curl -Ls https://scrypt.io/scripts/setup-zokrates.sh | sh -s -34```35 36or build from source:37 38```sh39git clone https://github.com/sCrypt-Inc/zokrates40cd ZoKrates41cargo +nightly build -p zokrates_cli --release42cd target/release43```44 45## ZoKrates Workflow46 47### 1. Design a circuit48 49Create a new ZoKrates file named `factor.zok` with the following content:50 51```python52// p, q are the factors of n53def main(private field p, private field q, field n) {54    assert(p * q == n);55    assert(p > 1);56    assert(q > 1);57    return;58}59```60 61This simple circuit/program proves one knows a factorization of an integer `n` into two integers, without revealing the factors. The circuit has two private inputs named `p` and `q` and one public input named `n`.62 63 64### 2. Compile the circuit65 66Compile the circuit with the following command:67 68```sh69zokrates compile -i factor.zok70```71 72This generates two files that encode the circuit in binary and human-readable format.73 74### 3. Setup75 76This generates a proving key and a verification key for this circuit.77 78```sh79zokrates setup80```81 82### 4. Calculate a witness83 84A proof attests that a prover knows some secret/private information that satisfies the original program. This secret information is called witness. In the following example, `7` and `13` are the witnesses, as they are factors of `91`.85 86```sh87zokrates compute-witness -a 7 13 9188```89 90A file named `witness` is generated.91 92### 5. Creating a proof93 94The following command produces a proof, using both the proving key and the witness:95 96```sh97zokrates generate-proof98```99 100The resulting file `proof.json` looks like the following:101 102```json103{104  "scheme": "g16",105  "curve": "bn128",106  "proof": {107    "a": [108      "0x0a7ea3ca37865347396645d017c7623431d13103e9107c937d722e5da15f352b",109      "0x040c202ba8fa153f84af8dabc2ca40ff534f54efeb3271acc04a70c41afd079b"110    ],111    "b": [112      [113        "0x0ec1e4faea792762de35dcfd0da0e6859ce491cafad455c334d2c72cb8b24550",114        "0x0985ef1d036b41d44376c1d42ff803b7cab9f9d4cf5bd75298e0fab2d109f096"115      ],116      [117        "0x265151afd8626b4c72dfefb86bac2b63489423d6cf895ed9fa186548b0b9e3f3",118        "0x301f2b356621408e037649d0f5b4ad5f4b2333f58453791cc24f07d5673349bf"119      ]120    ],121    "c": [122      "0x2b75a257d68763100ca11afb3beae511732c1cd1d3f1ce1804cbc0c26043cb6b",123      "0x2f80c706b58482eec9e759fce805585595a76c27e37b67af3463414246fbabbd"124    ]125  },126  "inputs": [127    "0x000000000000000000000000000000000000000000000000000000000000005b"128  ]129}130```131 132### 6. Export an sCrypt verifier133 134Using our version of ZoKrates, we can export a project template, which will contain a verifier for our circuit. Simply run the following command:135 136```sh137zokrates export-verifier-scrypt138``` 139 140This will create a directory named `verifier`, containing the project. Let's set it up. Run the following:141 142```sh143cd verifier && git init && npm i144```145 146Now the verifier is ready to be used. In the following section we will go over the code and show how to use it.147 148 149### 7. Run the sCrypt Verifier150 151In the generated project, let's open the file `src/contracts/verifier.ts`. This file contains an sCrypt smart contract, named `Verifier`, which can be unlocked by providing a valid ZK proof.152 153Under the hood it uses the `SNARK` library from `src/contracts/snark.ts`. This file includes an elliptic curve implementation along with a library that implements pairings over that elliptic curve and lastly the implementation of the proof verification algorithm. In our example the [`BN-256` elliptic curve](https://hackmd.io/@jpw/bn254) is being used along with the [`Groth-16` proof system](https://eprint.iacr.org/2016/260.pdf)..154 155Let's take a look at the implementation of `Verifier`:156 157```ts158export class Verifier extends SmartContract {159    160    @prop()161    vk: VerifyingKey162 163    @prop()164    publicInputs: FixedArray<bigint, typeof N_PUB_INPUTS>,165 166    constructor(167      vk: VerifyingKey,168      publicInputs: FixedArray<bigint, typeof N_PUB_INPUTS>,169      ) {170        super(...arguments)171        this.vk = vk172        this.publicInputs = publicInputs173    }174    175    @method()176    public verifyProof(177        proof: Proof178    ) {179        assert(SNARK.verify(this.vk, this.publicInputs, proof))180    }181 182}183```184 185As we can see, the contract has two properties, namely the verification key and the value(s) of the public inputs to our ZK program. 186 187The contract also has a public method named `verifyProof`. As the name implies it verifies a ZK proof and can be unlocked by a valid one. The proof is passed as a parameter. The method calls the proof verification function:188 189```ts190SNARK.verify(this.vk, this.publicInputs, proof)191```192 193The function takes as parameters the verification key, the public inputs and the proof. It's important to note that the proof is cryptographically tied to the verification key and thus must be a proof about the correct ZoKrates program (`factor.zok`).194 195The generated project will also contain a deployment script `deploy.ts`. Let's take a look at the code:196 197```ts198async function main() {199    await Verifier.compile()200    201    // TODO: Adjust the amount of satoshis locked in the smart contract:202    const amount = 100203 204    // TODO: Insert public input values here:205    const publicInputs: FixedArray<bigint, typeof N_PUB_INPUTS> = [ 0n ]206 207    let verifier = new Verifier(208        prepareVerifyingKey(VERIFYING_KEY_DATA),209        publicInputs210    )211 212    // Connect to a signer.213    await verifier.connect(getDefaultSigner())214 215    // Deploy:216    const deployTx = await verifier.deploy(amount)217    console.log('Verifier contract deployed: ', deployTx.id)218}219 220main()221```222 223We can observe that we need to adjust two things. First, we need to set the amount of satoshis we will lock into the deployed smart contract. The second thing is the public input value, i.e. the product of the secret factors. Let's set it to the value `91`:224 225```ts226const publicInputs: FixedArray<bigint, typeof N_PUB_INPUTS> = [ 91n ]227```228 229Note also, that ZoKrates already provided us with the values of the verification key, that we created during the setup phase.230 231Now, we can build and deploy the contract. Simply run:232 233```sh234npm run deploy235```236 237The first time you run the command, it will ask you to fund a testnet address. You can fund it using [our faucet](https://scrypt.io/faucet/).238 239After a successful run you should see something like the following:240 241```242Verifier contract deployed:  2396a4e52555cdc29795db281d17de423697bd5cbabbcb756cb14cea8e947235243```244 245The smart contract is now deployed and can be unlocked using a valid proof, that proves the knowledge of the factors for the integer `91`. You can see [the transaction](https://test.whatsonchain.com/tx/2396a4e52555cdc29795db281d17de423697bd5cbabbcb756cb14cea8e947235) using a block explorer.246 247Let's call the deployed contract. Let's create a file named `call.ts` with the following content:248 249```ts250import { DefaultProvider } from 'scrypt-ts'251import { parseProofFile } from './src/util'252import { Verifier } from './src/contracts/verifier'253import { Proof } from './src/contracts/snark'254import { getDefaultSigner } from './tests/utils/helper'255import { PathLike } from 'fs'256 257export async function call(txId: string, proofPath: PathLike) {258    await Verifier.compile()259 260    // Fetch TX via provider and reconstruct contract instance261    const provider = new DefaultProvider()262    const tx = await provider.getTransaction(txId)263    const verifier = Verifier.fromTx(tx, 0)264    265    // Connect signer266    await verifier.connect(getDefaultSigner())267 268    // Parse proof.json269    const proof: Proof = parseProofFile(proofPath)270 271    // Call verifyProof()272    const { tx: callTx } = await verifier.methods.verifyProof(273        proof274    )275    console.log('Verifier contract unlocked: ', callTx.id)276}277 278(async () => {279  await call('2396a4e52555cdc29795db281d17de423697bd5cbabbcb756cb14cea8e947235', '../proof.json')280})()281```282 283The function `call` will create the contract instance from the passed [TXID](https://wiki.bitcoinsv.io/index.php/TXID) and call its `verifyProof` method. The proof gets parsed from `proof.json`, which we already created in the section above.284 285Let's unlock our contract by running the following command:286```287npx ts-node call.ts288```289 290If everything goes as expected, we have now unlocked the verifier smart contract. You'll see an output similar to the following:291 292```293Verifier contract unlocked:  30127e0c340878d3fb7c165e2d082267eef2c8df79b5cf750896ef565ca7651d294```295 296Take a look at it using [a block explorer](https://test.whatsonchain.com/tx/30127e0c340878d3fb7c165e2d082267eef2c8df79b5cf750896ef565ca7651d).297 298## Conclusion299 300Congratulations! You have successfully created a zk-SNARK and verified it on-chain!301 302If you want to learn how you can integrate zk-SNARKS into a fully fledged Bitcoin web application, take a look at our free [course](https://academy.scrypt.io/en/courses/Build-a-zkSNARK-based-Battleship-Game-on-Bitcoin-64187ae0d1a6cb859d18d72a), which will teach you how to create a ZK Battleship game.303Additionally, it teaches you to use [snarkjs/circom](https://github.com/sCrypt-Inc/snarkjs).304 305To know more about ZKP, you can refer to [this awesome list](https://github.com/sCrypt-Inc/awesome-zero-knowledge-proofs).306