01

密碼學(xué)的歷史

人們對(duì)于信息編碼的需求幾乎伴隨著寫作的發(fā)展出現(xiàn)。加密寫作這一形式最先被應(yīng)用于古埃及、美索不達(dá)米亞以及古印度。隨著時(shí)間的推移，人們學(xué)會(huì)了使用特殊的工具來編碼文本。最早的加密工具之一是密碼棒(scytale)，斯巴達(dá)軍方使用其來進(jìn)行戰(zhàn)場(chǎng)通信。密碼學(xué)技術(shù)一直在不斷發(fā)展。一旦現(xiàn)有的加密方法不再奏效，人們就會(huì)發(fā)明出新的信息編碼方案。 在第二次世界大戰(zhàn)期間，第三帝國(德國)使用非常復(fù)雜的機(jī)電轉(zhuǎn)子密碼裝置(即Enigma裝置)來進(jìn)行軍事通信編碼。Enigma裝置的主要構(gòu)造包括鍵盤、轉(zhuǎn)子、電路板和燈。轉(zhuǎn)子將輸入文本轉(zhuǎn)換為密碼，其位置會(huì)隨著每次擊鍵發(fā)生改變。一個(gè)擁有一萬人的解密中心最終耗費(fèi)多年才成功破解Enigma代碼。隨著計(jì)算機(jī)時(shí)代的到來，密碼學(xué)躍升到了一個(gè)新的高度。許多國家，尤其是美國，組建了全新的國家資助加密計(jì)劃，其中就包括由NIST開發(fā)的安全哈希算法SHA-256。如今，在眾多應(yīng)用程序中，SHA-256哈希算法都被用于在比特幣中創(chuàng)建區(qū)塊。以太坊區(qū)塊鏈網(wǎng)絡(luò)使用的是Keccak算法?；贙eccak算法，一種新的哈希算法標(biāo)準(zhǔn)SHA-3問世，該新標(biāo)準(zhǔn)于2015年首次發(fā)布。

02

SHA-256和區(qū)塊創(chuàng)建過程

創(chuàng)建區(qū)塊的過程包括對(duì)交易進(jìn)行驗(yàn)證和記錄，此過程我們稱之為挖礦(mining)。交易經(jīng)過哈希運(yùn)算后被記錄在區(qū)塊中。所謂哈希，是指將任意長(zhǎng)度的文本信息轉(zhuǎn)換為固定長(zhǎng)度值的過程。比特幣交易就是使用SHA-256算法進(jìn)行哈希處理。 以下是通過SHA-256算法將任意文本及其對(duì)應(yīng)哈希的示例：

如上圖所示，哈希是由64個(gè)字符組成，通過SHA-256算法所得到的結(jié)果為256位，即64個(gè)16進(jìn)制字符。。SHA-256算法對(duì)于輸入字母的大小寫十分敏感，比如單詞Hello和hello的哈希完全不同。挖礦的目的是確定所生成區(qū)塊的哈希，以保證該哈希將適合某個(gè)特定區(qū)塊鏈網(wǎng)絡(luò)中的所有交易。隨著創(chuàng)建單個(gè)區(qū)塊所需的算力越來越多，挖礦的難度也會(huì)逐漸增加。隨著創(chuàng)建區(qū)塊所需的算力增長(zhǎng)，哈希碼中“零”的個(gè)數(shù)也在不斷增長(zhǎng)。目前在比特幣中，其哈希的開頭有20個(gè)連續(xù)的零，創(chuàng)建區(qū)塊需要消耗大量的計(jì)算資源(computational resources)。然而，產(chǎn)生區(qū)塊的時(shí)間上限是不變的，依舊保持在10分鐘。在每生成2016個(gè)區(qū)塊以后，比特幣挖礦的難度將進(jìn)行自動(dòng)調(diào)整，這個(gè)調(diào)整的切換率在比特幣代碼發(fā)布時(shí)已經(jīng)確定。因此，創(chuàng)建區(qū)塊的過程在于記錄該區(qū)塊內(nèi)所有交易的哈希值。每一個(gè)比特幣區(qū)塊均包含以下字段(fields)：幻數(shù)(magic number)、區(qū)塊大小(blocksize)、區(qū)塊頭(blockheader)、交易計(jì)數(shù)器(transaction counter)以及包含相關(guān)交易信息的交易字段(transactions field)。每個(gè)區(qū)塊頭包含以下部分：版本號(hào)

前一個(gè)區(qū)塊頭的哈希

Merkle根哈希

時(shí)間戳

難度目標(biāo)

隨機(jī)數(shù)

Merkle根顯示當(dāng)前區(qū)塊交易的哈希值，并根據(jù)Merkle樹算法進(jìn)行計(jì)算，也被稱為二進(jìn)制哈希樹。其工作原理如下：

首先，系統(tǒng)計(jì)算區(qū)塊內(nèi)所有交易的哈希值;

其次，系統(tǒng)將這些交易成對(duì)劃分，并計(jì)算出每個(gè)交易對(duì)的哈希;

最后，系統(tǒng)再次將所有這些交易對(duì)的哈希按對(duì)配對(duì)，并依次反復(fù)計(jì)算，直到計(jì)算出唯一的哈希碼，即得到所謂的根。

下圖展示的就是Merkle二進(jìn)制哈希樹結(jié)構(gòu)：

可以看出，Merkle樹的結(jié)構(gòu)是兩兩配對(duì)的，因此它必須擁有偶數(shù)個(gè)元素。如果Merkle樹內(nèi)的元素?cái)?shù)量是奇數(shù)，那么系統(tǒng)會(huì)將落單的元素加倍以滿足配對(duì)條件。

具有奇數(shù)元素?cái)?shù)量的Merkle樹如下所示：

區(qū)塊中的所有交易數(shù)據(jù)正是以這種方式進(jìn)行計(jì)算與記錄在區(qū)塊中的。 在區(qū)塊鏈序列中，每個(gè)區(qū)塊都與前一個(gè)和后一個(gè)區(qū)塊相連。如果有人嘗試修改區(qū)塊中的某一筆交易，將會(huì)引起連鎖反應(yīng)。首先，這將改變被修改后的交易的哈希，并向上擴(kuò)散改變Merkle樹的分支，最終改變Merkle根的哈希。此后，被修改的Merkle根將改變?cè)搮^(qū)塊的區(qū)塊頭，由此改變區(qū)塊鏈序列中的所有后續(xù)區(qū)塊。也就是說，哪怕只是一次修改也將導(dǎo)致此前用于創(chuàng)建該特定區(qū)塊序列的計(jì)算工作的報(bào)廢，并引發(fā)重新計(jì)算。

03

用于驗(yàn)證比特幣和以太坊交易的密碼學(xué)知識(shí)

比特幣和以太坊網(wǎng)絡(luò)中的交易數(shù)據(jù)通過一種稱為橢圓曲線數(shù)字簽名算法(ECDSA)所產(chǎn)生的簽名來進(jìn)行驗(yàn)證，這種算法主要運(yùn)用的是橢圓曲線和有限域。

簽署交易和驗(yàn)證交易的過程是截然不同的。我們使用一個(gè)被稱為私鑰(private key)的工具來簽署交易，而使用另一個(gè)被稱為公鑰(public key)的工具來驗(yàn)證交易。私鑰是在創(chuàng)建錢包的過程中隨機(jī)生成的。公鑰是基于有限域上的橢圓曲線乘法利用私鑰導(dǎo)出的,也就是說橢圓曲線數(shù)字簽名算法(ECDSA)就是用來產(chǎn)生公鑰的算法。只有簽署交易的人才知道私鑰，而公鑰可以被任何想要驗(yàn)證交易的人(即礦工)獲取。橢圓曲線主要包含以下參數(shù)：一個(gè)方程式(an equation)，一個(gè)素?cái)?shù)模(a prime modulo)和一個(gè)具有素?cái)?shù)階的基點(diǎn)(a base point with a prime order)。橢圓曲線的方程為 y²=x³+ ax + b。(備注：素?cái)?shù)也稱質(zhì)數(shù)，指在大于1的自然數(shù)中，除了1和該數(shù)自身外，無法被其他自然數(shù)整除的數(shù)，如2、3、5、7、11等都是質(zhì)數(shù))在比特幣，以太坊，BKX，EOS，Litecoin和許多其他加密貨幣中，其使用的橢圓曲線為secp256k1，該曲線方程的形式為y²=x³+ 7 mod p。secp256k1曲線的素?cái)?shù)模是2²??–2³²–2?–2?–2?–2?–2?–1(或十六進(jìn)制形式的FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F)。因?yàn)檫@個(gè)結(jié)果本質(zhì)上是一個(gè)大素?cái)?shù)，因此我們稱之為素?cái)?shù)模。實(shí)數(shù)域上的橢圓曲線如下所示

基點(diǎn)G具有素?cái)?shù)階n，從圖形化的角度來看，n可以被視為基點(diǎn)不斷相加直到其斜率無窮大或者成為垂線的次數(shù)。因此，在選定基點(diǎn)時(shí)，我們要確保其階數(shù)是大素?cái)?shù)。 對(duì)secp256k1來說，基點(diǎn)G的壓縮形式為：G = 02 79 BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798，并且G的階數(shù)n為：n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141。要生成公鑰，我們需要用私鑰乘以G，即： Keypub = Keypriv×G通過私鑰導(dǎo)出公鑰并不困難。但是，Keypriv是一個(gè)非常大的數(shù)字。因此，想要通過公鑰來獲取私鑰，并破解ECDSA算法，則需要進(jìn)行計(jì)算 2¹²?個(gè)附加點(diǎn)的操作。對(duì)于普通計(jì)算機(jī)而言，這樣的操作將花費(fèi)超過100億年，這是一個(gè)與整個(gè)宇宙的年齡相稱的時(shí)間過程。

在生成私鑰和公鑰后，我們必須使用私鑰對(duì)交易進(jìn)行簽名。為此，我們需要完成以下操作：

計(jì)算z = hash( 交易 ) mod n;

選擇隨機(jī)整數(shù)k，其等于或大于1且小于或等于n-1(1≤k≤n-1);

通過將k乘以G得到點(diǎn)(x, y);需要注意的是，k 是一個(gè)臨時(shí)的秘密值，其必須在步驟5之后立即銷毀。泄漏秘密值 k 等同于泄漏私鑰：如果攻擊者知道 k 和簽名，那么她(或他)就可以計(jì)算私鑰。

計(jì)算r = x mod n。如果r = 0則返回步驟1;函數(shù)x mod p 僅返回除法的余數(shù)，例如78 mod 33 = 12 等同于 78 = (33*2)+12，98 mod 31 = 5 等同于 98 = (31*3)+5。注意，s 模 n的乘法逆表示為1/k mod n，并且1/k mod n 等于等式 kx = 1(mod n) 的解。這個(gè)方程在歐幾里德算法的幫助下以下列方式求解：假設(shè) s = 3且 n = 5，則方程顯示為3x = 1(mod 5) ，或者利用歐幾里德算法，得3x = b(mod 5) 。如果我們將其擴(kuò)展到線性丟番圖方程ax - by = c，或sx - ny = b，或 3x - 5y = 1，其中 x = 2且 y = 1(6–5=1) 中，那么 s-1將為2。

計(jì)算 s = (1/k mod n) × (z + r × Keypriv) mod n。如果s = 0，則返回步驟1;

計(jì)算對(duì) (r, s) 將成為交易的簽名。

在交易簽名生成并被接收后，任何第三方都可以使用公鑰通過以下方式對(duì)其進(jìn)行驗(yàn)證：

確認(rèn)簽名元素，數(shù)字 r 和 s 均落在1到n-1的范圍內(nèi);

計(jì)算 z = hash(交易) mod n;

計(jì)算 w = 1/s mod n;

計(jì)算 u = z × w mod n;

計(jì)算 v = r × w mod n;

計(jì)算點(diǎn) (x, y) = (u × G) + (v × Keypub);

確認(rèn) r = x mod n。 如果r≠x mod n，則驗(yàn)證的簽名無效。

如上所述，ECDSA算法的安全性依賴于整數(shù) k 的隨機(jī)性以及使用普通算力在合理時(shí)間內(nèi)不可能導(dǎo)出私鑰的特性。 這種全新的加密方式賦予區(qū)塊鏈技術(shù)最高級(jí)別的安全性，打破它的唯一方法是創(chuàng)建一個(gè)具有超過2000個(gè)量子比特算力的量子計(jì)算機(jī)——這種做法，至少在目前看來，是不可能的。