你怎么證明你知道——零知識證明

45934

一、問題定義
       零知識證明主要解決的問題是，讓一方像另一方證明他知道某個問題的答案但卻不想透露該問題的具體答案。具體來說，對一個可清晰描述的論斷，一個證明方（Prover）能通過與驗證方（Verifier）的交互使其確信論斷是正確的，但除此之外驗證方一無所知。所謂的零知識，就是指驗證方除了對論斷判斷的結果（錯或對）之外，無法獲取任何額外信息。
例如，我知道你在學院里銀行里存了多少英鎊，但不能直接說出來，那么我要怎么向你證明我確實知道。

二、特點

• 完備性（Completeness）：若一個證明方確實掌握了某論斷的答案，則他肯定能找到方法向驗證方證明他手中掌握的數據的正確性，即真的假不了。（對應上面英鎊的例子，我是證明方，我肯定能夠想辦法說服驗證方，我真的知道你存了多少英鎊）
• 可靠性（Soundness）：若一證明方根本不掌握某論斷的答案，則他無法（或只能以極低概率）說服驗證方他手中所謂答案的準確性，即假的真不了。（對應上面英鎊的例子，我如果不知道，那么也沒辦法蒙混過關讓驗證方誤以為我知道）
• 零知識性（Zero-knowledgeness）：驗證方除了知道證明的結果外，對其他信息一無所知。
  

三、如何構造零知識證明
      零知識證明要求，證明方不直接回答本問題的具體答案，而是通過證明自己知道其他問題的答案來說服驗證方。什么樣的”其他問題的答案“能夠間接判斷本問題的答案？就是與本問題答案具有強相關性的其他答案。
      也就是讓驗證方知道一些，只有知道本問題答案后才能知道或做到的事情。驗證方通過這些事情，來判斷出證明方確實知道答案。
       以上述例子為例，我要怎么向你證明我知道你存了多少英鎊。
      比如，我向你列出了你，以往每次的存入和取出操作的日期。那么很大概率也是知道你的存儲的總金額的。
      或是，你想我多次驗證，某天存入或取出了多少英鎊，我給出了確切的答案，那么我也是有很大概率知道你存儲總額的。

      零知識證明不像其他數學證明一樣，具有明確的推論邏輯和確切的結果。它偏向于概率論證，驗證后是讓你大概率的相信，如果能夠完全確信，那么其實答案也就是出來了，此時就不是零知識了。

四、案例
交互式零知識證明——色盲游戲
       A是色盲，B不是色盲。B手上有兩個大小，形狀完全一樣的球，但兩個球顏色不一樣，一個紅色，一個藍色。由于A是色盲，無法分邊兩個球是否一樣，所以B要向A證明兩個球是不一樣的。這里的A就是驗證者，B是證明者。
      B需要在A不能獲得兩個球的顏色的情況下，向A證明這兩個球的顏色是不一樣的這個事實，這與零知識證明的定義是相符合的。具體證明方法為：
A當B的面拿起兩個球，左手拿藍球，右手拿紅球，然后將雙手放到背后，這樣B就看不到A手上的球了，A在背后隨機交換左右手上的球，交換完成后A將手伸出，并詢問B兩個球是否交換過位置，如果B能看到球上的顏色，那么每次A換過球的位置后，B都能正確回答出A的問題。
      了解概率論的同學應該知道，隨著實驗次數增加，兩個球不一樣的概率越大。當然有極小概率，B每次都蒙對。
非交互零知識證明——數獨游戲
        A為了向B證明他解決一個數獨難題，但不能告訴B具體的答案。A想到了一個辦法，對于9乘9數獨題，A制作了81張卡片，包括了9套1-9的數字，然后將題面的數字用卡片正面表示，答案數據用卡面背面表示，擺放過程中B禁止觀看。擺放完，B可以任意選擇一行一列或每個九宮格內的卡片取出，然后打亂后翻開，看看數值是否在1-9之間?？梢远啻沃貜透倪^程，如果A是真的解決了，那么無論重復多少次和選擇哪一行一列一宮，都能看到1-9九張數字牌。
      當然，還有極小的概率，A知道B會選擇哪一行一列一宮，只保證那一塊的卡片不重復。

204094

"我知道你有多少英鎊!"
"啊，你是怎么知道的!?!?!?"
"害嗨害，我看的你主頁!!!"

（哈哈哈開個玩笑，帖很有用，感謝分享~

169280

帖很有用，先贊在看?。?！

188423

感謝分享！

177252

感謝分享

189915

“你是不是外面有人了？我們分手吧！”
“你怎么知？不對，我沒有??！”
“給你看病把脈的老中醫是我爸爸！不信嗎？我還能拿出給你開的方子！還不信嗎？我能說出你是哪天開始去看的中醫，還不信嗎？你看的中醫的姓沒發現和我一個姓嗎？還有，你手機里2022年10月31日23點36分和小櫻桃的對話為什么要親？”

195208

感謝分享

204207

感謝分享

156723

謝謝分享

196169

感謝分享~