Utreexo
Cryptology ePrint Archive: Report 2019/611 - Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set
mit-dci/utreexo: accumulator for bitcoin utxo set
ELI5: Utreexo — A scaling solution | by Calvin Kim | Medium
Progress Towards Utreexo Goals | BitMEX Blog
Oleg AndreevさんはTwitterを使っています 「@SomsenRuben @adam3us @kcalvinalvinn Even if you use snarks just to go from root to root, you also need most of the data to track updates to your own utxos. If you don’t have any you don’t really need to run a node.」 / Twitter
しくみ
Full node は従来、すべての Block に対する UTXO を保持する
Fullnode validation の目的は、最新の UTXO を知ること = それが Bitcoin の現在の状態だから
そのためには、各 Block における UTXO の状態を Tx で更新していくしかない(同時に Tx が正しいか validate する)
UTXO の変化は Tx によってしか起きない
Utreexo は UTXO の hash tree を生成する
送金者が自分が消費する UTXO が最新の UTXO set に含まれていることを証明する必要がある
自分の UTXO と hash tree の path? を示すことで、validator は markle root を生成し検証できる
Utreexo の markle root をもっているだけで、Full node と同じレベレの検証ができる
それに加えて、自分が関心がある=自分のUTXO を保持していれば ok
従来は、validator がすべての UTXO をもっているので、送金側が proove する必要はない
しかし UTXO は数GB のサイズがあるので full node の負担は大きい
このような full node を Compact State Node(CSN) と呼ぶ
誰が? Tadge Dryja?
leaf の順番大事だよね?
実際の IBD のプロセスがイメージできていない...
Pros
full node が数キロバイトで済む
コンセンサスアルゴリズムとDBの分離
folk 不要
IBD でディスクI/O しなくていい
utxo がメモリに全部載っているのと同じことだから?
Cons
IBD での使用帯域が増加
archive ノードの容量は増加
Pruned Node は UTXO セットは保持する
full node の一種として Compact State Node ができる?
full node はすべての tx を自分のデータだけで検証できる?
(16) MIT Bitcoin Expo 2019 - Utreexo: Reducing Bitcoin Nodes to 1 Kilobyte - YouTube by Tadge Dryja
【動画で学ぶブロックチェーン】ハッシュベースのアキュムレーター Utreexoの仕組み - 安土 茂亨氏 - GBEC - Blockchain を推進するエンジニアリングコミュニティ - #GBEC
Tadge Dryja on Scaling Bitcoin With Utreexo — What Bitcoin Did
Grey Mirror #1—Tadge Dryja, Digital Currency Initiative: uTreeXO and Bootstrapping Bitcoin Upgrades | by Rhys Lindmark | MIT Media Lab Digital Currency Initiative | Medium
Video: What Could Utreexo Mean For Bitcoin? – Bitcoin Magazine
IBD が早くなる理由
現在の UTXOs を得るためにはすべてのブロックを検証して、いまの UTXO の状態を得る必要がある
ほかの full node から Tx をダウンロードして、検証して、Block ごとの UTXO set をつくっていく
Block 1 の UTXO set ができた
Block 2 の Tx をもらう
Input が Block 1 の Utxo set に含まれていることを検証する
だから utxo set が必要
コスト
disk I/O
disk size
正しい Utreexo markle root だけをもっていれば、Tx をもらって、tree を構成すれば検証できる
正しい Utreexo root であることは?
最新の root がもっとも hash power がのった chain の root であれば ok ということ?
root だけ持てばいい utreexo の場合は、小さいのでメモリにおいておけるから高速化できる
ただし、proof 分?ダウロードするデータは増加する
Light client のセキュリティが向上する?理由
Compact State Node
full node は少なくともすべての UTXOs を持つ必要があった
UTXOs を持っていないとリレーされてきた tx が正しいか検証できない
しかし、utreexo ではルートをもっていれば、proof と utxo が送られてくれば、自身の root に対して検証ができる
Wallet はなにを管理する?
いままで通り自分の utxos
proof
proof はブロックごとに変わる可能性がある?絶対かわる?
proof をもつことで proof がない場合と比べてなにがいいのか?
いまはすべてのフルノードが utxos セット全体を保持
exchange がもつ大量の utxos もコストをかけてマネージしている
自分のだけ管理がいいよね
ZkVM はすでに似た概念を実装している?
ZkVM: a new design for fast, confidential smart contracts | by Oleg Andreev | Stellar Developers | Medium