二級標題

二級標題

• 二級標題

• 我們在許多介紹零知識證明的文章中都能看到這樣三個性質：

• Soundness —— 可靠性

Completeness —— 完備性

Zero-Knowledge —— 零知識在『但是少有文章深入解釋這個特性背後的深意和洞見。

在『

Rather than giving a list of the events that are not allowed to occur, it (the definition of zero-knowledge proof) gives a maximalist simulation condition.

— Boaz Barak

系列（二）理解「模擬」

』一文中，我們介紹了「模擬器」這個概念。許多介紹文章避而不談「模擬」，但「模擬」可以說是安全協議中核心的核心，因為它是定義「安全性」的重要武器。

通常，我們定義安全會採用這樣一種方式，首先列出一些安全事件，然後說明：如果一個系統安全，那麼列出來的安全事件都不會發生。

• 借用密碼學家Boaz Barak 的話，翻譯一下，「零知識證明」並不是通過給出一個不允許發生的事件列表來定義，而是直接給出了一個最極致的「模擬條件」。

• 所謂「模擬條件」是指，通過「模擬」方法來實現一個「理想世界」，使之與「現實世界」不可區分；而由於在理想世界中不存在知識，所以可以推導出結論：現實世界滿足「零知識」。

• 我們繼續分析下一個交互系統（安全協議）的三個性質：「完備性」、「可靠性」與「零知識」。

可靠性（Soundness）：Alice 在沒有知識的情況下不能通過Bob 的驗證。

完備性（Completeness）：Alice 在有知識的情況下可以通過Bob 的驗證。

零知識（Zero-knowledge）：Alice 在交互的過程中不會洩露關於知識的任何信息。

我們可以看出來「可靠性」和「完備性」有一種「對稱性」。可靠性保證了惡意的Alice 一定失敗，而完備性保證了誠實的Alice 一定成功。

「完備性」比較容易證明，只要Alice 誠實，Bob 也誠實，那麼皆大歡喜。這好比，寫好一段代碼，餵了一個測試用例，跑完通過收工。

我們來想想「可靠性」應該如何定義？這個可靠性的逆否命題是：（在現實世界中）如果Alice 能通過Bob 的驗證，那麼Alice 一定有知識。或者說：Alice 知道那……個「秘密」！

下面的問題是如何證明Alice 知道一個「秘密」？

這好像也很難，對不對？假如我們需要證明一台機器知道一個「秘密」，最簡單的辦法就是我們在機器的硬盤裡，或者內存中找到這個「秘密」，但是這樣暴露了秘密。如果這台機器是黑盒子呢？或者是Alice 呢？我們沒有讀心術，猜不到她心裡的那個秘密。

如何定義「To Know」？

「零知識」保證了驗證者Bob 沒有（計算）能力來把和「知識」有關的信息「抽取」出來。不能抽取的「知識」不代表不存在。 「可靠性」保證了知識的「存在性」。只有「知識」在存在的前提下，保證「零知識」才有意義。』[1] 的核心技術之一。

二級標題

二級標題

• sk = a

• PK = aG

二級標題

簡潔的Schnorr 協議

Alice 擁有一個秘密數字，a，我們可以把這個數字想像成「私鑰」，然後把它「映射」到橢圓曲線群上的一個點a*G，簡寫為aG。這個點我們把它當做「公鑰」。

請注意「映射」這個詞，我們這裡先簡要介紹「同態」這個概念。橢圓曲線群有限域之間存在著一種同態映射關係。有限域，我們用Zq 這個符號表示，其中素數q是指有限域的大小，它是指從0, 1, 2, …, q-1 這樣一個整數集合。而在一條橢圓曲線上，我們通過一個基點，G，可以產生一個「循環群」，標記為0G, G, 2G, …, (q-1)G，正好是數量為q 個曲線點的集合。任意兩個曲線點正好可以進行一種「特殊的二元運算」，G + G = 2G，2G + 3G = 5G，看起來這個二元運算好像和「加法」類似，滿足交換律和結合律。於是我們就用+這個符號來表示。之所以把這個群稱為循環群，因為把群的最後一個元素(q-1)G，再加上一個G就回捲到群的第一個元素0G。

給任意一個有限域上的整數r，我們就可以在循環群中找到一個對應的點rG，或者用一個標量乘法來表示r*G。但是反過來計算是很「困難」的，這是一個「密碼學難題」—— 被稱為離散對數難題[2]。

也就是說，如果任意給一個橢圓曲線循環群上的點R，那麼到底是有限域中的哪一個整數對應R，這個計算是很難的，如果有限域足夠大，比如說256bit 這麼大，我們姑且可以認為這個反向計算是不可能做到的。

Schnorr 協議充分利用了有限域和循環群之間單向映射，實現了最簡單的零知識證明安全協議：Alice 向Bob 證明她擁有PK 對應的私鑰sk。

第一步：為了保證零知識，Alice 需要先產生一個隨機數，r，這個隨機數的用途是用來保護私鑰無法被Bob 抽取出來。這個隨機數也需要映射到橢圓曲線群上，rG。

第二步：Bob 要提供一個隨機數進行挑戰，我們把它稱為c。

第三步：Alice 根據挑戰數計算z = r + a * c，同時把z發給Bob，Bob通過下面的式子進行檢驗：z*G ?= R + c*PK = rG + c*(aG )

• 大家可以看到Bob 在第三步「同態地」檢驗z 的計算過程。如果這個式子成立，那麼就能證明Alice 確實有私鑰a。

• 可是，這是為什麼呢？

• 還有，在協議第一步中產生的隨機數r 保證了a 的保密性。因為任何一個秘密當和一個符合「一致性分佈」的隨機數相加之後的和仍然符合「一致性分佈」。

二級標題

二級標題

二級標題

證明零知識

我們這裡看一下Schnorr 協議如何證明一個弱一些的「零知識」性質——「SHVZK」：

注：這裡我們證明的僅僅是Special Honest Verifier Zero-Knowledge（SHVZK）。 SHVZK 要求協議中的Bob 的行為不能不按常理出牌，比如他必須按協議約定，在第二步時，去傳送帶上取一個新鮮的隨機數，並且立即使用。而通常意義上的「零知識」是不會對Bob 做任何要求，所以我們說這裡是一個弱一些的性質。雖然目前Schnorr 協議不能證明完全的「零知識」，但經過添加一些協議步驟，就可以達到完全零知識的目的，細節這裡不展開，有興趣的讀者請參考文獻[4]。以後我們在討論Fiat-Shamir 變換時，還會再次討論這個問題。

首先「模擬器」模擬一個「理想世界」，在理想世界中模擬出一個Zlice 和Bob 對話，Zlice 沒有Schnorr 協議中的知識，sk，而Bob 是有公鑰PK的。請大家看下圖，Bob 需要在Schnorr 協議中的第二步出示一個隨機數c，這裡有個額外的要求， 就是Bob 只能「誠實地」從一個外部「隨機數傳送帶」上拿一個隨機數，每一個隨機數都必須是事先拋k次「硬幣」產生的一個2^k 範圍內的一次性分佈隨機數。 Bob 不能採用任何別的方式產生隨機數，這就是為何我們要求Bob 是誠實的。

序幕：請注意Zlice 沒有關於sk 的知識，這時Bob 的隨機數傳送帶上已經預先放置了一些隨機數。

第一步：Zlice 產生一個一致性分佈的隨機數c，並且利用一個新的「超能力」，將剛剛產生的隨機數c替換掉Bob 的隨機數傳送帶上第一個隨機數。這時候，Bob 無法察覺。

第二步：Zlice 再次產生一個隨機數z，然後計算R'=z*G - c*PK，並將R' 發送給Bob。

第三步：這時候Bob 會從隨機數傳送帶上取得c，並且將c 發送給Zlice。請注意這個c 正好就是第一步中Zlice 產生的c。

• 第四步：Zlice 將第三步產生的隨機數z 發送給Bob，Bob 按照Schnorr 協議的驗證公式進行驗證，大家可以檢查下，這個公式完美成立。

• 大家可以再對比下「現實世界」的Schnorr 協議，在兩個世界中，Bob 都能通過驗證。

• 但區別是：

在「理想世界中」，Zlice 沒有sk；而在「現實世界中」，Alice 有sk

Q

在「理想世界中」，z 是一個隨機數，沒有涉及sk；而在「現實世界中」，z 的計算過程裡麵包含sk

這裡請大家思考下：

答案是不能。

如果Alice 能提前知道隨機數，那麼（現實世界中的）Alice 就可以按照模擬器Zlice 做法來欺騙Bob。

二級標題

二級標題

二級標題

再遇模擬器

其實，「可靠性」和「零知識」這兩個性質在另一個維度上也是存在著一種對稱性。可靠性保證了惡意的Alice 一定失敗，零知識保證了惡意的Bob 一定不會成功。有趣地是，這種對稱性將體現在模擬出來的「理想世界」中。

我們分析下可靠性這個定義：Alice 沒有知識導致Bob 驗證失敗。它的逆否命題為：Bob 驗證成功導致Alice 一定有知識。

我們再次求助模擬器，讓他在可以發揮超能力的「理想世界」中，去檢驗Alice 的知識。

再次，請大家設想在平行宇宙中，有兩個世界，一個是叫做「理想世界」，另一個叫做「現實世界」。理想世界有趣的地方在於它是被「模擬器」模擬出來的，同時模擬器可以在理想世界中放入帶有超能力的NPC。這次把Alice 的兩個分身同時放入「理想世界」與「現實世界」。

假設「你」扮演Bob 的角色，你想知道和你對話的Alice 是否真的是「可靠的」。於是把你放入「理想世界」，借助一個具有超能力的NPC，你可以把對面的Alice 的知識「抽取」出來。

W...hat？我們不是剛剛證明過：協議是零知識的嗎？零知識就意味著Bob 抽取不出任何的「知識」碎片。這裡敲黑板，「零知識」是對於「現實世界」而言的。我們現在正在討論的是神奇的「理想世界」。

重複一遍，在「理想世界」中，你可以藉助一個有超能力的NPC 來抽取Alice 的知識，從而可以保證「現實世界」中的Alice 無法作弊。可以想像一下，一個作弊的Alice，她肯定沒有知識，沒有知識也就不可能在「理想世界」中讓NPC 抽取到任何東西。然而在「現實世界」中，你無法借助NPC，當然也就看不到Alice 的知識，也就不會和「零知識」性質衝突。因為兩個世界發生的事件是「不可區分」的，我們可以得到這樣的結論：在「現實世界」中，Alice 一定是存在知識的。整理一下思路：如何證明在一個交互會話中Alice 不能作弊呢？我們需要為這個交互會話定義一個「模擬算法」，該算法可以模擬出一個「理想世界」，其中有一個特殊的角色叫做「抽取器」(Extractor)，也就是我們前面說的NPC，它能夠通過「超能力」來「抽取」Alice 的知識，但是讓對方「無所察覺」。

注意，超能力是必不可少的！這一點在『

這個要取決於具體的交互系統的證明，我們接下來就先拿我們剛剛講過的Schnorr 協議切入。

二級標題

二級標題

二級標題

Proof of Knowledge ：「知識證明」

我們來證明一下Schnorr 協議的「可靠性」，看看這個超能力NPC 如何在「理想世界」中把Alice 私鑰抽取出來。而這個「超能力」，仍然是「時間倒流」。

第一步：Alice 選擇一個隨機數r，並且計算R=r*G，並將R 發給「抽取器」

第二步：抽取器也選擇一個隨機的挑戰數c，並且發給Alice

第三步：Alice 計算並且回應z，然後抽取器檢查z是否正確

第四步：抽取器發現z 沒有問題之後，發動超能力，將時間倒回第二步之前

第五步：抽取器再次發送一個不同的隨機挑戰數c'給Alice，這時候Alice 回到第二步，會有一種似曾相識的感覺，但是無法感知到時間倒回這個事實

第六步：Alice 再次計算了z'，然後發給抽取器檢查

注：並不是所有的可靠性都必須要求存在抽取器算法。採用抽取器來證明可靠性的證明系統被稱為「Proof of Knowledge」。

二級標題

二級標題

二級標題

解讀ECDSA 簽名攻擊

在區塊鏈系統中到處可見的ECDSA 簽名方案也是一個樸素的零知識證明系統。橢圓曲線數字簽名方案ECDSA 與Schnorr 協議非常接近，基於Schnorr 協議的簽名方案發表在1991年的『密碼學雜誌』[5]上。 1991年，正值美國國家標準局（NIST）選擇數字簽名算法，優雅的Schnorr 簽名方案居然被申請了專利，因此NIST 提出了另一套簽名方案DSA（Digital Signature Algorithm），隨後這個方案支持了橢圓曲線，於是被稱為ECDSA。中本聰在構思比特幣時，選擇了ECDSA 作為簽名算法，但是曲線並沒有選擇NIST 標準推薦的橢圓曲線—— secp256-r1，而是secp256-k1。因為江湖傳言，NIST 可能在橢圓曲線參數選擇上做了手腳，導致某些機構可以用不為人知的辦法求解離散對數難題，從而有能力在「現實世界」中具備超能力。有不少人在懷疑，也許當年中本聰在設計比特幣時，也有這種考慮，故意選擇了secp256-k1 這樣一條貌似安全性稍弱的曲線。

我們拆解下ECDSA 簽名，用交互的方式定義一個類似ECDSA 的認證方案，交互見下圖。

第一步：Alice 仍然是選擇一個隨機數k，並將k 映射到橢圓曲線上，得到點K ，然後發送給Bob

第二步：Bob 需要產生兩個隨機數，c 和e，然後交給Alice

第三步：Alice 計算s，並且發送給Bob，他來驗證s 的計算過程是否正確

注：對熟悉ECDSA 簽名方案的讀者，這里略作解釋，Bob 產生的c 對應被簽消息的Hash值Hash(m)，而e 則是由一個轉換函數F(K)來產生。其中F(.) 是取橢圓曲線上的點的x 坐標經過(mod q) 得到[6]。

k = (c - c')/(s - s')a = (k * s - c)/e

江湖上流傳著一個說法：ECDSA 簽名方案有個嚴重的安全隱患，如果在兩次簽名中使用了同一個隨機數，那麼簽名者的私鑰將會暴露出來。其實Schnorr 簽名方案也有同樣的問題。

當年Sony PlayStation 3 的工程師在調用ECDSA 庫函數時，本來應該輸入隨機數的參數位置上，卻傳入了一個常數。熟悉密碼學的黑客們發現了這個嚴重的後門。 2011年1月，神奇小子Geohot 公開發布了Sony PS3 的主私鑰，這意味著任何用戶都可以輕鬆拿到遊戲機的root 權限。 Sony 隨後大為光火…… （後續故事大家可以上網搜）

如果Alice 在兩次交互過程中使用了同一個K，那麼Bob 可以通過發送兩個不同的c 和c' 來得到s 和s'，然後通過下面的公式算出私鑰a：

那麼我們應該怎麼來看這個「安全後門」呢？大家想想看，這個安全後門和我們前面證明過的Schnorr 協議的可靠性證明幾乎一模一樣！這個算法正是ECDSA 認證協議的「可靠性」證明中的「抽取器」算法。只不過在可靠性證明中，為了讓Alice 使用同一個隨機數k 來認證兩次，「抽取器」需要利用「時間倒流」的超能力。

1: z1 = r1 + c1*a2: z2 = r2 + c2*a

但是在Sony PS3 系統中，隨機數被不明所以的工程師寫成了一個固定不變的值，這樣相當於直接賦予了黑客「超能力」，而這是在「現實世界」中。或者說，黑客在不需要「時間倒流」的情況下就能實現「抽取器」。

提醒下，不僅僅是隨機數不能重複的問題。而是隨機數必須是具有密碼學安全強度的隨機數。

設想下，如果隨機數r 是通過一個利用「線性同餘」原理的偽隨機數生成器產生，雖然r的值一直在變化，但是仍然不能阻止「知識抽取」。假設線性同餘算法為r2= d*r1 + e (mod m)，還回到Schnorr 協議的第三步：

• 如果攻擊者讓Alice 連續做兩次簽名，那麼將r2 代入r1 之後，就出現了兩個線性方程求解兩個未知數(r1, a) 的情況，z1, z2, c1, c2, d, e 對於攻擊者是已知的，這個方程組只用初中數學知識就可以求解。

• 請注意，這並不是Schnorr 協議（或ECDSA 協議）的「設計缺陷」，恰恰相反，這是Schnorr 協議設計比較精巧的地方，它從原理上保證了協議的可靠性。類似技巧在密碼學協議中頻繁出現，達到一目了然的「簡潔」。但是也不得不說，如果不清楚協議的內在機制，尤其是區分不清楚「理想世界」與「現實世界」，使用者很容易引入各種花式的「安全漏洞」。

• 「理想世界」中的「超能力」到底是什麼？

二級標題

二級標題

二級標題

腦洞：我們生活在模擬世界中嗎

第一次讀懂「模擬器」時，我第一時間想到的是電影『黑客帝國』。我們生活所在「現實世界」也許是某一個模擬器模擬出來的「理想世界」，我們所看到、聽到的以及感知到的一切都是被「模擬」出來的。在「現實世界」裡，我們活在一個母體中。然而我們並不能意識到這一點。

早在春秋戰國時期，莊子也在思考類似的問題：

昔者莊週夢為胡蝶，栩栩然胡蝶也。自喻適志與！不知周也。俄然覺，則蘧蘧然周也。不知周之夢為胡蝶與？胡蝶之夢為週與？週與胡蝶則必有分矣。此之謂物化。

——《莊子·齊物論》

通俗地解釋下：莊子有一天睡著了，夢見自己變成了一隻蝴蝶，翩翩起舞，醒來之後發現自己還是莊子，在夢中，蝴蝶並不知道自己是莊子。於是莊子沉思到底是他夢中變成了蝴蝶，還是蝴蝶夢中變成了莊子呢？如果夢境足夠真實，……

• 「缸中之腦」是美國哲學家Gilbert Harman 提出的這樣一個想法：一個人的大腦可以被放入一個容器裡面，然後插上電線，通過模擬各種電信號輸入，使得大腦以為自己活在真實世界中。

• 這個想法源自哲學家笛卡爾的《第一哲學沉思集》[7]，在書中他論證我們應該懷疑一切，需要逐一檢驗所有人類的知識，數學，幾何，以及感知到的世界。然而他發現除了「我思故我在」之外，所有的知識都可能不靠譜，因為我們的大腦很可能被一個具有「超能力」的Evil Demon 所欺騙。

• 2003 年牛津大學的哲學教授Nick Bostrom 鄭重其事地寫了一篇論文『我們生活在計算機模擬世界中嗎？ 』[8]。認為以下三個事實中，至少有一個成立：

人類文明徹底滅絕。

人類文明已經到達可以完全模擬現實世界的科技水平，但是處於某種原因，沒有一個人願意去創造出一個新的模擬世界，充當上帝的角色。

我們現在的人類文明就生活在一個模擬世界中。

矽谷企業家Elon Musk 在一次公開採訪中，談到「我們生活在基礎現實世界」的概率只有「十億分之一」。也就是說，他認為我們生活在一個電腦遊戲（模擬世界）中，在模擬世界之外，有一個程序員，他開發並操縱了這個世界，我們每個人都是一個遊戲角色（ NPC）。

在玩膩越獄iPhone 和自動駕駛之後，神奇小子Geohot 在今年三月份的「西南偏南」大會上做了一個題為「Jailbreaking the Simulation」的演講[9]。他認為，我們被生活在一個模擬世界中，所謂的上帝就是外部世界里活蹦亂跳的碼農們，他們編程創造了我們的「現實世界」，當然，他們可能啟動了不止一個世界副本。然而，他們可能也生活在一個外層「模擬世界」中。

如果我們確實生活在模擬世界中，或許我們可以在地球的某個地方找到一個後門——「Simulation Trapdoor」，從而獲得「模擬器」的超能力，抽取出不可思議的「秘密知識」。

如果我們的世界的確是被程序模擬出來的，這個程序也許會有Bug，如果有Bug 存在，說不定我們可以利用這個Bug 進行越獄，跳出「理想世界」，到達外面一層的世界中，與可愛的碼農上帝聊一聊。