實現 Merkle Patricia Trie

May 14, 2019

我目前正在嘗試使用 Python 3.6 實現乙太坊的 Merkle Patricia Trie，我遇到了一些麻煩，老實說我很沮喪。
我正在使用以下來源：
乙太坊維基帕特里夏樹
乙太坊中的默克林
了解乙太坊 Trie - 部落格
了解 Ethereum Trie - Github Python 程式碼
特里測試
我確實了解 Merkle Patricia Trie (MPT) 的概念及其工作原理。然而，我在實施它時遇到了問題。
首先，我想知道乙太坊 Witi中給出的範例 trie是否正確。我覺得不正確。
包含以下鍵/值對的 trie：('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'),('horse', 'stallion')
他們的結果：
rootHash: [ &lt;16&gt;, hashA ]
hashA:    [ &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, hashB, &lt;&gt;, &lt;&gt;, &lt;&gt;, hashC, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt; ]
hashC:    [ &lt;20 6f 72 73 65&gt;, 'stallion' ]
hashB:    [ &lt;00 6f&gt;, hashD ]
hashD:    [ &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, hashE, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, 'verb' ]
hashE:    [ &lt;17&gt;, hashF ]
hashF:    [ &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, hashG, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, 'puppy' ]
hashG:    [ &lt;35&gt;, 'coin' ]
我的結果：
rootHash: [ &lt;16&gt;, hashA ]
hashA:    [ &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, hashB, &lt;&gt;, &lt;&gt;, &lt;&gt;, [ &lt;20 6f 72 73 65&gt;, 'stallion' ], &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt; ]  
hashB:    [ &lt;00 6f&gt;, hashD ]
hashD:    [ &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, hashE, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, 'verb' ]
hashE:    [ &lt;17&gt;, [ &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, [ &lt;35&gt;, 'coin' ], &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, &lt;&gt;, '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) &gt;= 32 else x and 
rlp.encode is the RLP encoding function.
此外，我嘗試將我的程式碼的結果與JS MPT實現進行比較，這給出了完全不同的根雜湊。
我想知道，什麼是正確的？我誤解了這個例子嗎？還有其他“更好”的文件嗎？我很感激任何幫助。

好吧，在花了時間弄清楚它是如何工作的之後，我終於做到了。耶：D
我相信乙太坊 Wiki 中給出的例子是不正確的！我的程式碼生成我給定的結果並返回正確的雜湊！
如果您有興趣弄清楚它的工作原理，程式碼在 github 上（我仍然需要清理一下並再寫一些評論）。
在評論中，我還找到了一種使用測試案例中給出的十六進制值的方法。一切都在回購中:)
我將嘗試更新 Wiki 範例，這樣人們就不會像我之前那樣感到困惑……

引用自：https://ethereum.stackexchange.com/questions/70480

實現 Merkle Patricia Trie

相關問答

什麼是儲存和狀態嘗試？

乙太坊區塊架構

乙太坊交易樹是如何形成的

有效地在合約中儲存大量數據

乙太坊中的默克爾

向區塊鏈證明日誌的存在