子彈證明：一種區(qū)塊鏈中的隱私保護技術(shù)

夏伏彪　高慶忠　劉軍　林錦達

摘? ?要：區(qū)塊鏈的隱私保護技術(shù)自2008年比特幣問世以來就成為研究熱點之一。加密貨幣如門羅幣（Monero）、大零幣（ZCash）、達世幣（Dash）等都是成功應(yīng)用各類隱私保護技術(shù)的明星貨幣，而在諸多的隱私保護技術(shù)之中，零知識證明技術(shù)能實現(xiàn)最好的匿名性，因此也成為隱私保護研究領(lǐng)域的焦點技術(shù)之一。論文對最新的子彈證明技術(shù)進行系統(tǒng)性和原理性的闡述分析，并與Zk-snarks和Zk-starks兩類前沿零知識證明技術(shù)進行對比。最后，對區(qū)塊鏈中的零知識證明技術(shù)的發(fā)展方向進行展望。

關(guān)鍵詞：隱私保護;零知識證明;機密交易;子彈證明;范圍證明

中圖分類號：TP309.7? ? ? ? ? 文獻標(biāo)識碼：A

Abstract： The privacy-preserving technologies on blockchains have been well studied since the invention of Bitcoin in 2008. Monero， Z-cash， Dash are the well-known crypto-currencies for their advanced privacy-preserving technologies. Zero-knowledge proof which provides the best anonymity， is the hot-spot of the block chain privacy and security. This survey paper focuses on the introduction of the cutting-edge technique， i.e.， the bullet proofs with its underlying principles. We also make some remarks on the bullet-proofs， with the other two similar zero-knowledge proofs， Zk-snarks and Zk-stark. And we make the conclusion for the envision of the zero-knowledge proofs in the blockchain industry.

Key words： privacy-preserving; zero-knowledge proofs; confidential transactions; bullet proofs; range proofs

1 引言

區(qū)塊鏈技術(shù)作為一種新興的技術(shù)應(yīng)用模式，主要解決了網(wǎng)絡(luò)空間里交易的信任和安全問題。其核心思想是區(qū)塊鏈里的每一個節(jié)點都按照塊鏈式結(jié)構(gòu)存儲全局完整的賬本數(shù)據(jù)，通過共識機制保證交易的有效性以及各節(jié)點存儲的一致性。自從2008年比特幣問世以來，其背后的核心區(qū)塊鏈技術(shù)就持續(xù)蓬勃發(fā)展，從共識機制、點到點分布式網(wǎng)、智能合約，到上層的激勵模型等多個方向都在不斷衍變。經(jīng)過十多年的發(fā)展，區(qū)塊鏈技術(shù)已經(jīng)在加密貨幣領(lǐng)域證明了其可靠性和安全性。

2? 背景

區(qū)塊鏈中的隱私保護問題，例如加密貨幣里的匿名交易、智能合約的隱私、區(qū)塊鏈隱私保護基礎(chǔ)設(shè)施等都是長期的研究熱點。按隱私保護技術(shù)分類，零知識證明、安全多方計算、同態(tài)加密、環(huán)簽名、代理重加密等，都是依靠密碼學(xué)技術(shù)來實現(xiàn)對數(shù)據(jù)隱私的保護。而其中，零知識證明作為能實現(xiàn)最強匿名性的隱私保護技術(shù)，一直受到各區(qū)塊鏈項目的重點研究和探索。

從應(yīng)用的角度來看，區(qū)塊鏈技術(shù)的各大應(yīng)用場景，例如加密貨幣、電子存證、身份識別、金融數(shù)據(jù)結(jié)算等對隱私保護的要求也越來越高。其中，加密貨幣是目前為止區(qū)塊鏈技術(shù)最為成功的應(yīng)用，誕生了諸如門羅幣（Monero）、大零幣（ZCash）、達世幣（Dash）等非常優(yōu)秀的隱私貨幣。零知識證明，作為能實現(xiàn)最強匿名性的隱私保護技術(shù)，一直受到這些加密貨幣項目的重點研究和探索。

零知識證明[1]是由S.Goldwasser、S.Micali和C.Rackoff在20世紀80年代初提出的。它是一種證明者能使驗證者相信某個論斷是正確的，同時這個證明過程不泄露任何有用的信息。零知識證明屬于交互式證明系統(tǒng)，除了傳統(tǒng)的完備性和可靠性必須滿足之外，其特有的零知識性保證了驗證者在被證明過程中無法獲得證明者擁有的秘密或者任何有助于獲得該秘密的其他信息。長期以來，零知識證明作為一種強安全的隱私保護技術(shù)，在理論上獲得了長足的研究和發(fā)展，但是其性能參數(shù)包括需要非常多的交互證明輪數(shù)、證明的數(shù)據(jù)長度、生成時間和驗證時間，常常是制約該技術(shù)獲得實際應(yīng)用的瓶頸。

3 機密交易和范圍證明

加密貨幣交易中的隱私性通常可以分為兩類：一是匿名性，即交易雙方的身份可以被隱藏起來;二是機密性，即該筆交易的交易金額是不可見的。早期的加密貨幣項目例如比特幣，其交易由于沒有把收款人和付款人的比特幣地址與他們各自在真實世界中的身份信息進行關(guān)聯(lián)，保證了一定程度的“弱匿名性”。因此，如何保證交易金額的機密性就成為了制約比特幣和其他加密貨幣，以及各類區(qū)塊鏈項目發(fā)展的一大限制。

3.1 機密交易

Maxwell在2016年[2]提出了“機密交易”（Confidential Transactions）的概念。注意，比特幣等加密貨幣的交易形式稱為未花費的交易輸出（Unspent Transaction Outputs，UTXO），即當(dāng)前這筆交易的其中一個輸入使用的是之前某一筆交易的未使用過的一個輸出，并且需要附加當(dāng)前交易輸入地址對應(yīng)的數(shù)字簽名。因此，UTXO模式的交易驗證的主要思想是：驗證當(dāng)前交易的每一個輸入都是屬于UTXO，并且所有的輸入總和大于所有的輸出總和。機密交易的思想就是交易金額，即 UTXO形式交易中的各個輸入和輸出，用承諾算法隱藏起來;同時，為了支持公開可驗證性（否則失去了區(qū)塊鏈的透明和可審計的意義），機密交易還會包含一段零知識證明，用來證明交易的輸入總和大于輸出總和，并且所有的輸出都是正值。

在機密交易中，交易金額通常用Pedersen承諾算法[3]隱藏起來。該承諾算法主要是承諾者先向接收者承諾某個秘密數(shù)，即生成某個承諾值，在后面的階段通過展示該秘密數(shù)，由接收者確認前后承諾值是否相等。注意，承諾算法的兩個要求：一是隱藏性（Hiding Property），即承諾值不能泄露任何關(guān)于秘密數(shù)的信息;二是綁定性（Binding Property），即承諾者給出承諾值后，無法更換承諾中的秘密數(shù)，使得在后面的階段用新的秘密數(shù)生成相同的承諾值，從而欺騙接收者。

基于橢圓曲線的Pedersen承諾算法主要形式如下：

Com（v）=v·B+·這里B和分別是作為公開參數(shù)的生成元，為橢圓曲線上的兩個基點，v是需要承諾的秘密數(shù)，是一個盲化因子， 用來保證語義安全性。

Pedersen承諾方案不但滿足承諾方案的兩個傳統(tǒng)的安全要求，完美的隱藏性（Perfect Hiding Property），和計算綁定性（Computationally Binding Property），而且具備非常好的同態(tài)加密性（Homomorphic Encryption），即：

Pedersen承諾方案的同態(tài)加密性，保證了UTXO交易中多個輸入和多個輸出的總和均是Pedersen承諾，即交易金額數(shù)可隱藏。

3.2 范圍證明

為了“零知識”地證明機密交易中的輸入和大于輸出和，需要依賴一種稱之為“范圍證明”[4]的技術(shù)。范圍證明主要是證明經(jīng)過加密或者承諾等隱藏處理之后的某個秘密數(shù)，其取值在某一個特定區(qū)間內(nèi)。

大多數(shù)的范圍證明方案看上去非常適合成為機密交易的一個組成部分，但是它的主要缺點在于需要一個可信任的初始化階段，以及時間和空間上帶來的巨大性能開銷。依賴初始化階段的可信環(huán)境，會給該區(qū)塊鏈的透明性帶來質(zhì)疑。采用了范圍證明的機密交易開始，會變得非常大而且驗證緩慢，其中的一個范圍證明大小約為幾千個字節(jié)，且需要幾個毫秒才能驗證。而傳統(tǒng)的UTXO交易里的數(shù)字簽名小于100個字節(jié)，且驗證時間不超過100微秒。因此如果能解決這兩個問題，那么機密交易看起來就能真正成為可能。

4? 子彈證明原理

子彈證明是2017年由Bunz等人[5]提出的一種非交互式零知識證明，用于解決機密交易中證明技術(shù)的可信啟動問題和性能問題。相比于文獻[5]，用加法群代替了原先的乘法群符號系統(tǒng)，同時將原文獻的證明推導(dǎo)過程以更詳細的公式和文字進行表述。

4.1 符號系統(tǒng)

用如下的符號定義系統(tǒng)。小寫字母a、b、c表示Zp里的標(biāo)量，大寫字母G、H、P、Q表示群G里的元素。向量被記為粗體，例如a和G。而兩個向量的內(nèi)積記為<-，->。請注意內(nèi)積∈Zp輸出的是一個標(biāo)量，而內(nèi)積∈G是一個多標(biāo)量的乘法。 全0和全1的向量記為0，1。對一個標(biāo)量y，用

表示相關(guān)的一個向量，且第i個元素是yi。對于具有偶數(shù)長度2k的向量v，定義分布為該向量的低半段和高半段：

Pedersen承諾方案被記為：

并且B和是這里被使用到的生成元和“盲化”因子（Blinding Factors），將v的盲化因子記為，使得變量和它的盲化因子之間可以清晰地關(guān)聯(lián)起來。為方便起見，用Com（v）符號代替Com（v·）。

同時，也用到了Pedersen向量承諾方案，定義為：

且G和H都是生成元組成的向量。

顧名思義，范圍證明是“零知識地”去證明一個數(shù)值在某一個區(qū)間范圍內(nèi)。證明者將要證明的值v，先進行承諾V=Com（v）發(fā)送V給驗證者。證明者希望在接下來的過程里能證明v∈[0，2n），同時不泄露v的具體的值。假設(shè)a是v的各個比特位組成的向量，例如n=3，v=7，a就是<1，1，1>;n=4，v=10，a就是<0，1，0，1>。v可以被表示成一個內(nèi)積，即：

必須保證a是一個只包含{0，1}的向量。這也可以用另一種形式來表示：

且x○y記為兩個向量之間的元素積。

因此二進制表示v時，v∈[0，2n）等價于以下兩個等式：

更進一步，其實關(guān)注的是向量a和a-1， 因此記aL=a，aR=a-1從而獲得

4.2 合并多向量陳述證明

接下來需要對這三個等式進一步處理，使之合并轉(zhuǎn)化為一個式子（statement），方便證明。因為b=0當(dāng)且僅當(dāng)=0對于任意的y。因此上述三個等式可以轉(zhuǎn)化為

對于驗證者選擇任意的y都成立。

更進一步地，對于驗證者任意選擇的y，都可以有：

4.3 合并內(nèi)積

需要再將上面等式里的這些項進一步處理，轉(zhuǎn)化成一個內(nèi)積的形式，且轉(zhuǎn)化后的內(nèi)積<-，->里，aL只出現(xiàn)在左邊，aR只出現(xiàn)在右邊，且將不包含秘密數(shù)的那些項合并起來記為一個新變量δ。

將這個陳述拆開，再重新排列之后，兩邊同時加上<-z1，z22n+zyn>之后再約簡。將所有的非秘密項整理到內(nèi)積之外，記為：

最后獲得了等式：

將內(nèi)積地左邊部分記為“unblinded l（x）”，右邊部分記為“unblinded r（x）”，因此有：

4.4 內(nèi)積盲化

證明者不能簡單地將“unblinded l（x）”和“unblinded r（x）”直接發(fā)送給驗證者，這樣將會導(dǎo)致證明過程不是“零知識化”。因此，聰明的證明者會隨機地選取這兩個向量的盲化因子：

sl，sr←Zpn并且用他們來構(gòu)造盲化后的多項式：

l（x）和r（x）將項al，ar盲化，用項aL+sLx，aR+sRx代替。其中，l0和r0項表示多項式里度數(shù)為0的項（關(guān)于x），類似的l1和r1表示多項式里度數(shù)為1的項。

很顯然，有：

然后記：

將系數(shù)t（x）用 Karatsuba方法展開：

因為：

證明者希望對驗證者證明上面那個未盲化的內(nèi)積等式成立，實質(zhì)上等價于證明：1. t（x）的常數(shù)項t0等于z2v+δ（y，z）， 并且 2. t（x）是正確的多項式。證明t（x）是正確的多項式，等價于證明l（x），? ?r（x）均是正確的，并且t（x）=。

4.5 證明t0的正確性

證明者首先制作一個關(guān)于t（x）的系數(shù)的承諾，然后將通過準確回答驗證者給出的任意挑戰(zhàn)值，來向驗證者證明“這些承諾是對t（x）的正確承諾”。 證明者已經(jīng)用V=com（v）來承諾了v（本質(zhì)是承諾了t0），因此證明者再計算兩個承諾：T1=com（t1） 和T2=com（t2），并且把這些承諾發(fā)送給了驗證者。注意到，這些承諾互相之間且與均形成了一些關(guān)系，即我們有如下的式子：

請注意每個列的和是一個對該列第一行里的變量承諾，且該承諾用了該列第二行里的變量作為盲化因子。而所有列的和就是， 即對 在取值時進行承諾， 且用了正交盲化因子：

為了向驗證者證明，證明者將向驗證者發(fā)送，后者根據(jù)以下式子檢查一致性：

4.6 證明的正確性

希望將和與，和這一組變量進行關(guān)聯(lián)。因為有：

需要找到關(guān)于和這兩個復(fù)合變量的承諾。但是知道證明者必須在驗證者給出挑戰(zhàn)值y之前計算出承諾，因此證明者只具備對和計算對應(yīng)的承諾值的能力。驗證者需要將證明者的承諾變形成 （對也要進行類似的變形）。 注意到：

因此記， 則關(guān)于的承諾被變形為關(guān)于的承諾。

為了將證明者的承諾和承諾關(guān)聯(lián)到和，用到如下式子：

其中。

與前面那個和式對列與行的分析類似，不難發(fā)現(xiàn)，上面式子里的每一列都是一個Pedersen向量承諾，且第三行里的元素均是相應(yīng)的盲化因子。所有列的和，也是一個Pedersen向量承諾，其正交盲化因子是。為了向驗證者證明，證明者需要將發(fā)送給驗證者，后者計算以下的式子：

如果證明者是誠實的，則，因此驗證者用作為內(nèi)積協(xié)議的輸入來證明。

4.7 內(nèi)積協(xié)議

首先，一個直接的辦法是證明者將向量and直接發(fā)送給驗證者，后者可以根據(jù)以下式子直接計算內(nèi)積和承諾是否是正確的。

盡管這樣做不會造成信息泄露，即證明過程確實是零知識化，但是需要在證明者和驗證者之間傳遞個標(biāo)量。為了節(jié)省帶寬，給出內(nèi)積論證協(xié)議（inner-product argument protocol），可以進行間接地證明，并且通信開銷減低到。

接下來需要修改一下符號定義系統(tǒng)，使得這部分將要闡述的內(nèi)積協(xié)議的定義不會與前文的范圍證明的定義沖突：

根據(jù)這套新的定義，需要進行以下這一個知識證明：

引入一個中間變量，再對第二個等式兩側(cè)同時乘以一個正交生成元，將這兩個等式合并為一個等式，即：

繼續(xù)引入以下符號對上面地等式簡化：

將獲得：

上面這個合并后的等式非常關(guān)鍵，因為它可以對等式里的各個向量進行持續(xù)地“對半壓縮”并且壓縮后獲得的新等式仍然保持相同的結(jié)構(gòu)。通過壓縮次，會獲得一個最終等式只有2個向量且每個向量的長度只包含有一個元素，這樣最后的校驗就變得非常簡單。需要強調(diào)的是，這里如果證明了對于所有的，都有上述等式里的組成結(jié)構(gòu)，那么上面的和也一定會符合等式。在UTXO模型里，只要證明交易的輸入大于輸出，這筆交易就可以被認為是有效的。也就是輸出在0和輸入之間。接下來介紹一下具體壓縮的過程。引入一個中間變量，并且對原始的進行如下變換：

令，并且采用與類似的結(jié)構(gòu)，但是用的是壓縮后的向量來定義：

將它展開得到：

然后我們將這個等式進一步表示成如下這個等式：

如果證明者確實是誠實地在隨機選擇之前對和進行了承諾計算，并且上面這個等式成立，則原始的等式（關(guān)于的那個等式）是極大概率成立。接下來可以繼續(xù)對壓縮，與上面過程類似地引入中間變量，...，一直到到達最后的我們有：

將上面的等式按照定義和，進行重寫后發(fā)現(xiàn)：

到這一步，證明者可以簡單地發(fā)送2個標(biāo)量和給驗證者，這樣后者可以直接校驗上面這個最終步的等式是否成立?？傮w的內(nèi)積協(xié)議有步，并且每一步都需要證明者將發(fā)送給驗證者，。至此，對于證明，的正確性，一共需要發(fā)送個元素。

至此，闡述了一個交互式地給出高效的范圍證明。通過采用Fiat-Shamir技術(shù)[6]將上述證明過程轉(zhuǎn)化為非交互式，就能獲得真正意義上的一個子彈證明。事實上，子彈證明的另外一大優(yōu)點是在整合處理的高效性。將多個機密交易的子彈證明整合/合并為一個子彈證明，增加的字節(jié)數(shù)非常的少（僅以對數(shù)級增長）。

4.8 子彈證明，Zk-snarks和Zk-starks

除了Bulletproofs之外，Zk-snarks和Zk-starks也是非常適合隱藏交易細節(jié)的零知識證明技術(shù)。

Zk-snarks技術(shù)[7]允許將任何復(fù)雜的驗證問題轉(zhuǎn)化為一個多項式驗證問題，再利用橢圓曲線上的指數(shù)知識困難假設(shè)[8]和同態(tài)隱藏手段，以及Fait-Shamir轉(zhuǎn)換技術(shù)，獲得最終形式的一種簡潔且非交互式的零知識證明。Zk-snarks目前主要應(yīng)用于大零幣（Zcash）的隱私交易里。但是，Zk-snarks的主要缺點在于它的安全性完全依賴于一個可信啟動（Trusted Setup），即證明系統(tǒng)的內(nèi)建隨機參數(shù)初始化必須保證不能被任何人掌握，需要通過一些特殊的密碼學(xué)技術(shù)如（Shamir秘密分割[9]）來達成。

Zk-starks[10]是Zk-snarks的“變種”技術(shù)，主要解決了Zk-snarks的可信啟動問題，同時引入了更加簡單的密碼學(xué)困難假設(shè)，能抵抗量子攻擊。但產(chǎn)生的問題是，一個Zk-snarks證明的大小將達到幾百千字節(jié)（KB），這讓Zk-starks的實際應(yīng)用再次受限。

雖然不能簡單地總結(jié)這三種引領(lǐng)加密貨幣隱私防護的零知識證明技術(shù)，孰優(yōu)孰劣，甚至在具體的性能方面，也很難簡單地給出比較。但是，可以確定的是，子彈證明技術(shù)不依賴可信啟動，比Zk-snarks和Zk-starks有相對更短的證明長度，以及支持快速批處理的優(yōu)勢，將會在很多區(qū)塊鏈領(lǐng)域特定的隱私保護場景里找到一席之地。

5 結(jié)束語

隨著隱私貨幣門羅幣（Monero）開始采用子彈證明作為其最新的匿名交易技術(shù)，門羅幣的環(huán)加密交易（一種以環(huán)簽名的形式保護交易匿名性的技術(shù)）效率明顯地提高，且交易大小的增長由原先的線性變?yōu)閷?shù)性，提高了隱私性以及可擴展性。而Zk-snarks已經(jīng)是隱私貨幣大零幣（ZCash）最重要的隱私保護手段之一，此外該貨幣也在考慮采用Zk-starks證明技術(shù)。可以看到這些優(yōu)秀的零知識證明技術(shù)在加密貨幣領(lǐng)域已經(jīng)得到了實踐性的應(yīng)用和發(fā)展。在未來，不僅限于子彈證明，各類零知識證明技術(shù)將會更加廣泛和可靠地為公有鏈、聯(lián)盟鏈的應(yīng)用場景提供隱私保護。

參考文獻

[1] Goldwasser S， Micali S， Rackoff C. "The knowledge complexity of interactive proof systems[J]， SIAM Journal on Computing， Philadelphia： Society for Industrial and Applied Mathematics， 18 （1）： 186–208， doi：10.1137/0218012， ISSN 1095-7111.

[2] Maxwell， G. Confidential transactions. https：//people.xiph.org/～greg/ confidential_values.txt， 2016.

[3] Pedersen TP. Non-interactive and information-theoretic secure verifiable secret sharing[M]. Advances in Cryptology CRYPTO '91 Springer 1991.

[4] Bootle J，? Cerulli A， Chaidos P， Groth J， Petit C. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C].? In Annual International Conference on the Theory and Applications of Cryptographic Techniques， pages 327–357. Springer， 2016.

[5] Bunz B， Bootle J， Boneh D， Poelstra A， Wuille P， Maxwel l G. Bulletproofs： short proofs for confidential transactions and more[C]. IEEE Symposium on Security and Privacy， 2018， pp.315-334.

[6] Fiat A， Shamir A. How to prove yourself： practical solutions to identification and signature problems[J]. CRYPTO 1986： pp. 186-194.

[7] Ben-Sasson E， Chiesa A， Tromer E， Virza M. Succinct non-interactive zero knowledge for a von Neumann architecture[C]. Proceedings of the 23rd USENIX conference on Security Symposium. Pages 781-796.

[8] Bellare M， Palacio A. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols[J]. Cryptology eprint archive. https：//eprint.iacr.org/2004/008.pdf.

[9] Shamir Adi. How to share a secret[J]. Communications of the ACM. 1979. 22 （11）： 612–613.

[10] Ben-Sasson E， Bentov I， Horesh Y， Riabze M. Scalable， transparent， and post-quantum secure computational integrity[J]. Cryptology eprint archive. https：//eprint.iacr.org/2018/046.pdf.

作者簡介：

夏伏彪（1985-），男，漢族，浙江寧波人，英國伯明翰大學(xué)，博士;主要研究方向和關(guān)注領(lǐng)域：應(yīng)用密碼學(xué)、區(qū)塊鏈技術(shù)。

高慶忠（1974-），男，漢族，福建漳州人，上海交通大學(xué)，碩士;主要研究方向和關(guān)注領(lǐng)域：區(qū)塊鏈和人工智能技術(shù)。

劉軍（1981-），男，漢族，江西吉安人，上海交通大學(xué)，碩士;主要研究方向和關(guān)注領(lǐng)域：區(qū)塊鏈、人工智能和大數(shù)據(jù)分析。

林錦達（1985-），男，漢族，福建漳州人，中國科學(xué)院大學(xué)，博士;主要研究方向和關(guān)注領(lǐng)域：人工智能、數(shù)據(jù)分析、區(qū)塊鏈技術(shù)。