深入浅出零知识证明（一）：Schnorr协议
? ? ? ?最近在學習零知識證明，因為內容很多并且難度也大，想根據自己的學習路線做一系列總結，這是第一篇文章，主要介紹零知識證明的一些重要概念和思想，可以對零知識證明有直觀的理解，然后講解一個經典簡潔的零知識證明安全協(xié)議Schnorr協(xié)議。
? ? ? ?本篇文章主要包含四個方面，首先來總體介紹一下零知識證明，然后以地圖三染色問題為例，體現零知識證明思想，然后分析交互式Schnorr協(xié)議和非交互式Schnorr協(xié)議。
1.零知識證明概述
? ? ?·簡介
? ? ? ?零知識證明(Zero-Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世紀80年代初提出的。證明者能夠在不向驗證者提供任何有用的信息的情況下，使驗證者相信某個論斷是正確的。零知識證明實質上是一種涉及兩方或更多方的協(xié)議，即兩方或更多方完成一項任務所需采取的一系列步驟。
? ? ·概念
? ? ? “P”表示 “證明者(Proofer)”：作為零知識證明的參與方，他在證明命題真實性的同時，不會泄漏任何相關信息。
? ? ? “V”表示 “驗證者(Verifier)”：作為零知識證明的另一參與方，驗證證明者提出的命題以及對應的證明是不是正確。
? ? ? “承諾階段(Commit)”：證明者針對命題做出承諾，并等待驗證者提出挑戰(zhàn)并進行驗證。
? ? ? “挑戰(zhàn)階段(Challenge)”：驗證者選擇隨機數，對提出的承諾進行挑戰(zhàn)。
? ? ? “回應挑戰(zhàn)階段(Response)”：證明者將收到的隨機數并結合給出的承諾，返回挑戰(zhàn)的回應。
? ? ? “驗證階段(Verify)”：驗證者驗證，挑戰(zhàn)的回應是否正確，錯誤的話那就證明失敗，如果成功就可進行下一次挑戰(zhàn)，直到可以相信的概率達到驗證者接受的條件，這樣就證明成功。
? ? ·性質
? ? ? ?在零知識證明中，需要滿足三個性質：
? ? ? ?正確性。沒有人能夠假冒P使這個證明成功。如果不滿足這條性質，也就是P不知道“知識”，再怎么證明，V也很難相信P擁有正確的知識。
? ? ? ?完備性。如果P和V都是誠實的，并證明過程的每一步都進行正確的計算，那么這個證明一定是成功的。也就是說如果P知道“知識”，那么V會有極大的概率相信P。
? ? ? ?零知識性。證明執(zhí)行完之后，V只獲得了“P擁有這個知識”這條信息，而沒有獲得關于這個知識本身的任何信息。
? ? ·應用
? ? ? ?數據的隱私保護：在隱私場景中，根據零知識性，不泄漏交易的接收方，發(fā)送方，交易余額等細節(jié)的前提下，證明區(qū)塊鏈上的資產轉移是有效的。再比如買保險的時候，保險公司需要了解是否患有某種疾病，但是我不想讓保險公司知道我的全部病歷信息，那我可以證明給保險公司看，我沒有相關疾病就足夠了。
? ? ? ? 計算壓縮與區(qū)塊鏈擴容：在當前的區(qū)塊鏈架構中，同樣的計算會被重復多次，比如簽名的校驗，交易合法性校驗，智能合約的執(zhí)行等等。這些計算過程都可以被零知識證明技術進行壓縮。比如以太坊采用 zkSNARK，帶來幾十倍的性能提升。
? ? ? ? 端到端的通訊加密：用戶可以互相通信，但是消息記錄不會完全暴露在服務器上，同時消息也可以按照服務器的要求，出示相應的零知識證明，比如消息的來源、與發(fā)送的目的地。
? ? ? ? 身份認證：用戶可以向網站證明，他擁有私鑰，網站并不需要知道私鑰的內容，可以通過驗證這個零知識證明， 確認用戶的身份。
? ? ? ? 去中心化存儲：服務器可以向用戶證明他們的數據被妥善保存，并且不泄露數據的內容。
2.舉例：地圖三染色問題
? ?·地圖三染色問題
?? ? ? ??三染色問題：假設存在一個地圖，不同城市之間修建一些道路，三染色問題即為是否存在一種染色方式，使得每個城市都用特定的三種顏色之一表示，并且任意有道路相連的兩個城市都不是相同的顏色。
? ? ? ? 下面設計一個交互協(xié)議： Alice是「證明者」，Bob是「驗證者」
? ? ? ? Alice擁有一個對特定地圖的三染色方案，希望在不泄漏任何信息的條件下向Bob證明自己擁有該方案。
? ? 1. 承諾階段
?? ? ? ?首先，在承諾階段，Alice 先要對染過色的圖進行一些「變換」，把顏色進行置換，例如把所有的藍色變成綠色，綠色變成橙色，橙色變成藍色。這樣 Alice 得到了一個新的染色答案，這時候她把新圖的每一個頂點都用紙片蓋上，然后出示給 Bob 看。
? ? ? 2. 挑戰(zhàn)階段
? ? ? ?下面進入挑戰(zhàn)階段，bob要挑戰(zhàn)Alice是否真的知道答案，但是他不能直接打開所有信封，只能隨機選擇任意一條邊，要求Alice打開相鄰兩個節(jié)點的紙片進行驗證兩個頂點的顏色是否相同。
? ? ? 3. 回應挑戰(zhàn)階段
?? ? ? ? 然后進入回應挑戰(zhàn)階段，假設 Bob 挑選的是最下面的一條邊。Alice打開Bob指定的兩個節(jié)點，作為對挑戰(zhàn)的回應，讓 Bob 檢查，發(fā)現這兩個頂點的顏色是不同的，那么 Bob 認為這次檢驗正確。但是Bob 只看到了圖的局部，一次挑戰(zhàn)不能讓他信任，但是多次挑戰(zhàn)可能讓Bob獲取到Alice全部的染色方案，極端情況就是Bob查看了所有邊的相鄰節(jié)點顏色，從而完全重構出染色方案。
? ? ? 4. 重復過程
? ? ? ?所以要對上述三個階段進行多次重復，每次在承諾階段Alice都會將染色方案進行一次隨機置換，使得Bob每次驗證，只能得到指定的兩個相鄰節(jié)點染色是否相等的信息。隨著重復的次數足夠多，Bob有極大概率相信Alice擁有一個正確的染色方案。但是Bob 每次看到的局部染色情況，都是 Alice 變換過后的結果，無論 Bob 看多少次，都不能拼出一個完整的三染色答案出來。Bob 在這個過程中，雖然獲得了很多「信息」，但是卻沒有獲得真正的「知識」。
? ? ? ?通過這個例子，對零知識證明可以有直觀的了解。接下來，介紹一個簡潔，用途廣泛的零知識證明系統(tǒng) —— Schnorr 協(xié)議。
?3.交互式Schnorr協(xié)議
? ? ? ? Schnorr機制是一種基于離散對數難題的零知識證明機制。證明者聲稱知道一個密鑰x的值，通過使用Schnorr加密技術，可以在不揭露x的情況下，向驗證者證明對x的知情權。可用于證明你有一個私鑰但是不披露私鑰的內容。
? ? ? ?原始的Schnorr機制是一個交互式的機制。Schnorr中涉及到的技術有哈希函數的性質、橢圓曲線的離散對數難題。
? ? （橢圓曲線的離散對數難題是指，已知橢圓曲線E和點G，隨機選擇一個整數d，容易計算橢圓曲線上另一點Q=d*G，但是給定的Q和G來計算d就非常困難。）
? ? ? ?假設Alice 擁有一個秘密數字，a，我們可以把這個數字當成「私鑰: sk」，然后把它「映射」到橢圓曲線群上的一個點 a*G，簡寫為 aG。這個點我們把它當做「公鑰: PK」。
? ? ? ?Schnorr 協(xié)議充分利用了有限域和循環(huán)群之間單向映射，實現了簡潔的零知識證明安全協(xié)議：Alice 向 Bob 證明她擁有 PK 對應的私鑰 sk，那么如何證明呢。
??? ? ? 交互式Schnorr協(xié)議的流程分為三步：
? ? ? ? 第一步：為了保證零知識，Alice 需要先產生一個隨機數r，這個隨機數是用來保護私鑰無法被 Bob 抽取出來，會映射到橢圓曲線群上的點rG上，記為R發(fā)送給Bob。
? ? ? ? 第二步：Bob 要提供一個隨機數進行挑戰(zhàn)，把它稱為 c。
? ? ? ? 第三步：Alice 根據挑戰(zhàn)數計算 z = r + a * c，然后把 z 發(fā)給 Bob，Bob通過式子進行檢驗：z*G ?= R + c*PK
? ? ? ? 由于z=r+c*sk，等式兩邊添加相同的生成元可得：z*G= rG + c*(aG)=c*PK+R。就可以驗證Alice確實擁有私鑰sk，但是驗證者Bob并不能得到私鑰sk的值，因此這個過程是零知識的，并且是交互式的。
? ? ? ? 由于橢圓曲線上的離散對數問題，知道R和G的情況下通過R=r*G解出r是不可能的，所以保證了r的私密性。
? ? ? ? 但是，整個過程是在證明者和驗證者在私有安全通道中執(zhí)行的。這是由于協(xié)議存在交互過程，只對參與交互的驗證者有效，其他不參與交互的驗證者，無法判斷整個過程是否存在串通的舞弊行為，一旦兩個驗證者相互串通，交換自己得到的值，便可以推出私鑰。因此，是無法公開驗證的。
? ? ? ? 進一步分析，為什么需要驗證者回復一個隨機數c呢？這是為了防止Alice造假。
? ? ? ? 如果Bob不回復一個c，就變成一次性交互。由于橢圓曲線上的離散對數問題，知道PK和G的情況下通過PK = a * G接觸a是不可能的，所以保證了a的私密性。
? ? ? ? 但是這種方案是存在問題的，a和r都是Alice自己生成的，她知道Bob會用PK和R相加然后再與z * G進行比較。所以她完全可以在不知道a的情況下構造：R = r * G - PK 和 z = r。 這樣Bob的驗證過程就變成：z * G ?== PK + R ==> r * G ?== PK + r * G - PK。這是永遠成立的，所以這種方案并不正確。
? ? ? ? 所以在交互式Schnorr協(xié)議中存在的私鑰泄露問題，使得算法無法在公開的環(huán)境下使用。
? ? ? ? 可以將原始的交互式協(xié)議轉變?yōu)榉墙换ナ絽f(xié)議來解決這個問題！
? ? ? ?下面來看，如何把一個三步的 Schnorr 協(xié)議變成一步。
?4.非交互式Schnorr協(xié)議
? ? ? ? ?回顧一下交互式Schnorr 協(xié)議的第二步，Bob 需要給出一個隨機的挑戰(zhàn)數 c，這里我們可以讓 Alice 用下面這個式子來計算這個挑戰(zhàn)數，從而達到去除協(xié)議第二步的目的。
? ? ? ? ?c = Hash(PK, R) 。
? ? ? ? ?其中 R 是 Alice 發(fā)給 Bob 的橢圓曲線點，PK 是公鑰。
? ? ? ? ?這個式子達到了兩個目的：
? ? ? ? ?第一個，Alice 在產生承諾 R 之前，沒有辦法預測 c，即使 c 最終是 Alice 生成的。
? ? ? ? ?第二個，c 通過 Hash 函數計算，會均勻分布在一個整數域內，可以作為一個隨機數。
? ? ? ? ?Hash 函數是「單向」的，這樣一來，雖然 c 是 Alice 計算的，但是 Alice 并沒有能力實現通過挑選 c 來作弊。因為只要 Alice 一產生 R， c 就相當于固定下來了。
? ? ? ? ?這樣，就把三步Schnorr協(xié)議合并為一步。Alice可直接發(fā)送（R，z），因為Bob擁有Alice的公鑰PK，于是Bob可自行計算出c。然后驗證z*G?=R+c*PK。
? ? ? ?如圖，利用 Hash 函數，把三步 Schnorr 協(xié)議合并為了一步。Alice 可以直接發(fā)送：(R, c, z)。又因為 Bob 擁有 PK，于是 Bob 可以自行計算出 c，于是 Alice 可以只發(fā)送 (R, z) 即可。
?? ? ??·Alice：均勻隨機選擇r，并依次計算 R=r*G c=Hash(R,PK) z=r+c*sk
? ? ? ?·Alice：生成證明(R,z)
? ? ? ?·Bob(或者任意一個驗證者)：計算e=Hash(PK,R)
? ? ? ?·Bob(或者任意一個驗證者)：驗證z*G?==R+c*PK
?5.Schnorr用于數字簽名
? ? ? ? Schnorr 協(xié)議可以用于數字簽名。
? ? ? ? 首先，為了保證攻擊者不能隨意偽造簽名，使用離散對數難題和Hash函數滿足抗第二原象（防碰撞）作為安全假設。
? ? ? ? 提出數字簽名的出發(fā)點有兩個：
? ? ? ? 一是，接收方希望證實消息在傳遞過程中沒有被篡改；
? ? ? ? 二是，希望確認發(fā)送者的身份，可以理解為發(fā)送者有一個私鑰，并且私鑰和這條消息進行關聯(lián)計算。
? ? ? ? 首先要證明發(fā)送者的身份，這正是Schnorr協(xié)議的功能，能夠向對方證明「我擁有私鑰」這個陳述。并且這個證明過程是零知識的，不泄露關于「私鑰」的任何知識。而c=Hash(m,R)可以保證發(fā)送者與信息相關聯(lián)。
? ? ? ? 上圖就是Schnorr簽名方案。在這里還有一個優(yōu)化，Alice發(fā)給Bob的內容不是(R,z)而是(c,z)，這是因為R可以通過c,z計算出來。
? ? ? ? 分析下優(yōu)化的原理，令n是有限域大小的位數。假設采用了非常接近2^256的有限域，也就是說z是256bit，那么橢圓曲線群的大小也差不多要接近256bit，這樣一來，把2^256開平方根后就是2^128，所以說256bit橢圓曲線群的安全性只有128bit。那么，挑戰(zhàn)數c也只需要128bit就足夠了。這樣Alice發(fā)送c要比發(fā)送R要更節(jié)省空間，而后者至少需要256bit。c只需要128bit。相比ECDSA簽名方案來說，可以節(jié)省1/4的空間。
總結
以上是生活随笔為你收集整理的深入浅出零知识证明（一）：Schnorr协议的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 圣诞树 圣诞树 圣诞树_圣诞网页设计资源
- 下一篇： snowboy嵌入式_jetson na