トークン転送のプライバシーとスケーラビリティを改善するzkCoins

はじめに

このブログ投稿では、zkCoins¹の紹介をします。zkCoinsは、ブロックチェーン上で効率的にトークン(カラードコイン)を転送するためのプロトコルです。似たようなプロトコルの括りでいうと、RGB²があります。

構成要素

使い捨てシール(single-use seal)

あるデータmに対して一度だけ貼ることができ、かつ特定のユーザーpが貼ったという証拠wを検証できるようなシール（一意なラベルとして機能する文字列）lを暗号学的に表現したもの³。具体的には、以下のような3つの構成方法がある。

中央サーバーと電子署名を使う方法

サーバーの公開鍵をpとする。サーバーは(m, l)に対して署名を行い、その署名値をwとする。サーバーは同じラベルlに対して、異なる2つのデータには署名しないことが期待され、信頼されているものとする。

ビットコインのUTXOを使う方法

ビットコインのUTXO（txid:index) をシールとする。ビットコインのUTXOの宛先アドレスをpとする。pからUTXOを消費してトランザクションを作ると、そのトランザクションの0番目のインデクスに入っているOP_RETURNの文字列がデータmになる。また、トランザクション自体がwになる。

非包含証明を使う方法

zkCoinsではこれを使う。厳密には使い捨てシールとは言えないかもしれないが、「検証者はすでに使われたシールを拒絶することができる」という意味で、検証者にとっては使い捨てシールとして機能する。非包含証明については後述。

STARK

任意の計算の実行履歴を非可逆圧縮する仕組み。過去の記事⁴を参照してください。

包含証明(inclusion proof)

あるリストSを表現するダイジェストdと要素eが与えられた時、Sの中にeが含まれていることをd,eを使って証明するとき、これを包含証明といいます。具体的には、数値の集合Sと、SをマークルツリーTで表現したマークルルートdと、要素eが与えられた時、T上でeからマークルルートdに至るパス（経路）があることを示すような証明が、包含証明の例として挙げられます。

非包含証明(non-inclusion proof)

包含証明とは逆に、与えられたリストSを表現するダイジェストdと要素eが与えられた時、Sの中にeが含まれていないことをd,eを使って証明するとき、これを非包含証明といいます。
もしSが辞書順であれば、辞書順に並べたマークルツリーからeの前後にあたる要素e1,e2をSから見つけてきて、(1)e1,e2がSに含まれること(2)e1,e2が隣接した要素であること を示せれば、e1とe2の間にはeが存在しないことが示せます。

Sが辞書順でない場合、非包含証明はSparse Merkle Tree⁵などを使って実現できます。

zkCoinsの概要

zkCoinsは以下の設計原則に基づいて設計されています。

• オフチェーンでコミュニケーションできる情報はブロックチェーンに書き込まない
• クライアント側で検証できることは、グローバルレイヤー（ビットコインブロックチェーン上）では検証しない

例えばOmniでは、全てのOmniトランザクションはビットコイントランザクションでもあるため、ビットコインブロックチェーン上で全てのトークン遷移の履歴検証が行われていることになりますが、zkCoinsではそのようなアプローチは取らないということです。

RGBで使われているClient-Side Validation (CSV)プロトコルでは、UTXOがどのような履歴を持っているかを検証します。トークンの受取人が、自分の受け取ったUTXOに関する情報だけを検証するようなイメージです。これは、ブロックチェーン上で検証せず手元で検証できるというメリットがありますが、一つのUTXOがたどってきた履歴を全て検証しようとすると、準指数関数的に検証すべき履歴のトランザクション数が増えてしまうという問題があります。

STARKによってCSVプロトコルの履歴が存在することの証明ができれば、トランザクション数の増加に伴って証明サイズが大きくなることはありません。

アカウント情報更新と支払い

ユーザーはこのzkCoins上で複数のコインを保持するということはないため、UTXO型ではなくアカウント型を使います。

以下の図で上の灰色のブロックは(ビットコインのものとは限らない)ブロックチェーンであり、黒い丸は使い捨てシールのコミットされたアカウント更新地点を表します。

以下の図はアリスだけのアカウント更新を書いた図です。

• 状態41: 64バイトの署名値がブロックチェーンに記録されます。この署名値が署名しているメッセージは、state_key_42を含んでいます。

• 状態42: state_key_42 を使って、次の状態更新の鍵 state_key_43 を含むメッセージState 42に署名します。

• アリスはState 41からState 42までの間の、自分が受け取った全てのコイン(Input A, B, C)を確認します。また、State 41の時点で持っていた残高を確認します。さらに、State 42の更新時に自分が支払う全ての相手（Output Bob, Carol）に対する残高を確認します。

• アリスがブロックチェーンに記録したState 42の署名が正しい保証はどこにもありません（普通、ブロックチェーンに記録されるトランザクション署名情報は公開検証可能な、正しいことが期待されるデータなので、これはかなり特異な性質だと思われます）。アリスからコインを受け取るボブ、キャロルは、それぞれ自分自身でアリスから渡された証明が正しいことを検証しなければなりません。ボブ、キャロルはアリスからオフチェーンで受け取ったState 42の更新情報と、署名値が正しいことを確認します。さらに、それだけだとアリスが二重支払いをしている可能性があるので、State 41からState 42までの間で、アリスが一度もState key 42を使っていないことを、非包含証明(non-inclusion proof)によってアリス自身が証明しておき、その証明を State 42に含めておきます。

ブロックチェーンの圧縮と非包含証明の簡素化

非包含証明の証明対象の期間が長くなってしまうと、証明の作成が大変になります。これを防ぐために、全てのノードが、コンセンサスとして定期的（例えば一ヶ月ごと）に使い捨てシールを辞書順にソートして、マークルツリーの中に入れたデータ構造を作っておきます。そのマークルルートを計算しておくと、より簡単に非包含証明を作成できます。（下図参照）

非包含証明を証明したい要素eを与えられた時、一ヶ月単位で、マークルツリーの葉の辞書順序でeの前後にあたる要素がマークルツリー内に隣接して存在することを証明すれば十分であり、複雑なゼロ知識証明を使うことなく簡潔に非包含証明を作成できます。

例えば、1年前までの間での非包含証明を作りたい場合、eに対してマークルツリーに含まれない証明を12個作るだけでよいことになります。

疑問

zkCoinsでは二重支払い問題をどのように解決するか？

分岐していない特定のブロックチェーン内部におけるトランザクションの二重支払いという観点においては、 非包含証明によって解決します。ただし、チェーンを分岐させないように強制することはできないので、そこはサイドチェーンでブロック生成の何らかのアルゴリズム(PoW, PoA等)が使われるか、ビットコインのコンセンサスに従うしかないです。

コミットメントとして64バイトのデータがあるだけなのに、非包含証明が作成できるのか？

64バイトが「32バイトの公開鍵ハッシュ」+「32バイトの状態ハッシュ」ならば、「ある公開鍵が、特定の公開鍵ハッシュのリストの中に含まれていない」ということは証明できそうです(多分)。Shielded CSVでは無効化因子(nullifier)を使っているようです。
32バイトの状態ハッシュがありますが、状態の中には現在の公開鍵に加えて次に使う公開鍵も含まれます。

では署名はどこにあるのかというと、ハッシュ化される前の状態の中にあれば十分で、コインを受け取るユーザーやコミットメントをブロックに入れるブロック生成者以外はこれらの署名を検証することはできないし、自分が受け取らないなら無関係なので検証する必要もないはずです。

使い捨てシールはビットコインのUTXOや信頼された中央サーバーを使う?

使い捨てシールが実際に一度しか使われていないことの証明には、non-inclusion proofを使います。そのため、ビットコインのUTXOや信頼された中央サーバーは使わずにすみます。

あるいは、実際には使い捨てシールを2回使うようなトランザクションを作ってもブロックチェーンに記録したとしても、受け取り手から2回使われていないことの証明を求められたときに証明できないので、支払いには成功しません。

課題

• トランザクション発行では受取人がオンラインでなければならない。ただし、やりとりは双方向ではなく一方通行である。
• アカウント履歴の証明データ失うと資産が失われる。
• 支払人はアカウント情報更新の計算を証明するために十分な計算能力が必要であり、スマホなどでは実行できない可能性がある。
• 一般的な話だが、証明システムが複雑であり、新規の技術であるため、実装はまだ成熟していない。
• zkCoins上でビットコインをトークン化して動作させるためには、BitVM⁶などのゼロ知識証明器が必要になる。

感想

BitVM Bridge⁶は単体だと使いみちがよく分からない感じでしたが、zkCoinsのような具体例があると知れてよかったです。このzkCoinsのアイデアを発展させた具体的な実装としては Shielded CSV⁷があるようです。
「どんなデータでもブロックに入れてよく、かつそのデータが正しいかどうかは受取人にしかわからない」という状態でPoWチェーンを成立させるのは大変そうですが、チェーンのマイナー自身もそのデータ更新による報酬の受け取り手になるならば検証を行い不要なデータを入れさせないインセンティブはありそうです。

昔から似たようなアイデア⁸はあったようですが、具体的なスキームとして公開されているのは初めてなのかなと思いました。

参考文献