Zenn
📝

【Circom/zkSNARKs】難しい数学は一旦おいて、実装して開発の流れを理解する

2024/05/03に公開
ブロックチェーン
cryptography
Ethereum
zk
circom
tech

はじめに

結論ZKPを理解するには数学は必須です。とは言え、アルゴリズムや仕組みの部分をもっと抽象的に理解したいと思っていたので、その方にはちょうど良い記事になるかと思います。
（暗号のからむセンシティブな内容だと思うので間違いがあれば指摘もらえると嬉しいです！）

snarkjsライブラリを用いてzkSNARKsを構築しながら、何をしているのかを追っていきます。今回解説するコマンドや実行手順などは全てこちらの READMEに記載があります。
https://github.com/iden3/snarkjs

zkSNARKsの概要

ZKP（ゼロ知識証明）とは何か、zkSNARKs（非対話なゼロ知識証明）とは何かなどは、他記事を参照ください。
https://crypto-times.jp/zero-knowledge-proof-and-zk-snarks/

ここではかなり簡単に説明します。
ゼロ知識証明とは、「ある命題が真であることを、命題が真であるという情報以外を伝えずに証明できること」 です。ゼロ知識証明には対話型と非対話型があり、zkSNARKsは非対話なゼロ知識証明を構築します。いちいち対話的にやり取りが生まれないので、非対話の方が便利ですよね。それを実現する一つの方法がzkSNARKsです。

zkSNARKsを構成するアルゴリズム

zkSNARKsは基本的に3つのアルゴリズムから構成されます。下記の理解は現状ではなんとなくで大丈夫です。後に説明していくzkSNARKs 開発の流れを見ていく中でイメージがついていくと思います。

Key Generator(G)：鍵を生成するアルゴリズム

ある秘密の値RとプログラムCから証明鍵(pk)と検証鍵(vk)を生成する。セットアップアルゴリズムと言ったりするが、証明や検証を行うための準備のようなもの。
(pk, vk) = G(R,C)

Prover(P)：証明者が証明をするアルゴリズム

証明者が、上記のセットアップフェーズで生成された証明鍵(pk)と証明する情報(X)とプログラムCへのインプット(h)から証明(proof)を生成する。
prf = P(pk, X, h)

  • prf : proof

Verifier(V)：検証者が証明を正当かどうか検証するアルゴリズム

検証鍵(vk)とプログラムCへのインプット(h)と証明(prf)から「正当か不正か」を返す。
V(vk, h, prf) = True or False

これらG、P、Vのアルゴリズムを使った実際の流れは下記図のようになります。

これから開発の流れを解説していきますが、都度こちらに戻り、どのアルゴリズムに該当している部分が行われているのかを確認します。

zkSNARKs(Groth16) 開発の流れ

開発のステップは下記になります。

  1. 環境構築
  2. circomでcircuit（回路）を定義
  3. circuitのコンパイル（R1CSに変換）
  4. 鍵の生成（Trusted Setup）
  5. Proofの生成
  6. Proofの検証
  7. スマコンで検証

基本snarkjsのREADMEの流れを追っていきますが、こちらの記事も非常に参考になります。
https://zenn.dev/0xywzx/articles/bdb6c991f3fc8b#開発の流れ

実際のリポジトリはこちらです。
https://github.com/Mameta29/circom_beginner/tree/main/implement_zk

1. 環境構築

Circomとsnarkjsをインストールする必要があります。

npm install -g snarkjs@latest

2. circomでcircuit（回路）を定義

circom言語でCircuitを書いていきます。ここではsnarkjsのREADMEの例と同じものを使用します。

circuit.circom
pragma circom 2.1.5;

template Multiplier(n) {
    signal input a;
    signal input b;
    signal output c;

    signal int[n];

    int[0] <== a*a + b;
    for (var i=1; i<n; i++) {
    int[i] <== int[i-1]*int[i-1] + b;
    }

    c <== int[n-1];
}

component main = Multiplier(1000);

Circom言語についてはまた別記事を書いていきたいと思いますが、ここでは簡単に説明します。

pragma circom 2.1.5;

使用する circom のバージョンを宣言しています。ここでは 2.1.5 バージョンを使用することを指定しています。

template Multiplier(n) {
    // 以下の部分
}

この部分は、Multiplier という名前の回路テンプレートを定義しています。n はテンプレートのパラメータで、後で具体的な値を割り振っていきます。

signal input a;
signal input b;
signal output c;

これらは、回路の入力と出力を表すシグナルを定義しています。a と b は入力、c は出力となります。
シグナルをパッと見ると変数のように見えますが、シグナルはCircuitの制約に関連する値を表しているという部分で大きな違いがあります。

signal int[n];

長さ n の整数型シグナルの配列 int を定義しています。

int[0] <== a*a + b;

配列の最初の要素 int[0] に a*a + b の値を割り当てています。<== は制約を表す演算子です。

for (var i=1; i<n; i++) {
    int[i] <== int[i-1]*int[i-1] + b;
}

このループでは、int 配列の残りの要素を計算しています。各要素 int[i] は、前の要素 int[i-1] の二乗に b を足した値になります。

c <== int[n-1];

最後に、出力 c に int 配列の最後の要素 int[n-1] の値を割り当てています。

component main = Multiplier(1000);

このコードの最後の行で、先ほど定義した Multiplier テンプレートを呼び出し、パラメータ n に 1000 を渡して具体的な回路を生成しています。

全体として、このコードは aa + b, (aa + b)^2 + b, ((aa + b)^2 + b)^2 + b ... と計算を繰り返し、最終的に (aa + b)^1000 の値を出力するような回路を定義しています。回路の計算量は n の値に応じて増減します。

何をゼロ知識証明している？

結構無理やりの例ではあるかもしれませんが、イメージをつきやすくするために提示します。
自分が知っている秘密の情報(a, b)を直接明かすことなく、その情報を使って特定の計算を実行できることを証明しています。

登場人物

Alice（証明者）：暗号通貨の取引所で勤務。
Bob（検証者）：取引所のセキュリティ監査官。

Alice と Bobの目的

Aliceの目的
Aliceは、顧客から預かった2つの数a, bを使って(a*a + b)^1000を計算できることを証明したいと考えています。ただし、顧客のプライバシーを守るために、aとbの実際の値をBobに知られたくない。

Bobの目的
Bobは取引所のセキュリティ監査官として、以下のことを確認したい。

  • Aliceが顧客から預かった数a, bを実際に知っていること。
  • Aliceが(a*a + b)^1000を正しく計算できること。
  • Aliceが顧客の情報を適切に扱っていること。

3. circuitのコンパイル（R1CSに変換）

下記コマンドでCircuitのコンパイルができます。

circom circuit.circom --r1cs --wasm --sym

このcircomコマンドは1つの入力（コンパイルする回路、ここではcircuit.circom）と3つのオプションを取っています。

  • r1cs: circuit.r1cs（回路のr1cs制約をバイナリ形式で）を生成します。
  • wasm: circuit.wasm（witnessを生成するためのwasmコード、詳細は後述）を生成します。
  • sym: circuit.sym シグナルや変数名一覧が記載しています。

成功すると下記のような出力があります。

そしてフォルダやファイルがいろいろ生成されていることも確認できます。
（私はimplement_zkフォルダを作成しその配下で作業しています。）

R1CSファイルを読み込むには、以下のようにsnarkjsを使うと表示されます。

snarkjs r1cs print circuit.r1cs

4. 鍵の生成（Trusted Setup）

計算の有効性を検証するためのパラメータを生成します。詳細はここでは省きますが、zk-SNARKsを使用するために必要な公開パラメータ（証明鍵や検証鍵など）を生成するプロセスのことをTrusted Setupといいます。Ceremonyといって複数人が参加可能で、ロジック的には信頼できる人が1人でもいれば、そのTrusted Setupは信頼できるものとなります。

zkSNARKsのgroth16の場合、Trusted Setupは２つのフェーズに別れます。

  • Phase 1
    この段階では、zkSNARKsのパラメータを生成するために使用される多項式が構築されます。ここでPower of Tauというものを使用しますが、これは多項式を構築する際に使用される秘密値のセットのことです。

  • Phase 2
    この段階では、Phase 1で生成された多項式から実際のzkSNARKsパラメータが導出されます。パラメータには、proving key（証明鍵）とverification key（検証鍵）が含まれます。

これは鍵生成アルゴリズムに該当


ここでは ある秘密の値R というのがPower of Tauのことで
プログラムC というのは r1cs (circuit.r1cs)を使用することになります。

Phase 1

  1. 新しいPowers of Tauセレモニーを開始
snarkjs powersoftau new bn128 14 pot14_0000.ptau -v


2. セレモニーに貢献する。これを複数回行うことができる

// 1回目
snarkjs powersoftau contribute pot14_0000.ptau pot14_0001.ptau --name="First contribution" -v
```![](https://storage.googleapis.com/zenn-user-upload/475f9692f1a2-20240503.png)

// 2回目
snarkjs powersoftau contribute pot14_0001.ptau pot14_0002.ptau --name="Second contribution" -v -e="some random text"
// 3回目
snarkjs powersoftau contribute pot14_0002.ptau pot14_0003.ptau --name="Third contribution" -v -e="some random text"

2回目
![](https://storage.googleapis.com/zenn-user-upload/f519df2843d0-20240503.png)
3回目
![](https://storage.googleapis.com/zenn-user-upload/41f405a25c46-20240503.png)

3. 現在までの進捗を検証
```sh
snarkjs powersoftau verify pot14_0003.ptau


それぞれのPowers Of tauでOKの出力が出ているのでいい感じです。

  1. ランダムビーコンを適用してPhase 1を完了させます。
snarkjs powersoftau beacon pot14_0003.ptau pot14_beacon.ptau 0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f 10 -n="Final Beacon"

  1. Phase 2の準備を行います。
snarkjs powersoftau prepare phase2 pot14_beacon.ptau pot14_final.ptau -v
  1. 最終的なptauファイルを検証します。
snarkjs powersoftau verify pot14_final.ptau

Phase 1 から　Phase 2へ

Phase 1の snarkjs powersoftau prepare phase2 pot14_beacon.ptau pot14_final.ptau -v このコマンドで、pot14_beacon.ptauから多項式の評価値が計算され、その結果がpot14_final.ptauに出力されます。pot14_final.ptauには、多項式の評価値に加えて、これまでのすべての貢献とランダムビーコンが含まれています。
そしてPhase 2では、このpot14_final.ptauから実際のzkSNARKsパラメータ(zkey)が導出されます。
つまり、Phase 1で生成された多項式そのものはファイルには出力されませんが、その評価値がpot14_final.ptauに暗号化された形で含まれており、Phase 2でその値から実際のパラメータが計算されるという流れになります。
多項式自体は直接見ることはできませんが、pot14_final.ptauにはPhase 1の出力が全て含まれており、Phase 2でそれを使ってzkSNARKsパラメータが生成されます。

Phase 2

Phase 2では、Phase 1で生成された多項式から実際のzkSNARKsパラメータが導出されます。すでにCircuitを作成しコンパイル済み(R1CS作成済み)なので下記のステップを行なっていきます。

  1. r1csをJSONにエクスポートします。
snarkjs r1cs export json circuit.r1cs circuit.r1cs.json
  1. セットアップを行います(Groth16の場合)。
    ここで秘密の値R(ptau)とプログラムC(r1cs)を使用しています。
snarkjs groth16 setup circuit.r1cs pot14_final.ptau circuit_0000.zkey
  1. Phase 2のセレモニーに貢献します。
    phase2もphase1と同様に、秘密情報のリレーを行います。
// 1回目
snarkjs zkey contribute circuit_0000.zkey circuit_0001.zkey --name="1st Contributor Name" -v

// 2回目
snarkjs zkey contribute circuit_0001.zkey circuit_0002.zkey --name="Second contribution Name" -v -e="Another random entropy"

// 3回目
snarkjs zkey contribute circuit_0002.zkey circuit_0003.zkey --name="Third contribution Name" -v -e="Another random entropy"
  1. 現在までの進捗を検証します。
snarkjs zkey verify circuit.r1cs pot14_final.ptau circuit_0003.zkey
  1. ランダムビーコンを適用してPhase 2を完了させます。
    ここで、最終的な circuit_final.zkey が作成されています。この zkey ファイルには、証明キーと検証キーの両方が含まれています。
    zkSNARKs のproof作成時に、このファイルの証明キーが必要になります。
snarkjs zkey beacon circuit_0003.zkey circuit_final.zkey 0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f 10 -n="Final Beacon phase2"
  1. 検証キーをJSONにエクスポートします。
    circuit_final.zkey から検証キーのみが verification_key.json として抽出されています。zkSNARKsのプルーフ検証時に、このファイルを使って証明の正当性をチェックします。
snarkjs zkey export verificationkey circuit_final.zkey verification_key.json

Trusted Setup後の最終的なディレクトリは下記のようになっています。

5. Proofの生成

実際にproof（証明）を作っていきます。

これは証明者が証明するアルゴリズムに該当


ここでいう証明する情報(X) と プログラムCへのインプット(h) は後述する witnessにあたると思われます。

  1. まず、witnessを生成します。
    circomがcircuit_jsディレクトリに作成したgenerate_witness.jsのプログラムを使って、入力のwitnessを作成します
// まずはinputを作成します。
// 今回はaを3, bを11として作成
cat <<EOT > input.json
{"a": 3, "b": 11}
EOT

// circuit_jsに移動
cd circuit_js

// witness生成
circuit_js$ node generate_witness.js circuit.wasm ../input.json ../witness.wtns

// ディレクトリの移動
cd ..
  1. proofを生成します。
    下記のコマンドでproofを生成します。proof.jsonとpublic.jsonの2つのファイルが出力されます。proof.jsonには実際のproofが、public.jsonには公開入力と出力の値が含まれています。
snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json

public.jsonには今回はpublic inputはないので出力の値 c だけがあります。

public.json
[
 "7713112592372404476342535432037683616424591277138491596200192981572885523208"
]

proof.jsonは生成された実際のproofデータを含んでいます。

proof.json
{
 "pi_a": [
  "6937781900196863717125177422348539222393493331463830968766273020484843843200",
  "21770877572961232974502807492396291556062257886406660961005814936795241135797",
  "1"
 ],
 "pi_b": [
  [
   "4041159000935360120359431221749322838698147605183287021400134220643052613074",
   "2490201272693825280477425425988551035193080757157643920045518477339424536667"
  ],
  [
   "13472989349342066863938436382617905864796473744677698772159471136148074328802",
   "20411811362346586282449654012449916600088777368936389527319187609523096562975"
  ],
  [
   "1",
   "0"
  ]
 ],
 "pi_c": [
  "5540864391242365909521971979075410249363882005593534934986371704084427235614",
  "12877349067841545031743510578319050359649234239504742364591333461066981906042",
  "1"
 ],
 "protocol": "groth16",
 "curve": "bn128"
}

6. Proofの検証

作成したproodを検証していきます。

これは検証者が証明を正当かどうか検証するアルゴリズムに該当


ここでいうプログラムCへのインプット(h)はpublic.jsonで、
証明(prf)はそのままproof.jsonに該当します。

snarkjs groth16 verify verification_key.json public.json proof.json

このコマンドを使って、先ほど出力したverification_key.jsonを使ってproofを検証します。
問題がなければ、コンソールにOKと出力されるはずです。これはプルーフが有効であることを示しています。

7. スマコンで検証

6. Proofの検証 ではコマンドで検証を行いましたが、Solidityスマートコントラクトにエクスポートすることでブロックチェーン上で検証することができます。
下記コマンドでverifier.solが生成されます。

snarkjs zkey export solidityverifier circuit_final.zkey verifier.sol

verifire.solで検証するためのproofを出力します。

mameta implement_zk %snarkjs zkey export soliditycalldata public.json proof.json

このアウトプット値は、verifier.solのverifyProof関数の第1(_pA), 2(_pB), 3(_pC)引数にはproofの値が、そして最後の_pubSignals引数にはpublic.jsonの値が入ると思われます。
_pA, _pB, _pCの値はproof.jsonのpi_a, pi_b, pi_cに該当するものです。

これでRemixなどを使って、verifire.solをデプロイしオンチェーンに公開することで、先ほどの出力されたproofを verifyProofに入力するとブロックチェーン上で検証できることが確認できます。

trueが返ってきているのでうまく検証することができました！

まとめ

以上でsnarkjsを使った開発の流れを見ながら、zkSNARKsでどのようなことが行われているのかを確認してきました！
実際にはR1CSをQAPに変換することでセットアップしたり、circomを書くときにはR1CSの制約条件を意識しながらプログラムしていく必要があるといったように数学的に配慮しなければならないことは多いです。そのことについては自分でも勉強して引き続き記事にできたらと思っていますが、今回は開発の流れが掴めていただけたら幸いです！

Discussion