干貨 | 何謂“零知識” 何謂“證明”？_ALI:LIC

編者注：本文出自郭宇@SECBIT之手，EthFans經授權轉載。文末附有SECBIT安比實驗室的公眾號二維碼，其中的文章都凝結了他們深入而謙遜的努力，值得關注。

本文已更新至Github

https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md

引言

我認為區塊鏈很難稱為一個“技術”。它更像是一個領域，包羅萬象。或者形而上地說，區塊鏈更像一個有機體，融合了各種不同的理論技術。零知識證明是構建信任的重要技術，也是區塊鏈這個有機體中不可缺少的一環。

零知識證明是打通鏈上數據與鏈下計算的關鍵技術，也是實現鏈上數據隱私保護的重要途徑要解釋「零知識證明」，我們需要先解釋「證明」，然后解釋什么是「知識」，最后再解釋什么是「零知識」。

"證明"的前世今生

什么是證明？很多人可能和我一樣，看到這兩個字，會不禁想起中學考卷中各種三角相似的幾何圖形，當老師在神奇地畫出一條輔助線后，證明過程突然顯而易見，然后會懊悔自己為何沒想到。

古希臘：「證明」==「洞見」

數學證明最早源于古希臘。他們發明了公理與邏輯，他們用證明來說服對方，而不是靠權威。這是徹頭徹尾的「去中心化」。自古希臘以降，這種方法論影響了整個人類文明的進程。

上圖是「勾股定理」的巧妙證明。歷史上曾出現過許許多多精巧的證明，神奇的思路，天才的靈感。一旦一個命題被證明，上帝都無能為力。嗯，對了，還有那個「上帝不是萬能的」證明：上帝不能造出一塊他舉不起來的石頭。一個數學證明往往暗藏無比深刻的「洞見」，相信很多人都看過「費馬大定理」的故事，這個定理證明橫跨四百年，從費馬寫下「這里空間太小，我寫不下」，到懷爾斯最終登頂，耗費了許多代人的聰明才智。最近如「彭加萊猜想」，稍微帶點年代感的如「哥德巴赫猜想」，還有我非常敬佩的華裔科學家張益唐十年磨一劍，在仔細研究了「Goldston-Pintz-Y?ld?r?m」和「Bombieri-Friedlander-Iwaniec.」的證明「洞見」之后，證明了「質數間的有界間隔」。自十七世紀，萊布尼茨起，人們就夢想找到一種機械的手段，可以來自動完成證明，而不再依賴天才的靈光一現。

二十世紀初：「證明」==「符號推理」

時間到了十九世紀末，康托、布爾、弗雷格、希爾伯特、羅素、布勞威、哥德爾等人定義了形式化邏輯的符號系統。而「證明」則是在利用形式化邏輯的符號語言編寫的推理過程。邏輯本身靠譜么？邏輯本身「自恰」嗎？邏輯推理本身對不對，能夠證明嗎？這讓數學家/邏輯學家/計算機科學家發明了符號系統，語法vs.語義，可靠vs.完備，遞歸vs.無窮。。1910年，羅素發表了洪(zhuan)荒(tou)巨著『數學原理』。在書中，羅素與懷特海試圖將數學完整地「形式化」下來。如果能達到這樣的目標，所有的數學成果都將以證明的方式建立在堅實的基礎上。下圖就是『數學原理』中的一頁：

其中110.643這是一個命題：「11=2」，然后接下來就是這個定理的證明。大家可能奇怪，難道11還需要證明嗎？是的，在數學原理一書中，數字0，1，2，……都有嚴格定義，「加法」、「乘法」、「等于」都要嚴格定義，然后每一步的推理都需要指出依據。證明意味著什么？證明是可能繁瑣無比的、但是每一步推理都嚴格無誤。書中大量的證明都機械式的，按照公理和推理規則進行一種證明的構造，尋找證明就好像可以交給一個人，然后他無腦在公理與推理規則的集合中進行機械查找。似乎人們距離「定理的自動證明」并不遙遠了。不幸的是，哥德爾在1931年證明了「哥德爾不完備性定理」，圖靈在1936年證明了圖靈機停機問題的不可判定性。這些成果徹底終結了這個幾百年的幻想。無論公理系統如何精巧設計，都無法抓住所有的真理。證明不僅僅是一個嚴格推理，而且凝結了似乎很難機械化的創造性思維。證明中蘊含了大量的「知識」，每一次的突破，都將我們的認知提升到一個新的高度。不管是「洞見」，還是推理過程中所構造的「算法」，一個定理的證明的內涵往往遠超出定理本身的結論。

吳磊：分布式資產的普及將從廣告產業往全Web3賽道蔓延:6月4日，在由世界無人機大會組委會、中國民協元宇宙工委主辦的第七屆世界無人機大會上，DA AGE合伙人吳磊預言了實體經濟中的真實物理資產將通過DLT的技術方式一一映射到區塊鏈數字資產世界，以顆粒化、精準化的數字流動方式，將分布式資產概念和權益分配到公眾手中的趨勢性未來。

同日晚，由DA AGE舉辦的“為什么RWA+NFT會成為Ordi之后的全新爆點”論壇，嘉賓們一致表示，RWA將物理世界的真實資產帶入區塊鏈，將解決股市和企業無法精準獎勵生態貢獻者等痛點。該場直播現場突破1.27萬人次在線觀看，和前日同主題直播累計回放超4萬人次觀摩，受到大家的一致好評。[2023/6/5 21:16:53]

六十年代：「證明」==「程序」

又過了半個世紀，到了六十年代，邏輯學家HaskellCurry和WilliamHoward相繼發現了在「邏輯系統」和「計算系統—Lambda演算」中出現了很多「神奇的對應」，這就是后來被命名的「Curry-HowardCorrespondence」。這個發現使得大家恍然大悟，「編寫程序」和「編寫證明」實際在概念上是完全統一的。而在這之后的50年，相關理論與技術發展使得證明不再停留在草稿紙上，而是可以用程序來表達。這個同構映射非常有趣：程序的類型對應于證明的定理；循環對應于歸納；……）。在直覺主義框架中，證明就意味著構造算法，構造算法實際上就是在寫代碼。(反過來也成立，嗯，碼農碼的不是代碼，是數學證明，:P)目前在計算機科學領域，許多理論的證明已經從紙上的草圖變成了代碼的形式，比較流行的「證明編程語言」有Coq，Isabelle，Agda等等。采用編程的方式來構造證明，證明的正確性檢查可以機械地由程序完成，并且許多啰嗦重復性的勞動可以由程序來輔助完成。數學理論證明的大廈正在像計算機軟件一樣，逐步地構建過程中。1996年12月W.McCune利用自動定理證明工具EQP證明了一個長達63年歷史的數學猜想「Ronbins猜想」，『紐約時報』隨后發表了一篇題為「ComputerMathProofShowsReasoningPower」的文章，再一次探討機器能否代替人類創造性思維的可能性。利用機器的輔助確實能夠有效幫助數學家的思維達到更多的未知空間，但是「尋找證明」仍然是最有挑戰性的工作。「驗證證明」，則必須是一個簡單、機械、并且有限的工作。這是種天然的「不對稱性」。

八十年代：「證明」==「交互」

時間撥到1985年，喬布斯剛剛離開蘋果，而S.Goldwasser博士畢業后來到了MIT，與S.Micali，Rackoff合寫了一篇能載入計算機科學史冊的經典：『交互式證明系統中的知識復雜性』。

他們對「證明」一詞進行了重新的詮釋，并提出了交互式證明系統的概念：通過構造兩個圖靈機進行「交互」而不是「推理」，來證明一個命題在概率上是否成立。「證明」這個概念再一次被拓展。交互證明的表現形式是兩個的「對話腳本」，或者稱為Transcript。而這個對話過程，其中有一個顯式的「證明者」角色，還有一個顯式的「驗證者」。其中證明者向驗證者證明一個命題成立，同時還「不泄露其他任何知識」。這種就被稱為「零知識證明」。再強調一遍，證明凝結了「知識」，但是證明過程確可以不泄露「知識」，同時這個證明驗證過程仍然保持了簡單、機械，并且有限性。這聽上去是不是有點「反直覺」？

美聯儲會議紀要：聯邦基金利率的最終目標已變得比加息速度更重要:金色財經報道，美聯儲會議紀要：隨著貨幣政策接近“足夠限制性”的水平，與會者強調，聯邦基金利率的最終目標已變得比加息速度更重要。

美聯儲會議紀要前，據CME“美聯儲觀察”：美聯儲12月加息50個基點至4.25%-4.50%區間的概率為75.8%，加息75個基點的概率為24.2%；到明年2月累計加息75個基點的概率為29.5%，累計加息100個基點的概率為55.8%，累計加息125個基點的概率為14.8%。[2022/11/24 8:02:10]

交互式證明

Alice:我想向你證明我有一個方程的解，

w^3-

Bob:好啊，我聽著呢

Alice:但是我不會告訴你x具體是多少，

除非你愿意掏錢，我才告訴你。

Bob:可以啊，但是你要先證明你

有方程的解，我再給錢你。

Alice:@#$%^&

Bob:??????

Alice:&*#!

Bob:??????

......

Alice:好了，完了

Bob:好吧，你確實有方程的解，

不過是不是我掏了錢，

你就會把答案告訴我？

Alice:別廢話，掏錢！

上面例子就是一個「交互式證明」。假設Alice知道方程的解，f(w)=0，那么Alice如何讓Bob確信她知道w呢？Alice在「黑科技階段」告訴了Bob一大堆的信息。好了，關鍵問題是，Bob能不能從Alice所說的一大堆信息中猜出w到底是幾，或者能分析出關于w的蛛絲馬跡呢？如果Bob有這個能力，Bob也許就沒必要掏錢了，因為他已經獲得了這個值錢的信息。

請注意，如果Alice與Bob的對話是「零知識」的，那么Bob除了知道w是f(w)=0的解之外，不能獲取其它任何關于w的信息。這一點非常重要，這是保護Alice的利益。現在回顧一下「零知識證明」這個詞，英文叫「Zero-KnowledgeProof」。這個詞包含三個關鍵部分：

零

知識

證明

各位可能已經有點感覺了，我們來嘗試著解讀一下：

零：Alice泄露了關于w的「零」知識，也就是沒有泄露知識。

知識：這里就是指的就是w。

證明：就是Alice與Bob對話中的「黑科技部分」。

好了，證明也就是黑科技部分還沒講。看官們不要急，且聽我慢慢道來。

零知識證明有什么用處？

一提零知識證明技術，很多人就想到了匿名Coin，比如Monero,比如ZCash。確實，這幾個Coin很好地普及了零知識證明，我本人也是通過ZCash才第一次聽說了零知識證明這個詞。但是在更深入地了解這個技術之后，深深感覺這個技術的威力遠不止這一點。

體育和娛樂公鏈Chiliz宣布開始Scoville測試網第4階段:10月24日消息，據官方消息，體育和娛樂公鏈 Chiliz 宣布開始 Scoville 測試網第 4 階段 CAYENNE。目前開發者指南和 GitHub repo 已經發布，用戶可根據指南運行 Scoville 測試網節點。[2022/10/24 16:37:08]

零知識證明技術可以解決數據的信任問題，計算的信任問題！張三說他有100塊錢，李四說他北大畢業，王五說要和八菲特共進午餐。空口無憑，Showmetheproof。

那么「零知識證明」能解決數據的信任如何理解呢？在上一篇文章『zkPoD:區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易』里面，我提到了一個概念「模擬」：

零知識證明技術可以「模擬」出一個第三方，來保證某一個論斷是可信的換句話說，當我們收到一個加了密的數據，然后還有一個零知識證明。這個零知識證明是說「關于數據的X斷言成立」，那么這等價于有一個天使在我們耳邊悄聲說，「關于數據的X斷言成立」！

對于這個X斷言，可以非常靈活，它可以是一個NP復雜度的算法。大白話講只要我們能寫一段程序來判斷一個數據是否滿足X斷言，那么這個斷言就可以用零知識證明的方式來表達。通俗點講，只要數據判定是客觀的，那么就零知識證明就適用。零知識證明的一些用處：

數據的隱私保護：在一個數據表格中，多多少少都有一些信息不想被暴露，比如當年我的成績單，我只想向人證明，我的成績及格了，但是我不想讓別人知道我到底考了61分還是62分，這會很尷尬。我沒有心臟病，但是保險公司需要了解這一點，但是我不想讓保險公司知道我的隱私信息。那我可以證明給保險公司看，我沒有心臟病，但是病歷的全部并不需要暴露。我是一家企業，我想向銀行貸款，我只想向銀行證明我具備健康的業務與還款能力，但是我不想讓銀行知道我們的一些商業秘密。

計算壓縮與區塊鏈擴容：在眾多的區塊鏈擴容技術中，Vitalik采用zkSNARK技術能夠給現有的以太坊框架帶來幾十倍的性能提升。因為有了計算的證明，同樣一個計算就沒必要重復多次了，在傳統的區塊鏈架構中，同樣的計算被重復多次，比如簽名的校驗，交易合法性校驗，智能合約的執行等等。這些計算過程都可以被零知識證明技術進行壓縮。

端到端的通訊加密：用戶之間可以互相發消息，但是不用擔心服務器拿到所有的消息記錄，同時消息也可以按照服務器的要求，出示相應的零知識證明，比如消息的來源、與發送的目的地。

身份認證：用戶可以向網站證明，他擁有私鑰，或者知道某個只要用戶自己才知道的秘密答案，而網站并不需要知道，但是網站可以通過驗證這個零知識證明，從而確認用戶的身份

去中心化存儲：服務器可以向用戶證明他們的數據被妥善保存，并且不泄露數據的任何內容。

信用記錄：信用記錄是另一個可以充分發揮零知識證明優勢的領域，用戶可以有選擇性的向另一方出示自己的信用記錄，一方面可以有選擇的出示滿足對方要求的記錄分數，同時證明信用記錄的真實性。

構造完全公平的線上數字化商品的交易協議。

更多的例子，可以是任何形式的數據共享，數據處理與數據傳輸。

Coin Center：美財政部制裁Tornado Cash或違反了正當程序及憲法權利:金色財經報道，加密貨幣倡導組織Coin Center發布博客文章稱，美國財政部外國資產控制辦公室(OFAC)制裁Tornado Cash可能在法律和憲法上存在缺陷，Coin Center表示，“我們認為OFAC通過將某些Tornado Cash智能合約地址添加到SDN列表中超越了其法律權限，這一行為可能違反了正當程序及憲法權利”。

Coin Center認為，智能合約不能成為可制裁的實體，這樣的標準對全世界的代碼人員來說都是危險的。文章稱，“這一行動發出了一個信號，實際上似乎是為了發出一個信號，美國人不應該使用某種工具和軟件，即使是完全合法的目的”。Coin Center承諾其第一步是與OFAC合作，但該組織也表示，“我們將開始與律師探討對這一行動的法庭挑戰。敬請期待。”[2022/8/16 12:27:43]

舉例：地圖三染色問題

下面講一個經典的問題，地圖的三染色問題。如何用三種顏色染色一個地圖，保證任意兩個相鄰的地區都是不同的顏色。我們把這個「地圖三染色問題」轉變成一個「連通圖的頂點三染色問題」。假設每個地區都有一個首府，然后把相鄰的節點連接起來，這樣地圖染色問題可以變成一個連通圖的頂點染色問題。下面我們設計一個交互協議：

「證明者」Alice

「驗證者」Bob

Alice手里有一個地圖三染色的答案，請見下圖。這個圖總共有6個頂點，9條邊。

現在Alice想證明給Bob她有答案，但是又不想讓Bob知道這個答案。Alice要怎么做呢？Alice先要對染過色的圖進行一些「變換」，把顏色做一次大挪移，例如把所有的綠色變成橙色，把所有的藍色變成綠色，把所有的綠色變成橙色。然后Alice得到了一個新的染色答案，這時候她把新的圖的每一個頂點都用紙片蓋上，然后出示給Bob看。

看下圖，這時候Bob要出手了，他要隨機挑選一條「邊」，注意是隨機，不讓Alice提前預測到的隨機數。

假設Bob挑選的是最下面的一條邊，然后告訴Alice。

這時候Alice揭開這條邊兩端的紙片，讓Bob檢查，Bob發現這兩個頂點的顏色是不同的，那么Bob認為這次檢驗同構。這時候，Bob只看到了圖的局部，能被說服剩下的圖頂點的染色都沒問題嗎？你肯定覺得這遠遠不夠，也許恰好Alice蒙對了呢？其它沒暴露的頂點可能是胡亂染色的。沒關系，Bob可以要求Alice再來一遍，看下圖

Alice再次把顏色做一次變換，把藍色改成紫色，改綠色改成棕色，把橙色改成灰色，然后把所有的頂點蓋上紙片。然后Bob再挑選一條邊，比如像上圖一樣，選擇的是一條豎著的邊，然后讓Alice揭開紙片看看，如果這時候Bob再次發現這條邊兩端的頂點顏色不同，那么Bob這時候已經有點動搖了，可能Alice真的有這個染色答案。可是，兩次仍然不夠，Bob還想再多來幾遍。那么經過反復多次重復這三個步驟，可以讓Alice作弊并能成功騙過Bob的概率會以指數級的方式減小。假設經過n輪之后，Alice作弊的概率為

這里|E|是圖中所有邊的個數，如果n足夠大，這個概率Pr會變得非常非常小，變得「微不足道」。可是，Bob每次看到的局部染況都是Alice變換過后的結果，無論Bob看多少次，都不能拼出一個完整的三染色答案出來。實際上，Bob在這個過程中，雖然獲得了很多「信息」，但是卻沒有獲得真正的「知識」。

Nansen：NFT每周交易額觸及12個月最低點:8月1日消息，區塊鏈數據分析平臺Nansen在其官方社交媒體表示，NFT每周交易額觸及自2021年7月以來的最低點。[2022/8/1 2:51:41]

信息vs.知識

信息「Information」

知識「Knowledge」

在地圖三染色問題的交互證明中，當重復交互很多次之后，Bob得到了大量的信息，但是這好比Alice發給Bob一堆隨機數一樣，Bob并沒有「知道」更多的東西。打個比方，如果Alice告訴Bob「11=2」，Bob得到了這個信息，可是Bob并沒有額外獲取更多的「知識」，因為這個事實人人皆知。假如Alice告訴Bob2^2^41-1這個數是一個質數，很顯然這個是「知識」，因為要算出來這個數是不是一個質數，這需要耗費大量的算力。假如Alice告訴Bob，總共有兩個頂點用了綠顏色，那么Bob就獲得了寶貴的「知識」，因為基于他剛剛獲取的這個信息，Bob可以用更短的時間用一臺圖靈機去求解三染色問題。假如Alice又透露給Bob，最左邊的頂點顏色是用橙色，那么很顯然，這個「信息」對于Bob求解問題并沒有實質上的幫助。我們可以嘗試定義一下，如果Bob在交互過程中獲得的「信息」，可以幫助提升Bob直接破解Alice秘密的能力，那么我們說Bob「獲得了知識」。由此可見，知識這個詞的定義與Bob的計算能力相關，如果信息并不能增加Bob的計算能力，那么信息不能被稱為「知識」。比如在Alice與Bob交互過程中，Alice每次都擲一個硬幣，然后告訴Bob結果，從信息角度看，Bob得到的信息只是一個「事件」，然而Bob并沒有得到任何「知識」，因為Bob完全可以自己來擲硬幣。下面引用『FoundationsofCryptography——BasicTools』一書中的總結

「知識」是與「計算難度」相關，而「信息」則不是

「知識」是與公共所知的東西有關，而「信息」主要與部分公開的東西有關

注：曾有人問我，這里的信息與知識的定義是否與Kolmogorov復雜性有關。根據算法信息論，一段字符串的信息量可以用產生字符串的最小程序的長度來測量。這個問題我不是很懂，希望路過的專業人士留言。

可驗證計算與電路可滿足性問題

看了上面的地圖三染色問題，大家是不是沒有感覺，好像這只是一個學術問題，如何跟現實問題關聯起來？地圖三染色問題是一個NP-Complete問題，這是「計算理論」中的一個名詞。另外有一個叫做「電路可滿足問題」也是同樣是NP-Complete問題。NP-Complete是一類問題，他的求解過程是多項式時間內難以完成的，即「求解困難」，但是驗證解的過程是多項式時間可以完成的，即「驗證簡單」。那什么是電路呢？下面是三個不同的「算術電路」：

可以看到一個電路由很多個門組成，其中有加法門，還有乘法門。每一個門有幾個輸入引腳，有幾個輸出引腳。每一個門做一次加法運算，或乘法運算。別看這么簡單，我們平時跑的代碼，都可以用算術電路來表示。這意味著什么呢？我們下面結合「零知識證明」與「電路可滿足性問題」來試著解決數據的隱私保護問題。下面請思考一個場景：Bob交給Alice一段代碼P，和一個輸入x，讓Alice來運行一遍，然后把運行結果告訴Bob。可能這個計算需要消耗資源，而Bob把計算過程外包給了Alice。然后Alice運行了一遍，得到了結果y。然后把y告訴Bob。下面問題來了：

如何讓Bob在不運行代碼的前提下，相信代碼P運行的結果一定是y呢？這里是思考時間，大家可以想個五分鐘……Alice的一種做法是可以把整個計算過程用手機拍下來，這個視頻里面包含了計算機CPU，還有內存，在整個運行過程中的每一晶體管的狀態。很顯然這么做是不現實的。那么有沒有更可行的方案呢？答案是Bob把程序P轉換成一個完全等價的算術電路，然后把電路交給Alice。Alice只要計算這個電路就可以了，然后這個過程是可以用手機拍下來的，或者用紙記下來，如果電路規模沒有那么大的話。Alice只要把參數6輸入到電路，然后記錄下電路在運算過程中，所有與門相連的引腳線上的值。并且最后的電路輸出引腳的值等于y，那么Bob就能確信Alice確實進行了計算。Alice需要把電路的所有門的輸入與輸出寫到一張紙上，交給Bob，這張紙就是一個計算證明。這樣Bob完全可以在不重復計算電路的情況下來驗證這張紙上的證明對不對，驗證過程很簡單：Bob依次檢查每一個門的輸入輸出能不能滿足一個加法等式或者一個乘法等式。比如1號門是一個加法門，它的兩個輸入是3，4，輸出是7，那么很容易就知道這個門的計算是正確的。當Bob檢查完所有的門之后，就能確信：Alice確確實實進行了計算，沒有作弊。這張紙上的內容就是「滿足」算術電路P的一個解「Solution」。

所謂的電路可滿足性就是指，存在滿足電路的一個解。如果這個解的輸出值等于一個確定值，那么這個解就能「表示」電路的計算過程。對于Alice而言，Bob如果用這種方式驗證，她完全沒有作弊的空間。但是這種方法很顯然有個弊端：

弊端一：如果電路比較大，那么證明就很大，Bob檢查證明的工作量也很大。

弊端二：Bob在驗證過程中，知道了所有的電路運算細節，包括輸入。

黑科技

我們再對剛才的Alice與Bob的場景做些修改。假如，Alice自己還有一個秘密，比如說網銀密碼。而Bob想知道Alice的網銀密碼的長度是不是20位長。而Alice想了下，告訴他密碼長度應該問題不大。這時候Bob把一個計算字符串長度的代碼轉換成了電路Q，并且發給Alice。Alice用電路Q算了一下自己的密碼，然后把電路所有門的引腳發給了Bob，并帶上運算結果20。Wai……t，這是有問題的，Bob拿到電路運算過程中的所有內部細節之后，不就知道密碼了嗎？是的，Alice顯然不能這么做。那么Alice應該怎么做？答案是有很多種辦法，熱愛區塊鏈技術的讀者最耳熟的就是zkSNARK，還有zkSTARK，子彈證明BulletProof，以及一些比較小眾的技術，都可以幫Alice做到：

Alice以一種零知識的方式，向Bob證明她計算過了電路，并且使用了她的秘密輸入。換句話說，這些「零知識的電路可滿足性證明協議」為Alice提供了強大的武器來向Bob證明她的網銀密碼長度為20，并且除此之外，Bob再也得不到任何其它有用的信息。除了網銀密碼，Alice理論上可以向Bob證明任何她的隱私數據的某些特性，但是并不暴露任何別的信息。

「零知識的電路可滿足性證明協議」提供了一種最直接的保護隱私/敏感數據的技術最近幾年來，零知識證明構造技術發展日新月異，并且在區塊鏈技術領域得到了越來越多的應用。最新的零知識證明技術，有的技術可以讓Bob高速驗證證明；有的技術可以讓所有吃瓜群眾幫忙驗證；有的技術支持非常小的證明大小。后續文章我們會逐步展開介紹。

寫在最后

無論是精妙的數論定理，地圖三染色問題，還是電路可滿足性問題。證明存在的意義是什么？所有的證明都體現了「證明」與「驗證」的「不對稱性」。證明可能是一個非常耗費算力，或者腦力的活動，無論是耗時幾百年的「費馬大定理」，還是比特幣中的POW證明，這些證明都凝結了在尋找證明過程中所消耗的能量，證明過程可能是超乎尋常的復雜，偶爾需要天才橫空出世。而驗證過程一定是一個非常簡單的，機械的，在有效時間內且能終止的活動。某種意義上，這個不對稱性真正體現了證明的意義，展示了零知識證明的價值。

粗略看，「證明」是「邏輯」的產物，但「邏輯」與「計算」卻又有著密不可分的聯系，大家可能模模糊糊感覺到一些關于「證明」與「計算」之間的關聯，它們貫穿始終：如機械推理、證明表達、交互計算。這是一個有趣但更宏大的哲學問題。

文章內容難免有不準確或不嚴謹的描述，還請各位專業人士撥冗指正。

參考文獻

西蒙,辛格,薛密.費馬大定理:一個困惑了世間智者358年的謎.上海譯文出版社,1998.AlecWilkinson.ThePursuitofBeauty:YitangZhangsolvesapure-mathmystery.TheNewYorker.Feb.2015.馬丁,戴維斯,張卜天.邏輯的引擎.湖南科學技術出版社,2012.RaymondSmullyan.G?del'sIncompletenessTheorems,OxfordUniv.Press.1991.Turing,Alan."Oncomputablenumbers,withanapplicationtotheEntscheidungsproblem."ProceedingsoftheLondonmathematicalsociety2.1(1937):230-265.Pierce,BenjaminC.,etal."Softwarefoundations."中文譯文:<https://github.com/Coq-zh/SF-zhKolata,Gina."Computermathproofshowsreasoningpower."MathHorizons4.3(1997):22-25.Goldwasser,Shafi,SilvioMicali,andCharlesRackoff."Theknowledgecomplexityofinteractiveproofsystems."SIAMJournaloncomputing18.1(1989):186-208.zkPoD:區塊鏈，零知識證明與形式化驗證，實現無中介、零信任的公平交易.安比實驗室.2019.Oded,Goldreich."Foundationsofcryptographybasictools."(2001).Gennaro,Rosario,etal."QuadraticspanprogramsandsuccinctNIZKswithoutPCPs."AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques.SpringerBerlin,Heidelberg,2013.Ben-Sasson,Eli,etal."Scalable,transparent,andpost-quantumsecurecomputationalintegrity."IACRCryptologyePrintArchive2018(2018):46.Bünz,Benedikt,etal."Bulletproofs:Shortproofsforconfidentialtransactionsandmore."2018IEEESymposiumonSecurityandPrivacy(SP).IEEE,2018.

Tags：BOBALILICALICEbobt幣怎么挖ALINK幣alice幣怎么樣My Neighbor Alice

瑞波幣