ゼロ知識証明技術を用いたBinanceの新しいProof of Reserves (PoR)システム

こんにちは！弐号です。

FTXショックを皮切りとして、中央集権取引所 (CEX) が顧客残高以上の準備金を持っていることを証明することが求められています。

この証明は「Proof of Reserves (PoR)」といわれ、一般的にはマークルツリーを用いて実行されます。

しかし、従来のマークルツリーのみを用いる方法では、取引所が残高が負となるようなダミーアカウントを不正に挿入することによって、顧客の預かり残高を過少に見せることができてしまう、という欠点がありました。

この問題を克服するために、世界最大手取引所であるBinanceは、2023年1月分のPoR監査より、ゼロ知識証明を用いた新しい証明方式を採用しています。

これにより、従来方式の欠点であった残高が負のアカウントを不正に挿入していないことをゼロ知識証明を用いて数学的に証明することができるようになり、PoR監査の信頼性が大きく向上しました。

本記事では、なるべく数学的な詳細に立ち入らずにゼロ知識証明に馴染みの薄い読者でも読めるように解説を行います。

ただし、前提知識として従来のマークルツリーのみを用いたPoR方式を理解されていることを仮定しますので、まだ理解をされていない方は拙筆の記事「取引所の監査が自分でできる！Proof of Reserves (PoR) とは？」を先にお読みください。

（サムネイル画像は ゼロ知識証明(Wikipedia) より引用）

従来方式の欠点

PoRで中央集権取引所が示すべきことは

準備金残高 \geqslant 顧客の預かり残高

であることです。

そのために取引所は主に

  • 準備金としてコールドウォレットなどに十分な残高を持っていること
  • 顧客の預かり残高が正しいこと

を証明する必要があります。

前者については取引所の持つアドレスを公開し、そのアドレスで電子署名を作成することで簡単に証明を行うことができます。

問題は後者です。

従来のマークルツリーのみを用いた方式では、自分のアカウントの個別の残高が、取引所の発表している預かり資産の合計残高の勘定に含まれていることをマークルプルーフを用いることで非常に効率的 (O(log N)) に証明することができます。

ところが従来方式だと、マークルルートの計算に用いた個別のアカウント残高の中に取引所が不正に負の残高のアカウントを混ぜ込むことで、過少に計算されてしまうという事態を防ぐことが難しいという問題があります。

少し具体例を挙げて詳しく見てみましょう。

（以下の図はHow zk-SNARKs Improve Binance’s Proof of Reserves System(Binance) より引用）

例えば実際のアカウント残高が上記のようだった場合、取引所は総預かり資産である1,480ETH以上の準備金を持つ必要があります。

しかしながらこの図のように-500ETHという負の残高を持つアカウントを不正に挿入してしまうと、顧客の預かり残高が890ETHであるということになってしまい、預かり資産を過少に見せることができてしまいます。

OKXの行っている方式では、自己のアカウントの「（マークルツリー上において）隣」にあるアカウントの残高や、途中のマークルノードの残高は分かるようになっていますので、こうした残高が負となっていれば不正に気づくことができる可能性は存在します。

しかしながら、自前でPoR監査を行う可能性の低いインアクティブなアカウントの隣にダミーの負の残高のアカウントを配置するなどの工夫を行えば、不正を行ったとしても発覚する可能性は非常に低く抑えることができてしまうでしょう。

また、OKXのように自己のアカウントの「隣」や途中のマークルノードの残高が分かってしまう方式では、残高以外の情報は匿名化されているものの一部の情報が露出している形となりますので、プライバシーの観点からは100点満点とは言えません。

このような問題点を解決する方式が、Binanceが採用したゼロ知識証明を活用した、より高度なPoR方式となります。

ゼロ知識証明とは？

まずはゼロ知識証明 (zero knowledge proof; zk proof) について軽く説明します。

ゼロ知識証明とは、証明者 (prover) が持つ秘密情報に対し、その秘密情報の中身を一切開示せずに、検証者 (verifier) に対して秘密情報を確かに保持していることを数学的に証明することです。

例えば、ブロックチェーンでも頻繁に利用される電子署名は、秘密鍵という「秘密情報」を持っているということを、電子署名の検証者に秘密鍵の情報自体は開示せずに証明することができますので、（広義の）ゼロ知識証明だと言えるでしょう。

また例えばRSA署名を利用すれば、巨大な半素数の素因数分解の結果を知っていることを、素因数分解の結果自体を知らせることなく証明することができます（※厳密にはRSA署名を作成できることと素因数分解の結果を知っていることはイコールではないのですが、ここでは細かいことは考えないようにします）。

このように「相手にはデータ本体は知らせたくないけど、データを持っていることは証明したい」というニーズに応える暗号技術がゼロ知識証明です。

電子署名の例では秘密鍵というランダムな整数値を保有していることしか証明することができませんが、実はこれを拡張して「任意の命題（厳密にはNP問題）に対して、その命題が真であること」を証明することができます。

命題としては数学的に正しく (well-definedに) 表せるものであればどのようなものでもよく、例えば「あるハッシュ関数の出力が0xabcd…になるような入力を知っていること（そのような入力が存在すること）」といった、電子署名よりも一歩進んだ複雑な条件が含まれているような命題に対しても適用することができます。

一般の命題に対するゼロ知識証明方式はいろいろなものが存在するのですが、最もよく用いられているのは「zk-SNARKs」と呼ばれる方式（たち）です。

zk-SNARKs は zero knowledge Succinct Non-interactive ARgument of Knowledge の略であり、技術的な詳細は省きますが

  • 非対話 (non-interactive) で証明できる
  • 証明サイズが非常に小さく、高速に検証できる (succinct)

といった特徴があります。

証明の作成には比較的計算コストがかかるのですが、検証は非常に高速（現代のコンピュータであれば一瞬）であり、実用レベルで利用できる技術となっています。

Binance の新しい PoR 方式も zk-SNARKs を利用しているようです。

zk-SNARKsで証明する命題

さて、少々ゼロ知識証明の説明が長くなりましたが、PoRの話しに戻ります。

zk-SNARKs を用いた PoR では、従来のマークルツリーのみを用いた方式に追加して、各マークルリーフの計算に用いたユーザ残高のドル建て評価額がゼロ以上であることを証明します。

これにより、取引所は各アカウントの個別残高を一切外部に公開することなく、負の残高を持つような不正なアカウントが存在しないことを証明することができるのです！

なお、Binanceの実装では、マークルツリーの計算に用いるハッシュ関数としてゼロ知識証明と相性の良いハッシュ関数であるPoseidonハッシュが用いられており、また証明の計算時間を並列化して高速化するために864ユーザごとにマークルツリーを生成し、ゼロ知識証明を作成しているようです。

こうした工夫により、32コアの128GBの計算ノードを1,000台同時に動かすことで、大量のユーザの残高情報をもとにした証明を、たったの二時間で計算することができ、合計の計算コストは1,000ドル程度であると報告しています。

1,000ドルは決して安い金額ではありませんが、Binanceが一億人近くのユーザ数を抱える巨大な取引所であることを考えれば、現実的な計算コストで収まっていると評価することができるでしょう。

また最後に演習問題としても載せますが、実際にゼロ知識証明の検証を手元のマシンで行ったところ約50秒で検証を行うことができ、これは十分実用的な計算時間であると考えられます。

まとめ

  • 既存のマークルツリーのみを用いた PoR 方式では、負の残高を持つアカウントを不正に挿入することで、意図的に預かり残高を過少に報告することができるという問題があった
  • ゼロ知識証明 (zk-SNARKs) 技術を用いることで、こうした不正がないことを数学的に証明しながら監査を行える方式を実装することができた
  • 証明の作成に必要な計算コストは、一億人近くのユーザ数であっても1,000ドル程度に抑えることができ、また検証に必要な時間も一般的な仮定用PCで一分未満で済む

参考リンク

演習問題

「How to Verify Your Account Balance on Binance」の手順に従って、自分のアカウントの監査データ（※要ログイン）を用いて監査を実行してみよ。

関連記事