副標(biāo)題：zkPoD 原理解讀系列（一）

本文面向有一定密碼學(xué)基礎(chǔ)，或者對密碼學(xué)感興趣的讀者。文中雖有大量數(shù)學(xué)公式出現(xiàn)，但都比較簡單不難理解。

導(dǎo)言：zkPoD 是什么？

zkPoD 實現(xiàn)了去中心化的「零知識有條件支付」，支持上 GB 數(shù)據(jù)的零信任公平交易。關(guān)于「零知識有條件支付」的概念請看這篇概述文章 『zkPoD：區(qū)塊鏈，零知識證明與形式化驗證，實現(xiàn)無中介、零信任的公平交易』。 zkPoD 是一個全新的實現(xiàn) ZKCP 目標(biāo)的方案。目前 zkPoD 已經(jīng)支持上 GB 的數(shù)據(jù)，支持低 TPS 公鏈，也支持高 TPS 聯(lián)盟鏈；既支持二進(jìn)制數(shù)據(jù)，也支持帶有內(nèi)部豐富類型與結(jié)構(gòu)的表格數(shù)據(jù)。與傳統(tǒng)的「受信第三方」相比，zkPoD利用區(qū)塊鏈來作為一個「Trustless 第三方」，實現(xiàn)「零信任公平交易」。

zkPoD 也是一個實現(xiàn)數(shù)據(jù)與價值雙向流通的底層基礎(chǔ)協(xié)議

zkPoD 開源代碼與更多文檔請見：https://github.com/sec-bit/zkPoD-node

Proof-of Delivery (PoD) 協(xié)議

PoD 是實現(xiàn) zkPoD系統(tǒng)的核心協(xié)議。PoD 協(xié)議實現(xiàn)了借用區(qū)塊鏈智能合約來進(jìn)行「數(shù)據(jù)」和 「Token」的原子交換，并且保證買賣雙方的公平性。PoD 并沒有像 ZKCP[1] 那樣采用單一的 zkSNARK 方案來實現(xiàn)原子交換，而是利用了 Pedersen Commitment，Schnorr Protocol 等密碼學(xué)經(jīng)典方案。這樣 PoD 可以做得更高效，同時易擴(kuò)展。PoD 協(xié)議還將利用形式化的證明來構(gòu)建堅實的「信任根基」。

本文介紹一個極簡的 PoD 協(xié)議——PoD-Tiny，這個協(xié)議簡化了很多細(xì)節(jié)，并不實用，但是可以幫助讀者快速理解 PoD 的原理和面臨的挑戰(zhàn)。

假設(shè)我是賣家，而你需要從我手里買一個數(shù)據(jù)文件，這個協(xié)議的一個大致流程是：

步驟一：我把「數(shù)據(jù)」加密后，傳給你

步驟二：你把「Token」交給區(qū)塊鏈「智能合約」

步驟三：我用「密鑰」交換「智能合約」手里的「Token」，然后你緊接著可以從智能合約中讀取「密鑰」進(jìn)行「數(shù)據(jù)」解密

是不是很簡單？聰明的你此刻正在高度懷疑這個過程是不是哪有問題。

「公平交易」中的關(guān)鍵問題

關(guān)鍵問題(1)：你收到的加密數(shù)據(jù)確實是你想要的數(shù)據(jù)

關(guān)鍵問題(2)：你收到加密數(shù)據(jù)之后，不付錢就跑路怎么辦

關(guān)鍵問題(3)：而我出示給智能合約的密鑰必須是真密鑰，否則拿不到 Token

關(guān)鍵問題(4)：我出示真密鑰之后，必須要能拿到 Token

我們接下來就抽絲剝繭，討論下 PoD-Tiny 是怎么巧妙解決這些問題的。

鎖定數(shù)據(jù)的特征：Authenticator

對于關(guān)鍵問題(1)，我們需要一個錨點，什么是你想要的數(shù)據(jù)。這里簡單起見，假設(shè)我們事先約定了一個數(shù)據(jù)文件的唯一標(biāo)簽，或者特征。然后你購買的數(shù)據(jù)需要能和這個標(biāo)簽一一對應(yīng)。

一般來說，大家喜歡用 Hash 來標(biāo)記對一個字符串的特征，比如計算

h = MD5("hello,zkPoD!")

我們看下這個字符串? "hello,zkPoD!" 總共有 12 個字節(jié)大小，也就是 96 個 bit。于是我們可以將這 12 個字節(jié)轉(zhuǎn)換成一個有限域上的整數(shù)（這里我們假設(shè)有限域的大小接近 256 bit ）。這樣我們可以把這個字符串編碼成一個整數(shù)，我們姑且用一個符號表示這個整數(shù)， 假設(shè)是 m。

我們通過下面的運算產(chǎn)生這個數(shù)據(jù)的「承諾」。

A = m*G

承諾也叫 Commitment，它可以做到和數(shù)據(jù)的一一對應(yīng)，同時并且能夠隱藏數(shù)據(jù)的值。這里的 A 在 zkPoD 系統(tǒng)中被稱為「認(rèn)證信息」 Authenticator。而這里的G 是一個橢圓曲線循環(huán)群的生成元。

「認(rèn)證信息」Authenticator 可以向所有人公開，我們不用擔(dān)心會泄露原始數(shù)據(jù)信息。這是因為，通過 A 難以反算出來 m。這個逆運算是一個有限域的「求對數(shù)」運算。假如有限域比較大的話，這個對數(shù)運算是非常非常困難的，這就是常說的「離散對數(shù)難題」假設(shè)。拋開這些理論細(xì)節(jié)，我們只要知道，Authenticator 可以放心交給任何人，而不用擔(dān)心 m? 被逆向破解。

「認(rèn)證信息」為什么要采用這種「承諾」形式，而不是采用大家所熟知的 Hash 運算。這是因為「承諾」具有加法運算同態(tài)性。所謂同態(tài)性質(zhì)，大家可以這么理解：明文數(shù)據(jù)具有的某種運算，可以同態(tài)映射到密文的運算中。假設(shè)有三個數(shù)據(jù)明文，m1，m2 還有 m3，其中? m1 = m2 + m3。

他們的 Authenticator 分別計算如下：

A1 = m1*G， A2 = m2*G， A3 = m3*G，

我們可以計算 A1 ?= A2 + A3

來驗證 m1 ?= m2 + m3。大家可以發(fā)現(xiàn)，雖然一個吃瓜群眾知道了 A1，他也不能反算出m1。但是他仍然知道 m1 等于另外兩個數(shù)的和，雖然他完全不知道這三個數(shù)具體的值是多少。

注：這里的加法是模加，a + b 是? a + b mod p的簡寫。為了易讀性，后續(xù)的加減乘除一律約定是有限域上的運算。

剩下的事情就簡單了，在 PoD協(xié)議中，我們可以任選一個隨機(jī)數(shù) k 作為一次性密鑰，來加密m，計算 E(m) = k + m。 E(m) 就是加密數(shù)據(jù)。我可以把 K = k*G 也發(fā)給你，這樣你手里有三樣?xùn)|西，A ，K，還有 E(m)。你就可以用下面的公式來「同態(tài)地」校驗加了密的 E(m) 確實是數(shù)據(jù) m 的密文：

E(m)*G ?= K + A

并且，通過上面的公式，你還能知道一個關(guān)鍵信息：密鑰是一個關(guān)聯(lián)到 K 的數(shù)值。盡管這時候你完全不知道 m 和 密鑰 k。這個信息也是解決關(guān)鍵問題(3)的關(guān)鍵所在。

總結(jié)一下：

通過同態(tài)性，買家可以在數(shù)據(jù)加密的情況驗證數(shù)據(jù)是否滿足一些條件

回憶一下關(guān)鍵問題(2)：

關(guān)鍵問題(2)：你收到加密數(shù)據(jù)之后，不付錢就跑路怎么辦

解決這個問題是核心方法是「零知識證明」。如果買家拿到加密數(shù)據(jù)之后，從中分析不出來任何多余的信息，那么就不會損害賣家利益，也就能解決關(guān)鍵問題(2)。簡單講，如果加密數(shù)據(jù)是零知識的，就不怕買家拿了加密數(shù)據(jù)不給錢就跑路。所謂的「零知識」，大家可以這么通俗理解：買家拿到的加密數(shù)據(jù)后，就像拿到一堆隨機(jī)數(shù)一樣，沒有任何信息量。怎么做到零知識呢？PoD-Tiny 采用了經(jīng)典 Schnorr 協(xié)議的思想。

插播科普：Schnorr 協(xié)議 與 「零知識」

Schnorr 協(xié)議是非常經(jīng)典的教課書例子，我這里快速帶大家過一遍。Schnorr 協(xié)議的用途之一是用來做身份認(rèn)證，它是一個兩方安全協(xié)議，一方「證明者」Alice ，向另一方「驗證者」Bob證明她擁有一個公鑰對應(yīng)的私鑰。

首先 Alice 產(chǎn)生一對「公私鑰」，(PK, sk)。然后 Bob 持有 Alice 的公鑰 PK。當(dāng) Alice 要向 Bob 證明身份時，他們會通過一個「三步交互協(xié)議」來完成證明：證明 Alice 擁有私鑰 sk。如果 Bob 接受了這個證明，那么 Bob 會認(rèn)為 對面證明有私鑰的人就是 Alice。下面簡單描述下這個協(xié)議：

sk = a, pk = a*G

公開輸入：PK = a*G

Alice私有輸入：sk = a

第一步：Alice 選擇一個隨機(jī)數(shù) r，并且發(fā)送 r 的「承諾」R = r*G 給 Bob

第二步：Bob 發(fā)回一個隨機(jī)數(shù) c，作為挑戰(zhàn)數(shù)

第三步：Alice 計算 z = r + c * a，然后將 z 發(fā)送給 Bob，然后 Bob 通過如下的公式來驗證：

驗證公式：z*G ?= R + c*PK = r*G + c*a*G

這個 Schnorr 協(xié)議具有三個性質(zhì)：

完備性 Completeness

可靠性 Special Soundness

對誠實驗證者零知 Special Honest Verifier Zero-Knowledge

其中第三個性質(zhì)就是「零知識」，這個性質(zhì)保證了：在協(xié)議交互過程中，Bob 無論如何都不會得到關(guān)于私鑰的任何信息。

注:嚴(yán)格地講， Schnorr 協(xié)議并不是「Full-ZK」，只能保證「HVZK」，這是一個相對弱一些的零知識性質(zhì)。不過大家暫時不用糾結(jié)這一點，Schnorr 協(xié)議可以通過一些技巧升級為「Full-ZK」。

PoD-Tiny：一個簡單的 PoD 協(xié)議

如果大家已經(jīng)大概記住了 Schnorr 協(xié)議的細(xì)節(jié)，那么我來展示一個協(xié)議叫做 PoD-Tiny。

協(xié)議描述：假設(shè) Alice 擁有一個數(shù)據(jù)明文 m?，然后 Bob 擁有這個數(shù)據(jù)的 Authenticator（A），這里還有一個 「Trustless 第三方」，我們暫且叫她 Julia。請大家記?。核且粋€智能合約。

協(xié)議：

開場前的道具：m,a,G, 一個隨機(jī)數(shù)產(chǎn)生器 rand()

角色：

Alice：擁有數(shù)據(jù)? m，一次性密鑰? k <-rand()

Bob：擁有 A

Julia:? N/A

步驟：

第一步：Alice 產(chǎn)生一個隨機(jī)數(shù)，r <-rand() ，然后發(fā)給 Bob 兩個數(shù) K=k*G 和 R=r*G

第二步：Bob 產(chǎn)生一個隨機(jī)數(shù) c <-rand()，發(fā)送給 Alice

第三步：Alice 計算兩個數(shù)字 E(m) = k + m，z = r + c * k，并且發(fā)送給 Bob。這兩個數(shù)，第一個 E(m) 是用一次性密鑰 k 加密后的「數(shù)據(jù)密文」，而 z 是「密鑰的密文」。

注：什么？密鑰的密文？沒錯，這里 Alice 用第一步生成的隨機(jī)數(shù) r，加上第二步 Bob 提供的挑戰(zhàn)數(shù) c對 k 做了加密，得到了 z。

第四步：Bob 對收到的數(shù)據(jù)密文 E(m) 進(jìn)行驗證（公式(1) ），并且對密鑰的密文進(jìn)行驗證（公式(2) ）：

驗證公式(1)：E(m) * G ?= A + K

驗證公式(2)：z*G ?= R + c*K

注：在第四步中，Bob 需要搞明白兩件事：首先傳給他的密文數(shù)據(jù)（E(m)）能不能對應(yīng)到數(shù)據(jù)錨點（A）；然后密文數(shù)據(jù)（E(m)）是不是由某一個未知密鑰 X 加密的，并且這個「未知密鑰」的密文應(yīng)該等于第三步中 Alice 發(fā)過來的「密鑰密文」（z）。倘若如此，在未來的某個時刻，若 Bob 得到「密鑰密文的密鑰」（r） 之后，就可以做兩次解密動作來成功拿到數(shù)據(jù)明文（m）。兩次解密動作為：首先 Bob 用「密鑰密文的密鑰」r 還有挑戰(zhàn)數(shù) c 解密 密鑰密文 z，得到數(shù)據(jù)密鑰 k，然后再用數(shù)據(jù)密鑰來解密 數(shù)據(jù)密文 E(m)，從而得到數(shù)據(jù)明文 m。

再注：上面的協(xié)議第一步到第四步，其實大家可以發(fā)現(xiàn)和 Schnorr 協(xié)議非常類似。只不過把 a 替換成了一個一次性密鑰 k。然后另一個不同點是，K = k*G 相當(dāng)于原 Schnorr 協(xié)議中的公鑰，并不是一開始發(fā)給了Bob，而是在協(xié)議的第一步和 R 一起發(fā)送給 Bob。不管如何，從整體上，這四步協(xié)議正是一個 Schnorr 協(xié)議的擴(kuò)展。當(dāng)然到這里還沒完，接下來區(qū)塊鏈要登場了，Bob，Alice 要和 Julia 開始進(jìn)行交互。

第五步：如果 Bob 在第四步中驗證公式(1)和公式(2)通過，那么說明 Alice 發(fā)的加密數(shù)據(jù)都是正確的。這時候 Bob 要發(fā)給 Julia 一個「數(shù)據(jù)交付收據(jù)」(Delivery-Receipt)，R。Bob 在這一步需要將 「Token」一并保存給 Julia。

注：這個收據(jù)是為了告訴 Julia，Bob 他已經(jīng)收到了加過密的數(shù)據(jù)了，但是密鑰還沒收到。密鑰需要 Julia 幫他接收并驗證。那么驗證的憑據(jù)是什么呢？正是「密鑰密文的密鑰」對應(yīng)的「承諾」，是不是有點繞，這個收據(jù)就是協(xié)議第一步 Alice 發(fā)給 Bob 的 R?。

第六步：Alice 向 Julia 出示「密鑰密文的密鑰」，也就是 r。Julia 檢查下面這個關(guān)鍵公式。如果驗證通過，Julia 可以將 Bob 保存的 Token 轉(zhuǎn)給 Alice。

驗證公式(3)：R ?= r*G

我們看看關(guān)鍵問題(3)是如何解決的。

關(guān)鍵問題(3)：Alice 出示給智能合約的密鑰必須是真密鑰，否則拿不到 Token

在協(xié)議的第一步，Alice 給 Bob 發(fā)送了一個「密鑰的密鑰」的「承諾」R；然后在協(xié)議的第五步，Bob 把 R 轉(zhuǎn)交給了 Julia；第六步，Alice 兌現(xiàn)承諾，揭示對應(yīng)的 r。如果 Alice 出示一個錯誤的值，Julia 立即就會發(fā)現(xiàn)公示(3)不成立。

還有一個：

關(guān)鍵問題(4)：Alice 出示真密鑰之后，必須要能拿到 Token

在協(xié)議的第六步，Julia 要檢驗公式(3)。在 Alice 出示正確的 r 的情況下，如果等式不成立，那么只有兩種情況：（1）Julia 故意搗亂， （2）R 的值不正確。對于前一種情況，需要保證 Julia 的合約代碼確實沒有漏洞，功能正常，這個需要額外采用「形式化驗證」的方法來解決。對于后一種情況，這里需要 Alice 在第六步先檢查一下 Julia 的內(nèi)部狀態(tài)，在第五步中 Bob 提交的 R 是不是一個正確的值。這里請注意：Julia 是一個公開的智能合約，她持有的任何數(shù)據(jù)都是公開可見的，她的任何內(nèi)部狀態(tài)與計算過程都是公開可見的。

協(xié)議的安全性與公平性分析

如果我們不考慮多次交易，PoD-Tiny 是一個「公平」的交易協(xié)議。我們接下來依次分析下為何這個協(xié)議是公平的。

我們首先考慮 Alice 有哪些作弊手段：

A1. 將假的數(shù)據(jù) m' 加密后傳給 Bob

A2. 加密數(shù)據(jù)時用的密鑰 k，但是在加密密鑰的時候卻用的是另一個 k'，并且 k <> k'

A3. 向 Julia 出示一個假的密文密鑰 r'

分析：如果 Alice 采用作弊手法 A1，那么 Bob 在校驗公式(1)時能夠發(fā)現(xiàn)；如果 Alice 采用作弊手法 A2，那么 Bob可以通過計算公式(2)發(fā)現(xiàn)；如果 Alice 采用作弊手法 A3，那么 Julia 通過公式(3)能發(fā)現(xiàn)。

我們再考慮 Bob 都有哪些作弊手段：

B1. Bob 在拿到加密數(shù)據(jù) E(m) 之后，就退出協(xié)議，然后嘗試破解密文

B2. Bob 在驗證加密數(shù)據(jù)之后，向 Julia 出示一個錯誤的「交付收據(jù)」

B3. Bob 賬戶沒有足夠的 Token

分析：如果 Bob 采用作弊手段 B1，那么 Bob 是無法從加密數(shù)據(jù)中得到任何信息的，因為協(xié)議的前三步是「零知識的」（準(zhǔn)確地說：Honest Verifier Zero-Knowledge）。如果 Bob 采用手段 B2，Alice 可以在第六步檢查下 Julia 手里的「數(shù)據(jù)交付收據(jù)」R 是不是和她在第一步發(fā)給 Bob 的相同，一旦 Bob 提交錯誤的收據(jù)，Alice 可以直接退出協(xié)議，拒絕出示密鑰。同樣，如果 Bob 采用手段 B3，Alice 可以在第六步的時候檢查 Bob保存在 Julia 處的 Token 是否足夠，如果不足則直接退出協(xié)議。

最后，Julia 有沒有可能作弊呢？Julia 是智能合約，她的任何行為和內(nèi)部狀態(tài)都能被任何人讀取，那么通過 Julia 是有可能產(chǎn)生信息泄露的，從而對 Alice 或者 Bob 不利。但是請大家注意下，Julia 其實并不接觸任何和數(shù)據(jù)明文 m 相關(guān)的信息，也就從鏈上不會泄露 m 的信息。Julia 接觸到的信息只有兩個，R 和 r。

壓縮到最簡協(xié)議

我們數(shù)一數(shù)上面的協(xié)議的交互步驟總共有五步，分別是 Alice 與 Bob交互三次，Bob 與 Julia 交互一次，Alice 與 Julia 交互一次。安全協(xié)議里面有一個叫做 Fiat-Shamir Heuristic 變換的工具，它可以將 PoD-Tiny 協(xié)議中的前三次交互，直接「壓縮」成為一次交互。

我們發(fā)現(xiàn)最主要的不同點是，在壓縮后的 PoD-Tiny 中挑戰(zhàn)數(shù)不再由 Bob 產(chǎn)生，而是由 Alice 產(chǎn)生。這里大家可能會產(chǎn)生疑問，這樣做會不會對 Bob 不公平？這相當(dāng)于三步的 Schnorr 協(xié)議直接壓縮成一步就完成了。這里先下個結(jié)論：壓縮后的協(xié)議保持零知識的性質(zhì)，仍然對雙方公平。原因是，壓縮前的協(xié)議可以證明 HVZK(Honest Verifier Zero-Knowledge)；壓縮后的協(xié)議可以證明出 NIZK (Non-Interactive Zero-Knowledge)。但是安全性在壓縮前后的對比會比較 Subtle，這里不再展開。

經(jīng)過壓縮，最后這個協(xié)議變得不可思議地簡潔：

邁向?qū)嵱眯缘奶魬?zhàn)：安全與性能

最簡協(xié)議 PoD-Tiny 只是萬里長征的第一步，當(dāng)面對紛繁冗雜的現(xiàn)實世界，要將理論變成代碼時，會面臨許許多多的問題。這些問題會相互糾纏在一起，反過來又會影響著協(xié)議在理論層面的設(shè)計。

如何支持長度超過 1MB 的數(shù)據(jù)，甚至上 GB

如何有效降低鏈上驗證計算的開銷

如何支持以太坊，并免疫以太坊上的各式安全問題

如何支持?jǐn)?shù)據(jù)的復(fù)雜同態(tài)計算

在安全和性能方面，zkPoD 做了不少的工程改進(jìn)和創(chuàng)新，感興趣的朋友請關(guān)注我們的后續(xù)文章。

寫在最后

區(qū)塊鏈到底能做什么？我在最近一年里看到了許多相當(dāng)「悲觀」的論調(diào)，我想 PoD 協(xié)議應(yīng)該會給這些懷疑論者帶來些許啟發(fā)。區(qū)塊鏈在 PoD 協(xié)議中起到了一個「Trustless 第三方」的關(guān)鍵角色，并且讓這個協(xié)議變得不可思議的簡潔，這是我們始料未及。

參考文獻(xiàn)

[1] Maxwell, G. "Zero knowledge contingent payment. 2011." URl: https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment (visited on 05/01/2016) (2016).

[2] Greg Maxwell. “The first successful Zero-Knowledge Contingent Payment.”https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/