View on GitHub

雑記

技術メモなど

Sapling protocol と向き合う

Sapling protocol とは zcash で定義された, ゼロ知識証明 zk-SNARK(zero-knowledge Succinct Non-interactive ARgument of Knowledge) を使ってトークンの送受信情報を匿名化したブロックチェーンプロトコルです. 一般にブロックチェーン上のアドレス間の送受信情報は公開されていて誰でも閲覧追跡できますが, 本プロトコルを使うとそれすら秘匿することができます. 最初に zerocash1 という名前で Bitcoin 内に匿名化に対応したコインを導入するする実装がされ,2nd layer の実装手法の一つとして Ethereum や Tezos などでも応用されています. ゼロ知識証明を使った 2nd layer 実装技術は zk-rollup とか pessimistic-rollup2 とか呼ばれています.

そもそも何ができるか

Sapling を実装した tezos の sandbox 上で送受信する例をみてみます.

https://tezos.gitlab.io/active/sapling.html

# set up the sandbox
./src/bin_node/octez-sandboxed-node.sh 1 --connections 0 &
eval `./src/bin_client/octez-init-sandboxed-client.sh 1`
octez-activate-alpha

# originate the contract with its initial empty sapling storage,
# bake a block to include it.
# { } represents an empty Sapling state.
octez-client originate contract shielded-tez transferring 0 from bootstrap1 \
running src/proto_alpha/lib_protocol/test/integration/michelson/contracts/sapling_contract.tz \
--init '{ }' --burn-cap 3 &
octez-client bake for bootstrap1

# if necessary, you can get information from the octez-client manual
octez-client sapling man

# generate two shielded keys for Alice and Bob and use them for the shielded-tez contract
# the memo size has to be indicated
octez-client sapling gen key alice
octez-client sapling use key alice for contract shielded-tez --memo-size 8
octez-client sapling gen key bob
octez-client sapling use key bob for contract shielded-tez --memo-size 8

# generate an address for Alice to receive shielded tokens.
octez-client sapling gen address alice
zet1AliceXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX # Alice's address


# shield 10 tez from bootstrap1 to alice
octez-client sapling shield 10 from bootstrap1 to zet1AliceXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX using shielded-tez --burn-cap 2 &
octez-client bake for bootstrap1
octez-client sapling get balance for alice in contract shielded-tez

# generate an address for Bob to receive shielded tokens.
octez-client sapling gen address bob
zet1BobXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX # Bob's address

# forge a shielded transaction from alice to bob that is saved to a file
octez-client sapling forge transaction 10 from alice to zet1BobXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX using shielded-tez

# submit the shielded transaction from any transparent account
octez-client sapling submit sapling_transaction from bootstrap2 using shielded-tez --burn-cap 1 &
octez-client bake for bootstrap1
octez-client sapling get balance for bob in contract shielded-tez

# unshield from bob to any transparent account
octez-client sapling unshield 10 from bob to bootstrap1 using shielded-tez --burn-cap 1
ctrl+z # to put the process in background
octez-client bake for bootstrap1
fg # to put resume the transfer

src/proto_alpha/lib_protocol/test/integration/michelson/contracts/sapling_contract.tz は zk-rollup における L2(Layer-2) の状態を Layer1 で管理するためのコントラクトです. 中身は L2 上のトランザクション sapling_transaction の列を受け取り, sapling_state を更新して保存するみたいな感じのシンプルな感じです3.

上の例では,

が行われています.

このとき,

つまり, L1 と L2 間のやり取りは見えてますが, L2 で何が起きたのかは何も分からないという感じです. L2 のアカウントが少ないと L1 と L2 間のやり取りでキャッシュフローが筒抜けになってしまいますが, 大規模になれば Mixer4 と違って追跡は難しいでしょう.

zerocash

sapling の内部で何が起こっているのかを理解したかったのですが, これ自体複雑で難解です. 一次ソース なんかは Sprout と Sapling の 2 バージョン混ざって載った zcash 全体のプロトコルとかで 150p もあって膨大です.

今回は sapling を理解するより先に, 元となった zerocash の論文を読んで理解しようとしてみます.

zerocash の仕組み

zerocash は bitcoin を拡張して匿名化した送金のトランザクションを可能にした実験的な実装です. zerocash の匿名化した世界のノードは状態として, Merkle-tree と Nullifier-Set5 を持っています. Merkle-tree はその葉に coin-commitment を保持しています. coin-commitment は

\[\begin{aligned} k := COMM_r(a_{pk} \parallel \rho)\\ cm := COMM_s(v \parallel k) \end{aligned}\]

で計算される \(cm\) です. ここで,

です. コイン \(c\) はこれらの組 \((a_{pk}, v, \rho, r, s, cm)\) と考えることができます.

Nullifier-Set は,シリアルナンバー \(sn := PRF^{sn}_{a_{sk}}(\rho)\) の集合です.

(zerocash の論文より) 図中の CRH は衝突耐性のあるハッシュ関数です.

このプロトコルでは mint と pour の 2 種類のトランザクションを発行することができます.

mint をする場合は, 上で定義したコインに対し, mint トランザクション \((v, k, s, cm)\) を発行します. \(cm := COMM_s(v \parallel k)\) を計算することで \(v\) を送るトランザクションということは誰でも確認できます(つまり外の世界から v が pool へ送られていなければおかしいことが分かります). しかし \(a_{pk}\) は公開されていないためどのアドレスへ送ったかはわかりません.

pour をする場合を考えます. pour では所有している複数の既存のコイン \(c^{from}_i\) を 複数の別のアカウントへ紐つけられた コイン \(c^{to}_i\) へ変換します. もしコイン中の量の合計の差 \(v_{pub} = \sum_i v^{from}_i - \sum_i v^{to}_i\) があれば, それは zerocash の世界から bitcoin の世界への送金としてそのトランザクションを実行したアカウントへ pool から送られます. 送信者は送信先のアドレス \(a^{to}_{pk,i}\) と贈りたいトークンの量 \(v^{to}_i\) に対し, \(\rho^{to}_i, r^{to}_i, s^{to}_i\) を生成してコイン \(c^{to}_i\) を計算して生成します. そして最後に zk-SNARK を使って以下の証明 \(\pi\) を生成します.

このとき pour トランザクションは \((rt, sn^{from}_i, cm^{to}_i, v_{pub}, \pi)\) です.

公開されているのは mint と pour のトランザクションの列になります. 各々のノードはそこから coin-commitment の merkle-tree と nullifier-set を構築できます. しかしこれだとトークンを送られた本人ですらどの coin-commitment が自分のコインで, いくら保有しているのかも分かりません. 別途安全な通信路で教えるということでも良いですが, 便宜上 pour トランザクションには \((v^{to}_i, \rho^{to}_i, r^{to}_i, s^{to}_i)\) を秘密鍵で暗号化した暗号文が付随しています. これは \(a_{sk}\) とは別に用意した公開鍵でやります. 各アカウントは pour トランザクションをスキャンすることで自分宛ての送金を検出して自分の保有するコインの情報を得られます.

さらに, この付与した暗号文がすり替えられるのを防ぐため, MAC(メッセージ認証コード)をつけます. 具体的には,

  1. 鍵ペア \((pk_{sig}, sk_{sig})\) を生成
  2. \(h_{sig} = CRH(pk_{sig})\) を計算
  3. \(h_i = PRF^{pk}_{a^{from}_{sk, i}}(h_{sig})\) を計算
    • これが MAC
  4. \(sk_{sig}\) で pour トランザクションを署名し, 署名 \(\omega\) を付与する

をします. 生成するゼロ知識証明にも \(h_{sig}, h_i\) の有効性の証明を加える必要がありますが, ここでは省略します.

zerocash は bitcoin と同様の UTXO モデルになっています. しかし coin-commitment は匿名性のためにどれが既に使われたコインを表すのか判別がつきません(逆にどれが使用済みか分かってしまうと, mint トランザクションから追跡できてしまいます). そこで二重消費を防ぐためにあるのがシリアルナンバーと Nullifier-Set です. コインを消費するたびにシリアルナンバーを公開し, Nullifier-Set へ追加していますから, もし Nullifier-Set に既にあるシリアルナンバーを使用しようとすれば二重消費が検出できるというわけです.

zk-SNARKs

zk-SNARK は以下の 3 アルゴリズム(KeyGen, Prove, Verify) の組です.

\[\begin{aligned} (pk, vk) \leftarrow \text{KeyGen}(1^\lambda, C)\\ \pi \leftarrow \text{Prove}(pk, x, a)\\ b \leftarrow \text{Verify}(vk, x, \pi) \end{aligned}\]

ここで

です. KeyGen は信頼できる第三者が実行して pk を生成し, Prove を実行する者にとって都合の良い入力にならないように制限をかけるためのものです.

zk-SNARK である条件としては,

です.

このような zk-SNARK の要件を満たすアルゴリズムは複数知られているらしいので, zk-SNARKs と複数形で呼ばれています. ここでは zk-SNARK を満たす具体的なアルゴリズムには触れません.

zerocash における zk-SNARK

KeyGen は信頼できる第三者が最初に一度だけ行い, \((pk, vk)\) を生成します. 信頼できる第三者がランダムに生成しない場合, 不正な pour トランザクションを生成できたりトークン量の不変条件が崩れたりするらしいです. L2 として実装している巷のブロックチェーンではスマートコントラクトがこの役割を担い, 最初にデプロイするときに KeyGen しています.

zk-SNARK は前述の通り pour のトランザクションを検証するのに使います. \(\text{Prove}(pk, x, a)\) の具体的なアルゴリズムは使用する zk-SNARK に依存しますが, 使う主張と補助入力は

\[\begin{aligned} x = (rt, sn^{from}_i, cm^{to}_i, v_{pub})\\ a = (path_i, c^{from}_i, c^{to}_i, a_{sk}) \end{aligned}\]

ただし, \(path_i\) は Merkle-tree における \(rt\) から \(cm^{from}_i\) までのパスです.

ここまで来ると大体想像がつくかもしれませんが, zk-SNARK の算術回路 \(C\) には \(x\) と \(a\) が満たして欲しい性質を埋め込みます. つまり,

がエンコードされています. \(COMM\) と \(PRF\) は hash 関数が使われていましたね. つまり最後のトークンの不変条件以外は hash 関数の一致をひたすら検証しているだけなので, 回路のほとんどは hash 関数になります.

zerocash と sapling の違い

Sapling protocol は zcash 上で実装された 2 つ目6のプロトコルです.

Sapling には鍵が5種類くらい定義されています. これは用途ごとに細かく権限を制御するために分けられてます.

(sapling protocol specification 3.1 p12 より)

他にも実装上の違いは色々ありそうですが, 一番の違いは多分

かなーと思います. こうして分けることで zk-SNARK の証明が小さくできるという利点があるらしいです. また, 対応する Spend と Output の間にはトークン量の不変条件(つまり, 送った 量と受け取った量が等しい)が成り立つ必要がありますが, それは別途 Pedersen Commitment というのを使って示しているらしいです.

Reference

Footnote

  1. 似たようなやつらがいます (出典) zerocoin : zerocash の先行研究, 送信元だけ匿名化, zerocash : zerocoin と比べて, 送信先, 送信するトークンの量を匿名化, zcash : bitcoin 上ではなく独自コインとして zerocash を実装 ↩

  2. pessimistic があるということは optimistic もあります. pessimistic の方はブロックチェーン上で検証済みのコミットしか受理されませんが, optimistic の方は誰かに反証されるまで検証しません. ↩

  3. tezos の sapling の型は謎の integer を受け取ります. これは sapling のトランザクションに付与できる受信者だけが見られる文字列メモの最大長らしいです. メモ自体は sapling protocol で定義されています. ↩

  4. 複数のアカウントから送られてきた残高を鍵付きで保管して, 複数のアカウントへ送る Mixer というコントラクトが一般に知られていて, マネロンの用途で使われるらしいですが, 送信者と受信者のアドレスもその総金額も公開されているのでどれだけ意味があるのか不明です. その点 sapling は追跡不能なので逆にどこかのプロトコルでは禁止されたとか ↩

  5. 論文中では \(\text{SNList}\) と呼ばれています ↩

  6. 1 つ目は Sprout と呼ばれています ↩