從簡單和實用出發，一文讀懂零知識證明
— 導讀/ 原用標題
作者：BenLaw
你之前是否閱讀過一些零知識證明的文章，但仍一頭霧水？這些文章可能：
- 只以故事和童話作例子來論述 ZKP，無法深入其本質。
- 內含大量密碼學術語，數學公式，學術論文等，對初學者而言過於復雜。
本文提供了對 ZKP 簡明扼要的概述，並從數學、密碼學和編程角度進一步闡述 ZKP 的核心要素。
向色盲提供顏色證明
如何向色盲患者證明兩個球的顏色確實是不同的？這其實並不復雜：
讓他在手裡握住兩個球，背到背後，然後隨機選擇交換或不交換兩個球的位置，再展示給你看，你告訴他這兩個球的位置是否有變化。
在他看來，你可以通過瞎蒙來完成一次證明。不過，如果成千上萬次地重複這個過程：如果你總是能說出正確答案，那麼靠純蒙的方式來保持一直正確的概率，是小到可以忽略的。因此可以通過這種方式來向色盲患者證明：兩個球的顏色確實不一樣，並且我們也有感知和區分的能力。
上述證明過程是典型的零知識證明：
- 驗證者無法在證明過程中獲得任何關於顏色的知識，因為經過驗證過程後他依然沒有區分顏色的能力。
- 該驗證過程是概率性的而非決定性的。
- 該過程是交互式的，需要多輪交互。不過，零知識證明中也有許多協議，通過高級技巧將證明過程轉化成了非互動式的。
掌握知識的證明
我們已經分享了一種現實世界中的零知識證明的例子，接下來再來看一下在二進制世界中如何實現零知識證明。
Arthur 是 Elon 的朋友，並且知道對方的手機號。Betty 不知道 Elon 的號碼。如果 Arthur 想要向 Betty 證明他知道，但又不想洩露號碼，應該怎麼實現呢？
一種不成熟的方案是，Elon 發布自己電話號碼的哈希，Arthur 通過一個程序輸入哈希的原像，程序進行運算並檢查結果。這個方法有一些致命的缺陷：
- 根據哈希，Betty 可以通過暴力破解的方式得到原像，能破解出來的概率是不可忽略的，而且得到的結果幾乎是確定性的。
- Arthur 必須向該程序輸入原像。如果程序在 Arthur 的電腦上，Betty 就會對此有疑問：我怎麼知道你有沒有作弊，你的電腦也許會一直聲稱你的證明是對的？
- 如果程序在 Betty 的電腦上運行，Arthur 也會擔心，自己輸入的信息會不會被竊取，即使程序肉眼可見的代碼中並沒有竊取信息的命令。
- 因為無法將程序分開在不同的環境中運行，這個信任問題是難以解決的。
常規的方法在這裡碰壁了，是時候讓零知識證明出場了！
基於密碼學的零知識證明的實現方案
在此我會用零知識證明中的 Sigma Protocol 來解決問題，因為它比較簡單。並且，為了簡潔和易於理解，這裡不會使用嚴格的密碼學和數學中的定義、術語及推導過程等。
核心流程
使用零知識證明證明一個人有特定的知識，我們採取如下辦法：
- 定義一個
P階的有限群及其生成元g。我們可以暫時忽略這些奇怪的名詞具體什麼意思。 - 根據上面的定義，某個擁有知識或能接觸到知識的第三方，將知識（記為
w）通過h = g^w (mod P)的方式加密後，將 h 發佈出去。 - 證明者啟動零知識證明流程。生成一個隨機數 r，計算
a = g^r，並將a發送給驗證者。 - 驗證者生成一個隨機數
e並發送給證明者。 - 證明者計算
z = r + ew並發送給驗證者。 - 驗證者檢查
g^z == a·h^e(mod P)。如果為真，則驗證者確實掌握其聲稱的知識。
好啦，該證明協議到此就結束了！非常簡短，但你仍可能對上面的一些數學運算感到困惑，但這不要緊，我們先有個大概印象再深入理解。
示例程序
我用 Python 寫了一個簡化的 Sigma Protocol 的示範程序，對理解上述過程有很大幫助。在程序中，你既可以扮演定義和發布知識的第三方，也可以成為掌握了知識或沒有掌握知識的證明者。
from random import SystemRandom
# Cryptography Public Parameters
g = 22500 # Generator of the finite group
P = 3213876088517980551083924184682325205044405987565585670609523 # Order of the finite group. A big prime number.
# The encrypted knowledge, will be set by a 3rd party.
# Its preimage, which the prover needs to prove he knows, is not accessible to both the prover and verifier.
h = None
# These parameters will be set in further proving steps and passed from the verifier to the prover or vice versa.
a = e = z = None
def specifyKnowledge(w):
global h
h = pow(g,w,P)
print('\n'+'The knowledge topic has been designated.'+ '\n' +
'Neither the verifier nor prover can read since it\'s discarded after this func executed.' + '\n' +
'Only its encryption is publicly known.' '\n' +
'If the prover hasn\'t learned it somewhere else before, he won\'t be able to pass the verification.''\n')
class Verifier:
def __init__(self):
return
def verify_step1(self):
global e
e = SystemRandom().randrange(P)
print('Verifier:')
print('random number b = ',e,', b -----> Prover','\n')
def verify_step2(self):
print('Verifier:'+'\n'+'Checking if pow(g,z,P) == (a * pow(encryptedKnowledge,b,P)) % P:')
if pow(g,z,P) == (a * pow(h,e,P)) % P:
print('Accept! Prover knows the knowledge','\n')
else:
print('Reject! Prover knows nothing','\n')
class Prover:
def __init__(self, knowledge_to_verify):
self.k = knowledge_to_verify
self.r = SystemRandom().randrange(P)
print('Start proving','\n')
def prove_step1(self):
global a
a = pow(g,self.r,P)
print('Prover:')
print('random number r = ',self.r)
print('a = g ** r % p = ',a,', a -----> Verifier','\n')
def prove_step2(self):
global z
z = self.r + e * self.k
print('Prover:')
print('z = r + b * knowledge_to_verify = ',a,', z -----> Verifier','\n')
print('\n'+'-------- Zeroknowledge Example Begins --------'+'\n')
specifyKnowledge(w = int(input("Enter your secret knowledge (Intger):")))
prover = Prover(knowledge_to_verify = int(input("Enter Prover's knowledge (Intger) :")))
verifier = Verifier()
prover.prove_step1()
verifier.verify_step1()
prover.prove_step2()
verifier.verify_step2()Source code:
dysquard/SimpleZkpExplanation · GitHub
Just python example.py.
數學原理
這套流程背後的核心數學原理是離散對數難題：當 P 是一個很大的質數時，對於給定的 h，很難找到滿足 h = g^w(mod P)的 w。該原理適用於上面所有類似的式子。
我們來一步一步解析下：
經過加密的知識 h = g^w (mod P)，是難以被暴力破解的。由於求餘運算的特點，即使被破解了也不具備單一確定解。這意味著對證明者而言，通過暴力破解來作弊，欺騙驗證者，是不可行的。
然後我們將 3，4，5 步作為一個整體來看一下他們為什麼要交換這些隨機數：
I. 證明者並不想暴露其秘密，所以他必須用隨機數包裹一下將其隱藏起來。而驗證者也需要通過添加一些隨機數，讓該知識可被自己驗證的同時防止證明者作弊，而且不會窺探到證明者的秘密。
II. 如果驗證者先發送了隨機數 e（即將 3 和 4 步交換一下），很明顯，證明者可以通過編造 a = g^z·h^-e 來在最終檢查中欺騙驗證者，即使沒有知識也可以通過。所以證明者必須先手發送一個承諾 (a=g^r)，但非 r 本身，來避免可作弊場景，同時不讓驗證者通過 w = (z - r)/e 提取到秘密。
III. 在收到承諾後，證明者向驗證者發送隨機數 e。由於其本身或者其衍生物無法洩露任何一方的信息，這個數不需要加密。之後證明者計算 z = r + ew 並將 z 發送給驗證者。驗證者最終通過檢查 g^z= g^(r+ew)= g^r·(gw)^e= a·h^e 來確定證明者是否掌握知識。
通過這種往返交錯的結構，我們收穫了三個性質：
完備性:
當且僅當證明者輸入正確知識，驗證才能通過。
可靠性:
當且僅當證明者輸入錯誤知識，驗證才會失敗。
零知識性:
驗證者無法在驗證過程中獲取任何知識。
上述三點即零知識證明的核心特性。通過數學和密碼學，我們構建出了一套光怪陸離的證明體系。恭喜你一路走了這麼遠，現在應該已經可以說正式邁入了富麗堂皇又奧妙無窮的 ZKP 聖殿。
Have fun!
進一步了解
模擬器和零知識性
我們現在來考慮一些魔幻場景。如果一個證明者俱有預言或篡改驗證者生成的隨機數的超能力，我們稱其為模擬器。
設想，模擬器在驗證者的隨機數 e 生成前就對其進行了篡改，確保其生成後是自己預設的值。根據上面 II 所說，這種能力使模擬器能編造承諾 a 來欺騙驗證者。不論模擬器的輸入是什麼，驗證者總會得出結論模擬器具有知識，然而實際上他並沒有。
顯然，經過這種思想實驗我們可以得出結論，驗證者無法在該零知識證明協議中獲取任何知識，也即其零知識性是成立的：
零知識性<== ∀模擬器 S，使得 S(x) 與真實的協議執行不可區分，其中 S(x)：
選擇隨機的 z 和 e，令 a = g^z·h^-e，其中 (a,e,z) 的分佈與真實的隨機數環境一致並滿足 g^z=a·h^e。
抽取器和可靠性
再來想像一下另一種超能力者——抽取器，具有時光倒流的能力。不過這次是抽取器作為驗證者，面對一個正常的證明者。
當協議結束時，抽取器發起時間倒流，回到協議的起點，並持有上一輪得到的 (z, e, a) 。現在，協議重新執行一遍。由於證明者沒有超能力無法進行時間旅行只能在固定的時間線上做確定的事，他又生成了一個一模一樣的隨機數 r 以及承諾 a = g^r，而抽取器則可以生成新的隨機數 e'給證明者。
現在，抽取器獲得了：g^z= a·h^e, g^z'=a·h^e => g^(z-z') = h(e-e') => 加密後的知識 h = g^((z-z')/(e-e')) => 知識 w = (z-z')/(e-e').
顯然，只要證明者真的掌握了知識，抽取器總是可以將其抽取出來，也即完備性成立：
完備性<== ∀抽取器 E，對給定的任何 h，在掌握 (a,e,z),(a,e',z')且 e≠e'的情況下，都能輸出 w st (h,w) ∈ R.
完備性
完備性不需要任何特殊角色來證明，因為：g^z = g^r+ew = g^r·(g^w)^e = a·h^e.
免責聲明：作為區塊鏈信息平台，本站所發布文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。本文內容僅用於信息分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
