你怎么證明你知道——零知識(shí)證明

45934

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

二、特點(diǎn)

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

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

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

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

204094

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

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

169280

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

188423

感謝分享！

177252

感謝分享

189915

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

195208

感謝分享

204207

感謝分享

156723

謝謝分享

196169

感謝分享~