zkRollupの回路内で計算してること

はじめに

本記事は Ethereum Advent Calendar 2021 の19日目の記事で、zkRollupの具体的な処理について解説していきたいと思います。

実際に稼働してるロールアップのコードではなく、わかりやすいチュートリアル向けのミニマムな実装があるのでそれのコードの解説をしていければと思います。

ゼロ知識証明(Zero Knowledge Proof)

ゼロ知識証明とは、秘密を知っていることを秘密を教えることなく、第三者に秘密を知っていると証明できる仕組みのことです。

ここではあまり深入りしませんが、zkRollupを作る上で大切な特徴があります。それは、大量の計算を正しく行ったことを証拠を見るだけで検証できるということです。

例えば、Bob(検証者)はAlice(証明者)の担任の先生だとします。

大量の計算(宿題)を正しく行ったことと証明したいAliceがProof(証拠)を生成します。この行為のことを証明(Prove)と言います。

Bobは40人もクラスに生徒がいるので、宿題の丸つけやチェックが面倒です。どうにかしてサボれないでしょうか？

こんな時にZKPが使えます。BobはAliceからProofを受け取り、検証(Verify)するだけで大量の宿題をAliceがきちんとやっていることがわかります。これを40回するだけで大丈夫です。

証明(Prove)にはかなり時間がかかりますが検証(Verify)は一瞬でできます。無理やり例えるのであれば、提出されたノートの表紙を見るだけで宿題をやったかどうかわかるぐらいの楽さです！

---

話はそれますが、ZKPのもう1つの大きな機能としてプライバシーの保護があります。

ZKPの計算をするときにprivateな入力にするかpublicな入力して計算するかを回路の設計者は選べます。

証拠(Proof)からprivateな入力が何だったかはわからないので、秘密を入力して計算してもその秘密がバレることはないという感じです。

例えばこれを使えば年齢確認の時に相手の年齢を聞かずとも20歳以上であるかの検証ができたり(ただし、相手が嘘をつかないという前提です)、自分の資産を明かさずとも自分が資産を持っていることを証明して誰かを明かさずに送金できたりします。

ですが、既存のzkRollupではこちらの特徴を使っているものは少ないです。Aztec ぐらいでしょうか？

zkRollup以外ではZcash等に使われています。

Circom(さーこむ)

zkSNARKsという種類のZKPの回路を書くためのプログラミング言語とツールキットの総称です。

https://github.com/iden3/circom

EdDSAの署名検証

お金を扱うようなATMの裏側にあるようなプログラムを想像してみましょう。ユーザーからのデータを入力をそのまま使うといろいろ危険です。

• 本当にATMの前にいる人は本人なのか

ATMでは本人しか持ってないであろう通帳やキャッシュカードに加えて、本人しか知らないであろう暗証番号を検証することで本人であることを確認しています。

ブロックチェーンの世界ではそんな脆弱な仕組みではなく、デジタル署名を使って本人であるかの確認を行っています。

デジタル署名にも色々な種類がありますが、zkSNARKs系のRollupではEdDSA(エドワーズ曲線デジタル署名アルゴリズム)というものが使われます。なぜBitcoinやEthereumで使われている電子署名アルゴリズムである、ECDSA(楕円曲線デジタル署名アルゴリズム)が使われていないのでしょうか？その答えはシンプルで、EdDSAの方が遥かに効率がいいからだそうです。

署名検証により本人確認をし、資産を持っている本人からの意思で資産の移動を検証できます。

include "../circomlib/circuits/eddsamimc.circom";

template VerifyEdDSAMiMC() {
    signal input from_x;
    signal input from_y;
    signal input R8x;
    signal input R8y;
    signal input S;
    signal input M;

    component verifier = EdDSAMiMCVerifier();
    verifier.enabled <== 1;
    verifier.Ax <== from_x;
    verifier.Ay <== from_y;
    verifier.R8x <== R8x
    verifier.R8y <== R8y
    verifier.S <== S;
    verifier.M <== M;
}

component main = VerifyEdDSAMiMC();

Circomが用意してくれてるライブラリのcircomlibを使えば簡単にできますね。

Merkle Proofの検証

Merkle TreeはBitcoinやEthereum等のブロックチェーンで使われている、効率的にデータの要約をしその要約の中にあるデータが含まれていることを小さいデータで証明できるツリー構造です。

資産のツリーをハッシュ関数で作ることで、たった32byteのMerkle Rootとleafを証明するためのsiblingを集めれば、効率的に資産を証明できます。

例えばこのようなツリーがあったとします。
BobのアドレスやBobの資産を証明しようと思った時に、赤の丸印の部分のhashさえあればMerkle Rootを構成できます。

その構成されたMerkle RootとL1に刻まれてるMerkle Rootが同じであればL2で正しく資産を持っているということが証明できます。
Merkle Treeがなかったらどうやって資産の証明ができるでしょうか。全部のデータをブロックチェーンに載せなければ検証することはできないでしょう。これはストレージを圧迫するので非効率的です。そうではなく、圧縮してMerkel RootのみをL1のコントラクトに刻むことでガス代を抑えることができます。

1. get_merkle_root.circom はリーフとマークルパスを引数にとり、計算されたMerkle Rootを返します。

include "../circomlib/circuits/mimc.circom";

template GetMerkleRoot(k){
    // kはツリーの深さです

    signal input leaf;
    signal input paths2_root[k];
    signal input paths2_root_pos[k];

    signal output out;

    // Merkle Proofの最初の２つの入力のハッシュ
    component merkle_root[k];
    merkle_root[0] = MultiMiMC7(2,91);
    
    // もし `paths2_root_pos` が `0`なら、　`merkle_root[0].in[0]` が leafになり、
    // `merkle_root[0].in[1]` が `paths2_root[0]` になります。
    // もし `paths2_root_pos` が `1` なら、`merkle_root[0].in[0]` が `paths2_root[0]` になり
    // `merkle_root[0].in[1]` が `leaf` になります。
    merkle_root[0].in[0] <== paths2_root[0] - paths2_root_pos[0]* (paths2_root[0] - leaf);
    merkle_root[0].in[1] <== leaf - paths2_root_pos[0]* (leaf - paths2_root[0]);

    // 他の全ての入力値をhashしてMerkle proof
    for (var v = 1; v < k; v++){
        merkle_root[v] = MultiMiMC7(2,91);
        merkle_root[v].in[0] <== paths2_root[v] - paths2_root_pos[v]* (paths2_root[v] - merkle_root[v-1].out);
        merkle_root[v].in[1] <== merkle_root[v-1].out - paths2_root_pos[v]* (merkle_root[v-1].out - paths2_root[v]);
    }

    // output computed Merkle root
    out <== merkle_root[k-1].out;

}

component main = GetMerkleRoot(2)

2. leaf_existence.circom は、予想されるMerkle Rootと計算されたMerkle Rootを比較する回路です。

include "./sample_get_merkle_root.circom";
include "../circomlib/circuits/mimc.circom";

// checks for existence of leaf in tree of depth k

template LeafExistence(k){
    // k はTreeの深さ

    signal input leaf;
    signal input root;
    signal input paths2_root_pos[k];
    signal input paths2_root[k];

    component computed_root = GetMerkleRoot(k);
    computed_root.leaf <== leaf;

    for (var w = 0; w < k; w++){
        computed_root.paths2_root[w] <== paths2_root[w];
        computed_root.paths2_root_pos[w] <== paths2_root_pos[w];
    }

    // inputのRootと計算して算出されたMerkle Rootが同じか確かめる
    root === computed_root.out;

}

component main = LeafExistence(2);

zkRollupを掘り下げる

L2内のすべての状態は、ルートがチェーン上に保持されているツリーに格納され、チェーン外の有効な状態遷移を証明するSNARK Proofを送信することによってのみ状態遷移ができます。この記事では、ERC20スタイルのtransferを行っているため、ユーザーのバランスをハッシュツリーの葉に保存できます。もっと詳細をみてみましょう。

アカウントリーフのフォーマット

各アカウントは、アカウントツリーの1つのリーフで表されます。これは次の要素を次の順序でハッシュすることによって計算されます。
leaf = Hash(pubkey_x, pubkey_y, balance, nonce, token_type)

class Account = {
    pubkey_x: public key X // (253 bits)
    pubkey_y: public key Y //(253 bits)
    balance: balance // (128 bits)
    nonce: nonce // (32 bits)
    token_type: token type // (32 bits)
}

この記事では最小限の実装にしたいので次のようにします。(本番で使ってはいけません。)

class Account = {
    pubkey: eddsa_pubkey,
    balance: integer
}

Transaction

SNARKごとに、TransactionsのMerkle Treeを構築し、このリーフはSNARKによって処理されたトランザクションです。

class Transaction = {
  from: eddsa_pubKey,
  fromIndex: integer, // from index is the index of sender's leaf in the accounts tree
  to: eddsa_pubKey,
  amount: integer,
  nonce: integer,
  token_type: integer
}

例のごとくミニマムバーションでこんな感じにしましょう。

class Transaction = {
    from: eddsa_pubkey,
    to: eddsa_pubkey,
    amount: integer
}

rollupにdepositする

各depositはスマートコントラクトにリーフを作成します。スマートコントラクトはnonce, token_type, balanceが正しいことを確認します。誰でもこれらのdepositをdeposit_rootを使用してdeposit_treeに集約できます。

オペレーターは、次の方法で現在の残高のツリーに追加できます。

1. account_treeでdeposit_treeと同じ深さのempty_nodeが空であることを証明します。
2. このempty_nodeをdeposit_rootに置き換えます
3. 同じMerkle証明を使用して、新しいaccount_rootを計算します。

rollupからwithdrawする

withdrawは、通常のtransferの状態遷移のようなものです。引き出しの場合、ユーザーはzero addressにトークンを送信するだけで、チェーンのアドレスを書き込むようなものになります。トークンはこのアドレスでのみ受信できます。

• 引き出しはzero addressにトランザクションを送信します
• Withdraw() 関数は、次のことを行うスマートコントラクトで呼び出すことができます
  • 署名を確認します
  • withdraw txの存在を確認します
  • プールから指定されたアドレスに送金する

１つのtxを処理するだけの回路

zkRollupでは複数のtxをまとめて処理することが一般的ですが、今回はミニマム実装のために１つのtxから状態遷移する回路を書いてみましょう。

include "./leaf_existence.circom";
include "./verify_eddsamimc.circom";
include "./get_merkle_root.circom";
include "../circomlib/circuits/mimc.circom";

template ProcessTx(k){
    // kはアカウントツリーの深さ

    // アカウントツリーの情報
    signal input accounts_root;
    signal private input intermediate_root;
    signal private input accounts_pubkeys[2**k, 2];
    signal private input accounts_balances[2**k];

    // トランザクションの情報
    signal private input sender_pubkey[2];
    signal private input sender_balance;
    signal private input receiver_pubkey[2];
    signal private input receiver_balance;
    signal private input amount;
    signal private input signature_R8x;
    signal private input signature_R8y;
    signal private input signature_S;
    signal private input sender_proof[k];
    signal private input sender_proof_pos[k];
    signal private input receiver_proof[k];
    signal private input receiver_proof_pos[k];

    // アウトプット
    signal output new_accounts_root;

    // accounts_rootの中にsenderのアカウントがあるか検証する
    component senderExistence = LeafExistence(k, 3);
    senderExistence.preimage[0] <== sender_pubkey[0];
    senderExistence.preimage[1] <== sender_pubkey[1];
    senderExistence.preimage[2] <== sender_balance;
    senderExistence.root <== accounts_root;
    for (var i = 0; i < k; i++){
        senderExistence.paths2_root_pos[i] <== sender_proof_pos[i];
        senderExistence.paths2_root[i] <== sender_proof[i];
    }

    // txがsenderによって署名されてるか確認する
    component signatureCheck = VerifyEdDSAMiMC(5);
    signatureCheck.from_x <== sender_pubkey[0];
    signatureCheck.from_y <== sender_pubkey[1];
    signatureCheck.R8x <== signature_R8x;
    signatureCheck.R8y <== signature_R8y;
    signatureCheck.S <== signature_S;
    signatureCheck.preimage[0] <== sender_pubkey[0];
    signatureCheck.preimage[1] <== sender_pubkey[1];
    signatureCheck.preimage[2] <== receiver_pubkey[0];
    signatureCheck.preimage[3] <== receiver_pubkey[1];
    signatureCheck.preimage[4] <== amount;

    // senderのアカウントの残高を記入し、ハッシュしてleafを作る
    component newSenderLeaf = MultiMiMC7(3,91){
        newSenderLeaf.in[0] <== sender_pubkey[0];
        newSenderLeaf.in[1] <== sender_pubkey[1];
        newSenderLeaf.in[2] <== sender_balance - amount;
    }

    // accounts_rootをアップデートする
    component computed_intermediate_root = GetMerkleRoot(k);
    computed_intermediate_root.leaf <== newSenderLeaf.out;
    for (var i = 0; i < k; i++){
        computed_intermediate_root.paths2_root_pos[i] <== sender_proof_pos[i];
        computed_intermediate_root.paths2_root[i] <== sender_proof[i];
    }

    // computed_intermediate_root.out === intermediate_rootになることを確認する
    computed_intermediate_root.out === intermediate_root;

    // intermediate_rootの中に受信者のアカウントの存在があるか検証する
    component receiverExistence = LeafExistence(k, 3);
    receiverExistence.preimage[0] <== receiver_pubkey[0];
    receiverExistence.preimage[1] <== receiver_pubkey[1];
    receiverExistence.preimage[2] <== receiver_balance;
    receiverExistence.root <== intermediate_root;
    for (var i = 0; i < k; i++){
        receiverExistence.paths2_root_pos[i] <== receiver_proof_pos[i];
        receiverExistence.paths2_root[i] <== receiver_proof[i];
    }

    // receiverアカウントの残高を増やし、ハッシュしてleafを作る
    component newReceiverLeaf = MultiMiMC7(3,91){
        newReceiverLeaf.in[0] <== receiver_pubkey[0];
        newReceiverLeaf.in[1] <== receiver_pubkey[1];
        newReceiverLeaf.in[2] <== receiver_balance + amount;
    }

    // accounts_rootをアップデートする
    component computed_final_root = GetMerkleRoot(k);
    computed_final_root.leaf <== newReceiverLeaf.out;
    for (var i = 0; i < k; i++){
        computed_final_root.paths2_root_pos[i] <== receiver_proof_pos[i];
        computed_final_root.paths2_root[i] <== receiver_proof[i];
    }

    // 最後のaccounts_rootを出力とする
    new_accounts_root <== computed_final_root.out;
}

component main = ProcessTx(1);

zkRollupの流れ

ここまでZKPの回路内でどういう処理をしていくのか学びましたが、zkRollupの流れをざっくりと解説します。

1. ユーザーがtxに署名してオペレーターに渡す
2. オペレーターは複数のtxを受け取る
3. オペレーターは回路にtxやMerkle Treeの情報をinputとして入れ計算する(Prove)
4. 検証者(L1のスマートコントラクト)にProofを渡して、Verifyする
5. 新しいMerkle RootがL1コントラクトに刻まれる(残高が反映され、状態遷移が確定する)

まとめ

zkRollupのベース技術であるゼロ知識証明を完全にブラックボックスとして捉えてしまうと、そんなに難しいことをやっているわけではないとわかります。署名検証とMerkle TreeのInclusion Proofだけです。ごくごく普通のブロックチェーンの技術です。

ゼロ知識証明は数学や暗号をベースとした技術なので、中身を完璧に理解するには大学で学ぶような数学の知識がいるかもしれません。ちなみに筆者は理解していませんw

理解した方がいいのは間違いないですが、機能とインターフェースさえわかれば色々作れるものです。多くのプログラマがCPUの仕組みやアセンブラを理解してなくてもコードがかけるように。

この記事がよかったなと思えたらツイート、いいね、コメント等よろしくお願いします！

参考文献

Zk Rollup Tutorial