零知識(shí)證明
2022年11月14日 in 中國科學(xué)院大學(xué)
數(shù)獨(dú)解的例子解釋零知識(shí)證明
如何證明數(shù)獨(dú)有解？不能直接給出解（數(shù)據(jù)保護(hù)問題：數(shù)獨(dú)題目存在價(jià)值）。
一、零知識(shí)證明方法：
- 承諾
將謎底卡片扣在桌子上，謎面卡片放在桌子上。（Alice不能查看） - 隨機(jī)挑戰(zhàn)
鏈下互動(dòng)：Bob讓Alice用任意一種（行、列、宮格）方法檢查，Alice嚴(yán)格隨機(jī)選擇一種規(guī)則進(jìn)行檢查。 - 響應(yīng)
將Alice選擇驗(yàn)證方式的每一行/列/宮格放入一個(gè)麻袋中打亂交由Alice驗(yàn)證。（放入過程Alice監(jiān)視）
Bob在每一次Alice選擇驗(yàn)證方式的隨機(jī)中無法猜測(cè)，重復(fù)若干次。 - 驗(yàn)證
在Bob沒有解的情況下，欺騙成功的概率是1/3，Alice抓住欺騙的概率是2/3。
二、如何讓Alice以外的人相信？
- 將同樣的解做多次備份，放入機(jī)器中（機(jī)器可以根據(jù)指令自動(dòng)完成按行/列/宮格打包）。
- 指令結(jié)合不能由Bob生成，找到可信方法生成隨機(jī)串為機(jī)器提供指令，完成非交互式的證明。
- 由此，隨機(jī)串必須采用所有人公認(rèn)方法。
- 至此，零知識(shí)證明問題的核心是解決隨機(jī)串的選取問題。
三、數(shù)獨(dú)問題零知識(shí)證明中出現(xiàn)的問題
- 交互式證明無法上鏈
- 非交互式證明在驗(yàn)證的過程數(shù)據(jù)量過大，無法在一個(gè)交易的擴(kuò)展部分中進(jìn)行說明。
- 方法：將過大的數(shù)據(jù)量進(jìn)行簡潔處理，使用Merkle Tree做多次Hash。
零知識(shí)證明相關(guān)理論
一、交互證明系統(tǒng)
交互證明系統(tǒng)中進(jìn)行證明者和驗(yàn)證者之間的信息交換。通過信息交換，參與方證明某個(gè)聲明成立。
1、交互證明的性質(zhì)：
- 完備性：正確的聲明“驗(yàn)證者”總是接受。
- 可靠性：錯(cuò)誤的生命“驗(yàn)證者”總是拒絕。
- 交互式：證明者和驗(yàn)證者之間采用交互形式完成證明過程
2、交互證明系統(tǒng)的定義：
- 一個(gè)0，1組成的字符串稱為語言L，一對(duì)交互圖靈機(jī)<P,V>，P表示證明者（擁有無限計(jì)算能力），V表示驗(yàn)證者（在概率多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證）
- 稱<P,V>為語言L的交互證明系統(tǒng)，滿足以下條件：
a. 完備性：Pr[(P,V)(x) = 1|x屬于L] <= 1 - negl(|x|)
b. 可靠性：Pr[(P*,V)(x) = 0|x不屬于L] >= 1 - negl(|x|)
3、IP語言類
- 擁有交互證明系統(tǒng)的語言類稱為IP語言類。
二、零知識(shí)證明
零知識(shí)證明是交互證明系統(tǒng)的一個(gè)實(shí)例，目標(biāo)是：證明某一個(gè)事實(shí)且不泄漏知識(shí)。
1、定義
在交互證明系統(tǒng)基礎(chǔ)上增加零知識(shí)性(驗(yàn)證者無法從該證明過程中獲得額外的信息)。
- 零知識(shí)：在任意概率多項(xiàng)式時(shí)間驗(yàn)證者V*，都存在一個(gè)概率多項(xiàng)式時(shí)間的模擬器S（代表未參與驗(yàn)證的局外人），使得任意x屬于L：<P,V*>(x) ~=c S(x)
2、零知識(shí)性的三種形式
- 計(jì)算零知識(shí)性：沒有有效算法區(qū)分兩個(gè)分部
- 統(tǒng)計(jì)零知識(shí)性：統(tǒng)計(jì)距離可忽略
- 完美零知識(shí)性：兩個(gè)分布同分布
利用零知識(shí)證明的應(yīng)用
一、小零幣（Zerocoin）
鑄幣過程中只公布序列號(hào)的承諾（序列號(hào)與身份綁定），使得承諾與擁有者割裂開，沒有指定幣值。文章來源：http://www.zghlxwxcb.cn/news/detail-783968.html
1、做法
a. 生成一個(gè)序列號(hào)S和隨機(jī)密鑰r
b. 生成序列號(hào)s的承諾Commit(S,r)，可以充當(dāng)該幣地址
c. 在區(qū)塊鏈`bitcoin的鏈`上公布承諾（燒幣）
2、如何花小零幣
a. 將鑄好的小零幣注入零幣池中，構(gòu)建承諾對(duì)象中r的集合
b. 交易時(shí)，交易包涵序列號(hào)S和自己能打開承諾的聲明
c. 礦工驗(yàn)證零知識(shí)證明，認(rèn)為你可以打開區(qū)塊鏈中一個(gè)零幣
d. 礦工查詢序列號(hào)S確認(rèn)沒被花費(fèi)過
e. 花費(fèi)交易的輸出形成一個(gè)新的零幣，用自己比特幣擁有地址來作為輸出地址
二、大零幣（ZeroCash）
引入了zk-SNARKs提升效率，可以隱藏交易數(shù)額。文章來源地址http://www.zghlxwxcb.cn/news/detail-783968.html
承諾過程
- 公鑰地址和序列號(hào)與隨機(jī)數(shù)r進(jìn)行承諾生成commit(k)
- commit(k)和幣值v與隨機(jī)數(shù)s進(jìn)行承諾生成commit(coin)
- 將commit(coin)上鏈
到了這里，關(guān)于【零知識(shí)證明】數(shù)獨(dú)解的例子解釋零知識(shí)證明的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
