電子發(fā)燒友App
我們?cè)谠S多介紹零知識(shí)證明的文章中都能看到這樣三個(gè)性質(zhì)：
Completeness —— 完備性
Soundness —— 可靠性
Zero-Knowledge —— 零知識(shí)
但是少有文章深入解釋這個(gè)特性背后的深意和洞見。
通常，我們定義安全會(huì)采用這樣一種方式，首先列出一些安全事件，然后說明：如果一個(gè)系統(tǒng)安全，那么列出來的安全事件都不會(huì)發(fā)生。
借用密碼學(xué)家 Boaz Barak 的話，翻譯一下，「零知識(shí)證明」并不是通過給出一個(gè)不允許發(fā)生的事件列表來定義，而是直接給出了一個(gè)最極致的「模擬條件」。
所謂「模擬條件」是指，通過「模擬」方法來實(shí)現(xiàn)一個(gè)「理想世界」，使之與「現(xiàn)實(shí)世界」不可區(qū)分；而由于在理想世界中不存在知識(shí)，所以可以推導(dǎo)出結(jié)論：現(xiàn)實(shí)世界滿足「零知識(shí)」。
我們繼續(xù)分析下一個(gè)交互系統(tǒng)（安全協(xié)議）的三個(gè)性質(zhì)：「完備性」、「可靠性」與「零知識(shí)」。
· 可靠性（Soundness）：Alice 在沒有知識(shí)的情況下不能通過 Bob 的驗(yàn)證。
· 完備性（Completeness）：Alice 在有知識(shí)的情況下可以通過 Bob 的驗(yàn)證。
· 零知識(shí)（Zero-knowledge）：Alice 在交互的過程中不會(huì)泄露關(guān)于知識(shí)的任何信息。
我們可以看出來「可靠性」和「完備性」有一種「對(duì)稱性」?？煽啃员ＷC了惡意的 Alice 一定失敗，而完備性保證了誠實(shí)的 Alice 一定成功。
「完備性」比較容易證明，只要 Alice 誠實(shí)，Bob 也誠實(shí)，那么皆大歡喜。這好比，寫好一段代碼，喂了一個(gè)測(cè)試用例，跑完通過收工。
我們來想想「可靠性」應(yīng)該如何定義？這個(gè)可靠性的逆否命題是：（在現(xiàn)實(shí)世界中）如果 Alice 能通過 Bob 的驗(yàn)證，那么 Alice 一定有知識(shí)?；蛘哒f：Alice 知道那……個(gè)「秘密」！
下面的問題是如何證明 Alice 知道一個(gè)「秘密」？
這好像也很難，對(duì)不對(duì)？假如我們需要證明一臺(tái)機(jī)器知道一個(gè)「秘密」，最簡(jiǎn)單的辦法就是我們?cè)跈C(jī)器的硬盤里，或者內(nèi)存中找到這個(gè)「秘密」，但是這樣暴露了秘密。如果這臺(tái)機(jī)器是黑盒子呢？或者是 Alice 呢？我們沒有讀心術(shù)，猜不到她心里的那個(gè)秘密。
如何定義「To Know」？
「零知識(shí)」保證了 驗(yàn)證者 Bob 沒有（計(jì)算）能力來把和「知識(shí)」有關(guān)的信息「抽取」出來。不能抽取的「知識(shí)」不代表不存在。「可靠性」保證了知識(shí)的「存在性」。
只有「知識(shí)」在存在的前提下，保證「零知識(shí)」才有意義。
為了進(jìn)一步分析「知識(shí)」，接下來首先介紹一個(gè)非常簡(jiǎn)潔，用途廣泛的零知識(shí)證明系統(tǒng) —— Schnorr 協(xié)議。這個(gè)協(xié)議代表了一大類的安全協(xié)議，所謂的 Σ-協(xié)議，而且 Schnorr 協(xié)議擴(kuò)展也是『零知識(shí)數(shù)據(jù)交換協(xié)議 zkPoD』［1］ 的核心技術(shù)之一。
簡(jiǎn)潔的 Schnorr 協(xié)議
Alice 擁有一個(gè)秘密數(shù)字，a，我們可以把這個(gè)數(shù)字想象成「私鑰」，然后把它「映射」到橢圓曲線群上的一個(gè)點(diǎn) a*G，簡(jiǎn)寫為 aG。這個(gè)點(diǎn)我們把它當(dāng)做「公鑰」。
sk = a
PK = aG
請(qǐng)注意「映射」這個(gè)詞，我們這里先簡(jiǎn)要介紹「同態(tài)」這個(gè)概念。橢圓曲線群有限域之間存在著一種同態(tài)映射關(guān)系。有限域，我們用 Zq 這個(gè)符號(hào)表示，其中素?cái)?shù) q是指有限域的大小，它是指從 0， 1， 2， …， q-1 這樣一個(gè)整數(shù)集合。而在一條橢圓曲線上，我們通過一個(gè)基點(diǎn)，G，可以產(chǎn)生一個(gè)「循環(huán)群」，標(biāo)記為 0G， G， 2G， …， （q-1）G，正好是數(shù)量為 q 個(gè) 曲線點(diǎn)的集合。任意兩個(gè)曲線點(diǎn)正好可以進(jìn)行一種「特殊的二元運(yùn)算」，G + G = 2G，2G + 3G = 5G，看起來這個(gè)二元運(yùn)算好像和「加法」類似，滿足交換律和結(jié)合律。于是我們就用 +這個(gè)符號(hào)來表示。之所以把這個(gè)群稱為循環(huán)群，因?yàn)榘讶旱淖詈笠粋€(gè)元素 （q-1）G，再加上一個(gè) G就回卷到群的第一個(gè)元素 0G。
給任意一個(gè)有限域上的整數(shù) r，我們就可以在循環(huán)群中找到一個(gè)對(duì)應(yīng)的點(diǎn) rG，或者用一個(gè)標(biāo)量乘法來表示 r*G。但是反過來計(jì)算是很「困難」的，這是一個(gè)「密碼學(xué)難題」—— 被稱為離散對(duì)數(shù)難題［2］。
也就是說，如果任意給一個(gè)橢圓曲線循環(huán)群上的點(diǎn) R，那么到底是有限域中的哪一個(gè)整數(shù)對(duì)應(yīng) R，這個(gè)計(jì)算是很難的，如果有限域足夠大，比如說 256bit 這么大，我們姑且可以認(rèn)為這個(gè)反向計(jì)算是不可能做到的。
Schnorr 協(xié)議充分利用了有限域和循環(huán)群之間單向映射，實(shí)現(xiàn)了最簡(jiǎn)單的零知識(shí)證明安全協(xié)議：Alice 向 Bob 證明她擁有 PK 對(duì)應(yīng)的私鑰 sk。
第一步：為了保證零知識(shí)，Alice 需要先產(chǎn)生一個(gè)隨機(jī)數(shù)，r，這個(gè)隨機(jī)數(shù)的用途是用來保護(hù)私鑰無法被 Bob 抽取出來。這個(gè)隨機(jī)數(shù)也需要映射到橢圓曲線群上，rG。
第二步：Bob 要提供一個(gè)隨機(jī)數(shù)進(jìn)行挑戰(zhàn)，我們把它稱為 c。
第三步：Alice 根據(jù)挑戰(zhàn)數(shù)計(jì)算 z = r + a * c，同時(shí)把 z發(fā)給 Bob，Bob通過下面的式子進(jìn)行檢驗(yàn)：z*G ？= R + c*PK = rG + c*（aG）
大家可以看到 Bob 在第三步「同態(tài)地」檢驗(yàn) z 的計(jì)算過程。如果這個(gè)式子成立，那么就能證明 Alice 確實(shí)有私鑰 a。
可是，這是為什么呢？
z 的計(jì)算和驗(yàn)證過程很有趣，有幾個(gè)關(guān)鍵技巧：
1. 首先 Bob 必須給出一個(gè)「隨機(jī)」挑戰(zhàn)數(shù)，然后 Bob 在橢圓曲線上同態(tài)地檢查 z 。如果我們把挑戰(zhàn)數(shù) c 看成是一個(gè)未知數(shù)，那么 r+a*c=z 可以看成是一個(gè)一元一次方程，其中 r 與 a 是方程系數(shù)。請(qǐng)注意在 c 未知的前提下，如果 r + a*x = r‘ + a’*x 要成立，那么根據(jù) Schwatz-Zippel 定理［3］，極大概率上 r=r‘，a=a’ 都成立。也就是說， Alice 在 c 未知的前提下，想找到另一對(duì)不同的 r‘，a’ 來計(jì)算 z 騙過 Bob 是幾乎不可能的。這個(gè)隨機(jī)挑戰(zhàn)數(shù) c 實(shí)現(xiàn)了r 和 a 的限制。雖然 Bob 隨機(jī)選了一個(gè)數(shù)，但是由于 Alice 事先不知道，所以 Alice 不得不使用私鑰 a 來計(jì)算 z。這里的關(guān)鍵： c 必須是個(gè)隨機(jī)數(shù)。
2. Bob 驗(yàn)證是在橢圓曲線群上完成。Bob 不知道r，但是他知道 r 映射到曲線上的點(diǎn)R；Bob 也不知道 a，但是他知道 a 映射到曲線群上的點(diǎn) PK，即 a*G。通過同態(tài)映射與Schwatz-Zippel 定理，Bob 可以校驗(yàn) z 的計(jì)算過程是否正確，從而知道 Alice 確實(shí)是通過 r 和 a 計(jì)算得出的 z，但是又不暴露 r 與 a 的值。
3. 還有，在協(xié)議第一步中產(chǎn)生的隨機(jī)數(shù) r 保證了 a 的保密性。因?yàn)槿魏我粋€(gè)秘密當(dāng)和一個(gè)符合「一致性分布」的隨機(jī)數(shù)相加之后的和仍然符合「一致性分布」。
證明零知識(shí)
我們這里看一下 Schnorr 協(xié)議如何證明一個(gè)弱一些的「零知識(shí)」性質(zhì)——「SHVZK」：
注：這里我們證明的僅僅是 Special Honest Verifier Zero-Knowledge（SHVZK）。SHVZK 要求協(xié)議中的 Bob 的行為不能不按常理出牌，比如他必須按協(xié)議約定，在第二步時(shí)，去傳送帶上取一個(gè)新鮮的隨機(jī)數(shù)，并且立即使用。而通常意義上的「零知識(shí)」是不會(huì)對(duì) Bob 做任何要求，所以我們說這里是一個(gè)弱一些的性質(zhì)。雖然目前 Schnorr 協(xié)議不能證明完全的「零知識(shí)」，但經(jīng)過添加一些協(xié)議步驟，就可以達(dá)到完全零知識(shí)的目的，細(xì)節(jié)這里不展開，有興趣的讀者請(qǐng)參考文獻(xiàn)［4］。以后我們?cè)谟懻?Fiat-Shamir 變換時(shí)，還會(huì)再次討論這個(gè)問題。
首先「模擬器」模擬一個(gè)「理想世界」，在理想世界中模擬出一個(gè) Zlice 和 Bob 對(duì)話，Zlice 沒有 Schnorr 協(xié)議中的知識(shí)，sk，而 Bob 是有公鑰 PK的。請(qǐng)大家看下圖，Bob 需要在 Schnorr 協(xié)議中的第二步出示一個(gè)隨機(jī)數(shù) c，這里有個(gè)額外的要求， 就是 Bob 只能「誠實(shí)地」從一個(gè)外部「隨機(jī)數(shù)傳送帶」上拿一個(gè)隨機(jī)數(shù)，每一個(gè)隨機(jī)數(shù)都必須是事先拋k次「硬幣」產(chǎn)生的一個(gè) 2^k 范圍內(nèi)的一次性分布隨機(jī)數(shù)。Bob 不能采用任何別的方式產(chǎn)生隨機(jī)數(shù)，這就是為何我們要求 Bob 是誠實(shí)的。
下面演示 Zlice 如何騙過 Bob：
序幕：請(qǐng)注意 Zlice 沒有關(guān)于 sk 的知識(shí)，這時(shí) Bob 的隨機(jī)數(shù)傳送帶上已經(jīng)預(yù)先放置了一些隨機(jī)數(shù)。
第一步：Zlice 產(chǎn)生一個(gè)一致性分布的隨機(jī)數(shù) c，并且利用一個(gè)新的「超能力」，將剛剛產(chǎn)生的隨機(jī)數(shù) c 替換掉 Bob 的隨機(jī)數(shù)傳送帶上第一個(gè)隨機(jī)數(shù)。這時(shí)候，Bob 無法察覺。
第二步：Zlice 再次產(chǎn)生一個(gè)隨機(jī)數(shù) z，然后計(jì)算 R‘=z*G - c*PK，并將 R’ 發(fā)送給 Bob。
第三步：這時(shí)候Bob 會(huì)從隨機(jī)數(shù)傳送帶上取得 c，并且將 c 發(fā)送給 Zlice。請(qǐng)注意這個(gè) c 正好就是第一步中 Zlice 產(chǎn)生的 c。
第四步：Zlice 將第三步產(chǎn)生的隨機(jī)數(shù) z 發(fā)送給 Bob，Bob 按照 Schnorr 協(xié)議的驗(yàn)證公式進(jìn)行驗(yàn)證，大家可以檢查下，這個(gè)公式完美成立。
大家可以再對(duì)比下「現(xiàn)實(shí)世界」的 Schnorr 協(xié)議，在兩個(gè)世界中，Bob 都能通過驗(yàn)證。
但區(qū)別是：
· 在「理想世界中」，Zlice 沒有 sk；而在「現(xiàn)實(shí)世界中」，Alice 有 sk
· 在「理想世界中」，z 是一個(gè)隨機(jī)數(shù)，沒有涉及 sk；而在「現(xiàn)實(shí)世界中」，z 的計(jì)算過程里面包含 sk
· 在「理想世界中」，Zlice 使用了超能力，替換了 Bob 的隨機(jī)數(shù)；而在「現(xiàn)實(shí)世界中」，Alice 看不到 Bob 的隨機(jī)數(shù)傳送帶，也無法更改傳送帶上的數(shù)字
這里請(qǐng)大家思考下：
Schnorr 協(xié)議中，Bob 在第二步發(fā)挑戰(zhàn)數(shù)能不能和第一步對(duì)調(diào)順序？也就是說 Bob 能不能先發(fā)挑戰(zhàn)數(shù)，然后 Alice 再發(fā)送 R = r*G。
（兩分鐘后……）
答案是不能。
如果 Alice 能提前知道隨機(jī)數(shù)，那么 （現(xiàn)實(shí)世界中的）Alice 就可以按照模擬器 Zlice 做法來欺騙 Bob。
再遇模擬器
其實(shí)，「可靠性」和「零知識(shí)」這兩個(gè)性質(zhì)在另一個(gè)維度上也是存在著一種對(duì)稱性?？煽啃员ＷC了惡意的 Alice 一定失敗，零知識(shí)保證了惡意的 Bob 一定不會(huì)成功。有趣地是，這種對(duì)稱性將體現(xiàn)在模擬出來的「理想世界」中。
我們分析下可靠性這個(gè)定義：Alice 沒有知識(shí)導(dǎo)致 Bob 驗(yàn)證失敗。它的逆否命題為：Bob 驗(yàn)證成功導(dǎo)致 Alice 一定有知識(shí)。
我們?cè)俅吻笾M器，讓他在可以發(fā)揮超能力的「理想世界」中，去檢驗(yàn) Alice 的知識(shí)。
再次，請(qǐng)大家設(shè)想在平行宇宙中，有兩個(gè)世界，一個(gè)是叫做「理想世界」，另一個(gè)叫做「現(xiàn)實(shí)世界」。理想世界有趣的地方在于它是被「模擬器」模擬出來的，同時(shí)模擬器可以在理想世界中放入帶有超能力的 NPC。這次把 Alice 的兩個(gè)分身同時(shí)放入「理想世界」與「現(xiàn)實(shí)世界」。
假設(shè)「你」扮演 Bob 的角色，你想知道和你對(duì)話的 Alice 是否真的是「可靠的」。于是把你放入「理想世界」，借助一個(gè)具有超能力的 NPC，你可以把對(duì)面的 Alice 的知識(shí)「抽取」出來。
W.。.hat？我們不是剛剛證明過：協(xié)議是零知識(shí)的嗎？零知識(shí)就意味著 Bob 抽取不出任何的「知識(shí)」碎片。這里敲黑板，「零知識(shí)」是對(duì)于「現(xiàn)實(shí)世界」而言的。我們現(xiàn)在正在討論的是神奇的「理想世界」。
重復(fù)一遍，在「理想世界」中，你可以借助一個(gè)有超能力的 NPC 來抽取 Alice 的知識(shí)，從而可以保證「現(xiàn)實(shí)世界」中的 Alice 無法作弊?？梢韵胂笠幌?，一個(gè)作弊的 Alice，她肯定沒有知識(shí)，沒有知識(shí)也就不可能在「理想世界」中讓 NPC 抽取到任何東西。
然而在「現(xiàn)實(shí)世界」中，你無法借助 NPC，當(dāng)然也就看不到 Alice 的知識(shí)，也就不會(huì)和「零知識(shí)」性質(zhì)沖突。因?yàn)閮蓚€(gè)世界發(fā)生的事件是「不可區(qū)分」的，我們可以得到這樣的結(jié)論：在「現(xiàn)實(shí)世界」中，Alice 一定是存在知識(shí)的。
整理一下思路：如何證明在一個(gè)交互會(huì)話中 Alice 不能作弊呢？我們需要為這個(gè)交互會(huì)話定義一個(gè)「模擬算法」，該算法可以模擬出一個(gè)「理想世界」，其中有一個(gè)特殊的角色叫做「抽取器」（Extractor），也就是我們前面說的 NPC，它能夠通過「超能力」來「抽取」Alice 的知識(shí)，但是讓對(duì)方「無所察覺」。
注意，超能力是必不可少的！這一點(diǎn)在『系列（二）理解「模擬」』有解釋，如果模擬器在沒有超能力的情況下具備作弊能力，那相當(dāng)于證明了協(xié)議「不可靠」（Unsoudness）。同樣地，如果「抽取器」在沒有超能力的情況下具備抽取信息能力，那相當(dāng)于證明了協(xié)議不零知（Not-zero-knowledge）。
最后一點(diǎn)，超能力是什么？
這個(gè)要取決于具體的交互系統(tǒng)的證明，我們接下來就先拿我們剛剛講過的Schnorr 協(xié)議切入。
Proof of Knowledge ：「知識(shí)證明」
我們來證明一下 Schnorr 協(xié)議的「可靠性」，看看這個(gè)超能力 NPC 如何在「理想世界」中把 Alice 私鑰抽取出來。而這個(gè)「超能力」，仍然是「時(shí)間倒流」。
第一步：Alice 選擇一個(gè)隨機(jī)數(shù) r，并且計(jì)算 R=r*G，并將 R 發(fā)給「抽取器」
第二步：抽取器也選擇一個(gè)隨機(jī)的挑戰(zhàn)數(shù)c，并且發(fā)給 Alice
第三步：Alice 計(jì)算并且回應(yīng) z，然后抽取器檢查 z是否正確
第四步：抽取器發(fā)現(xiàn) z 沒有問題之后，發(fā)動(dòng)超能力，將時(shí)間倒回第二步之前
第五步：抽取器再次發(fā)送一個(gè)不同的隨機(jī)挑戰(zhàn)數(shù) c‘給 Alice，這時(shí)候 Alice 回到第二步，會(huì)有一種似曾相識(shí)的感覺，但是無法感知到時(shí)間倒回這個(gè)事實(shí)
第六步：Alice 再次計(jì)算了 z’，然后發(fā)給抽取器檢查
第七步：這時(shí)候抽取器有了z 和 z‘，就可以直接推算出 Alice 所擁有的私鑰 a，達(dá)成「知識(shí)抽取」
到這里，「可靠性」就基本證明完了。大家是不是對(duì)可靠性和零知性的「對(duì)稱性」有點(diǎn)感覺了？
總結(jié)一下：「抽取器」在「理想世界」中，通過時(shí)間倒流的超能力，把 Alice 的「知識(shí)」完整地「抽取」出來，這就保證了一個(gè)沒有知識(shí)的 Alice 是無法讓抽取器達(dá)成目標(biāo)，從而證明了「可靠性」。
注：并不是所有的可靠性都必須要求存在抽取器算法。采用抽取器來證明可靠性的證明系統(tǒng)被稱為「Proof of Knowledge」。
解讀 ECDSA 簽名攻擊
在區(qū)塊鏈系統(tǒng)中到處可見的ECDSA 簽名方案也是一個(gè)樸素的零知識(shí)證明系統(tǒng)。橢圓曲線數(shù)字簽名方案 ECDSA 與 Schnorr 協(xié)議非常接近，基于 Schnorr 協(xié)議的簽名方案發(fā)表在 1991年的『密碼學(xué)雜志』［5］上。1991年，正值美國國家標(biāo)準(zhǔn)局（NIST）選擇數(shù)字簽名算法，優(yōu)雅的 Schnorr 簽名方案居然被申請(qǐng)了專利，因此 NIST 提出了另一套簽名方案 DSA（Digital Signature Algorithm），隨后這個(gè)方案支持了橢圓曲線，于是被稱為 ECDSA。中本聰在構(gòu)思比特幣時(shí)，選擇了 ECDSA 作為簽名算法，但是曲線并沒有選擇 NIST 標(biāo)準(zhǔn)推薦的橢圓曲線 —— secp256-r1，而是 secp256-k1。因?yàn)榻餮裕琋IST 可能在橢圓曲線參數(shù)選擇上做了手腳，導(dǎo)致某些機(jī)構(gòu)可以用不為人知的辦法求解離散對(duì)數(shù)難題，從而有能力在「現(xiàn)實(shí)世界」中具備超能力。有不少人在懷疑，也許當(dāng)年中本聰在設(shè)計(jì)比特幣時(shí)，也有這種考慮，故意選擇了 secp256-k1 這樣一條貌似安全性稍弱的曲線。
我們拆解下 ECDSA 簽名，用交互的方式定義一個(gè)類似 ECDSA 的認(rèn)證方案，交互見下圖。
第一步：Alice 仍然是選擇一個(gè)隨機(jī)數(shù) k，并將 k 映射到橢圓曲線上，得到點(diǎn) K ，然后發(fā)送給 Bob
第二步：Bob 需要產(chǎn)生兩個(gè)隨機(jī)數(shù)，c 和 e，然后交給 Alice
第三步：Alice 計(jì)算 s，并且發(fā)送給 Bob，他來驗(yàn)證 s 的計(jì)算過程是否正確
注：對(duì)熟悉 ECDSA 簽名方案的讀者，這里略作解釋，Bob 產(chǎn)生的 c 對(duì)應(yīng)被簽消息的 Hash 值 Hash（m），而 e 則是由一個(gè)轉(zhuǎn)換函數(shù) F（K）來產(chǎn)生。其中 F（。） 是取橢圓曲線上的點(diǎn)的 x 坐標(biāo)經(jīng)過 （mod q） 得到［6］。
江湖上流傳著一個(gè)說法：ECDSA 簽名方案有個(gè)嚴(yán)重的安全隱患，如果在兩次簽名中使用了同一個(gè)隨機(jī)數(shù)，那么簽名者的私鑰將會(huì)暴露出來。其實(shí) Schnorr 簽名方案也有同樣的問題。
當(dāng)年 Sony PlayStation 3 的工程師在調(diào)用 ECDSA 庫函數(shù)時(shí)，本來應(yīng)該輸入隨機(jī)數(shù)的參數(shù)位置上，卻傳入了一個(gè)常數(shù)。熟悉密碼學(xué)的黑客們發(fā)現(xiàn)了這個(gè)嚴(yán)重的后門。2011年1月，神奇小子 Geohot 公開發(fā)布了 Sony PS3 的主私鑰，這意味著任何用戶都可以輕松拿到游戲機(jī)的 root 權(quán)限。Sony 隨后大為光火…… （后續(xù)故事大家可以上網(wǎng)搜）
如果 Alice 在兩次交互過程中使用了同一個(gè) K，那么 Bob 可以通過發(fā)送兩個(gè)不同的 c 和 c’ 來得到 s 和 s‘，然后通過下面的公式算出私鑰 a：
k = （c - c’）/（s - s‘）
a = （k * s - c）/e
那么我們應(yīng)該怎么來看這個(gè)「安全后門」呢？大家想想看，這個(gè)安全后門和我們前面證明過的 Schnorr 協(xié)議的可靠性證明幾乎一模一樣！這個(gè)算法正是 ECDSA 認(rèn)證協(xié)議的「可靠性」證明中的「抽取器」算法。只不過在可靠性證明中，為了讓 Alice 使用同一個(gè)隨機(jī)數(shù) k 來認(rèn)證兩次，「抽取器」需要利用「時(shí)間倒流」的超能力。
但是在 Sony PS3 系統(tǒng)中，隨機(jī)數(shù)被不明所以的工程師寫成了一個(gè)固定不變的值，這樣相當(dāng)于直接賦予了黑客「超能力」，而這是在「現(xiàn)實(shí)世界」中?；蛘哒f，黑客在不需要「時(shí)間倒流」的情況下就能實(shí)現(xiàn)「抽取器」。
提醒下，不僅僅是隨機(jī)數(shù)不能重復(fù)的問題。而是隨機(jī)數(shù)必須是具有密碼學(xué)安全強(qiáng)度的隨機(jī)數(shù)。
設(shè)想下，如果隨機(jī)數(shù) r 是通過一個(gè)利用「線性同余」原理的偽隨機(jī)數(shù)生成器產(chǎn)生，雖然 r的值一直在變化，但是仍然不能阻止「知識(shí)抽取」。假設(shè)線性同余算法為 r2= d*r1 + e （mod m），還回到 Schnorr 協(xié)議的第三步：
1： z1 = r1 + c1*a
2： z2 = r2 + c2*a
如果攻擊者讓 Alice 連續(xù)做兩次簽名，那么將 r2 代入 r1 之后，就出現(xiàn)了兩個(gè)線性方程求解兩個(gè)未知數(shù) （r1， a） 的情況，z1， z2， c1， c2， d， e 對(duì)于 攻擊者是已知的，這個(gè)方程組只用初中數(shù)學(xué)知識(shí)就可以求解。
請(qǐng)注意，這并不是 Schnorr 協(xié)議（或 ECDSA 協(xié)議）的「設(shè)計(jì)缺陷」，恰恰相反，這是 Schnorr 協(xié)議設(shè)計(jì)比較精巧的地方，它從原理上保證了協(xié)議的可靠性。類似技巧在密碼學(xué)協(xié)議中頻繁出現(xiàn)，達(dá)到一目了然的「簡(jiǎn)潔」。但是也不得不說，如果不清楚協(xié)議的內(nèi)在機(jī)制，尤其是區(qū)分不清楚「理想世界」與「現(xiàn)實(shí)世界」，使用者很容易引入各種花式的「安全漏洞」。
作為一個(gè)能寫出安全可靠軟件的負(fù)責(zé)任的碼農(nóng)，我們需要了解哪些？徹底理解安全協(xié)議的設(shè)計(jì)機(jī)制當(dāng)然是最好的，但是絕大多數(shù)情況下這是不現(xiàn)實(shí)的。一般來說，我們把各種密碼學(xué)工具當(dāng)做「黑盒」來用，但這可能是不夠的，我們最好能了解下：
「安全定義」是什么？
「安全假設(shè)」到底是什么？
「理想世界」中的「超能力」到底是什么？
腦洞：我們生活在模擬世界中嗎
第一次讀懂「模擬器」時(shí)，我第一時(shí)間想到的是電影『黑客帝國』。我們生活所在「現(xiàn)實(shí)世界」也許是某一個(gè)模擬器模擬出來的「理想世界」，我們所看到、聽到的以及感知到的一切都是被「模擬」出來的。在「現(xiàn)實(shí)世界」里，我們活在一個(gè)母體中。然而我們并不能意識(shí)到這一點(diǎn)。
早在春秋戰(zhàn)國時(shí)期，莊子也在思考類似的問題：
昔者莊周夢(mèng)為胡蝶，栩栩然胡蝶也。自喻適志與！不知周也。俄然覺，則蘧蘧然周也。不知周之夢(mèng)為胡蝶與？胡蝶之夢(mèng)為周與？周與胡蝶則必有分矣。此之謂物化?！肚f子·齊物論》
通俗地解釋下：莊子有一天睡著了，夢(mèng)見自己變成了一只蝴蝶，翩翩起舞，醒來之后發(fā)現(xiàn)自己還是莊子，在夢(mèng)中，蝴蝶并不知道自己是莊子。于是莊子沉思到底是他夢(mèng)中變成了蝴蝶，還是蝴蝶夢(mèng)中變成了莊子呢？如果夢(mèng)境足夠真實(shí)，……
「缸中之腦」是美國哲學(xué)家 Gilbert Harman 提出的這樣一個(gè)想法：一個(gè)人的大腦可以被放入一個(gè)容器里面，然后插上電線，通過模擬各種電信號(hào)輸入，使得大腦以為自己活在真實(shí)世界中。
這個(gè)想法源自哲學(xué)家笛卡爾的《第一哲學(xué)沉思集》［7］，在書中他論證我們應(yīng)該懷疑一切，需要逐一檢驗(yàn)所有人類的知識(shí)，數(shù)學(xué)，幾何，以及感知到的世界。然而他發(fā)現(xiàn)除了「我思故我在」之外，所有的知識(shí)都可能不靠譜，因?yàn)槲覀兊拇竽X很可能被一個(gè)具有「超能力」的 Evil Demon 所欺騙。
2003 年牛津大學(xué)的哲學(xué)教授 Nick Bostrom 鄭重其事地寫了一篇論文『我們生活在計(jì)算機(jī)模擬世界中嗎？』［8］。認(rèn)為以下三個(gè)事實(shí)中，至少有一個(gè)成立：
1. 人類文明徹底滅絕。
2. 人類文明已經(jīng)到達(dá)可以完全模擬現(xiàn)實(shí)世界的科技水平，但是處于某種原因，沒有一個(gè)人愿意去創(chuàng)造出一個(gè)新的模擬世界，充當(dāng)上帝的角色。
3. 我們現(xiàn)在的人類文明就生活在一個(gè)模擬世界中。
硅谷企業(yè)家 Elon Musk 在一次公開采訪中，談到「我們生活在基礎(chǔ)現(xiàn)實(shí)世界」的概率只有「十億分之一」。也就是說，他認(rèn)為我們生活在一個(gè)電腦游戲（模擬世界）中，在模擬世界之外，有一個(gè)程序員，他開發(fā)并操縱了這個(gè)世界，我們每個(gè)人都是一個(gè)游戲角色（ NPC）。
在玩膩越獄 iPhone 和自動(dòng)駕駛之后，神奇小子 Geohot 在今年三月份的「西南偏南」大會(huì)上做了一個(gè)題為「Jailbreaking the Simulation」的演講［9］。他認(rèn)為，我們被生活在一個(gè)模擬世界中，所謂的上帝就是外部世界里活蹦亂跳的碼農(nóng)們，他們編程創(chuàng)造了我們的「現(xiàn)實(shí)世界」，當(dāng)然，他們可能啟動(dòng)了不止一個(gè)世界副本。然而，他們可能也生活在一個(gè)外層「模擬世界」中。
如果我們確實(shí)生活在模擬世界中，或許我們可以在地球的某個(gè)地方找到一個(gè)后門——「Simulation Trapdoor」，從而獲得「模擬器」的超能力，抽取出不可思議的「秘密知識(shí)」。
如果我們的世界的確是被程序模擬出來的，這個(gè)程序也許會(huì)有 Bug，如果有 Bug 存在，說不定我們可以利用這個(gè) Bug 進(jìn)行越獄，跳出「理想世界」，到達(dá)外面一層的世界中，與可愛的碼農(nóng)上帝聊一聊。
這是在開玩笑嗎？下面摘自自知乎的一個(gè)段子［10］：
如果世界是虛擬的，有哪些實(shí)例可以證明？
1.為什么宏觀上豐富多彩，但是微觀的基本粒子卻都是一模一樣的？這正和圖片富多彩，但是像素是一模一樣的一回事
2.為什么光速有上限？因?yàn)闄C(jī)器的運(yùn)行速度有限
3.為什么會(huì)有普朗克常量？因?yàn)闄C(jī)器的數(shù)據(jù)精度有限
4.為什么微觀粒子都是幾率云？這是為了避免系統(tǒng)陷入循環(huán)而增加的隨機(jī)擾動(dòng)
5.為什么有泡利不相容原理？看來系統(tǒng)采用的數(shù)據(jù)組織是多維數(shù)組
6.為什么量子計(jì)算機(jī)運(yùn)行速度那么快，一瞬間可以嘗試所有可能？因?yàn)檫@個(gè)本質(zhì)上是調(diào)用了宿主機(jī)的接口
7.為什么會(huì)有量子糾纏？這實(shí)際上是引用同一個(gè)對(duì)象的兩個(gè)指針
8.為什么會(huì)有觀察者效應(yīng)？這顯然是lazy updating
9.為什么時(shí)間有開端？系統(tǒng)有啟動(dòng)時(shí)間
未完待續(xù)
設(shè)計(jì)一個(gè)密碼學(xué)協(xié)議就好像在走鋼絲，如果你想同時(shí)做到「零知識(shí)」和「可靠性」就意味著既要讓協(xié)議內(nèi)容充分隨機(jī)，又要保證「知識(shí)」能夠參與協(xié)議的交互。如果協(xié)議沒有正確設(shè)計(jì)，亦或沒有正確工程實(shí)現(xiàn)，都將導(dǎo)致系統(tǒng)安全性坍塌。比如可能破壞了零知性，導(dǎo)致「知識(shí)」在不經(jīng)意間泄露；或者也許破壞了可靠性，導(dǎo)致任何人都能偽造證明。而且這種安全性，遠(yuǎn)比傳統(tǒng)的代碼底層機(jī)制漏洞來得更加嚴(yán)重，并且更難被發(fā)現(xiàn)。嚴(yán)格數(shù)學(xué)論證，這似乎是必不可少的。
我們的世界真的是某個(gè)「三體文明」模擬出來的嗎？不能排除這個(gè)可能性，或許，我們需要認(rèn)真地重新審視自己的各種執(zhí)念。不過那又怎么樣呢？至少自己的「思想」是真實(shí)的。
工商網(wǎng)監(jiān)
評(píng)論