Beosin硬核研究 | 3种针对ZK基础算法Groth16的攻击手法分享

本文作者：Beosin安全研究专家Saya

本篇文章依然是Beosin带给大家的硬核安全研究系列文章，今天我们来为大家讲解3种针对ZK基础算法Groth16的攻击手法。

1. 什么是延展性攻击？

2014年MT.GOX交易所安全事件（也被称为“门头沟事件”），遭受了比特币上的交易延展性攻击(Transaction malleability attack)，造成了约85万枚比特币的损失。此次攻击的具体过程如下：攻击者首先在MT.GOX发起一笔提现交易A，接着在交易A被确认之前通过篡改交易签名，使得标识一笔交易唯一性的交易哈希发生改变，生成伪造的交易B。

如果交易B比A先被矿工打包记录到比特币账本中，那么后续矿工在打包交易A的时候会因为B已经使用了同样的UTXO而认为A存在双花问题，从而拒绝打包A。最后，攻击者向交易所申诉未收到代币，交易所会根据交易A去链上查询交易状态，发现提现交易确实未成功后会再次向攻击者转账，造成交易所资金流失。这种延展性攻击并未改变交易内容本身，而仅仅是改变了交易签名。

比特币的延展性攻击是椭圆曲线ECDSA签名算法存在的漏洞，比特币通过校验交易id是否已经存在，防止由于交易重放导致的双花攻击。而交易id是由交易内容的哈希自动生成，所以如果交易签名sigscript改变，则交易id也会随之改变，因此攻击者通过反转签名中的S值之后，可以伪造出另一个合法签名。但是这种攻击方式，无法改变交易的输入和输出。比特币在BIP-141中提出了隔离见证这一方案，通过将交易签名存储在witness中，不再置于交易数据中，可以防范该攻击并达到扩容的目的。

这种由于算法设计本身造成的延展性安全问题，在zk算法Groth16中同样存在，今天我们将为大家详细介绍Groth16 证明延展性攻击。

2. Groth16算法

Groth16算法是使用最广泛的zk-SNARKs(Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)的非交互式零知识证明方案之一。相比于其他的zk-SNARKs算法，其生成的证明尺寸更小，验证速度更快，因此被应用到如Zcash、celo等项目中。下图列举了常见的zk算法：

https://medium.com/coinmonks/comparing-general-purpose-zk-snarks-51ce124c60bd

2.1 Groth16算法概述

通常一个zk-SNARKs零知识证明的DApp开发过程分为以下几个步骤，首先项目方会将业务逻辑抽象生成数学表达式，接着将其转化为R1CS描述的电路。

但是由于R1CS只能依次验证电路中的各个逻辑门，这种做法非常低效，所以zk-SNARKs算法将其转化为QAP电路，也就是将R1CS中用向量表示的约束转换为插值多项式，再生成可以在链下密码库或者链上合约中验证的证明，最后根据电路生成的验证合约将对生成的证明进行合法性校验。

https://docs.circom.io/

其中，Groth16算法作为一种zk-SNARKs算法，同样涉及到零知识证明电路，其二次算术电路的约束关系为：

1 有限域F：包含有限个元素的域，该域满足以下几个特质：

1. 封闭性：若有限域中的任意两个元素  ，那么  和  也属于该有限域

2. 结合律：若任意  ，则有：

3. 交换律：若任意  ，则有：  

2 aux：附加信息

3    阶数

4 多项式  ，  ，  ：Groth16在可信设置中生成的第三方参数，用于生成证明

5 多项式  ：R1CS规定电路需满足  ，所以对于一组  ，有  成立。但是R1CS需要依次检查上述m组约束。即，如果电路需满足10个条件，R1CS即使检查了前面9个约束，最后一个约束仍有可能出错，导致整个电路不能成立，这导致每次校验必须完成所有的10个约束。而QAP则将该问题转化为多项式问题，即若  都能使式子成立，则等价于多项式  是  的解，即  可以整除  ，这样可以一次性校验完所有的约束。

需要注意的是，仅当  时，其左右两个多项式计算出的值才相等，而不是指多项式方程本身成立，即在其他点上  。因此在实际的计算中为了得到更准确的结果，通常不会仅使用上述m个点生成多项式，所以Groth16算法的核心方程如下：

Groth16算法就是为了证明Prover知道一组多项式的解witness即  h(x)满足上式。

2.2 可信设置

由于Groth16算法在椭圆曲线域上进行计算，域上的值是一个个坐标点，那么如何使用坐标点表示多项式呢？这就需要使用椭圆曲线配对。关于椭圆曲线配对这里简单介绍一个例子，更为具体的解释请参考V神的博客:

https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627。

在有限循环群中(能由单个元素生成的群)，如果  且  ，就称  是一个  对，那么点  也是一个   对，且在实际计算中该点对应一个唯一的多项式  ，这样我们就能用  对表示多项式了。同时，假设存在一组  对  ，那么要生成新的  对  就必须知道一组系数  使得  ，  。

因为简单的配对不适用于密码学，所以可信设置会首先选取一组随机数   ，并计算出隐式包含  对的一组多项式，最终生成一个公共参考字符串(CRS) σ，并将σ分为σ1和σ2两部分，分别为Prover和Ver­i­fier使用，具体计算如下：

2.3 Prover生成证明

Groth16中证明的生成和验证都与双线性配对有关，双线性配对是在不暴露系数的情况下，证明椭圆曲线配对是否正确的方法。Groth16中使用的双线性配对包含三个椭圆曲线群，分别是  。其中，三个群的椭圆曲线方程都为：  ，但是  在  的扩展域上，满足映射  ，具体性质如下：

假设对任意的  ，有：

上述式子代表在满足双线性映射的情况下，可以将系数单独取出，所以假设需要验证  中的点  是否为  对时，仅需知道  中的一个  对  ，即可通过下列式子验证点P是否是  对：

Groth16算法中使用的配对更为复杂，涉及到多个配对，本文将不再介绍。综上，Prover根据选取的两个随机数  计算出商  ，并使用可信设置中生成的公共字符串σ1，通过双线性配对生成对应的证明Proof π = ([A]1,[C]1,[B]2)，具体计算过程如下：

生成的证明如下图所示：

2.4 Ver­i­fier验证证明

根据Groth16中使用的双线性配对，Verifier接收到证明π[A、B、C]后验证如下方程：

如果等式成立，则代表证明验证成功。

实际的项目验证过程中，还有第三个参数public_inputs，该参数是电路的一组输入称为statement，因为Prover和Verifier需要对计算和验证的证明有一个数据共识，即针对哪一组实际的数据生成证明并验证。

3. Groth16 算法延展性攻击

由于验证方程只要左右两式相等即可通过校验，则可将证明中的A、B、C伪造为A‘、B’、C‘：

其中，  代表  上的某个证明  ，同理  代表  上对应的证明  ,根据计算式的不同，共有如下两种证明伪造方式。

3.1 乘法逆元构造法

乘法逆元是指对于群  中的任意元素  ，  中都存在另一个元素$b$，使得下列式子成立：

其中e指的是单位元，实数域中该值为1。举一个简单的例子说明乘法逆元，即在平常的实数域中，3的逆元就是  。在Groth16算法中假设在有限域  上选取一个随机数  ，并计算其逆元  ，并伪造对应的证明A‘、B’、C‘：

由于在有限域上进行计算，所以满足交换律和结合律，具体的推导过程如下：

根据验证方程，计算出的  结果与原始验证方程的结果一致，因此同样可以通过校验。这种构造方式较为简单，x必须是  域上的元素，可以伪造出多个证明。

3.2 加法构造法

同样地，可以根据加法构造如下伪造的证明A‘、B’、C‘，其中  是  域上的随机数，  是可信设置参数，可以从verification_key中获取。可信设置生成的参数不同的库采取的方式不同，一些存储在一个单独的json文件中，一些存储在链上的合约中，但是都是可以获取到的公开参数。

具体的推导过程如下：

根据验证方程，计算出的  结果与验证方程中右式一致，因此同样可以通过校验，这种方式同样可以构造出多个伪造证明。

3.3 合并构造法

上述两种伪造证明的构造方式可以合并为下列表示式：

在ark代码库中已经有对应实现：

/// Given a Groth16 proof, returns a fresh proof of the same statement. For a proof π of a
/// statement S, the output of the non-deterministic procedure `rerandomize_proof(π)` is
/// statistically indistinguishable from a fresh honest proof of S. For more info, see theorem 3 of
/// [\[BKSV20\]](https://eprint.iacr.org/2020/811)
pub fn rerandomize_proof(
        vk: &VerifyingKey<E>,
        proof: &Proof<E>,
        rng: &mut impl Rng,
    ) -> Proof<E> {
        // These are our rerandomization factors. They must be nonzero and uniformly sampled.
        let (mut r1, mut r2) = (E::ScalarField::zero(), E::ScalarField::zero());
        while r1.is_zero() || r2.is_zero() {
            r1 = E::ScalarField::rand(rng);
            r2 = E::ScalarField::rand(rng);
        }

        // See figure 1 in the paper referenced above:
        //   A' = (1/r₁)A
        //   B' = r₁B + r₁r₂δ
        //   C' = C + r₂A

        // We can unwrap() this because r₁ is guaranteed to be nonzero
        let new_a = proof.a.mul(r1.inverse().unwrap());
        let new_b = proof.b.mul(r1) + &vk.delta_g2.mul(r1 * &r2);
        let new_c = proof.c + proof.a.mul(r2).into_affine();

        Proof {
            a: new_a.into_affine(),
            b: new_b.into_affine(),
            c: new_c.into_affine(),
        }
    }

4. 总结

本篇文章主要介绍了Groth16算法相关的基本概念、密码学基础和主要算法流程，以及重点展示了三种Groth16算法延展性攻击的攻击向量构造方法。

接下来的文章，我们将通过对 Groth16 算法常见的密码库实现攻击演示，来进一步展示验证性攻击。欢迎继续关注Beosin的后续文章。

Beosin作为一家全球领先的区块链安全公司，在全球10多个国家和地区设立了分部，业务涵盖项目上线前的代码安全审计、项目运行时的安全风险监控、预警与阻断、虚拟货币被盗资产追回、安全合规KYT/AML等“一站式”区块链安全产品+服务，目前已为全球3000多个区块链企业提供安全技术服务，审计智能合约超过3000份，同时，Beosin也提供上币项目的安全评估以及提供符合各地监管要求的合规评估、VaaS自动化上币审计服务、交易所渗透服务、交易所安全建设咨询服务等安全解决方案。欢迎点击公众号留言框，与我们联系。

参考链接：

https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd

https://eprint.iacr.org/2016/260.pdf

 近期热点文章阅读：