解密區塊鏈中的密碼學
在這片文章中,我們總結了區塊鏈會用到的一些密碼學原語,那什麼是密碼學“原語”?
不同於作業系統的“原語”概念,(OK區塊鏈工程院注:作業系統原語是作業系統或計算機網路用語範疇。是由若干條指令組成的,用於完成一定功能的一個過程,具有不可分割性。)密碼學原語強調的是“動機”,可以簡單理解為:你想做什麼事情?比如“加密”、“簽名”是個原語,“金鑰交換”、“零知識證明”也是個原語。
位於第一層階層的原語可能一共有十幾個左右,由第一階層的原語派生出的,大大小小加上各種屬性組合起來,可能有上千個之多。
一些密碼學家,在網路上做了一個很有趣的組合,左邊選原語、右邊選屬性,不同的原語跟不同的屬性,再加上不同的公平認證框架,三者互相組合可以就產生出上千種應用,也就是新的密碼原語。
而區塊鏈是一個密碼密集,比特幣就是區塊鏈的典型代表,它的基本結構可以概括成一個“雙鏈Hash鎖定”,其特性就體現在:
①它是一個全新的分散式帳本;
②它是“只增不改”;
怎麼來理解這兩點呢?其實楊義先原來打過一個比方的,他在《安全簡史》裡面把區塊鏈比喻成一個家譜。 相當於,我說話的時候拿著一個高音喇叭在廣場上面,我說出去的話被很多人聽到了,當我想反悔的時候,只要有足夠多的人證明你已經說過的話,你不能反悔,這樣就保證你說出去的話做到只增不改。
比特幣核心用密碼學原語就是簽名演算法(ECDSA)和雜湊演算法(Hash)。其實區塊鏈當中用到的密碼原語有很多,比如雜湊、數字簽名等。而且數字簽名不僅僅用了標準的數字簽名,還用到了環簽名、可連線環簽名、一次簽名,還有博羅梅環簽名,以及多重簽名,同態加密、同態承諾、累積器以及零知識證明等等,還有最近比較火的密碼擲籤。
(1)雜湊函式
目前來說,我們用的雜湊函式大部分三大類:SHA1、SHA2、SHA3。目前比特幣裡面又有一個主要是SHA0,當然現在也有一些已經用到了SHA3裡面的一些。
(OK區塊鏈工程院注::SHA即安全雜湊演算法(Secure Hash Algorithm的縮寫)是一個密碼雜湊函式家族,是FIPS所認證的安全雜湊演算法。SHA家族的五個演算法,分別是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,由美國國家安全域性(NSA)所設計,並由美國國家標準與技術研究院(NIST)釋出)
SHA3的好處是非NSA設計的,非NSA設計有一個好處,就是這裡面存在著一個後門(OK區塊鏈工程院注:後門一般是指那些繞過安全性控制而獲取對程式或系統訪問權的程式方法)。
從密碼演算法的角度來講,如果是設計者故意藏進去的“後門”,理論上可以做到不可區分,也就是除了設計的人知道,別的人想探知“後門”的存在性,將會面對一個人非常困難的數學難題。
為了便於對比,我們用破解MD5做一個對比,使用不超過2的64次方的位元運算、邏輯運算就可以實現。目前行業主要使用的是SHA—256,目前上沒有被破解。
OK區塊鏈工程院注:MD5是一種被廣泛使用的密碼雜湊函式,可以產生出一個128位(16位元組)的雜湊值(hash value),用於確保資訊傳輸完整一致。MD5由美國密碼學家羅納德·李維斯特(Ronald Linn Rivest)設計,於1992年公開,用以取代MD4演算法。
我們在提到Hash函式的時候,不可避免的要考慮一下Hash函式開放性概念,在區塊鏈裡,目前來說多數應用的是單向性。經常看有一些業界的人講區塊Hash加密的,其實Hash不叫加密,它只是取了一個摘要。
雜湊函式的設計,都需要滿足抗碰撞性。抗碰撞從攻擊的角度要求最低,安全目標的角度很高。也就是如果攻擊者連最低的攻擊目標都達不到,也就意味著存在最高的安全性。
還有一些典型的用於區塊鏈其他的Hash函式,比如說Equihash、Ethash、sCrypt,sCrypt已經在推薦標準草案裡面發過了。
最後總結一下“挖礦”和“對抗挖礦”,這是圍繞Hash技術研究“攻”和“防”的兩個概念。這是很奇異的一件事情,我們研究Hash從來沒有想過把Hash的速度降低,但是區塊鏈出來以後,使得對抗挖礦成為一個新的研究方向。
所謂對抗挖礦就是要求被計算速度不能太快,因為追求計算速度意味著不公平。比如過去的十年從最開始的一秒鐘完成100兆Hash運算,到用ASIC晶片可以完成14個T。
而對抗挖礦一種是在於提高硬體記憶體的門檻,如Ethash、Scrypt。另一種是如X11的這種序列的設計方案。把11種Hash函式串起來呼叫,而X17就是17種。目的都是為了讓Hash計算得慢,仍然保持著一個抗碰撞的特性。
目前為止,這麼做的方法從密碼學原理上面來說並沒有增強安全性,Hash函式串起來用,大家或許感覺更難、更安全了,但從理論上面來說並沒有。
(2)一次簽名
一次簽名是把簽名的概念結合一次一密的思想,就是說一個簽名私鑰只能使用一次,如果是想使用兩次就有一個危險:會洩露前面的私鑰。這個概念提得很早,主要是Lamport提出的,Lamport他本人也是一個搞分散式的大家。
Leslie B. Lamport
OK區塊鏈工程院注:Leslie B. Lamport是美國電腦科學家。以其在分散式系統中的開創性工作以及文件準備系統LaTeX的最初開發人員而聞名。也是2013年圖靈獎的獲勝者,他設計了重要的演算法並開發了正式的建模和驗證協議,以提高真實分散式系統的質量。這些貢獻提高了計算機系統的正確性,效能和可靠性
(3)環簽名
關於環簽名最大的特點是它的匿名性,被人描述為“拉你入環、與你何干”,也就是說我為了達到匿名性,可以隨便拉一些人組成這個環,代表一個組織來發佈一個訊息,只要我知道這些人的公鑰就可以。
打個比方,如果我們以人的名字為公鑰舉例子,那我可以跟特朗普的名字組合,釋出一個虛假資訊,然後說這個訊息是特朗普釋出的,而且特朗普也確實可以釋出這個東西。它的匿名性都是無條件,只要你知道一個人的名字,不需要徵得他的同意,就可以被你拉入到這個環當中來。
OK區塊鏈工程院注:環簽名(ring signature)是一種數字簽名方案,最初由Rivest等人提出,環簽名是一種簡化的群簽名,環簽名中只有環成員沒有管理者,不需要環成員間的合作。
一個好的環簽名必須滿足以下的安全性要求:
1)無條件匿名性。攻擊者即使非法獲取了所有可能簽名者的私鑰,他能確定出真正的簽名者的概率不超過1/n,這裡n 為環成員(可能簽名者)的個數。
2)不可偽造性。外部攻擊者在不知道任何成員私鑰的情況下,即使能夠從一個產生環簽名的隨機預言者那裡得到任何訊息m 的簽名,他成功偽造一個合法簽名的概率也是可以忽略的。
3)環簽名具有良好的特性。可以實現簽名者的無條件匿名;簽名者可以自由指定自己的匿名範圍;構成優美的環形邏輯結構;可以實現群簽名的主要功能但無需可信第三方或群管理員等。
環簽名是一種特殊的群簽名,沒有可信中心,沒有群的建立過程,對於驗證者來說,簽名人是完全正確匿名的。環簽名提供了一種匿名洩露祕密的巧妙方法。環簽名的這種無條件匿名性在對資訊需要長期保護的一些特殊環境中非常有用。例如,即使RSA被攻破也必須保護匿名性的場合。
(4)可連線環簽名
環簽名的匿名性是很好,但是這個匿名性太強悍了,以至於常常被用來洗錢、幹壞事。所以人們對於環簽名提出了一些限制,也就是可連線的環簽名,就是環中同一個人的兩次環簽名可以連結,但是簽名的身份仍然是你匿名的。
其實到這個層次,環簽名和群簽名有點類似之處了。群簽名的概念是91年Chaum提出的。Chaum也是盲簽名的提出者,第二次貨幣的研究就起源於1981年、80年左右,他在十年之後,提出了群簽名的概念。
群簽名是有一定的匿名性,對驗證者是匿名的,但是對群管理員來說不是匿名的,能夠查找出來是誰籤的。
這兩個概念,可連線的群簽名和可連線的環簽名當初都有各自的發展,而且都在區塊鏈當中使用,最後這些技術結合在一起,實現了環簽名交易,這個是門羅幣隱藏交易金額的一個關鍵技術。
(5)博羅梅環簽名
最初門羅幣想用博羅梅環簽名來做交易金額的範圍證明,想把交易金額的範圍證明想隱藏起來,後來因為博羅梅環簽名的效率很低而放棄。
博羅梅有一個歷史來源,以前一個很古老的家族博羅梅家族,用三個環繞的環做了一個家族的徽標,數學上面抽象起來就是這樣,這三個環開啟其中任何一個的時候,另外兩個環已經同時被打開了。
上面說過環簽名是有匿名性的,把多個環簽名放在一起,通過“或運算”可以把其看成每一個簽名人。
比如這個簽名是X1、X2籤的,或者Xn籤的,這一塊代表真,表示這裡面有一個人簽了名。此外另外一個Y1籤或者Y2籤,也是同樣的原理。每一個裡面到底是誰籤的,就是匿名的,匿名性是靠“或邏輯”實現的,而同時有效是靠“與邏輯”實現的。
博羅梅環簽名的意思是,一個環簽名具有匿名性,那麼把多個環簽名拼在一起,就完成了一個交易金額的證明,一旦有一個環被公開或者有一個環的匿名性丟失的時候,整個匿名性就丟失了,這是博羅梅環簽名。
(6)多重簽名與聚合簽名
多重簽名跟聚合簽名的概念稍微有些不一樣,比聚合簽名稍微簡單一些。多重簽名就是對於與相同訊息的多個不同的簽名聚合在一起,最後驗證的時候只驗證一次,就是不同的人對同一個訊息進行簽名,在區塊鏈當中用得比較少。
而聚合簽名比多重簽名這個範圍更廣一些,聚合簽名就把這個“相同”兩個字可以改成“不同”。聚合簽名把不同訊息的多個簽名,簽名人不同,簽名訊息也可能不同,還可以聚合成一個簽名,最終簽名還可以一樣的。目前還沒有發現區塊鏈專案應用聚合簽名,但是多重簽名確實用到了。
(7)同態加密
同態加密是一直是區塊鏈和加密貨幣行業討論的焦點,大家都對這個技術很關心,但是後來發現,就目前來說,同態加密這個技術,在區塊鏈中還用得比較淺顯,用的也很少。
同態加密的概念就是無需解密,基於密文(OK區塊鏈工程院注::密文是加了密的的文字,明文是加密之前的文字。密文是對明文進行加密後的報文)能夠做一些運算,它在安全計算、雲端計算當中都有很廣泛的應用。為了理解同態加密,我們可以從“加法同態”開始,也就是兩個密文加起來再解密,相當於兩個訊息加在了一塊。
而“乘法同態”就是兩個密文乘起來(特殊的乘法)再解密。“全同態”就是同時支援一組邏輯完備操作。實際上數學已經證明,定義在任何一個環上,只有滿足加法、乘法,就是最完備的,所以說只要同時實現了加法同態和乘法同態,相當於實現了全同態。
同態加密在區塊鏈當中還沒有直接使用。Zcash只有在最開始的一個構造的證明當中用了一步同態加密,而且是線性同態加密,還不是全同態加密。
(8)同態承諾
目前很多人所說的同態加密對區塊鏈很重要,實際描述的是來同態承諾。同態承諾在區塊鏈當中確實用得很多。承諾和加密的區別在哪?
承諾是不需要開啟或者是隻有出現糾紛的時候才能開啟。任何一個加密方案都可以變成一個承諾方案。承諾方案比加密方案構造各個方面要簡單,邏輯上要簡單很多。
從密碼構造、原子度構造的角度來說,承諾就是利用任何的單項函式,也就是說我只有一個Hash函式就可以構造出來。Hash函式我們通常看是非常有效的單項函式。但到目前為止,如果只靠單項函式,還無法將加密構造出來。
(9)累積器
累積器的作用,一方面是用來構造環簽名,另一方面是直接在區塊鏈當中使用,可能門羅幣當中就有用了。關於累積器,國內也有翻譯成聚合器的,這是一個很好的概念。
它可以把很多個物件壓縮到一個空間裡面,而且壓縮起來的空間跟原來每個物件的空間幾乎還是一樣大。但是同時根據特定的條件,還會構造出“成原證據”和“非成原證據”,比如說一半就能夠證明你在裡面或者證明你不在裡面,這就需要累積器,可以概括為八個字“萬眾歸一、真假可辨”。
這個潛力是了不得的,在區塊鏈當中肯定是希望使用這樣的東西。比如說把很多筆交易壓縮成一個交易,傳輸很快,而且如果真正拿出一個交易的時候,我還能夠證明你在裡面或者是你不在裡面。
當然,這裡面有一個必須消除的誤解,比如我給你一個壓縮後的東西,你從這個裡面“抽出”那一個東西,是抽不出來的。
基於資訊理論上可知,資訊壓縮是有丟失的。比如說把一千兆的一個位元資訊壓成1K,肯定有信息丟失,但是我構造的巧妙,你拿了一個原模原樣的東西,你問在不在我這個壓縮的裡面,我能證明它在裡面或者證明它不在裡面,這就是它的奇妙之處,而抽是抽不出來的。
打一個比方,有一個保密箱包含著每個人的半截頭髮,因為每個人的基因都是不同的,我可以通過半截頭髮,來證明你是否在這個保密箱裡。但是從基因的保密箱子裡面克隆出一個完整的人來則不行。
這一點對於很多應用來說這個已經很好了,目前對於聚合器在區塊鏈裡的應用,大家探索得還不夠,如果能夠找到直接使用的方法是最好的。
(10)零知識證明
顧名思義,零知識證明就是既能充分證明自己是某種權益的合法擁有者,又不把有關的資訊洩露出去——即給外界的“知識”為“零”。其實,零知識證明早在16世紀的文藝復興時期,義大利有兩位數學家為競爭一元三次方程求根公式發現者的桂冠,就採用了零知識證明的方法。
當時,數學家塔爾塔裡雅和菲奧都宣稱自己掌握了這個求根公式,為了證明自己沒有說謊,又不把公式的具體內容公佈出來(可能在當時數學公式也是一種技術祕密),他們擺開了擂臺:雙方各出30個一元三次方程給對方解,誰能全部解出,就說明誰掌握了這個公式。
比賽結果顯示,塔爾塔裡雅解出了菲奧出的全部30個方程,而菲奧一個也解不出。於是人們相信塔爾塔裡雅是一元三次方程求根公式的真正發現者,雖然當時除了塔爾塔裡雅外,誰也不知道這個公式到底是個什麼樣子。從這個故事,我們可以初步瞭解零知識證明的概念。
零知識證明是由S.Goldwasser、S.Micali及C.Rackoff在20世紀80年代初提出的。它指的是證明者能夠在不向驗證者提供任何有用的資訊的情況下,使驗證者相信某個論斷是正確的。
零知識證明實質上是一種涉及兩方或更多方的協議,即兩方或更多方完成一項任務所需採取的一系列步驟。證明者向驗證者證明並使其相信自己知道或擁有某一訊息,但證明過程不能向驗證者洩漏任何關於被證明訊息的資訊。
大量事實證明,零知識證明在密碼學中非常有用,如果能夠將零知識證明用於驗證,將可以有效解決許多問題。
關於區塊鏈,人們都還比較關心零知識證明,特別是Zcash提出了相關的技術zk—SNARK。
(OK區塊鏈工程院注:Zcash 是首個使用零知識證明機制的區塊鏈系統,它可提供完全的支付保密性,同時仍能夠使用公有區塊鏈來維護一個去中心化網路。與比特幣相同的是,Zcash代幣(ZEC)的總量也是2100萬,不同之處在於,Zcash交易自動隱藏區塊鏈上所有交易的傳送者、接受者及數額。只有那些擁有檢視金鑰的人才能看到交易的內容。使用者擁有完全的控制權,他們可自行選擇向其他人提供檢視金鑰。)
zk—SNARK的構造形式很複雜,可以說是一個“十八般武藝”的大整合,它是基於同態加法的多項式盲計算與盲驗證,然後基於這個二次算術程式設計的任意算術證明,然後基於橢圓曲線進行配對的一次乘法的合成。它還有引入了公共參考串,公共參考串在其中起到了隨機性內嵌的一個作用,試圖實現去中心化。
(11)密碼擲籤
密碼透支的基本思想是用抽籤的方式決定或者篩選出潛在的參與者,之後參與者再進行抽籤,最終第i個使用者是第r輪被選為潛在的leader的條件。為了滿足第i個使用者在第r輪第s步被選為驗證者的條件。這個簽名當中有歷史簽名存在,所以別人篡改不了這個,所以就是擲籤。
相當於把歷史整體可以看出來是隨機串。然後通過P1、P2引數的調整,可以證明在它的當中產生分杈的概率是可以忽略的,這是一個很強悍的概念。可忽略這個概率是呈指數下降的,只要系統引數足夠長。十萬分之一、百萬分之一、千萬分之一都不叫可忽略。可忽略要比任意多項式的DOS還小,降低的速度都還要快,這叫可忽略。