比特幣的延展性攻擊是橢圓曲線 ECDSA 簽名演算法存在的漏洞，比特幣通過校驗交易 id 是否已經存在，防止由於交易重放導致的雙花攻擊。
作者： Saya，Beosin 安全研究專家
封面： Photo by Shubham Dhage on Unsplash
本篇文章依然是 Beosin 帶給大家的硬核安全研究系列文章，今天我們來為大家講解什麼是 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 演演算法：
2.1 Groth16 算法概述
通常一个 zk-SNARKs 零知识证明的 DApp 开发过程分为以下几个步骤，首先项目方会将业务逻辑抽象生成数学表达式，接着将其转化为 R1CS 描述的电路。
但是由于 R1CS 只能依次验证电路中的各个逻辑门，这种做法非常低效，所以 zk-SNARKs 算法将其转化为 QAP 电路，也就是将 R1CS 中用向量表示的约束转换为插值多项式，再生成可以在链下密码库或者链上合约中验证的证明，最后根据电路生成的验证合约将对生成的证明进行合法性校验。
其中，Groth16 算法作为一种 zk-SNARKs 算法，同样涉及到零知识证明电路，其二次算术电路的约束关系为：
Groth16 算法就是为了证明 Prover 知道一组多项式的解 witness 即 h(x) 满足上式。
2.2 可信设置
2.3 Prover 生成证明
Groth16 算法中使用的配对更为复杂，涉及到多个配对，本文将不再介绍。综上，Prover 根据选取的两个随机数 计算出商 ，并使用可信设置中生成的公共字符串σ1，通过双线性配对生成对应的证明 Proof π = ([A]1,[C]1,[B]2)，具体计算过程如下：
生成的证明如下图所示：
2.4 Verifier 验证证明
根据 Groth16 中使用的双线性配对，Verifier 接收到证明π[A、B、C] 后验证如下方程：
如果等式成立，则代表证明验证成功。
实际的项目验证过程中，还有第三个参数 public_inputs，该参数是电路的一组输入称为 statement，因为 Prover 和 Verifier 需要对计算和验证的证明有一个数据共识，即针对哪一组实际的数据生成证明并验证。
3. Groth16 算法延展性攻击
由于验证方程只要左右两式相等即可通过校验，则可将证明中的 A、B、C 伪造为 A‘、B’、C‘：
其中， 代表 上的某个证明 ，同理 代表 上对应的证明 , 根据计算式的不同，共有如下两种证明伪造方式。
3.1 乘法逆元构造法
3.2 加法构造法
同样地，可以根据加法构造如下伪造的证明 A‘、B’、C‘，其中 是 域上的随机数， 是可信设置参数，可以从 verification_key 中获取。可信设置生成的参数不同的库采取的方式不同，一些存储在一个单独的 json 文件中，一些存储在链上的合约中，但是都是可以获取到的公开参数。
具体的推导过程如下：
根据验证方程，计算出的 结果与验证方程中右式一致，因此同样可以通过校验，这种方式同样可以构造出多个伪造证明。
3.3 合并构造法
上述两种伪造证明的构造方式可以合并为下列表示式：
/// 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-9f857b0dcafdhttps://eprint.iacr.org/2016/260.pdf
免責聲明：作為區塊鏈資訊平臺，本站所發佈文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。 本文內容僅用於資訊分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
