Merkle Tree 實現(xiàn)細(xì)節(jié)及（不）存在性證明

Merkle Tree in BitCoin & BitCoin Cash

20181112

Merkel Tree是Bitcoin的核心組件，其相關(guān)資料已經(jīng)非常豐富，所以本文檔偏重于介紹Merkle Tree的存在性證明與不存在性證明，并且鋪墊一下Merkle Tree在Bitcoin中起的作用和開發(fā)中容易被忽視的一些細(xì)節(jié)。

Merkle Trees in Bitcoin

Merkle trees是以它的創(chuàng)造者 Ralph Merkle命名的。在Bitcoin的白皮書中得知，Merkle Trees的引入是將一個區(qū)塊中所有的交易進(jìn)行整合生成然后整個交易集合的數(shù)字指紋，從而確保的BTC不可篡改性。說一下自己理解的不可篡改性：

image

Bitcoin 借用Merkle Trees的結(jié)構(gòu)從而實現(xiàn)了僅僅 256-bit 的Merkle Root即可“看管”住近1M的交易信息（BCH 為 32M）。一旦被篡改，立刻反映到塊頭，從而當(dāng)前塊以及當(dāng)前塊之后的每一塊都要受到影響，并且這個”改變”貌似對你沒有任何好處，因為比特幣的非對稱加密機(jī)制可以阻止你盜竊別人的比特幣, 你只能開一條不被其他礦場認(rèn)可的新鏈。這樣的話即使你擁有巨大的算力，如果你稍微有理性的,你就不會去篡改比特幣區(qū)塊鏈, 所以說比特幣從技術(shù)和動機(jī)兩個方面打消了別人篡改比特幣數(shù)據(jù)的念頭。

比特幣系統(tǒng)中的 Merkle Tree的計算其實包含有一些很隱晦的細(xì)節(jié)，這些細(xì)節(jié)很重要，它們會影響到整個計算結(jié)果的正確性, 在Bitcoin Wiki 中 ‘Protocol_documentation’提到過：

Note: Hashes in Merkle Tree displayed in the Block Explorer are of little-endian notation. For some implementations and calculations, the bytes need to be reversed before they are hashed, and again after the hashing operation.

Hashes以小端的形式（byte數(shù)組）進(jìn)行hash運(yùn)算，以大端形式（Hash值）展示給人看。

gcash中源碼中hash.go存在相應(yīng)佐證：

hash, err := chainhash.NewHashFromStr(str)

// NewHashFromStr creates a Hash from a hash string.  The string should be
// the hexadecimal string of a byte-reversed hash, but any missing characters
// result in zero padding at the end of the Hash.
func NewHashFromStr(hash string) (*Hash, error) {
    ret := new(Hash)
    err := Decode(ret, hash)
    if err != nil {
        return nil, err
    }
    return ret, nil
}

// Decode decodes the byte-reversed hexadecimal string encoding of a Hash to a
// destination.
func Decode(dst *Hash, src string) error {
    // Return error if hash string is too long.
    if len(src) > MaxHashStringSize {
        return ErrHashStrSize
    }

    // Hex decoder expects the hash to be a multiple of two.  When not, pad
    // with a leading zero.
    var srcBytes []byte
    if len(src)%2 == 0 {
        srcBytes = []byte(src)
    } else {
        srcBytes = make([]byte, 1+len(src))
        srcBytes[0] = '0'
        copy(srcBytes[1:], src)
    }

    // Hex decode the source bytes to a temporary destination.
    var reversedHash Hash
    _, err := hex.Decode(reversedHash[HashSize-hex.DecodedLen(len(srcBytes)):], srcBytes)
    if err != nil {
        return err
    }

    // Reverse copy from the temporary hash to destination.  Because the
    // temporary was zeroed, the written result will be correctly padded.
    for i, b := range reversedHash[:HashSize/2] {
        dst[i], dst[HashSize-1-i] = reversedHash[HashSize-1-i], b
    }

    return nil
}

newHash := HashMerkleBranches(hash1, hash2)

func HashMerkleBranches(left *chainhash.Hash, right *chainhash.Hash) *chainhash.Hash {
    // Concatenate the left and right nodes.
    var hash [chainhash.HashSize * 2]byte
    copy(hash[:chainhash.HashSize], left[:])
    copy(hash[chainhash.HashSize:], right[:])

    newHash := chainhash.DoubleHashH(hash[:])
    return &newHash
}

用圖可以更直觀理解來這些Merkle Tree的計算過程隱晦的細(xì)節(jié)：

含一筆交易的Merkle樹計算

image

image

image

Merkle Trees Inclusive Verification

Merkle Trees除了不可篡改性起重要作用，也提供了SPV（Simplified Payment Verification）節(jié)點(diǎn)即使不用全部下載交易信息也能驗證交易的方案。
在bitcoin wiki 中這樣解釋SPV的：

As noted in Nakamoto's whitepaper, it is possible to verify bitcoin payments without running a full network node. And this is called simplified payment verification or SPV. A user or user’s bitcoin spv wallet only needs a copy of the block headers of the longest chain, which are available by querying network nodes until it is apparent that the longest chain has been obtained. Then, wallet using spv client get the Merkle branch linking the transaction to its block. Linking the transaction to a place in the active chain demonstrates that a network node has accepted it, and blocks added after it further establish the confirmation.hain headers connect together correctly and that the difficulty is high enough

簡單地來說 SPV 節(jié)點(diǎn)并不會下載全部的區(qū)塊鏈數(shù)據(jù)，而只是下載塊頭，這條鏈并不包括交易數(shù)據(jù). 當(dāng)前的某個時刻比特幣區(qū)塊鏈的高度是 550387, 一個區(qū)塊頭的大小是 80 個字節(jié), 那么由區(qū)塊頭組成的鏈的大小大概是 42 M, 這和整個區(qū)塊鏈動輒上幾百 G 的數(shù)據(jù)相比少了很多很多。

交易驗證而言，SPV節(jié)點(diǎn)不會所有交易都去驗證，它只對沒有驗證的與它相關(guān)的交易進(jìn)行驗證，于是SPV節(jié)點(diǎn)會設(shè)置一個filter只去接受匹配它設(shè)置的fliter的交易。比如：
SPV接收到一筆錢，并不能確認(rèn)這個交易是否合法，因此要對這個交易的輸入進(jìn)行驗證。SPV要拿著這個交易的信息向網(wǎng)絡(luò)發(fā)起查詢請求getdata（用MSG_MERKLEBLOCK標(biāo)示），這個請求的響應(yīng)被稱為merkle block message。
當(dāng)有全節(jié)點(diǎn)收到這個MSG_MERKLEBLOCK請求之后，利用傳過來的交易信息在自己的區(qū)塊鏈數(shù)據(jù)庫中進(jìn)行查詢，并把驗證路徑返回給請求源，SPV節(jié)點(diǎn)拿到驗證路徑之后，再做一次merkle校驗，

驗證過程分兩階段：

  1. 驗證transaction是否在相應(yīng)的block里（驗證tx～block，即本文Merkle Trees Inclusive Verification）
  2. 驗證該block后是否在主鏈上，并且等待到其后是鏈上了6個或6個以上block才認(rèn)為其不會被回滾掉（驗證block～主鏈最長鏈block chain）。

確認(rèn)無誤之后，就認(rèn)為這個交易是可信的。

這里我們假設(shè)這個全節(jié)點(diǎn)是誠實節(jié)點(diǎn)（實際上在p2p網(wǎng)絡(luò)中，不可以相信任何節(jié)點(diǎn)），這里假設(shè)是為了解釋后面存在性證明。

存在性證明的第一步就是解析merkle block message。所以我們先看一下SPV節(jié)點(diǎn)接收到的merkle block message：
摘自Bitcoin Developer Reference 的 Merkle Block Message部分

The merkleblock message is a reply to a getdata message which requested a block using the inventory type MSG_MERKLEBLOCK. It is only part of the reply: if any matching transactions are found, they will be sent separately as tx messages.
If a filter has been previously set with the filterload message, the merkleblock message will contain the TXIDs of any transactions in the requested block that matched the filter, as well as any parts of the block’s merkle tree necessary to connect those transactions to the block header’s merkle root. The message also contains a complete copy of the block header to allow the client to hash it and confirm its proof of work.

解析之后 結(jié)果如下：

01000000 ........................... Block version: 1
82bb869cf3a793432a66e826e05a6fc3
7469f8efb7421dc88067010000000000 ... Hash of previous block's header
7f16c5962e8bd963659c793ce370d95f
093bc7e367117b3c30c1f8fdd0d97287 ... Merkle root
76381b4d ........................... Time: 1293629558
4c86041b ........................... nBits: 0x04864c * 256**(0x1b-3)
554b8529 ........................... Nonce

07000000 ........................... Transaction count: 7
04 ................................. Hash count: 4

3612262624047ee87660be1a707519a4
43b1c1ce3d248cbfc6c15870f6c5daa2 ... Hash #1
019f5b01d4195ecbc9398fbf3c3b1fa9
bb3183301d7a1fb3bd174fcfa40a2b65 ... Hash #2
41ed70551dd7e841883ab8f0b16bf041
76b7d1480e4f0af9f3d4c3595768d068 ... Hash #3
20d2a7bc994987302e5b1ac80fc425fe
25f8b63169ea78e68fbaaefa59379bbf ... Hash #4

01 ................................. Flag bytes: 1
1d ................................. Flags: 1 0 1 1 1 0 0 0

Mercle Block Message包含，塊頭全部信息，交易個數(shù)，以及用于生成Merkle Proof的Hash值列表和Flag值列表。

接下來SPV可以根據(jù)交易個數(shù)得出 Merkle Tree的大小（不用真正意義上的建立一個MerkleTree，而是通過Merkle Tree 的SIZE 從而推導(dǎo)出 Merkle Path里節(jié)點(diǎn)間聯(lián)系），根據(jù)Hash列表以及 Flags列表確定目標(biāo)交易及它到Merkle Root的路徑。
具體流程可以參考下圖：

image
圖中Flag多出的一個0是為了湊夠字節(jié)于是在最后加了一個0

Flag操作含義：


image

最后如何衡量我們指定的Block都是否包含目標(biāo)交易？有以下條件：

if you find a node whose left and right children both have the same hash, fail. This is related to CVE-2012-2459.

If you run out of flags or hashes before that condition is reached, fail. Then perform the following checks (order doesn’t matter):

  • Fail if there are unused hashes in the hashes list.
  • Fail if there are unused flag bits—except for the minimum number of bits necessary to pad up to the next full byte.
  • Fail if the hash of the merkle root node is not identical to the merkle root in the block header.
  • Fail if the block header is invalid. Remember to ensure that the hash of the header is less than or equal to the target threshold encoded by the nBits header field. Your program should also, of course, attempt to ensure the header belongs to the best block chain and that the user knows how many confirmations this block has.

可以分成兩個階段，在構(gòu)建過程中：

  • 如果某個Node的左右節(jié)點(diǎn)的hash相同，則返回 fail；

    簡單來說：為了防止重復(fù)交易設(shè)置的，spv會去檢查最后兩個節(jié)點(diǎn)的hash值是否相同，如果相同則返回錯誤。具體解釋可以參考博士論文：on the application of hash function in bitcoin
    之前有過一個存疑點(diǎn)：全節(jié)點(diǎn)在構(gòu)建merkle tree的時候，對待“落單”的節(jié)點(diǎn)會copy然后以MerkleBlockMessage發(fā)過來，這種情況會不會與上述的判斷條件矛盾？
    回答：不會，主要原因：交易總數(shù)限制著。具體在不存在性證明部分進(jìn)行解釋（涉及全節(jié)點(diǎn)生成MerkleBlockMessage邏輯）。

  • 如果在還沒能得出Merkle Root的情況下，F(xiàn)lag或者Hash已使用完，則返回 fail。

構(gòu)建完畢之后：

  • 如果hash列表中還有沒有使用到的hash值，返回 fail；
  • 如果flag列表中還有沒有使用到的flag值，返回 fail，除非為了滿足最低flag個數(shù)標(biāo)準(zhǔn)從而填充的0（如上圖）；
  • 本地生成的Merkle root用于和塊頭中的Merkle root不相同，返回 fail；
  • 如果塊頭不合法（PoW的值大于Target），返回 fail；

根據(jù)Merkle path進(jìn)行存在性證明的PoC代碼如下：

const HashSize = 32


func main() {
    var nodeshash []*chainhash.Hash
//[h1 h2 h3 h4 h12 h34 root]
    var hashstrings = []string{
        "8c14f0db3df150123e6f3dbbf30f8b955a8249b62ac1d1ff16284aefa3d06d87",
        "fff2525b8931402dd09222c50775608f75787bd2b87e56995a7bdd30f79702c4",
        "6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4",
        "e9a66845e05d5abc0ad04ec80f774a7e585c6e8db975962d069a522137b80c1d",
        "ccdafb73d8dcd0173d5d5c3c9a0770d0b3953db889dab99ef05b1907518cb815",
        "8e30899078ca1813be036a073bbf80b86cdddde1c96e9e9c99e9e3782df4ae49",
        "f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766",
    }

     root,err := chainhash.NewHashFromStr("f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766")
    if err != nil {
        fmt.Printf("wrong" )
        return
    }

    for _ , item := range hashstrings{
        hash, err := chainhash.NewHashFromStr(item)
        if err != nil {
            fmt.Printf("wrong2+%s",item )
            return
        }
        nodeshash = append(nodeshash, hash)
    }
    result := merklerootinclusive(nodeshash,2,root)

    fmt.Printf("result: %t" ,result)

}

func merklerootinclusive(nodeshash []*chainhash.Hash,index int,root *chainhash.Hash) bool{
    length := len(nodeshash)
    if length<index {
        fmt.Printf("sssss%d" ,len(nodeshash))
        return false
    }



    for cur := index; cur < length-1;  {
        if cur%2 == 0 {//left
            neigh := nodeshash[cur + 1];
            nodeshash[length - (length -1 - cur)/2] = HashMerkleBranches(nodeshash[cur],neigh);//left,right
            cur = length - (length -1 - cur)/2
        }else {//right
            neigh := nodeshash[cur - 1]
            nodeshash[length  - (length-cur)/2] = HashMerkleBranches(neigh,nodeshash[cur]);
            cur = length - 1 - (length-cur-2)/2
        }
        fmt.Printf("%d vs %s \n" ,cur, nodeshash[cur].String())
    }


    if root.String() == nodeshash[length-1].String(){
        return true;
    }

    fmt.Printf("result %s vs root %s\n" ,nodeshash[length-1].String(),root.String())
    return  false;
}

func HashMerkleBranches(left *chainhash.Hash, right *chainhash.Hash) *chainhash.Hash {
    // Concatenate the left and right nodes.
    var hash [chainhash.HashSize * 2]byte
    copy(hash[:chainhash.HashSize], left[:])
    copy(hash[chainhash.HashSize:], right[:])

    newHash := chainhash.DoubleHashH(hash[:])
    return &newHash
}

程序用例，比如查找的tx是6359f0868171b1d194cbee1af2f16ea598ae8fad666d9b012c8ed2b79a236ec4，
計算出來的ancients的hash：index為5和6的節(jié)點(diǎn)。其中index為6的節(jié)點(diǎn)即為我們算出來的merkle root節(jié)點(diǎn)，值與塊頭中的root相等，存在性證明通過。


image

Merkle Trees Exclusive Verification（Non-membership Proofs）(TODO 用圖展示 IDEA)

Merkle Tree不存在性證明是最近一個熱門話題，其實相關(guān)資料并沒有很多。而最近提的很多是因為11月15日BCH再一次的硬分叉，這一次分叉中有一個重要內(nèi)容 規(guī)范交易排序：除了coinbase交易之外，區(qū)塊內(nèi)的交易必須按交易 id的數(shù)字（大端表示）升序排序，在Merkle Tree中它們會被解釋為256位的小端整數(shù)（little endian integers）。coinbase交易必須是一個區(qū)塊當(dāng)中的第一筆交易。

有了這個規(guī)范交易排序，之前一直被社區(qū)討論的的不存在證明的方案之一：基于排序交易的不存在性證明，有望更進(jìn)一步發(fā)展。

不存在性證明的意義是什么？倘若SPV請求的目標(biāo)交易并不在相應(yīng)的塊中，全節(jié)點(diǎn)應(yīng)該怎么證明該目標(biāo)交易并不在塊的交易列表中呢？如果全部交易發(fā)過去讓SPV節(jié)點(diǎn)一個個遍歷比對，對于大區(qū)塊結(jié)構(gòu)區(qū)塊而言，這種方案效率非常低。所以基于排序交易的不存在性證明的idea是：，先讓目標(biāo)交易與Coinbase交易比對，如果不相等，再去與排序后的交易中比對，找到最大的小于目標(biāo)交易的交易，記為pre，最小的大于目標(biāo)交易的交易，記為next。通過證明pre與next在排序后交易列表里位置相鄰（中間不存在其他節(jié)點(diǎn)），并且都可以驗證其在相應(yīng)的block中（即有Merkle Tree Inclusive Verifacation），從而可證明目標(biāo)交易并不在block的交易列表中。

image

不存在性證明具體方案是本人參考github上別人的idea：Sorted merkle tree as solution to issue #693設(shè)計的：通過生成pre 與 next 節(jié)點(diǎn)用于存在性證明的MerkleBlock Message來實現(xiàn)不存在性證明。
本方案設(shè)計原因有兩個：

  1. 比對pre與next的MerkleBlock Message里的Merkle Root從而確定他們都在同一個塊的交易列表中。
  2. 在Merkle Tree Inclusive Verifacation過程中，我們不僅可以確認(rèn)兩者的存在性，而且可以鎖定pre（或next）交易在Merkle Tree TXID Nodes中的位置，由于Merkle Tree TXID Nodes與block中交易列表的位置一一對應(yīng)，根據(jù)對比pre 與 next 在同一棵Merkle Tree 中 TXID Nodes的Index可以確定pre 與 next是相鄰的。

全節(jié)點(diǎn)生成 MerkleBlock Message的過程可以參考下圖：


image

展示這個圖也是為了證明我們確實可以通過給出MerkleBlock Message來鎖定pre（或next）交易在Merkle Tree TXID Nodes中的位置。

基于排序交易的不存在性證明的PoC代碼如下

const HashSize = 32

func main() {
    var nodeshash []*chainhash.Hash
    //sortedtxhash ：[coinbase tx,small ....  big]
    var hashstrings = []string{
        "a40d79679a8f2d532ece4a3fa4b382470810037ddf36814989732d65e30a926d",
        "0ba507f50b62ecfacf9c64681231bdb3ae154f9cab0bbd61abba0c6b5341a16c",
        "2cdcefb08d10d59f81401f3a492c2c8e9929088245111cc4ce6a56b5617bdad9",
        "37a99f006f115afad21a03b7d6f3568d9f3c5d487c9ccc17476baf472e17ec1d",
        "3aa5297e0318275910d82c17d6b25313e0dc73875bff3f0f2597fc2eb61ed5dd",
        "548dbb1ef032c8e1a72e7f8a56ce89c8da37aff930a6430738badef2303b5c60",
        "584bd7e5e5efcff0db5beffbdde252f60d3c4c12550a9dd15e0d03f047feea67",
        "6307ac1a59a635fcdf82953f8a55df6062eed7ebb32e189586281d352766cb17",
        "668d8d9dc1b168bf401b83a150c97d358c9fd6f43a32dd8148afc4979dbd81a4",
        "68f68945ad4bbbc1572963119ead4436ccbc33312f26fb05f61ae1673b21b103",
        "89b0b1a4d5f907d378543cee4106df480f713a54c5545232e44cc346562cbf30",
        "c76d38a803601c93bc7f07023fef7c7a151b5b7991451dbcc76201a74a240c5f",
        "cd71afaa322db432aa80031d571364548e6c4d56efb34dbde24fcc2e9b6f97bc",
        "d51ffcb68bb8b673286a9693c03f29bf8c62d23cd3ce0c0752a9b61668ca4275",
        "df24734cafbe5cf8f07749a1007ea703f0deaedf850a93ed7f7b85f5a8b3ceb3",
        "e7e011c98726aec33b9929020f279d3c716185ebd9160cee5a721a06b8225605",

    }

    targettx,err := chainhash.NewHashFromStr("6f7c8a6a2ed308074bf5078fd141e66e7d3440ec348ddd38c9ec7882f7960e64")
    if err != nil {
        fmt.Printf("wrong" )
        return
    }

    for _ , item := range hashstrings{
        hash, err := chainhash.NewHashFromStr(item)
        if err != nil {
            fmt.Printf("wrong2+%s",item )
            return
        }

        nodeshash = append(nodeshash, hash)
    }
    merklerootexclusive(nodeshash,targettx)
}


func merklerootexclusive(sortedtxhash []*chainhash.Hash,targettxhash *chainhash.Hash)  {//已確認(rèn)target不在txs里，merkle樹已構(gòu)造出，給出不存在性證明
    length := len(sortedtxhash)
    targettxhash = reverseHash(targettxhash)

    index := 1
    slice := 0
    for  ; index < length  ; {
        cur := reverseHash(sortedtxhash[index])
        if targettxhash[slice] > cur[slice] {
            index++
            slice = 0
            continue
        }else if targettxhash[slice] == cur[slice] {
            slice ++
            continue
        }else {
            if index == 1 {
                //next = sortedtxhash[0]
                fmt.Printf("mintx : %s vs \ntarget : %s \n",reverseHash(cur).String(),reverseHash(targettxhash).String())//最小tx>目標(biāo)交易
                minproof(length,1)//給出cur的proof路徑及hash，并鎖定cur指向最小tx
                return
            }else {
            fmt.Printf("pretx : %s <\ntargettx : %s <\nnexttx : %s \n",sortedtxhash[index-1].String(),targettxhash.String(),sortedtxhash[index])//最大tx<目標(biāo)交易
            normalproof(length,index-1,index)//給出pre，next的proof路徑及hash，spv根據(jù)生成的merkle路徑定位可知pre與next相鄰
            return
            }
        }
    }
    fmt.Printf("maxtx : %s vs \ntarget : %s \n",sortedtxhash[length-1],reverseHash(targettxhash).String())//最大tx<目標(biāo)交易
    maxproof(length,length-1);//給出cur的proof路徑及hash，鎖定cur指向最大tx
    return


}
func minproof(txsum int , targetindex int)  {
    var flag string
    flag = buildflags(txsum,targetindex)

    fmt.Printf("minflag : %s" ,flag)
}

func maxproof(txsum int , targetindex int)  {
    var flag string
    flag = buildflags(txsum,targetindex)

    fmt.Printf("maxflag : %s" ,flag)
}

func normalproof(txsum int , preindex int, nextindex int)  {
    preflag := buildflags(txsum,preindex)
    nextflag := buildflags(txsum,nextindex)

    fmt.Printf("preflag : %s\n" ,preflag)
    fmt.Printf("nextflag : %s" ,nextflag)

}

func buildflags(txsum int , targetindex int) string {

    hash := list.New()
    nodeslength := txsum * 2-1
    var substr string
    for cur:=targetindex;cur < nodeslength-1; {
        if cur%2 == 0 {
            substr = "1"+substr+"0"
            if cur == targetindex{
                hash.PushFront(cur)
                hash.PushBack(cur + 1)
            }else {
                hash.PushBack(cur+1)
            }
        }else {
            substr = "01"+substr
            if cur == targetindex{
                hash.PushFront(cur)
                hash.PushFront(cur - 1)
            }else {
                hash.PushFront(cur-1)
            }
        }
        cur=nodeslength - (nodeslength - cur - (cur+1)%2)/2
    }
    fmt.Print("hash list of ", targetindex," :")
    for e := hash.Front(); e != nil; e = e.Next() {
        fmt.Print(" ",e.Value, ";")
    }
    fmt.Print("\n")
    //fmt.Printf("flag : %s",substr)
    return "1"+substr//root 節(jié)點(diǎn)

}

func reverseHash(hash *chainhash.Hash) *chainhash.Hash {

    for i := 0; i < HashSize/2; i++ {
        hash[i], hash[HashSize-1-i] = hash[HashSize-1-i], hash[i]
    }

    return hash
}

程序用例，比如查找的tx是
"6f7c8a6a2ed308074bf5078fd141e66e7d3440ec348ddd38c9ec7882f7960e64"，交易列表“hashstrings”中不存在，返回兩筆相鄰交易的存在性證明：
pre：“68f68945ad4bbbc1572963119ead4436ccbc33312f26fb05f61ae1673b21b103”
和
next：“89b0b1a4d5f907d378543cee4106df480f713a54c5545232e44cc346562cbf30”


image

圖中的pre 與 next是用小端法表示的，以及Hash列表和Flag列表。Hash 列表簡化成了相應(yīng)Node在Merkle Tree中對應(yīng)的index值。


image

回答之前問題：


image

To be Continued

其實Merkle Tree被廣泛運(yùn)用于區(qū)塊鏈中，雖然在Bitcoin中是二叉樹的結(jié)構(gòu)，其實merkle tree也不一定是二叉樹，可以是任意樹結(jié)構(gòu)，也可以有很多變種，比如Plasma Cash用來存儲關(guān)于存儲資產(chǎn)的信息的Sparse Merkle Tree，而在以太坊中用于存儲信息的是“Merkle Patricia Tree”，等等等等?？傊?，Authenticated Data Structure調(diào)研之道陡峭且漫長，后會有期～

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Merkle Tree概念 Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的...
    dtdh閱讀 1,126評論 2贊 3
  • 轉(zhuǎn)載于：風(fēng)之舞555 Merkle Tree學(xué)習(xí) /最近在看Ethereum，其中一個重要的概念是Merkle T...
    Venture_Mark閱讀 574評論 0贊 0
  • 原文：https://blog.ethereum.org/2016/02/17/smart-contracts-c...
    orcl_zhang閱讀 1,196評論 2贊 49
  • 沒有一扇窗能讓你不絕望，看一看花之世界原來像夢一場。 有人哭，有人笑，有人輸有人老到...
    夢幻如泡影閱讀 524評論 0贊 0
  • 文/明光 村子里有好多狗，鄰家大媽說，只有我家的狗最漂亮。我也是這么認(rèn)為的。我家的小狗就象七八歲的小帥哥，是狗族里...
    明光照耀閱讀 371評論 0贊 0

友情鏈接更多精彩內(nèi)容