eth默克爾樹

『壹』 挖比特幣的原理

比特幣每個區塊的數據結構，每個區塊由區塊頭和區塊體兩部分組成。區塊頭中包含父區塊的哈希，版本號，當前時間戳，難度值，隨機數和上面提到的默克爾樹根。區塊體中包含了礦工搜集的若干交易信息，假設有8個交易被收錄在區塊中，所有的交易生成一顆默克爾樹，默克爾樹是一種數據結構，它將葉子節點兩兩哈希，生成上一層節點，上層節點再哈希，生成上一層，直到最後生成一個樹根。

『貳』 密碼學系統

本文分為7個部分，第1部分介紹密碼學的基本概念，第2部分講解常見的對稱加密演算法，第3部分講解常見的非對稱加密演算法，第4部分講解 數字簽名, 第5部分講解PKI(Public Key Infrastructure)，第6部分講解哈希函數加密，第7部分講解密碼學在區塊鏈里的應用, 最後一部分會講解隨機數。

比較常見的對稱加密演算法有: Digital Encryption Standard(DES), Triple-DES, IDEA, BLOWFISH。

對稱加密的挑戰：

非對稱加密的挑戰:

比較常見的非對稱加密演算法有: RSA, ElGamal, ECC。

菲斯特爾結構的塊加密演算法是著名的一個分組密碼加密的設計模型。

1990年後對DES進行徹底的密鑰搜索的速度開始引起DES用戶的不適。 然而，用戶並不想取代DES，因為它需要花費大量的時間和金錢來改變廣泛採用並嵌入到大型安全架構中的加密演算法。

務實的做法不是完全放棄DES，而是改變DES的使用方式。 這導致了三重DES(3DES)的修改方案。

三重DES
在使用3TDES之前，用戶首先生成並分配一個3TDES密鑰K，它由三個不同的DES密鑰K1，K2和K3組成。

詳細可以看 Triple-DES

高級加密標准(Advanced Encryption Standard，AES)是目前比較流行和廣泛採用的對稱加密演算法。 發現至少比三重DES快6倍。
AES的功能如下:

對稱密鑰對稱分組密碼
128位數據，128/192/256位密鑰
比Triple-DES更強更快
提供完整的規格和設計細節

詳細可以看 AES

這個密碼系統是最初的系統之一。 即使在今天，它仍然是最多被使用的密碼系統。 該系統由三位學者Ron Rivest，Adi Shamir和Len Adleman發明，因此被稱為RSA密碼系統。

下面給出生成RSA密鑰對的一個例子(為了便於理解，這里採用的素數p＆q值很小，實際上這些值非常高）。

設兩個素數為p = 7且q = 13。因此，模數n = pq = 7×13 = 91。

選擇 e = 5，這是一個有效的選擇，因為沒有數字是公因子5和(p - 1)(q - 1)= 6×12 = 72，除了1。

這對數字(n，e) = (91, 5)形成公鑰，可以讓任何我們希望能夠向我們發送加密消息的人使用。

向擴展歐幾里德演算法輸入p = 7，q = 13和e = 5。 輸出將是d = 29。
因此，公鑰是(91, 5)，私鑰是(91, 29)。

假設發送者希望發送一些文本消息給公鑰為（n，e）的人。然後發件人將明文表示為一系列小於n的數字。
為了加密第一個明文P，它是一個模n的數字。 加密過程是簡單的數學步驟:
C = Pe mod n
換句話說，密文C等於明文P乘以自己e次，然後減去模n。 這意味著C也是一個小於n的數字。
回到我們的密鑰生成例子，明文P = 10，我們得到密文C:
C = 105 mod 91

屬於ECC的一種變化。加密的核心理念與RSA相似，也是利用離散對數很難求解。
但與RSA不同的是 公鑰的組成部分，EIGamal的公鑰有三部分組成， 質模數 p, 生成元素 g, 以及 公共的 Y = gx(g的x次方) mod p。
詳細可以看 ElGamal Crytosystem

橢圓曲線密碼術(ECC)是用來描述一套密碼工具和協議的術語，其安全性基於特殊版本的離散對數問題。它不使用數字模p。ECC基於與稱為橢圓曲線的數學對象相關聯的數字集合。有這些數字的加法和計算倍數的規則，就像數字模p一樣。

ECC包含許多最初為模塊化數字設計的密碼方案的變體，如ElGamal加密和數字簽名演算法。

相信當應用於橢圓曲線上的點時，離散對數問題更加困難。這會提示從數字模p切換到橢圓曲線上的點。如果我們使用基於橢圓曲線的變體，也可以用較短的密鑰獲得等效的安全級別。

較短的密鑰有兩個好處:
易於管理
高效的計算
這些優點使基於橢圓曲線的加密方案變體對計算資源受到限制的應用程序非常有吸引力。

詳細可以看 Elliptic Curve Cryptography

^符號表示為多少次方
簽名 = 消息^D mod N (D和N 為簽名者的私鑰，計算消息的D次方並求mod N，所得余數即為簽名)
消息 = 簽名^E mod N (E和N 為簽名者的公鑰，計算簽名的E次方並求mod N)

舉個例子:
私鑰: D = 29; N = 323
公鑰: E = 5; N = 323
消息: 123

由於 N 的值為 323, 因此消息需要為 0 ~ 322 這個范圍內的整數. 假設需要對 123 這個消息進行簽名.
用私鑰(D,N) = (29,323) 對消息 123 進行簽名.

消息^D mod N = 123^29 mod 323 = 157
因此 (消息, 簽名) = (123, 157)

用公鑰(E,N) = (5,323)對消息進行驗證
簽名^E mod N = 157^5 mod 323 = 123

得到消息 123 與發送者發送過來的消息 123 是一致的，因此簽名驗證成功.

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introction/

加法逆: a在集合中, -a在集合中的定義為使 a + (-a) = 0, 這就是加法逆元運算
乘法逆: a在集合中,且不為0, a^-1 在集合中定位為使 a* a^-1 = 1, 這就是乘法逆元運算

在聊橢圓曲線前，我們先打一些基礎然後再討論一下對數問題.

在一個集合上定義一個二元運算，這就是數學中的群。一個集合 G 要成為一個群，必須滿足下面 4 個條件:

從平常的加法概念來看, 整數集 Z 是一個群(而且是阿貝爾群). 自然數集 N 不是一個群.

我們可以在橢圓曲線上定義一個群:

https://andrea.corbellini.name/ecc/interactive/reals-add.html

如下圖: 點 A 的自我相加過程就是做 乘法的過程 這個過程叫 Point Doubling

計算 nP 需要做 n次加法 如果 n 為 k 位二進制 時間復雜度為 O(2^k)

倍加演算法 比如 n = 151 二進制為 10010111

用倍加演算法 時間復雜度有了很大的改進 O(logN) or O(k)

Q = nP

這只是 p = 211, 像 Secp256k1 這條橢圓曲線的 p = 34671663 一個78位的數字 要怎麼求出 n?

一個通俗的比喻: 假設這些點是有個人 A 在一個很大的房間里玩彈珠的游戲 玩了兩年 兩年後 A 的朋友 B來了 B看到了最後的點 以及 A 告訴B 起點 但是B怎麼能知道 A 是彈了多少次才從起點彈到終點？

上面這兩張圖是 橢圓曲線 - Secp256K1: y^2 = x^3 + 7
第一張圖: 定義在 實數域
第二張圖: 定義在 有限域Zp
是用下面的參數(p,a,b,G,n,h)形成的:

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2^256 - 2^32 - 997
a = 0
b = 7
G = [0x79BE667E_F9DCBBAC_55A06295_CE870B07_029BFCDB_2DCE28D9_59F2815B_16F81798,
0x483ADA77_26A3C465_5DA4FBFC_0E1108A8_FD17B448_A6855419_9C47D08F_FB10D4B8]
n = 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_BAAEDCE6_AF48A03B_BFD25E8C_D0364141
h = 1

如果橢圓曲線上一點P, 存在最小的正整數 n 使得數乘 nP=O∞, 則將 n 稱為 P 的階

計算可得 27P = -P = (3, 13) 所以 28P = 0∞ P的階為28

如何簽名?
Sig = F sig ( F keccak256 ( m ) , k )

如何計算 r

如何計算 s
s ≡ q^-1 (Keccak256(m) + r * k) (mod p)

如何驗證簽名?

P.S. 上述驗證簽名的過程中 沒有用到發送者的 私鑰

RSA 密鑰大小(bits) ECC 密鑰大小 (bits)
1024 160
2048 224
3072 256
7680 384
15360 521

有一個研究例子 同一台計算能力的計算機

為什麼 比特幣和以太坊要選擇 Secp256k1 這條橢圓曲線?

假如有人提供一條橢圓曲線比如 Secp256r1 如何驗證這條曲線的安全性？

因為公鑰是公開的，很容易被破壞或者篡改，因此需要建立和維持一種可信的基礎機制來管理公鑰。

PKI由5部分組成:

作為比喻，證書可以被視為發給該人的身份證。人們使用駕照，護照等身份證來證明自己的身份。數字證書在電子世界中具有相同的基本功能。
但有一點不同，數字證書不僅發給人，還可以發給電腦，軟體包或任何其他需要證明電子世界身份的東西。

數字證書基於ITU標准X.509，該標準定義了公鑰證書和認證驗證的標准證書格式。因此數字證書有時也被稱為X.509證書。

與用戶客戶端相關的公鑰與證書頒發機構(CA)一起存儲在數字證書中，以及其他相關信息，例如客戶信息，到期日期，使用情況，發行者等。

CA對此整個信息進行數字簽名並在證書中包含數字簽名。

任何需要對客戶的公共密鑰和相關信息進行保證的人，他都會使用CA的公鑰進行簽名驗證過程。成功的驗證可確保證書中給出的公鑰屬於在證書中給出詳細信息的人員。

下圖了展示了個人/實體獲取數字證書的過程:

如圖所示，CA接受來自客戶端的申請以證明其公鑰。 CA在適當驗證客戶身份後，向該客戶發出數字證書。

如上所述，CA向客戶頒發證書並協助其他用戶驗證證書。 CA負責正確識別要求頒發證書的客戶的身份，並確保證書中包含的信息是正確的並對其進行數字簽名。

CA的關鍵功能:

證書類別
有四種典型的證書類別:

第1類 - 通過提供電子郵件地址可輕松獲取這些證書。

第2類 - 這些證書要求提供額外的個人信息。

第3類 - 這些證書只有在對請求者的身份進行檢查後才能購買。

第4類 - 它們被需要高度信任的政府和金融機構使用。

CA可以使用第三方注冊機構(RA)對要求證書確認其身份的人或公司進行必要的檢查。 RA可能在客戶端看起來像一個CA，但它們實際上並不簽署發布的證書。

這是發布證書的管理系統，暫時或永久暫停，續訂或撤銷證書。 證書管理系統通常不會刪除證書，因為可能有必要在某個時間點證明其身份，這是出於法律原因。 CA和相關RA運行證書管理系統，以便能夠跟蹤他們的責任。

雖然客戶端的公鑰存儲在證書中，但關聯的私鑰可以存儲在密鑰所有者的計算機上。 這種方法一般不採用。 如果攻擊者能夠訪問計算機，他可以輕松訪問私鑰。 出於這個原因，私鑰存儲在通過密碼保護的安全可移動存儲令牌上。

不同的供應商經常使用不同的專有的存儲格式來存儲密鑰。 例如，Entrust使用專有的.epf格式，而Verisign，GlobalSign和Baltimore使用標準的.p12格式。

1.6 Hierarchy of CA:
由於擁有龐大的網路和全球通信的要求，所有用戶從唯一一個可信的CA獲得證書是不切實際的。其次，只有一個CA的可用性可能會導致大的阻礙，如果CA受到影響。

在這種情況下，層次認證模型很受關注，因為它允許在兩個通信方與相同CA沒有信任關系的環境中使用公鑰證書。

根CA位於CA層次結構的頂部，根CA的證書是自簽名證書。

直接隸屬於根CA(例如，CA1和CA2)的CA具有由根CA簽名的CA證書。

層次結構中下級CA(例如，CA5和CA6)下的CA具有由上級下級CA簽名的CA證書。

證書頒發機構(CA)層次體現在證書鏈中。證書鏈跟蹤從層次結構中的分支到層次結構根的證書路徑。

下圖顯示了具有從實體證書到兩個從屬CA證書(CA6和CA3)到根證書頒發機構CA證書的證書鏈的CA層次結構:

驗證證書鏈是確保特定證書鏈有效，正確簽署和可信的過程。 以下過程驗證證書鏈，從提供驗證的證書開始 -

一個正在驗證其真實性的客戶端提供他的證書，通常連同證書鏈一直到根CA.

驗證者獲取證書並使用發行者的公鑰進行驗證。 發行人的公鑰在發行人的證書中找到，該證書位於客戶證書旁邊的鏈中。

現在，如果已簽署發行人證書的較高的CA由驗證方信任，則驗證成功並在此停止。

否則，發行人證書的驗證方式與客戶在上述步驟中完成的相似。 此過程將繼續進行，直到在其中找到可信的CA，否則它將持續到根CA。

哈希函數非常有用，並且出現在幾乎所有信息安全應用程序中。

哈希函數是將數字輸入值轉換為另一個壓縮數值的 數學函數。 哈希函數的輸入具有任意長度，但輸出始終為固定長度。

哈希函數返回的值稱為消息摘要或簡單的散列值。 下面的圖片說明了哈希函數:

為了成為一個有效的加密工具，哈希函數具有以下屬性:

散列的核心是一個數學函數，該函數在兩個固定大小的數據塊上運行以創建散列碼。 這個哈希函數構成哈希演算法的一部分。

每個數據塊的大小因演算法而異。 通常塊大小從128位到512位。 下圖演示了哈希函數:

哈希演算法涉及上述哈希函數，如分組密碼。 每一輪都會輸入一個固定的大小，通常是最近消息塊和最後一輪輸出的組合。

這個過程重復進行多次，以散列整個消息。 哈希演算法的示意圖如下圖所示:

因為第一消息塊的散列值變成第二散列操作的輸入，其輸出改變第三操作的結果，等等。 這種效應被稱為散列的雪崩效應。雪崩效應對兩個即使是單個數據位也不相同的消息產生明顯不同的散列值。理解哈希函數和演算法之間的區別。 哈希函數通過對兩個固定長度的二進制數據塊進行操作來生成哈希碼。哈希演算法是一個使用哈希函數的過程，指定如何分解消息以及如何將先前消息塊的結果鏈接在一起。

後來在1995年，SHA-1被設計用於糾正SHA-0的所謂弱點。SHA-1是現有SHA哈希函數中使用最廣泛的。它被用於幾個廣泛使用的應用程序和協議，包括安全套接字層(SSL)安全。

2005年，發現了一種在實際時間框架內發現SHA-1沖突的方法，使SHA-1的長期可用性受到懷疑。

SHA-2系列具有四個更進一步的SHA變體，SHA-224，SHA-256，SHA-384和SHA-512，取決於其散列值中的位數。還沒有成功的攻擊報道過SHA-2哈希函數。

雖然SHA-2是一個強大的哈希函數。雖然有很大的不同，但其基本設計仍然遵循SHA-1的設計。因此，NIST要求提供新的競爭性散列函數設計。

2012年10月，NIST選擇Keccak演算法作為新的SHA-3標准。 Keccak提供了許多好處，例如高效的表現和良好的攻擊抵抗力。

該集包括RIPEND，RIPEMD-128和RIPEMD-160。此演算法還有256位和320位版本。

原始的RIPEMD(128位)基於MD4中使用的設計原則，並且發現提供可疑的安全性。 RIPEMD 128位版本是解決原始RIPEMD漏洞的快速修復替代品。

RIPEMD-160是一個改進版本，是使用最廣泛的版本。與RIPEMD-128和RIPEMD-160相比，256和320位版本分別減少了意外沖突的可能性，但沒有更高的安全等級。

Merkle Tree 默克爾樹

哈希演算法的一個重要應用是默克爾樹(Merkle tree)，默克爾樹是一種數據結構，通常是一個二叉樹，也有可能是多叉樹，它以特定的方式逐層向上計算，直到頂部，最頂層叫做默克爾根(Merkle Root)，默克爾樹最為常見和最簡單的是二叉默克爾樹。

『叄』 梅克爾樹-Merkle Trees

梅克爾樹是一種二叉樹，能快速檢查和歸納大量數據，可用於驗證區塊中交易記錄的完整性。

梅克爾樹是區塊鏈的重要數據結構， 其作用是快速歸納和校驗區塊數據的存在性和完整性。一般意義上來講，它是哈希大量聚集數據「塊」的一種方式，它依賴於將這些數據「塊」分裂成較小單位的數據塊，每一個 bucket 塊僅包含幾個數據「塊」，然後取每個 bucket 單位數據塊再次進行哈希，重復同樣的過程，直至剩餘的哈希總數僅變為1。

在這顆數中，每個交易都可以單獨刪除，只需要保存好這筆交易的哈希值即可。這樣一來，就可以極大的減小了每個區塊的內存，可以存放更多的最新交易。所以在 UTXO 模型中，使用默克爾樹結構，就無需擔心數據的增長過大的問題了。

使用場景：
1、區塊頭維護交易的梅克爾樹；
2、SPV 錢包通信的交易驗證，存放該樹。

歡迎留言討論，有錯誤請指出，謝謝！

【聯系我（QQ：3500229193）或者加入社群，請戳這里！】

『肆』 Filenet技術背簡析

Filenet技術背簡析：費激勵層如何實現構建高效率檢索分發網路？

Filenet的目標是連接一切閑置存儲空間，並且在激勵機制上完美解決了去中心化文件分發貢獻度問題。

為何Filenet是IPFS最具創新性的產品？我們將從技術角度，參照白皮書對此予以簡析。

Filenet共識機制

區塊鏈的核心技術是共識機制，Filenet也不例外。

目前比較常用的共識機制有PoW（Proof-of-Work，工作量證明）、PoS（Proof-of-Stake，權益證明）、DPoS（Delegated- Proof-of-Stake，委託權益證明）、PoC（Proof-of-Contribution，貢獻證明

PoW 機制， 需要礦工解決復雜的密碼數學難題，依賴計算能力，優點是系統安全可靠，缺點是消耗能源和計算能力、有 51%算力攻擊可能、吞吐量小。

PoS 機制， 根據權益選舉礦工打包數據，優點是不消耗資源，缺點是安全性較低，且股權越多的人話語權越高。

DPoS 機制， 多數有投票權的人將投票權委託給少數節點來代理，優點是系統效率高、吞吐量和並發數高，缺點是話語權掌握在少數節點手上並不安全。

PoC 機制， 根據節點所做的貢獻來分配打包權，優點是不浪費資源、按勞分配，缺點是貢獻的計算方法要根據具體的場景來定。

區塊鏈 3.0 時代，Filenet共識機制朝著 不浪費資源，且最大程度考慮安全性，並優化吞吐量和並發數的方向發展。

Filenet有向無環圖

比特幣的區塊鏈結構是一個單向鏈表，這種結構是區塊鏈早期採用的，存在很多問題， 如區塊存儲容量小、交易速度慢、數據總量大、單節點存儲壓力大以及每秒交易數少。

(有向無環圖)

而DAG（Directed

Acirclic Graph，有向無環圖）是一種新型的區塊鏈數據結構。

DAG和鏈表結構都能由上一個節點來確定下一個節點。 所不同的是，鏈表結構只能是一對一，而DAG支持一對多、多對一，但不會產生回環。

也就是通過前面節點來驗證後面節點保持一致，但鏈表結構同一時間只能有一個分支，而DAG結構可以有多個分支，故DAG結構並發數更高，同時存儲的數據更多。

同時，DAG記賬是一個非同步的過程，數據是弱同步，可以接受一定程度的數據差異，在後續非同步確認過程中再進行修正。 這樣可以極大地節省確認時間，提高交易速度。

Filenet默克爾樹

默克爾樹是快速驗證數據的一種方式，在比特幣中也有採用，在點對點數據傳輸等領域也廣泛採用。

(默克爾樹示意圖)

默克爾樹將數據分成很多小塊，每一塊計算出一個hash值，多個數據塊合並生成一個hash值（一般是兩個數據塊）， 最終生成並匯集到一個根節點， 生成一棵樹（一般是二叉樹）。

由於數據分塊，並且提供了hash值索引，在數據很大或是點對點系統中，不用得到所有數據，再驗證數據是否正確。

哪怕只得到了一小塊數據， 只需要在這棵樹上找到數據所在的位置，確定樹上關鍵位置的數據和hash值，就能驗證數據是否正確。

建立一個去中心化的文件存儲和分享網路，是一個非常有吸引力和激動人心的願景，而Filenet作為一個創新的免費激勵層，完美實現了最高效率的分發。

可以預見，Filenet的綜合技術優勢，將帶給它巨大的實用價值和廣闊的想像空間。

PS.還未注冊 Filenet早期礦工 的粉絲們請抓住最後的申請時間

『伍』 區塊鏈-默克爾樹

Merkle 樹是一種組織和構造大量數據以使其更易於處理的方法。在加密貨幣和區塊鏈的情況下，Merkle 樹用於以對資源要求較低的方式構建交易數據。

當在 Merkle 樹結構中進行加密貨幣交易時，它會被散列，然後被賦予一個等效的散列值。每筆交易在 Merkle 樹中散列後，產生的散列值與另一個散列值配對，然後再次散列。例如，將散列值「AB」和「AC」組合起來創建「ABC」。

重復這個配對散列值的過程，直到產生最終的散列值。最終的哈希值，即默克爾根，提供了它包含的所有交易的摘要。然後將 Merkle 根摘要插入到塊頭中。

Merkle 樹結構提供了一個區塊中交易的易於訪問的記錄。因此，檢查塊中的數據是否已更改或篡改非常簡單。這是真的，因為對 Merkle 樹中的交易（或任何其他相關數據）的任何更改都會導致完全不同的對應 Merkle 根。

如果加密貨幣不使用 Merkle 樹，則每個驗證請求都將涉及通過網路發送的大量信息。在 Merkle 樹中構建交易數據是一種更有效的資源利用。驗證交易不需要賬本的完整副本，因為可以在 Merkle 根中驗證散列的交易數據，需要在節點間發送的信息少得多，因此分析整體數據完整性的計算能力也更少。

換句話說，Merkle 樹結構使用戶能夠驗證單個交易是否已包含在一個區塊中，而無需經過下載整個區塊鏈的過程。該技術是加密貨幣組織交易數據並像它們一樣高效運行的重要工具。如果沒有默克爾樹，對資源的更大需求很可能會導致參與網路的節點更少。

『陸』 006：MPT與RLP|《ETH原理與智能合約開發》筆記

待字閨中開發了一門區塊鏈方面的課程：《深入淺出ETH原理與智能合約開發》，馬良老師講授。此文集記錄我的學習筆記。

課程共8節課。其中，前四課講ETH原理，後四課講智能合約。
第二課分為三部分：

這篇文章是第二課第二部分的學習筆記：MPT與RLP。

MPT，Merkle Patricia Tree，結合了Merkle Tree（默克爾樹）和 Patricia Tree（帕特里夏樹）的一種數據結構。
RLP，Recursive Length Prefix，一種編碼方法。

這是兩個非常重要的數據結構，在以太坊的區塊和交易中都有用到。

先分別介紹一下Merkle Tree 和 Patricia Tree。
Merkle Tree 和 Patricia Tree Merkle Tree 和 Patricia Tree
默克爾樹的解釋：對每一個交易計算其散列值（Hash），再對兩個散列值求他們的散列值。如果是奇數個，就把最後一個重復一次。最後得到的一個散列值就是默克爾樹根的值。如圖，交易1、1、2、3的散列值分別是HASH0、HASH1、HASH2、HASH3。HASH0和HASH1結合在一起計算散列值得HASH01，HASH2和HASH3結合在一起計算散列值得HASH23，接下來HASH01、HASH23結合在一起，計算散列值得HASH0123。

採用默克爾樹的好處是可以方便的判斷一個交易是否在區塊中。

Patricia Tree，可稱為壓縮前綴樹。如上圖右半部分。相同的前綴在同一分支中，後面一同的部分分叉出來，如test和toast，都有相同的t，est和oast在兩個分支中。

這個結構的好處是節省空間，因為每一級的鍵值可以是多個字元。

了解了Merkle Tree 和 Patricia Tree後，再來看這兩者混合後的產物——MPT。
這里的原理知識單獨來看不易理解，和具體的例子結合起來才更容易理解，此處先放上課件截圖。在後面的例子中再做說明。
Merkle Patricia Tree 規格 Merkle Patricia Tree 規格
在MPT中，還涉及到三個小的編碼標准。主要規則如圖。下面結合兩個例子說明一下。
三個編碼標准 三個編碼標准
HEX編碼的例子：從ASCII碼表中可以查出，b的十六進制編碼為62，o的十六進制編碼為6F，F在十六進制中就是15的意思。因為這是個葉子節點，最後加上0x10表示結束，也就是16。所以最後的編碼為[6 2 6 15 6 2 16]

HEX-Prefix編碼的例子：[6 2 6 15 6 2 16]，將其最後的0x10去掉，[6 2 6 15 6 2]。前面補一個四元組，其中（倒數）第0位是區分奇偶信息的，[6 2 6 15 6 2]是偶數位，第0位是0；第1位是區分節點類型的，這是葉子節點，第1位是1。所以這個四元組就是0010是2。「如果輸入key的長度是偶數則再添加一個四元組0x0在flag四元組之後。」，所以，最終的前綴是0x20。本例最終的結果，[32 98 111 98]，即[0x20, 0x62, 0x6F, 0x62]

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

初始的key-value對為：

其中，<>中的數據為key的16進制編碼。
MPT.jpg MPT.jpg
因為4組數據都有公共的6，所以這個節點的值為6，長度為1，奇數；節點類型：擴展節點；所以前綴就是0001，即1。

這是個擴展節點，它的值是一個Hashvalue，它指向一個分支節點。Hashvalue，具體指的是分支節點RLP編碼的結果的散列值。（RLP見下小節）

分支節點。上面4組數據的第2位是4和8兩種情況。在4的位置上存的是下面的擴展節點的散列值，在8的位置上存的是下面的葉子節點的散列值。

葉子節點。以68開頭的只有一個了。所以這個節點上的四元組就是6f727365了。它是偶數位。前綴是0x20（同前文HEX-Prefix編碼的例子）。這個葉子節點的value值為'stallion'。

擴展節點。在64之後，公共的部分是6f，這個擴展節點的key即為6f，前綴為0000，即00。這個擴展節點的value存放的是一個hashvalue，指向下一個節點，一個分支節點。

分支節點。646f已經表達完，這個節點的value值就是646f對應的值，'verb'。

除此之外，646f之後就是6，所以在這個分支節點的6位置上有一個散列值，指向下一個節點。

擴展節點。在646f6之後，公共的部分是7，其長度為1，奇數。所以前綴為0001。這個節點的value是一個散列值，指向下一個節點。

分支節點。646f67已經表達完，這個節點的value值就是646f67對應的值，'puppy'。

除此之外，646f67之後就是6，所以在這個分支節點的6位置上有一個散列值，指向下一個節點。

葉子節點。key為5，value為'coin'。長度為1，奇數，前綴0011，即3。

整個分析過程結束。可結合上圖和前文的理論多加復習。

這小節也是理論性較強，通過例子可以方便理解。先放上課件，再根據我的理解舉更多的例子。同樣，學習方法也是理論和例子配合學習。其中，list的例子在下篇文章的上機實驗部分再列舉。 RLP的編碼標准 RLP的編碼標准 再舉幾個例子 再舉幾個例子

『柒』 交易數據是寫入區塊鏈的哪個部分

現實的區塊鏈直接將內容數據(如交易數據)存儲在資料庫中，稱為默克爾樹，然後將默克爾樹的跟存儲在區塊頭。
_默克爾樹具有非常獨特的屬性，使我們能夠在對等網路中進行有效的數據驗證。默克爾樹是二叉樹，其中節點存儲哈希，而不是排序存儲數據塊。 https：//right.bdstatic.com/vcg/edit/.jpg
區塊鏈，就是一個又一個區塊組成的鏈條。每一個區塊中保存了一定的信息，它們按照各自產生的時間順序連接成鏈條。這個鏈條被保存在所有的伺服器中，只要整個系統中有一台伺服器可以工作，整條區塊鏈就是安全的。
這些伺服器在區塊鏈系統中被稱為節點，它們為整個區塊鏈系統提供存儲空間和算力支持。

『捌』 關於比特幣的謎題（完結）

你可曾想過： 為什麼礦機算力越大越好？（既然是解數學題那為什麼不是拼誰的演算法厲害啊喂！） 比特幣的數量總和為什麼是2100萬？ 比特幣盜竊是怎麼回事？ 我不玩比特幣，就真的與比特幣無關了嗎…… 🤔️

關於大眾不再感到陌生的比特幣，背後還有許多巧妙之處。本文介紹了比特幣的基本原理和主要原則，並結合對部分技術細節的剖析，來對上述的一些疑問作出解答。全文較長，約7000字，閱讀時間約為22分鍾，建議收藏後閱讀😁

文章可以分成以下幾個部分：

* 比特幣先驗知識

        -- 密碼學相關

        -- 比特幣重要概念

* 交易的生命周期

* 區塊鏈的構成

* 區塊鏈的生長

         -- 「挖礦」的數學本質

         -- 「礦工」的收益

* 比特幣的共識機制

          -- 比特幣的去中心化共識

          -- 「最長鏈優先」原則

* 比特幣安全性

比特幣作為第一個去中心化的數字貨幣，其設計中運用了不少的密碼學相關知識，主要包括非對稱加密技術、哈希函數等等。理解這些密碼學知識，能幫助我們更好地理解比特幣中的一些概念及規則。

以下是比特幣的一些定義及概念解說，了解過的小夥伴們可以直接跳過～

在比特幣這個創新的支付網路中，一個交易的生命周期大概可以分為幾個階段：創建、傳播和被驗證交織、被打包進區塊記錄到區塊鏈中、獲得更多的確認。圖1對這幾個階段做出了示意。

註：

1⃣️一個支付方A在發起一個比特幣交易時，會使用自己的私鑰對交易信息的哈希值進行簽名。因此A向全網廣播的內容除了交易信息之外，還有自己的公鑰信息、對消息的簽名。其他礦工只要利用A的公鑰即可對這個交易進行驗證，判斷是否真的由A創建。

2⃣️」交易傳播和交易驗證「交替意味著 各個節點基於一定的規則獨立驗證每個交易（共識基礎1） , 一個節點只有認為這個交易有效才會把它繼續傳播出去。

比特幣的底層技術是區塊鏈。區塊鏈系統是一種分布式共識系統，區塊鏈網路中所有的參與節點將就交易的狀態達成一致。

區塊鏈到底是什麼呢？你可以把它理解成一種分布式的交易的共享賬本，以區塊為基本單位鏈接在一起。交易信息將被整理並打包記錄在區塊中。每一個區塊，包含區塊頭，以及緊跟其後的交易列表。區塊頭包含3個區塊元數據集合：前序區塊哈希(嚴格來說是前序區塊頭哈希，因為只有區塊頭被用於哈希運算)、元數據集（包括難度、時間戳、隨機數等）、一個基於加密哈希來高效概括區塊中所有交易的默克爾樹（merkle tree)。了解這個結構，將幫助我們更好地理解挖礦的數學本質。

你可能聽說過「挖礦」這個詞，或者聽說眾人爭相購買挖礦機器來發家致富。但讓人疑惑的是：都說打包區塊的本質是解數學難題，但單憑那些看似簡陋的機器嗡嗡嗡瘋狂耗費電力，就能確保自己解出比特幣難題的勝率高了嗎？比特幣技術原理中，礦工們解決的數學題，難道是一個暴力破解題？

看了一圈，發現礦工們解決的題，還真有點暴力破解的意思，每次嘗試解題的過程幾乎都是茫茫然、去碰運氣的。拼的是誰足夠幸運，也拼誰算的足夠快；算的快了么，試錯次數多，自然勝算也就大了。

解題的背景是這樣的—— 挖礦節點通過基於工作量證明演算法（Proof-of-Work,POW）的證明運算，獨立將交易匯聚到新區塊中（共識基礎2）。 當礦工從網路中接收到一個新的區塊的時候，他發現自己已經在上一輪競爭中失敗了，所以立即開始新區塊的挖礦過程。為了創建一個新的區塊，他從內存池中選擇交易來填充區塊（加入區塊的第一筆交易是一個「鑄幣交易」，3.2節會給出詳相關細節）。接下來是填充欄位來創建區塊頭（包括前序區塊的區塊頭哈希、交易的默克爾樹（Merkel樹）、時間戳、難度目標值、隨機數），然後開始計算這個新區塊的工作量證明。

這個計算的過程簡單來說是對區塊頭部進行兩次sha256運算，得到一個RESULT，如果這個RESULT滿足特定要求，這個人才能算是算對了、才有權利去記賬。滿足要求的RESULT被稱為「工作量證明」（中本聰論文中稱為「proof of work」）。

關於這個計算過程，強調以下幾點：

第一，區塊頭部，包含了前序區塊頭部的哈希、本區塊交易信息的默克爾樹、時間戳、難度目標值、隨機數等信息（見圖2）。

第二，哈希運算具有「知道y，無法推出使得h(x)=y成立的x」、「即使輸入只改變一點點，輸出也會差很多」、「利用任意長度的數據作為輸入，生成一個固定長度的確定結果」的特性。所以大家也不知道什麼樣子的輸入才能產生自己想要的結果，礦工只能不斷嘗試。

第三，前面說到，區塊頭哈希值需要滿足一個特定要求才能成為工作量證明——小於某一閾值，或者說哈希值含有給定前綴。閾值的大小求和挖礦難度有關：挖礦難度是一個動態參數，其值越大，則閾值越小，說明哈希值符合要求的概率更小，礦工每次計算能成為工作量證明的概率越小。比特幣有一個自我調節過程——通過對現有的挖礦算力情況進行估算，來對應調整挖礦難度，可以保證區塊鏈每十分鍾出一個塊，達到控制發行速度的目的。（這個過程的基本思想類似產品筆試的數據估算題，根據「一個提供、一個需要「的思路去構造一個等式，然後求解等式一邊的一個因子；想了解挖礦難度系統和調整方式的同學可以進一步查閱～）

綜合以上三點來看，為了產生工作量證明，用戶基本上會通過調整隨機數來碰運氣（因為其他欄位基本不變）、進行多次運算直至符合要求，別無他法。如此一看，隨機數就具有「幸運數字」的意味了。因此，平均來講，誰計算的能力越強（嘗試的次數越多），就更有希望打包塊。

你可能會想，礦工這么心甘情願地消耗算力去維護區塊鏈，是受到怎樣的利益驅使呢？簡單來說，礦工的收益來源有二：1、計算出工作量證明，創造一個新區塊所獲得的新幣獎勵；2、記賬礦工費。

當礦工找到工作量證明、打包一個新區塊，並把區塊傳送給他的所有對等節點。 每一個挖礦節點都獨立驗證新區塊、把合格的新區塊整合進區塊鏈（共識基礎3） ，並把這個區塊繼續傳給自己的對等節點。結果是，只有經過驗證的區塊才會在網路當中廣泛傳播，保證了誠實礦工挖出的新區塊能被區塊鏈所接納。挖礦成功的個體節點或集體節點，可以同時獲得新幣獎勵和記賬礦工費。

新幣獎勵類似於貨幣的發行，其遵循規則是，第一個四年每一個新區塊產生50btc，第二個四年每一個新區塊產生25btc，第三個四年每個新區塊產生12.5btc，如此周期指數遞減。按照等比數列求和可知，到2140年，比特幣產生的總和約為21000000（所以說比特幣數量有限，天生緊縮）。屆時，不再隨區塊的產生增加新的比特幣，礦工不再擁有第一項收益。但現實中，由於挖礦成本高昂，挖礦成功的往往是是一個礦池的所有參與者。收益被分給礦池地址，礦池按照組內算力貢獻比例來分攤收益的。

記賬礦工費又稱交易費用，以交易輸入和交易輸出之間的差值的形式存在；一個區塊的總交易費用是對加入區塊的所有交易的（交易輸入-交易輸出）求和。一般來說，礦工費越高的交易，會越快被處理。而礦工費在這里起到兩個作用，一個是獎勵礦工，另一個是防止主鏈濫用（防止大家發送交易垃圾信息，因為提出交易是有一定代價的）。

礦工的收益以什麼樣的形式被驗證呢？這里不得不提到 「鑄幣交易」 。每個計算機節點在進行工作量證明計算之前加入區塊的第一筆交易，正是「鑄幣交易」。這個交易從無到有生成比特幣，其金額是新幣獎勵與記賬礦工費的總和，被支付到挖礦礦工自己的比特幣地址。如果礦工找到了一個工作量證明使區塊有效，他就贏得了這個獎勵，因為他構造的「鑄幣交易」生效了。

關於鑄幣交易和「新幣獎勵」，之前有一個讀者問我：一個礦工把自己挖到新區塊的消息公布出去，他的工作量證明 不會被別人剽竊 嗎？

個人認為，至少「鑄幣交易」能防止這件事情發生。讓我們來重申一下計算工作量證明的過程——一個礦工E在新區塊里加入了獎賞自己的「鑄幣交易」，並利用時間戳、前序區塊頭哈希、隨機數、本區塊交易的merkle樹等信息計算出一個符合要求的工作量證明。

在這個過程中，merkle樹啥樣子，取決於包括「鑄幣交易」在內的本區塊所有交易信息。因此可以把鑄幣交易視為工作量證明的間接變數之一。那麼，即使其他人拿到了E的工作量證明，這個工作量證明也是帶有E的印記的、與獎賞E的鑄幣交易相關的，別人根本無法納為己用。

你還可以通過設想以下的場景來加深對共識基礎2「挖礦節點通過基於工作量證明演算法的證明運算，獨立將交易匯聚到新區塊中」的理解。

為什麼一個挖出新區塊的礦工不悄悄使個心眼，在創建區塊之初就把鑄幣交易的金額設成1000BTC呢？原因在於每個節點都是基於相同的規則來獨立驗證區塊的。礦工必須創建完美的、符合公共規則的、正確依據工作量證明方法的區塊；而一個無效的鑄幣交易會導致整個區塊無效，並被其他節點拒絕，永遠無法成為賬本的一部分。可以預想，為了生成這個工作量證明，礦工們已經投入了巨大的算力和電量去挖礦，如果涉嫌欺詐而被否決，其為挖礦付出成本都付諸東流。

綜上所述，礦工不能冒領他人的獎勵，而拿到獎勵的礦工也必須只能拿取符合規定的數額。

   比特幣的卓越之處，在於建立了一種去中心化的自發共識。這種共識是自發產生的，是成千上萬在網路中遵循著共同規則的節點，在非同步交互中形成的，不依賴於任何中央機構的調解和干涉。

   關於比特幣的4項主要共識基礎，本文在講解對應細節時有提及，下面做一個整合：

     這四個過程相輔相成、互相作用，形成了自發的全網共識，促使全網節點組合出可信、公開、權威的總賬。  

你可能會想，比特幣是一個去中心化的、基於大眾信任的、依靠眾人力量運轉的一個東西。萬一有一部分礦工被壞人收買了咋辦呢？「51%攻擊」指的又是什麼？比特幣交易所要求的「6個確認」又是怎麼回事？

這里首先要提到比特幣的一個規則「 最長鏈優先 」。意思是， 比特幣的賬單鏈在出現分叉的時候，每個礦工會獨立選擇長（累積了最多工作量證明）的鏈條，在上面繼續挖礦工作（共識基礎4） 。

這個原則主要涉及到兩個問題：

當有兩個礦工A和B同時挖礦成功（算出符合要求的數學答案）時，他們分別把自己計算出來的工作量證明作為下一個塊的前序區塊哈希，生成一個塊銜接到原有的鏈後面，由此出現了兩個分支。

這個時候，這兩個成功的礦工廣播了自己打包成功的消息。由於區塊鏈是一個去中心化的數據結構，區塊消息到達不同節點的時間點不一致，故不同的節點可能擁有不完全一樣的區塊鏈視圖——有的礦工會先收到A的消息，有的則先收到B的消息。為了解決這個問題，收到消息的礦工們遵循一個原則：選擇並嘗試延長最長的鏈。

因此，這兩條分支會各自成長一小段時間，直到他們的長度出現差異（不可能長度一直相同），比如說其中一條鏈的礦工們，更快地打包在支鏈後面又加上一塊。按照「最長鏈優先「的規則，較短的鏈會被拋棄，原本工作在短鏈上的礦工們都回到長鏈上工作。

換言之，分叉只是不同節點暫時的不一致現象，當新區塊被加入到其中某一分支時，最終收斂將解決這一個問題。[讀者可以思考一下，為什麼區塊鏈被設置成每十分鍾挖出來一個塊：如果時間短了，是不是就增加了分支產生的次數？如果時間長了，是不是交易結算的效率就太低了？]

雙重支付的本質其實也是區塊鏈的分叉，但這種分叉卻是「非自然惡意蓄謀」的產物。

我們假設小敏是密謀雙重支付的一方，她把自己僅有的10BTC先給小強、交換一塊黃金，待這條交易信息P被打包進區塊Q後，她從小強手中拿到了黃金。這時，小敏使了個心眼，她想偷偷抹去、篡改區塊Q上的交易信息P，「白嫖」這塊黃金。為了實現這樣的目的，根據「最長鏈優先」法則，小敏必須剔除該筆交易P後、重新進行結算工作，集中算力來形成分叉，並讓分叉以更快的增速超過並取代Q所在的主鏈。如果小敏確實能讓分叉更長，分叉就成為了主鏈，其他節點也會轉向新主鏈上繼續工作。這樣，小強付出了黃金，卻沒有收到這10個比特幣，「賠了夫人又折兵」。

在這個過程中，小敏需要和原鏈進行「抗爭」，使新分叉成為最長的主鏈，這被稱為「共識攻擊」。「共識攻擊」本質上是對下一區塊的爭奪，攻擊方越「強壯」、哈希算力越大，就越容易成功。

「共識攻擊「成功的可能性有多大呢？

大多數比特幣交易所規定，一個交易傳送到區塊鏈上後需要6個「確認」來完成驗證該筆交易。這一規定的根據是，假設意圖造假的礦工擁有10%的算力（挖礦成功概率0.1），那麼造假礦工要構造另一條偽鏈實施長度超越，必須至少成功挖礦6次。那麼原鏈被取代、被拋棄的概率約為0.1的6次方，趨近於0。你可以把比特幣理解為地質構造層，表層可能因為季節變換而有所改變，甚至可能被風颳走，但一旦深入到地下，地質層就能更加穩定、不受干擾。

而假設有一群擁有了51%算力的礦工，他們控制了一半以上的全網哈希算力，可以故意在區塊鏈中製造分叉、進行雙重支付交易 。但事實是，全網哈希算力的大量增加，個體礦工幾乎不可能控制哪怕1%的哈希算力了（但礦池帶來的算力集中化控制，存在一定的風險）。更何況，如果真有擁有如此強大算力的組織，他完全可以憑借自己強大的算力投入到挖礦中去獲取開發新區塊所獲的的比特幣獎勵，誠實挖礦比雙花更有利可圖。

盡管實際上並未出現51%攻擊的問題，但不可否認的是，算力的集中違背了比特幣去中心化這一初衷，並成為其繼續發展的一大隱患。

一個系統的安全性，往往取決於系統安全的最薄弱環節，這也就是所謂的「木桶原理「。與區塊鏈系統相關的安全性問題包括但不限於以下幾項：

（1）在區塊鏈上被廣泛使用的公鑰系統基本上是安全的，但量子演算法在理論上能夠破解公鑰系統；因此，區塊鏈的演算法安全性是相對的。

（2）區塊鏈協議本身存在邏輯缺陷，例如受到黑客攻擊的區塊鏈系統共識機制。

（3）所有數字貨幣系統高度依賴私鑰，私鑰在存儲、使用方面的安全性成為區塊鏈系統安全性中至關緊要的一環。

盡管區塊鏈是去中心化系統，但目前絕大多數數字交易所卻是中心化的，存在著人為安全漏洞及技術安全漏洞。這些數字交易所擁有存放大量加密貨幣的私鑰，這對於黑客來說無疑是最矚目的目標；只要黑客偷走了這些私鑰，就可以獲取到這些加密貨幣。

作者會繼續閱讀相關資料、不斷完善本文，目標是完成一篇通俗易懂的比特幣科普文章。:)

**本文系網上信息與個人理解的結合，如有偏差及誤讀，歡迎讀者指出。也歡迎給出關於文章結構上的指導～

『玖』 什麼是默克爾樹

默克爾樹（Merkle tree）是一種哈希二叉樹，1979年由Ralph Merkle發明，將數據存儲在樹狀結構的葉子節點中，並通過對數據的逐級哈希（Hash）操作確保數據的不可篡改性。葉子節點數據的任何變動，都會傳遞到上一級節點並最終反應到樹根的變化。比特幣區塊裡面的每一筆交易就是通過默克爾樹結構進行存儲的。

『拾』 用途是什麼意思

用途的意思是指應用的層面和范圍，也指一種多種用途的工具。