零知識證明

出自 MBA智库百科(https://wiki.mbalib.com/)

零知識證明，最小泄露證明系統，Zero—Knowledge Proof

　　零知識證明是由S.Goldwasser、S.Micali及C.Rackoff在20世紀80年代初提出的。它指的是證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。零知識證明實質上是一種涉及兩方或更多方的協議，即兩方或更多方完成一項任務所需採取的一系列步驟。證明者向驗證者證明並使其相信自己知道或擁有某一消息，但證明過程不能向驗證者泄漏任何關於被證明消息的信息。大量事實證明，零知識證明在密碼學中非常有用。如果能夠將零知識證明用於驗證，將可以有效解決許多問題。

　　在有必要證明一個命題是否正確，又不需要提示與這個命題相關的任何信息時，零知識證明系統(也叫做最小泄露證明系統)是不可或缺的。零知識證明系統包括兩部分：宣稱某一命題為真的示證者(prover)和確認該命題確實為真的驗證者(verifier)。證明是通過這兩部分之間的交互來執行的。在零知識協議的結尾，驗證者只有當命題為真時才會確認。但是，如果示證者宣稱一個錯誤的命題，那麼驗證者完全可能發現這個錯誤。這種思想源自互動式證明系統。互動式系統在計算複雜度理論方面已經獲得異常獨立的地位。^[1]

　　零知識證明(Zero—Knowledge Proof)起源於最小泄露證明。設P表示掌握某些信息，並希望證實這一事實的實體，設V是證明這一事實的實體。假如某個協議向V證明P的確掌握某些信息，但V無法推斷出這些信息是什麼，我們稱P實現了最小泄露證明。不僅如此，如果V除了知道P能夠證明某一事實外，不能夠得到其他任何知識，我們稱P實現了零知識證明，相應的協議稱作零知識協議。

　　在最小泄露協議中零知識證明需要滿足下述兩個性質：

　　(1)正確性。P無法欺騙V。換言之，若P不知道一個定理的證明方法，則P使V相信他會證明定理的概率很低。

　　(2)完備性。V無法欺騙P。若P知道一個定理的證明方法，則P使V以絕對優勢的概率相信他能證明。

　　在零知識協議中，除滿足上述兩個條件以外，還滿足下述的第三個性質：

　　(3)零知識性。V無法獲取任何額外的知識。

　　我們把性質(1)和(2)稱為零知識證明的正確性和完備性，而性質(3)稱為零知識性。

　　零知識證明需要滿足三個屬性。

　　1、如果語句為真，誠實的驗證者（即：正確遵循協議的驗證者）將由誠實的證明者確信這一事實。

　　2、如果語句為假，不排除有概率欺騙者可以說服誠實的驗證者它是真的。

　　3、如果語句為真，證明者的目的就是向驗證者證明並使驗證者相信自己知道或擁有某一消息，而在證明過程中不可向驗證者泄漏任何有關被證明消息的內容。

　　零知識證明並不是數學意義上的證明，因為它存在小概率的誤差，欺騙者有可能通過虛假陳述騙過證明者。換句話來說，零知識證明是概率證明而不是確定性證明。但是也存在有技術能將誤差降低到可以忽略的值。

　　零知識的形式定義必須使用一些計算模型，最常見的是圖靈機的計算模型。

　　A要向B證明自己擁有某個房間的鑰匙，假設該房間只能用鑰匙打開鎖，而其他任何方法都打不開。這時有2個方法：

　　①A把鑰匙出示給B，B用這把鑰匙打開該房間的鎖，從而證明A擁有該房間的正確的鑰匙。

　　②B確定該房間內有某一物體，A用自己擁有的鑰匙打開該房間的門，然後把物體拿出來出示給B，從而證明自己確實擁有該房間的鑰匙。

　　後面的②方法屬於零知識證明。它的好處在於，在整個證明的過程中，B始終不能看到鑰匙的樣子，從而避免了鑰匙的泄露。

　　A擁有B的公鑰，A沒有見過B，而B見過A的照片，偶然一天兩個人見面了，B認出了A，但A不能確定面前的人是否是B，這時B要向A證明自己是B，也有2個方法：

　　① B把自己的私鑰給A，A用這個私鑰對某個數據加密，然後用B的公鑰解密，如果正確，則證明對方確實是B。

　　② A給出一個隨機值，並使用B的公鑰對其加密，然後將加密後的數據交給B，B用自己的私鑰解密並展示給A，如果與A給出的隨機值相同，則證明對方是B。後面的方法屬於零知識證明。

　　一天，阿裡巴巴被強盜抓住了，強盜向阿裡巴巴拷問進入山洞的咒語。面對強盜，阿裡巴巴是這麼想的：如果我把咒語告訴了他們，他們就會認為我沒有價值了，就會殺了我省糧食；但如果我死活不說，他們也會認為我沒有價值而殺了我。怎樣才能做到既讓他們確信我知道咒語，但又一丁點咒語內容也不泄露給他們呢？

　　這的確是一個令人糾結的問題，但阿裡巴巴想了一個好辦法，當強盜向他拷問打開山洞石門的咒語時，他對強盜說：“你們在離開我一箭遠的地方，用弓箭指著我，當你們舉起右手我就念咒語打開石門，舉起左手我就念咒語關上石門，如果我做不到或逃跑，你們就用弓箭射死我。”

　　強盜們當然會同意，因為這個方案不僅對他們沒有任何損失，而且還能幫助他們搞清楚阿裡巴巴到底是不是真的知道咒語這個問題。阿裡巴巴也沒有損失，因為處於一箭之地的強盜們聽不到他念的咒語，不必擔心泄露了秘密，同時他又確信自己的咒語有效，也不會發生被射死的杯具。

　　強盜舉起了右手，只見阿裡巴巴的嘴動了幾下，石門果真打開了，強盜舉起了左手，阿裡巴巴的嘴動了幾下後石門又關上了。強盜還是有點不信，說不准這是巧合呢，他們不斷地換著節奏舉右手舉左手，石門跟著他們的節奏開開關關，最後強盜們想，如果還認為這隻是巧合，自己未免是個傻瓜，那還是相信了阿裡巴巴吧。

　　這樣，阿裡巴巴既沒有告訴強盜進入山洞石門的咒語，同時又向強盜們證明瞭，他是知識這個咒語的。

　　那麼，利用了區塊鏈技術的ZCash，就是利用“零知識證明”實現的匿名性。

　　相對於ZCash來說，比特幣的轉賬並不是完全匿名的，只要知道了一個比特幣地址，任何人都可以通過這個網站，查到這個地址的所有“消費”行為和關聯。比如給誰轉了賬，又從誰（的比特幣地址）那裡收到過轉賬，在以區塊鏈技術為基礎的“賬本”上都“本本份份”地記錄著。

　　例如A有3個BTC，要給B轉賬1個BTC，那麼在賬本上就會記錄著：A轉出了兩筆BTC，一筆為1BTC，轉給了B；另一筆為2BTC，轉給了自己。

　　那麼利用了“零知識證明”的ZCash是怎麼做到的所謂匿名呢？

　　ZCash的代幣為ZEC。同樣假設A有3個ZEC，要給B轉賬1個ZEC。

　　首先，A會將自己的1個ZEC分成若幹份隨機投入一系列的“混合容器”中，指定接收方B的地址，同時混入的時候還有其他交易方輸出的若幹份ZEC。這些ZEC又被混合容器隨機拆分，再從這些被拆分生成的所有的ZEC中取出合計為1ZEC的若幹份，轉移到B的地址中，同時在發送的時間上也可以設置一定的延遲[3]。

　　其中的“混合容器”，就是一條“公有鏈”。經過這條公有鏈一系列的“混幣”過程，就使得包括交易地址和具體金額在內的交易信息變得無從考證了。

　　當然，雖然ZCash以其匿名性使其市場熱度一度很高，但其仍面臨諸多障礙與“原罪”。

　　首先，要實現匿名性，其所需要的證明信息所花費的計算資源就非常多，帶來了大量的資源浪費，也導致了其可擴展性面臨巨大挑戰。

　　另外，匿名性會帶來大量的額外監管問題，一旦有不法份子利用其用戶黃、賭、毒等違法領域，將會給追蹤與監管帶來非常大的挑戰，造成一系列社會問題。

• 區塊鏈