Full Report
Halo2 is a zero-knowledge (ZK) proof framework based on the PLONK protocol that was originally used for Zcash. Circuits, the flow of operations and verification in a ZK proof, are structured as tables. In these tables, each column holds a sequence of values and each row represents a step in the computation. Constraints, or the limits of the circuit, are defined by querying values in these columns at specific offsets, known as Rotations. Each column is encoded as a polynomial over a finite field. Querying a column at a certain Rotation corresponds to evaluating the value at a specific point. Constraints among columns are enforced using gates. The prover commits the columns using polynomial commitment schemes like KZG. The verifier will receive these commitments and verify it for correctness via black magic math. Circuits have multiple columns and gates, resulting in the evaluation of polynomials at multiple commitment openings. To make this efficient, Halo2 uses a multi-point opening technique, allowing for the verifier to batch many queries into a single proof. In practice, they batch the evaluations, compute a linear combination of all values and check a single equation to ensure it's been satisfied. Alright, enough of the math! What's the vulnerability!? The multi-point opening system encodes the data as Commitment,QueryPoint as the key and to a Value. This key isn't unique enough! It's possible for a "query collision" to occur, where two independent queries have the same key, even if their values are expected to be different. In the context of Halo2, the consequence is horrible: one evaluation can silently overwrite the other. This means that it's possible to forge proofs in many situations. From what I can gather, this vulnerability appears to be somewhat theoretical as no live protocols could have been exploited. Regardless, the bug was super cool and entertaining to look at, even though I don't fully understand ZK math.
Analysis Summary