A scalable drop-in replacement for merkle trees at Scaling Bitcoin 2018

Scaling Bitcoin 2018復習シリーズ。今回は、昨年もBullet Proofsなど発表したスタンフォード大学のBenedikt Bünzによる「A scalable drop-in replacement for merkle trees」の発表で、内容的にはマークルツリーの代わりにRSAアキュムレータを利用したUTXOセットの管理方法の提案↓（58分くらいから）

youtu.be

発表スライド↓

https://tokyo2018.scalingbitcoin.org/files/Day1/scalable-drop-in-replacement-for-merkle-trees.pdf

書き起こしは↓

http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/accumulators/

UTXO

UTXOセットの成長はますます問題になってきている。現在のUTXOの数は6000万個にもおよぶ。問題は前のセッションでもあったようにUTXOのデータ構造が非効率的だということにある。古いブロックをダウンロードしたい場合、全てのブロックヘッダが必要になる。ブロックチェーンの先頭（最近のブロック）しか持っていない状況で、古いトランザクションをダウンロードし、それが使用済みかどうかチェックしたい場合、その間にあるトランザクションをすべてチェックし、そのトランザクションが使われているかどうかチェックする必要がある。

UTXO commitment

この問題を解決するために以前提案されたのがUTXO commitmentだった。全ブロックは現在のUTXOセットの状態など現在の状態へのコミットメントを取得する。このアイディアでは、実際に正しいUTXO commitmentがブロックヘッダ内に存在することをコンセンサスルールで保証する。そのため軽量クライアントはこれをチェックできる。軽量クライアントに未使用のUTXOであることを納得させたい場合は、それがUTXOセットcommitmentに含まれている証拠を提供すればよく、これをすべての軽量クライアントに対して行うことができる。

マークルツリーを使ったUTXO commitment

UTXO commitmentを実装する古典的な方法はマークルツリーを使用する方法。その時点のUTXOセットでマークルツリーを構成し、そのルートハッシュをブロックヘッダに格納する。

f:id:techmedia-think:20181028124733p:plain

UTXOセット内に対象のUTXOが存在することを証明するinclusion proofを提供すればよく、それはlog(n)のハッシュにになる（仕組み的にはSPVクライアントで実装されている部分マークルツリーの復元と同じロジック）。UTXOセット内に対象のUTXOが存在しないことを証明するexclusion proofもlog(n)のハッシュになる（この場合UTXOセットはソートされているか、マークルツリーの幅を知っている必要がある）。

ステートレスフルノード

UTXO commitmentを利用すると完全なUTXOセットを保存する必要がないステートレスなフルノードを構築することができる。スタンドアロンで完全な検証をするがそのノードは完全なUTXOセットを持っていないという状態になる。これがどのように動作するかというと、トランザクションを送信する際に、送信者がそのトランザクションのインプットは未使用のコインであることの証明を提供する必要がある。現在はマイナーによってマイナーが管理するUTXOセットにより未使用のトランザクションであることがチェックされているが、この設計ではこれをユーザーがコインが未使用であることを証明するようになる。このアプローチの良い点は、現在UTXOセットとして4GBのストレージを必要とするマイナーも、そのUTXOセットを保持する必要なく、単にその証明を使ってトランザクションの使用コインが未使用であることを検証するだけで済むという点だ。

マークルツリーの問題点

ただ、マークルツリーを使ったこのアプローチには以下のような問題点がある。

トランザクション毎にinclusion proofが必要になる。
主な問題としてinclusion proofをすべてのトランザクションに追加するとそれが非常に大きくなる。
- 単純にやると600GBのサイズに
- いろいろ最適化して160GB
検証コストが大きい。
- フルノードの検証が遅くなる。

RSA アキュムレータ

そこで今回マークルツリーの代わりに提案されたのがRSAアキュムレーター。アキュムレータというのは、何らかのジェネレーターによって生成され、以下の操作、関数を持つデータ構造になる。

要素の追加
アキュムレータと要素を引数にとり、要素を追加した更新されたアキュムレータを返す。
証明関数
ある要素がアキュムレータ内に存在することを証明する証明データを生成する。
検証関数
アキュムレータと証明データを引数に取り、bool値を返す。

ブロックチェーンのUTXOの管理をアキュムレータで行う場合、さらに要素の削除をサポートする必要がある。

セットアップ

以下のようにアキュムレータをセットアップする。

２つの素数の積（pとqは秘密の素数）N = p * qを選択する。
H：任意の要素を素数に写像するハッシュ関数
アキュムレータを初期化するため群から要素を選択 ${A_0 = g \in Z_n}$

※ 個人的にHの素数への写像については、衝突耐性とか問題ないのか気になる。

アキュムレータへの要素の追加

アキュムレータはセット（集合）に対する小さなコミットメントとして機能する。

現在のアキュムレータ ${A_i}$ に要素xを追加する場合、 ${A_{i+1} = A_i^{H(x)}}$ を計算することで、要素が追加されたアキュムレータ ${A_{i+1}}$ が得られる。

アキュムレータから要素の削除

逆にアキュムレータから要素を削除する場合、 ${A_{i+1} = A_i^{1/H(x)}}$ を計算することで、削除後のアキュムレータ ${A_{i+1}}$ が得られる。

ここでUTXOのセットを表現すると、アキュムレータの状態はセット内のすべての要素の積になる。セットSの全ての要素の積を ${u = \Pi_{s \in S} S}$ とすると、そのアキュムレータは ${A_t = g^{u}}$ となる。

このアキュムレータは良い特性の１つは要素がいつ追加されたかどうかは問題ではなく、可換である点。

inclusion proofの作成

上記以外にも良い特性がある。それがアキュムレータ内にある要素が存在するかどうかを証明するinclusion proofが非常に簡単なこと。

アキュムレータAにxが含まれていかどうかのinclusion proof πは以下になる。

${\pi = A^{\frac{1}{x}} \in \mathbb G}$

これはtraproor（落とし戸）（pとq）使って計算するか、シークレットを使って計算することができる。もしくはセットの全要素（O|S|）を知っているか。

inclusion proofの検証

inclusion proofが正しいかの検証は、アキュムレータAと要素ｘおよびそのinclusion proof ${\pi}$ が与えられ、

${\pi^x = A}$

を検証する。 ${\pi}$ が正直に構築されているのであればxと1/xが相殺して、Aになる。

また、もしxがセット内になければ、このRSAグループにおいてこのようなオペレーションはできないという安全性上の証明がある。

exclusion proof

同様にexclusion proofも生成できるが↓、少し複雑で発表では詳細は省略されてる。

${A= g^{u}}$
${a \cdot x + b \cdot u = gcd(x, u) = 1}$

[LiLiXue07]参照となってたので、原理はそのホワイトペーパー↓読むと分かるかも。

https://www.cs.purdue.edu/homes/ninghui/papers/accumulator_acns07.pdf

Trusted Setupが必要

RSAアキュムレータの課題はTrusted Setupを必要とする点。Nは巨大な素数pとqの積だが、このpとqの値を知っていれば暗号スキームを破ることができる。つまり、要素がアキュムレータ内に入っていなくても、入っていると騙すことができてしまう。

また、アキュムレータから効率よくデータを削除するためにはtrapdoor（落とし戸）の情報が必要になる。古典的なスキームではこれを行うアキュムレータマネージャーの存在を前提としている。

もしくは、ロン・リベスト仮定で公開されてるNを利用するか。RSAの発明者であるロン・リベストがNを作成し、その元となったpとqを削除し誰もそれを知らない状態にする。もしロン・リベストを信頼するならそのNを使えばいい。

が、なるべくそういった信頼モデルは排除したい。

Class Group

そこで別の提案が、Class Groupという仕組みを利用するアプローチ。これはもともとGaussにより開発された数学的オブジェクト。二次体のClass Group（類群）で、位数が未知の群であり、その群に含まれるアイテムの数は分からない。RSAと同様の特性があるが、Trusted Setupを必要としない。またClass Groupの要素は、RSAの要素より少し短く約半分になるもよう。

RSAアキュムレータの現状

現状可能なこと

inclusion proofについては、アキュムレータ内の要素数に関係なく一定のサイズにできる（全体で3000 bitくらい）。セットのサイズが4000を超えると、マークルツリーベースのinclusion proofより優れている。
動的でステートレスな追加が可能。アキュムレータ内に何が入っているかに関係なくアキュムレータに要素の追加が行える。
フルノード分のストレージを必要とせず、ユーザーは自身が所有するUTXOと、そのメンバーシップ証明を保持するだけで良い。

この研究での改善および課題

inclusion proofの集約およびバッチ処理

2つのトランザクション xとyがありそれぞれinclusion proof π1とπ2を持っているとする。そして以下の式が成立するものとする。

${\pi^x_1 = A, \pi^y_2 = A}$

そしてシャミアのトリックを使いxとyのinclusion proofを ${\pi_{1,2}^{x\cdot y} = A}$ とすることができる。

これの良いところはπ1も1.5 KB、π2も1.5 KBそして、 ${\pi_{1,2}^{x\cdot y}}$ も1.5 KBであるという点。そして任意の数分同じことができる。そのため、1.5 KBというのはトランザクション単位のマークルパスやRSA inclusion proofではなく、ブロック内の全てのinclusion proofのサイズになる。

ステートレスなdelete処理

trapdoorを持っていれば効率的に削除が可能だが、trapdoorを持って無い場合どうなる？効率的に計算するためにモデルの変更を考える。UTXOをアキュムレータから削除するタイミングはそれが使われたタイミングなので、その際、一緒にその所有者からinclusion proofが提供されるというモデルだ。↑ではアキュムレータから要素を削除する際の計算として、 ${A_{i+1} = A_i^{1/H(x)}}$ と定義したが、削除の際にアキュムレータと要素およびinclusion proof ${A_t, x, \pi}$ が提供されるのであれば、それは次のアキュムレータの値を持っていることに等しい。つまり、次のアキュムレータは ${A_{t+1} = \pi}$ である。

ただBitcoinに適用する場合は、工夫が必要になる。ブロックには多数のトランザクションが含まれるため、同じアキュムレータに対して、複数のトランザクションおよび複数のinclusion proofが存在する。そのままでは、上記のようにinclusion proofが次のアキュムレータを指すといったことにはならない。このため、↑のようにinclusion proofの集約を行う。その結果が次のアキュムレータになる。これがBatch Deleteで、同じアキュムレータに対して多くのinclusion proofを持ち、かつそれらを一度に削除することができるようになる。

バッチ検証の高速化

よく上がる懸念はRSAはハッシュ計算なんかに比べて遅いじゃないかということ。OpenSSLで2048 bitのRSAを使用すると毎秒219回の更新になる。特にブロックチェーンの完全同期を考えた場合、ブロックチェーン全体の更新は全てのプルーフをチェックする必要があるためとても遅くなる。集約技術は証明サイズの縮小にはなるが、検証時間を短くすることにはならない。

Class Groupを使った良いベンチマークはまだ無いが、最近Verifiable Delay Function（VDF）と呼ばれるものなどに使われつつある。また最近Chia NetworkがClass Groupをスピードアップさせるか、破壊を試みる競争に10万ドルの賞金をかけたので、その結果、良い情報が得られるだろう。

他には、検証時間を短縮するのにVDFの開発で生まれたWesolowski Proofと呼ばれる技術を使うことができるという提案。そしてそれを拡張し、Proof of Exponentiationを効率的に行う仕組みを提案。

高速なブロックの検証

↑の仕組みを使って高速なブロックの検証を実現する。

マイナーが高速にブロックをコンパイルしたい場合、

ブロックチェーンの現在の状態＝現在のアキュムレータの状態に対して、Stateless deleteにより使用された一連のUTXOを削除する。
新しく作成されたUTXOを追加する。
以下を持つ新しいブロックをコンパイルする。
- ブロックヘッダ
- トランザクションのリスト
- BLS署名
- 前のブロックのアキュムレータ ${A_t}$ から使用済みのUTXOを削除した ${A_{t + \frac{1}{2}}}$
- ${A_{t + \frac{1}{2}}}$ に対して新しいUTXOを追加した ${A_{t + 1}}$
- PoE（Proof of Exponentiation）

フルノードは↑の新しいブロックに対して、BLS署名の検証、以下２つのPoEの検証を行う。

${PoE(A_{t + \frac{1}{2}}^{\Pi_{s \in S^{S}}} = A_t)}$

${PoE(A_{t + \frac{1}{2}}^{\Pi_{n \in N^{N}}} = A_{t+1})}$

パフォーマンス

JavaのBigIntegerとJDKのハッシュ関数を使ってmacbookで検証すると、

マークルツリーを使った6,400万件のinclusion proofは26個のハッシュ計算で約8.5μs。
マイナーがアキュムレータに要素を追加したい場合、これは少し高価になって約1.5ms。
Wesolowski proofを使って検証した場合、0.3μs。これはマークルツリーを使う方法よりはるかに高速。

Class Groupについては実装がなく計測できていない。

以下は、今回のRSAアキュムレータの研究の応用ネタっぽい。

Vector Commitment

Vector Commitmentはアキュムレータに似ており、マークルツリーと一緒に使うこともできる。要素 ${a_1,...,a_n}$ のvectorがあり、そのVector Commitment（VC）がある場合、ある位置でそのvector commitmentを開くことができ、vectorのこの位置にある値を伝えることができ、その証明が ${\pi = Open(VC, a_i, i)}$ 。ただこの要素の証明πを使って、要素の検証 ${Verify(VC, \pi, a_i, i)}$ をするのが大変で、従来検証者はGB単位のメモリを必要とした。検証者がメモリを必要としない新しいVector Commitmentを構築することができる。

Short IOPs

IOP（Interactive oracle proofs）と呼ばれる高レベルなゼロ知識証明では（zk-STARKsなどもその一種）、

証明者は非常に長い証明に対する短いコミットメントを送信する。
検証者はそれに対し、いくつかのインデックスを指定する。
証明者は指定されたインデックスについて、その位置にある値を知っていることを示す証明と、マークルパスを検証者に送る。
検証者は証明を確認し、受け入れるか拒否するかを決める。

問題は3のマークルパスが非常に長いことで、これをvector commitmentに置き換える。またこの時、アキュムレータで使った技術と似た技術を使ってvector commitmentを集約することができる。これにより証明のサイズを小さくすることができる。

所感

長期的な視点で見た場合に、膨張するUTXOの管理やフルノードの負荷は課題になるので、こういったアキュムレータの取り組みは興味深い。でも↓などの気になるポイントも。

Trusted Setupを避けようとするとClass Groupを利用するということだけど、Class Groupの安全性やパフォーマンスについてははっきりしたデータがなく、実用可否ふくめてまだ時間かかりそう。
要素の削除処理についてはバッチ処理の説明があったけど、追加についてはそういった機能は無さそうだが、実際新しいブロックができる度に多くのUTXOが新しくできる訳で、それら１つずつRSAの計算していくと結構な計算量になりそうな気がするけどパフォーマンス的に大丈夫なんだろうか？
一方LNのペーパーの著者でもあるTadgeが提案しているマークルツリーベースのアキュムレータ「utreexo」のベースはツリーとハッシュ計算なので、単純な計算コストはこっちの方が速そうではある。ただ証明のサイズはRSAアキュムレータの方が固定値であり小さい。このあたりutreexoの情報が出てきたら比較してみたい。

Develop with pleasure!

福岡でCloudとかBlockchainとか。