实施Merkle Patricia Trie

Question

我目前正试图使用Python3.6实现Ethereum的，而且我遇到了一些麻烦，老实说，我很沮丧。

我使用的资料如下：

• 百合花帕特里夏树
• 以太默默无语
• [医] -博客了解Ethereum
• 理解Ethereum Github代码
• Trie试验

我确实了解(MPT)的概念以及它是如何工作的。然而，我在实施它时遇到了困难。

首先，我想知道trie在巫术中给出的例子是否正确。我觉得这是不对的。

包含以下键/值对的trie：('do', 'verb')、('dog', 'puppy')、('doge', 'coin')、('horse', 'stallion')

他们的结果：

rootHash: [ <16>, hashA ]
hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]
hashC:    [ <20 6f 72 73 65>, 'stallion' ]
hashB:    [ <00 6f>, hashD ]
hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE:    [ <17>, hashF ]
hashF:    [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]
hashG:    [ <35>, 'coin' ]

我的结果是：

rootHash: [ <16>, hashA ]
hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]  
hashB:    [ <00 6f>, hashD ]
hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

为什么看起来这么不一样？下面的例子是下面这句话：

When one node is referenced inside another node, what is included is 
H(rlp.encode(x)), where H(x) = sha3(x) if len(x) >= 32 else x and 
rlp.encode is the RLP encoding function.

此外，我尝试将我的代码的结果与JS MPT实现进行比较，这提供了一个完全不同的根哈希。

我在想，什么是正确的？我是否误解了这个例子？还有其他“更好”的文档吗？我很感谢你的帮助。

Answer 1

好吧，在花时间搞清楚它是怎么工作的之后，我终于做到了。Yay :D

我相信给出的例子是不对的！我的代码生成我给定的结果，它返回正确的哈希！

如果您感兴趣的是谁的工作，代码是在github (我仍然需要清理一点，并写一些更多的评论)。

在注释中，我还找到了一种方法来处理测试用例中给出的十六进制值。所有东西都在回购范围内:)

我将尝试更新Wiki的例子，这样人们就不会像我一样困惑。