深入理解Zcash的零知識證明體系

買賣虛擬貨幣
前言主要分享Zcash Sapling版本的協議細節。多多指教!!!Zcash迄今為止,Zcash總共經歷了三個版本的迭代,第四次版本升級時間預計在12.11.2019,據官方介紹,此次更新主要是縮短了出塊的時間。作為零知識證明的成功應用專案,讓我們帶著以下幾個問題去研究Zcash的機制:Zcash是如何隱藏傳送方的?
Zcash是如何隱藏接收方的?Zcash是如何隱藏交易金額的?建議:閱讀本文前,您最好已經瞭解了:1. note的概念;2. 零知識證明的基本概念;Sapling本篇主要分享Zcash Sapling版本協議的主要細節,相對於Sprout版本,還是做了很多的修改和最佳化,在此不做詳細的對比分析。迴歸到大方向,無論是Sapling版本,還是Sprout版本,交易的整體流程都可以簡要概括為以下三個步驟:
1. 交易者發起交易; 2. 交易者生成zk-proof,和signature,驗證者驗證;3. 接收者接收交易;接下來,我們將盡量仔細挖掘每一個步驟,去探索一下,它是如何實現這三點的。Transaction

在這裡,我們不詳細介紹交易發起者是如何發起一起交易的,我們直接介紹Sapling中的交易結構,如圖所示:

實際上,Sapling的交易結構內容不止這些,在這只是羅列出Sapling特有的一些欄位及相應的解釋,完整的交易結構在協議說明書的7.1章節有詳細介紹。

在Sapling中,交易由Spend Transfer和Output Transfer組成,分別對應隱匿的輸入和隱匿的輸出,而spendDescription和output Description是用來分別描述Spend Transfer和Output Transfer的資料欄位,它們被各自編碼表示成vShieldSpend和vShieldOutput欄位儲存在交易結構中。

接下來,重點介紹vShieldSpend、vShieldOutput、valueBlance、bindingSig四個欄位表示的內容。

1. vShieldSpend

一個vShiledSpend對應著一個SpendDescription,一個可靠的SpendDescription表示一個note的有效花費,它包含的內容如下圖所示:

cv:對Inpunote 的value的承諾,所謂承諾,其實就是對v值的一種隱藏,這種隱藏是單向的,不可逆的,也不可偽造;anchor:cm默克爾樹的根,用於驗證inputnote的存在性及有效性;nullifier:note的唯一性標識,用來防止同一note被重複花費; rk:用於驗證消費授權簽名;zkproof:零知識證據,在不透露相應隱私的情況下,證明note的有效性、花費note的權力、隱私地址的有效性 spendAuthSig:用私鑰對spendDescription簽名,對note的花費進行授權

2. vShieldOutput

同理,一個vShiledOutput對應一個OutputDescription,一個可靠的OutputDescription表示產生的新note的有效性,它包含的內容如下圖所示:

  cv:對outputnote 的 value的承諾,亦滿足單向性,不可偽造性;cmu:對outputnote的承諾,承諾的數學形式是曲線上的一個點(u,v),cmu為點的u座標;ephemeralKey:臨時公鑰,用於計算解密金鑰 encCiphertext:noteplaint的密文,noteplaint是note的具體內容;outCiphertext:用來計算共享金鑰的資訊密文,可用來恢復noteplaint資訊 zkproof:零知識證據,在不透露任何隱私的情況下,證明新生成Note的有效性

   3. valueBlance

valueBalance表示此transparent value pool的變化量,由Spend Transfer的v總和減去Output Transferd的v的總和得出。當valueBalance 為正數時,表示從Sapling value pool轉移valueBalance至transparent value pool,如果為負數,則執行相反的操作。valueBalance將在bindingSig中,用於驗證交易的balance 屬性。

  4. bindingSig在Sapling中,bingingSig發揮兩個作用。第一,保證了交易的balance屬性;第二,利用計算輸入和輸出note cv的隨機數rcv,來生成簽名私鑰,防止outputDescription被攻擊者進行重放攻擊(spendDescription的防重放攻擊由spendAuthSig來保證)

Zk-proof and Signature

在Sapling中,交易者總共要生成兩個zkproof(spend zkproof & output zkproof)和兩個簽名(spendAuthSig & bindingSig)。下面逐個介紹。

 1. spend zk-proof

spend zkproof 主要是實現了在不暴露任何隱私資訊的場景下,去證明txsender有權力去花費一些note,並且這些note都是有效的。輸入分為兩個部分,一個是primary input, 一個是Auxiliary input。primary input是公開的輸入資訊,Auxiliary input是隱私的輸入資訊,只有txsender知道。具體內容如下圖所示:

根據上圖可知,spend zkproof總共證明了以下幾點:Note commitment integrity:inputnode的承諾的完整性,證明cm確實根據v,rcm,gd,pkd計算出來的;Merkle path validity:默克爾樹驗證路徑有效性,證明cm是存在默克爾樹上的,是一個有效的cm;Value commitment integruty:inputnote v的承諾完整性,證明cv確實根據rcv,v計算出來的;Small order checks:證明私有引數,gd和ak是合法的;Nullifier integrity:Note的唯一標識,證明nf確實根據nsk,cm,pos計算出來的;Spend authority:Note的花費權力,證明擁有花費note所需的私有引數;Diversified address integrity:一次性地址的計算完整性。若以上等式均能滿足,則說明txsender有權力花費對應的Note,因為等式4,6,7成立;其花費的note是有效性,因1,2,3,5成立。

2. output zkproof

output zkproof 主要是實現了在不暴露任何隱私資訊的情況下,去使得validator相信txsender所產生的新note是有效的。輸入仍分為兩個部分,一個是primary input, 一個是Auxiliary input。primary input是公開的輸入資訊,Auxiliary input是隱私的輸入資訊,只有txsender知道。具體內容如下圖所示:

根據上圖可以看出,output zkproof總共證明了一下幾點: Note commitment integrity:outputnode的承諾的完整性,證明cm確實根據v,rcm,gd,pkd計算出來的;Value commitment integruty:inputnote v的承諾完整性,證明cv確實根據rcv,v計算出來的;Small order checks:證明私有引數,gd是合法的;Ephemeral public key integrity:臨時公鑰的計算完整性。若以上等式均滿足,則說txsender產生的新note是有效的,因為等式1,2,3均成立;等式4成立則可以保證txreceiver可以根據自己的ivk金鑰和epk去解析加密後的np,並儲存到本地的集合當中。

  3. spendAuthSig

關於spendAuthSig 的意義,可在兩種場景下,進行描述。第一:txsender自己產生zkproof,然後對spendDescription進行簽名。這時,如果存在一個攻擊者,想對spendDescription進行重放攻擊,則其需要重新簽名,則rk會被替換,那麼驗證者在驗證spend zkproof時,就會驗證失敗;如果攻擊者不替換rk,那麼spendAuthSig的驗籤就會失敗,因此spendAuthSig的存在,有效規避spendDescription的重放攻擊;第二:txsender呼叫第三方產生zkproof,然後自己對spendDescription進行簽名,這是Sapling版本允許的,為了讓記憶體和計算能力受限的一些錢包也能支援隱私交易,即使這樣損失了隱私性,因為需要把auxiliary input全部傳送給第三方。因此,在這種情況下,為了不讓第三方惡意產生有效的zkproof,txsender需要對spendDescription進行簽名,需要注意的是,txsender簽名用的是ask,zkproof中spend Authority的證明用的是ak(ak可由ask計算得出),因此第三方無法產生有效的簽名,有效規避spendDescription的重放攻擊。spendAuthSig的簽名流程如下圖所示:

  4. bindingSig

如前面所說,bindingSig主要實現了兩個功能。第一:在不暴露spend Transfer 和 output Transfer的v值的情況下,保證了transaction balance;第二:防止了outputDescription被攻擊者重放,主要是利用spendDescription 和 outputDescription對應的用於計算cv的隨機數rcv來產生簽名私鑰bsk,這使得攻擊者無法作惡,因此簽名驗證公鑰是利用spendDescription 和 outputDescription對應的cv來生成的,攻擊者無法改變cv,否則zkproof會驗證失敗。bindingSig的簽名驗籤流程如下圖所示:

Receive Transation

txReceiver接收交易的一般步驟為:接收者遍歷每筆交易的outputDes,用自己的ivk和outputDes裡的epk嘗試解密每一個Cenc ,如果返回成功,則將接收到的note新增至本地的receiveSets。那麼什麼是Cenc呢?用ivk和epk如何去解密Cenc?

  1. 什麼是Cenc?

Cenc是encCiphertext,是noteplaint經過對稱金鑰加密後的密文資訊,noteplaint是指交易新生成的note的內容,這些內容都是私密的。np的組成及Cenc的加密過程如下圖所示:

相關欄位解釋如下 DiverfiedHash:一次性引數生成器,輸入d,輸出gd,每次呼叫都不一樣;esk、epk:一次性私鑰、公鑰,滿足epk = esk * gd;pkd:一次性傳輸地址;np:noteplaint{memo、rcm、v、d} => note資訊{特殊欄位,由交易傳送者和接收者協商一致使用、生成cm的隨機數、note的面額、 diversifier};KA.DerivePublic:計算公鑰;KA.Agree:計算共享金鑰;KDF:金鑰獲取函式,得到最終的加密金鑰Kenc;Sym.Encrypt:一次性對稱加密函式;其中Kenc為一次性對稱加密金鑰,Penc為編碼後的Cenc。從交易結構裡可以看出,Kenc並沒有直接的當作明文進行傳輸,那麼,交易接收者是如何獲取Kenc,對Cenc進行加密的呢?

2. 用ivk和epk如何去解密Cenc?

首先,讓我們關注兩個等式:pkd = ivk * gd esk * gd = epk 在加密的過程中,KA.Agree的輸入引數為pkd和esk,由pkd * esk = ivk * gd * esk = ivk * epk,因此在解密的過程中,如果能輸入ivk和epk,那麼由KA.Agree(pkd,esk) == KA.Agree(ivk,epk)。理解了這一點,下面具體看一下Cenc的解密過程,如下圖所示:

相關欄位解釋如下:

NoteCommit:cm計算函式,原始輸入為np的資料;cm:note的承諾;Extractor:抽取器,返回cm的u座標,cm形式(u,v);若返回的cmu與outputDes裡的一致,則說明證明者有計算cm的私有資料;

總結

1. Sapling中spendDescrption部分關於spendAuthSig的理解。

a. 目的:證明某個人對於inputnote具有花費的權力,即擁有spendKey
b. 疑問:在spendDes的zkproof中,證明花費權力如下:

spend authority: rk = spendAuthSig.RandomizePublic(a,ak) (1)

由於a、ak都是Auxiliary input,是私有資料。且ak = spendAuthSig.DerivePublic(ask) (2),ask也是私有資料,因此若公式(1)成立,意味著此人有相應花費權力。那spendAuthSig存在的意義是啥?

c. 解答:在sapling版本,考慮到一些計算能力和記憶體空間受限的錢包,不具備生成proof的能力,因此可能需要第三方代理生成,此時,需要把ak、nsk等生成證明需要的私有資料公開給第三方,這樣就會損失隱私性,在這種情況下,為了保證第三方不能隨意生成一個有效的zkproof,交易發起者需要對整個spendDes用私鑰進行簽名。一個需要注意的點是:生成zkproof需要ak,不需要ask,ask是在簽名時使用。因此第三方無法生成一個有效的簽名。

2. 為何由sprout的joinsplit transfer 演變成sapling的spend transfer & output transfer。

a. 生成proof的大小變小了,joinsplit[1698bytes] > spend[384bytes] + output[948bytes]
b. balance證明不在zkproof中實現,減少了電路的複雜性,可改善生成和驗證效能

3. spend 和output proof 均為驗證balance屬性,怎麼保證整體value平衡。

使用了 pederson value commitment方法,它具有同態加法屬性,即在不暴露v值的情況下,驗證:  ∑vold - ∑vold = vbalance

 4. Sapling接收者如何接收note。

接收者遍歷每筆交易的outputDes,用ivk和outputDes裡的epk嘗試解密每一個Cenc ,如果成功,則計算note並新增至receiveSets

5. BindingSig。

關於這個簽名的實現,您可參考協議說明文件4.12章節,金鑰對不是重新生成的,而是基於cv和rcv的生成關係,實現簽名驗簽過程

6. 如何隱藏交易傳送者?

每筆交易的驗證公鑰都是一次性臨時公鑰,因此礦工不知道交易發起者。

7. 如何隱藏交易接收者?

交易結構中不存在交易接收者的地址資訊,用交易接收者的隱私地址去生成對稱金鑰,生成Cenc ,交易接收者用問題4的方法接收交易。且同一交易接收者暴露給不同交易發起者的地址是不同的,為了防止交易發起者之間串通作惡。

8. 如何隱藏v值?

利用pederson value commitment進行同態隱藏。

以上是個人理解,如果錯誤,還希望各位讀者批評指正。

附錄
ZCASH 官方協議說明書 https://github.com/zcash/zips/blob/master/protocol/protocol.pdf

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;