安比實驗室郭宇：當深度神經網絡遇上零知識證明

編者按：本文來自萬向區塊鏈（ID：gh_1b8639a25429），Odaily經授權轉載。

編者按：本文來自

萬向區塊鏈（ID：gh_1b8639a25429）

萬向區塊鏈（ID：gh_1b8639a25429）

，Odaily經授權轉載。

萬向區塊鏈（ID：gh_1b8639a25429）

，Odaily經授權轉載。

編者按：本文來自

萬向區塊鏈（ID：gh_1b8639a25429）

零知識證明

，Odaily經授權轉載。

本文為萬向區塊鏈蜂巢學院線上公開課第二十九期的分享內容。本期邀請了安比（SECBIT）實驗室創始人郭宇，帶來分享《當深度神經網絡遇上零知識證明》。

今天跟大家一起交流下「當深度神經網絡遇上零知識證明」。

零知識證明

「零知識證明」這個概念在區塊鏈底層技術架構裡並不陌生，它是在1985 年時由Goldwasser、Micali 和Rackoff 三人提出（如圖）。雖然長期以來「零知識證明」只是局限在計算理論研究裡的一個小領域，但是它帶來的影響非常深遠。

零知識證明里面有個詞「證明」，這個概念在整個人類文明發展歷史中經過了很多次範式轉換。在古希臘，「證明」是一種巧妙的數學技巧；到20 世紀初，數學證明在第三次數學危機中被重新詮釋，引入形式邏輯被形式化，因而從此誕生了計算理論與計算機。

到70 年代，程序和證明之間的奇妙關聯被發現，現代函數式編程與自動定理證明的很多概念被引入；到80 年代，「證明」的概念被延伸到了交互系統。到了80 年代之後交互式證明系統無論是從哲學意義上，還是從理論技術方面，都帶來了革命性的新的見解。

在我第一次看到零知識證明概念的時候，第一反應是這個東西非常反直覺。為什麼「反直覺」？我先來簡單介紹一下零知識證明基本的框架。

在零知識證明中一定有像右邊這樣一個人，我們把他稱之為Bob，左邊可能是一台不受信任的機器。此時，假如說Bob 有一個計算任務要交給左邊的機器來運行，但這機器本身可能會受人控制。 Bob 需要把一個「F （）」函數作為計算任務，帶上輸入「X」，交給左邊機器，讓它去完成這個計算任務。因為這個計算過程發生在左邊的機器上，對於Bob 來說並沒有見證整個計算過程，那Bob 憑什麼相信計算結果Y=F （X，W）的式子能成立呢。並且運算過程中摻入了一些只有左邊機器知道的秘密數據（W），而Bob 並沒有W，因而Bob 是不能通過復現計算過程來獲知計算結果是否正確。在這樣的情況下，能不能讓Bob 還能相信計算結果是對的呢？

一句話，零知識證明能夠神奇地讓Bob 相信計算結果是正確的。這聽上去有點不可思議，信任計算結果Y 是基於對左邊機器的不信任，也就是說零知識證明它憑空地產生了一些信任，這正是反直覺所在。設想一下，在兩個人互相完全不信任的情況下，居然可以通過某種東西建立信任，這點是非常非常有趣的。

zkSNARK

反直覺的零知識證明我總結一下，它可以這麼來理解：可以保證一個遠程計算過程的完整性與機密性。

1、完整性。雖然我沒有看見在遠程發生的計算過程，雖然沒有見證它的過程，但知道這計算過程一定是真實發生過的，而且計算結果是正確的，也就說計算過程並沒有被惡意的修改或者是被偽造。

2、機密性。雖然我見證不了計算過程，同時不可能知道計算過程中的一些中間結果，也不可能知道它內部的一些信息，所以說整個計算過程，包括一些秘密輸入，對我來說是機密的、保密的。

這就是反直覺零知識證明所能達到的效果。零知識證明到底有什麼用處呢？我覺得最直接的用處就是所謂的「數據隱私保護」。我簡單列了一些，例如個人數據：健康數據、銀行流水、出行安排、通信記錄。其實我們是不想讓任何人知道我們的健康狀況，包括心跳、醫療記錄，也不想讓人知道每天花了多少錢。但是我們又想享受第三方的服務，比如說出門打車，想讓有些人知道自己在哪，但又不想讓其他人知道，或者說只想讓他知道一個大概的地方，不想讓他知道具體的位置。

企業數據：人事檔案、倉儲物流、財務賬本、客戶信息，傳統意義上這些都是非常機密的數據，但是為了能夠最大發揮企業間協作的效果，必須要共享一部分數據。零知識證明提供了一種既能夠保證數據的隱私，同時還能共享數據的方式，所以說它對我們未來生活、工作的最大影響就是能夠提供非常有效的數據隱私保護技術。

零知識證明在區塊鏈底層技術中還有很多有趣的用處，自從1985 年零知識證明被提出來之後，它長期停留在理論結果層面，直到區塊鏈技術得到大規模應用之後，大概自2015年-2020 年，零知識證明在區塊鏈上得到了廣泛的應用。包括區塊壓縮、保護交易匿名性、身份隱私、共享數據、鏈下數據存儲完整性等等之類，在區塊鏈行業的技術朋友們應該對這些都不太陌生。

接下來介紹兩個很基本的概念。

非交互式的零知識證明

我們前面講過，零知識證明提出來的時候對「證明」的範式做了全新的革新，以前證明是寫在紙上，比如說老師出了一道題考試，要證明它，要把證明過程寫出來。而零知識證明是一種交互式證明，通過和老師對話，可以在不告訴老師任何證明過程的情況下讓老師相信我。

為什麼又有了非交互式零知識證明呢？非交互式零知識證明是用一些特殊的技巧，能夠把交互式的證明過程折疊成非交互式的零知識證明。非交互零知識證明在區塊鏈領域的應用更加廣泛。

這也是一個很常見的詞，當然它在學術領域也有很多不那麼一致的解釋。不嚴謹的說，zkSNARK 是一種特殊的NIZK，即特殊的非交互式零知識證明，特殊在哪呢？

下面列了三點：

1、簡潔。它生成的證明非常小，有多小呢？通常是KB 量級，甚至可以小到200 個字節以內。別看只有這幾百個字節，但它能代表的計算過程可以非常非常龐大，它所能保護的數據也可以是上TB 量級的。

2、Argument。是零知識證明的一種，稍後會簡單解釋下。

3、zkSNARK 最後有一個「K」，就是Knowledge 的意思。含義是證明是關於「knowledge」的證明，這個「knowledge」是有一個數學定義。

隱私保護、區塊鏈與零知識證明

講這個概念之前先要講一個非常重要的密碼學概念——承諾。如圖，大家可以看到左邊是一個數據庫，這個數據庫非常非常大，可能是超過1TB 那麼大，可以用密碼學的手段把它變成很小很小的一段字節，大概小於100 字節。不管這個數據庫多大，最後承諾都可以壓成不超過100 字節這麼大的數據。

別看只有100 多個字節，它可以和數據庫建立唯一的綁定關係，如果當數據庫裡發生任何的改變，這個承諾就必須跟著一起改變。承諾就好比是「一把鎖」，只要有人把承諾記下來之後，數據庫只要有任何的修改，承諾就會發生巨大的變化。

承諾有兩個性質：

性質一：Binding，一個承諾綁定一個原始數據集（無法篡改）。這個數據集可能非常大，但可以用一個非常小的承諾給綁定起來。

假如有很多數據庫，比如說出行記錄、銀行各有一個數據庫，可以生成兩個承諾，然後把承諾上鍊，當把承諾放在區塊鏈上之後就會有一個效果，就是再也不能反悔去修改數據庫了，但把承諾上鍊之後可以給大家看，大家可以通過承諾訪問數據庫，當然是有選擇性的開放，或者把數據庫的數據做一些處理之後開放。但因為有這個承諾被鎖定在鏈上，所以說不可能作弊。把數據交給另外一個人之前可以做很複雜的處理，可以把裡面的敏感數據刪掉，這麼做一定是非常誠實，並沒有造假的，因為承諾在鏈上。

zkSNARK 原理

承諾聽上去也挺神奇，卻是很傳統很常用，但是非專業人士了解很少的的密碼學工具。承諾其實有很多種實現方法，最簡單的是可以用一些像Hash 運算。還有Merkle Tree 、Pedersen Commitment 或者是Polynomial Commitment、Elgamal Encryption，這些都是能實現承諾。

承諾中有兩類很關鍵，這是從密碼學理論的角度來分析：第一類：Computational Binding and Perfect Hiding。第二類：Perfect Binding and Computational Hiding。

所謂的Perfect Hiding 就是承諾絕對不可能洩露一絲一毫，完美的隱藏了原始數據，但它的綁定關係是Computational，如果想像未來100 年後有人擁有超級量子計算機，它遠超現在的計算能力，那時候就可以造假，偽造一個和原數據不關聯的假承諾。

另外一類是反過來的，它的綁定關係是Perfect Binding，有超級量子計算機也不可能去造假，但是它的Hiding 是Computational，也就說如果100 年以後有超級量子計算機出來之後可以破解現在產生承諾，並能夠從中間提取出來一些有用的信息。

已有理論證明，在Binding 和Hiding 都很完美的承諾方案是不可能存在的。但是在用來做隱私保護的零知識證明方面，我們通常用第一類承諾，也就它是Perfect Hiding，但承諾是Computational Binding。因為我們要把承諾上鍊，上鍊就意味著100 年以後它仍然還被所有人看得見，但不用擔心100 年以後這個信息真的能被別人破解。另外，這一類的承諾可以產生非常簡潔的零知識證明，這就是前面我提到的Argument。

zkSNARK 原理

憑什麼能夠做到用100 個字節去承諾一個數據庫，同時還能去證明這些數據滿足一定的性質，這聽上去挺不可思議的。

首先再回顧下什麼叫「零知識證明」？就是右邊Bob 說要做一個計算，把計算給遠程一台不太相信的機器，這個機器可能已經被黑客控制了或者這個人可能會搗亂，但沒關係，把函數給它，輸入X，過一會交給我一個Y。雖然不相信那台機器，但因為看見Y 了，雖然對Y 也是有懷疑的，但因為檢查了附加的零知識證明，零知識證明告訴我這個Y 是真的，我就相信了。這個怎麼做到的呢？

先回到一個最樸素的想法，如果有台機器去跑我的程序，我看不見肯定不放心，那最簡單的做法就是拿一個攝像機從頭到尾把整個計算過程給錄製下來，拿到視頻之後可以一幀一幀的去檢驗，是不是計算的每一步都是正確的。這個很傻，但理論上也許可行。

但顯然方案非常不實用，因為機器在跑的時候，機器的內存狀態非常大，比方說4G 內存，把整個過程錄下來視頻文件會超級大，以至於無法驗證。

有沒有辦法改進呢？我們採用計算電路的計算模型，而不是CPU 加內存的模型。算術電路計算模型和計算機CPU 跑程序的表達能力是大致相當的，基本上常見的計算都可以表達。

算術電路由一些互相連接的「門」組成，有「乘法門」與「加法門」。輸入從電路的左邊輸入，運算完右邊的輸出線上產生運行結果，整個過程就是在算「+」、「×」，不要小看這兩種運算，它們能表達絕大多數運算。

算術電路的好處是它的計算過程是可以拍照的。這個時候只要相機按快門拍一下，把電路的全景拍下來，就相當於記錄了所有的計算過程。這樣一來，驗證計算就不再是驗證視頻，視頻是一幀一幀看的，但是照片就一張照片，只要驗證照片的每個細節就可以。

怎麼驗證電路計算呢？要驗證每一個門的運算，對於每一個加法門，驗證左輸入和右輸入加起來等不等於輸出。對於乘法門，驗證左輸入和右輸入乘起來等不等於輸出。只要耐心地挨個檢查每一個門，肯定就沒問題。

如果有上百億個門，可能驗證要花不止一年的時間。有沒有一種辦法把這麼多門的驗證過程變的簡單？用「多項式編碼」這個數學工具可以做到這一點。

比如說有一些數：y0、y1、y2，我們把他們放到一個XY 軸平面上，變成一個個的點，然後找到一根曲線恰好通過那些點，相當於用一根曲線編碼了所有的數值，從y0 到yn。

編碼成曲線有什麼好處呢？好處是如果我想改其中某一個值yk，哪怕只要改動一點點，整條曲線就會發生明顯的擾動。擾動後的曲線和原曲線只在n 個點處相同，而其它的點都產生了偏離。多項式編碼之後能放大任何一個哪怕微小的修改。於是我們可以通過隨機驗證一個點，就能檢查曲線編碼的點有沒有被修改過。

接下來可以對剛才算術電路中所有乘法門的左輸入門、右輸入門、輸出門做三個不同的多項式編碼，形成三根曲線。現在只要有三根曲線，驗證這三根曲線（三個多項式）之間滿足乘法關係就夠了。驗證乘法關係只需要隨機抽樣X 軸上的一個點均可，不需要再驗證一百億個門。雖然驗證了這三根曲線，但顯然驗證者看到了太多的秘密，零知識證明要保證計算過程的秘密不被洩漏。怎麼做？可以把多項式運算同態映射到橢圓曲線群上。

整數有限域的加法運算會映射到橢圓曲線群上的二元運算。整數乘法運算可以同態映射到橢圓曲線群上的雙線性配對（Pairing）操作，乘法只能是單乘法，但足可以驗證算術電路的運算關係。

這個過程看似簡單，但zkSNARK 的研究是基於許許多多的密碼學家的苦苦探索，路線可以追溯到IKO07 （2007 年），2010 年Groth 有了初步想法，重點的突破是2013 年，而Groth16 的改進方案是現在業界最流行的零知識證明算法。還有一些非常新改進方案如：Marlin、Aurora、Spartan、Fractal，都是由GGPR13 算法不斷改進一路發展過來的。

2013 年的GGPR13 論文是比較大的突破，許多美妙的想法都來源於它。論文的四位作者是Rosario Gennaro、Craig Gentry、Bryan Parno、Mariana Raylova。

看一下GGPR13/Pinocchio/Groth16 框架。當我們想表達任何計算的時候，先用高級語言編寫代碼，然後通過compiler 編譯成算術電路，再通過矩陣表示產生R1CS 矩陣，並通過多項式編碼產生QAP，最後通過Trusted-Setup 產生：Proving Key、Verifying Key。用Proving Key 可以證明計算過程，而通過Verifying Key 就可以知道證明π是對的。

零知識證明+深度神經網絡

有了零知識證明之後我們可以為數據庫計算承諾並發佈到鏈上，通過Commitment 把數據庫放到鏈上後可以做很多很多事情，可以利用數據庫產生大量有用的信息，在不暴露個人隱私的情況下能夠將信息共享給朋友、企業以及全社會。接下來介紹一下我們團隊在深度網絡方面做的階段性成果。

圖像識別用處很廣，這是一個標準的圖像設別的模型，標準的測試用例裡有飛機、汽車、鳥、狗等，分辨率是224×224。接下來要做隱私保護+機器學習（零知識證明+深度神經網絡）。

左邊有個數據庫，數據庫裡面有很多隱私信息，經過機器學習（訓練）後產生人工智能模型。 Alice 不希望暴露模型，畢竟模型裡能反映出個人隱私。

但Alice 覺得模型又可以給Bob 提供有價值的信息，Bob 就會提供一張圖片交給Alice 說你來幫我識別一下圖片，但是我又不知道你的訓練集的細節。 Alice 就可以拿著圖片放到模型裡進行識別並產生結果，同時還附帶了零知識證明。如果模型產生的結果是識別出了一隻貓，但是我還告訴你零知識證明，證明這個結果確實是通過某個秘密模型識別出來的，當然貓狗不需要證明也能看出來，但對於有些機器學習場景是沒有辦法確定預測結果是否可信的。

比如醫療診斷拍一張片子有沒有癌症的早期跡象，這個結果沒有辦法通過看片子看出來，但模型可以告訴你是非常健康的。你不相信沒關係，零知識證明可以告訴你這確實是通過非常可靠的X 光片數據庫推斷出來的結果。

模型可以承諾上鍊，使得Alice 絕對不可能欺騙Bob，關鍵的是你不再需要信任Alice 這個人是好人還是壞人，如果能產生證明結果就是對的，只關心結果，不關心誰提供。

接下來做了圖像識別的實驗，是VGG16 的神經網絡模型。它是一個16 層的深度神經網絡。有大量的參數，14 個卷積層、2 個全連接層、Relu 激活函數、Max-pooling 池化。

做這件事情非常有挑戰，首先沒有任何前人的工作供我們參考。

挑戰一：如何在算術電路中進行科學計算。

科學計算裡有大量的小數與浮點數運算。我們選擇在有限域上編碼定點數，對VGG16 模型所有的數據做歸一化處理，保證所有的數不超過256。取六位小數定點數，8bit 表示整數部分，6bit 表示小數部分，用24 個bit 表示一定點數。用數字電路實現定點數上的各種運算（乘方、開方、求對數等）。

挑戰二：R1CS 矩陣巨大無比，需要PB 級別內存。

一般計算機的內存是GB 的，服務器到幾百G 內存已經算很大了。如果真的把R1CS 矩陣算術電路編碼出來，需要PB 級的內存。正常的機器難以承受。我們算了一下做VGG16 圖像識別，需要146 億個乘法門。據我們所知，這是世界上首次進行如此大規模的實用算法的零知識證明。乘法數量分佈大部分是卷積層，做深度神經網絡時大量是卷積運算，佔90% 以上。

電路矩陣太大了，我們不得不發明了一種新的零知識證明方案——CLINK，用來證明圖片識別過程。 CLINK 與其它零知識證明方案相比，採取了一些特殊的技術來處理大規模電路。

技術一：巨大電路里有著大量相重複的電路。就圖像識別而言，有非常多的捲積層，這麼多卷積層的電路部分是相似的，可以把相似的進行合併處理。

技術二：巨大電路可以進行拆解，拆成很多小電路，這樣內存可以放得下小電路，一個一個做，做完以後再鏈接起來。電路拆解完但多個電路之間連線的部分需要保護，這些值仍然是秘密，是不能暴露出來的。我們仍然用承諾把中間所有子電路之間暴露出來的連線保護起來。然後就能實現電路的拆解。

相同的子電路可以合併證明。最後對巨大電路產生了好多個零知識證明，加上中間值承諾，最後拼成完整的零知識證明。過程中為子電路產生零知識證明，對中間暴露的線計算承諾，中間值不作為公共輸入/ 輸入把結果打包再壓縮。

我們做了兩個實驗方案：

方案一（並行）：盡量發揮多核CPU 的優勢，同時並行計算VGG16，所有16 層的電路一起並行證明，所有承諾層之間的鏈接證明是同時做的。

方案二（串行）：串行一層一層來，先做第一層第二層，再做第一層和第二層之間的鏈接證明。