Cointime

Download App
iOS & Android

ZKP Series: Principles and Implementation of Extensibility Attacks on Groth16 Proofs

Preface

In our previous article, we reviewed the technical features of mainstream ZKP implementation solutions and mentioned the potential extensibility risks associated with certain ZKP algorithms. In this article, we will continue to demonstrate the attack principles and defense methods from a practical perspective.

Vulnerability Overview

Extensibility attacks on ZKP refer to the ability of an adversary to generate a new valid proof without knowledge of the witness, given an existing valid proof.

Not all proof systems are susceptible to extensibility attacks. In fact, this problem currently exists mainly in the Groth16 proof system. So why do we still insist on using Groth16, given that there are so many other proof systems available? The truth is that the proofs generated by Groth16 are extremely small in size and very fast to verify. In the context of blockchain, where computational costs are high, using Groth16 seems to be the most ideal choice.

What risks does extensibility vulnerability bring? Let’s imagine a deposit system that uses ZKP proofs submitted by users to verify their identity. Once verified, users can make withdrawals. Since the verification process of this system is public, anyone can obtain the proof. If the proof value itself is used as a withdrawal record and the proof is obtained and transformed, it can be used for multiple withdrawals. The exploitation of this vulnerability depends on the specific scenario, but we can see that extensibility vulnerability primarily brings the risk of double-spending.

Mathematical Principles

To understand the attack principles, we first need to understand the algorithm, which requires some knowledge of cryptography. Interested readers can find information on the Groth16 algorithm on their own. Here, we will focus on the root cause of the vulnerability: the verification function.

Let’s take a look at the formula for the verification function:

Without going into a detailed explanation of each individual variable, it may be difficult to fully comprehend the formula’s meaning. However, an extensive introduction is not necessarily required. By simply remembering the “A * B” on the left side of the formula, we can begin to unravel its intricacies and apply mathematical magic. The following incantation is all it takes:

This is just one of the simpler construction methods, and there is another construction method, which we will not elaborate on here, as we have already gathered what we needed.

Implementation

With the above formula, we can execute the extension of Groth16 proofs in implementation. To forge a proof for a target object, we can obtain its proof, for example:

{  pi_a: [    '17566212007750634279332191898019870443899908963707812937725971557556988121113',    '13653824972036797689593667463260040326059024360787769597142078414930263663703',    '1'  ],  pi_b: [    [      '14906111038352923510344648516413952434168552622848767570599399834157918236589',      '15289017543994496306320102143103349779456992442925111629326024552687168229256'    ],    [      '18841235948006283310515755114762069779103481848435391875780416574913227842443',      '6835281862874020275059416795628130939104366467185014410026268177455413514889'    ],    [ '1', '0' ]  ],  pi_c: [    '21641806348662631815866837255154640732047306895903168385641666607914783128458',    '2082587994352117459125871298218148663854896572836176277773049196516560449682',    '1'  ],  protocol: 'groth16',  curve: 'bn128'}

Let’s take a look at a proof like this: pi_a, pi_b, pi_c are the A, B, C described in the formula above. This proof uses the BN128 curve, so we need to find a development library that supports the BN128 curve. Here, we choose ffjavascript, which is a finite field library based on JavaScript that supports the BN128 and BLS12381 curves.

First, we arbitrarily construct an element on the field and its inverse element:

const X = F.e("123456");const invX = F.inv(X);

Then, we multiply them together separately. The core code is as follows:

const A = curve.G1.fromObject(proof.pi_a);const B = curve.G2.fromObect(proof.pi_b);new_pi_a = curve.G1.timesScalar(A, X);  //A'=x*Anew_pi_b = curve.G2.timesScalar(B, invX);  //B'=x^{-1}*B

Finally, we replace the original proof with new_pi_a and new_pi_b to obtain a new proof:

{  pi_a: [    '6515337738552169645617263495374285821912767490069335826295120714428977813009',    '10671874016637483602721966808912960491553808325993800847672325376634242358838',    '1'  ],  pi_b: [    [      '20523135654483520737281403147507843211011765855706506084021355785019229409285',      '4032527486736971273144842057682931136787425732029780739716144011227563817375'    ],    [      '9389285843105460816015935120908213706233585149018458753845466963847282799614',      '7207137211649923819130654483456848273137049778520784010268635580504303221849'    ],    [ '1', '0' ]  ],  pi_c: [    '21641806348662631815866837255154640732047306895903168385641666607914783128458',    '2082587994352117459125871298218148663854896572836176277773049196516560449682',    '1'  ],  protocol: 'groth16',  curve: 'bn128'}

By this point, we have successfully constructed a new proof. When we place this proof into the verification function, we can see that it can pass the verification.

Prevention

How can we prevent Groth16 extensibility attacks? Here are four methods:

  1. Sign the proof, and have the verifier validate the signature along with the proof.
  2. Add nullifier values in the public inputs of the circuit, as TornadoCash does, to ensure that a proof can only correspond to a public input once.
  3. Add the identity information of the prover (such as Ethereum’s msg.sender) to the public inputs of the circuit, allowing the verifier to verify the prover’s identity.
  4. Use other proof systems, as discussed in our previous article.

Conclusion

In conclusion, Groth16 is vulnerable to extensibility attacks, as new proofs can be forged through simple calculations. In practice, it is important to take measures to prevent double-spending attacks.

Comments

All Comments

Recommended for you

  • Decentralized AI project GaiaNet completes $10 million seed round of financing

    Decentralized AI project GaiaNet has completed a $10 million seed round of financing, with participation from EVM Capital, Mirana Ventures, Mantle EcoFund, Generative Ventures' Lex Sokolin, and Republic Capital's Brian Johnson. According to a statement released on Tuesday, the newly raised funds will support GaiaNet in developing educational tools for STEM students and in using distributed ledger technology to decentralize the AI network.

  • Oracle protocol Switchboard completes $7.5 million Series A financing

    On May 28th, Switchboard, a prophecy machine protocol, announced the completion of a $7.5 million Series A financing round. This round of financing was led by Tribe Capital and RockawayX, with participation from Mysten Labs, InfStones Global, OtterSec, Bixin Ventures, and various angel investors.

  • RWA stablecoin issuer Anzen Finance raises $4 million in seed funding

    Anzen Finance, the issuer of the stablecoin RWA, has raised $4 million in seed funding from companies such as Mechanism Capital, Circle Ventures, Frax, and Arca. The company aims to use the new funding to expand support for USDz in blockchain and protocols, and to broaden the ways in which users can earn rewards using the token.

  • BTC falls below $68,000

    The market shows BTC has fallen below $68,000, currently trading at $67,998.99, with a daily decline of 1.05%. The market is volatile, please manage your risks.

  • SocialFi infrastructure OpenSocial completes $5 million in financing

    SocialFi infrastructure OpenSocial Protocol announced the completion of a $5 million seed round of financing, led by Portal Ventures and SNZ Capital, with participation from Animoca Brands, Awesome People Ventures, Arche Fund, Decima Fund, Moonrock Capital, OKX Ventures, Orange DAO, Panony Group, Summer Ventures, and others.

  • BONK breaks through $0.0000435

    According to market data, BONK has broken through 0.0000435 US dollars and is currently trading at 0.00004335 US dollars, with a 24-hour increase of 16.32%. The market is volatile, please be cautious with risk management.

  • Arkham: Mt.Gox has moved its Bitcoin holdings to 3 new wallets

    Mt.Gox's Bitcoin holdings have been transferred to three new wallets in the past hour, as monitored by Arkham. All wallets received their first test transaction about four hours ago. Each address contains 47,230 BTC.

  • The gap between BlackRock and Grayscale’s Bitcoin holdings has narrowed to less than 2,000 BTC

    The gap between BlackRock and Grayscale's Bitcoin holdings has further narrowed, currently to less than 2,000 BTC. According to official data, as of May 24th, Grayscale's Bitcoin ETF GBTC held 289,040.5264 BTC (worth approximately $20,002,254,770.20), while BlackRock's holdings during the same period were 287,167.7407 BTC (worth approximately $19,794,802,610.26), with a difference of only 1,872.7857 BTC and a market value difference of approximately $200 million.

  • Mt. Gox confirms multiple transactions today were intended to prepare repayments to creditors ahead of the October 31 deadline.

    On May 28th, according to a screenshot shared on X platform by Cointelegraph, Mt. Gox confirmed that multiple transactions conducted today were in preparation for repayment before the October 31st deadline for creditors.In the letter, Mt. Gox stated: "As per the rehabilitation plan, the rehabilitation trustee is preparing to make repayments to the rehabilitation creditors in the form of cryptocurrency. This repayment method means that rehabilitation creditors can choose to (i) receive bitcoin and bitcoin cash (BCH) on behalf of the rehabilitation creditors through specified cryptocurrency exchanges, or (ii) make repayments through the proceeds from the sale of bitcoin and BCH. Recently, the rehabilitation trustee has received inquiries/deep concerns regarding the management of bitcoin and BCH. However, at present, the rehabilitation trustee has neither made repayments through the specified cryptocurrency exchanges mentioned in (i) above nor sold bitcoin and BCH to make repayments as mentioned in (ii) above. The rehabilitation trustee is currently managing bitcoin and BCH in a secure manner. Please wait for a while until repayments are made as the rehabilitation trustee is preparing for the above repayments."

  • Bloomberg: Russian companies turn to cryptocurrencies for commodity trading

    On May 28th, at least two top Russian metal producers have started using Tether Holdings' stablecoin and other cryptocurrencies to settle some of their cross-border transactions with suppliers. The company's executives declined to reveal their identities as the information is not public. In some cases, settlements are made through Hong Kong.