Utreexo：压缩很多UTXO比特币

哈Ha！

在比特币网络中，所有节点都在许多UTXO上达成共识：可用于消费的硬币数量，对象和对象以及条件。 UTXO的集合是验证者节点所需的最小数据集，否则该节点将无法验证传入事务及其包含的块的有效性。

在这方面，以各种方式尝试减少该组的存储表示，以压缩它而不损失安全保证。 存储的数据量越小，对验证器节点的磁盘空间的要求越低，这使得启动验证器节点变得便宜，从而使您能够扩展网络并从而提高网络稳定性。

在本说明中，我们将介绍Lightning Network Paper合著者Thaddeus Dryja - Utreexo最近提出的一项提案的Rust原型：这是一种基于哈希的动态累加器，已针对比特币UTXO集进行了优化 ，从而减少了验证器节点的磁盘空间需求。

怎么了

比特币的永恒问题之一是它的可扩展性。 “拥有银行”的想法要求网络参与者跟踪所有可用资金。 在比特币中，可用资金表示为一组未使用的输出-UTXO集。 尽管这不是一个非常直观的视图，但与每个钱包都有“余额”作为单独条目并增加隐私（例如CoinJoin提供工作）的视图相比，它在实现性能上具有优势。

区分交易历史记录（称为区块链）和系统当前状态非常重要。 比特币的交易历史目前占据约200 GB的磁盘空间，并且还在继续增长。 但是，系统的状态要小得多，大约为4 GB，并且仅考虑到某人当前拥有硬币这一事实。 这些数据的数量也随时间增加，但是速率要低得多，有时甚至会减少（请参阅KDPV）。

轻客户端（SPV）交换安全性保证，以确保不存储除私钥之外的任何最低状态（UTXO集）。

UTXO和UTXO集

UTXO（未花费的交易输出）-未花费的交易输出，即交易中传输的每个聪的旅程的终点​​。 未使用的输出将成为新交易的输入并同时花费，并从UTXO集中删除。

新的UTXO始终由事务创建：

• 没有输入的币库交易：在矿工发行硬币期间创建新的UTXO
• 常规交易：创建新的UTXO，同时花费一些现有的UTXO

使用UTXO的过程：

钱包会根据可用于该钱包消费的UTXO数量，考虑可用于消费的硬币数量（余额）。

为了防止重复尝试，每个验证器节点必须在验证每个块的每个事务期间跟踪所有 UTXO的收集。

该节点必须具有逻辑：

• UTXO集的补充
• UTXO集删除
• 检查集中是否存在单个UTXO

有一些方法可以减少对有关集合的存储信息的要求，同时保留使用密码电池添加和删​​除元素，检查并证明集合中元素存在的能力。

UTXO电池

前面 已经讨论了使用电池存储许多UTXO的想法。

UTXO集是在块链的初始加载（IBD，初始块下载）过程中动态构建的，它被完整且不断地存储，而其内容在处理来自每个新的正确网络块的事务后会发生变化。 此过程需要下载大约200 GB的数据块并验证数亿个数字签名。 IBD过程完成后，UTXO-set中的干燥残留物将占据约4 GB。

但是，在使用电池时，有关资金的共识规则归结为检查和生成加密证据，而追踪可用资金的负担就落在这些资金所有者的肩上，这为它们的存在和所有权提供了证据。

电池可以称为该装置的紧凑表示。 在这种情况下，存储视图的大小必须恒定 $$$O（1）$，或相对于元素集合的大小和元素本身的大小亚线性增加，例如 $$$O（对数（n））$其中n是存储集的幂。

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

如果电池允许您添加电池组中的物品或从电池组中取出物品，则称为动态电池。

这种电池的一个例子是由Boneh，Bunz，Fisch在2018年12月提出的RSA电池 。 这样的电池具有恒定的存储视图大小，但是需要共享的机密 （可信设置）。 该要求否定了这种累加器在诸如比特币之类的不信任网络中的适用性，因为在生成机密期间数据泄漏可能使攻击者通过基于此类累加器对带有UTXO集合的节点进行欺骗来创建UTXO存在的虚假证据。

Utreexo

Utreexo提议的Thaddeus Dryja设计使您可以创建动态电池， 而无需进行可信设置。

Utreexo是理想的二进制Merkle树的森林 ，是对分布式pki的高效异步累加器中提出的思想的发展，增加了从集合中删除元素的能力。

电池的逻辑结构

电池单元排列在完美的二叉树林中。 树木按高度排序。 该演示文稿被选为最直观的演示文稿，可让您在电池操作过程中可视化树木的融合。

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

因此，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()函数，该函数识别两个给定元素的父节点。

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

在向电池添加项目时，需要跟踪正在更改的根项目。 按照更改添加的每个元素的根元素的路径，以后可以构造这些元素存在的证明。

 #[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 }); } } 

• 将根元素从篮子移动到生成的电池阵列

 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 （ Proof ）将用作Merkle路径（Merkle Path），由ProofStep链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 } } 

显然：

删除项目

要从电池中取出电池，必须提供有效的证据证明电池在其中。 使用证明中的数据，我们可以计算出该证明不再适用的新电池根元素。

算法如下：

1. 与添加项一样，我们组织了一组与Merkle树相对应的空篮子，其高度等于篮子索引的两倍
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的证据。 当新的区块随交易到达时，网桥计算新的哈希值并更新电池和证据。 支持和更新电池以及证据不会在此类节点上施加额外的计算负荷。 桥梁牺牲了磁盘空间：保持秩序 $$$2n$哈希与 $$$log（n）$紧凑节点的哈希，其中n是设置的UTXO的幂。

网络架构

网桥使逐渐将紧凑的节点添加到网络成为可能，而无需更改现有节点的软件。 完整节点像以前一样工作，在它们之间分配事务和块。 桥节点是完整的节点，可以额外存储Utreexo电池数据和当前所有 UTXO的一组包含证据。 桥节点不会像这样通告自己，而是假装为所有完整节点的完整节点和所有紧凑节点的紧凑节点。 尽管网桥将两个网络连接在一起，但实际上，它们仅需要一个方向进行连接：从现有的完整节点到紧凑型节点。 这是可能的，因为不需要更改事务格式，并且可以丢弃用于紧凑型节点的UTXO证据，因此任何紧凑型节点都可以以相同的方式向所有网络参与者发送事务，而无需桥接节点的参与。

结论

我们审查了Utreexo电池，并在Rust中实现了其原型。 我们检查了网络架构，该架构将基于电池集成节点。 紧凑捕获的优点是存储数据的大小，它在对数上取决于许多UTXO的功能，从而大大减少了此类节点的磁盘空间要求和存储性能。 缺点是用于证据传输的额外节点流量，但是证据聚合技术（当一个证据证明存在多个元素时）和缓存可以帮助将流量保持在可接受的范围内。

参考文献 ：

• Utreexo Rust原型GitHub
• Thaddeus Dryja - Utreexo：针对比特币UTXO集优化的基于哈希的动态累加器
• 文章中的动画图稿