区块链学习总结2

众所周知&＃xff0c;比特币作为区块链最早最成功的应用&＃xff0c;其不可篡改性和隐私保护性是基于哈希算法的。为了迎合哈希算法的使用&＃xff0c;Merkle-Tree应运而生。Merkle-Tree就是一颗将指针换为哈希指针的特殊的树。然而&＃xff0c;比特币的记录是基于交易的&＃xff0c;这样就不能很方便地查询某个时刻某节点的余额&＃xff08;balance&＃xff09;。虽然&＃xff0c;比特币中的全节点也维护一个UTXO&＃xff08;即未支出的交易&＃xff09;&＃xff0c;轻节点也可以向全节点查询UTXO中的内容从而得到某节点的余额。但是&＃xff0c;这耗费的成本和时间是不必要的&＃xff0c;同时也与我们的日常习惯相悖。

于是&＃xff0c;以太坊提出了基于账户的区块&＃xff0c;即以太坊中的区块体中是包括每一个区块的余额的。这时&＃xff0c;问题来了。我们是否还能采用比特币中的Merkle-Tree结构进行账户余额的存储呢&＃xff1f;后面我们将会揭晓。

比特币的数据结构

以上便是区块体中交易的存储结构。首先&＃xff0c;各个交易Di生成一个哈希值&＃xff0c;然后逐层向上两两合并&＃xff0c;最后得到一颗树结构。最后&＃xff0c;将树的根哈希值存放在区块头中作为所有交易的唯一标识。只要Merkle-Tree上的任何一笔交易被篡改&＃xff0c;对应的哈希也会逐层变更&＃xff0c;正所谓牵一发而动全身&＃xff0c;最后根哈希也会被改变。所以&＃xff0c;基于Merkle-Tree的数据结构是可以保证交易数据的不可篡改性的。其次&＃xff0c;在区块链网络中存在着许多轻节点&＃xff0c;即只存放区块链头信息的节点。那么当这些轻节点想检验某个交易是否被记录在区块上时&＃xff0c;它需要怎么做呢&＃xff1f;

难道它需要向节点请求下载树上的完整信息吗&＃xff1f;当然不是。它只需要全节点提供该交易到根的路径上其他有关生成哈希的必要哈希值&＃xff0c;通过沿着路径生成哈希&＃xff0c;最后轻节点会计算出一个根哈希值。最后只需要比较计算出的根哈希和区块上记录的根哈希是否一致&＃xff0c;若一致则说明该交易确实被记录在区块里&＃xff0c;否则则说明该交易不存在。

这样&＃xff0c;每个区块都把10分钟左右的交易记录在案&＃xff0c;所有交易都将可追溯。通过交易的验证&＃xff0c;双花问题就可以得到解决。通常&＃xff0c;在一笔交易中&＃xff0c;比如A需要向B支付10个比特币。那么A就得证明它在之前的区块中有得到一定量比特币的交易&＃xff0c;这个叫做output script。比如&＃xff0c;之前C向A支付了8个比特币&＃xff0c;D向A支付了5个比特币。这样A在给B转账的时候&＃xff0c;需要明确的指出C和D是曾经以一共给了他13个比特币的&＃xff0c;这样才能顺利完成交易。同时&＃xff0c;剩余的3个比特币需要A自己建立一个新的找零账户进行存储&＃xff0c;否则就会被矿工当成交易费拿走&＃xff08;doge&＃xff09;。

大家有没有觉得这样很麻烦&＃xff1f;每次给别人钱&＃xff0c;都得去证明自己手头上的钱是合法的。于是&＃xff0c;以太坊建立了基于账户的区块&＃xff0c;这样显式地记录某账户的余额&＃xff0c;就无需像比特币一般进行多次验证。

以太坊的数据结构

以太坊中的区块含有三棵树&＃xff0c;他们都采用同一个数据结构。这里对数据结构的决定起主要作用的当然就是状态树&＃xff08;state tree&＃xff09;&＃xff0c;也就是显示某个账户有多少余额的树。这里需要维护的好像就是一个(key,value)对&＃xff0c;key就是账户的地址&＃xff0c;而value就是余额&＃xff08;balance)。

那么&＃xff0c;不如试一下哈希表&＃xff1f;它的查询、更新速度很快。有什么问题呢&＃xff1f;如何生成根哈希呢&＃xff1f;所有哈希同时一起算出一个根哈希可行吗&＃xff1f;那么这就无法提供快速的Merkle-proof&＃xff0c;如果采用哈希表&＃xff0c;只有获得区块体中其余所有账户的哈希才能证明某个账户的余额是正确的。这对轻节点是十分不友好的。

那么&＃xff0c;可否采用比特币的Merkle-Tree依葫芦画瓢呢&＃xff1f;这里是不行的。我们需要认清比特币和以太坊的一个很大的区别。在比特币中&＃xff0c;被记录在Merkle-Tree上的交易都是有效交易&＃xff1b;但在以太坊中&＃xff0c;Merkle-Tree上记录的是全部节点的余额。但在一段时间中&＃xff0c;可能只有很少一部分账户的余额发生了变化&＃xff0c;这对存储造成了巨大的浪费。同时&＃xff0c;Merkle-Tree也没有快速查找和更新的方法&＃xff0c;也没有唯一性保证。

那么&＃xff0c;能不能只将当前发生余额变化的账户记录到Merkle-Tree上呢&＃xff1f;这个想法不错。但可惜&＃xff0c;仍然是不可行的。举个例子&＃xff0c;如果B要收取A一笔费用。B就需要从当前区块逐个向前寻找包含A账户余额的区块&＃xff0c;假若A很长一段时间没有参与交易&＃xff0c;那么对B而言就会造成巨大的时间成本。更有甚者&＃xff0c;如果A压根未出现过&＃xff0c;B就需要一直搜索到创始区块&＃xff08;genisis block&＃xff09;才能发现。

现在已经否决了hash table和Merkle- Tree了。我们再次进行升级——Sorted Merkle Tree。会排序的Merkle-Tree&＃xff0c;这就解决了快速查找和更新的问题。不幸的是&＃xff0c;SMT的插入成本是很大的&＃xff0c;它需要重构整颗树&＃xff0c;代价很大。

所以&＃xff0c;我们目前面临的一个情况是&＃xff0c;少量的账户的余额如何进行证明&＃xff1f;这里需要说明的是&＃xff0c;账户的地址是由40位的16进制组成&＃xff0c;地址之间是十分稀疏的。当然&＃xff0c;我们还是需要对所有节点的余额信息进行存储。

想想其他数据结构。既然地址的每一位都是0~f&＃xff0c;有没有一点思路&＃xff1f;没错&＃xff01;就是trie&＃xff0c;传说中的前缀树。它在这里简直合适不过了。其一&＃xff0c;它的查找效率取决于地址的长度&＃xff0c;这个我们都可以接受。其二&＃xff0c;无论输入顺序如何&＃xff0c;它的结构都是唯一的。其三&＃xff0c;如果更新局部信息&＃xff0c;只需沿着一条路径进行访问即可&＃xff0c;无需重构数据结构。

trie在这里看似已经不错了&＃xff0c;但其实还是有一定的缺陷。例如存在一定的存储浪费&＃xff0c;可能地址中间的某些信息对区分地址是无用的&＃xff0c;这就需要将其合并。这就引出了我们最终的结果&＃xff1a;Patricia tree&＃xff08;路径压缩trie&＃xff09;。再与哈希结合&＃xff0c;它就成了Merkle-Patricia-tree&＃xff0c;也就是MPT。

总结
比特币和以太坊的工作机制固然是空前的&＃xff0c;但我们不仅应该熟悉其工作原理&＃xff0c;更重要的是我们应该尝试去揣测整个思考过程。正是这种批判性思维&＃xff0c;使得区块链应用一步步趋于更加合理化。正是这种批判性思维&＃xff0c;推动着科技发展走向新的台阶&＃xff01;