Zcash协议分析(3). 账本的简单优化
在第一篇文章中，我们提出了一个极其简单的、略微有点匿名性质的加密货币的方案。我着重讨论了代币的所有权而没有强调区块链是如何记录交易的。这里我将介绍在之前提出的方案中，账本中究竟记录哪些数据。
之前提到了，铸币交易tx_mint铸造一枚ZEC就是产生一个向量组c:=(r, sn, cm)，并把cm写入到账本中，其中需满足cm := COMM_r(sn)。消费交易tx_spend，实际上是明文公布sn并且零知识地证明拥有r。实际上ZEC系统需要对这两种交易分别进行记录。
CMList：账本中维护一张CMList列表，这个列表记录的是所有铸币交易中产生的cm；
SpentList：账本中还维护一张SpentList列表，这张列表记录了所有tx_spend交易所公布的sn。当然每个验证节点在接收到一笔消费交易tx_spend 时，该节点需要验证这币交易中的sn字段是否已经在SpentList中出现过。在所有铸币交易产生的币的sn字段都不重复的假设下（假设的合理性可以参照hash函数的抗碰撞性。实际上后面的文章会详细解读sn产生的过程），如果这币的sn已经出现在SpentList中，那么这笔消费交易可被认为是双花交易，验证节点抛弃这笔交易。
这样，可以看到系统维护了两张列表，搜索CMList和SpentList的时间复杂度和存储的空间复杂度都会随着时间和交易的增加而增加，这一问题可以通过对列表的压缩来达到优化的效果。
这一步优化的步骤其实也很简单，就是用Merkle-tree对CMList进行作用Tree(CMList)，Tree(CMList)作用结果是这个树的树根rt，在账本中记录rt，全节点记录完整的CMList列表的详细数据。Tree(CMList)具有的性质保证了，往CMList插入一个cm，Tree(CMList)的更新速度是很快的。这样牺牲了时间换取了将CMList的空间复杂度降低到对数级别。
这样我们的协议中的tx_spend交易需要作部分修改。tx_spend交易包含如下两组数据：
- 某一枚币的序列号sn；
- 他知道这个一个r，满足COMM_r(sn)出现在根节点为rt的Merkle树的某个叶子节点的零知识证明pi。
这样，我们对于账本作了优化，取了时间和空间的一个平衡。