您的位置:首页 > 区块链 >

ZK-ConSNARK无需trusted setup 可推进隐私保护区块链的效率

2019-10-04 21:49:38 来源: 区块网

为什么关注ZK-ConSNARKSuterusu项目关注的是无需trusted setup,且证明空间复杂度为常数的,计算高效的零知识证明方案,简称ZK-ConSNARK。

为什么关注ZK-ConSNARK

Suterusu项目关注的是无需trusted setup,且证明空间复杂度为常数的,计算高效的零知识证明方案,简称ZK-ConSNARK。我们知道,一般情况下区块链系统需要将交易通过p2p网络传输给系统中每个验证节点进行验证。

因此,网络单位时间能处理的交易数目,俗称出块率,很大程度上取决于区块大小,以及单位交易所占空间大小【CDEGJKMSSSS16】。交易越小,则出块率越高。在隐私保护区块链方案中,交易大小又很大程度上取决于其所包含的零知识证明大小。

事实上,需要trusted setup的ZK-ConSANRK文献里已有不少,Zcash所使用的方案就属于这个类别。但无需trusted setup的ZK-ConSNARK却是稀有品种,目前本人所能找到这方面的结果只有两篇:Crypto 2019年新鲜出炉的结果【LM19, BBF19】。这篇文章将简单介绍这两个方案的基本思路以及Suterusu项目在ZK-ConSANRK上的关注点。

上述两篇论文【LM19, BBF19】都结合了概率性可验证证明(Probabilistically Checkable Proof,PCP)和子向量承诺(Subvector Commitment)方案。PCP是复杂性理论和密码学里一个非常经典的结果,相关定理的提出者因此获奖无数。

PCP作为一个基础方案可用于构造零知识证明。上述两篇论文主要贡献不在于PCP,而在于这个子向量承诺方案。其原因在于PCP方案如果想在非交互式零知识证明这个领域施展身手离不开高效的子向量承诺方案这个助手。

什么是概率性可验证证明

首先,我们简单介绍下什么是概率性可验证证明。我们在前文【林19-1】中介绍过零知识证明的概念。零知识证明中有这么个验证者的概念,在PCP中也有个验证者。但PCP的验证者特别懒,所以我们需要考虑验证者如何能在做非常少工作的情况下,还能准确判断PCP证明者针对一个定理提供的证明是否正确。

尽管PCP本身的证明是非常长,但PCP有个神奇的性质就是在证明者生成证明后,验证者只需随机在证明上查询若干点(实际中大概是安全系数×3bits即可,所以如果是256-bit security,查询长度只需256*3 bits),然后做一些极为高效的运算就可以验证证明的正确性。

我们在前文【林19-1】中提过,区块链中使用的零知识证明需要是极为简短的且最好计算也是高效的,尽管PCP的验证计算颇为高效,但证明过长仍是个弊病。我们注意到在验证时验证者真正需要访问的只是整个证明中极小一部分内容。

那么问题来了,有没有可能让证明者在生成PCP证明后自己在证明上随机选取验证者需要的查询点,然后只传输这些信息给验证者,从而大大减少通信量呢?

这个思路是对的,但一个恶意的证明者,或者一个不掌握证明秘密的人可以针对这个简单思路发起如下几个攻击:比如可能这个用于随机选取查询点的随机数本身不随机,或者攻击者先生成随机数,然后再针对这些随机位置生成对应证明,换句话说他可能没有能力生成全部正确PCP证明,但他却有办法针对提前生成的随机位置生成合法的部分证明,进而相应地替换篡改他所生成的非法证明的对应位置内容,从而通过验证。

什么是子向量承诺

如何防止这类攻击呢?这就需要引入我们的子向量承诺方案了。首先,我们先说下2019年前的工作中如何解决这个问题。承诺这个概念我在前面介绍Mimblewimble的文章【林19-3】中曾提到,事实不仅仅有Pedersen承诺方案,我前面关于Zcash的文章【林19-2】中提到的Merkle tree也可以被看作是一种承诺方案。

那么具体Merkle tree可以怎么和PCP结合呢?

证明者首先生成PCP证明,这些证明每个bit将作为Merkle tree的一个叶节点来计算哈希树根节点数值,这个数值就是一个对上述PCP证明的承诺了。

我们之前提过承诺方案有个soundness性质可以保证一旦承诺公开,用户是没法在打开承诺时改变承诺的内容的,在Merkle tree中这个性质主要是由所使用哈希函数的抗碰撞性来保证的。

那么好,证明内容一旦生成无法篡改了,接下来的问题就是随机性如何解决的问题了?如果Merkle tree现在的根节点值是r的话,那么用于决定证明查询位置的随机数将被定义成H(r),这里H是个安全哈希函数,比如SHA256。

为什么这能保证H(r)是随机的呢?

这个是和哈希函数的理论建模有关的。密码学理论里一般把H(.)建模成随机预言机,这意味着即使哈希函数的输入是公开的,其输出也是完全随机的。

哈希函数的这个随机预言机模型和承诺方案的soundness性质合力保证验证者可以相信这个随机数是在证明者把PCP证明关进承诺这个箱子之后才生成的,且这个用于定义证明查询位置的随机数确实是随机的。因此如果他确定后面承诺打开过程中显示的消息确实是这些随机数对应的位点信息后,那么上述攻击就可以被认为是无效的。

好,那么现在问题就规约到如何保证证明者在承诺打开阶段输出的信息确实是对应由这些随机数定义的位置的。在Merkle tree这种承诺中,每个打开的消息同时还会有一些附属的证明信息来证明这个打开的消息确实是某个叶节点位置的信息。但注意这个承诺方案的附属证明空间复杂度不是常数,而是PCP空间复杂度的对数。

另外,由于Merkle tree每次只能打开一个证明位点,上述证明过程需要重复和安全参数相关的次数(比如256*3次),这就导致证明所占空间无法避免地膨胀。【LM19】文章提到如果一个PCP所占空间为1GB,使用Merkle tree这种承诺方案,对应的最终零知识证明所占空间为88KB,且绝大部分都是由Merkle tree的这种附属证明导致的额外开销。

现在,我们终于可以介绍什么是子向量承诺了,事实上,Merkle tree可以看作一种非常简陋的子向量承诺方案。和Merkle tree一样,Crypto 19提出的子承诺方案可以一次性把整个向量装进承诺这个黑箱里,但和Merkle tree不同的是,在打开承诺阶段,用户可以同时打开和向量若干个位置绑定的内容,而且对应的证明空间复杂性为常数。这个方案的构造需要用到一个特殊的代数结构,叫group of unknown order。

事实上,这个概念可以看作RSA group的一种抽象。但RSA group对应方案需要trusted setup,所以不太适用于隐私保护区块链系统。目前也存在无需trusted setup的RSA group方案,但效率极低。所以上述两文都提到了另外一种基于class groups of quadratic imaginary order的代数结构来保证无需trusted setup的高效子向量承诺方案。

Suterusu的关注点

尽管上述两文的方案已能实现可高效验证的ZK-ConSNARK,但底层基于的PCP方案由于生成证明的开销太大无法实际应用,但他们起码从理论上证明了无需trusted setup的ZK-ConSNARK的可行性。Suterusu将针对去中心化隐私支付这种特殊的应用场景优化实现一些特殊的ZK-ConSNARK,来推进隐私保护区块链的效率和去中心化程度。(林煌)

关键词: ZK-ConSNARK trusted setup 隐私

精选 导读

募资55亿港元万物云启动招股 预计9月29日登陆港交所主板

万科9月19日早间公告,万物云当日启动招股,预计发行价介乎每股47 1港元至52 7港元,预计9月29日登陆港交所主板。按发行1 167亿股计算,万

发布时间: 2022-09-20 10:39
管理   2022-09-20

公募基金二季度持股情况曝光 隐形重仓股多为高端制造业

随着半年报披露收官,公募基金二季度持股情况曝光。截至今年二季度末,公募基金全市场基金总数为9794只,资产净值为269454 75亿元,同比上

发布时间: 2022-09-02 10:45
资讯   2022-09-02

又有上市公司宣布变卖房产 上市公司粉饰财报动作不断

再有上市公司宣布变卖房产。四川长虹25日称,拟以1 66亿元的转让底价挂牌出售31套房产。今年以来,A股公司出售房产不断。根据记者不完全统

发布时间: 2022-08-26 09:44
资讯   2022-08-26

16天12连板大港股份回复深交所关注函 股份继续冲高

回复交易所关注函后,大港股份继续冲高。8月11日大港股份高开,随后震荡走高,接近收盘时触及涨停,报20 2元 股。值得一提的是,在7月21日

发布时间: 2022-08-12 09:56
资讯   2022-08-12

万家基金再添第二大股东 中泰证券拟受让11%基金股权

7月13日,中泰证券发布公告,拟受让齐河众鑫投资有限公司(以下简称齐河众鑫)所持有的万家基金11%的股权,交易双方共同确定本次交易的标的资

发布时间: 2022-07-14 09:39
管理   2022-07-14

央行连续7日每天30亿元逆回购 对债市影响如何?

央行12日再次开展了30亿元逆回购操作,中标利率2 10%。这已是央行连续7日每天仅进行30亿元的逆回购缩量投放,创下去年1月以来的最低操作规

发布时间: 2022-07-13 09:38
资讯   2022-07-13

美元指数创近20年新高 黄金期货创出逾9个月新低

由于对美联储激进加息的担忧,美元指数11日大涨近1%创出近20年新高。受此影响,欧美股市、大宗商品均走弱,而黄金期货创出逾9个月新低。美

发布时间: 2022-07-13 09:36
资讯   2022-07-13

美股三大股指全线下跌 纳斯达克跌幅创下记录以来最大跌幅

今年上半年,美股持续回落。数据显示,道琼斯指数上半年下跌15 3%,纳斯达克综合指数下跌29 5%,标普500指数下跌20 6%。其中,纳斯达克连续

发布时间: 2022-07-04 09:51
推荐   2022-07-04

融资客热情回升 两市融资余额月内增加超344亿元

近期A股走强,沪指6月以来上涨4%,融资客热情明显回升。数据显示,截至6月16日,两市融资余额1 479万亿元,月内增加344 67亿元,最近一个半

发布时间: 2022-06-20 09:41
资讯   2022-06-20

4个交易日净买入超百亿元 北向资金持续流入A股市场

北向资金净流入态势延续。继6月15日净买入133 59亿元后,北向资金6月16日净买入44 52亿元。自5月27日至今,除6月13日以外,北向资金累计净

发布时间: 2022-06-17 09:37
推荐   2022-06-17