– Published by Mark A. Greenslade – Casper Association R & D on Medium（元記事）
はじめに
すべてのブロックチェーンに不可欠なセキュリティ対策は、暗号的に安全な情報データベースを使用することである。ブロックチェーンの設計はビットコインにまで遡る。ビットコインでは、UTXO（Unspent Transaction Outputs）はこのような安全なデータベースに保存される。このアイデアは、UTXOsをすべてハッシュ化してMerkle Treeにすることだ。
Merkle Tree（マークルツリー）→暗号データストア
ビットコインのマークルツリーでは、取引情報はハッシュ化され、リーフ（leave）として保存されます。それぞれのリーフは別のリーフとペアになり、連結されたペアがハッシュ化され、このプロセスがルートが1つになるまで続けられます。
イーサリアムはこの設計を改良し、イエローペーパーでパトリシア・マークルツリー（Patricia Merkle Tree）を導入しました。パトリシア・マークルツリーは値のペアをハッシュ化する代わりに、プレフィックスツリー（trie）を形成します。各ノードは、関連するデータとともに、キー（鍵）のプレフィックスを表します。Casper Patricia Merkle tree（呼称：Casper Trie）は、イーサリアムと同様の設計に従っています。
従来のマークルツリーもパトリシア・マークルツリーも、単一の要素がデータベースの一部であることを効率的な方法で暗号的に証明できます。2ⁿ の要素を持つマークルツリーでは、包含証明（inclusion proof）にn個のハッシュが必要となります。例えば、上記の例で5のハッシュの包含を証明するには、4、3、10のハッシュをこのように使用します：
3の計算に使われた1と2のハッシュは必要なく、3そのものが必要です。
パトリシア・マークルツリーの包含証明は、バイナリー・マークルツリーの証明よりも複雑です。このため、Casper Patricia Merkle treeのRustによる実装と、そのMerkle証明の検証方法について説明します。
ハッシュ化
簡略化のため、Casperのtrieコンポーネントをハッシュ化するアルゴリズムについては詳しく説明しません。これは、大きな入力をチャンク（塊）として処理するblake2bハッシュ化の一つとなります。実装については、casper_hashing ライブラリを参照ください。
ここでは、下記を取り上げます。
- ダイジェスト型の導入：
pub struct Digest([u8; 32]);
- 署名付きのハッシュ関数を仮定：
fn hash<T: AsRef<[u8]>>(data: T) -> Digest {
...
}パトリシア・マークルツリーのデータ構造
Casperのトライにおけるポインターブロックは、タグ付きダイジェストからなるradix-256のブランチノードとなります。256個のダイジェストはそれぞれ、リーフのハッシュか他のノードのハッシュのどちらかになります。
pub enum Pointer {
LeafPointer(Digest),
NodePointer(Digest),
}PointerBlockは、Option<Pointer>インスタンスの256サイズのarrayになります。
pub struct PointerBlock([Option<Pointer>; 256]);
impl PointerBlock {
pub fn new() -> Self {
PointerBlock(vec![None; 256].try_into().unwrap())
}
}(idx, Pointer)ペアのsparse（疎）スライスからPointerBlockを構築できる便利さ：
impl PointerBlock {
pub fn from_indexed_pointers(indexed_pointers: &[(u8, Pointer)]) -> Self {
let PointerBlock(mut pointer_block_array) = PointerBlock::new();
for (idx, ptr) in indexed_pointers.iter() {
pointer_block_array[*idx as usize] = Some(ptr.clone());
}
PointerBlock(pointer_block_array)
}
}これで、Trieの中核となるデータ構造にたどり着ります。3つのバリエーション（ リーフ、ノード、エクステンション）があります。
- リーフは、CasperのPatricia Merkleツリーに格納されたデータを含み、これらはキーで構成されます。
- ノードはPointerBlockを含み、ノードは暗黙的にTrieの接頭辞に位置します。PointerBlockの各ブランチは、ノードの暗黙の接頭辞よりも1バイト長い別の接頭辞を表します。
- エクステンション（拡張）ノードは、接頭辞またはキーが表す中間部分から構成されます。
Trie`の `to_bytes` メソッドを省略したが、これはデータ構造のバイト表現を提供します。
pub enum Trie {
Leaf { key: Key, value: StoredValue },
Node { pointer_block: Box<PointerBlock> },
Extension { affix: Bytes, pointer: Pointer },
}
impl Trie {
pub fn trie_hash(&self) -> Result<Digest, bytesrepr::Error> {
let bytes: Vec<u8> = self.to_bytes()?;
hash(&bytes)
}
}ここでも、(idx, Pointer)のペアのsparse（疎）リストをNodeにマーシャリングするのに役立つ便利な関数が提供されます。
impl Trie {
pub fn node(indexed_pointers: &[(u8, Pointer)]) -> Self {
let pointer_block = Box::new(PointerBlock::from_indexed_pointers(indexed_pointers));
Trie::Node { pointer_block }
}
}マークル・プルーフ（証明）
Merkle（マークる）証明は Trie データ構造を使用し、各ブロックに含まれるステートルートを再構築します。Trie::NodeとTrie::Extensionを反映して、Merkle証明のステップは次のようになります：
pub enum TrieMerkleProofStep {
Node {
hole_index: u8,
indexed_pointers_with_hole: Vec<(u8, Pointer)>,
},
Extension {
affix: Bytes,
},
}完全なマークル証明は、リーフ情報（この場合は `Key` と `StoredValue` のペア）と一連のステップから構成されます。
pub struct TrieMerkleProof {
key: Key,
value: StoredValue,
proof_steps: Vec<TrieMerkleProofStep>,
}これがCasperのtrieに要素が含まれているかどうかを検証するための中心的アルゴリズムになります。
– まず、`key` と `value` を使って `Trie::Leaf` を構築し、そのハッシュを計算します。これは、要素が属する Patricia Merkle trie の *Merkle root* を計算するための初期ハッシュです。これは変更可能な変数 `hash` に格納されます。
全ての証明ステップを一周すると：
- まず最初に、 `hash` が `Pointer::LeafPointer` でラップされます。そうでない場合は `Pointer::NodePointer` でラップします。
- `Trie::Node` に対応する各ステップは *hole* を持ち、スロットインさせる為に前のステップのハッシュのブランチのインデックスとなります。
- Trie::Extension`に対応する各ステップは、前のステップのハッシュを必要となります。
この一連の流れが終了すると、結果はCasperブロックに含まれるMerkleルートとなります。
impl TrieMerkleProof {
pub fn compute_state_hash(&self) -> Result<Digest, bytesrepr::Error> {
let mut hash = {
let leaf = Trie::Leaf {
key: self.key.clone(),
value: self.value.clone(),
};
leaf.trie_hash()?
};
for (proof_step_index, proof_step) in self.proof_steps.iter().enumerate() {
let pointer = if proof_step_index == 0 {
Pointer::LeafPointer(hash)
} else {
Pointer::NodePointer(hash)
};
let proof_step_bytes = match proof_step {
TrieMerkleProofStep::Node {
hole_index,
indexed_pointers_with_hole,
} => {
let hole_index = *hole_index;
let mut indexed_pointers = indexed_pointers_with_hole.clone();
indexed_pointers.push((hole_index, pointer));
Trie::node(&indexed_pointers).to_bytes()?
}
TrieMerkleProofStep::Extension { affix } => {
Trie::Extension {
affix: affix.clone
pointer
}.to_bytes()?
}
};
hash = Digest::hash(&proof_step_bytes);
}
Ok(hash)
}
}最終的な考察
大半のブロックチェーン同様、Casperプラットフォームは暗号化的に安全なデータベースのセットに永続的なステートを保存します。各データベースはマークルツリーの実装であり、より具体的にはCasperプラットフォームの場合はパトリシアマークルツリーとなります。
従って、Casperチェーン全体のステートは、マークルツリーの集合にエンコードされるため、基礎となる実装の最適化が不可欠です。ここでは、CasperのPatricia Merkle Treeについて深く掘り下げてみました。
Litmusの文脈では、Merkle Treeの集合に関連するMerkle証明の検証を通じたシステムのステートの最適化が、ネットワークとのトラストレスなインテラクションの基礎となる柱なのです。
No responses yet