为什么需要UTXO证明,UTXO证明是为了解决什么问题

前一段时间 BCH 宣布要给区块增加 UTXO Commitments,并已经在测试网上线。

为了照顾不熟悉 UTXO 的朋友,先简单科普下 UTXO。Bitcoin 的区块上记录的是交易,每条交易都有一组 input 和 output,通过复式记账法记录 BTC 的交易,不熟悉的朋友可以简单理解成 Bitcoin 在转账的时候顺便把对账清算的事情也给做了。UTXO 的全称就是 ”unspent transaction output”,未花费的交易输出。所以 Bitcoin 上正真有价值的数据实际上就是 UTXO,相当于余额,已经花费的就是历史账单了。

图片来自精通比特币

但 UTXO 在区块上是记录在每个交易里面的,区块上的 Merkle hash 只能证明交易是否存在(具体参看 Bitcoin 的 SPV 机制),但不能证明该交易的 UTXO 是否被花费掉了。于是大家就讨论,是否有办法提供 UTXO 证明。

同时,另外一问题是,当前 Bitcoin 的所有区块已经有几百 G 大了,同步一次非常耗时,节点同步所有区块后,从区块中筛出来 UTXO,做新区块的校验,而总共的 UTXO 只有几个 G。所以大家想,那能不能只把 UTXO 同步过来呢?但这个方式带来的另外一个问题是,怎么证明同步过来的 UTXO 是对的,没被篡改?和上一个问题类似。

所以总结下,UTXO 证明实际上要解决两个问题:

  1. 全节点的同步问题,可以让新的全节点快速启动。

  2. 提供 UTXO 证明,即满足上面 1 的验证需求,也可用在交易验证,轻钱包上。

Bitcoin 的邮件列表里讨论了三个方案(链接1):

  1. ECMH commitment

ECMH(Elliptic Curve Multiset Hash)是一种 hash 算法,它的特点是可以把多个数据的 hash 合并到一个 hash 中,但还可以支持删除。这样节点维护一个 UTXO 的根 hash 的成本就很低了,每次只需做增量修改。然后只需要把 UTXO 根 hash 记录到区块上,其他节点同步 UTXO 集合之后,就可以验证该集合是否被篡改了。但这个方案的缺点是只能做全量验证,没办法验证单独一个 UTXO 是否存在,所以不满足问题 2 的需求。

  1. Bucketed ECMH commitment

这个方案和上面的类似,也用 ECMH,但要把每个 UTXO 的 hash 都保留着,维护一个分片的 Bucket 或者 Trie 结构,Bucket 或者 Trie 结构的每层都用 ECMH。 这样就有办法证明单个的 UTXO 了。

  1. Commitment enabled UTXO storage

改造 UTXO 的存储,将它存储在一种 Merkle binary tree 结构中,每次新区块产生,进行 merge 只需要计算变更的一部分。这种方案可以满足上面两个需求,但实现复杂度比较高,并且需要对 binary tree 的实现做优化。

初步看起来 BCH 采用的是方案1。社区中很早实际上就有类似方案讨论,最早在 2012 年,Bitcoin 论坛中就有《Storing UTXOs in a Balanced Merkle Tree》的讨论(链接2),作者设计了一种红黑树来保存 UTXO。《Dietcoin: shortcutting the Bitcoin verification process for your smartphone》这篇论文里讨论了一种 UTXO 分片的办法来实现这个机制。

UTXO

个人认为,Bitcoin 实际上需要一种类似于 Ethereum 的 global state 的机制,只不过 Ethereum 中的 global state 维护的是 Account 的余额,而 Bitcoin 这样的 UTXO 机制的,需要维护的是用户的 UTXO,复杂度高些,不过 Ethereum 的 Merkel Patricia Trie 的实现是有借鉴意义的。

qrcode_jolestar_blog2

相关链接


  1. https://lists.linuxfoundation.org/pipermail/bitcoin-ml/2018-March/000688.htm

  2. Storing UTXOs in a Balanced Merkle Tree (zero-trust nodes with O(1)-storage)