Utreexo：压缩许多 UTXO 比特币

嘿哈布尔！

在比特币网络中，所有节点通过共识就一组 UTXO 达成一致：有多少代币可用于消费、具体消费给谁、以及在什么条件下消费。 UTXO 集是验证器节点所需的最小数据集，没有它，节点将无法验证传入交易和包含交易的区块的有效性。

在这方面，正在以各种可能的方式尝试减少该集合的存储表示，以在不失去安全保证的情况下对其进行压缩。 存储数据量越小，验证器节点的磁盘空间要求就越低，这使得启动验证器节点变得便宜，允许您扩展网络，从而提高网络的稳定性。

在这篇文章中，我们将发布合著者最近提案的 Rust 原型 闪电网络论文, 撒迪厄斯·德雷亚 - Utreexo：针对比特币 UTXO 集优化的基于动态哈希的累加器，这可以减少验证器节点的磁盘空间需求。

有什么问题？

比特币长期存在的问题之一是其可扩展性。 “你自己的银行”的想法要求网络参与者保存所有可用资金的记录。 在比特币中，可用资金表示为一组未花费的输出——UTXO 集。 虽然这不是一个特别直观的表示，但与每个“钱包”都有一个“余额”作为单独条目的表示相比，它在实现性能方面是有利的，并且还增加了隐私（例如，钱包）。 CoinJoin).

区分交易历史（所谓的区块链）和系统的当前状态非常重要。 比特币交易历史目前占用约 200 GB 的磁盘空间，并且还在持续增长。 然而，系统状态要小得多，约为 4 GB，并且仅考虑某人当前拥有硬币的事实。 这些数据量也会随着时间的推移而增加，但速度要慢得多，有时甚至会减少（参见 CDPV）。

轻客户端 (SPV) 以安全保证换取除私钥之外不存储最低状态（UTXO 集）的能力。

UTXO 和 UTXO 集

UTXO（Unspent Transaction Output）是未花费的交易输出，是交易中转移的每个中本聪旅程的终点​​。 未花费的输出成为新交易的输入，因此被花费（花费）并从 UTXO 集中删除。

新的 UTXO 总是由交易创建：

• 无输入的 coinbase 交易：当矿工发行硬币时创建新的 UTXO
• 常规交易：创建新的 UTXO，同时花费一组现有的 UTXO

使用 UTXO 的流程：

钱包根据该钱包可用于支出的 UTXO 数量来计算可用于支出的代币数量（余额）。

为了防止双重支出尝试，每个验证器节点必须监视该集合 所有 检查时的UTXO 每 交易 每 堵塞。

节点必须具有逻辑：

• UTXO 集的添加
• 从 UTXO 集中删除
• 检查集合中是否存在单个 UTXO

有多种方法可以减少对集合存储信息的要求，同时保持添加和删除元素的能力，使用以下方法检查和证明集合中元素的存在 密码累加器.

UTXO 电池

使用电池存储多个UTXO的想法 讨论 早期.

UTXO 集是在初始块下载 (IBD) 期间动态构建的，完整且永久地存储，而其内容在处理来自网络的每个新的正确块的交易后会发生变化。 这个过程需要下载大约200GB的区块数据并验证数亿个数字签名。 IBD过程完成后，UTXO集将占用大约4GB。

然而，对于累加器，资金的共识规则被简化为验证和生成密码证明，并且跟踪可用资金的负担转移到这些资金的所有者身上，由其提供其存在和所有权的证明。

累加器可以称为集合的紧凑表示。 存储表示的大小必须是常量 ，或者相对于集合的基数和元素本身的大小呈次线性增加，例如 ，其中 n 是存储集合的基数。

在这种情况下，累加器应该允许生成集合中包含元素的证明（包含证明），并且可以有效地验证该证明。

这种电池被称为 动态的 if 允许您添加元素和从集合中删除元素。

这种电池的一个例子是 Boneh、Bunz、Fisch 于 2018 年 XNUMX 月提出的 RSA 累加器。 这样的累加器具有恒定大小的存储表示，但需要存在 共享秘密 （可信设置）。 这一要求否定了这种累加器对于像比特币这样的去信任网络的适用性，因为秘密生成期间的数据泄漏可能允许攻击者创建 UTXO 存在的虚假证明，并使用基于这种累加器的 UTXO 集欺骗节点。

Utreexo

Thaddeus Dryja 提出的 Utreexo 设计使得创建 动态 电池 无 可信设置。

Utreexo 是完美二元森林 默克尔树 并且是对中提出的想法的发展 用于分布式 pki 的高效异步累加器，添加从集合中删除元素的功能。

电池逻辑结构

电池单元排列在理想二叉树森林中。 树木按高度排序。 该表示被选为最直观的表示，允许您在电池操作期间可视化树木的合并。

作者指出，由于森林中的所有树木都是理想的，因此它们的高度可以表示为 XNUMX 的幂，就像任何自然数都可以表示为 XNUMX 的幂之和一样。 因此，任何叶子集合都可以分组为二叉树，并且在所有情况下，添加新元素都需要知识 仅关于存储树的根节点.

因此，Utreexo 累加器的存储表示是根节点（Merkle 根）的列表， 而不是整个森林.

让我们将根元素列表表示为 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()，它识别两个给定元素的父节点。

父函数（）

由于我们使用 Merkle 树，因此两个节点中的每一个的父节点都是一个节点，用于存储子节点哈希值串联的哈希值：

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[..])
}

作者指出，为了防止 Charles Bouillaguet、Pierre-Alain Fouque、Adi Shamir 和 Sebastien Zimmer 在
对抖动哈希函数的第二次原像攻击，除了两个哈希之外，树内部的高度也应该添加到串联中。

当您向累加器添加元素时，您需要跟踪哪些根元素发生了更改。 通过遵循更改添加的每个元素的根元素的路径，您可以稍后构建这些元素存在的证明。

添加更改时跟踪更改

为了跟踪所做的更改，让我们声明结构 Update，它将存储有关节点更改的数据。

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

要向电池添加元件，您需要：

• 创建根元素篮子数组 new_roots 并将现有的根元素放在那里，每个存储桶一个：

代码

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. 从篮子的末尾取出两个元素，计算它们的父元素，删除这两个元素
    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 });
    }
}

• 将根元素从 bin 移动到结果累加器数组

代码

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
    }
}

创建证明的过程

检查元素的证明

检查元素的包含证明归结为遵循 Merkle 路径，直到它通向现有的根元素：

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. 与加法一样，我们根据篮子索引组织一组与 Merkle 树相对应的空篮子，其高度等于 XNUMX 的幂
2. 我们将 Merkle 路径的步骤中的元素插入到篮子中； 篮子索引等于当前步骤的编号
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 集。 然而，使用证据的问题出现了。

我们调用使用 UTXO 累加器的验证器节点 紧凑的 （紧凑状态节点），没有累加器的验证器是 充分 （全节点）。 两类节点的存在给将它们集成到单个网络中带来了问题，因为紧凑节点需要证明 UTXO 的存在，这些 UTXO 用于交易，而完整节点则不需要。 如果所有网络节点不同时并以协调的方式切换到使用 Utreexo，那么紧凑节点将被抛在后面，并且将无法在比特币网络上运行。

为了解决将紧凑节点集成到网络中的问题，建议引入一类额外的节点 - 桥梁。 桥接节点是一个完整的节点，还存储 Utreexo 电池和开机证明 所有 来自 UTXO 集合的 UTXO。 当新的交易块到达时，桥计算新的哈希值并更新累加器和证明。 维护和更新累加器和证明不会对此类节点施加额外的计算负载。 桥接会牺牲磁盘空间：需要让事情井井有条 哈希值，相比 紧凑节点的哈希值，其中 n 是 UTXO 集的幂。

网络架构

网桥可以在不改变现有节点软件的情况下逐步向网络添加紧凑节点。 全节点像以前一样运行，在它们之间分配交易和块。 桥接节点是完整节点，额外存储 Utreexo 电池数据和一组包含证明 所有 暂时是UTXO。 桥接节点不会这样宣传自己，它会假装是所有全节点的全节点和所有紧凑节点的紧凑节点。 虽然网桥将两个网络连接在一起，但实际上它们只需要在一个方向上连接它们：从现有的全节点到紧凑节点。 这是可能的，因为交易格式不需要改变，并且紧凑节点的UTXO证明可以被丢弃，因此任何紧凑节点都可以类似地向所有网络参与者广播交易，而无需桥接节点的参与。

结论

我们研究了 Utreexo 电池并用 Rust 实现了它的原型。 我们研究了允许集成基于电池的节点的网络架构。 Compact catch的优点是存储数据的大小，它与UTXO集合的功率成对数依赖，这大大降低了此类节点对磁盘空间和存储性能的要求。 缺点是传输证据需要额外的节点流量，但证据聚合技术（当一个证据证明多个元素的存在时）和缓存可以帮助将流量保持在可接受的范围内。

引用:

• Rust 中的 Utreexo 原型的 GitHub
• 撒迪厄斯·德雷亚 - Utreexo：针对比特币 UTXO 集优化的基于动态哈希的累加器
• 文章中的动画插图

来源： habr.com