离散对数零知识证明

在零知识证明中，信息 x 被加密成 y 后保存在 Bob 处，Alice 如何在不揭露信息 x 的情况下，证明她知道这个信息呢？

在下图中，Alice 首先生成一个随机数 r，然后计算 $C_r = g^r \mod p$，并将 $C_r$ 发送给 Bob。Bob 会随机发送一个挑战给 Alice：

• $C_r$ 对应的 r 值是多少？
• $x + r \mod (p-1)$ 是多少？

由于 Alice 并不知道每次 Bob 要发送什么挑战，所以除非 Alice 连续蒙对 100 次 Bob 要发送的挑战，否则就无法伪装。 而连续蒙对 100 次的概率为 $\frac{1}{2^{100}}$，可以认为无法实现。 实际应用中，可以通过增加循环次数来进一步增加安全性。

如何验证 Alice 的回答？

1. 验证 r

Alice 返回 r 后，Bob 需要验证 $C_r = g^r \mod p$ 是否成立。

2. 验证 $x + r \mod (p-1)$

Alice 返回 $x + r \mod (p-1)$ 后，Bob 只需验证 $g^{(x+r) \mod (p-1)} \mod p = (C_x \cdot C_r) \mod p$ 是否成立。

已知 $C_r = g^r \mod p$ , $C_x = g^x \mod p$ , 证明：

代入费马小定理：

证明完毕，实现代码参考附录【离散对数零知识证明Python实现】。

基于 Schnorr 的 ZKP

Alice -> Bob: $C = g^x \mod p$, $t = g^k \mod p$

Bob -> Alice: $c \in [0, p-1]$

Alice -> Bob: $s = k + c\cdot x \mod (p-1)$

Bob Verify: $g^k \mod p = g^s \cdot C^{-c} \mod p$

Python 代码示例：

x = random.randint(1, p-1)
alice = Alice(x)
alice.k = random.randint(1, p-1)
bob = Bob(alice.Cx)

# Alice -> Bob
gk = pow(g, alice.k, p)

# Bob -> Alice
bob.c = random.randint(1, p-1)

# Alice -> Bob
s = (alice.k + bob.c * alice.x ) % (p-1)

# Bob Verify
gk1 = (pow(g, s, p) * pow(alice.Cx, -bob.c, p)) % p
print(gk1, gk, gk1 == gk)

Alice 会不会作弊？

Bob 会不会破解出 x ？

常见问题

1. Bob 有没有可能通过验证过程推测信息 x ？

答：由于 Alice 并不知道每次 Bob 要发送什么挑战，所以除非 Alice 连续蒙对 100 次 Bob 要发送的挑战，否则就无法伪装。 而连续蒙对 100 次的概率为 $\frac{1}{2^{100}}$，可以认为无法实现。 实际应用中，可以通过增加循环次数来进一步增加安全性。

2. Alice 同时告知 r 和 x_plus_r_mod_p_minus_1，Bob 有没有可能推测出 x ？

答：可以，$x = (answer - r) \mod (p-1)$。

如何对数据 $C_x = g^x \mod p$ 进行加减？

比如 Bob 这本来存的是 x， Alice 现在想更新到 (x+t)。

如果 t 是负数的话，可以通过求模反元素的方式求得。所以这里只需要 Alice 传递一个 $C_t = g^t \mod p$ 即可。实现代码参考【加减法】。

在加减法中，如何证明 $C_x > 0$ ？

将 x 表示为二进制形式：$x = \sum x_i \cdot 2^i$ 。

要使用零知识证明 $x \ge 0$，则需证明：

• $x_i \in \{0, 1\}$
• $G_y = \prod G_{y_i}$

验证加和性

这里 $x_i$ 和 $r_i$ 是 x 和 r 拆分为二进制后的结果。

通过上述，将 x, r 拆分为二进制后挨个提出零知识证明，然后验证是否最终结果和 $C_x$ 一致即可。

验证布尔性

仅需证明 $P(X) = X \cdot (1 - X) = 0$ 成立即可。

代入离散对数公式：$C_{P(X)} = g^{P(X)} \cdot {h^r}$，则为：$C_{x_i \cdot (1-x_i)} = g^{x_i \cdot (1-x_i)} \cdot h^r$，因为 $x_i \in [0, 1]$，则 $x_i^2 = x_i$，那么：

附录

离散对数零知识证明Python实现

import random


p = 162259276829213363391578010288127   # 2^107 - 1
g = 5


class ChallengeType:
    WANT_R = 0
    WANT_M = 1


class Alice:
    def __init__(self, x: int):
        self.x = x

    @property
    def Cy(self):
        return pow(g, self.x, p)

    def send_r(self):
        self.r = random.randint(1, p-1)
        self.Cr = pow(g, self.r, p)
        return self.Cr

    def answer_challenge(self, challenge: dict):
        if challenge['type'] == ChallengeType.WANT_R:
            challenge.update(answer=self.r)
        elif challenge['type'] == ChallengeType.WANT_M:
            x_plus_r_mod_p_minus_1 = (self.x + self.r) % (p-1)
            challenge.update(answer=x_plus_r_mod_p_minus_1)
        else:
            raise ValueError(f"Invalid Challenge Type: {challenge}")

        return challenge


class Bob:
    def __init__(self, Cy):
        self.Cy = Cy

    def send_challenge(self, Cr):
        self.Cr = Cr
        challenge = dict(
            type=random.randint(0, 1),
            answer=None,
        )
        return challenge

    def verify(self, challenge: dict):
        if challenge['type'] == ChallengeType.WANT_R:
            r = challenge['answer']
            return pow(g, r, p) == self.Cr
        elif challenge['type'] == ChallengeType.WANT_M:
            x_plus_r_mod_p_minus_1 = challenge['answer']
            return pow(g, x_plus_r_mod_p_minus_1, p) == (self.Cy * self.Cr) % p
        else:
            raise ValueError(f"Invalid Challenge Type: {challenge['type']}")


if __name__ == '__main__':
    x = random.randint(1, p-1)
    alice = Alice(x)
    bob = Bob(alice.Cy)

    for i in range(100):
        r = alice.send_r()
        challenge = bob.send_challenge(r)
        challenge = alice.answer_challenge(challenge)
        assert bob.verify(challenge), f"Challenge {i} r={r} is not verified successfully."
    else:
        print("All challenges are verified successfully.")

加减法

class Alice:
    ...

    def transfer(self, transaction: dict):
        amount = transaction['amount']
        dst_x = self.x - amount
        return dict(
            src_Cy=pow(g, self.x, p),
            dst_Cy=pow(g, dst_x, p),
            Ct=pow(g, amount, p),
        )

class Bob:
    ...

    def verify_transfer(self, transaction: dict):
        src_Cy = transaction['src_Cy']
        dst_Cy = transaction['dst_Cy']
        Ct = transaction['Ct']
        return (dst_Cy * Ct) % p == src_Cy

if __name__ == '__main__':
    x = random.randint(1, p-1)
    alice = Alice(x)
    bob = Bob(alice.Cy)

    result = alice.transfer(dict(amount=100))
    print(f"Transfer result: {result}")
    print(f"Bob verify result: {bob.verify_transfer(result)}")

参考

• Bulletproofs