Poseidon.md

Poseidon

论文地址

条件：在 ZK 证明系统里，电路的成本单位不是「CPU 周期」，而是约束数（R1CS constraints，本质是乘法门数量）。

设计目标：用尽可能少的域乘法，构造一个安全的哈希。加法和常数乘法在 R1CS 里几乎免费，只有变量×变量才要付钱。

MiMC 的痛点

MiMC 每一轮只用一个 S-box $x^3$ 作用在整个状态上。为了让代数次数（algebraic degree）增长到足够高以抵抗插值攻击、Gröbner 基攻击，MiMC 需要很多轮——因为每轮只把次数乘以 3，且状态窄（只有 1 个元素），"稀释"次数的空间很小。

POSEIDON 想让状态变宽（t≥2，甚至几十），这样一次置换能处理更多输入/输出，对海绵结构（sponge）和 Merkle 树更友好。但状态一宽，如果像经典 SPN（比如 AES）那样每轮都对所有 t 个格子做 S-box，约束数（R1CS 里的乘法门数）会随 t 线性增长，代价太大。

Sponge 结构

作用：变长输入 → 定长输出：不管消息多长，都能切块吸收；不管想要多少输出，都能反复挤出。这是它最直接的功能。

结构：把宽度为 t（对应 N 比特左右）的置换的状态切成两部分： rate（吞吐率） r：负责"进出数据"的部分 capacity（容量） c：不直接暴露给外部，负责"藏安全性"的部分

过程：

1. 初始状态全 0
2. 吸收阶段（absorbing）：把消息切成 r 大小的块，每次把一块异或/加到状态的 rate 部分，然后跑一次置换 P；重复直到消息吸收完
3. 挤出阶段（squeezing）：从状态的 rate 部分读出输出；如果需要更多输出，再跑一次置换继续挤

HADES 结构

问题：为了抗统计类攻击（查分，线性），要求充分扩散，传统的方法是每轮所有格子都过S-box，成本高。但如果要省成本，就要减少S-box，容易被插值攻击 / Gröbner 基攻击打穿，需要非常多轮才能补回来

结构：混合两种轮，一部分轮用全 S-box 层扛统计攻击，另一部分轮用部分 S-box 层（省成本）扛代数攻击