本稿について
COSMOSのホワイトペーパー、最終更新日: 2018/4/7時点のものを対象とします。本稿では「Appendix」の日本語訳を掲載します。
原文はこちらになります。
スポンサードサーチ
Appendix（続き）
マークルツリーと証明の仕様
Tendermint/Cosmosエコシステム内でサポートされるマークルツリーは2種類ある。シンプルツリー（Simple Tree）とIAVL+ツリー（IAVL+ Tree）である。
シンプルツリー
シンプルツリーは静的な要素リストのためのマークルツリーだ。アイテム数が2のべき乗でない場合、いくつかのリーフは異なるレベルになる。シンプルツリーは木の両側を同じ高さにしようとするが、左側が1段高くなる可能性がある。このマークルツリーはブロックのトランザクションとアプリケーションステートルートの最上段のエレメントをマークル化するのに使用される。
IAVL+ツリー
IAVL+データ構造の目的は決定論的なマークルルートハッシュを効率的に演算できるように、アプリケーションステート内のキーバリューペアのための永続的なストレージを与えることにある。ツリーはAVLアルゴリズムを少し変形したものを用いて平衡を取り、あらゆるオペレーションはO(log(n))である。
AVLツリーでは、任意のノードの子の2つのサブツリーの高さは最大で1異なる。アップデートでこの条件に違反すると、旧ツリーの未修正ノードを指すO(log(n))個の新規ノードを作成することでツリーを平衡にする。元来のAVLアルゴリズムでは、インナーノードはキーバリューのペアを持つこともできる。AVL+アルゴリズム（+が付いている点に注目）はキーの保存にブランチノードだけを使いながらリーフノードのあらゆる値を維持できるようにAVLアルゴリズムを修正したものである。これはマークルハッシュの証跡を短く保持しながらアルゴリズムを単純化する。
AVL+ツリーはEthereumのパトリシアツリー（筆者注：Patricia trie, あるいはRadex tree）と似ている。トレードオフがある。IAVL+ツリーへの挿入前であればキーはハッシュ化されている必要はない。従ってキー空間での高速な順序通りの繰り返しができ、一定のアプリケーションにとってはメリットとなる。実装のロジックは単純で、インナーノードとリーフノードの2種類のノードしか必要としない。マークル証明は平均して短く、平衡なバイナリツリーである。一方でIAVL+ツリーのマークルルートはアップデートの順序に依存する。
今後、例えばEthereumのパトリシアツリーなど、効率的なマークルツリーもバイナリの変形版が使えるようになればさらにサポートする予定である。
（COSMOSホワイトペーパー日本語訳17 ←← 前）｜（次 →→ COSMOSホワイトペーパー日本語訳19(終)）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。