关于零知识应用安全性的几点思考
0xb06c
March 15th, 2022

Update :增添了关于Groth16延展性的内容,写完了才想起来,就直接补充进来算了

前言

意识到自己有很长一段时间没有写过文章了,以前什么都不懂的时候很爱去分享一些东西,现在回头看,很多地方其实说的都很不严谨,甚至还有不少错误,在经历了几年的密码学学习后,知道了在很多地方保持严谨是非常重要的。导师经常说有时看到网上一些博客写的科普文章,写的东西错漏百出,不过像他这样也没空去管这些,这时想到我自己曾写过的一些东西,不免也有些汗颜。

当然,倒不是说完全不要去看博客里写的东西,毕竟还是有很多大牛会在博客里分享一些真知灼见,只不过当你真的想要深入了解某些事物时,还是建议看书或者看论文。另外,作为一个搞安全的,快速入门或者是了解某种技术的需求那确实是家常便饭,这时候去看一些科普文章进行一个大概的了解也是很正常的。

零知识证明近几年确实很火,虽然理论知识在上个世纪就已经相对比较完善了,不过近些年在效率上有了很大的提升,在某种程度上也算是得益于区块链的推动,很多密码学家自己也没想到真的能看到零知识证明能实际应用起来,同样的还有环签名,在应用到区块链之前也没找到什么应用场景,可见很多密码学中的很多创新在未来确实是可能派上大用场的。(虽然在这之前这论文可能得在arxiv上躺一段时间

这篇文章在我的TODO list里躺了很久,之前为了写论文了解了一下常见的零知识证明协议的使用,分析了不少论文后有感而发,决定聊聊如何安全地将零知识证明作为工具添加到我们的应用中。

零知识证明协议的安全性

在这篇文章我不会去详细地介绍各个零知识证明系统,因此后面也不会涉及多少高深的密码学知识,但如果你实际上对于零知识证明一无所知,建议是看一点科普文章再回来,下面是一些相关资源的整合,有兴趣深入了解的可以看看

本来想在这里稍微提下零知识证明协议本身的安全性,不过最近Trail of Bits的zkdocs已经对这部分内容进行了总结,目前里面主要是一些经典的零知识证明协议,向开发人员展示了如何正确使用这些协议,避免很多低级错误。这就类似于很多开发人员在应用中使用密码算法时也会犯很多错误,比如AES-GCM中对Nonce的重用,ECDSA中随机数生成器的问题导致的随机数重用等等。因此如果有兴趣深入了解的话,建议是好好研究一下这些协议的正确使用方式的,特别是这些零知识证明协议为何往往是满足诚实验证者模型下的零知识性。(目前zkdocs主要包含经典证明协议的内容,如Schnoor,而SNARK,Bulletproof等协议还未包含,不过针对它们的使用规范目前也超出了我的能力范围)

此外还有一个比较有意思的活动zkHack,里面给出了几道挑战题目,可以帮你更深入的了解各零知识证明协议,执行协议的任何一个环节处理不当都会破坏零知识证明系统的安全性,目前所有题目都给出了解决方案,有兴趣的话可以深入一波

如果你对于这些协议的代码实现问题更感兴趣,我也找过部分资源,下面是一个以太坊的layer2协议Aztec的部分漏洞披露,它们使用的是PLONK协议

另外还有一个有趣的实现漏洞,也是在PLONK协议的代码库中出现的,允许任意伪造证明

聊到这里不免想再提一嘴当前零知识证明在区块链扩容领域的应用,正好前几天Zksync 2.0的测试网也上线了,算是有了个功能较完善的zkEVM,这也是zk-Rollups的代表项目之一。

虽然是叫zk-Rollups,但大部分这类项目实际上跟零知识特性没啥关系,它们主要是使用了SNARK类证明的简洁性succinct,即SNARK中的“S”,表示其协议验证的计算开销和通信开销相对较小。尤其是SNARK类协议中进行proof验证的复杂度是常数级的,与证明的电路大小无关,在我自己的笔记本上进行测试的验证用时也在10ms的数量级,因此可以应用到区块链的状态数据验证上,只需要有部分证明者去根据区块中状态数据的更新生成相应的证明,其他的验证者即可以相对较小的计算量复用证明者的计算结果,同时验证其正确性,从而更新本地的状态根。可以看到这个过程实际上并没有做到保护用户隐私,与我们印象里的零知识证明的特性有点不沾边,所以有人提议是不是该给zk-Rollups改个名字,不然太有误导性

零知识证明应用的安全设计

上面讲的这些并不是我今天想描述的重点,在这里我们主要分析当把零知识证明作为一个开箱即用的工具进行使用时,如何确保我们构建的协议是安全可靠的,尤其是与区块链相结合时

证明的绑定关系

首先我们来聊聊Sigma协议的使用,Sigma本身是Schnoor协议构建的零知识证明协议,属于知识证明的一种,不过具有零知识性,协议的具体内容和构造方法这里就不展开说了,没了解过的可以通过下面的链接速成一下

这种证明通常用来证明离散对数问题,不像zk-SNARK那样属于通用性的零知识证明协议,而且满足的是诚实验证者零知识性,在实际落地的项目中出现的确实较少,不过因其不需要进行可信设置,在很多场景下还是比较有优势的,在论文里面使用的较多

在实际应用中常会见到Sigma协议构建的凭证系统,类似下面的形式

f(x)在这里抽象为由秘密值x参与计算的过程,比如进行签名的验证或是累加器的验证,承诺值C在这里即表示凭证的主体

在上述的证明协议中通常涉及两个关系的证明,一方面P可作为一个身份证明,表明持有一个由秘密值x参与生成的身份ID,另一方面证明承诺值C与P均包含x参与计算,在二者之间建立绑定关系,即凭证C确实是颁发给身份P的

这样一看好像设计方案还挺简单的,不过实际将各种组件塞进去后会比这复杂的多,因此很多论文劈里啪啦写了一长串的证明关系式,看起来倒确实是那么回事,但若仔细分析的话很多都是存在问题的(协议太长审稿人都懒得看了属于

举个例子,下面是我将看过的某篇论文中构建的协议进行了简化的结果,在上面提到的基础协议之上进行了修改

这个协议想证明的关系要多一些,本意是想证明凭证C由两个秘密值x和y参与计算,不过实际进行协议构建时由t替代了x和y,且在这里是一个加法关系

显而易见的,这个证明协议并没有实现我们上面提到的C和P之间的绑定关系,也就是说,对于颁发的凭证C,我可以任意使用其他身份P*来声明对于凭证C的所有权

这通常会破坏凭证系统的不可转移性,一般破坏这一性质需要用户将其私钥分享出去,但像上面的凭证系统直接将凭证C发送出去即可,这肯定是很不安全的

有些人可能会想着直接将t替换回x+y来重新构建证明

不幸的是这样依然无法避免其他身份对凭证C的使用,因为t与x,y之间对应的加法关系使得我们可以任意构造一对x,y来满足关系

一般而言,我们可通过证明如下关系来确保安全性

我们前面提到Sigma协议通常用来证明离散对数关系,在这方面它比通用型的SNARK类协议高效得多,但对于涉及分组密码或是散列函数的证明,在Sigma上构建的成本是非常高的,而SNARK的表现则好的多,因此考虑在零知识证明协议中进行二者的融合确实可以提升效率,将要证明的内容分离开分别使用Sigma和SNARK进行证明。

很多的签名方案中会先对消息进行散列运算,比如ECDSA亦或是我们国密的SM2签名,这就导致没法直接使用Sigma协议进行证明,不过遗憾的是迫于复杂性,很多论文中构造的协议为了最大限度地利用Sigma协议的优势并没有采用融合的方法进行证明

我们可以将类似的证明简化为如下的形式

但是完整的Verify阶段会包含一个散列算法,对消息值x进行散列,但这个是没法直接在Sigma协议中运行的,有些论文中对这个Verify的关系进行了一系列的变换,直接从验证等式中移除了签名的消息x,最后只证明了一个合法签名满足的结构性质,也就是只要是由签名者签署的合法签名均可通过验证,这就与我们上面所提到的问题相同,整个证明没有形成绑定关系,导致在这个系统中颁发的凭证C可以被任何人使用。

有些人可能会想既然如此,那我直接把签名和验证算法中的散列部分给去掉,保证签名的消息m是在一定范围内的,或是在签名前先进行一次散列,在签名算法中直接对消息的散列值进行签名,这样不就可以完美运行在Sigma协议上了。然而这样的操作往往会直接破坏对应的签名算法的安全性,每个标准算法中的步骤都是必不可少的,如果有上过可证明安全课程的同学应该能理解到很多签名算法中的散列函数在随机谕言机模型下的安全性证明中有多么重要。

不过不了解也没关系,我们下面拿国密中的SM2签名算法来举个例子,如果去掉算法流程中的散列函数,那么攻击者完全有能力伪造合法签名,下面是SM2签名算法的流程

如果把其中的Hash(m)直接替换为m,那么我们可以使用如下的方法在没有私钥d的情况下成功伪造签名

虽然我们不能随意控制对应的消息m,如果实际合法的消息m的空间比较小,那么我们找到一个可以利用的签名的概率也不是那么大,这可能要看具体的使用场景,但不管怎么说,这肯定是会极大地削弱系统的安全性,任意修改标准密码算法的行为是绝对不可取的(这等同于自己创建密码算法

当然,也有很多签名算法的流程中是不包含散列函数的,在Sigma协议的零知识证明中用的较多的BBS签名和PS签名等都在这一范畴。

重放攻击的防御

在这一节我们要来如何谈谈在零知识应用中抵御replay attack,其实很容易意识到这种攻击的存在,特别是在非交互式的零知识证明系统中,当证明者构造出对应的proof时,如不添加限制,一个合法的proof可以被多次重放以通过验证过程。

有些人可能会想既然如此,那么将Hash(proof)记录下来作为proofId,保证每个proofId只能使用一次,这样已经用过的proof就无法被重放了。需要注意的是采用这种做法的话必须首先确认系统中使用的证明协议的延展性,一些证明协议如Groth16不是simulation extractable,因此不满足non-malleability,如果你有用过zokrates来开发SNARK电路,在使用Groth16作为证明协议时也会给出Warning信息,提醒你查看文档中关于Groth16延展性的信息。这意味着取得一个合法的proof后,我们可以在它的基础上重新生成一个新的合法proof,那么我们前面生成proofId的方法在这种情况下就行不通了。关于利用Groth16的延展性生成新的proof的细节,可以查看下面的文章。

我也使用文中给出的两种方法简单写了个脚本,可以直接应用到zokrates的输出上,另一个常用工具circom的证明格式也是类似的。

使用其他一些支持non-malleability的协议如GM17等倒也能解决这个问题,不过安全性的提升往往意味着效率的削减,libsnark库中做了一个比较,可以看到相比于Groth16,GM17在证明的生成和验证上所需时间都会增加,因此实际应用中Groth16协议的应用依然是极为广泛的。

在仍然选用Groth16作为系统中选定协议的情况下,我们可以考虑其他方式来解决重放问题。与很多系统中解决重放攻击的方式类似,我们可以想办法为proof添加一个不重复的Nonce,使得构造的每个证明都只能生效一次,目前常见的零知识证明应用中通常使用名为nullifier的结构来实现这一目标,如果你有看过一些项目的源码或是它们的设计文档,应该也都见过类似的概念。著名的混币项目Tornado cash也在他们的白皮书中阐述了这一设计

其实对于nullfier的设计究竟该怎么做目前倒也没有什么标准的规范,大家根据自己的经验及实际的需要来生成对应的nullifier,在下面有人做了一个简单的总结

总的来说,你可以像Tornado cash那样为每个proof随机生成一个秘密的nullifier,公开它的hash,在证明中为其添加一个hash原象证明,使用hash值作为每个proof的唯一性标识符,或者是使用证明的部分输入来计算nullfier,主要目的就是保证不论是对于中间人或者是证明者自身,同样的输入不能构建出新的证明以重复使用。

事实证明,这种全凭开发者经验的设计还是比较容易出问题的,不久前StealthDrop项目的nullifier设计就被发现是存在问题的

他们使用一个ECDSA签名的hash来计算nullifier,对ECDSA比较熟悉的朋友应该都知道该算法是包含随机数的,并不是一种确定性签名算法,对于消息m的签名,签名者每次选取不同的随机数k得到的签名都是不同的,使用它来计算nullifier无疑会使得证明者可以针对消息值固定的消息值m无限次地重放proof,而这个系统的原本设计却可能是每个证明者亦即私钥的拥有者应只能针对m生成一个可用的proof。退几步讲,哪怕要以签名作为nullifier,至少也应该选择一个满足强不可伪造性(SUF-CMA)的签名方案,不然肯定会存在类似这样的延展性问题,在这个基础上还得保证签名编码格式的唯一性。

最终该项目的修复方案选择直接使用私钥和消息m的hash来计算nullifier,有意思的是本身其原始设计就是为了避免直接在生成证明时读取私钥,现在还是回到原点了。

此外,在一些论文里还能看见把时间戳放进电路的输入中来防止重放,检查验证时的时间是否对得上,不过这样也只能防止跨时间片下的重放,同一个时间片下仍然不受限制。

可以说各种奇怪的操作数不胜数,后面相关的应用发展起来感觉确实得有对应的设计规范来保证零知识应用的安全性。

考虑front running

在这一节我们来关注下零知识证明应用与区块链的结合,很多零知识证明应用的设计者可能对其使用的区块链系统本身的特性不甚了解,导致应用存在漏洞,有点类似于之前区块链上的智能合约兴起时,很多初入合约应用开发的开发者按照旧有的思维去写代码,结果出现各种各样的安全问题(虽然现在合约里的安全问题还是层出不穷

上一节我们已经讲到通过nullifier来确保每个proof只能使用一次,但同时我们还得确保该proof第一次使用也是由证明者触发的,因为当我们的应用部署到区块链中时,往往我们调用合约的交易都是公开的,也就是说我们的交易被打包进区块之前,交易内容便已经将proof内容泄露了,而此时nullifier还未生效,设想若我们的应用是一个类似于Tornado Cash的服务,在提款时提供有效的proof后,合约便会将提取的金额发送到msg.sender,此时攻击者即可直接窃取证明者的proof,提高gas price以实现抢跑,或者可能直接就被矿工给截胡了。

关于这样的抢跑交易front running的研究现在一般作为矿工可提取价值MEV的一部分,虽然问题实际上一直都存在,不过在前两年Defi的应用爆发后才真正得到社区的重视,现在以太坊网络上不知存在着多少交易机器人,构成了以太坊黑暗森林。

关于MEV能说的东西很多,现在社区也在积极的提供解决方案,比如PBS模式来提供抗审查交易的功能,一些矿池以前也提供了隐私mempool的服务,可以避免交易内容被整个网络窥探(可惜后来都相继关门了),以后有机会倒是可以聊聊这个话题。

言归正传,我们要在零知识应用中解决这个问题倒也没那么麻烦,只要将这个proof使用者的身份也绑定到proof中即可,就像上面我们提到的提款证明,可以在证明电路中添加msg.sender作为公开输入,这样即可实现用户身份与proof整体的绑定。

Tornado cash实际实现时也是在进行提款时将传入的取款地址作为证明电路的公开输入,并添加了一个简单的约束,从而将取款地址与整个证明进行绑定,哪怕被攻击者拿到proof也无法将取款地址替换掉

// Verifies that commitment that corresponds to given secret and nullifier is included in the merkle tree of deposits
template Withdraw(levels) {
    signal input root;
    signal input nullifierHash;
    signal input recipient; // not taking part in any computations
    signal input relayer;  // not taking part in any computations
    signal input fee;      // not taking part in any computations
    signal input refund;   // not taking part in any computations
    signal private input nullifier;
    signal private input secret;
    signal private input pathElements[levels];
    signal private input pathIndices[levels];

...
    // Add hidden signals to make sure that tampering with recipient or fee will invalidate the snark proof
    // Most likely it is not required, but it's better to stay on the safe side and it only takes 2 constraints
    // Squares are used to prevent optimizer from removing those constraints
    signal recipientSquare;
    signal feeSquare;
    signal relayerSquare;
    signal refundSquare;
    recipientSquare <== recipient * recipient;
    feeSquare <== fee * fee;
    relayerSquare <== relayer * relayer;
    refundSquare <== refund * refund;
}

当然,如何设计证明电路完全取决于应用的逻辑,比如以太坊上基于zk-SNARK的黑暗森林游戏中在电路中包含from坐标和to坐标,同时检查from坐标的拥有者是否是交易的发送者msg.sender,这样其他人拿到proof也没法利用,用以攻击目标星球,不过它们的电路中倒是没有添加nullifier的设计,这意味着当你拿下某颗星球后,有能力重放这颗星球的前任owner以该星球为起点构造的proof,我觉得这反而挺真实的。

就我目前看过的一些项目及论文而言,很多已经上线的零知识证明应用一般还是注意了proof与使用者的绑定关系,虽然目前而言使用零知识证明的应用程序还是比较少的,而很多论文里倒是没太注意这一点,一些论文里构造的proof与整个系统其实是有点脱节的,如果你有兴趣使用零知识证明作为工具构建你的Idea,那么在设计的时候希望能更多地考虑部署的平台的特性。

小结

写这篇文章的在某种程度上其实也是为了抛砖引玉,这几年零知识证明开始变得火热,可以看到很多研讨会和讲座都在讨论,学术界在不断改进已有的证明系统,并尝试将很多已有的密码学原语与其相结合,工业界也在不断努力提升效率,同时构建SNARK友好的hash算法签名算法,各种以zk-SNARK,zk-STARK,Bulletproof等证明系统构建的应用也越来越多,可能不久后基于零知识证明的应用也能出现几个爆款,毕竟其在隐私方面有着巨大的优势,而且可以完成很多很酷的事情。但是目前来说这一领域还是比较欠缺对应的安全规范,我在这里讲的也不过是一些显而易见的问题,还有更多坑隐藏在实际的应用当中,可能再过一段时间使用零知识证明的门槛越来越低,用户变多以后,这个领域的发展能添加更多的规范,对安全也能给予更多的重视。

很多关注这个方向的爱好者可能并不是搞安全的,懂的人很多也没空写这方面的东西,我就斗胆分享了一下最近接触这个方向的一些思考,总结了一下看的部分论文及项目中出现的问题,本来想写个零知识应用的安全设计指北,后来感觉标题起的有点大了,如果以后有机会继续深入的话希望自己能将这篇文章进行进一步的扩充吧。

Arweave TX
tsh6wpX-eG-Rnk2YpKZj-ULMGWgaBWyf9iN7wZxbuvQ
Ethereum Address
0xb06c20108d92Fd5fb4Ca4c05B14B3F326aAF887a
Content Digest
V9pqaI7l5U08yq-kRhL6kYcrpCALMYuxJQ3TP-Pa0iA