ZK Hack Puzzle 5 题解：如何使用弱Fiat-Shamir攻破消息相等性证明可靠性

1挑战内容

见：https://www.zkhack.dev/puzzle5.html

消息相等性证明：证明两个Pedersen承诺是对同一个消息的承诺的证明系统。

可使用Fiat-Shamir启发式编译下述-协议得到：

离线阶段

• 证明者计算并发送给验证者：

C_1 := PedersenCOMM(a; r1) = a * G + r1 * H
C_2 := PedersenCOMM(a; r2) = a * G + r2 * H

在线阶段

• 证明者采样随机元素
• 证明者计算并发送给验证者

C_ρ := PedersenCOMM(r; ρ)
C_τ := PedersenCOMM(r; τ)

• 验证者发送随机挑战给证明者
• 证明者计算并发送给验证者

s := r + e * a
u := ρ + e * r1
t := τ + e * r2

• 验证者检验如下是否通过

PedersenCOMM(s; u) = C_ρ + eC_1
PedersenCOMM(s; t) = C_τ + eC_2

Fiat-Shamir启发式挑战生成代码如下：

let challenge = b2s_hash_to_field(&(*ck, commitment));

即挑战是下述输入的哈希：

• 承诺密钥 ：包括 和
• commitment：包括两个承诺值 和

两个输入参数类型如下：

pub struct CommitKey {
    pub message_generator: GAffine,
    pub hiding_generator: GAffine,
}
pub struct ProofCommitment {
    pub comm_rho: GAffine,
    pub comm_tau: GAffine,
}

注意到两个消息承诺都未包含在FS的输入中，这种版本的FS被称为弱Fiat-Shamir

2题解

上述Offline-Online版本-协议是selective的，意即消息承诺在随机挑战之前已经生成。如果调整协议消息序使得消息承诺在随机挑战之后生成，那么一个adaptive的恶意证明者敌手可以通过选择和随机挑战相关的消息以攻破可靠性。

利用弱Fiat-Shamir

目标是得到对不同消息的承诺，依然通过检验，记不同消息为：

观察验证者检验方程：

和 都参与随机挑战的生成，不可改变；类似的 和 会在 和 中使用，依赖于 和 ，也不能做什么。故为了得到恶意的通过验证的 和 ，需要在 处做文章。

计算s

要想使得，已经确定，则需要两个不同的值：

// CHEAT: generate 2 random r values instead of 1
let r_rho = Fr::rand(rng);
let r_tau = Fr::rand(rng);

在作为FS哈希输入的证明承诺中使用：

C_ρ := PedersenCOMM(r; ρ)
C_τ := PedersenCOMM(r; τ)

则：

计算

// CHEAT: compute a_2 from a_1, r_rho, r_tau
let r_diff = r_tau - r_rho;
let a_2 = a_1 - r_diff / challenge;
let comm_2 = ck.commit_with_explicit_randomness(a_2, r_2);

攻击代码

let (instance, witness, proof): (Instance, (Fr, Fr, Fr, Fr), Proof) = {
    let rng = &mut rand::thread_rng();

    // === CHANGE: DEFER OFFLINE PHASE ===

    // === ONLINE PHASE ===
    // Step 1: Prover samples random elements r, ρ, τ.
    // CHEAT: generate 2 random r values instead of 1
    let r_rho = Fr::rand(rng);
    let r_tau = Fr::rand(rng);
    // generate random values rho and tau below using commit_with_rng

    // Step 2: Prover computes C_ρ, C_τ
    // create the proof commitment with randomly generated rho and tau
    let (comm_rho, rho) = ck.commit_with_rng(r_rho, rng);
    let (comm_tau, tau) = ck.commit_with_rng(r_tau, rng);
    let commitment = ProofCommitment { comm_rho, comm_tau };

    // compute verifier's challenge via Fiat-Shamir: e = H(G, H, comm_rho, comm_tau)
    let challenge = b2s_hash_to_field(&(ck, commitment));

    // === BEGIN REORDERED OFFLINE PHASE PART 1: a_1, r_1, r_2, comm_1 ===
    let a_1 = Fr::rand(rng);

    // compute comm_1 and generate r_1
    let (comm_1, r_1) = ck.commit_with_rng(a_1, rng);

    // generate random r_2
    let r_2 = Fr::rand(rng);
    // === END REORDERED OFFLINE PHASE PART 1 ===

    // Step 3: Prover computes s, u, t
    // CHEAT: compute s with r_rho and a_1
    let s = r_rho + challenge * a_1;

    // compute u, t honestly
    let u = rho + challenge * r_1;
    let t = tau + challenge * r_2;
    // create the proof response
    let response = ProofResponse { s, u, t };


    // === BEGIN REORDERED OFFLINE PHASE PART 2: a_2, comm_2 ===
    // CHEAT: compute a_2 from a_1, r_rho, r_tau
    let r_diff = r_tau - r_rho;
    let a_2 = a_1 - r_diff / challenge;
    let comm_2 = ck.commit_with_explicit_randomness(a_2, r_2);
    // === END REORDERED OFFLINE PHASE PART 2 ===


    // PREPARE STRUCTS FOR SOLUTION VALIDATION
    let instance = Instance { comm_1, comm_2 };
    let witness = (a_1, r_1, a_2, r_2);
    let proof = Proof {
        commitment,
        response,
    };

    // return
    (instance, witness, proof)
};

3协议修复

可通过剥夺证明者自适应计算的能力以避免上述攻击。只需将加入生成随机挑战哈希的输入即可，这样就可将弱Fiat-Shamir变为强Fiat-Shamir，随机挑战依赖于消息承诺，则消息不可依赖于随机挑战，恶意证明者将不可再以利用上述改变协议消息序的攻击。

let challenge = b2s_hash_to_field(&(*ck, instance, commitment));

pub struct Instance {
    pub comm_1: GAffine,
    pub comm_2: GAffine,
}