HASH GAME - Online Skill Game GET 300

　　根据[6]中回答者所说，Merkle Tree的插入和删除操作其实是一个工程上的问题，不同问题会有不同的插入方法。如果要确保树是平衡的或者是树高是log(n)的，可以用任何的标准的平衡二叉树的模式，如AVL树，红黑树，伸展树，2-3树等。这些平衡二叉树的更新模式可以在O(lgn)时间内完成插入操作，并且能保证树高是O(lgn)的。那么很容易可以看出更新所有的Merkle Hash可以在O((lgn)2)时间内完成(对于每个节点如要更新从它到树根O(lgn)个节点，而为了满足树高的要求需要更新O(lgn)个节点)。如果仔细分析的话，更新所有的hash实际上可以在O(lgn)时间内完成，因为要改变的所有节点都是相关联的，即他们要不是都在从某个叶节点到树根的一条路径上，或者这种情况相近。

　　Merkle tree的树根并不表示树的深度。这可能会导致second-preimage attack，即攻击者创建一个具有相同Merkle树根的虚假文档。一个简单的解决方法在Certificate Transparency中定义：计算叶节点的hash时，在hash数据前加0x00。当计算内部节点时，在前面加0x01。通过在hash值前面加深度前缀。因此，前缀每一步会减少，只有当到达叶子时前缀依然为正，提取的hash链才被定义为有效。

　　在点对点网络中作数据传输的时候，我们会从同时从多个机器上下载数据，而且其中很多机器可以认为是不稳定或者是不可信的。实际中，点对点网络在传输数据的时候，其实都是把比较大的一个文件，切成小的数据块。这样的好处是，如果有一个小块数据在传输过程中损坏了，那我只要重新下载这一个数据块就行了，不用重新下载整个文件。这就要求每个数据块都拥有自己的哈希值。BT 下载的时候，在下载真正的数据之前，我们会先下载一个哈希列表的。那么多的哈希，我们怎么保证它们本身都是正确地呢？