In 2014, MT.GOX exchange claimed to have suffered from a transaction malleability attack on Bitcoin, resulting in a loss of approximately 850,000 BTCs. The attack proceeded as follows: The attacker initiated a withdrawal transaction A on MT.GOX and then manipulated the transaction signature before transaction A was confirmed. By altering the signature, which is used to identify the uniqueness of a transaction's hash, the attacker generated a forged transaction B. If transaction B was included in the Bitcoin ledger by miners before transaction A, subsequent miners packaging transaction A would see it as a double-spending issue, as transaction B had already used the same unspent transaction output (UTXO). As a result, they would refuse to include transaction A. Finally, the attacker would file a complaint with the exchange, claiming non-receipt of funds. The exchange, upon checking the transaction status on the blockchain using transaction A, would find that the withdrawal transaction indeed failed and would proceed to transfer funds to the attacker, resulting in financial loss for the exchange. This type of malleability attack does not alter the content of the transaction itself but only changes the transaction signature.
The transaction malleability attack in Bitcoin is a vulnerability in the Elliptic Curve Digital Signature Algorithm (ECDSA). Bitcoin prevents double-spending attacks caused by transaction replay by verifying whether the transaction ID already exists. The transaction ID is generated from the hash of the transaction content. Therefore, if the transaction signature (sigscript) is modified, the transaction ID will also change. By manipulating the S value in the signature, the attacker can forge another valid signature. However, this attack method cannot alter the transaction inputs and outputs. Bitcoin introduced the Segregated Witness (SegWit) solution in BIP-141, which stores transaction signatures in the witness section instead of the transaction data itself, effectively mitigating this attack and achieving scalability.
This inherent malleability security issue, caused by algorithmic design, is also present in the zk-SNARK algorithm Groth16.
Groth16 algorithm is one of the most widely used non-interactive zero-knowledge proof solutions for zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge). Compared to other zk-SNARKs algorithms, it produces smaller proof sizes and offers faster verification speeds. As a result, it has been applied in projects such as Zcash and Celo. The following diagram lists common zk algorithms:
https://medium.com/coinmonks/comparing-general-purpose-zk-snarks-51ce124c60bd
Typically, the development process of a zk-SNARK DApp involves several steps. Firstly, the project abstracts the business logic and translates it into a mathematical expression. Then, this expression is converted into a circuit described in R1CS (Rank-1 Constraint System) format. However, R1CS can only sequentially verify each logical gate in the circuit, which is highly inefficient. Therefore, the zk-SNARKs algorithm transforms it into a QAP (Quadratic Arithmetic Program) circuit. This involves converting the constraints represented as vectors in R1CS into interpolation polynomials. The resulting proof can be verified using off-chain cryptographic libraries or on-chain smart contracts. Finally, the generated proof is validated for its legitimacy using a verification contract based on the circuit.
In the Groth16 algorithm, which is a zk-SNARKs algorithm, it also involves zero-knowledge proof circuits. The constraints of its quadratic arithmetic circuit are as follows:
Closure: If any two elements of the finite field $a、b\in F_{q}$，then $a+b$ and $a\cdot b$ also belong to the finite field.
Associativity：If any $a、b、c\in F_{q}$，then:
$(a+b)+c=a+(b+c)$、$(a\cdot b)\cdot c = a \cdot(b \cdot c)$
Commutativity: If any $a、b、c\in F_{q}$，then: $a+b=b+a，a \cdot b=b\cdot a$