對於做開發的技術人員來說，理論上正確、實務上不可行的想法就只是空談，今天來介紹比特幣論文中為了提昇運作效率所使用的資料結構-Merkle Tree。

Merkle Tree

Merkle Tree是一種樹狀結構，其中leaf是根據hash function得來的hash值，之後往上的每個node就是將下面的node hash相加再做hash一直傳到root為止。

比特幣論文中的Merkle Tree運作示意圖:

來用套件練習一下:

sudo pip install merkletools

# -*- coding: utf-8 -*-
import merkletools

mt = MerkleTools(hash_type="SHA256")

Txs = ['Sam get $100 by POW', 'Tim give Jimmy $100', 'Johb give Jimmy $100', 'Jimmy give Tom $100']

mt.add_leaf(Txs)
mt.make_tree()

print(mt.get_merkle_root())
# root hash 值 header只需保留該值加入block計算POW的過程
# 3205666be9ffd95d6c6f6b507bd28c4d0d8e5f382a2403b233780cb6f1e67232

在github放有完整的範例程式提供，可以直接執行參考。

在論文中使用Merkle Tree的重點在於每個Transaction用hash一層一層往上傳，最後只需要留下root的hash存進Block Header中，這樣在之前提到的挖礦(計算POW)過程中就只需要包含root的hash就能將所有交易資訊都hash進來了。

如下圖所示，Transaction 3進來的時候，就算把之前0~2Transaction的資訊丟掉了或先不去管也沒關西，只要hash留著就可以算出最後要加進header的hash了。

中本聰在論文中的假設是這樣的:

A block header with no transactions would be about 80 bytes.
If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem even if the block headers must be kept in memory.

簡單來說他認為如果只考慮header，那麼每年只會增加約4.2MB的資料，根據摩爾定律的預測這點資料對記憶體增長來說不是問題，但是如果是要當挖礦(計算POW)的節點的話，還是把過去的所有交易資料存起來做追蹤比較保險，不然好不容易算到合法區塊才去跟別的節點要歷史交易資料追蹤確認就來不及了。

事實上目前比特幣的每個產出區塊的大小約在1MB左右，6 * 24 * 365 = 52560，也就是照目前的交易量把每個節點都塞滿的情況，每年會有將近50G的數據加入帳本中，目前的比特幣挖礦真不是一般人玩的起的。但既然挖礦的節點不好丟掉過去的交易資料，那Merkle Tree這種設計還有太大價值嗎?

有的，只做交易不挖礦就行了。

簡化交易驗證

如果今天只是想要用比特幣進行交易，而不是挖礦的話，只要用對方公鑰跟自己的公、私鑰進行交易後發到網路上，接著確定自己跟當前的比特幣網路同步到最長的區塊鏈，在利用timestamp查詢自己的交易有沒有成功被紀錄即可。

如下圖所示，除了Tx3的完整資訊，其餘只存header的資訊。

實務上大致對應所謂的比特幣熱錢包，熱錢包會跟目前網路上的比特幣網路進行同步，但可以選擇只儲存還未被交易過的transaction相關紀錄即可，這樣只需要約2、3G左右的資料量。

閱讀推薦

今天的最後推薦一本介紹比特幣技術與生態系的好書:
Master Bitcoin 簡體中文翻譯

放心合法免費閱讀，想看實體書的話O'Reilly也有賣，作者在比特幣大漲後發文感嘆自己手裡沒有，馬上收到了讀者價值100多萬美元的比特幣捐款，可見這本書寫的多棒！

相關參考資源:

《Bitcoin: A Peer-to-Peer Electronic Cash System》
https://bitcoin.org/bitcoin.pdf
pymerkletools
https://github.com/Tierion/pymerkletools
Master Bitcoin
https://github.com/bitcoinbook/bitcoinbook