一種高效的范圍證明方案*

張 凡,高 勝,2,曾志強,劉 喆

1.興唐通信科技有限公司,北京100191

2.數(shù)據(jù)通信科學(xué)技術(shù)研究所,北京100191

3.信息保障技術(shù)重點實驗室,北京100072

4.北京理工大學(xué)信息和電子學(xué)院,北京100081

1 引言

2008年,化名Satoshi Nakamoto(中本聰)的學(xué)者在網(wǎng)絡(luò)上發(fā)表了一篇題為《比特幣:一種點對點的電子現(xiàn)金系統(tǒng)》的文章,于是比特幣[1]進入人們的視野.歷經(jīng)十余年的發(fā)展,各種數(shù)字貨幣紛紛出現(xiàn),例如門羅幣[2,3]、零幣[4]、萊特幣[5]等.比特幣具有去中心化,分布式記賬以及用戶身份匿名等優(yōu)點.然而值得詬病的是,交易金額是明文傳輸?shù)?這嚴重限制了比特幣的廣泛應(yīng)用.隨后諸如門羅幣和零幣等數(shù)字貨幣采用各種密碼技術(shù)(比如環(huán)簽名[6]等特殊數(shù)字簽名、承諾[7]、零知識證明[8]、同態(tài)加密等)來解決交易金額的隱私保護問題.例如門羅幣采用Borromean環(huán)簽名結(jié)合 Perdersen承諾[9]來實現(xiàn)對交易金額的隱藏,零幣則采用zk-SNARK[10–12]這類零知識證明對交易身份以及交易金額進行隱藏.

區(qū)塊鏈作為數(shù)字貨幣的支撐技術(shù),本質(zhì)上是采用鏈式數(shù)據(jù)結(jié)構(gòu)來驗證和存儲數(shù)據(jù)并結(jié)合分布式共識機制來生成并更新數(shù)據(jù),從而保證全網(wǎng)誠實節(jié)點的狀態(tài)一致性.去中心化、可驗證以及防篡改是區(qū)塊鏈技術(shù)的基本屬性.隨著對區(qū)塊鏈技術(shù)的深入研究以及其可能的應(yīng)用場景的探討,敏感數(shù)據(jù)的隱私保護問題顯得尤為重要.在區(qū)塊鏈系統(tǒng)[13]中,隱私保護主要體現(xiàn)在兩個方面:匿名性和秘密性.其中匿名性是指交易發(fā)起者和交易接收者的身份隱藏,而秘密性是指交易金額的隱藏.目前比特幣系統(tǒng)只提供弱匿名性,即交易發(fā)起者和交易接收者的真實身份與其對應(yīng)的公鑰沒有關(guān)系.門羅幣和零幣雖然能解決隱私保護問題,但門羅幣中證據(jù)的長度較大,而零幣需要可信任第三方的參與并且證據(jù)生成時間很長.因而給出一個高效簡潔的隱私保護方案是一個非常有挑戰(zhàn)的問題.

為了保障交易的秘密性,Maxwell等人提出秘密交易 (CT)[14]概念,即交易發(fā)起者對交易金額做承諾,然后給出相應(yīng)的證據(jù)證明該金額在某個公開的范圍內(nèi).Maxwell等人利用Borromean環(huán)簽名給出一個具體的范圍證明方案,該方案無需可信第三方的參與,然而證據(jù)長度比較龐大并且證據(jù)生成和證據(jù)驗證的時間復(fù)雜度也不小(均與金額的比特數(shù)線性相關(guān)),因此該方案在實際應(yīng)用中很受限.Jan Camenisch等人于 2008年提出基于 Boneh-Boyen簽名[15]的交互式范圍證明方案[16],該方案后來被 Shunli Ma等人[17]借鑒用來保護交易金額的隱私性,由于該方案利用雙線性對并且需要可信第三方的參與,雖然證據(jù)長度很短,但驗證時間比較長.2017年,Benedikt Bunz等人[18]提出新的范圍證明方案,該方案借鑒Jonathan Bootle[19]等人提出的基于多項式承諾的零知識證明方案,并利用向量內(nèi)積承諾方案將證據(jù)長度減為對數(shù)級別.該方案不僅不需要可信第三方的參與,而且將證據(jù)長度大大降低并且減少證據(jù)驗證的時間復(fù)雜度,這使得該方案能很好地應(yīng)用在區(qū)塊鏈系統(tǒng)中.本文在 Benedikt Bunz等人工作的基礎(chǔ)上提出了一個新的范圍證明方案,該方案將金額按兩比特劃分并構(gòu)造新的可滿足性電路,然后借鑒 Jonathan Bootle等人的零知識證明方案和向量內(nèi)積承諾,將證據(jù)的生成時間和證據(jù)的驗證時間大幅減少.結(jié)合Jonathan Bootle等人的零知識證明方案以及向量內(nèi)積承諾的安全性證明,很容易給出本文提出的范圍證明方案的安全性證明.當(dāng)公開區(qū)間為[0,264)時,本文方案不僅將證據(jù)生成時間減少近一半,而且將證據(jù)驗證時間減少約 33%.為了對這些范圍證明方案有一個直觀的認識,表1給出這四個方案的性能比較,其中ct表示橢圓曲線中標量點乘的時間復(fù)雜度,cs表示橢圓曲線中點的長度.容易看出本文的范圍證明方案更適合應(yīng)用在區(qū)塊鏈系統(tǒng)中來保護交易金額的隱私.

本文的結(jié)構(gòu)如下:首先第2節(jié)介紹符號定義、Pedersen承諾以及多項式承諾的基本概念.接下來第3節(jié)介紹Jonathan Bootle等人提出的對任意函數(shù)的零知識證明方案.第4節(jié)給出本文的范圍證明方案.最后第5節(jié)對本文做出一個總結(jié).

表1 n=64,m=8具體方案性能比較Table 1 Performance comparison among specific schemes with n=64,m=8

2 預(yù)備知識

本節(jié)首先介紹一些符號定義,然后介紹Pedersen承諾、多項式承諾以及向量內(nèi)積承諾等基礎(chǔ)知識.

2.1 符號定義

下面介紹本文將要使用的符號定義.

G 滿足離散對數(shù)困難問題的乘法交換群

g群G的生成元

q群G的階,為大素數(shù)

Zq模q的整數(shù)環(huán)

H抵抗碰撞的哈希函數(shù)

?向量的Hadmard積

·向量的內(nèi)積

⊕異或運算

ct G上隨機元素指數(shù)運算的計算復(fù)雜度

ce G上雙線性對運算的計算復(fù)雜度

cs G上元素的長度

本文規(guī)定加粗的字符表示向量,未加粗的字符表示集合中的元素.并且規(guī)定這里g=(g1,g2,···,gn)∈Gn,a=(a1,a2,···,an)∈. 規(guī)定兩個向量多項式a(X),b(X)∈[X]的乘積運算c(X)=a(X)·b(X)為多項式乘法并且系數(shù)之間的乘法定義為內(nèi)積,此時c(X)∈Zq[X].

2.2 Pedersen承諾

Pedersen承諾[9]是由雙方參與的協(xié)議.定義公開參數(shù)ck={G,q,g,h},這里g是G的生成元,h∈G且其離散對數(shù)未知.

定義 1(Pedersen承諾)Comck(a;r):=grha為對a的Pedersen承諾,這里r是隨機數(shù)且不公開.

而多元 Pedersen承諾類似于 Pedersen承諾,即給定公開的參數(shù) ck=(G,q,g,h1,···,hn),這里g是 G 的生成元,(h1,···,hn)∈Gn,這些點的離散對數(shù)均未知.給定消息 (m1,···,mn)∈,則對應(yīng)的Pedersen承諾為

Pedersen承諾滿足隱藏性(Hiding)和綁定性(Binding):

隱藏性:承諾值和隨機數(shù)在計算上不可區(qū)分.由于r是隨機數(shù),C0=grha0和C1=grha1在計算上是不可區(qū)分的,進而隱藏承諾內(nèi)容.

綁定性:在承諾做出之后,承諾內(nèi)容不可抵賴.假設(shè)存在r′和a′?=a使得grha=C=gr′ha′,則有h=g(r?r′)(a′?a)?1,這說明h的離散對數(shù)已經(jīng)被求出,而這與離散對數(shù)的困難性假設(shè)矛盾,因此綁定性滿足.

2.3 多項式承諾

假設(shè)證明者擁有多項式t(X)=t0+t1X+t2X2+···+td?1Xd?1,則該多項式承諾是一個三段式協(xié)議,具體流程如下:

(1)證明者計算pc←PolyCommit(t(X)),即對t(X)的每個系數(shù)做承諾,

這里ck={G,q,g,h},然后將pc發(fā)送給驗證者.

(2)驗證者隨機選擇x∈,并將其發(fā)送給證明者.

(3)證明者計算 pe←PolyEval(x,t(X)),這里 pe=(v,ρ),其中v=t(x),ρ=;并將 pe發(fā)送給驗證者.

(4)驗證者計算v←PolyVerify(pc,pe,x),這里

利用Fiat-Shamir方法,該承諾方案變?yōu)榉墙换ナ匠兄Z方案,此時x=H(pe,ck).于是證明者公開承諾值(pe,v,ρ),驗證者則計算x并調(diào)用PolyVerify(pc,pe,x)驗證該承諾是否合法.

注意到承諾的長度會隨多項式的次數(shù)d增加而線性增加.為了降低承諾的長度,文獻 [19]將多項式的系數(shù)分段并構(gòu)造矩陣,然后對矩陣的每一行做多元 Pedersen承諾并構(gòu)造新的多項式承諾方案,此時承諾長度為

2.4 向量內(nèi)積承諾

向量內(nèi)積承諾是指證明者擁有兩個秘密向量a,b∈,公開c=a·b以及A=ga和B=hb,證明者向驗證者證明A和B所蘊含的向量a和b之內(nèi)積確實為c.

下面介紹文獻[19]提出的向量內(nèi)積承諾方案,不妨將該方案記做(G,g,h,A,B,c,n;a,b),這里g和h中每個元素的離散對數(shù)互不知曉且n為二的冪次方.

首先將n維向量切成2個塊,每個塊是n/2維的向量,記

這里g1,g2,h1,h2∈Gn/2,a1,a2,b1,b2∈,則

如果令A(yù)′=(g′)a′,B′=(h′)b′,則原向量內(nèi)積承諾轉(zhuǎn)化為對新向量a′和b′的內(nèi)積承諾.注意到驗證者需要計算g′,h′,A′,B′以及c′,證明者需要傳輸Ak,Bk和ck,這里k∈{?1,1}.

下面描述該向量內(nèi)積承諾方案(G,g,h,A,B,c,n;a,b)的具體過程,這里只有a和b是秘密.在下面的過程描述中,P是指證明者,而V是指驗證者.

公開輸入:g,h∈Gn,A,B∈G,c∈,并且假設(shè)n為二的冪次方.

秘密輸入:證明者擁有(a,b)且滿足A=ga,B=hb以及c=a·b.

協(xié)議過程:(1)當(dāng)(n>1)時,執(zhí)行遞歸約減步驟:

?P→V:發(fā)送A?1,B?1,c?1,A1,B1,c1共 6個元素 (注意到A0=A,B0=B和c0=c,這三元組不用發(fā)送);

?P←V:發(fā)送隨機數(shù)x∈;

?P→V:P和V分別將原始知識證明問題轉(zhuǎn)化為如下知識證明問題

這里

此外,P還需更新自己的秘密輸入,即a′=a1x+a2x2和b′=b1x?1+b2x?2.

然后P和V循環(huán)執(zhí)行該遞歸約減步驟.

(2)當(dāng)(n=1)時,執(zhí)行終止步驟:

?P→V:P直接發(fā)送(a,b);

?P←V:如果A=ga,B=hb以及c=ab成立,則返回接受,否則拒絕.

上述方案中證明者需要向驗證者發(fā)送Ai,Bi以及ci,所需的通信帶寬較大.為了降低通信復(fù)雜度,文獻[18]考慮P=gahb,這里c=a·b,gt的離散對數(shù)未知.此時在遞歸約減的步驟中Ai,Bi和ci可以合并發(fā)送.不妨將該承諾方案記做(G,gt,g,h,P,n;a,b),下面是其具體過程.

公開輸入:g,h∈Gn,gt,P∈G,這里n是二的冪次方.

秘密輸入:證明者擁有a=(a1,a2),b=(b1,b2)并滿足,這里

g=(g1,g2),h=(h1,h2),c=a1·b1+a2·b2

協(xié)議過程:如果n=1,則

?P→V:直接發(fā)送(a,b)

?P←V:如果P=gahb,這里c=ab,則返回接受;否則拒絕.

遞歸約減:如果n>1,則證明者令n′=n/2,然后計算

?P→V:發(fā)送 (L,R),這里cR=a2·b1∈Zq.

?P←V:發(fā)送隨機數(shù)x∈

?證明者和驗證者將原問題轉(zhuǎn)化為如下新問題

(G,gt,g′,h′,P′,n′;a′,b′)

這里

而且證明者還需計算

綜上,第一個向量內(nèi)積承諾方案的通信復(fù)雜度為6logn+2,而第二個向量內(nèi)積承諾方案的通信復(fù)雜度為2logn+2,而且第二個方案的計算復(fù)雜度比第一個方案小.引理1給出這兩個內(nèi)積承諾方案的安全性.

引理 1上述向量內(nèi)積承諾方案具有完美完全性 (perfect completeness)和統(tǒng)計的見證擴展仿真性(statistical witness-extended-emulation),即提取出非平凡的離散對數(shù)或者提出有效的見證(witness).

證明請參考文獻[18].

3 算術(shù)電路的無中心零知識證明方案

零知識證明由 Goldwasser等人[21]于上世紀 80年代提出.它是一種密碼學(xué)技術(shù),通過交互,證明者向驗證者證明某個提議是正確的并且無需泄露除了它是正確之外的任何信息.后來,Goldreich等人[22]證明任何 NP問題都有零知識證明系統(tǒng).至此人們提出許多零知識證明方案,其中最為著名的是 Fiat-Shamir零知識身份認證協(xié)議[23–25],其安全性建立在大整數(shù)分解問題的困難性,然而其通信和計算復(fù)雜度太大,因而實用性不強.2013年,Parno等人提出匹諾曹協(xié)議[10],該協(xié)議是一個簡潔非交互式零知識證明協(xié)議(zk-SNARK),并且用于對任意布爾 (或算術(shù))電路的可信計算.該協(xié)議最大的優(yōu)勢是無論可滿足性電路有多復(fù)雜,其證據(jù)的長度固定為 288字節(jié).2016年,Bootle等人[19]提出另外一種零知識證明協(xié)議,該協(xié)議同樣用于對任意布爾電路的可信計算.與匹諾曹協(xié)議不同的是,該協(xié)議不僅無需可信第三方以及復(fù)雜的預(yù)計算過程,而且其安全性只依賴于離散對數(shù)的困難性.2017年,Bootle等人[26]提出可以批處理的零知識證明,該方法將多個秘密滿足的簡單電路轉(zhuǎn)化為低次數(shù)的多項式,進而利用多項式承諾給出高效的證明.2018年,Wahby等人[27]提出新的zk-SNARK協(xié)議Hyrax,該協(xié)議結(jié)合Pedersen承諾、求和驗證協(xié)議等密碼學(xué)工具對任意電路實現(xiàn)可信計算,并且無需可信第三方以及安全性假設(shè)只依賴于離散對數(shù)問題.除此之外,Huige WANG等人[28,29]借鑒這類對可滿足性電路的零知識證明方法并應(yīng)用在功能加密和訪問控制加密中.

本節(jié)介紹Bootle等人的零知識證明方案,其中3.1節(jié)介紹算術(shù)電路轉(zhuǎn)化為代數(shù)表達式的過程,第3.2介紹代數(shù)表達式轉(zhuǎn)化為向量多項式的過程,接下來3.3節(jié)介紹基于多項式承諾的零知識證明方案,最后3.4節(jié)給出該零知識證明方案的具體過程.

3.1 算術(shù)電路的代數(shù)表達式刻畫

本節(jié)介紹將任意給定算術(shù)電路轉(zhuǎn)化為代數(shù)表達式的過程.

如圖1所示,首先對每個乘法門分配相應(yīng)的(ai,bi,ci),其對應(yīng)的代數(shù)表達式為aibi=ci;其次對于常數(shù)乘法門以及異或門,利用相關(guān)輸入輸出的仿射表達式刻畫,例如圖1中右側(cè)的線性表達式給出了常數(shù)乘法門和異或門的代數(shù)刻畫.

圖1 算術(shù)電路的代數(shù)表達式刻畫Figure 1 Algebraic expression of arithmetic circuity

假設(shè)該電路圖的乘法門個數(shù)N=m?n,(ai,bi,ci)則用三個m?n的矩陣 (A,B,C)表示,定義A?B=C,這里A,B和C的每一行表示為

且滿足ai?bi=ci,其中i∈{1,···,m}.每個仿射表達式的刻畫表示如下

這里wq,a,i,wq,b,i,wq,c,i和Kq是只與電路有關(guān)的常數(shù),Q是仿射表達式的個數(shù).

3.2 算術(shù)電路的多項式轉(zhuǎn)化

本節(jié)介紹將代數(shù)表達式轉(zhuǎn)化為單變元多項式的過程.設(shè)Y是自變量,定義Y′=(Ym,Y2m,···,Ynm)和Y=(Y,Y2,···,Ym),則Y(A?B)Y′T=YCY′T,展開得

即Yi+jm對應(yīng)的系數(shù)滿足ai,jbi,j=ci,j.令M=N+m,對于Q個仿射表達式,則有

將上面的兩個表達式聯(lián)立,有

定義

于是電路是可滿足的當(dāng)且僅當(dāng)

設(shè)驗證者發(fā)送隨機數(shù)y∈,此時證明者需要證明

這里y′=(ym,y2m,···,ynm).

3.3 基于多項式承諾的零知識證明

根據(jù)算術(shù)電路的代數(shù)表達式刻畫,證明者構(gòu)造如下洛朗多項式:

這里d為盲化向量.容易驗證t(X)的常數(shù)項為零.

一種非常直接的思路是,證明者首先將ai,bi,ci和d的承諾發(fā)送給驗證者,隨后驗證者隨機選取y∈并將其發(fā)送給證明者,接下來證明者利用PolyCommit將t(X)的承諾pc發(fā)送給驗證者,驗證者隨后隨機選取x∈并將其發(fā)送給證明者,然后證明者將r(x)以及由PolyEval產(chǎn)生的pe一并發(fā)送給驗證者,此時驗證者首先根據(jù)ai,bi,ci和d的承諾驗證r(x)的正確性,然后計算s(x)和K(y)以及r′(x),接著驗證者根據(jù)(pc,pe)驗證承諾的正確性并計算t(X)在x處的取值,最后驗證者判斷t(x)r(x)·r′(x)?2K(y)是否成立即確定該證據(jù)是否為對應(yīng)電路的合法零知識證明.

文獻[18]的作者利用向量內(nèi)積承諾給出更高效的證明方案.注意到

這里Ai,Bi,Ci和D分別是ai,bi,ci和d的承諾,即

Ai=Comck(ai,αi),Bi=Comck(bi,βi),Ci=Comck(ci,γi),D=Comck(d,δ)

其中 ck={G,q,g,g=(g1,g2,···,gn)}. 如果令,則gr=hr?y′并且hr′=grh2s.設(shè)v=t(x),則r·r′=v+2K(y).此時該零知識證明方案轉(zhuǎn)化為如下向量內(nèi)積承諾方案

(G,g,h,R,R′,v+2K(y),n;r,r′)

這里R=gr,R′=R?h2s=hr′,此時證明者的秘密輸入是r和r′,而驗證者通過多項式承諾方案得到v的取值.

3.4 零知識證明方案的具體描述

本小節(jié)介紹零知識證明方案的詳細過程,其中P是指證明者,V是指驗證者.

公開輸入:(ck,C,N,m,n),這里ck=(G,q,g,g),g=(g1,g2,···,gn)∈Gn和函數(shù)f的布爾電路C.

證明階段:

如果n=1,將 (pe,r,ρ)發(fā)送給 V;

否則計算r′=r?y′+2s(x),并將 (pe,ρ)發(fā)送給 V.

驗證階段:首先V計算v←PolyVerify(pc,pe,x),如果v=⊥則拒絕并驗證失敗.

?如果n=1,V根據(jù)收到的r計算r′=r?y′+2s(x)并且驗證

?如果n>1,P和V運行如下向量內(nèi)積承諾

(G,g,h,R,R′,v+2K,n/2;r,r′)

這里

引理2給出上述對任意可滿足性電路的基于多項式承諾的零知識證明方案的安全性.

引理 2上述對可滿足性電路的零知識證明方案滿足完美完全性 (perfect completeness)、完美誠實驗證者零知識性 (perfect special honest verifier zero-knowledge)以及統(tǒng)計的見證擴展模擬性 (statistical witness-extended emulation),即提取一個違背承諾方案綁定性的實例或者可滿足性電路中的見證(witness).

證明請參考文獻[19].

4 高效的范圍證明方案

范圍證明是零知識證明在區(qū)塊鏈系統(tǒng)中的一個重要應(yīng)用.范圍證明是指對于某個值v∈[0,2n),證明者構(gòu)造Pedersen承諾V=gwhv以及相應(yīng)的證據(jù),以證明該值v確實在范圍[0,2n)中.

文獻[18]將v按單比特處理,即令,則vi(vi?1)=0,根據(jù)這兩個方程構(gòu)造多項式,并利用多項式承諾構(gòu)造范圍證明.最后他們提出的改進的向量內(nèi)積承諾將證據(jù)的長度減為O(logn).本文將v按兩比特處理并構(gòu)造新的多項式,然后構(gòu)造相應(yīng)的多項式承諾,最后結(jié)合向量內(nèi)積承諾給出高效的范圍證明方案.

4.1 新方案描述

令v=,這里k=n/2.此時vi(vi?1)(vi?2)(vi?3)=0.令

a=(v0,v1,···,vk?1),

b=a?3,c=a?b,d=c+2,

v=a·t4

這里定義

按照前面介紹的方法,我們構(gòu)造兩個洛朗多項式r(X)和r′(X),使得這兩個向量多項式的乘積多項式的常數(shù)項為零,即令

r(X)=ay?1X+bX?1+cX2+dX?2+cy?1X3+eX4

s(X)=y·y2k·(yX?1?X+ykX?2?ykX2)+t4yX?1?2y′X?3

r′(X)=r(X)?y′+s(X)

t(X)=r(X)·r′(X)?K(y)

這里y=(y,y2,···,yk)∈Zkq,y′=(y2,y4,···,y2k)∈以及K(y)=y2k·y·(3+2yk).于是t(X)的常數(shù)項

t0=2(a?b?c)·y′·y?1+2(c?d)·y′+y·y2k((a?b)+(c?d)·yk)+(a·t4)?K(y)

=y2k·y·(3+2yk)+v?K(y)=v

在介紹協(xié)議的執(zhí)行過程之前,令該協(xié)議的公開參數(shù) (G,q,g,h,gs,hs,gu,g,h),這里g=(g1,g2,···,gk),h=(h1,h2,···,hk),且g,h,g,h,gs,hs,gu的離散對數(shù)互不知曉.下文的過程描述中P是指證明者,V是指驗證者.

證明過程:

?P→V: 隨機選擇α,β,γ,δ,θ∈以及盲化向量 e∈,計算

A=Comck(a;α),B=Comck(b;β),C=Comck(c;γ),

D=Comck(d;δ),E=Comck(e;θ)

這里ck={G,q,g,g},然后將A,B,C,D和E發(fā)送給驗證者.

?P←V:發(fā)送隨機值y∈,然后 P計算s(X)和K(y)

?P→V:P計算洛朗多項式

r(X)=ay?1X+bX?1+cX2+dX?2+cy?1X3+eX4

s(X)=y·y2k·(yX?1?X+ykX?2?ykX2)+t4yX?1?2y′X?3

r′(X)=r(X)?y′+s(X)

t(X)=r(X)·r′(X)?K(y)

然后對t(X)的非零系數(shù)做承諾,即,這里t(X)=

i∈{?5,?4,?3,?2,?1,1,2,3,4,5,6}.P 將這 11個承諾值發(fā)送給 V.

?P←V:發(fā)送隨機值x∈,V計算

s=s(x)=y·y2k(yx?1?x+ykx?2?ykx2)+t4yx?1?2y′x?3

?P→V:P計算

r=r(x)=ay?1x+bx?1+cx2+dx?2+cy?1x3+ex4

ρ=αy?1x+βx?1+γx2+δx?2+γy?1x3+θx4

s=s(x)=y·y2k·(yx?1?x+ykx?2?ykx2)+t4yx?1?2y′x?3

以及t=t(x)=r·(r?y′+s)和τx=,這里τ0=ω,即承諾值V的隨機指數(shù).如果k=1,P將τx,ρ,r發(fā)送給 V;否則 P將τx,ρ,t發(fā)給V.

驗證過程:首先驗證者根據(jù)收到的τx和t驗證是否成立,如果不成立,則驗證失敗.其次,

?如果k=1,V根據(jù)r計算t=r·(r?y′+s)?K(y)并驗證

Comck(r;ρ)=Ay?1xBx?1Cx2Dx?2Cy?1x3Ex4

是否成立,如果不成立,則驗證失敗.

?如果k>1,P 和 V 均計算R=Ay?1xBx?1Cx2Dx?2Cy?1x3Ex4g?ρ=gr并計算

(G,q,gu,gv,hv,R′,k;r,r′)

本節(jié)給出的范圍證明方案是交互式方案,為了將其應(yīng)用在區(qū)塊鏈系統(tǒng)中,利用Fiat-Shamir變換很容易將其變?yōu)榉墙换ナ椒秶C明方案.

定理1本文提出的范圍證明方案具有完美完整性(perfect completeness)、完美誠實驗證者零知識性(perfect honest verifier zero-knowledge)以及計算特殊合理性(computational special soundness).

證明:證明者和驗證者在運行向量內(nèi)積承諾之前,他們的交互過程與文獻[19]中的對可滿足性電路的零知識證明方案的過程一致.如果證明者和驗證者不運行向量內(nèi)積承諾,而是證明者在最后一步將t(X)的承諾以及r直接發(fā)送給驗證者,根據(jù)引理1和多項式承諾的完美完整性和統(tǒng)計特殊合理性 (statistical special soundness),該修改的范圍證明方案具有完美完整性、完美誠實驗證者零知識性以及計算特殊合理性.而本文提出的范圍證明方案是將向量內(nèi)積承諾替換這個修改范圍證明方案的最后一步,由于gu,g,h的離散對數(shù)互不知曉,根據(jù)引理2以及類似文獻[18]對計算特殊合理性的證明,本文提出的范圍證明方案具有完美完整性、完美誠實驗證者零知識性以及計算特殊合理性.

4.2 新方案性能分析

本文我們只考慮將G上的指數(shù)運算作為對范圍證明方案的計算復(fù)雜度的估計,這是因為Zq上的算術(shù)運算與G上的指數(shù)運算相比可以忽略不計.記ct為G上隨機元素的指數(shù)運算所需的時間復(fù)雜度,指數(shù)運算由平方和乘法運算組成.本文假設(shè)指數(shù)運算所需的總平方運算和總乘法運算耗時相當(dāng),并且假設(shè)固定元素的指數(shù)運算所需要的時間復(fù)雜度只占隨機元素指數(shù)運算時間復(fù)雜度的一半 (這里暫不考慮建表等優(yōu)化細節(jié)).設(shè)cs為G上元素的長度并且假設(shè)G中元素和Zq中元素的比特長度相同(如果考慮G為橢圓曲線群,利用點壓縮技術(shù)后,G中元素只比Zq中元素多1比特).

下面分析本文方案的計算復(fù)雜度和證據(jù)長度.在運行內(nèi)積向量承諾(G,q,gu,gv,hv,R′,k;r,r′)之前,證明者的計算開銷主要是 (A,B,C,D,E)的計算、11個Ti的計算以及 (gv,hv,R′)的計算,其總的時間復(fù)雜度約為 (0.75n+19)ct,而驗證者的計算開銷主要是 (τx,t)的驗證以及 (gv,hv,R′)的計算,其總的時間復(fù)雜度約為 (0.5n+12)ct.證明者和驗證者運行內(nèi)積向量承諾 (G,gu,gv,hv,R′,k;r,r′)所需的時間復(fù)雜度分別為 (0.5n+6.5logn?15)ct和 (4.5logn?7)ct.綜上,證明者產(chǎn)生證據(jù)的時間復(fù)雜度為 (1.25n+6.5logn+4)ct,而驗證者產(chǎn)生證據(jù)的時間復(fù)雜度為 (0.5n+4.5logn+5)ct,證據(jù)的長度為(19+2logn)cs.

接下來分析文獻[18]中方案的計算復(fù)雜度和證據(jù)長度.在運行內(nèi)積向量承諾之前,證明者花費的時間復(fù)雜度約為(2n+3.5)ct,而驗證者花費的時間復(fù)雜度約為(n+6)ct.證明者和驗證者運行內(nèi)積向量承諾所需的時間復(fù)雜度分別為(n+6.5logn?8.5)ct和(4.5logn?2.5)ct.因此證明者總的時間復(fù)雜度約為(3n+6.5logn?5)ct,而驗證者總的時間復(fù)雜度約為(n+4.5logn+3.5)ct,證據(jù)的長度為(9+2logn)cs.

最后分析文獻 [16]和文獻 [14]方案的計算復(fù)雜度和證據(jù)長度,并在表2中給出這四個方案的證據(jù)生成時間、證據(jù)驗證時間以及證據(jù)長度.值得一提的是,文獻[16]方案需要可信第三方的預(yù)計算,且預(yù)計算的時間復(fù)雜度為 (2n/m+0.5)ct,表中ce表示G上的雙線性對的時間復(fù)雜度,一般來說ce>8.5ct.本文與文獻[18]相比,證據(jù)生成的時間和證據(jù)驗證的時間均大大減少.

從表中可以看出,在無中心的前提下,本文的方案是非常有優(yōu)勢的.值得一提的是,工程實現(xiàn)一般選擇G為滿足離散對數(shù)困難的素數(shù)階橢圓曲線群,則文獻[14,18]以及本文所提出的方案具有很大的優(yōu)化空間,而文獻 [16]方案中證據(jù)的真實生成時間不會比本文方案的證據(jù)生成時間要少.考慮到本文的方案在驗證的時間復(fù)雜度上更有優(yōu)勢以及證據(jù)長度很小,本文的方案更適合應(yīng)用在區(qū)塊鏈系統(tǒng)中.

表2 范圍證明方案的性能比較Table 2 Performance comparison among range proof schemes

5 結(jié)論

本文研究文獻[18]的范圍證明方案并結(jié)合該文獻的零知識證明方案提出一種新的高效的范圍證明方案,新方案對金額進行兩比特分割,然后結(jié)合向量內(nèi)積承諾構(gòu)造相應(yīng)的多項式承諾.與文獻[18]中的方案相比,當(dāng)范圍區(qū)間為[0,264)時,本文的方案將證明者的計算時間減少了近一半,而將驗證者的計算時間減少約33%.通過與文獻[14,16,18]的方案相比,本文的方案非常實用.