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 keypkと公開入力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の計算量やwitnessx, yのサイズに依存しません(これがzk-SNARKsの簡潔性に当たります)。
proof pfは実行ごとに違う値になります。複数回認証をする場合は、使いまわしによる偽装を防ぐために、一度使用されたpfを記録しておき、二度と同じものを受け付けてはいけません。

参考文献

ZoKratesとは

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

注意

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

とのことです。

Install

Linux, MacOS and FreeBSDへのインストール

curl -LSfs get.zokrat.es | sh

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

docker run -ti zokrates/zokrates /bin/bash

使ってみる

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

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
においても同様に指定する必要があります。

proofの作成(Aliceが行う)

zokrates compute-witness -a 4 16
zokrates generate-proof

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

{
  "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でデプロイしてみます。

yarn add hardhat
yarn hardhat

でhardhatのTypescript templateを作成後、verifier.solをcontractsディレクトリに配置し、scripts/deploy.tsを次のように編集します。

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アプリに組み込むなどの実装が必要になります。

ユースケース: パスワード認証

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ファイルを作成します。

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ファイルを作成します。

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ファイルの出力を行います。

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

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

zokrates verify

ZoKratesを利用した実装例

Githubで検索して出てきたものをいくつか貼っておきます。

ERC20トークンの匿名送金

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

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