Merkle Tree
由Ralph Merkle在1970年代提出迎罗，它是絕對(duì)對(duì)稱的二叉樹結(jié)構(gòu)杠愧。每個(gè)葉子(leaf)是對(duì)應(yīng)數(shù)據(jù)的hash喳钟，其它的節(jié)點(diǎn)則是它的2個(gè)子節(jié)點(diǎn)合并后的hash值篮撑。[1]
當(dāng)遇到葉子數(shù)量不是2^n的時(shí)候减细，無(wú)法形成完全對(duì)稱的二叉樹結(jié)構(gòu)，即存在節(jié)點(diǎn)無(wú)法湊對(duì)的情況赢笨，這時(shí)候就和自己湊對(duì)未蝌。[2]
ABCDEEEE .......Merkle root
/ \
ABCD EEEE
/ \ /
AB CD EE .......E is paired with itself
/ \ / \ /
A B C D E .........Transactions
當(dāng)添加一個(gè)新葉子的時(shí)候，這個(gè)葉子從下到上的整個(gè)路徑都要重新計(jì)算hash茧妒。如果總?cè)~子數(shù)是n萧吠，那么就需要進(jìn)行roof(Log2(n))次計(jì)算。
Merkle Mountain Ranges(MMR)
最初由Peter Todd在2016年提出[3]桐筏，和Merkle Tree一樣纸型，葉子是一塊數(shù)據(jù)的hash，其它節(jié)點(diǎn)是子節(jié)點(diǎn)拼起來(lái)之后的hash。不同的是對(duì)非對(duì)稱二叉樹結(jié)構(gòu)的處理方式狰腌。它會(huì)在當(dāng)前葉子數(shù)量的條件下除破，盡量構(gòu)建對(duì)稱的二叉樹。
比如如果葉子數(shù)位14癌别，那么：
- 前8個(gè)葉子可以構(gòu)建一個(gè)深度為3的對(duì)稱二叉樹
- 剩余6個(gè)葉子皂岔，其中4個(gè)葉子可以構(gòu)建一個(gè)深度為2的對(duì)稱二叉樹
- 剩余2個(gè)葉子，可以構(gòu)建一個(gè)深度為1的對(duì)稱二叉樹
/\
/ \
/\ /\ /\
/\/\/\/\/\/\/\
形狀上就像是3座小山展姐，這也是MMR名字的由來(lái)躁垛。MMR root的計(jì)算方法是，將第一個(gè)小山的root hash和第二個(gè)小山的root hash拼接圾笨，計(jì)算得到hash教馆。然后在此基礎(chǔ)上，再和第3個(gè)小山進(jìn)行拼接擂达，計(jì)算得到hash土铺。[4]如果還有更多，就依次循環(huán)板鬓。
/\
/\ \
/ \ \
/\ \ \
/ \ \ \
/\ /\ /\ \
/\/\/\/\/\/\/\
將葉子數(shù)用二進(jìn)制表示悲敷，即1110。此時(shí)添加一個(gè)新葉子俭令，只需要進(jìn)行1次hash后德。
- 如果葉子數(shù)是1101101，添加新葉子需要進(jìn)行2次hash抄腔。
- 如果葉子數(shù)是1100111瓢湃，添加新葉子需要進(jìn)行4次hash。
- 如果葉子數(shù)是1011111赫蛇，添加新葉子需要進(jìn)行6次hash绵患。
計(jì)算規(guī)律是，最右側(cè)連續(xù)的小山數(shù)量+1悟耘。
如果用Merkle Tree落蝙，上述3種情況需要做的hash次數(shù)都是7次，即Log2(n)并向上取整暂幼。
對(duì)于MMR而言掘殴，最壞情況是所有的小山都是連續(xù)的，即葉子數(shù)為1111111的情況粟誓，添加新葉子需要進(jìn)行7次hash奏寨，和使用Merkle Tree一樣。
MMR被用于Grin[5]鹰服，同時(shí)也是Flyclient的基礎(chǔ)病瞳。
MMR可以通過(guò)遞歸實(shí)現(xiàn)[6]
-
https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md ?
-
https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py ?
-
https://github.com/mimblewimble/grin/blob/master/doc/mmr.md ?
-
FlyClient: Super-Light Clients for Cryptocurrencies https://eprint.iacr.org/2019/226.pdf ?
