待字閨中開發(fā)了一門區(qū)塊鏈方面的課程：《深入淺出ETH原理與智能合約開發(fā)》，馬良老師講授沙合。此簡書文集記錄我的學(xué)習(xí)筆記再愈。

課程共8節(jié)課榜苫。其中，前四課講ETH原理翎冲，后四課講智能合約垂睬。
第二課分為三部分：

1. 以太坊交易
2. MPT與RLP
3. MPT與RLP實(shí)驗(yàn)

這篇文章是第二課第二部分的學(xué)習(xí)筆記：MPT與RLP。

MPT抗悍，Merkle Patricia Tree驹饺，結(jié)合了Merkle Tree（默克爾樹）和 Patricia Tree（帕特里夏樹）的一種數(shù)據(jù)結(jié)構(gòu)。
RLP缴渊，Recursive Length Prefix赏壹，一種編碼方法。

這是兩個非常重要的數(shù)據(jù)結(jié)構(gòu)衔沼，在以太坊的區(qū)塊和交易中都有用到蝌借。

1、Merkle Tree/ Patricia Tree

先分別介紹一下Merkle Tree 和 Patricia Tree指蚁。

Merkle Tree 和 Patricia Tree

默克爾樹的解釋：對每一個交易計(jì)算其散列值（Hash）菩佑，再對兩個散列值求他們的散列值。如果是奇數(shù)個欣舵，就把最后一個重復(fù)一次擎鸠。最后得到的一個散列值就是默克爾樹根的值。如圖缘圈，交易1劣光、1、2糟把、3的散列值分別是HASH0绢涡、HASH1、HASH2遣疯、HASH3雄可。HASH0和HASH1結(jié)合在一起計(jì)算散列值得HASH01，HASH2和HASH3結(jié)合在一起計(jì)算散列值得HASH23，接下來HASH01数苫、HASH23結(jié)合在一起聪舒，計(jì)算散列值得HASH0123。

采用默克爾樹的好處是可以方便的判斷一個交易是否在區(qū)塊中虐急。

Patricia Tree箱残，可稱為壓縮前綴樹。如上圖右半部分止吁。相同的前綴在同一分支中被辑，后面一同的部分分叉出來，如test和toast敬惦，都有相同的t盼理，est和oast在兩個分支中。

這個結(jié)構(gòu)的好處是節(jié)省空間俄删，因?yàn)槊恳患壍逆I值可以是多個字符宏怔。

2、Merkle Patricia Tree 規(guī)格

了解了Merkle Tree 和 Patricia Tree后抗蠢，再來看這兩者混合后的產(chǎn)物——MPT举哟。
這里的原理知識單獨(dú)來看不易理解，和具體的例子結(jié)合起來才更容易理解迅矛，此處先放上課件截圖妨猩。在后面的例子中再做說明。

Merkle Patricia Tree 規(guī)格

3秽褒、RAW/HEX/HEX-Prefix的編碼標(biāo)準(zhǔn)

在MPT中壶硅，還涉及到三個小的編碼標(biāo)準(zhǔn)。主要規(guī)則如圖销斟。下面結(jié)合兩個例子說明一下庐椒。

三個編碼標(biāo)準(zhǔn)

HEX編碼的例子：從ASCII碼表中可以查出，b的十六進(jìn)制編碼為62蚂踊，o的十六進(jìn)制編碼為6F约谈，F(xiàn)在十六進(jìn)制中就是15的意思。因?yàn)檫@是個葉子節(jié)點(diǎn)犁钟，最后加上0x10表示結(jié)束棱诱，也就是16。所以最后的編碼為[6 2 6 15 6 2 16]

HEX-Prefix編碼的例子：[6 2 6 15 6 2 16]涝动，將其最后的0x10去掉迈勋，[6 2 6 15 6 2]。前面補(bǔ)一個四元組醋粟，其中（倒數(shù)）第0位是區(qū)分奇偶信息的靡菇，[6 2 6 15 6 2]是偶數(shù)位重归，第0位是0；第1位是區(qū)分節(jié)點(diǎn)類型的厦凤，這是葉子節(jié)點(diǎn)鼻吮，第1位是1。所以這個四元組就是0010是2泳唠”吠“如果輸入key的長度是偶數(shù)則再添加一個四元組0x0在flag四元組之后”啃龋”，所以勇垛，最終的前綴是0x20脖母。本例最終的結(jié)果，[32 98 111 98]闲孤，即[0x20, 0x62, 0x6F, 0x62]

4谆级、Merkle Patricia Tree 的例子

下面是綜合性的例子，通過它可以很方便地理解前面的理論知識讼积。值得多看幾篇肥照，仔細(xì)休會。

初始的key-value對為：

(<64 6f>”do” : 'verb')
(<64 6f 67> “dog”: 'puppy')
(<64 6f 67 65> “doge”: 'coin')
(<68 6f 72 73 65> “horse”: 'stallion')

其中勤众，<>中的數(shù)據(jù)為key的16進(jìn)制編碼舆绎。

MPT.jpg

1. 第一個框，綠色们颜，根節(jié)點(diǎn)

因?yàn)?組數(shù)據(jù)都有公共的6吕朵，所以這個節(jié)點(diǎn)的值為6，長度為1窥突，奇數(shù)努溃；節(jié)點(diǎn)類型：擴(kuò)展節(jié)點(diǎn)；所以前綴就是0001阻问，即1梧税。

這是個擴(kuò)展節(jié)點(diǎn)，它的值是一個Hashvalue称近，它指向一個分支節(jié)點(diǎn)第队。Hashvalue，具體指的是分支節(jié)點(diǎn)RLP編碼的結(jié)果的散列值煌茬。（RLP見下小節(jié)）

2. 第二個框斥铺，藍(lán)色

分支節(jié)點(diǎn)。上面4組數(shù)據(jù)的第2位是4和8兩種情況坛善。在4的位置上存的是下面的擴(kuò)展節(jié)點(diǎn)的散列值晾蜘，在8的位置上存的是下面的葉子節(jié)點(diǎn)的散列值邻眷。

3. 第三個框，粉色

葉子節(jié)點(diǎn)剔交。以68開頭的只有一個了肆饶。所以這個節(jié)點(diǎn)上的四元組就是6f727365了。它是偶數(shù)位岖常。前綴是0x20（同前文HEX-Prefix編碼的例子）驯镊。這個葉子節(jié)點(diǎn)的value值為'stallion'。

4. 第四個框竭鞍，橙色

擴(kuò)展節(jié)點(diǎn)板惑。在64之后，公共的部分是6f偎快，這個擴(kuò)展節(jié)點(diǎn)的key即為6f冯乘，前綴為0000，即00晒夹。這個擴(kuò)展節(jié)點(diǎn)的value存放的是一個hashvalue裆馒，指向下一個節(jié)點(diǎn)，一個分支節(jié)點(diǎn)丐怯。

5. 第五個框喷好，藍(lán)色

分支節(jié)點(diǎn)。646f已經(jīng)表達(dá)完读跷，這個節(jié)點(diǎn)的value值就是646f對應(yīng)的值梗搅，'verb'。

除此之外舔亭，646f之后就是6些膨，所以在這個分支節(jié)點(diǎn)的6位置上有一個散列值，指向下一個節(jié)點(diǎn)钦铺。

6. 第六個框订雾，橙色

擴(kuò)展節(jié)點(diǎn)。在646f6之后矛洞，公共的部分是7洼哎，其長度為1，奇數(shù)沼本。所以前綴為0001噩峦。這個節(jié)點(diǎn)的value是一個散列值，指向下一個節(jié)點(diǎn)抽兆。

7. 第七個框识补，藍(lán)色

分支節(jié)點(diǎn)。646f67已經(jīng)表達(dá)完辫红，這個節(jié)點(diǎn)的value值就是646f67對應(yīng)的值凭涂，'puppy'祝辣。

除此之外，646f67之后就是6切油，所以在這個分支節(jié)點(diǎn)的6位置上有一個散列值蝙斜，指向下一個節(jié)點(diǎn)。

8. 第8個框澎胡，粉色

葉子節(jié)點(diǎn)孕荠。key為5，value為'coin'攻谁。長度為1稚伍，奇數(shù)，前綴0011巢株，即3槐瑞。

整個分析過程結(jié)束「蟀可結(jié)合上圖和前文的理論多加復(fù)習(xí)。

5祠挫、RLP的編碼標(biāo)準(zhǔn)

這小節(jié)也是理論性較強(qiáng)那槽，通過例子可以方便理解。先放上課件等舔，再根據(jù)我的理解舉更多的例子骚灸。同樣，學(xué)習(xí)方法也是理論和例子配合學(xué)習(xí)慌植。其中甚牲，list的例子在下篇文章的上機(jī)實(shí)驗(yàn)部分再列舉。

RLP的編碼標(biāo)準(zhǔn)

再舉幾個例子

不足之處請指教蝶柿，謝謝丈钙。