谈谈区块链的 UTXO 证明
为什么需要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 证明实际上要解决两个问题：
-
全节点的同步问题，可以让新的全节点快速启动。
-
提供 UTXO 证明，即满足上面 1 的验证需求，也可用在交易验证，轻钱包上。
Bitcoin 的邮件列表里讨论了三个方案（链接1）：
- ECMH commitment
ECMH（Elliptic Curve Multiset Hash）是一种 hash 算法，它的特点是可以把多个数据的 hash 合并到一个 hash 中，但还可以支持删除。这样节点维护一个 UTXO 的根 hash 的成本就很低了，每次只需做增量修改。然后只需要把 UTXO 根 hash 记录到区块上，其他节点同步 UTXO 集合之后，就可以验证该集合是否被篡改了。但这个方案的缺点是只能做全量验证，没办法验证单独一个 UTXO 是否存在，所以不满足问题 2 的需求。
- Bucketed ECMH commitment
这个方案和上面的类似，也用 ECMH，但要把每个 UTXO 的 hash 都保留着，维护一个分片的 Bucket 或者 Trie 结构，Bucket 或者 Trie 结构的每层都用 ECMH。 这样就有办法证明单个的 UTXO 了。
- 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 分片的办法来实现这个机制。
个人认为，Bitcoin 实际上需要一种类似于 Ethereum 的 global state 的机制，只不过 Ethereum 中的 global state 维护的是 Account 的余额，而 Bitcoin 这样的 UTXO 机制的，需要维护的是用户的 UTXO，复杂度高些，不过 Ethereum 的 Merkel Patricia Trie 的实现是有借鉴意义的。
相关链接