Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

Write-up for zkHack puzzle #3: Double Trouble

1. The data

The puzzle consists in a Rust project available on https://github.com/kobigurk/zkhack-double-trouble. When running it, the following message is displayed:

Bob has developed a new zero-knowledge inner-product proof allows proving that
the inner product of a hidden, committed vector `a` with a public vector `b`
equals the claimed value `v` that is committed. He's released the protocol
license-free below, but still wants to profit from his invention. So, he
developed a proprietary prover that he claims is 2x faster than the standard one
described below, but without sacrificing zero-knowledge: it still hides all
information about the committed vector `a`. To back up his claim, he has
published a few proofs generated by this proprietary prover for the same `a` but
with respect to different `b` vectors, and has challenged people to recover `a`
from just these proofs.

Can you rise to the challenge and recover the vector `a`?.


The inner-product proof is obtained by applying the Fiat--Shamir transform to the following sigma protocol:

Before proof:
During proof of inner product with public vector b:
        Prover                                           Verifier
=================================================================================================
Offline phase (before `b` is available):
1. Prover computes 
    C_a := PedersenCOMM(a; α) 
         = sum_i (a_i * G_i) + α * H
    where G_i and H are random group elements, 
    and s is sampled randomly.
                            --------- C_a ---------->

Online phase for a given public vector `b` (can be repeated for different `b`s):

1. Prover samples a random vector r
    and random elements ρ, τ, υ.
2. Prover computes 
    C_r := PedersenCOMM(r; ρ)
    C_1 := PedersenCOMM(<a, b>; τ) // <x, y> denotes inner product of x and y.
    C_2 := PedersenCOMM(<r, b>; υ)
                            ---- C_r, C_1, C_2 ----->
                            <- random challenge γ ---
3. Prover computes 
    s := a + γr,
    u := α + γρ
    t := τ + γυ,
                            -------- s, u, t ------->
                                                // Check that `s` really is a + γr,
                                                Check PedersenCOMM(s; u) = C_a + γC_r
                                                // Check that the inner product is committed in C_1.
                                                Check PedersenCOMM(<s, b>; t) = C_1 + γC_2
==================================================================================================

These notations are quite obscure. Maybe the code is clearer? The Rust project provides the data for two proofs, in src/data.rs. This data is serialized in the Rust source code, which make them hard to read. Thankfully the structures are also provided, and matches the mathematic explanation:

// https://github.com/kobigurk/zkhack-double-trouble/blob/38f256a6af533ac49056bf17092b20b5730b83d5/src/inner_product_argument/data_structures.rs#L14
pub struct CommitKey {
    pub generators: Vec<GAffine>,   // Generators for Pedersen commitments, G_i
    pub hiding_generator: GAffine,  // Hiding generator for Pedersen commitments, H
}

pub struct Witness {
    pub a: Vec<Fr>,         // Secret vector a
    pub comm_a_rand: Fr,    // Random element α
}

// https://github.com/kobigurk/zkhack-double-trouble/blob/38f256a6af533ac49056bf17092b20b5730b83d5/src/inner_product_argument.rs#L14
pub struct Instance {
    pub comm_a: GAffine,    // Pedersen commitment C_a
    pub b: Vec<Fr>,         // Public vector b
}

https://github.com/kobigurk/zkhack-double-trouble/blob/38f256a6af533ac49056bf17092b20b5730b83d5/src/inner_product_argument/data_structures.rs#L45
pub struct Proof {
    pub commitment: ProofCommitment, // Pedersen commitments (C_r, C_1, C_2)
    pub response: ProofResponse,     // Proof response (s, u, t)
}
pub struct ProofCommitment {
    pub comm_r: GAffine,    // Pedersen commitment C_r
    pub comm_1: GAffine,    // Pedersen commitment C_1
    pub comm_2: GAffine,    // Pedersen commitment C_2
}
pub struct ProofResponse {
    pub s: Vec<Fr>,         // Public vector s
    pub u: Fr,              // Public element u
    pub t: Fr,              // Public element t
}

There structures use two types: Fr and GAffine. Both types are provided by the Rust crate ark_ed_on_bls12_381:

  • GAffine (which is in fact EdwardsAffine) is used to represent a point on a twisted Edwards curve known a "Jubjub".
  • Fr is used to represent big integers modulo r = 6554484396890773809930967563523245729705921265872317281365359162392183254199. This number is prime, and is the order of elements in the used twisted Edwards curve. This means that for any point P which is used in the project, r * P should be the unit point, which is (0, 1) on a twisted Edwards curve.

The puzzle provides a CommitKey object and two Proof objects. We can observe that there are some elements in the text descriptions which do not appear in the structures: the random elements ρ, τ, υ and the random challenge γ. We need to analyze the protocol in more details to understand what is going on.

2. The protocol

The protocol starts with a commitment key ck. This key contains some points which can be displayed in Rust by adding the following code to src/bin/verify-double-trouble.rs:

    println!("ck.generators.len() = {}", ck.generators.len());
    for i in 0..ck.generators.len() {
        println!("ck.generators[{}] = {}", i,  ck.generators[i]);
    }
    println!("ck.hiding_generator = {}", ck.hiding_generator);

This displays:

ck.generators.len() = 8
ck.generators[0] = GroupAffine(x=Fp256 "(198B8C3FC05A64DF64DEC6C0C9CF997E1AFA1DBB5C191ED0DFD5C771467F089D)", y=Fp256 "(5AE26A746DDBBCC5ECC3C970E715AEC48BB2551DD9DDE8AE7A7DA7032E161577)")
ck.generators[1] = GroupAffine(x=Fp256 "(4B92D491ACE817177026CD40C5020D04B30759F240CFDFF8DD795629E3307C5E)", y=Fp256 "(6604E7622969E8E968970E74DB648CF8226DCB0B67FF8E6313A3B9CAD7353701)")
ck.generators[2] = GroupAffine(x=Fp256 "(70F5E9698EF8F51B85D089DBBCC2F25190C905F6113976696F109307D347ACBA)", y=Fp256 "(3BD293E00769FE7963674BFA0745B4FE316AF189856418E679DBEF49B00A9085)")
ck.generators[3] = GroupAffine(x=Fp256 "(3FF005D6FE8FE85EA40051BF5051464AB69F0B587BE571B2800C08F4B93AD452)", y=Fp256 "(445D24D6D0EDEFC80B3785F27613FD072E4E69EBFC6A0B9716036F19E15C6ABF)")
ck.generators[4] = GroupAffine(x=Fp256 "(5174580F00FB73C60E3CA1D0A0EBF328FDAC3A018D15F6ED81B39D833927C079)", y=Fp256 "(26053B0E29A8E735673D8ACC0C0353EA6326DF6F81A2EE0AC65A8C1A853241F5)")
ck.generators[5] = GroupAffine(x=Fp256 "(65B0213A6DE2BC0DDAD9648179372A2B3939B06A1062CF0D58F731ABF7D6B742)", y=Fp256 "(11C6904D697A2638441B3125D0A3316507A03C16D79FCB3F5A19CF3ECFD649E6)")
ck.generators[6] = GroupAffine(x=Fp256 "(50644971731D58AFB54EB92D6F0C7700F06774B2AF10E72B646C0D5A93AA6347)", y=Fp256 "(1C282A3A58C4AD917587EBE68DC84A4CAC0E4A914FA83618439373528617AAAF)")
ck.generators[7] = GroupAffine(x=Fp256 "(3181568CB6D37D00412E3348F2C08C1579DB32492A768F41EAC49D8E7E6F9BBF)", y=Fp256 "(27EDAEA9068A61645B11E8D5C15E9569340E59E3963AE78CAADD2282451F10F4)")
ck.hiding_generator = GroupAffine(x=Fp256 "(3A2ED8E0E81BED90A83FA22E58FA8A0F08752AAB03CD4BA9BB558965B9A57B32)", y=Fp256 "(3C603EF0D0BB80987AD83208034C552F8919C5F8FEACC5404DEBCC16FE3B947F)")

So the puzzle uses a Pedersen commitment key with 8 generators and a hiding generator. To generate such a key, the project provides a function named sample. When displaying the key generated by CommitKey::sample(8), we find the same key. The project provides the way how this key was generated (from a deterministic pseudo-random number generator) so it is unlikely to be backdoored.

This commitment key is used to compute Pedersen commitments of 9 numbers (in group Fr). The first 8 numbers are a vector which is committed and the last one is a random element used to hide the vector (it ensures that it is impossible to recover the vector from the commitment).

In practise, the computation done in the Pedersen commitment function to commit a vector a with a random element α is:

PedersenCOMM(a; α) = sum_i (a_i * G_i) + α * H
    = a_0*G_0 + a_1*G_1 + a_2*G_2 + a_3*G_3 + a_4*G_4 + a_5*G_5 + a_6*G_6 + a_7*G_7 + α*H

The protocol used in the puzzle is about the inner-product of two vectors a and b, which is the number:

<a, b> = sum_i (a_i * b_i) = a_0*b_0 + a_1*b_1 + ... + a_7*b_7

Vector a is secret but is committed and the point C_a is given. Vector b is given. We can display the data of the two instances used in the puzzle:

    println!("instance1.comm_a = {}", instance1.comm_a);
    println!("instance2.comm_a = {}", instance2.comm_a);

    println!("instance1.b.len() = {}", instance1.b.len());
    println!("instance2.b.len() = {}", instance2.b.len());
    for i in 0..8 {
        println!("instance1.b[{}] = {}", i, instance1.b[i]);
        println!("instance2.b[{}] = {}", i, instance2.b[i]);
    }

This displays:

instance1.comm_a = GroupAffine(x=Fp256 "(6AE271E04FBB0AE9FB89506FF7180F5C06A8D60F802D934987965F694228BF8A)", y=Fp256 "(2BFBFA9CCF2151F01E71A069366DAD9398960B64684888D1AABB50D4D57BDF32)")
instance2.comm_a = GroupAffine(x=Fp256 "(6AE271E04FBB0AE9FB89506FF7180F5C06A8D60F802D934987965F694228BF8A)", y=Fp256 "(2BFBFA9CCF2151F01E71A069366DAD9398960B64684888D1AABB50D4D57BDF32)")
instance1.b.len() = 8
instance2.b.len() = 8
instance1.b[0] = Fp256 "(08180E66A534AADEBC88D09E1397DC7C33E2014115EB973B489E7D5CDBF839CD)"
instance2.b[0] = Fp256 "(08180E66A534AADEBC88D09E1397DC7C33E2014115EB973B489E7D5CDBF839CD)"
instance1.b[1] = Fp256 "(036AFB822FAC04AC9191CCEEF5BF4E27ADA6DC0440C88ECF3E06DC2FAFB162E6)"
instance2.b[1] = Fp256 "(036AFB822FAC04AC9191CCEEF5BF4E27ADA6DC0440C88ECF3E06DC2FAFB162E6)"
instance1.b[2] = Fp256 "(0DE7FE23DCF79F2A041E2C21876F9B9AEB3F2BC628E07B87F52DF460408334F2)"
instance2.b[2] = Fp256 "(0DE7FE23DCF79F2A041E2C21876F9B9AEB3F2BC628E07B87F52DF460408334F2)"
instance1.b[3] = Fp256 "(0891BBE1E3DA5717F7ED59288C9F51186E7BBAE018C9DA56F4BC8B4BBBD7457E)"
instance2.b[3] = Fp256 "(0891BBE1E3DA5717F7ED59288C9F51186E7BBAE018C9DA56F4BC8B4BBBD7457E)"
instance1.b[4] = Fp256 "(05D81F4C416350A3D02B1685176BFE5A98FA15D51C84DBD47680326F9F005E96)"
instance2.b[4] = Fp256 "(05D81F4C416350A3D02B1685176BFE5A98FA15D51C84DBD47680326F9F005E96)"
instance1.b[5] = Fp256 "(06D5E58667508A24F3A3FFBB244575DE29ECB3408D6EBC6D3DCDEFF02AA9453C)"
instance2.b[5] = Fp256 "(06D5E58667508A24F3A3FFBB244575DE29ECB3408D6EBC6D3DCDEFF02AA9453C)"
instance1.b[6] = Fp256 "(06BC47A67C6BD353EE624051B4C4A6A28E7F8CEDB6ED65A007D897AC071CBDCB)"
instance2.b[6] = Fp256 "(06BC47A67C6BD353EE624051B4C4A6A28E7F8CEDB6ED65A007D897AC071CBDCB)"
instance1.b[7] = Fp256 "(0CF6D9D35E0B6F2309568E5BB7C19448D993D2EFFEF7B3D77C137A26C524315A)"
instance2.b[7] = Fp256 "(0CF6D9D35E0B6F2309568E5BB7C19448D993D2EFFEF7B3D77C137A26C524315A)"

We observe that the two instance contains the same data! So in fact the two instances which were given proved the same operation <a, b>.

The objective now consists in recovering a and α. These values are defined in struct Witness, but (of course) they are not provided. Instead, the puzzle provides two proofs of the protocol. We can again display their content:

    println!("proof1.commitment.comm_r = {}", proof1.commitment.comm_r);
    println!("proof2.commitment.comm_r = {}", proof2.commitment.comm_r);
    println!("proof1.commitment.comm_1 = {}", proof1.commitment.comm_1);
    println!("proof2.commitment.comm_1 = {}", proof2.commitment.comm_1);
    println!("proof1.commitment.comm_2 = {}", proof1.commitment.comm_2);
    println!("proof2.commitment.comm_2 = {}", proof2.commitment.comm_2);
    println!("proof1.response.s.len() = {}", proof1.response.s.len());
    println!("proof2.response.s.len() = {}", proof2.response.s.len());
    for i in 0..8 {
        println!("proof1.response.s[{}] = {}", i, proof1.response.s[i]);
        println!("proof2.response.s[{}] = {}", i, proof2.response.s[i]);
    }
    println!("proof1.response.u = {}", proof1.response.u);
    println!("proof2.response.u = {}", proof2.response.u);
    println!("proof1.response.t = {}", proof1.response.t);
    println!("proof2.response.t = {}", proof2.response.t);

This gives:

proof1.commitment.comm_r = GroupAffine(x=Fp256 "(54103849E3BA52CCE4C2C7485134A683257413F5B9A1E0DD8B04FAF09D18EC28)", y=Fp256 "(245981A43B6DB2323AB5DD6B59A72428238E1F7416DA0C30E239D3AD8EFC7CF1)")
proof2.commitment.comm_r = GroupAffine(x=Fp256 "(10098E91DCAF5036082E598F953E71B128BF1DA198D1CC39364272EE6A0FCD20)", y=Fp256 "(2DD073C47A020602A0CEF1C13E6D1365CB0ADC716935AE1A010E1546DF2BF7A1)")
proof1.commitment.comm_1 = GroupAffine(x=Fp256 "(0ADC9FA9FE8D825BD5DA31F56D60EEB608EA5C47AF990736C3D27FAC048C11E1)", y=Fp256 "(46202BAFFE0145321B52334023D0A64C70B0283EB02A542C788FDF182C06ED4A)")
proof2.commitment.comm_1 = GroupAffine(x=Fp256 "(2F6A95827C2DF00431A43567CE757DCA4FABA1439EE6B09EB0A8CE88DF06B68C)", y=Fp256 "(2F06AC079158FC73402C6C4AF49DA4E9A957283439C4B45C25D116F340107C06)")
proof1.commitment.comm_2 = GroupAffine(x=Fp256 "(19FD6B1FBA846B5212FD91F823E1D3CDD944FE641035B2E459876BB67C2A20F5)", y=Fp256 "(63BE5660CDF347C66B93E5CD5F53BED2AC02172EF99A960D5D13B7BE896952BD)")
proof2.commitment.comm_2 = GroupAffine(x=Fp256 "(110DE1B6E88AABFFAA4ED784B5EEF7BF359D5D02C7EDF745A873ED28221C208B)", y=Fp256 "(2A7594A3D6F65B338A8817D79F5ED22FC2751EBDDD5246A88645D25C8510FD85)")
proof1.response.s.len() = 8
proof2.response.s.len() = 8
proof1.response.s[0] = Fp256 "(03BF9E72E978A1435A8FCCF9972DF1A9F32E2847E909E3AA893625EF7459A29B)"
proof2.response.s[0] = Fp256 "(097509C49C1A23D1561032AF0E913ABECFD7118ECAED891B4FF03E371C4851FD)"
proof1.response.s[1] = Fp256 "(07D44C895824B728A023E99D519F1FA1374B79BBAE6F014685E67645C56EA52F)"
proof2.response.s[1] = Fp256 "(030D44CB2D0EE4FFB432662D369391F9CDA993C8688A8A40397789D6AD699A12)"
proof1.response.s[2] = Fp256 "(052B1A3B43952AEED13DF00EBB1B6B2F905C27ADE223F95322E564BF20DF8D02)"
proof2.response.s[2] = Fp256 "(028270F51132616399FF22BE1B75F384CB20DD2930FD6D266BACC4F9FEEED431)"
proof1.response.s[3] = Fp256 "(0A7FCBBF77CD3051E02AF01BEB027B9A6B366EB2EE7F8F305514F1875649E3E8)"
proof2.response.s[3] = Fp256 "(05B387186F4F1529791DB3C4B3DD35A569C898479A3D088717EB56090E545AB6)"
proof1.response.s[4] = Fp256 "(0043445A2F596ECCB9FA5C1C0FE312DC6B3A9854F85B73577BE2B5DBDE8FEE2D)"
proof2.response.s[4] = Fp256 "(00FDB640151794E90A19180FE8E067E2EE8CA8FDD59CC7655B31FD73E9A65470)"
proof1.response.s[5] = Fp256 "(0249A8766973344D00B661117304DD3DF50B984B1172E3D146BA3FF2F0659716)"
proof2.response.s[5] = Fp256 "(0939B29EB3EDE613409D97AA2F9619FC8EA6DEEF453E3D53A357F6F23481E710)"
proof1.response.s[6] = Fp256 "(087B39177C45A824F26105645B5B6D35D497E4509059891B077C87A3A9C7090E)"
proof2.response.s[6] = Fp256 "(051CD7A2A71AAC95A3C859B04EB7556C5D60AA8712769D54C7A41549BAD674D6)"
proof1.response.s[7] = Fp256 "(03C7CDA534B7807FEEEF6166933D0468AD46538C27C65A7D2449A948C78A7EE4)"
proof2.response.s[7] = Fp256 "(029E6EA6CCFAF79F09BD858EE3391DCF2365F0DF1375FC4023E6D5A4BD42E2A4)"
proof1.response.u = Fp256 "(01BC0E747CD1C6343A1CFE54395A0B25978C2F42F2D8E34A51C6E41558E7138E)"
proof2.response.u = Fp256 "(052104D8AF9E6D932D8ABCB0D4EF77EC7B66859534D4660508AA899B625AB3EE)"
proof1.response.t = Fp256 "(0164EA3B3158A5ACD6C8C68828675474290082567AEE467167DDCA1631900D0A)"
proof2.response.t = Fp256 "(0842F86E0ED1DEE9408DE3F950D31D65A3DE3DAB87DFD06F333F088B976F2EAC)"

The two proofs contains very different values. How were they generated? The protocol describes the operations like this:

  • Prover generates a random vector r and random elements ρ, τ, υ.
  • Prover computes:
C_r := PedersenCOMM(r; ρ) = r_0*G_0 + r_1*G_1 + ... + r_7*G_7 + ρ*H
C_1 := PedersenCOMM(<a, b>; τ) = (a_0*b_0 + a_1*b_1 + ... + a_7*b_7)*G_0 + τ*H
C_2 := PedersenCOMM(<r, b>; υ) = (r_0*b_0 + r_1*b_1 + ... + r_7*b_7)*G_0 + υ*H
  • Prover computes a challenge γ. This is "the Fiat--Shamir transform to the sigma protocol". In the Rust code, this is implemented by computing the BLAKE2s hash of (ck, instance, proof_comm) in inner_product_argument/utils.rs. In the puzzle, we can recompute the challenge:
    let challenge1 = challenge(&ck, &instance1, &proof1.commitment);
    let challenge2 = challenge(&ck, &instance2, &proof2.commitment);
    println!("challenge1 = {}", challenge1);
    println!("challenge2 = {}", challenge2);
challenge1 = Fp256 "(064DD347B8477F6E9FCB600C301F341097B96C2DFA096166ADAA4A536DBCCAD9)"
challenge2 = Fp256 "(020C4359FA99590A9926F0327542791772070D6883B32AB6C217D5097C6712E7)"
  • Prover computes:
s := a + γ*r     (this is a vector of 8 integers modulo r)
u := α + γ*ρ     (this is an integer modulo r)
t := τ + γ*υ     (this is an integer modulo r)

With this construction, the verifier can check that some linear combinations of the commitment points are equals.

In the puzzle, the data contains two proofs. This write-up will use (C_r, C_1, C_2, s, u, t) for the first one and (C'_r, C'_1, C'_2, s', u', t') for the second one.

3. The attack

A classical attack of such a scheme is possible when the prover used the same random vector twice. If r = r', then with:

s  = a + γ *r
s' = a + γ'*r

... it is possible to recover the secret a by computing a = (1 / (γ' - γ))*(γ'*s - γ*s'). This is what the lecture from Stanford given in the puzzle subject was about (https://crypto.stanford.edu/cs355/19sp/lec5.pdf).

Here, if r = r', we would expect that C_r = C'_r. But we saw previously that proof1.commitment.comm_r and proof2.commitment.comm_r were different. What's the trick?

It is time to go back to the subject of the puzzle:

he developed a proprietary prover that he claims is 2x faster than the standard one described below, but without sacrificing zero-knowledge

How can a "cheating" prover be much faster than the standard one? Of course if r and ρ are reused for several proofs, computing C_r would only need to be done once. But this would be visible. Another possibility consists in re-using r but with different ρ. Doing so, it is possible to recover a but not α, which means that we cannot prove that the recovered secret was indeed the a which was committed in C_a.

After much time trying several tracks, a revelation happened when reading again the puzzle title:

Double Trouble

What if r' was computed from r, for example by doubling it? Let's display 2*C_r:

    println!("2*C_r = {}", proof1.commitment.comm_r + proof1.commitment.comm_r);
    println!("C'_r  = {}", proof2.commitment.comm_r);
2*C_r = GroupAffine(x=Fp256 "(10098E91DCAF5036082E598F953E71B128BF1DA198D1CC39364272EE6A0FCD20)", y=Fp256 "(2DD073C47A020602A0CEF1C13E6D1365CB0ADC716935AE1A010E1546DF2BF7A1)")
C'_r  = GroupAffine(x=Fp256 "(10098E91DCAF5036082E598F953E71B128BF1DA198D1CC39364272EE6A0FCD20)", y=Fp256 "(2DD073C47A020602A0CEF1C13E6D1365CB0ADC716935AE1A010E1546DF2BF7A1)")

We clearly see that C'_r = 2*C_r !!!

Now, the "discrete logarithm problem" (and the fact that the commitment key was really generated from a PRNG) ensures that:

r' = 2*r
ρ' = 2*ρ

So the equations become:

s  = a + γ *r
s' = a + γ'*r' = a + 2*γ'*r

u  := α + γ *ρ
u' := α + γ'*ρ' = α + 2*γ'*ρ

And therefore:

a = (1 / (2*γ' - γ))*(2*γ'*s - γ*s')
α = (1 / (2*γ' - γ))*(2*γ'*u - γ*u')

We can compute this in Rust:

// Add at the top: use ark_ff::BigInteger256;
    let two = Fr::from_repr(BigInteger256::from(2)).unwrap();
    let mut a: Vec<Fr> = vec![Fr::zero(); 8];
    for i in 0..8 {
        a[i] = (proof1.response.s[i] * two * challenge2 - proof2.response.s[i] * challenge1)
            / (two * challenge2 - challenge1);
        println!("a[{}] = {}", i, a[i]);
    }
    let comm_a_rand = (proof1.response.u * two * challenge2 - proof2.response.u * challenge1)
        / (two * challenge2 - challenge1);
    println!("comm_a_rand = {}", comm_a_rand);

    println!("Computed commitment: {}", ck.commit_with_explicit_randomness(&a, comm_a_rand));

This leads to:

a[0] = Fp256 "(052A875D7E3F3F47D964D8D03C9C96BAC72690BD62D529233A5F196EA626DA47)"
a[1] = Fp256 "(0709F70E0787B6F99008CAD06522A40A7C4A0B4D62E8029B7073F64D6832E97C)"
a[2] = Fp256 "(0B72FDA7B32B74DF0EE544558104AE1B79318A4BF2F768F045140EA48EE8CC2E)"
a[3] = Fp256 "(04CFCDCCAF8D3DA832B5F677B3D20B27444C77AB52901ABA1C4F4A124C6C8BFA)"
a[4] = Fp256 "(0BBDE6DD34E9A0C21118ACAB8083F6308F297DB567D3AC7DF3BE555335FECC85)"
a[5] = Fp256 "(0CD666318404B4C1042C3B1646E32F072A10C30F05FAA2701A3F25C987470DB5)"
a[6] = Fp256 "(023961D1A8FCD42B7BB8EEE8CBCBE46A1FAEBB65320BABF09A635FDF8C9821F9)"
a[7] = Fp256 "(03A52AF29CA3C162D31CD9D8E8937B652E0BCEC0E3C03270E3F82C91920C2A56)"
comm_a_rand = Fp256 "(039356E0074288047BE3CD30583A88B7A760D6AFC2C1E996C33A41684D989534)"
Computed commitment: GroupAffine(x=Fp256 "(6AE271E04FBB0AE9FB89506FF7180F5C06A8D60F802D934987965F694228BF8A)", y=Fp256 "(2BFBFA9CCF2151F01E71A069366DAD9398960B64684888D1AABB50D4D57BDF32)")

The computed commitment of (a, α) matches instance1.comm_a (and instance2.comm_a, which is equals), which proves that it was indeed the secret value used by the prover.

In decimal, the solution is:

let (a, comm_a_rand): (Vec<Fr>, Fr) = (
    vec![
        Fr::from_str(
            "2336706075964247989947433674548942226827306841875429968112509828215618329159",
        ).unwrap(),
        Fr::from_str(
            "3183796673245796636687562422863836804215466330278309281736435087784983849340",
        ).unwrap(),
        Fr::from_str(
            "5178612562806274700109127208151001095511383281260239557723446192273548168238",
        ).unwrap(),
        Fr::from_str(
            "2176409113060157430684277991899328451416352041675746388298954703991743482874",
        ).unwrap(),
        Fr::from_str(
            "5310968795039368315853267802615936582862130677392677794847104969389960514693",
        ).unwrap(),
        Fr::from_str(
            "5806564767929688700136171453700501428844225212575251330189050251826120035765",
        ).unwrap(),
        Fr::from_str(
            "1006011101679865533947259717866832372946407201677415593630279116718161273337",
        ).unwrap(),
        Fr::from_str(
            "1648764725587973804015859780978773015249711523441957090043447269437062523478",
        ).unwrap(),
    ],
    Fr::from_str(
        "1617264654250654530393647253572292035968664667634001469351271665735252350260",
    ).unwrap(),
);

Conclusion

The prover tried to optimise the protocol by doubling (r, ρ) for the second proof (doing so greatly simplifies the computation of C_r). Attacking this scheme is less straightforward than if r was directly reused, but this is nonetheless possible once we know how the "optimisation" works.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment