oumuamua-labs/hekate
GitHub: oumuamua-labs/hekate
基于二进制塔域的流式零知识证明引擎，以 O(N) 内存复杂度实现边缘原生客户端证明。
Stars: 9 | Forks: 1
# Hekate ZK Engine
[](https://github.com/oumuamua-labs/hekate/actions/workflows/ci.yml)
[](./LICENSE)
基于二进制塔域的零知识证明系统。流式架构。内存受限。边缘原生。
Hekate 使用 Sumcheck + Brakedown PCS 在 GF(2^128) 中证明计算，prover 时间复杂度为 O(N)，内存复杂度为 O(N)。没有 FFT，
没有 trace 实体化，不需要服务器级 RAM。可以在笔记本电脑和移动设备上证明 ML-KEM 解封装和 ML-DSA 签名
验证。
## ⚠️ 安全警告
此工作区尚未经过审计，可能包含 bug 和安全漏洞。
使用风险自负！
## 为什么开发 Hekate
当前的 ZK prover，RISC Zero、Plonky2、Plonky3、Binius、Stwo、Winterfell，在证明前会将完整的执行 trace 实体化到 RAM
中。大多数随后运行基于 FFT 的承诺（FRI, Circle FRI），在 trace 的基础上使内存膨胀 2 到 8 倍，
prover 时间复杂度为 O(N log N)。这种“单体 trace + FFT 膨胀”架构对内存施加了硬性下限：
真实工作负载需要 128GB 以上，仅在 2^20 规模下进行 Keccak 就需要 76GB (Binius)，在 2^24 规模下会导致 swap 死亡 (Plonky3)。
这一下限抹杀了客户端证明。没有移动设备、没有浏览器、没有边缘节点能够运行这些 prover。
Hekate 消除了这一下限。prover 以流式方式通过 trace，就地折叠，并丢弃中间状态。峰值
内存是按表限制的，而不是按计算限制的。2^24 的 Keccak 证明可以在消费级笔记本电脑上的 29.7 GB 内存中运行，而在此情况下 Binius
和 Plonky3 会崩溃或发生频繁交换（thrash）。
## Hekate 生态系统
Hekate 不仅仅是一个 crate。prover 是引擎；数学核心、硬件 chiplet、移动工具链
和 fuzzer 都作为独立的 crate 发布，您可以根据需要组合使用。
| Crate | 角色 |
|:-------------------------------------------------------------------------------------------|:------------------------------------------------------------------------------------------------------------|
| [`hekate-math`](https://github.com/oumuamua-labs/hekate-math) | 二进制塔域算术，常量时间，PMULL / PCLMULQDQ。数学核心。 |
| [`hekate-prover-sys`](https://github.com/oumuamua-labs/hekate/tree/main/hekate-prover-sys) | 开放 FFI 垫片。通过稳定的 C ABI 链接已签名的 prover cdylib；唯一可以调用 prover 的 crate。 |
| [`hekate-keccak`](https://github.com/oumuamua-labs/hekate/tree/main/hekate-keccak) | Keccak-f[1600] chiplet 以及 SHA-3 / SHAKE。虚拟打包，节省约 16 倍内存。 |
| [`hekate-aes`](https://github.com/oumuamua-labs/hekate/tree/main/hekate-aes) | 带有 S-box ROM 的 AES-128 / AES-256 轮函数 chiplet (FIPS 197)。 |
| [`hekate-pqc`](https://github.com/oumuamua-labs/hekate/tree/main/hekate-pqc) | ML-KEM 解封装和 ML-DSA 验证 (FIPS 203 / 204)，包含 NTT, basemul, norm-check。 |
| [`hekate-mobile`](https://github.com/oumuamua-labs/hekate-mobile) | 将 Rust prover 封装为带有强类型 Swift / Kotlin API 的已签名 iOS `.xcframework` / Android `.aar`。 |
| [`hekate-scribble`](https://github.com/oumuamua-labs/hekate/tree/main/hekate-scribble) | Trace 变异 fuzzer。篡改有效的 trace，如果您的约束遗漏了篡改则会引发 panic。 |
工作区内的 crate：`hekate-core`、`hekate-crypto`、`hekate-program`、`hekate-verifier`、
`hekate-sdk` 如上述技术栈所示。
## 它的功能
**二进制塔域算术**，GF(2^8) 到 GF(2^128)，递归塔扩展，通过
PMULL/CLMUL 进行硬件加速。默认常量时间。
**Chiplet 架构**，独立的 AIR 表（Keccak, AES, RAM, NTT, ML-KEM, ML-DSA），各自具有独立的 trace 和
承诺。没有列浪费，没有强制填充。表通过 LogUp bus 连接。
**虚拟打包**，Keccak 将 1600 位存储在 25 个物理 B64 列中，而不是 1600 个位列。位在寄存器中 JIT 展开。节省 16 倍内存。
**线性码承诺**，Brakedown PCS：O(N) prover，O(N) 内存。没有 FFT 膨胀。仅在编码列上进行 Merkle 树操作
（原始 trace 从不进行哈希处理，真正的 ZK）。
**后量子密码套件**，ML-DSA (Dilithium) 签名验证，ML-KEM (Kyber) 解封装，AES-128/256，
全部在二进制域中原生证明，没有位分解开销。
### 硬件支持
| 架构 | 状态 | 指令集 |
|:-------------|:-----------|:--------------------------------------|
| aarch64 | 生产环境 | PMULL, NEON |
| x86_64 | 回退方案 | 软件回退（PCLMULQDQ 在路线图中） |
| WASM | 计划中 | 软件乘法 |
## 快速示例
真正的 32 位整数 Fibonacci。CPU 侧持有五个列和两个 Fibonacci 递推
约束。每个 `u32` ADD 都被卸载到 `IntArithmeticChiplet`，它拥有独立的 trace、独立的
承诺、独立的 ZeroCheck、独立的 evaluation argument，并通过 LogUp bus 连接
（`(val_a, val_b, val_res, opcode, request_idx)` 作为带有行索引时钟的键）。
```
type F = Block128;
#[derive(Clone)]
struct FibProgram {
num_rows: usize,
}
impl Air for FibProgram {
fn num_columns(&self) -> usize {
CpuArithColumns::NUM_COLUMNS
}
fn column_layout(&self) -> &[ColumnType] {
static LAYOUT: std::sync::OnceLock> = std::sync::OnceLock::new();
LAYOUT.get_or_init(CpuArithColumns::build_layout)
}
fn boundary_constraints(&self) -> Vec> {
vec![BoundaryConstraint::with_public_input(
CpuArithColumns::VAL_B,
self.num_rows - 1,
0,
)]
}
fn permutation_checks(&self) -> Vec<(String, PermutationCheckSpec)> {
vec![(
IntArithmeticChiplet::BUS_ID.into(),
CpuIntArithmeticUnit::linking_spec(),
)]
}
fn constraint_ast(&self) -> ConstraintAst {
let cs = ConstraintSystem::::new();
let s = cs.col(CpuArithColumns::SELECTOR);
let val_b = cs.col(CpuArithColumns::VAL_B);
let val_res = cs.col(CpuArithColumns::VAL_RES);
let next_a = cs.next(CpuArithColumns::VAL_A);
let next_b = cs.next(CpuArithColumns::VAL_B);
cs.assert_boolean(s);
cs.constrain(s * (next_a + val_b)); // next_a = b
cs.constrain(s * (next_b + val_res)); // next_b = a + b (chiplet provides val_res)
cs.build()
}
}
impl Program for FibProgram {
fn num_public_inputs(&self) -> usize { 1 }
fn chiplet_defs(&self) -> errors::Result>> {
let arith = IntArithmeticChiplet::new(32, self.num_rows)?;
Ok(vec![ChipletDef::from_air(&arith)?])
}
}
```
Trace 生成独立构建 CPU 列和 chiplet trace；它们在 bus 上汇合。
```
fn generate_traces(num_rows: usize) -> errors::Result<(ColumnTrace, ColumnTrace, u32)> {
let num_vars = num_rows.trailing_zeros() as usize;
let mut tb = TraceBuilder::new(&CpuArithColumns::build_layout(), num_vars)?;
let mut ops: Vec = Vec::with_capacity(num_rows - 1);
let mut a: u32 = 0;
let mut b: u32 = 1;
for i in 0..num_rows - 1 {
let res = a.wrapping_add(b);
tb.set_b32(CpuArithColumns::VAL_A, i, Block32::from(a))?;
tb.set_b32(CpuArithColumns::VAL_B, i, Block32::from(b))?;
tb.set_b32(CpuArithColumns::VAL_RES, i, Block32::from(res))?;
tb.set_b32(CpuArithColumns::OPCODE, i, Block32::from(ArithmeticOpcode::ADD as u32))?;
tb.set_bit(CpuArithColumns::SELECTOR, i, Bit::ONE)?;
ops.push(IntArithmeticOp::U32 {
op: ArithmeticOpcode::ADD,
a,
b,
request_idx: i as u32,
});
a = b;
b = res;
}
// Padding row: selector = 0, val_b carries fib[N-1] for the boundary check.
tb.set_b32(CpuArithColumns::VAL_A, num_rows - 1, Block32::from(a))?;
tb.set_b32(CpuArithColumns::VAL_B, num_rows - 1, Block32::from(b))?;
let cpu_trace = tb.build();
let arith_layout = IntArithmeticLayout::compute(32);
let arith_trace = generate_arithmetic_trace(&ops, &arith_layout, num_rows)?;
Ok((cpu_trace, arith_trace, b))
}
```
Chiplet 通过进位强制执行 32 位 ADD，对其自身的 selector 进行布尔检查，并在其
行处于空闲状态时将其影子列置零。CPU AIR 只需要上述两个递推约束，
LogUp bus 保证对于 `s = 1` 的每一行，`val_res = a + b` 都成立。
连接程序、instance 和 witness，然后使用 `hekate-prover-sys` 进行证明，并使用
`hekate-verifier` 进行验证。Transcript 标签、`Config` 和矩阵种子必须在两端匹配，
driver 构建一个 `config` 并复用它。只有当所有 Sumcheck 轮次、
LogUp bus 求和以及 evaluation openings 都成立时，`verify` 才会返回 `true`。
```
fn run(num_rows: usize) -> errors::Result {
let (cpu, arith, fib_n) = generate_traces(num_rows)?;
let program = FibProgram { num_rows };
let instance = ProgramInstance::new(num_rows, vec![F::from(fib_n as u128)]);
let witness = ProgramWitness::new(cpu).with_chiplets(vec![arith]);
let mut config = Config::default();
OsRng.try_fill_bytes(&mut config.matrix_seed).unwrap();
let mut blinding_seed = [0u8; 32];
OsRng.try_fill_bytes(&mut blinding_seed).unwrap();
let proof = prove(
b"Fibonacci",
&program,
&instance,
&witness,
&config,
blinding_seed,
None,
)?;
let mut transcript = Transcript::::new(b"Fibonacci");
HekateVerifier::::verify(
&program,
&instance,
&proof,
&mut transcript,
&config,
)
}
```
## 示例
使用 `hekate-prover-sys` 进行证明并使用 `hekate-verifier` 进行验证的端到端程序。每个文件都是独立的
二进制文件，您可以通过 `cargo run --release --example ` 运行。
- [ML-DSA 签名验证](https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/mldsa.rs) (FIPS 204；
44 / 65 / 87 级别)
- [ML-KEM-768 解封装](https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/mlkem.rs) (FIPS 203)
- [AES-128 / AES-256 块证明](https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/aes.rs) (FIPS 197)
- [Keccak 内联内核](https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/keccak_inline.rs) (CPU AIR
带有嵌入式 f1600 置换)
- [32 位整数算术](https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/arith.rs) (通过 `IntArithmeticChiplet` 进行加 / 减 /
乘)
- [RAM 读/写证明](https://github.com/oumuamua-labs/hekate/blob/main/hekate/examples/ram.rs) (通过 `RamChiplet` 实现
离线内存一致性)
## 性能
所有数据均在 Apple M3 Max（16 核，48 GB RAM）上测得，`--release` 带 `-C target-cpu=native`，
特性为 `std parallel blake3 table-math`。在 `master` 分支的 commit 上使用 `hekate/examples/` 中的示例二进制文件进行测量。峰值 RSS 是进程的最大常驻内存大小（`/usr/bin/time -l`）。
复现：
```
RUSTFLAGS="-C target-cpu=native" cargo build --release \
--no-default-features --features "std parallel blake3 table-math" \
--example
/usr/bin/time -l target/release/examples/ []
```
### 后量子密码与 AES
| | ML-KEM-768 | ML-DSA-44/65 | ML-DSA-87 | AES-128 | AES-256 |
|:-------------|:-----------|:-------------|:----------|:----------|:----------|
| 证明 | 945.36 ms | 1.8 s | 2.95 s | 1.68 s | 1.80 s |
| 验证 | 12.4 ms | 18.6 ms | 23.3 ms | 8.8 ms | 9.4 ms |
| 证明大小 | 2,831 KiB | 3,510 KiB | 4,415 KiB | 2,856 KiB | 3,027 KiB |
| 峰值 RSS | 393 MB | 435 MB | 786 MB | 854 MB | 1,256 MB |
| Chiplets | 6 | 7 | 7 | 2 | 2 |
Chiplet trace 大小：
- ML-KEM-768：Ctrl 2^16，Keccak 2^11，NTT 2^15，TwiddleROM 2^15，Basemul 2^12，RAM 2^16。
- ML-DSA-44 / ML-DSA-65：Ctrl 2^16，Keccak 2^13，NTT 2^16，TwiddleROM 2^16，NormCheck 2^11，HighBits 2^11，RAM 2^16。
- ML-DSA-87 将 Ctrl 和 Keccak 翻倍：2^17 / 2^14。
AES 注意：AES-128 和 AES-256 每次运行都会证明 **31,250 个区块**（约 500 KB 明文）。
CPU trace 为 2^16 行；Round-AIR 和 S-box ROM chiplet 为 2^19。每区块证明成本：约 69 µs (AES-128) / 约 73 µs (AES-256)。
### Keccak-f[1600]，扩展
`hekate/examples/keccak_inline.rs `，默认为 20。
| 规模 (行数) | 置换次数 | 已哈希 | 证明 | 验证 | 证明大小 | 峰值 RSS |
|:-------------|:-------------|:--------|:---------|:--------|:-----------|:----------|
| 2^15 | 1,310 | ~178 KB | 455 ms | 4.1 ms | 642 KiB | 143 MB |
| 2^20 | 41,943 | ~5.4 MB | 10.77 s | 11.9 ms | 3,424 KiB | 2,561 MB |
| 2^24 | 671,088 | ~91 MB | 187.10 s | 44.3 ms | 13,403 KiB | 23,447 MB |
### Fibonacci（32 位整数加法），扩展
`hekate/examples/fibonacci_raw.rs `，默认为 24。每一行：带
显式进位链的位切片 32 位加法，虚拟扩展为 32 个位 + 32 个和 + 32 个进位列。
| 规模 (行数) | 证明 | 验证 | 证明大小 | 峰值 RSS |
|:-------------|:----------|:--------|:-----------|:----------|
| 2^20 | 583.62 ms | 5.1 ms | 647 KiB | 138 MB |
| 2^24 | 8.54 s | 19.1 ms | 2,499 KiB | 1,805 MB |
| 2^26 | 35.41 s | 40.0 ms | 4,951 KiB | 6,972 MB |
## 入门指南
- [安装](https://oumuamua.dev/hekate/docs/getting-started/installation)，从源码构建，配置特性
- [你的第一个 ZK 程序](https://oumuamua.dev/hekate/docs/getting-started/your-first-zk-program)，端到端的
首次证明
- [架构](https://oumuamua.dev/hekate/docs/basics/system-architecture)，二进制塔域，Sumcheck，Brakedown，
LogUp
- [编写 AIR 约束](https://oumuamua.dev/hekate/docs/basics/air-constraints)，约束 DSL，边界
条件
- [Chiplets](https://oumuamua.dev/hekate/docs/basics/cryptographic-chiplets)，独立的表，虚拟打包，bus
集成- [安全](https://oumuamua.dev/hekate/docs/advanced/soundness-and-security)，威胁模型，对抗性测试套件，
Fiat-Shamir 绑定
## 许可证
Apache-2.0。请参阅 [LICENSE](LICENSE) 和 [NOTICE](NOTICE)。
标签：可视化界面, 后量子密码学, 密码学, 手动系统调用, 数学核心算法, 流式架构, 边缘计算, 通知系统, 零知识证明