值得信赖的区块链资讯!
比推数据  |  比推终端  |  比推英文  |  比推 APP  | 

下载比推 APP

值得信赖的区块链资讯!
iPhone
Android

零知识证明 – zkHack挑战赛第五名

星想法

zkHack算是这几年举办的比较有意思的零知识证明技术挑战的活动。整个活动由六道零知识证明的题目组成,每周三的北京时间凌晨3:00左右公布一道新题目。每一道题目在公布之前会提供相应的背景资料,参与者有一周左右的时间解题。

Trapdoor Tech团队顺利完成六道题目,获得第3题第二名,总体第五名的成绩。

图片

Trapdoor Tech团队在解题后都会提交完整的解题思路。完整的解题思路可以从zkHack的网站查询。总结回顾一下每条题目的解题心得,分享给感兴趣的小伙伴:

第1题:Let's Hash it Out – https://www.zkhack.dev/puzzle1.html

第一题是个签名设计的问题。椭圆曲线的离散对数问题,保证在知道椭圆曲线点的情况下,无法推算出scalar。问题出在hash_to_curve的函数,只是按照hash的bit位进行椭圆曲线点的叠加。又因为椭圆曲线支持同态加计算,整个签名的计算过程可以看成是256个椭圆曲线点的0/1线性叠加。问题就转换成,需要求解256个椭圆曲线点。从题目给出的256个已知hash以及对应的签名结果,可以求解方程。

第2题:Group Dynamics – https://www.zkhack.dev/puzzle2.html

第二题是个有趣的题目。众所周知,椭圆曲线的子群上的点计算具有离散对数问题。深入一点看,这个子群有限制条件:子群的阶是质数,不能因子分解。如果某个子群的阶可以因子分解,则在这些因子上可以通过枚举的方法获取对应的scalar,并通过中国剩余定理(CRT)获取最初的子群上的阶。这条题目告诉大家,不能只看曲线的定义, 还需要检查曲线上的点是否在合适的子群上。

第3题:Double Trouble – https://www.zkhack.dev/puzzle3.html

第三题需要一些想象力。该题设计的零知识证明系统本身没有问题。但是,为了加强Prover的计算性能,本来需要采用随机数的地方,简单的采用了之前证明计算的中间结果:没有完整的计算随机Scalar对应的Perdersen承诺,而是用之前计算的承诺值进行“Double”。这个Double操作是问题所在。该题目告诉大家,即使零知识证明系统设计没有问题,计算过程也需要多加小心,如果两个证明之间存在一些逻辑关系,有可能存在一些漏洞。

第4题:Hidden in plain sight- https://www.zkhack.dev/puzzle4.html

第4题的基础是多项式承诺KZG算法。承诺的设计采用了盲化多项式,但是这个盲化多项式是2阶,也就是这个盲化多项式有两个多形式系数。题目给出了两个挑战以及两个挑战对应的多项式的值,从而可以求解盲化多项式的系数,确定整个多项式的系数。

第5题:To be Adaptive is to be Strong – https://www.zkhack.dev/puzzle5.html

第5题涉及到Fiat-Shamir算法。这个算法可以将交互式的挑战转化为非交互式的挑战。该算法在零知识证明系统中大量运用。该算法实现了随机预言机,需要满足如下两个条件:1/ 每一次的不一样的查询返回随机数据 2/ 针对同样的查询返回同样的数据。只有在这样的前提下,这种非交互式的算法才是安全的。题目中的Fiat-Shamir算法的应用破坏了第一个条件,对于不一样的查询也返回了同样的数据。也就是说,采用Fiat-Shamir算法需要对挑战有关的所有数据进行hash计算,并不能只对其中的部分进行hash计算。

第6题:Soundness of Music – https://www.zkhack.dev/puzzle6.html

第6题如果没有背景资料的话,其实是比较难的。解题原理和很早之前的Zcash的一个漏洞有关。简单的说,在零知识证明系统的可信设置中如果增加了一些“多余”信息,也可能对整个证明系统带来漏洞。该题的背景资料中的论文给出了这个漏洞的清晰的解释,感兴趣的小伙伴可以直接查看论文。有趣的是,这条题目本身还有另外一个解法。在证明验证的实现中,并没有验证椭圆曲线的点是否有效。

总结:

zkHack是个有趣的零知识证明技术挑战的活动。参与者需要在六周内解答六道题目。Trapdoor Tech获得第3题第二名,总体第五名的成绩。zkHack中的每一道题目都是零知识证明系统设计和开发者需要注意的问题:可信设置的多余信息,挑战信息不正确,椭圆曲线的点的合法性,多个证明之间存在逻辑关系等等。建议对零知识证明系统感兴趣的小伙伴可以仔细查看每道题目,并上手做题。

说明:比推所有文章只代表作者观点,不构成投资建议
原文链接:https://www.bitpush.news/articles/2046483

比推快讯

更多 >>

下载比推 APP

24 小时追踪区块链行业资讯、热点头条、事实报道、深度洞察。

邮件订阅

金融科技决策者们都在看的区块链简报与深度分析,「比推」帮你划重点。