ZoKratesでzk-SNARKs

# zk-SNARKsとは
zk-SNARKsとは、ある関数の実行結果が正しいことを、その関数の引数の一部を**秘匿に**しながら**簡潔に**証明することができるアルゴリズムです。
例えば、次のような関数を考えてみましょう。

```
function C(x, y) {
  return ( x*x == y );
}
```
この関数は```x```の2乗が```y```と等しいかどうかを確認して正しければ```true```、間違っていれば```false```を返します。

いま、Aliceは```y = 16```に対して```C(x, y) = true```となる```x```(つまり```x = 4```)を知っていることを、Bobに対して証明したいとします。

ただし、Aliceは```x = 4```をBobや他の人に知られたくありません(この例では``y　 = 16``から``x``を簡単に逆算できるので意味が無いですが、ハッシュ関数などの一方向性関数の場合は``y``から``x``を知ることは難しくなります。後でハッシュ関数の例を扱います)。


これはzk-SNARKを使って次のような手順で実現できます。

- Step 1. Bobは関数`C(x, y)`からproving key ```pk```とverification key ```vk```を作成して公開します。

```
(pk, vk) = Generate(C)
```

- Step 2. Aliceはproving key```pk```と公開入力```y = 16```, 秘密入力```x = 4```を利用してproof ```pf```を作成し、公開します。

```
pf = Prove(pk, x, y)
```

- Step 3. Bobはproof ```pf```, verification key ```vk```, 公開入力```y = 16```を使って認証します。　認証に成功すればBobはAliceが```C(x, 16)=true```を満たす```x```を知っていることを確証できます。

```
Verify(pf, vk, y)
```


補足

- Bobは```x```の値を知ることができません（これがzk-SNARKsの秘匿性に当たります）。 
- proof ```pf```のサイズは関数```C```の計算量やwitness```x, y```のサイズに依存しません(これがzk-SNARKsの簡潔性に当たります)。
- proof ``pf``は実行ごとに違う値になります。複数回認証をする場合は、使いまわしによる偽装を防ぐために、一度使用された``pf``を記録しておき、二度と同じものを受け付けてはいけません。


参考文献

https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b

https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/

# ZoKratesとは
ZoKratesとはzk-SNARKsのツールボックスです。上の例の```Generate, Prove, Verify```に相当する関数を提供しています。 また```Verify```関数のSolidityコードでの実装を出力してくれるので、認証部分をcontractとしてイーサリアムネットにデプロイすることが可能です。

https://zokrates.github.io/

https://github.com/Zokrates/ZoKrates

注意 
> This is a proof-of-concept implementation. It has not been tested for production.

とのことです。
## Install
Linux, MacOS and FreeBSDへのインストール

```bash
curl -LSfs get.zokrat.es | sh
 ```

Dockerで使うこともできます。

```
docker run -ti zokrates/zokrates /bin/bash
```

# 使ってみる
最初の例(Aliceが```x * x = 16```を満たす```x```を知っているとBobに証明する例)を実装してみましょう。
```root.zok```ファイルを作成し、以下のコードを書き込みます。

```python
def main(private field x, field y){
  assert(x * x == y);
  return;
}
```

型```field```は```[0, p - 1]```の範囲の整数の型を表します。ただし```p```は非常に大きな素数

```
21888242871839275222246405745257275088548364400416034343698204186575808495617
```
です。``private``は引数```x```が秘密であることを示します。


- コンパイル(Bobが行う)

```
zokrates compile -i root.zok
```

　```out```ファイルが生成されます。

- verification keyとproving keyの作成(Bobが行う)

```
zokrates setup
```

2つのファイル``verification.key``と``proving.key``が生成されます。

注: デフォルトでは``G16``と呼ばれる証明スキームを利用して鍵が生成されますが、このスキームは一つの``pf``から別の有効な``pf``が生成できてしまうという脆弱性があります。従って一回の鍵生成につき一回の認証しか安全に行なえません。鍵を使いまわしたい場合は別の証明スキームを利用する必要がります。例えば``GM17``スキームを利用する場合はオプションに``--proving-scheme gm17 --backend ark``を指定します。　ここで``--backend ark``は``GM17``スキームに対応しているバックエンド``ark``を指定しています。
・ ``zokrates generate-proof``
・ ``zokrates verify``
・ ``zokrates export-verifier``
においても同様に指定する必要があります。

https://zokrates.github.io/toolbox/proving_schemes.html

- proofの作成(Aliceが行う)


```
zokrates compute-witness -a 4 16
zokrates generate-proof
```
``-a``オプションで引数```x, y```を入力します。
　proof ```proof.json```が生成されます。
proofの中身は次のようになっています。

```json
{
  "proof": {
    "a": [
      "0x1eba2ac7caa6c8dfd93a23876bbfbe18f235dac3016b651b96a823ad76b66c0f",
      "0x203bfe12215d6541a540dc587ea8c3ef3a4f1b95c564cf5b19081d89f7065aa0"
    ],
    "b": [
      [
        "0x153e13df8ace8336acca9693fc1eb93f2084f13a571a39f52c3486095b56f63d",
        "0x047d35803bb05bb79889673d3091db5f401a4daec380d2be746543b23d8d5f7c"
      ],
      [
        "0x2bed1dcdc967642bd36924f00e60cf516ad832ec782e406b16295315cae2e35f",
        "0x23634f713241e7aea135f150c84dc1ff3d3e1d0b70e95e2e0167d35b478607a5"
      ]
    ],
    "c": [
      "0x2d1943ad01dd7acb487e95a310802b570229447d726c47370dffdf075f731170",
      "0x2e596b38f720ae614d0ffa6f9e4d4df5e154be1de9e7cdbed7769696950daeea"
    ]
  },
  "inputs": [
    "0x0000000000000000000000000000000000000000000000000000000000000010"
  ]
}
```

確かに、``inputs``には公開入力の``y``の値``0x0000000000000000000000000000000000000000000000000000000000000010``
(``10``進数に直すと``16``)が記録されています。

- 認証できるか確認

```
zokrates verify
```

``PASSED``が返ってきたら成功です。


- verifierの作成

```
zokrates export-verifier
```

Solidityファイル```verifier.sol```が出力されます。

# Deploy
hardhatでデプロイしてみます。
```bash 
yarn add hardhat
yarn hardhat
```
でhardhatのTypescript templateを作成後、`verifier.sol`を`contracts`ディレクトリに配置し、`scripts/deploy.ts`を次のように編集します。

```typescript
import { ethers } from "hardhat";

async function main() {
  const Verifier = await ethers.getContractFactory("Verifier");
  const verifier = await Verifier.deploy();
  await verifier.deployed();
  const proof = require("path/to/proof.json");
  const result = await verifier.verifyTx(proof.proof, proof.inputs);
  console.log(result);
}

main().catch((error) => {
  console.error(error);
  process.exitCode = 1;
});

```

`yarn hardhat run scripts/deploy.ts`を実行し、`true`が表示されることを確認します。

補足
一般的なケースでは、AliceはユーザーでBobは開発者です。BobはZoKratesを持っていますがAliceは持っていません。Aliceがproofを作成するステップは、ZoKratesのjs版をWebアプリに組み込むなどの実装が必要になります。

https://zokrates.github.io/toolbox/zokrates_js.html

# ユースケース: パスワード認証
Aliceがパスワード```m```を知っていることをBob(contract)に証明したい場合を考えます。


Bobは`m`のハッシュ値`h = hash(m)`を保持しておき、Aliceが送信してきたパスワード`m'`が`hash(m') = h`を満たすことをチェックするというのが簡単な方法ですが、この方法ではAliceが送信したパスワードは丸見えになってしまいます。

zk-SNARKsを使うと、Aliceは「`hash(m') = h`となる`m'`を知っている」というステートメントを`m'`を明かさずに証明することができます。

今回は```field```型の4つの整数```0, 0, 0, 5```をパスワードにすることにします。

まずこのパスワードのハッシュ値を計算するために```hash.zok```ファイルを作成します。

```python
import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> field[2]{
    field[2] h = sha256packed([a, b, c, d])
    return h
}
```

ここで```sha256packed```は4つの```field```型整数のハッシュ値を2つの```field```型整数として出力する関数です。　

ハッシュ値を計算するためコンパイルしてwitnessを作成します。

```
zokrates compile -i hash.zok
zokrates compute-witness -a 0 0 0 5
```

witnessファイルの```~out```から始まる行に返り値が格納されているので、```grep '~out' witness```で見てみます。

```
~out_0 263561599766550617289250058199814760685
~out_1 65303172752238645975888084098459749904
```

秘密の入力```a, b, c, d```のハッシュ値がこれらと等しくなるかを検証する```hashcheck.zok```ファイルを作成します。

```python
import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d){
    field[2] h = sha256packed([a, b, c, d])
    assert(h[0] == 263561599766550617289250058199814760685)
    assert(h[1] == 65303172752238645975888084098459749904)
    return
}
```

あとは最初の例と同じです。
コンパイル→proving.keyとverification.keyの作成→witnessの作成→proofの作成→Solidityファイルの出力を行います。

```bash
zokrates compile -i hashcheck.zok
zokrates setup
zokrates compute-witness -a 0 0 0 5
zokrates generate-proof
zokrates export-verifier
```

最後、認証に成功することを確認します

```bash
zokrates verify
```

# ZoKratesを利用した実装例
Githubで検索して出てきたものをいくつか貼っておきます。

ERC20トークンの匿名送金

https://github.com/zhenpanda/ethsf_confer

入力した数字の偶奇のみを明らかにする投票アプリ

https://github.com/tomoima525/zkp-vote

労働の開始時間、終了時間を明らかにせず合計時間を証明できるコントラクト

https://github.com/robmuth/proof-of-work