承诺方案 — Pedersen 承诺与同态性

日期: 2026-11-19 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #承诺 #Pedersen #ZK基础

---

今日目标

---

一、承诺方案 (Commitment Scheme) 形式化

1.1 抽象接口

Commit: (m, r) → c        # commit message m with randomness r
Open:   (c, m, r) → bool  # verify (m, r) opens c

类比"信封"：

• 把消息装入信封封口（commit）→ 不能改
• 之后撕开信封展示（open）→ 任何人可验证

1.2 安全性质

Hiding (隐藏性): 看到 commitment $c$ 学不到 $m$ 的任何信息

• Statistical Hiding: 信息论意义上完美 (即使无限算力也无法区分)
• Computational Hiding: 多项式时间区分困难

Binding (绑定性): 一旦 commit，无法找到 $(m', r') \ne (m, r)$ 使 $\text{Commit}(m, r) = \text{Commit}(m', r')$

• Statistical Binding: 信息论意义上唯一
• Computational Binding: 多项式时间寻找碰撞困难

1.3 Hiding/Binding 不可兼得

定理: 任何承诺方案不能同时 statistical hiding + statistical binding。

直觉: 若 statistical hiding 完美，存在多个 $(m, r)$ 映射到同 $c$ → 攻击者（无限算力）必能找到不同 opening → 仅 computational binding。

实践中常选 statistical hiding + computational binding（Pedersen 类型）或 computational hiding + statistical binding（hash 类型）。

---

二、常见承诺构造

2.1 Hash-based Commitment

$$c = H(m | r)$$

• ✓ Computational hiding (假设 $H$ 抗原像 + 假设 $r$ 高熵)
• ✓ Statistical binding (假设 $H$ 抗碰撞)
• ✗ 无同态性
• ✓ 简单、快、ZK 不友好（电路内 hash 开销大）

2.2 Pedersen Commitment ⭐ 主角

设群 $G$ 阶 $q$，generators $g, h$ 满足 $\log_g h$ 未知（trusted setup 或 nothing-up-my-sleeve）。

$$\text{Commit}(m, r) = g^m h^r \quad (m, r \in \mathbb{Z}_q)$$

• ✓ Perfect hiding (无限算力下 $m$ 完全隐藏 — 见下证)
• ✓ Computational binding (DLP 假设)
• ✓ 加法同态: $C_1 \cdot C_2 = g^{m_1+m_2} h^{r_1+r_2}$
• ✓ ZK 友好
• ✗ Hash-based 之上稍慢 (1 multi-exp vs 1 hash)

2.3 ElGamal Commitment

$$\text{Commit}(m, r) = (g^r, g^m h^r)$$

• 同时是加密方案
• 可解开（"trapdoor commitment"）

---

三、Pedersen 承诺安全性证明

3.1 Perfect Hiding

定理: 给定 $c$，对任意 $m^* \in \mathbb{Z}_q$，存在唯一 $r^* = \log_h(c \cdot g^{-m^})$ 使得 $g^{m^} h^{r^*} = c$.

证明: 因 $r$ 在 $\mathbb{Z}_q$ 中均匀分布，$h^r$ 在 $G$ 中均匀分布（$h$ 是 generator），$g^m h^r$ 也均匀分布。$c$ 的分布与 $m$ 无关。

意义: 即使无限算力的攻击者也无法从 $c$ 学到 $m$ 的任何信息。

3.2 Computational Binding

定理: 若 DLP 在 $G$ 中困难，则 Pedersen 计算绑定。

证明: 假设攻击者能找 $(m, r) \ne (m', r')$ s.t. $g^m h^r = g^{m'} h^{r'}$, 则: $$g^{m-m'} = h^{r'-r}$$ $$\Rightarrow \log_g h = (m-m') / (r'-r)$$

攻击者解出了 $\log_g h$ → DLP 解。矛盾。

安全前提: $h$ 必须没人知道 $\log_g h$。常用做法:

• "Nothing up my sleeve": $h = H_{\text{group}}(\text{seed})$ 用 hash-to-curve
• Trusted setup with destruction
• $h = H_{\text{group}}(g)$ 用确定性派生

3.3 同态性

$$C_1 \cdot C_2 = g^{m_1} h^{r_1} \cdot g^{m_2} h^{r_2} = g^{m_1+m_2} h^{r_1+r_2}$$

应用:

• 隐藏余额: 用户余额 = $C(\text{balance})$，转账时 $C_{\text{Alice}}' = C_{\text{Alice}} - C(amount)$, $C_{\text{Bob}}' = C_{\text{Bob}} + C(amount)$
• 求和无需打开: ZK 证明 $\sum m_i = T$ 时只需验证 $\prod C_i = g^T h^{\sum r_i}$
• Bulletproofs: 整个 inner-product 论证基于 Pedersen 同态

---

四、Vector Pedersen Commitment

承诺一个向量 $\vec{m} = (m_1, ..., m_n)$: $$C(\vec{m}, r) = h^r \prod_{i=1}^n g_i^{m_i}$$

其中 $g_1, ..., g_n, h$ 是 $n+1$ 个独立 generators (无人知任何对的离散对数关系)。

性质:

• 同样 perfect hiding + comp binding
• 大小固定 (1 个群元素，与 $n$ 无关)
• 加法同态 + 标量同态: $C(\vec{m_1}) \cdot C(\vec{m_2}) = C(\vec{m_1} + \vec{m_2})$, $C(\vec{m})^k = C(k \vec{m})$
• 不能 open 单个分量（否则破坏 hiding）

应用: Bulletproofs 内积论证、IPA、Dory。

---

五、Pedersen Hash (用于 Merkle Tree)

设 $g_1, ..., g_n$ generators。把消息 $m$ 切成 $n$ 块 $m_1, ..., m_n$: $$\text{PedersenHash}(m) = \sum_i m_i \cdot g_i$$

• 在 EC 群中 → 输出是一个点 (32-64 字节)
• ZK 友好: 仅 $n$ 个 point mul（每个 ~10 约束）
• 不抗碰撞，仅在 binding 意义下安全

ZK 协议（Zcash Sapling、Tornado Cash）的 Merkle Tree 用 Pedersen hash 而非 SHA-256，因为:

• SHA-256 在 R1CS 中 ~25k 约束 vs Pedersen ~3k

---

六、代码实现 — pedersen.py

"""
pedersen.py - Pedersen 承诺方案 (在 secp256k1 上)
"""
from __future__ import annotations
import hashlib
import os
from dataclasses import dataclass

# secp256k1
P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
GX = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
GY = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

def inv(x, m): return pow(x, -1, m)

def point_add(P1, P2):
    if P1 is None: return P2
    if P2 is None: return P1
    x1, y1 = P1; x2, y2 = P2
    if x1 == x2 and (y1 + y2) % P == 0:
        return None
    if x1 == x2:
        m = (3*x1*x1) * inv(2*y1, P) % P
    else:
        m = (y2 - y1) * inv(x2 - x1, P) % P
    x3 = (m*m - x1 - x2) % P
    y3 = (m*(x1 - x3) - y1) % P
    return (x3, y3)

def point_neg(P_pt):
    if P_pt is None: return None
    return (P_pt[0], (P - P_pt[1]) % P)

def scalar_mul(k, point):
    k = k % N
    result = None
    addend = point
    while k:
        if k & 1: result = point_add(result, addend)
        addend = point_add(addend, addend)
        k >>= 1
    return result

G = (GX, GY)

def hash_to_curve(seed: bytes) -> tuple:
    """Try-and-increment hash-to-curve (NIST P-style).
    Used to derive H without knowing dlog_G(H)."""
    counter = 0
    while True:
        h = hashlib.sha256(seed + counter.to_bytes(4, 'big')).digest()
        x = int.from_bytes(h, 'big') % P
        # try y^2 = x^3 + 7 mod P
        y_sq = (pow(x, 3, P) + 7) % P
        y = pow(y_sq, (P + 1) // 4, P)
        if pow(y, 2, P) == y_sq:
            return (x, y)
        counter += 1

H = hash_to_curve(b"PEDERSEN_H_GEN_secp256k1_v1")

# --------------------------- Pedersen Commitment ---------------------------

@dataclass
class PedersenCommitment:
    point: tuple

    def to_bytes(self) -> bytes:
        x, y = self.point
        return b'\x04' + x.to_bytes(32, 'big') + y.to_bytes(32, 'big')

    def __add__(self, other):
        return PedersenCommitment(point_add(self.point, other.point))

    def __sub__(self, other):
        return PedersenCommitment(point_add(self.point, point_neg(other.point)))

    def __mul__(self, k: int):
        return PedersenCommitment(scalar_mul(k, self.point))

def commit(m: int, r: int) -> PedersenCommitment:
    """C = m*G + r*H"""
    p = point_add(scalar_mul(m, G), scalar_mul(r, H))
    return PedersenCommitment(p)

def open_commit(c: PedersenCommitment, m: int, r: int) -> bool:
    expected = commit(m, r)
    return c.point == expected.point

# --------------------------- Vector Pedersen ---------------------------

def setup_generators(n: int) -> list:
    """Derive n independent generators via hash-to-curve."""
    return [hash_to_curve(f"PEDERSEN_GEN_{i}".encode()) for i in range(n)]

def vector_commit(values: list[int], r: int, gens: list = None) -> PedersenCommitment:
    """C = r*H + sum(v_i * g_i)"""
    if gens is None:
        gens = setup_generators(len(values))
    p = scalar_mul(r, H)
    for v, g in zip(values, gens):
        p = point_add(p, scalar_mul(v, g))
    return PedersenCommitment(p)

# --------------------------- Pedersen Hash ---------------------------

def pedersen_hash(msg: bytes, chunk_size: int = 4) -> tuple:
    """ZK-friendly hash: ph(m) = sum_i m_i * g_i (no randomness, only binding)."""
    chunks = [int.from_bytes(msg[i:i+chunk_size], 'big')
              for i in range(0, len(msg), chunk_size)]
    gens = setup_generators(len(chunks))
    p = None
    for v, g in zip(chunks, gens):
        p = point_add(p, scalar_mul(v, g))
    return p

# --------------------------- ZK Proof of Opening (Schnorr-style) ---------------------------

def prove_opening(m: int, r: int) -> tuple:
    """
    Schnorr-style proof of knowledge for (m, r) opening C = mG + rH.
    Returns (R, s_m, s_r) where:
      R = a*G + b*H (commitment to randomness)
      e = H(C || R)
      s_m = a + e*m, s_r = b + e*r
    Verifier checks: s_m*G + s_r*H == R + e*C
    """
    a = int.from_bytes(os.urandom(32), 'big') % N
    b = int.from_bytes(os.urandom(32), 'big') % N
    R = point_add(scalar_mul(a, G), scalar_mul(b, H))
    C = commit(m, r).point
    e = int.from_bytes(hashlib.sha256(
        C[0].to_bytes(32,'big') + C[1].to_bytes(32,'big') +
        R[0].to_bytes(32,'big') + R[1].to_bytes(32,'big')
    ).digest(), 'big') % N
    s_m = (a + e * m) % N
    s_r = (b + e * r) % N
    return (R, s_m, s_r)

def verify_opening(C: PedersenCommitment, proof: tuple) -> bool:
    R, s_m, s_r = proof
    e = int.from_bytes(hashlib.sha256(
        C.point[0].to_bytes(32,'big') + C.point[1].to_bytes(32,'big') +
        R[0].to_bytes(32,'big') + R[1].to_bytes(32,'big')
    ).digest(), 'big') % N
    lhs = point_add(scalar_mul(s_m, G), scalar_mul(s_r, H))
    rhs = point_add(R, scalar_mul(e, C.point))
    return lhs == rhs

# --------------------------- Demo ---------------------------

if __name__ == "__main__":
    # 1. 基本 commit/open
    m, r = 42, int.from_bytes(os.urandom(32), 'big') % N
    c = commit(m, r)
    assert open_commit(c, m, r)
    assert not open_commit(c, m + 1, r)
    assert not open_commit(c, m, r + 1)
    print("Basic Pedersen commit/open: PASS")

    # 2. 同态加法 — 隐私转账核心
    bal_alice = commit(100, int.from_bytes(os.urandom(32), 'big') % N)
    bal_bob = commit(50, int.from_bytes(os.urandom(32), 'big') % N)
    amount = 30
    r_amount = int.from_bytes(os.urandom(32), 'big') % N
    c_amount = commit(amount, r_amount)
    
    # 转账后:
    # bal_alice_new = bal_alice - c_amount
    # bal_bob_new = bal_bob + c_amount
    bal_alice_new = bal_alice - c_amount
    bal_bob_new = bal_bob + c_amount
    
    # 任何人能验证 sum 不变（不知具体值）:
    sum_before = bal_alice + bal_bob
    sum_after = bal_alice_new + bal_bob_new
    assert sum_before.point == sum_after.point
    print("Homomorphic conservation (sum_before == sum_after): PASS")

    # 3. ZK proof of opening (用 Schnorr-like sigma protocol)
    proof = prove_opening(m, r)
    assert verify_opening(c, proof)
    print("ZK proof of opening: PASS")

    # 4. Vector commit
    vec = [10, 20, 30, 40]
    r_v = int.from_bytes(os.urandom(32), 'big') % N
    cv = vector_commit(vec, r_v)
    print(f"Vector commit (n=4): {cv.point[0].to_bytes(32, 'big').hex()[:20]}...")

    # 5. Hiding 演示: 同 m 不同 r → 不同 c
    c1 = commit(42, 100)
    c2 = commit(42, 200)
    assert c1.point != c2.point
    print("Different randomness → different commitment (perfect hiding): PASS")

    # 6. 防 Binding 攻击：不能伪造 opening
    # 攻击者尝试找 (m', r') ≠ (m, r) 使 commit(m,r) == commit(m',r')
    # 等价于解 dlog_G(H)，所以仅 computationally infeasible
    print("Computational binding: relies on DLP hardness")

---

七、Pedersen 承诺的应用

7.1 Confidential Transactions (CT) — Monero / Mimblewimble

每个 UTXO 不是明文金额，而是 Pedersen $C = vG + rH$.

转账验证: $\sum C_{\text{out}} - \sum C_{\text{in}} = 0$ (自动验证守恒，无需打开)

需配 Range Proof 证明 $v \in [0, 2^{64})$（防止负值），通常用 Bulletproofs。

7.2 Bulletproofs

整个论证基于 Vector Pedersen 同态。证明 $v \in [0, 2^n)$ 仅需 $O(\log n)$ 群元素，无需 trusted setup。

7.3 Tornado Cash 隐私存款

Note commitment = $H_{\text{Pedersen}}(\text{secret} | \text{nullifier})$.

• 在电路内验证开承诺
• ZK Merkle proof 证明在树中

7.4 Zcash Sapling Note

note = (d, pk_d, value, rcm)
note_commitment = WindowedPedersenCommit(d || pk_d || value || rcm)

7.5 Polynomial Commitment 基础

KZG / Bulletproofs IPA 都把多项式的系数 commit 成 vector Pedersen 风格的承诺。明日详讲。

---

八、真实漏洞 / 事件

Mimblewimble traceability: 虽然 Pedersen 隐藏值，但交易图（UTXO 关系）仍可观察。Ivan Bogatyy (2019) 论文显示通过 sniffing 96% MimbleWimble tx 可被关联。

---

九、协议应用 — Web3 速查

---

十、常见陷阱

1. $h$ 的 dlog 已知 = binding 完全失效。$h$ 必须用 hash-to-curve 或可验证的 nothing-up-my-sleeve
2. 重用 randomness $r$ → 多个 commitment 关联性: $C_1 - C_2 = (m_1 - m_2)G$，attacker 学到 $m_1 - m_2$
3. Modular arithmetic 错误 — m, r 必须在 $\mathbb{Z}_q$ 中 (不是 $\mathbb{Z}_p$)
4. Vector commitment 不能 open 单个分量 — 否则 hiding 破坏（剩余分量被推断）
5. 同态运算时维度不匹配 — vector 长度不同 → 不可加
6. Pedersen hash 不抗碰撞 — 仅 binding，不能用作通用哈希
7. Range proof 缺失 — 同态 + 无 range proof = 攻击者可 commit 负值制造通胀
8. Group order mismatch — secp256k1 vs Babyjubjub 必须一致

---

十一、关键速查

承诺方案对比

性能 (secp256k1)

---

十二、面试题

Q1: Pedersen 承诺如何同时 hiding + binding？ A: Statistical hiding + computational binding: $r$ 在 $\mathbb{Z}_q$ 均匀分布 → $h^r$ 在群中均匀 → $g^m h^r$ 完全独立于 $m$（perfect hiding，信息论级别）。Binding 要求找到不同 opening 等价于解 $\log_g h$ → 仅 DLP 困难下绑定。这意味着量子计算机出现时 binding 立即失效（Shor 算法）。

Q2: Pedersen 承诺为何在隐私协议中流行？ A: 三大优势: (1) 加法同态 → 不打开就能验证守恒（CT）; (2) Perfect hiding → 信息论级别隐私; (3) ZK 友好 → 在电路内开承诺成本 ~3k 约束 vs hash ~25k。代价: binding 仅计算意义，量子下失效（但 hash-based 也类似困境）。

Q3: 为什么 Tornado Cash 的 commitment 不直接用 SHA-256？ A: ZK 电路成本。Tornado 需要在 SNARK 内验证 commitment = H(secret || nullifier). SHA-256 在 R1CS 中 ~25k 约束/哈希 → 证明慢 + 大。Pedersen hash 用 EC 加法仅 ~3k 约束。代价: Pedersen 不抗碰撞（仅 binding），但用作 commitment 而非 hash 时安全。

Q4: Vector Pedersen 为什么不能 open 单个分量？ A: 若 commit 是 $C = \sum m_i g_i + rH$, 公开 $m_1$ 即让攻击者计算 $C - m_1 g_1 = \sum_{i\ge 2} m_i g_i + rH$ — 这仍是 vector commit 但维度更小，每次 open 都缩小搜索空间 → 多次 open 可解出全部。要支持单分量 open 需用 KZG / Verkle 等明天讲的方案。

Q5: Pedersen 与 KZG 在多项式承诺中的取舍？ A:

• Pedersen IPA (Bulletproofs): 无 trusted setup，proof size $O(\log n)$，但验证 $O(n)$ → 慢
• KZG: 需 trusted setup，proof size $O(1)$ (1 群元素), 验证 $O(1)$ pairing → 快
• 选择: 不愿信任 setup → IPA (Halo2 用); 愿意 setup 换性能 → KZG (PLONK / Eth4844 blob 用)

---

十三、明日预告

Day 203: 多项式承诺 — 进入 KZG / Bulletproofs IPA 的世界。多项式承诺是现代 ZK 协议（PLONK、Halo2、STARK）的核心基础。手写简化版 KZG 承诺+open+verify。