零知识证明学习

241219 阅读《Chameleon-Hashes with Ephemeral Trapdoors And Applications to Invisible Sanitizable Signatures》遇到了 NIZKPoK，故学习一下

NIZKPoK#

Non-Interactive Zero-Knowledge Proof 非交互零知识证明

论文中的体现#

\begin{align} &Generate\ \pi\leftarrow NIZKPoK\{(x):h=g^x\}\\ &if\ \pi\ is\ not\ valid, return\perp \end{align}

解释#

证明着想要证明自己知道某个值 $x$，而不透露 $x$ 本身

Fiat-Shamir 变换（简化的非交互证明）#

初始化：$g$ 和 $h$ 是公开的参数，$x$ 是秘密（证明者知道它）
生成证明：随机选择一个随机值 $r$，计算承诺值 $t=h*g^r$
计算挑战：生成一个挑战 $c$（通常通过哈希函数生成）
计算响应：计算 $z=r+c*x$
发送证明：发送三元组 $(t,c,z)$
验证：验证者检查是否满足 $g^z=t*h^c$

实验代码#

#这份是手搓的，放进代码复现成功
def gen_NIZK( g , x , p ):
    h = pow( g , x , p )
    r = random.randint( 1 , p )
    t = pow( g , r , p )
    c = SM3("窝丝一个挑战")
    z = r+c*x
    return (t,c,z),(g,p,h)

def verf_NIZK( pi ):
    ( t , c , z ) , ( g , p , h ) = pi
    if pow( g , z , p ) == t * pow( h , c , p ) % p:
        return True
    return False

完整代码

#这份是gpto1写的，不过是基于椭圆曲线的
from ecdsa import SECP256k1, SigningKey, VerifyingKey
import hashlib

# 曲线参数
curve = SECP256k1
G = curve.generator  # 基点 g
n = curve.order      # 阶

# 私钥 x（随机生成）
x_sk = SigningKey.generate(curve=curve)
x = x_sk.privkey.secret_multiplier  # x 的数值
# 公钥 h = g^x
h_vk = x_sk.verifying_key
h = h_vk.pubkey.point

def nizkpok_prove(x):
    # 证明者生成随机数 r
    r_sk = SigningKey.generate(curve=curve)
    r = r_sk.privkey.secret_multiplier
    # 计算承诺 t = g^r
    t = r * G
    # 计算挑战 e = Hash(g || h || t)
    e = hashlib.sha256()
    e.update(int(G.x()).to_bytes(32, 'big') + int(G.y()).to_bytes(32, 'big'))
    e.update(int(h.x()).to_bytes(32, 'big') + int(h.y()).to_bytes(32, 'big'))
    e.update(int(t.x()).to_bytes(32, 'big') + int(t.y()).to_bytes(32, 'big'))
    e_int = int(e.hexdigest(), 16) % n
    # 计算响应 s = r + e * x mod n
    s = (r + e_int * x) % n
    return (e_int, s)

def nizkpok_verify(h, proof):
    e_int, s = proof
    # 计算 t' = g^s + (-h^e)
    sG = s * G
    eH = e_int * h
    # 获取 eH 的负元
    neg_eH = (n - 1) * eH
    # 计算 t' = sG + (-eH)
    t_prime = sG + neg_eH
    # 重新计算挑战 e' = Hash(g || h || t')
    e_prime = hashlib.sha256()
    e_prime.update(int(G.x()).to_bytes(32, 'big') + int(G.y()).to_bytes(32, 'big'))
    e_prime.update(int(h.x()).to_bytes(32, 'big') + int(h.y()).to_bytes(32, 'big'))
    e_prime.update(int(t_prime.x()).to_bytes(32, 'big') + int(t_prime.y()).to_bytes(32, 'big'))
    e_prime_int = int(e_prime.hexdigest(), 16) % n
    # 验证 e 是否等于 e'
    return e_int == e_prime_int

# 生成证明
proof = nizkpok_prove(x)

# 验证证明
is_valid = nizkpok_verify(h, proof)
print("证明是否有效：", is_valid)