Utreexo: 多くの UTXO ビットコインを圧縮

おい、ハブル！

ビットコインネットワークでは、すべてのノードがコンセンサスを通じて一連のUTXO、つまり、何枚のコインを、正確に誰に、どのような条件で使用できるかについて合意します。 UTXO セットはバリデーター ノードに必要な最小限のデータ セットであり、これがないとノードは受信トランザクションとそれらを含むブロックの有効性を検証できません。

この点に関して、セキュリティの保証を失わずに、このセットの保存された表現を削減し、圧縮するためのあらゆる可能な方法が試みられています。 保存されるデータの量が少ないほど、検証ノードのディスク容量要件が少なくなり、検証ノードの起動が安価になり、ネットワークを拡張できるため、ネットワークの安定性が向上します。

この投稿では、共著者からの最近の提案の Rust プロトタイプを投稿します。 ライトニングネットワーク用紙, タデウス・ドライヤ - Utreexo: ビットコイン UTXO セット用に最適化された動的ハッシュベースのアキュムレーターこれにより、バリデーター ノードのディスク容量要件を削減できます。

問題は何ですか？

ビットコインの長年の問題の XNUMX つは、そのスケーラビリティです。 「自分の銀行」という考えでは、ネットワーク参加者は使用可能なすべての資金の記録を保持する必要があります。 ビットコインでは、利用可能な資金は未使用の出力のセット、つまり UTXO セットとして表現されます。 これは特に直観的な表現ではありませんが、各「ウォレット」が別個のエントリとして「残高」を持つ表現よりも実装パフォーマンスの点で有益であり、プライバシーも追加されます（例: コインジョイン).

トランザクションの履歴 (いわゆるブロックチェーン) とシステムの現在の状態を区別することが重要です。 ビットコインのトランザクション履歴は現在、約 200 GB のディスク容量を占めており、増加し続けています。 ただし、システム状態は 4 GB 程度とはるかに小さく、誰かが現在コインを所有しているという事実のみが考慮されます。 このデータの量も時間の経過とともに増加しますが、その速度ははるかに遅く、場合によっては減少する傾向さえあります (CDPV を参照)。

ライト クライアント (SPV) は、セキュリティの保証と引き換えに、秘密キー以外の最小状態 (UTXO セット) を保存できない機能を備えています。

UTXO および UTXO セット

UTXO (Unspent Transaction Output) は、未使用のトランザクション出力であり、トランザクションで転送された各サトシの旅の終点です。 使用されなかった出力は新しいトランザクションの入力となるため、使用され (spend)、UTXO セットから削除されます。

新しい UTXO は常にトランザクションによって作成されます。

• 入力のない Coinbase トランザクション: マイナーがコインを発行するときに新しい UTXO を作成します
• 通常のトランザクション: 既存の UTXO の特定のセットを使用しながら、新しい UTXO を作成します。

UTXO を使用するプロセス:

ウォレットは、このウォレットで使用可能な UTXO の量に基づいて、使用可能なコインの数 (残高) をカウントします。

各バリデーター ノードは、二重支出の試行を防ぐために、セットを監視する必要があります。 すべて UTXO確認時 各 トランザクション それぞれの ブロック。

ノードには次のロジックが必要です。

• UTXO セットへの追加
• UTXO セットからの削除
• セット内の単一の UTXO の存在を確認する

要素の追加と削除、セット内の要素の存在の確認と証明を行う機能を維持しながら、セットに関する保存情報の要件を軽減する方法があります。 暗号アキュムレータ.

UTXO用バッテリー

バッテリーを使用して複数のUTXOを保管するというアイデア 話し合った 前.

UTXO セットは、初期ブロック ダウンロード (IBD) 中にオンザフライで構築され、完全かつ永続的に保存されますが、その内容は、ネットワークの新しい正しいブロックごとにトランザクションを処理した後に変更されます。 このプロセスでは、約 200 GB のブロック データをダウンロードし、数億のデジタル署名を検証する必要があります。 IBD プロセスが完了すると、UTXO セットは約 4 GB を占有することになります。

しかし、アキュムレーターを使用すると、資金の合意ルールは検証と暗号証明の生成に簡素化され、利用可能な資金を追跡する負担は、資金の存在と所有権の証明を提供する資金の所有者に移されます。

アキュムレータは、セットのコンパクトな表現と呼ぶことができます。 保存された表現のサイズは定数である必要があります。 または、セットのカーディナリティと要素自体のサイズに関して線形的に増加しません。たとえば、 ここで、n は格納されたセットのカーディナリティです。

この場合、アキュムレータは、要素がセットに含まれていることの証明 (包含証明) を生成でき、この証明を効果的に検証できるようにする必要があります。

バッテリーと呼ばれます ダイナミック if を使用すると、セットに要素を追加したり、セットから要素を削除したりできます。

そのようなバッテリーの例は次のとおりです。 2018 年 XNUMX 月に Boneh、Bunz、Fisch によって提案された RSA アキュムレータ。 このようなアキュムレータは、格納された表現のサイズが一定ですが、存在する必要があります。 共有秘密 (信頼できるセットアップ)。 この要件は、ビットコインのようなトラストレス ネットワークに対するこのようなアキュムレータの適用性を無効にします。シークレット生成中のデータ漏洩により、攻撃者が UTXO の存在の偽りの証拠を作成し、そのようなアキュムレータに基づく UTXO セットでノードを欺く可能性があるためです。

ウトレクソ

Thaddeus Dryja によって提案された Utreexo デザインにより、 ダイナミック アキュムレータ без 信頼できるセットアップ。

Utreexo は完璧なバイナリの森です マークルの木 で提示されたアイデアを発展させたものです。 分散型 pki 用の効率的な非同期アキュムレータ、セットから要素を削除する機能が追加されました。

バッテリーの論理構造

バッテリーセルは、理想的な二分木の森の中に配置されています。 木は高さ順に並べられます。 この表現は最も視覚的に選択されており、バッテリーでの操作中にツリーの結合を視覚化できます。

著者は、森の中の木はすべて理想的なので、自然数が XNUMX の累乗の和で表現できるのと同様に、その高さも XNUMX の累乗で表現されると述べています。 したがって、任意のリーフのセットをバイナリ ツリーにグループ化できます。どの場合でも、新しい要素を追加するには知識が必要です。 保存されたツリーのルート ノードのみについて.

したがって、Utreexo アキュムレータの保存表現はルート ノード (マークル ルート) のリストです。 木の森全体ではありません.

ルート要素のリストを次のように表します。 Vec<Option<Hash>>。 オプションタイプ Option<Hash> は、ルート要素が欠落している可能性があることを示します。これは、アキュムレータ内に適切な高さのツリーが存在しないことを意味します。

/// SHA-256 хеш
#[derive(Copy, Clone, Hash, Eq, PartialEq)]
pub struct Hash(pub [u8; 32]);

#[derive(Debug, Clone)]
pub struct Utreexo {
    pub roots: Vec<Option<Hash>>,
}

impl Utreexo {
    pub fn new(capacity: usize) -> Self {
        Utreexo {
            roots: vec![None; capacity],
        }
    }
}

要素の追加

まずは機能を説明します parent()、指定された XNUMX つの要素の親ノードを認識します。

親()関数

マークル ツリーを使用しているため、XNUMX つのノードのそれぞれの親は、子ノードのハッシュを連結したハッシュを格納する XNUMX つのノードになります。

fn hash(bytes: &[u8]) -> Hash {
    let mut sha = Sha256::new();
    sha.input(bytes);
    let res = sha.result();
    let mut res_bytes = [0u8; 32];
    res_bytes.copy_from_slice(res.as_slice());

    Hash(res_bytes)
}

fn parent(left: &Hash, right: &Hash) -> Hash {
    let concat = left
        .0
        .into_iter()
        .chain(right.0.into_iter())
        .map(|b| *b)
        .collect::<Vec<_>>();

    hash(&concat[..])
}

著者は、シャルル・ブイヤゲ、ピエール＝アラン・フーク、アディ・シャミール、セバスチャン・ジマーが述べた攻撃を防ぐには次のように述べている。
ディザリングされたハッシュ関数に対する XNUMX 回目のプリイメージ攻撃、XNUMX つのハッシュに加えて、ツリー内の高さも連結に追加する必要があります。

アキュムレータに要素を追加するときは、どのルート要素が変更されたかを追跡する必要があります。 追加する各要素のルート要素を変更するパスに従うことで、後でこれらの要素の存在の証明を構築できます。

追加時に変更を追跡する

加えられた変更を追跡するには、構造体を宣言しましょう Update、ノードの変更に関するデータが保存されます。

#[derive(Debug)]
pub struct Update<'a> {
    pub utreexo: &'a mut Utreexo,
    // ProofStep хранит "соседа" элемента и его положение
    pub updated: HashMap<Hash, ProofStep>,
}

バッテリーに要素を追加するには、以下が必要です。

• ルート要素のバスケットの配列を作成する new_roots そして、既存のルート要素をバケットごとに XNUMX つずつそこに配置します。

コード

let mut new_roots = Vec::new();

for root in self.roots.iter() {
    let mut vec = Vec::<Hash>::new();
    if let Some(hash) = root {
        vec.push(*hash);
    }

    new_roots.push(vec);
}

• 追加する要素(配列)を追加します。 insertions) 最初のカートへ new_roots[0]:

コード

new_roots[0].extend_from_slice(insertions);

• 最初のバスケットに追加したアイテムを残りのアイテムと結合します。
  • 複数の商品が入っているすべてのカートの場合:
    1. バスケットの端から XNUMX つの要素を取り出し、それらの親を計算し、両方の要素を削除します
    2. 計算された親を次のカートに追加します

コード

for i in 0..new_roots.len() {
    while new_roots[i].len() > 1 {
        // Объединяем два элемента в один и удаляем их
        let a = new_roots[i][new_roots[i].len() - 2];
        let b = new_roots[i][new_roots[i].len() - 1];
        new_roots[i].pop();
        new_roots[i].pop();
        let hash = self.parent(&a, &b);

        // Наращиваем количество корзин если требуется
        if new_roots.len() <= i + 1 {
            new_roots.push(vec![]);
        }

        // Помещаем элемент в следующую корзину
        new_roots[i + 1].push(hash);

        // Не забываем отслеживать изменения;
        // это пригодится для генерации доказательства добавления элементов
        updated.insert(a, ProofStep { hash: b, is_left: false });
        updated.insert(b, ProofStep {hash: a, is_left: true });
    }
}

• ルート要素をビンから結果のアキュムレータ配列に移動します

コード

for (i, bucket) in new_roots.into_iter().enumerate() {
    // Наращиваем аккумулятор если требуется
    if self.roots.len() <= i {
        self.roots.push(None);
    }

    if bucket.is_empty() {
        self.roots[i] = None;
    } else {
        self.roots[i] = Some(bucket[0]);
    }
}

追加された要素のプルーフを作成する

バッテリーにセルが含まれていることの証明 (Proof) はチェーンで構成されるマークル パスとして機能します。 ProofStep。 道がどこにも通じていない場合、証明は間違っています。

/// Единичный шаг на пути к элементу в дереве Меркла.
#[derive(Debug, Copy, Clone)]
pub struct ProofStep {
    pub hash: Hash,
    pub is_left: bool,
}

/// Доказательство включения элемента. Содержит сам элемент и путь к нему.
#[derive(Debug, Clone)]
pub struct Proof {
    pub steps: Vec<ProofStep>,
    pub leaf: Hash,
}

要素（構造体）を追加するときに、以前に取得した情報を使用します。 Update) を使用すると、バッテリーに要素が追加されたことを示す証拠を作成できます。 これを行うために、行われた変更のテーブルを調べて、各ステップを Merkle のパスに追加します。これは後で証拠として機能します。

コード

impl<'a> Update<'a> {
    pub fn prove(&self, leaf: &Hash) -> Proof {
        let mut proof = Proof {
            steps: vec![],
            leaf: *leaf,
        };

        let mut item = *leaf;
        while let Some(s) = self.updated.get(&item) {
            proof.steps.push(*s);
            item = parent(&item, &s);
        }

        proof
    }
}

プルーフ作成の流れ

要素の証明をチェックする

要素の包含証明のチェックは、既存のルート要素に至るまでマークル パスをたどることに要約されます。

pub fn verify(&self, proof: &Proof) -> bool {
    let n = proof.steps.len();
    if n >= self.roots.len() {
        return false;
    }

    let expected = self.roots[n];
    if let Some(expected) = expected {
        let mut current_parent = proof.leaf;
        for s in proof.steps.iter() {
            current_parent = if s.is_left {
                parent(&s.hash, &current_parent)
            } else {
                parent(&current_parent, &s.hash)
            };
        }

        current_parent == expected
    } else {
        false
    }
}

明らかに：

Aの証明をチェックするプロセス

アイテムの削除

バッテリーからセルを取り外すには、そのセルがそこにあるという有効な証拠を提供する必要があります。 証明からのデータを使用すると、指定された証明が真ではなくなるアキュムレータの新しいルート要素を計算することができます。

アルゴリズムは次のとおりです。

1. 追加と同様に、バスケット インデックスから XNUMX の累乗に等しい高さのマークル ツリーに対応する空のバスケットのセットを編成します。
2. マークル パスのステップからの要素をバスケットに挿入します。 バスケットインデックスは現在のステップの番号に等しい
3. 証明からのパスが導くルート要素を削除します
4. 加算と同様に、バスケットの要素をペアで結合し、結合の結果を次のバスケットに移動することによって、新しいルート要素を計算します。

コード

fn delete(&self, proof: &Proof, new_roots: &mut Vec<Vec<Hash>>) -> Result<(), ()> {
    if self.roots.len() < proof.steps.len() || self.roots.get(proof.steps.len()).is_none() {
        return Err(());
    }

    let mut height = 0;
    let mut hash = proof.leaf;
    let mut s;

    loop {
        if height < new_roots.len() {
            let (index, ok) = self.find_root(&hash, &new_roots[height]);
            if ok {
                // Remove hash from new_roots
                new_roots[height].remove(index);

                loop {
                    if height >= proof.steps.len() {
                        if !self.roots[height]
                            .and_then(|h| Some(h == hash))
                            .unwrap_or(false)
                        {
                            return Err(());
                        }

                        return Ok(());
                    }

                    s = proof.steps[height];
                    hash = self.parent(&hash, &s);
                    height += 1;
                }
            }
        }

        if height >= proof.steps.len() {
            return Err(());
        }

        while height > new_roots.len() {
            new_roots.push(vec![]);
        }

        s = proof.steps[height];
        new_roots[height].push(s.hash);
        hash = self.parent(&hash, &s);
        height += 1;
    }
}

要素「A」を削除するプロセス:

既存のネットワークへの統合

提案されたアキュムレータを使用すると、ノードは、UTXO セットを変更できる一方で、すべての UTXO を格納するために DB を使用することを回避できます。 ただし、証拠の扱いに問題が生じます。

UTXO アキュムレータを使用するバリデータ ノードを呼び出してみましょう コンパクト (コンパクト状態ノード)、アキュムレータのないバリデータは次のようになります。 完成する (フルノード)。 XNUMX つのクラスのノードが存在すると、それらを単一のネットワークに統合する際に問題が生じます。これは、コンパクト ノードではトランザクションで消費される UTXO の存在証明が必要ですが、フル ノードでは必要がないためです。 すべてのネットワーク ノードが同時に連携して Utreexo の使用に切り替えないと、コンパクト ノードが取り残され、ビットコイン ネットワークで動作できなくなります。

コンパクトなノードをネットワークに統合するという問題を解決するために、追加のノード クラスを導入することが提案されています。 橋。 ブリッジ ノードは、Utreexo バッテリーと電源投入証明も保存する完全なノードです。 すべて UTXOセットのUTXO。 ブリッジは、トランザクションの新しいブロックが到着すると、新しいハッシュを計算し、アキュムレータと証明を更新します。 アキュムレータと証明を維持および更新しても、そのようなノードに追加の計算負荷がかかることはありません。 ブリッジはディスク容量を犠牲にします: 物事を整理しておく必要があります ハッシュと比較して コンパクト ノードのハッシュ。n は UTXO セットの累乗です。

ネットワーク アーキテクチャ

ブリッジを使用すると、既存のノードのソフトウェアを変更することなく、コンパクトなノードをネットワークに徐々に追加することができます。 フルノードは以前と同様に動作し、トランザクションとブロックをノード間で分散します。 ブリッジ ノードは、Utreexo バッテリー データと一連の包含証明を追加で保存する完全なノードです。 すべて とりあえずUTXO。 ブリッジ ノードは、それ自体をそのようにアドバタイズせず、すべてのフル ノードに対してはフル ノード、すべてのコンパクト ノードに対してはコンパクト ノードであるふりをします。 ブリッジは両方のネットワークを接続しますが、実際には、既存のフル ノードからコンパクト ノードへという一方向にのみ接続する必要があります。 これが可能なのは、トランザクション形式を変更する必要がなく、コンパクト ノードの UTXO プルーフを破棄できるためです。そのため、ブリッジ ノードの参加なしに、どのコンパクト ノードも同様にすべてのネットワーク参加者にトランザクションをブロードキャストできます。

まとめ

私たちは Utreexo バッテリーを調べ、そのプロトタイプを Rust に実装しました。 私たちは、バッテリーベースのノードの統合を可能にするネットワーク アーキテクチャを検討しました。 コンパクト キャッチの利点は、保存されるデータのサイズが UTXO のセットの能力に対数的に依存することです。これにより、そのようなノードのディスク領域とストレージ パフォーマンスの要件が大幅に軽減されます。 欠点は、プルーフを送信するための追加のノード トラフィックですが、証拠集約技術 (XNUMX つのプルーフが複数の要素の存在を証明する場合) とキャッシュにより、トラフィックを許容範囲内に抑えることができます。

リファレンス:

• Rust の Utreexo プロトタイプの GitHub
• タデウス・ドライヤ - Utreexo: ビットコイン UTXO セット用に最適化された動的ハッシュベースのアキュムレーター
• 記事のアニメーションイラスト

出所： habr.com