algorithm - 使用 Utreexo 累加器设置 UTXO 的证明

Question

我正在尝试了解 Utreexo 技术，但遇到了问题。在 Utreexo 中，我们有一片森林，每棵树都有 2^k 片叶子。我们有3个操作：

add(acc, newNode) : Proof // simply adds new UTXO to our Utreexo, and returns the proof for added element.
verify(acc, proof) : Bool // gets the proof as argument and checks that the element is still in set.
remove(acc, proof) // removes element with given proof from accumulator.

问题是：我添加了一个新的 UTXO 并得到了证明。之后，发生了一些变化（不同的删减和添加），Utreexo 的结构也发生了变化。现在，如我所见，我的证明（我在添加新 UTXO 时收到的）将不正确。如何处理这个问题？还是我误解了什么？

标签： algorithmtransactionscryptographybitcoincryptocurrency

Answer 1

您正在了解 Utreexo 如何正常工作。为单个累加器状态生成的证明仅对该状态有效。如果累加器因添加和删除而改变，则必须生成新的证明。

例如，区块#500,000 的单个 UTXO 的证明对区块 #500,001 无效。

进一步说明：

一般来说，Utreexo 是一个花哨的Merkle Tree。“证明”是散列到根所需的所有节点。对于这棵树：

 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
 12              13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
 08      09      10      11                                                                                                                                                                                      
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01  02  03  04  05  06  07

一个节点只需要保留根，因此该节点的树视图可能看起来像这样，其中只14保留了根 , 。

 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                                                                                                                                                                                                             
 |-------\       |-------\                                                                                                                                                                                       
                                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
  

如果有人想证明 node 的存在00，他们将需要提供以下节点：00, 01, 09, 13. 这些是需要能够散列到 的节点14，然后验证者将检查14它们存储的是否与用 的证明计算的相匹配00, 01, 09, 13。

所以对于这棵树，生成的证明将是节点00, 01, 09, 13。

假设通过删除 node 来修改树07。生成的树将如下所示：

  12                                                                                                                                                                                                              
  |-------\                                                                                                                                                                                                       
  08      09      10                                                                                                                                                                                              
  |---\   |---\   |---\                                                                                                                                                                                           
  00  01  02  03  04  05  06

如果我们想00再次证明，所需的节点是00, 01, 09，我们将匹配它12。这与之前的证明不同00, 01, 09, 13。

用比特币的术语来说，由于在生成新块时会修改累加器，因此证明会因块而异。