公开两个图 $ G_0 $ 和 \(G_1\)，证明者（Prover，简称 P）知道一个秘密的置换（映射）$ \phi $，使得通过对 $ G_0 $ 的顶点进行重排，可以完全变成 $ G_1 $，即 $ G_1 = \phi(G_0) $。证明者需要向验证者（Verifier，简称 V）证明这一点，但绝不泄露 $ \phi $ 的任何信息。
标准三轮零知识流程（由 Goldreich, Micali 和 Wigderson 于 1991 年提出）：
第一轮：承诺阶段（Commitment）
证明者 P 随机选取一个临时的置换 $ \pi $（仅本次会话使用），将 $ G_0 $ 的顶点随机打乱，生成一个与 $ G_0 $（也必然与 $ G_1 $）同构的中间图（中介图） $ H $
P 将计算出的图 $ H $（包含所有顶点和边的邻接信息）作为“承诺值”发送给验证者 V。
此时 P 的逻辑：P 必须足够聪明，确保无论 V 接下来问什么，P 都能拿出对应钥匙。因为 P 同时知道 $ G_0 \to H $ 的映射（即 $ \pi $），也暗暗知道 $ H \to G_1 $ 的映射（即 $ \pi \circ \phi^{-1} $）。
第二轮：挑战阶段（Challenge）
验证者 V 收到中间图 $ H $ 后，随机抛出一枚公平的硬币，选取一个挑战值 $ b \in {0, 1} $，并将 $ b $ 发送给 P。
- 如果 $ b = 0 $：V 要求 P 证明 $ H $ 与 $ G_0 $ 同构。
- 如果 $ b = 1 $：V 要求 P 证明 $ H $ 与 $ G_1 $ 同构。
第三轮：响应阶段（Response）
P 根据收到的挑战值 $ b $，给出对应的“钥匙”（置换映射），但绝不直接交出原始的 $ \phi $：
- 若 $ b = 0 $：P 直接发送先前生成的随机置换 $ \pi $。V 验证 $ H $ 是否等于 $ \pi(G_0) $。若成立，说明 $ H \cong G_0 $。
- 若 $ b = 1 $：P 发送复合置换 $ \rho = \pi \circ \phi^{-1} $（即先执行 $ \phi^{-1} $ 将 $ G_1 $ 变回 $ G_0 $，再执行 $ \pi $）。V 验证 $ H $ 是否等于 $ \rho(G_1) $。若成立，说明 $ H \cong G_1 $。
验证与安全性分析
1. 完备性（Completeness）：
如果 P 诚实地知道 $ \phi $，无论 V 抛出 $ b=0 $ 还是 $ b=1 \(，P 总能算出对应的映射（\) \pi $ 或 $ \rho $）并成功通过验证，V 绝对接受。
2. 可靠性（Soundness）/ 防欺骗：
如果 P 不知道 $ \phi $（试图作弊），他在第一轮只能针对一个方向准备 $ H $。
- 若 P 准备 $ H $ 仅能应对 $ b=0 $（即知道 $ \pi $），当 V 抛出 $ b=1 $ 时，P 无法给出合法的 $ \rho $，当场被抓。
- 若 P 准备 $ H $ 仅能应对 $ b=1 $，当 V 抛出 $ b=0 $ 时，P 同样失败。
因为 V 的挑战是完全随机的，所以作弊者一次通过的概率恰好是 $ \frac{1}{2} $。
3. 零知识性（Zero-Knowledge）/ 不泄露信息：
无论 V 收到哪个响应（$ \pi $ 或 $ \rho $），这些响应都只是随机均匀分布的置换。
- 当 $ b=0 $ 时，V 看到的是一个随机置换 $ \pi $，与秘密 $ \phi $ 毫无数学关联。
- 当 $ b=1 $ 时，V 看到的是 $ \rho $，由于 $ \pi $ 是完全随机的，$ \rho $ 也呈现为均匀随机分布，V 无法从中倒推出原始的 $ \phi $。
V 拿到的所有信息，都是他自己早已公开知道的两图同构这一事实，没有任何关于“如何映射”的额外知识。
如何将错误概率降至可忽略（Negligible）？
单轮交互的欺骗概率高达 $ \frac{1}{2} $，这在密码学上不可接受。通常，该协议需要并行或重复执行 $ t $ 次（例如 $ t = 80 $ 或 $ 128 $ 次）。
- 每一轮都独立随机选取新的 $ \pi $，重新生成全新的 $ H $。
- 只有在 所有 $ t $ 轮 都通过验证时，V 才最终相信 P。
此时，作弊者成功欺骗的概率降为：
当 $ t=128 $ 时，该概率小到现实世界中完全不可行（远低于暴力破解的难度）。
该协议的重要提示与变体
- 零知识性仅对“诚实验证者（Honest-Verifier）”严格成立。如果验证者恶意选择挑战 $ b $（非随机，例如根据 $ H $ 的结构挑选），可能会诱骗 P 泄露额外信息。但标准密码学假设中，通过将交互式协议转换为非交互式（Fiat-Shamir 启发式），可以消除这一风险。
- 复杂度考量：虽然图同构本身尚未被证明是 NP 完全问题（它可能是 NP 中间态），但该 ZKP 协议的计算开销主要在于顶点置换和图的比较，对于大规模图（成千上万个顶点），通信量（需传输完整邻接矩阵）是巨大的工程瓶颈。