Write-up for ZK Hack III puzzle #3: Bigger is Better

zkhack2022_III_puzzle3_writeup.md

Write-up for ZK Hack III puzzle #3: Bigger is Better

• Author: Nicolas IOOSS
• Date: 2022-12-12
• Puzzle: https://zkhack.dev/zkhackIII/puzzleT3.html, https://github.com/ZK-Hack/puzzle-bigger-is-better

1. Subject

The GitHub repository contains this introduction.

Bob was catching up on the latest in zkSNARK research, and came across the Vampire paper. In that paper, he found a reference to an inner-product commitment scheme, which allows committing to a vector and later proving that its inner-product with another (public) vector is equal to a claimed value. Bob was intrigued by this scheme, and decided to implement it in Rust.

Bob was delighted with the performance of the resulting implementation, and so decided to deploy it. The scheme requires a universal Powers-of-Tau-type trusted setup, and so Bob generated a SRS using an MPC ceremony.

Things were going smoothly for a while, but then Bob received an anonymous email that contained a full break of the scheme! Unfortunately for Bob, the email didn't contain any details about the break. Can you help Bob figure out the issue, and fix his scheme?

This puzzle is about a Zero-Knowledge protocol which proves that the inner-product of a secret vector with a public one is equal to a claimed value. This protocol is implemented in a ILV trait in src/algorithms.rs (named after the authors Izabachène, M., Libert, B., Vergnaud, D. of the paper Block-wise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes). This file also includes a test named test_ilv which shows how the functions can be used.

• This test starts by randomly generating two vectors of 512 elements

let mut rng = ark_std::test_rng();
let dim = 512;
let a = (0..dim).map(|_| Fr::rand(&mut rng)).collect::<Vec<_>>();
let b = (0..dim).map(|_| Fr::rand(&mut rng)).collect::<Vec<_>>();

• Then it loads a Structured common Reference String (SRS) from a binary file ck.srs.

let ck = CommitmentKey::<Bls12_381>::deserialize_unchecked(crate::SRS).unwrap();

• This SRS contains a Commitment Key (CK), which structure is defined in src/data_structures.rs.

#[derive(CanonicalSerialize, CanonicalDeserialize, PartialEq, Eq)]
pub struct CommitmentKey<E: PairingEngine> {
    /// The powers [beta^0 * G, beta^1 * G, ..., beta^n * G]
    pub powers_of_beta_g_first: Vec<E::G1Affine>,
    /// The powers [beta^{n + 2} * G,  ..., beta^{2n} * G]
    pub powers_of_beta_g_second: Vec<E::G1Affine>,
    /// The powers [beta^0 * H, beta^1 * H, ..., beta^n * H]
    pub powers_of_beta_h: Vec<E::G2Affine>,
}

• This Commitment Key is used to commit the first vector and to generate a proof.

let cm = ILV::commit(&ck, &a);
let proof = ILV::open(&ck, &a, &b);

• The test then verifies that the proof is valid.

let inner_product = a.iter().zip(b.iter()).map(|(&a, b)| a * b).sum::<Fr>();
assert!(ILV::verify(&ck, &cm, &b, inner_product, &proof));

Function main creates an Attack object and calls assert_attack_works from src/attack.rs which calls the same ILV::commit and ILV::verify functions. But assert_attack_works has two major differences with test_ilv:

• It generates vector b from a deterministic random number generator which takes the commitment of a as input. This looks like a Fiat–Shamir heuristic to prevent the prover from cheating in a non-interactive setup.
• It also compares a field named claimed_inner_product with the actual inner-product of a and b and fails if they are equal.

So the puzzle consists in crafting a valid proof which states that the inner-product of vectors a and b is some value different from the actual one. To understand how to solve it, we first need to go into the details of the proving system.

2. Polynomial-Based Proof

Let's introduce some mathematical notations. The puzzle is about the inner-product of two vectors of the same dimension $n$: $a = (a_0, a_1... a_{n-1})$ and $b = (b_0, b_1... b_{n-1})$. The elements of these vectors are in a finite field $\mathbb{F}_r$ of order $r$. This field is the scalar group of a pairing-friendly curve $E$ which uses two groups $\mathbb{G}_1$ and $\mathbb{G}_2$. Each of these groups has a generator point: $G \in \mathbb{G}_1$ and $H \in \mathbb{G}_2$. The order of these points is $r$. The curve is associated with a pairing function $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ where $\mathbb{G}_T$ is the group of the $r$-th roots of unity of a finite field.

The puzzle uses these generic notations when defining the algorithm of the protocol (for example E::Fr in src/algorithms.rs is the type which represents an element of $\mathbb{F}_r$). It also uses a specific setup with the BLS12-381 curve for the attack in src/main.rs, implemented in Rust's crate ark_bls12_381.

The inner-product of $a$ and $b$ is:

$$a \cdot b = \sum_{i=0}^{n-1} a_i b_i$$

To commit $a$, ILV::commit performs two steps:

• Convert the elements $a_i$ to big integers with method Fr::into_repr.
• Combine these integers with some points from the Commitment Key with function VariableBaseMSM::multi_scalar_mul. Even though this function is not documented in arkworks 0.3.0, we can guess that it performs a Multi-Scalar Multiplication between points and integers.

What does the Commitment Key contain? Its definition in src/data_structures.rs contains some helpful comments:

• ck.powers_of_beta_g_first contains $(\beta^0 G, \beta^1 G..., \beta^n G)$ in $\mathbb{G}_1$
• ck.powers_of_beta_g_second contains $(\beta^{n+2} G, \beta^{n+3} G..., \beta^{2n} G)$ in $\mathbb{G}_1$
• ck.powers_of_beta_h contains $(\beta^0 H, \beta^1 H..., \beta^n H)$ in $\mathbb{G}_2$

The $\beta$ here is a secret value and not knowing it does not prevent from using the Commitment Key. Indeed such a key is usually used with a bilinear pairing function, by using the property $e(\lambda G, \mu H) = e(G, H)^{\lambda \mu}$. To avoid writing exponents of exponents too much, this write-up will use the additive notation for the target group $\mathbb{G}_T$ of the pairing $e$. This means that the bilinear equations are written:

$$\forall (\lambda, \mu) \in \mathbb{F}_r^2, e(\lambda G, \mu H) = [\lambda \mu] e(G, H)$$

$$\forall (\lambda, \mu) \in \mathbb{F}_r^2, \left([\lambda] e(G, H)\right)\left([\mu] e(G, H)\right) = [\lambda + \mu] e(G, H)$$

Back to the algorithm, function ILV::commit therefore computes:

$$Comm_a = \sum_{i=1}^n a_{i - 1} \beta^i G \in \mathbb{G}_1$$

Function ILV::open is more complex.

• It starts by computing the inner-product of the two given vectors:

$$a \cdot b = \sum_{i=0}^{n-1} a_i b_i$$

• It then creates a polynomial of degree $n + 1$ from $a$:

$$a_{poly} = \sum_{i=1}^n a_{i - 1} X^i$$

• It also creates a polynomial from $b$, reversing the coefficients:

$$b_{poly} = \sum_{i=1}^n b_{n - i} X^i$$

• It multiplies both polynomials:

$$p = a_{poly} \times b_{poly} = \sum_{i=1}^n \sum_{j=1}^n a_{i - 1}b_{n - j} X^{i+j} = \sum_{s=2}^{2n}\sum_{0 \le k \le n - 1, s - 1 - n \le k \le s - 2} a_k b_{n - (s - 1 - k)}X^s$$

(with $s = i + j$ and $k = i - 1$, so $i = k - 1$ and $j = s - k - 1$)

• It checks that the coefficient of $X^{n + 1}$ in $p$ is the inner-product. Indeed this coefficient is:

$$p_{n+1} = \sum_{k=0}^{n + 1 - 2} a_k b_{n - (n + 1 - 1 - k)} = \sum_{k=0}^{n - 1} a_k b_k = a \cdot b$$

• It extracts the coefficients of $p$ in a vector $(p_0, p_1..., p_{2n}) \in \mathbb{F}_r^{2n + 1}$
• It computes a proof by combining all these coefficients with the Commitment Key:

$$Proof = \sum_{i=0}^n p_i \beta^i G + \sum_{i=0}^{n - 2} p_{n + 2 + i} \beta^{n + 2 + i} G = \sum_{i=0, i \neq n + 1}^{2n} p_i \beta^i G$$

In short, ILV::open computes a polynomial commitment of the product $p$ of two polynomials crafted from vectors $a$ and $b$, without the inner-product term $p_{n+1} = a \cdot b$.

To verify such a proof using the Commitment Key, ILV::verify starts by computing a commitment of the polynomial $b_{poly}$:

$$Comm_b = \sum_{j=1}^n b_{n - j} \beta^j H$$

It then computes three pairings, using the claimed value of the inner-product $Claimed_{a \cdot b}$

$$e_1 = e(Proof, H)$$

$$e_2 = e(Comm_a, Comm_b)$$

$$e_3 = e(Claimed_{a \cdot b} \beta^n G, \beta H)$$

ILV::verify accepts the proof if and only if $e_1 e_3 = e_2$. How does this work?

With the prover implemented in ILV::open, the computed pairings can be expanded:

$$e_1 = e\left(\sum_{i=0, i \neq n + 1}^{2n} p_i \beta^i G, H\right) = \left[\sum_{i=0, i \neq n + 1}^{2n} p_i \beta^i\right] e(G, H)$$

$$e_2 = e\left(\sum_{i=1}^n a_{i - 1} \beta^i G, \sum_{j=1}^n b_{n - j} \beta^j H\right) = \left[\sum_{i=1}^n\sum_{j=1}^n a_{i - 1} b_{n - j} \beta^{i + j}\right] e(G, H) = \left[\sum_{i=0}^{2n} p_i \beta^i\right] e(G, H)$$

$$e_3 = e(Claimed_{a \cdot b} \beta^n G, \beta H) = \left[Claimed_{a \cdot b} \beta^{n+1}\right] e(G, H)$$

So $e_1 e_3 = e_2$ becomes:

$$\left[\sum_{i=0, i \neq n + 1}^{2n} p_i \beta^i + Claimed_{a \cdot b} \beta^{n+1}\right] e(G, H) = \left[\sum_{i=0}^{2n} p_i \beta^i\right] e(G, H)$$

This equation verifies that the claimed inner-product of vectors $a$ and $b$ is $p_{n+1}$, which is computed in the right-side of the equation using the commitments of $a$ and $b$.

3. The Leaked Point

The algorithm only uses several points from the Commitment Key: $\beta^i G$ for $i = 0, 1..., n$ and $i = n + 2, n + 3..., 2n$, and $\beta^i H$ for $i = 0, 1..., n$. The length of the different parts of the key loaded from ck.srs can be displayed in Rust:

println!(
    "ck.powers_of_beta_g_first 0..n => n+1 items = {}",
    ck.powers_of_beta_g_first.len()
);
println!(
    "ck.powers_of_beta_g_second n+2..2n => n-1 items = {}",
    ck.powers_of_beta_g_second.len()
);
println!("ck.powers_of_beta_h 0..n => n+1 items = {}", ck.powers_of_beta_h.len());

This displays:

ck.powers_of_beta_g_first 0..n => n+1 items = 514
ck.powers_of_beta_g_second n+2..2n => n-1 items = 511
ck.powers_of_beta_h 0..n => n+1 items = 513

As $n$ is supposed to be 512, the first line contains an unexpected result: there is one more point than expected in ck.powers_of_beta_g_first! We can check that this is indeed $\beta^{n + 1} G$ by checking that points $\beta^i G$ in ck.powers_of_beta_g_first verify the pairing relation

$$e(\beta^i G, \beta H) = e(\beta^{i+1} G, H)$$

for i in 0..ck.powers_of_beta_g_first.len() - 1 {
    assert_eq!(
        E::pairing(ck.powers_of_beta_g_first[i], ck.powers_of_beta_h[1]),
        E::pairing(ck.powers_of_beta_g_first[i + 1], ck.powers_of_beta_h[0])
    );
}

From the understanding of the equation that the verifier checks, it seems interesting to add this point to the proof. Let's define a modified proof point using a scalar $\delta \in \mathbb{F}_r$:

$$Proof' = Proof + \delta (\beta^{n + 1} G)$$

Function ILV::verify checks that $e_1 e_3 = e_2$. When changing $Proof$, $e_1$ is updated to:

$$e'_1 = e(Proof', H) = e(Proof, H) e(\delta \beta^{n + 1} G, H) = e_1 \left(\left[\delta \beta^{n + 1}\right] e(G, H)\right)$$

Can we use this to modify the claimed inner-product? As it is uses in $e_3 = e(Claimed_{a \cdot b} \beta^n G, \beta H)$, it seems possible. Let's try to find a modified $Claimed'_{a \cdot b}$ such that $e'_1 e'_3 = e_2$.

$$e'_1 e'3 = e_2 \Leftrightarrow e_1 \left(\left[\delta \beta^{n + 1}\right] e(G, H)\right) e(Claimed'{a \cdot b} \beta^n G, \beta H) = e_1 e_3$$

$$\Leftrightarrow \left[\delta \beta^{n + 1} + Claimed'_{a \cdot b} \beta^{n+1}\right] e(G, H) = e_3$$

$$\Leftrightarrow \left[(\delta + Claimed'{a \cdot b}) \beta^{n+1}\right] e(G, H) = \left[Claimed{a \cdot b} \beta^{n+1}\right] e(G, H)$$

$$\Leftarrow \delta = Claimed_{a \cdot b} - Claimed'_{a \cdot b}$$

Therefore, we can claim any value for the inner-product of $a$ and $b$, and the above equation gives a value $\delta$ to use to modify the associated proof!

Here is an implementation of this attack in function attack in src/main.rs.

pub fn attack<E: ark_ec::PairingEngine>(ck: &CommitmentKey<E>, dim: usize) -> attack::Attack<E> {
    use crate::algorithms::ILV;
    use ark_ec::AffineCurve;
    use ark_std::UniformRand;

    // Craft a valid inner-product proof for a random vector a
    let mut rng = ark_std::test_rng();
    let a = (0..dim).map(|_| E::Fr::rand(&mut rng)).collect::<Vec<_>>();
    let cm = ILV::commit(ck, &a);
    let b = attack::hash(cm, dim);
    let proof = ILV::open(&ck, &a, &b);
    let inner_product = a.iter().zip(b.iter()).map(|(&a, b)| a * b).sum::<E::Fr>();
    assert!(ILV::verify(&ck, &cm, &b, inner_product, &proof));

    // Craft the attack to claim a random value as the inner product
    let attack_claim = E::Fr::rand(&mut rng);
    assert_ne!(attack_claim, inner_product);
    let delta: E::Fr = inner_product - attack_claim;
    let attack_proof = Proof(proof.0 + ck.powers_of_beta_g_first[dim + 1].mul(delta).into());

    // Verify the attack
    assert!(ILV::verify(&ck, &cm, &b, attack_claim, &attack_proof));

    println!(
        "Created an attack with {} instead of {}",
        attack_claim, inner_product
    );

    attack::Attack {
        a,
        commitment: cm,
        claimed_inner_product: attack_claim,
        proof: attack_proof,
    }
}

In the end, this inner-product protocol was broken because the Structured common Reference String of the Trusted Setup contained an additional point, $\beta^{n + 1} G$. This point enables adjusting the proof to claim that the inner-product of a committed vector $a$ with a public vector $b$ is any value.