CH1

直觉

Step 1 / 17
P Prover · 证明者 "我知道某个秘密 X" V Verifier · 验证者 "那你证明给我看" I know X. How do I prove it without telling you X? Ali Baba 洞穴 路径 A 路径 B 🔒 魔法门 · 需要密码 只有知道密码才能从一边穿到另一边 P 入口 挑战: 从 X 路出来! 骗子蒙混概率 n 轮后 ≤ 2⁻ⁿ 10 轮 ≈ 0.1%, 20 轮 ≈ 0.0001% Verifier 学到了什么? 仅: "P 知道密码" 密码本身: 一无所知 证明知识 vs 出示知识 —— 想个反直觉的中间路 Quisquater 1990 · Ali Baba 洞穴：用 challenge-response 把"知识"概率性地证明出来 ✓ Completeness 完备性 · 诚实者一定通过 Pr[V accepts | true stmt] ≥ 1 − ε 真陈述 + 诚实 Prover → 几乎一定接受 ✗ Soundness 可靠性 · 假陈述骗不过 Pr[V accepts | false stmt] ≤ 2⁻ⁿ 没 secret 的人 n 轮挑战通过率指数级衰减 1 ✗ 3 ✗ 5 ✗ 7 ✗ 9 ✗ 10 轮挑战，假 Prover 命中 ≈ 50%；100 轮后：2⁻¹⁰⁰ ≈ 不可能 🔒 Zero-Knowledge 零知识 · 证完啥也没漏 Verifier 视角 ≈ Simulator 视角 无 witness 的 Simulator 也能造出"看似真的"对话 t₁ c₁ s₁ t₂ c₂ s₂ 真实 transcript 👻 Simulator 无 witness 也能造出 分布相同的对话 反面教训 某些 SNARK 实现因约束写漏 → 诚实 Prover 偶尔被拒 = 完备性挂掉 第一根支柱：诚实证明者必须能通过 第二根支柱：作弊者通过率指数级衰减 第三根支柱：Verifier 一无所获 —— Simulator 范式 P Prover witness x V Verifier public h 公开陈述: h = g^x ∈ G ① commit t = g^r　(r 随机) ② challenge c　(随机) ③ response s = r + c·x　(mod q) "我让你随便挑一个 c，我都能在不暴露 x 的前提下给出对应的 s" Verifier 检查 g^s ?= t · h^c ✓ accept 一次乘法 + 一次幂运算 假设同一个 t 对应两个有效回答: (c₁, s₁): g^s₁ = t · h^c₁ (c₂, s₂): g^s₂ = t · h^c₂ ⟹ x = (s₁ − s₂) · (c₁ − c₂)⁻¹ (mod q) → Knowledge Extractor 拿到 witness ② challenge · 由 hash 取代 c = H(g, h, t) 本地 hash anyone, anytime 无需在线交互 非交互证明 π π = (t, s) ⚠️ r 必须每轮新鲜随机 两次复用同 r → 立即解出 x 真实事故: 2010 PS3 ECDSA Schnorr 三步握手：commit → challenge → response，最经典 Σ-protocol 一行等式同时蕴含 completeness + soundness Special Soundness：两个不同 c 的合法回答 → 抽出 witness x Fiat–Shamir：用 hash 当虚拟 Verifier，握手 → 单条非交互证明 Pedersen Commitment c = g^x · h^r x: 隐藏的值　·　r: 随机盲化因子 Hiding · 看不出 x r 均匀随机 → c 在群里也均匀随机 Binding · 改不了 x 想换成 (x', r') 让 c 不变 = 解 DLP，做不到 所有 ZKP 系统的"信封"基石：先 commit，后 reveal / 后 prove ① 算术电路 × + × ② R1CS A·s ∘ B·s = C·s 三矩阵 A,B,C + 见证向量 s ∘ 是逐元素积 (Hadamard) ③ 多项式恒等式 P(x) 随机点 z 取值检零 Schwartz–Zippel Pr[err] ≤ d / |F| d=多项式度数 额外彩蛋: 加法同态 commit(x₁,r₁) · commit(x₂,r₂) = commit(x₁+x₂, r₁+r₂) ⟹ Bulletproofs / Groth16 范围证明的关键基石 Pedersen Commitment：藏值 + 不可改 + 可后续打开 —— ZKP 的"信封" 算术化第一步：把"我知道 x" 翻译成 R1CS 约束 第二步：R1CS → 多项式恒等式，靠 Schwartz–Zippel 在随机点检验 Trusted Setup · MPC ceremony 每人贡献随机性，最后销毁自己那份 🔥 toxic waste 必须销毁 prove π = (A, B, C) 3 群元素 ≈ 200 bytes verify ⏱️ ~5 ms Verifier 端验证耗时 zk-STARK Scalable · Transparent · No trusted setup 仅依赖 hash + Reed-Solomon proof 大但 post-quantum 安全 ↑ 详细对比见下方表格 vs. SNARK 真实仪式实例 Zcash Sapling: 90+ 人贡献 Filecoin: 1000+ 人级别 MPC zk-SNARK · Groth16：trusted setup → 200 字节 proof + ms 级 verify zk-STARK：transparent + post-quantum，但 proof 较大 Zcash Shielded Transaction from ▓▓▓▓▓▓▓▓ to ▓▓▓▓▓▓▓▓ amount ▓▓▓▓▓▓▓▓ Verifier 验账本仍能确认: balance ✓　no double-spend ✓　ownership ✓　all without seeing the data ZK-Rollup (L2 → L1) 1000 笔 L2 交易 π L1 block 把"算"留在 L2，把"证"提交到 L1 DECO · 隐私预言机 (Chainlink) HTTPS 原始数据 DECO oracle 本地生成证明 on-chain π 链上验证 数据不上链，证明上链 六章思维导图 · ZKP 拼图完整一览 ZKP you are here 🕳️ CH1 直觉 Ali Baba 洞穴 ⚖️ CH2 三性质 C / S / ZK 🤝 CH3 Schnorr Σ + Fiat-Shamir 🔢 CH4 算术化 R1CS + Pedersen ⚡ CH5 SNARK/STARK 简洁 + 非交互 🌍 CH6 应用 Zcash / Rollup / DECO Zcash · 隐藏 from / to / amount，仍可证账本守恒 两大应用：ZK-Rollup 压缩 L2 + DECO 隐私预言机