1、以太坊概述
1.1 簡介
以太坊作為區(qū)塊鏈2.0的典型代表歪今，是為了解決比特幣浪費(fèi)電能株婴、網(wǎng)絡(luò)擁堵等問題而重新設(shè)計的公鏈。
大家可以查看eth中文社區(qū)eth-fans提供的星火節(jié)點(diǎn)（https://stats.ethfans.org）喊熟，星火節(jié)點(diǎn)類似比特幣的種子節(jié)點(diǎn)，星火節(jié)點(diǎn)的信息會被打包到節(jié)點(diǎn)文件中供社區(qū)成員下載姐刁，通過使用節(jié)點(diǎn)文件芥牌，本地運(yùn)行的以太坊客戶端可以連接到更多的超級節(jié)點(diǎn)，大大加快了區(qū)塊同步速度聂使。
1.2 以太坊架構(gòu)
以太坊總體架構(gòu)：
[圖片上傳失敗...(image-59a5d1-1533223786890)]
上圖簡要描述了以太的軟件架構(gòu)壁拉，可以看出是EVM和智能合約擴(kuò)展了上層應(yīng)用程序，使之成為區(qū)塊鏈2.0.
區(qū)塊鏈六層架構(gòu)：
[圖片上傳失敗...(image-264659-1533223468139)]
數(shù)據(jù)層：是一個區(qū)塊 + 鏈表的數(shù)據(jù)結(jié)構(gòu)柏靶，本質(zhì)是一個分布式區(qū)塊鏈弃理。
網(wǎng)絡(luò)層：p2p網(wǎng)絡(luò)。
共識層：制定區(qū)塊鏈的獲取貨幣的機(jī)制宿礁。比如比特幣用的是POW(Proof of Work工作量證明機(jī)制)：電腦的性能越好案铺，越容易獲取到貨幣獎勵蔬芥。還有POS(Proof of Stake權(quán)益證明機(jī)制)：類似于眾籌分紅的概念梆靖，會根據(jù)你持有的貨幣數(shù)量和時間控汉，給持有者發(fā)放利息。還有比如超級賬本用的是PBFT（拜贊庭容錯）返吻。
激勵層：挖礦機(jī)制
合約層：以往的區(qū)塊鏈?zhǔn)菦]有這一層的姑子。所以最初的區(qū)塊鏈只能進(jìn)行交易，而無法用于其他的領(lǐng)域或是進(jìn)行其他的邏輯處理测僵。但是合約層的出現(xiàn)街佑，使得在其他領(lǐng)域使用區(qū)塊鏈成為了現(xiàn)實(shí)，比如用于IOT捍靠。以太坊中這部分包括了EVM(以太坊虛擬機(jī))和智能合約兩部分沐旨。
應(yīng)用層：區(qū)塊鏈的展示層。如以太坊使用的是truffle和web3-js.區(qū)塊鏈的應(yīng)用層可以是移動端榨婆，web端磁携，或是是融合進(jìn)現(xiàn)有的服務(wù)器，把當(dāng)前的業(yè)務(wù)服務(wù)器當(dāng)成應(yīng)用層良风。
1.3 以太坊常用項(xiàng)目介紹
以太坊的源碼托管在https://github.com/ethereum
由上圖可以看到以太坊有兩種語言寫的客戶端谊迄，其中go-ethereum是官方首推的版本，cpp是用c++寫的版本烟央，兩個版本功能完全一樣统诺，只是不同語言實(shí)現(xiàn)的而已。
除了以上的核心客戶端外疑俭，以太坊還提供了一系列獨(dú)立的工具粮呢，例如還在實(shí)驗(yàn)中的智能合約編程語言Viper、Solidity钞艇，和以太坊的JS調(diào)用庫Web3.js鬼贱，以太坊官方錢包等。目前eth的github官網(wǎng)已經(jīng)有150多個各類功能的工具項(xiàng)目香璃，以下整理一些常用的進(jìn)行說明：
go-ethereum
官方go語言客戶端这难，客戶端文件是geth。這是使用最廣泛的客戶端葡秒，類似比特幣的中本聰客戶端姻乓，可用于挖礦、組建私有鏈眯牧，管理帳號蹋岩、部署智能合約等。但是不能編譯只能合約（1.6之前還是內(nèi)置編譯模塊的学少，1.6之后就獨(dú)立出去了）剪个。該客戶端可以作為一個獨(dú)立程序運(yùn)行，也可以作為一個庫文件嵌入其他的GO版确、Android和ios項(xiàng)目中扣囊，它沒有界面乎折，是一個命令行程序。
- cpp-ethereum
與第一個相同侵歇，只是用C++實(shí)現(xiàn)的骂澄。
- EIPs
官方描述是eth平臺的實(shí)施標(biāo)準(zhǔn)，包括核心協(xié)議詳述惕虑，客戶端API及合約的標(biāo)準(zhǔn)坟冲。
以上三項(xiàng)也是官方github置頂?shù)娜齻€項(xiàng)目。
- mist
JS寫的一個DAPP browser客戶端溃蔫，可以用于瀏覽和使用DAPP健提，類似app strore，此前也是錢包客戶端伟叛，其實(shí)可以把Ethereum Wallet理解為配置Mist Browser上的一個dapp矩桂。
MIST一般是配合go-ethereum或者cpp-ethereum運(yùn)行的，如果在Mist啟動是沒有運(yùn)行一個命令行的ethereum客戶端痪伦，則mist將啟動區(qū)塊鏈數(shù)據(jù)同步（通常綁定geth客戶端）侄榴。如果想要Mist運(yùn)行在一個私有網(wǎng)絡(luò)，只要在Mist啟動前先啟動節(jié)點(diǎn)（即geth）即可网沾，Mist可以通過IPC鏈接到私有鏈癞蚕。
- Solidity項(xiàng)目。
Solidity使用C++開發(fā)辉哥，客戶端文件為solc桦山，跨平臺，使用命令行界面醋旦。solc是一個基本的編譯平臺恒水，Solidity是以太坊智能合約的編程語言。
- browse-solidity項(xiàng)目
智能合約瀏覽器版本的IDE饲齐，可以直接在瀏覽器中進(jìn)行開發(fā)钉凌、調(diào)試、編譯捂人。
- Remix
智能合約（以太坊稱為DAPP）開發(fā)IDE御雕，采用圖形化界面可以支持DAPP的編寫、調(diào)試滥搭、部署酸纲，是目前最主流的以太坊智能合約開發(fā)平臺。Remix現(xiàn)在可以和brower Solidity集成在一起使用了瑟匆。
- pyethereum項(xiàng)目
Python語言編寫的以太坊客戶端闽坡。
- ethereumj項(xiàng)目
Java語言編寫的客戶端，與geth功能完全相同。
1.4 以太坊目錄簡介
accounts 實(shí)現(xiàn)了一個高等級的以太坊賬戶管理
bmt 二進(jìn)制的默克爾樹的實(shí)現(xiàn)
build 主要是編譯和構(gòu)建的一些腳本和配置
cmd 命令行工具疾嗅，又分了很多的命令行工具外厂，下面一個一個介紹
/abigen Source code generator to convert Ethereum contract definitions into easy to use, compile-time type-safe Go packages
/bootnode 啟動一個僅僅實(shí)現(xiàn)網(wǎng)絡(luò)發(fā)現(xiàn)的節(jié)點(diǎn)
/evm 以太坊虛擬機(jī)的開發(fā)工具， 用來提供一個可配置的宪迟，受隔離的代碼調(diào)試環(huán)境
/faucet
/geth 以太坊命令行客戶端，最重要的一個工具
/p2psim 提供了一個工具來模擬http的API
/puppeth 創(chuàng)建一個新的以太坊網(wǎng)絡(luò)的向?qū)?br> /rlpdump 提供了一個RLP數(shù)據(jù)的格式化輸出
/swarm swarm網(wǎng)絡(luò)的接入點(diǎn)
/util 提供了一些公共的工具
/wnode 這是一個簡單的Whisper節(jié)點(diǎn)交惯。 它可以用作獨(dú)立的引導(dǎo)節(jié)點(diǎn)次泽。此外，可以用于不同的測試和診斷目的席爽。
common 提供了一些公共的工具類
compression Package rle implements the run-length encoding used for Ethereum data.
consensus 提供了以太坊的一些共識算法意荤，比如ethhash, clique(proof-of-authority)
console console類
contracts
core 以太坊的核心數(shù)據(jù)結(jié)構(gòu)和算法(虛擬機(jī)，狀態(tài)只锻，區(qū)塊鏈玖像，布隆過濾器)
crypto 加密和hash算法，
eth 實(shí)現(xiàn)了以太坊的協(xié)議
ethclient 提供了以太坊的RPC客戶端
ethdb eth的數(shù)據(jù)庫(包括實(shí)際使用的leveldb和供測試使用的內(nèi)存數(shù)據(jù)庫)
ethstats 提供網(wǎng)絡(luò)狀態(tài)的報告
event 處理實(shí)時的事件
les 實(shí)現(xiàn)了以太坊的輕量級協(xié)議子集
light 實(shí)現(xiàn)為以太坊輕量級客戶端提供按需檢索的功能
log 提供對人機(jī)都友好的日志信息
metrics 提供磁盤計數(shù)器
miner 提供以太坊的區(qū)塊創(chuàng)建和挖礦
mobile 移動端使用的一些warpper
node 以太坊的多種類型的節(jié)點(diǎn)
p2p 以太坊p2p網(wǎng)絡(luò)協(xié)議
rlp 以太坊序列化處理
rpc 遠(yuǎn)程方法調(diào)用
swarm swarm網(wǎng)絡(luò)處理
tests 測試
trie 以太坊重要的數(shù)據(jù)結(jié)構(gòu)Package trie implements Merkle Patricia Tries.
whisper 提供了whisper節(jié)點(diǎn)的協(xié)議齐饮。
1.5 以太坊關(guān)鍵概念
1.5.1 狀態(tài)
以太坊中將狀態(tài)轉(zhuǎn)換的過程稱為狀態(tài)轉(zhuǎn)換函數(shù)‘捐寥。
| 狀態(tài)1 | 狀態(tài)轉(zhuǎn)換函數(shù)---> | 狀態(tài)2 |
以太坊的每一個區(qū)塊頭，都包含了指向三棵樹的指針祖驱，分別是：狀態(tài)樹握恳、交易樹、收據(jù)樹捺僻。
交易樹指針就類似于比特比區(qū)塊頭中的梅克爾樹根乡洼，交易樹是用來代表區(qū)塊中發(fā)生的所有交易歷史的；
狀態(tài)樹：代表訪問區(qū)塊后的整個狀態(tài)匕坯；
收據(jù)樹代表每筆交易對應(yīng)的收據(jù)束昵，所謂的收據(jù)是指每一筆交易影響的數(shù)據(jù)條，或者說是每一筆交易影響的結(jié)果葛峻。這些都是針對比特比中梅克爾交易樹的增強(qiáng)锹雏，通過狀態(tài)樹可以很方便地獲得類似賬戶存在與否、賬戶余額术奖、訂單狀態(tài)這樣的結(jié)果逼侦，而不用只依靠交易事務(wù)去追溯。
以太坊狀態(tài)樹的示意圖：
[圖片上傳失敗...(image-b80dae-1533223468140)]
如上圖所示腰耙，狀態(tài)樹中存儲了整個系統(tǒng)的狀態(tài)數(shù)據(jù)榛丢，比如賬戶余額、合約存儲挺庞、合約代碼以及賬戶隨機(jī)數(shù)等數(shù)據(jù)晰赞。狀態(tài)樹有點(diǎn)類似我們玩游戲時的存檔功能。
再來看以下源碼中如何定義狀態(tài)樹根哈希的：
go-ethereum/core/types/block.go: 以太坊的區(qū)塊頭結(jié)構(gòu)
type Header struct {
ParentHash common.Hash `json:"parentHash" gencodec:"required"`
UncleHash common.Hash `json:"sha3Uncles" gencodec:"required"`
Coinbase common.Address `json:"miner" gencodec:"required"`
Root common.Hash `json:"stateRoot" gencodec:"required"`
TxHash common.Hash `json:"transactionsRoot" gencodec:"required"`
ReceiptHash common.Hash `json:"receiptsRoot" gencodec:"required"`
Bloom Bloom `json:"logsBloom" gencodec:"required"`
Difficulty *big.Int `json:"difficulty" gencodec:"required"`
Number *big.Int `json:"number" gencodec:"required"`
GasLimit uint64 `json:"gasLimit" gencodec:"required"`
GasUsed uint64 `json:"gasUsed" gencodec:"required"`
Time *big.Int `json:"timestamp" gencodec:"required"`
Extra []byte `json:"extraData" gencodec:"required"`
MixDigest common.Hash `json:"mixHash" gencodec:"required"`
Nonce BlockNonce `json:"nonce" gencodec:"required"`
}
root : 狀態(tài)樹根哈希
TxHash：交易樹根哈希
ReceiptHash：收據(jù)樹根哈希
1.5.2 賬戶
在以太坊系統(tǒng)中，狀態(tài)是由被稱為“賬戶”的對象和在兩個賬戶之間轉(zhuǎn)移價值和信息的狀態(tài)轉(zhuǎn)換構(gòu)成的掖鱼，每個賬戶有一個20字節(jié)的地址然走，這個其實(shí)就跟銀行賬戶差不多意思。 注意戏挡，比特幣中是沒有賬戶的概念的芍瑞。
以太坊中由于有賬戶的概念，所以可直接獲得當(dāng)前的余額褐墅。
看以下代碼中如何定義的：
go-ethereum/core/state/state_object.go中
type Account struct {
Nonce uint64
Balance *big.Int
Root common.Hash // merkle root of the storage trie
CodeHash []byte
}
由代碼可以看到拆檬，賬戶是由四個部分組成：
Nonce：隨機(jī)數(shù)，用于確定每筆交易只能被處理一次的計數(shù)器妥凳，實(shí)際上就是每個賬戶的交易計數(shù)竟贯，用以防止重放攻擊，當(dāng)一個賬戶發(fā)送一筆交易時逝钥，根據(jù)已經(jīng)發(fā)送的交易數(shù)來累加這個數(shù)字屑那，比如賬戶發(fā)送了5個交易，則賬戶隨機(jī)數(shù)是5.
Balance：賬戶目前的以太幣余額
Root：賬戶的存儲（默認(rèn)為空艘款，指向的是一顆帕夏爾前綴樹
CodeHash：賬戶的合約代碼（只有合約賬戶才有持际，否則為空）
以太坊中的賬戶是區(qū)分類型的：
1、外部賬戶
? EOA哗咆，就是一般賬戶选酗，外部所有賬戶是由一堆密鑰定義的，一個私鑰一個公鑰岳枷，公鑰的后20位作為其地址（跟比特比類似）芒填。外部所有賬戶是沒有代碼的，但是可以通過創(chuàng)建和簽名一筆交易從一個外部賬戶發(fā)送消息到合約賬戶空繁，通過傳遞一些參數(shù)殿衰，如EOA的地址，合約的地址盛泡，以及數(shù)據(jù)闷祥，使用ABI作為傳遞數(shù)據(jù)的編碼和解碼的標(biāo)準(zhǔn)。
2傲诵、合約賬戶
? 合約賬戶是一種特殊的可編程賬戶凯砍，合約賬戶可以在賬戶間傳遞消息，合約存儲在以太坊的區(qū)塊鏈上拴竹，并被編譯為以太坊虛擬字節(jié)碼悟衩，合約賬戶也是有地址的，不過與外部所有賬戶不同栓拜，不是根據(jù)公鑰來獲得的座泳，而是通過合約創(chuàng)建者的地址和該地址發(fā)出過的交易數(shù)量計算得到惠昔。
外部所有賬戶在以太坊中相當(dāng)于一把鑰匙，合約賬戶相當(dāng)于一個籍貫挑势，一旦被外部所有賬戶確認(rèn)激活镇防，機(jī)關(guān)就啟動了。
1.5.3 交易
以太坊中的交易也就是上一節(jié)說到的狀態(tài)轉(zhuǎn)換過程潮饱。
在以太坊中交易是一個廣義的概念来氧，它的定義是指簽名的數(shù)據(jù)包，這個數(shù)據(jù)包中存儲了從外部賬戶發(fā)送的消息香拉。
所謂的交易就是一個消息啦扬，這個消息被發(fā)送者簽名了。
以太坊中的交易源碼：
core/types/transaction.go
type Transaction struct {
data txdata
// caches
hash atomic.Value
size atomic.Value
from atomic.Value
}
其中的data是主要的字段缕溉，是結(jié)構(gòu)體類型：
type txdata struct {
AccountNonce uint64 `json:"nonce" gencodec:"required"`
Price *big.Int `json:"gasPrice" gencodec:"required"`
GasLimit uint64 `json:"gas" gencodec:"required"`
Recipient *common.Address `json:"to" rlp:"nil"` // nil means contract creation
Amount *big.Int `json:"value" gencodec:"required"`
Payload []byte `json:"input" gencodec:"required"`
// Signature values
V *big.Int `json:"v" gencodec:"required"`
R *big.Int `json:"r" gencodec:"required"`
S *big.Int `json:"s" gencodec:"required"`
?
// This is only used when marshaling to JSON.
Hash *common.Hash `json:"hash" rlp:"-"`
}
1）AccountNonce:表明交易發(fā)送者已發(fā)送過的交易數(shù)考传，與賬戶結(jié)構(gòu)中定義的隨機(jī)數(shù)對應(yīng)吃型；
2）Price與GasLimit：單價和所需的計算量证鸥，它倆的乘積是總的花費(fèi)，用來抵抗DDOS攻擊勤晚。
3）Recipient：接收方的地址枉层；
4）Amount：發(fā)送的以太幣余額，單位是wei赐写；
5）Payload：交易攜帶的數(shù)據(jù)鸟蜡，根據(jù)不同的交易類型有不同的用法；
6）V挺邀、R揉忘、S：交易的簽名數(shù)據(jù)；
上面沒有發(fā)送方地址端铛，是因?yàn)樗梢酝ㄟ^簽名獲得泣矛。
以太坊中的3種交易類型：
1）轉(zhuǎn)賬交易
web3.eth.sendTransaction({from:"",to:"",value:}); //web3.js是一個JS庫，可以通過RPC調(diào)用與本地節(jié)點(diǎn)通信禾蚕，實(shí)際上就是一個外部應(yīng)用程序用來調(diào)用以太坊核心節(jié)點(diǎn)功能的一個調(diào)用庫您朽。
2）合約創(chuàng)建交易
3）合約執(zhí)行交易
交易數(shù)據(jù)在以太坊中是存在交易樹中的，如1.5.1節(jié)中圖所示换淆，交易樹非常類似BTC中的默克爾樹哗总，只不過存儲的結(jié)構(gòu)與編碼方式有些差別。
1.5.4 收據(jù)
收據(jù)這個概念也是以太坊中特有的倍试。
源碼：
core/types/receipt.go
type Receipt struct {
// Consensus fields
PostState []byte `json:"root"`
Status uint64 `json:"status"`
CumulativeGasUsed uint64 `json:"cumulativeGasUsed" gencodec:"required"`
Bloom Bloom `json:"logsBloom" gencodec:"required"`
Logs []*Log `json:"logs" gencodec:"required"`
?
// Implementation fields (don't reorder!)
TxHash common.Hash `json:"transactionHash" gencodec:"required"`
ContractAddress common.Address `json:"contractAddress"`
GasUsed uint64 `json:"gasUsed" gencodec:"required"`
}
交易執(zhí)行后會影響狀態(tài)的變更讯屈，會消耗Gas，我們來看下上述結(jié)構(gòu)體中的主要屬性：
1）PostState：這是狀態(tài)樹的根哈希县习，不過不是直接存儲的哈希值耻煤，而是轉(zhuǎn)換為字節(jié)碼存儲具壮，通過這個字段使得通過收據(jù)可以直接訪問到狀態(tài)數(shù)據(jù)。
2）CumulativeGasUsed：所在區(qū)塊的gas交易之和
3）TxHash：交易事務(wù)的哈希值
4）ContractAddress：合約地址哈蝇，如果是普通的轉(zhuǎn)賬交易則為空
5）GasUsed：本條交易消耗的Gas棺妓。
收據(jù)實(shí)際上是一個數(shù)據(jù)的統(tǒng)計記錄，記錄了交易執(zhí)行后的特征數(shù)據(jù)炮赦。收據(jù)和交易是關(guān)聯(lián)對應(yīng)的怜跑。
其實(shí)從技術(shù)上來說收據(jù)不是必須的，沒有它也可以查詢到一些數(shù)據(jù)吠勘。它的存在只是為了提高賬本數(shù)據(jù)在各種需求下的統(tǒng)計效率性芬，方便各種查詢。
1.5.5 RLP編碼
RLP（Recursive length prifix）,遞歸前綴編碼剧防，是一種數(shù)據(jù)編碼方式植锉，在以太坊中使用非常普遍，是以太坊中對象序列化的主要方式峭拘，在區(qū)塊俊庇、交易、賬戶狀態(tài)等地方都有使用鸡挠。
比如交易從一個節(jié)點(diǎn)發(fā)送到另一個節(jié)點(diǎn)時辉饱，要被編譯為一種特別的數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)稱為trie樹拣展，也稱為前綴樹彭沼，然后根據(jù)這個前綴樹計算出一個根哈希（上述的交易樹，狀態(tài)樹备埃，收據(jù)樹都是這種方式）姓惑，而這顆樹的每一個數(shù)據(jù)項(xiàng)都會使用RLP的方式編碼。
編碼：將二進(jìn)制數(shù)據(jù)按照某種格式和規(guī)則進(jìn)行組裝按脚，以便于數(shù)據(jù)傳送的編碼與解碼于毙。
RLP編碼規(guī)則：略
1）單字節(jié)編碼
2）字符串長度是0-55字節(jié)
3）字符串長度大于55字節(jié)
以上都是字符串的編碼，以太坊中還涉及到列表的編碼乘寒，網(wǎng)上文檔很多望众，此處不贅述。
1.5.6 默克爾-帕特里夏樹
我們都知道比特幣中有默克爾樹的概念伞辛，每個區(qū)塊頭都有默克爾根烂翰，實(shí)際上就是一個區(qū)塊中交易哈希樹的根哈希值，而以太坊的區(qū)塊頭中有三個根哈希（交易蚤氏、狀態(tài)甘耿、收據(jù)），對應(yīng)各自的樹結(jié)構(gòu)竿滨。那么區(qū)別是什么呢佳恬？
嚴(yán)格來說捏境，比特幣中的默克爾樹叫二叉默克爾樹，而以太坊中是默克爾-帕特里夏樹（Merkle-Patricia Tree,有時也稱為帕特里夏樹）,是一種更加復(fù)雜的結(jié)構(gòu)毁葱，它是默克爾樹和帕特里夏樹的結(jié)合垫言。
我們來了解下什么是帕特里夏樹.
1）Patricia Tree
應(yīng)用場景：以交易數(shù)據(jù)為例，當(dāng)交易數(shù)據(jù)從一個節(jié)點(diǎn)發(fā)送到另一個節(jié)點(diǎn)的時候倾剿，必須被編譯為trie（前綴樹）筷频，這個trie中的每一個項(xiàng)都使用RLP編碼。在p2p網(wǎng)絡(luò)上傳輸?shù)慕灰资且粋€簡單的列表前痘，它們被組裝成一個叫做trie樹的特殊數(shù)據(jù)結(jié)構(gòu)來計算根哈希凛捏，這意味著交易列表在本地以trie樹的形式存儲，發(fā)送給客戶端的時候序列化成列表芹缔。這里的trie結(jié)構(gòu)就是patiricia tree坯癣。
Ptricia Tree是基于trie tree的一種結(jié)構(gòu)，trie tree是一種單詞查找樹結(jié)構(gòu)最欠。如下圖：
[圖片上傳失敗...(image-d34f89-1533223468140)]
trie中每個節(jié)點(diǎn)存儲一個字符示罗，這樣能很好地節(jié)約存儲空間。
而Ptiricia Tree每個節(jié)點(diǎn)可以存儲字符串或者二進(jìn)制串窒所，這樣就使其可以存儲更為一般化的數(shù)據(jù)鹉勒，而不只是一個單詞字符：
[圖片上傳失敗...(image-974cd-1533223468140)]
在這樣的樹結(jié)構(gòu)中每個節(jié)點(diǎn)存儲一個key-value鍵值對數(shù)據(jù)帆锋，key用來保存索引，是用來搜索定位的，value則是節(jié)點(diǎn)中具體的業(yè)務(wù)數(shù)據(jù)捏浊。
而以太坊中的樹結(jié)構(gòu)在這個基礎(chǔ)上還要復(fù)雜不少叭爱，我們來看看以太坊中的Merkle Patricia Tree具體是哪種結(jié)構(gòu)。
- 以太坊中用的
Merkle Patricia Tree
- 首先以太坊中節(jié)點(diǎn)分為空節(jié)點(diǎn)实辑、葉子節(jié)點(diǎn)捺氢、擴(kuò)展節(jié)點(diǎn)、分支節(jié)點(diǎn)剪撬。樹是由節(jié)點(diǎn)組成的摄乒，每個節(jié)點(diǎn)都是key-value形式，這些節(jié)點(diǎn)數(shù)據(jù)被存在本地的
LevelDB中, 以鍵值方式存儲残黑，value是節(jié)點(diǎn)的RLP編碼馍佑，key則是RLP編碼的哈希值。
Node=（key,value） //節(jié)點(diǎn)中
對應(yīng)LevelDB中：
value=RLP(Node)
key=sha3(value)
以太坊網(wǎng)絡(luò)中的核心客戶端會不斷地同步更新這個數(shù)據(jù)庫以報錯與網(wǎng)絡(luò)中的其他客戶端數(shù)據(jù)同步梨水，源碼中的定義：
trie/sync.go:
type SyncResult struct {
Hash common.Hash // Hash of the originally unknown trie node
Data []byte // Data content of the retrieved node
}
- 節(jié)點(diǎn)類型
1）空節(jié)點(diǎn)：value中是一個空字符串
2）葉子節(jié)點(diǎn)：
[圖片上傳失敗...(image-e82a7d-1533223616512)]
3）擴(kuò)展節(jié)點(diǎn)
[圖片上傳失敗...(image-815000-1533223616512)]
注意拭荤，擴(kuò)展節(jié)點(diǎn)指向的是存儲在LevelDB中的葉子節(jié)點(diǎn)哈希值。
4）分支節(jié)點(diǎn)
分支節(jié)點(diǎn)是真正存儲業(yè)務(wù)數(shù)據(jù)的疫诽。Merkle Partricia Tree作為一種前綴樹舅世，主要特點(diǎn)是依靠共享的前綴來提高樹結(jié)構(gòu)的處理性能旦委，那么這個前綴就很重要了，對于擴(kuò)展節(jié)點(diǎn)的和葉子節(jié)點(diǎn)來說雏亚，節(jié)點(diǎn)key就是起到前綴的作用缨硝。
[圖片上傳失敗...(image-7b25f4-1533223616512)]
5）樹結(jié)構(gòu)示例
由于比特幣只支持轉(zhuǎn)賬交易合約，所以默克爾樹是一顆二叉哈希樹罢低，但以太坊支持智能合約追葡，也增加了更多的概念，為了更有效的增刪改查并且讓樹的結(jié)構(gòu)更加平衡有效奕短，因此設(shè)計了更復(fù)雜的結(jié)構(gòu)：
[圖片上傳失敗...(image-fca30-1533223616512)]
- 葉子節(jié)點(diǎn)1的前綴為01234宜肉，因?yàn)槭怯筛?jié)點(diǎn)01開始。就是要通過共享前綴來充分提高存取效率翎碑。
- 十六進(jìn)制前綴
- 由于分支節(jié)點(diǎn)的結(jié)構(gòu)是長度為17的列表很容易判斷谬返，葉子節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn)都是長度為2的字節(jié)，是靠在key的前面增加4位二進(jìn)制前綴來識別的日杈。
- 最低位用來表示key長度的奇偶性遣铝，第二低位用來表示是否終止（1表示終止，也就是葉子節(jié)點(diǎn)莉擒，0表示擴(kuò)展節(jié)點(diǎn)）
[圖片上傳失敗...(image-1f4e08-1533223616512)]
[圖片上傳失敗...(image-e8d380-1533223616512)]
注意
增加的16進(jìn)制前綴并不是屬于節(jié)點(diǎn)key的一部分酿炸，而僅僅是在構(gòu)建樹結(jié)構(gòu)的時候附加上去的。整棵樹表示的數(shù)據(jù)在網(wǎng)絡(luò)中傳遞時候就是一個列表數(shù)據(jù)涨冀，而樹結(jié)構(gòu)是以太坊客戶端接收到數(shù)據(jù)后另行構(gòu)造出來的填硕。
