Hekate v0.29.1

Consolidated notes for the 0.29 series, 0.29.0 and 0.29.1. 0.29.0 shipped without separate notes, so this covers both.

This is a breaking release. The fixed-column migration changed the wire format, program_id, and proof encoding: bundles and proofs from earlier releases no longer deserialize or verify. Rebuild the prover cdylib (0.6.1) and re-prove. Headlines: two constant-time fixes close side-channel oracles in the AES and ML-KEM proving paths, fixed (preprocessed) columns pin committed data to a cryptographically verified shape, verification is 2 to 4 times faster, the standalone chiplet crates fold into one workspace, and prover cdylib 0.6.1 proves faster and emits smaller Keccak proofs.

Upgrade priority: high. The timing fixes remove real key-recovery surface for anyone proving AES or ML-KEM on shared or multi-tenant hardware, and the wire and program_id change means a migration is required either way.

§ Security hardening

Two witness-generation paths leaked secret-dependent timing. Both are now branchless and table-free. Neither touches the AIR, the committed trace, the wire format, or program_id.

AES S-box: cache-timing key-recovery oracle removed. SubBytes was computed through a 256-entry SBOX[byte] lookup. During proving that index is a key or state byte, so the lookup is the textbook AES cache-timing side channel: an attacker at cache-line resolution recovers the key. SubBytes is now field arithmetic, the GF(2^8) inverse x^254 followed by the FIPS 197 affine map, with no key-dependent table index, branch, or memory access. Output values are identical to the FIPS 197 table across all 256 inputs, and the committed trace is byte-for-byte the same.

ML-KEM decapsulation: Fujisaki-Okamoto branch oracle removed. The implicit-rejection step (FIPS 203 section 6.3) selected the shared secret with a secret-dependent branch, if ct_match { K' } else { K̄ }. A branch on the re-encryption comparison is an FO decapsulation oracle. The comparison and selection are now branchless: a constant-time mask derived from all 32 hash bytes drives K' & mask | K̄ & !mask, with no data-dependent control flow.

Soundness caps stated explicitly. Integrators must size trust against the ZK layer, not only the underlying primitive. Both are now documented in the crate READMEs:

• AES-256: proof soundness is field-capped at approximately 128 bits, an AES-256 proof binds at about 2^-128, not 2^-256. The proven ciphertext is still full AES-256; AES-128 is matched.
• Post-quantum: a proof binds at about 2^-128 regardless of parameter set. For ML-KEM-768 and 1024 and ML-DSA-65 and 87, the ZK proof, not the lattice scheme, is the weaker link. ML-KEM-512 and ML-DSA-44 are matched. The proven decapsulation and verification remain the full FIPS 203 and 204 parameter sets.

§ Fixed (preprocessed) columns

The single-row boundary pin is generalized into a fixed column constrained to any row-indexed shape: Periodic, Sparse, or Dense, plus the FirstRow / LastRow / Custom indicators. A fixed column is discharged by recomputing the shape's multilinear extension at the verifier's final challenge and asserting equality: one equality at one post-commitment random point pins every row by Schwartz-Zippel. This replaces the previous Lagrange-pin machinery (LagrangePoint, LagrangePin, lagrange_pinned_columns()).

Preprocessed and selector columns are now committed and bound cryptographically at O(1) verifier cost instead of carried as per-row boundary terms. The RAM chiplet is migrated (Q_STEP and Q_FIRST become last_row / first_row fixed columns) with identical constraint behavior. program_id hashes each shape under a distinct tag, so distinct shapes are never collision-equal.

This is the change that breaks the wire format, program_id, and proof bytes; see Breaking changes below.

§ Performance

Verification is 2 to 4 times faster. The TensorPCS proximity check and Merkle verification are parallelized over rayon, now the verifier default with a single-threaded fallback retained; the expander matrix is cached by (width, degree, seed); and a redundant basis conversion is removed. Measured speedups on Apple M3 Max: Keccak 2^15 4.4x, ML-DSA 3.0x, ML-KEM and AES 2.2x. Current verify latencies range 4 to 23 ms across the example circuits. Verifier-side only, no proof, wire, or program_id change.

Proving is 22 to 27 percent faster on the post-quantum and Keccak circuits with prover cdylib 0.6.1, at production blinding (sumcheck_blinding_factor = 2), Apple M3 Max, aarch64:

Keccak scaling shows the same trend: 2^15 858 to 455 ms, 2^20 14.68 to 10.77 s, 2^24 253.95 to 187.10 s.

Keccak proofs are 14 to 16 percent smaller. 2^15 drops 1,530 to 1,312 KiB and 2^20 drops 6,105 to 5,156 KiB; the 2^24 proof is unchanged. Verification time and peak heap are unchanged.

Preflight diagnostics are about 5 times faster. The debug-time constraint checker hoisted a loop-invariant tower-to-hardware basis conversion out of the per-row AST loop (it was reconverting every constant on every row, over 1,600 conversions per row on a Keccak chiplet). Zero cost when preflight is not called; no effect on proving or verifying.

§ Workspace and architecture

Chiplet crates consolidated into one workspace. hekate-keccak, hekate-aes, hekate-pqc, and hekate-scribble (renamed from zk-scribble) are now workspace members instead of standalone repos pinned through crates.io. The old layout forced two semver-incompatible hekate-math versions into the tree, breaking every cross-crate field type; as path members they collapse to a single hekate-math and make future bumps atomic. The crates remain independently publishable.

Expander-matrix sampler moved to hekate-crypto. The degree-regular binary expander-matrix generator and its AES-256-CTR PRG now live beside the Merkle tree, the other Brakedown building block. Which oracle draws the matrix from a seed governs the linear code's distance, so it is a PCS soundness parameter and belongs in the commitment layer, not the field-arithmetic crate. The relocated generator is bit-identical to the version it replaced, so prover and verifier derive the same matrix and proofs are unaffected. It ships behind a new optional expander feature; the cipher and RNG dependencies are now optional and pulled only when that feature is on, so hash-only consumers no longer compile code they never call.

Post-quantum chiplet sizing derived from the security level. MlKemChiplet::new and MlDsaChiplet::new drop the params argument and derive trace dimensions from the level. The per-level sizing tables duplicated across test and example helpers collapse into one production source, and the never-validated defaults that could select an undersized trace are gone. Sizing is public and honest witnesses occupy the same rows, so this changes no proof.

ReuseExpandBits virtual-expansion variant. Adds bit-expansion of a reused physical column, the inverse of the Keccak wide-plus-bits shape. Additive and self-contained: no chiplet consumes it yet, the prover binary is unchanged, and every existing program is byte-for-byte unaffected. The program_id of any program that does not use the variant is unchanged.

§ Dependencies and security advisories

• hekate-math upgraded to 0.8.0.
• Post-quantum test and reference dependencies migrated from the unmaintained pqcrypto-* PQClean bindings to pure-Rust RustCrypto ml-kem 0.3 and ml-dsa 0.1, closing RUSTSEC-2026-0161, 0162, 0163, and 0166; yanked aes 0.9.0 bumped to 0.9.1. Dev and build dependency only, no library API, wire, program_id, or proof change; cargo deny check is clean with no advisory ignores.
• Prover cdylib pinned to 0.6.1, signed and verified at build time (SHA-256 plus Ed25519 plus ML-DSA-65). Source of the proving and Keccak proof-size gains above.
• Each crate carries a standalone Apache-2.0 LICENSE and NOTICE, so every published crate is self-contained.

§ Breaking changes and upgrade

Proofs, bundles, and program_id. The fixed-column migration reworked the wire format and the program_id hash and stopped emitting per-row boundary terms for pinned columns, so the round polynomials differ. Bundles written by the prior format do not deserialize, existing proofs no longer bind, and prover cdylib 0.6.1 additionally emits smaller Keccak proofs. Rebuild the cdylib and re-prove; a proof is matched to the prover and verifier pair that produced it.

Public API. Consumers must update:

• hekate-program: LagrangePoint, LagrangePin, lagrange_pinned_columns(), and validate_lagrange_pins() are removed in favor of FixedShape, FixedColumn, and fixed_columns(). ConstraintAst::evaluate_into gains a leading consts: &[Flat<F>] argument, obtained from precompute_hardware_consts(); evaluate() is unchanged.
• hekate-verifier: HekateVerifier::verify now requires P: Program<F> + Sync; EvalVerifyContext's row parser becomes a &RP: VirtualRowParser<F>, and VirtualRowParser and RowParseScratch are public. parallel is now a default feature.
• hekate-pqc: MlKemChiplet::new and MlDsaChiplet::new take only the level; the params argument, the params() getter, and the public MlKemParams / MlDsaParams types are removed.
• hekate-aes: the public SBOX table is removed; the S-box is derived arithmetically.
• hekate-crypto: new optional expander feature; aes and rand are now optional dependencies. Enable expander to sample the Brakedown matrix directly. The verifier and the integration crate enable it automatically.

Crate renames and versions. zk-scribble is renamed hekate-scribble; hekate-keccak and hekate-aes go 0.1 to 0.2, hekate-pqc 0.2 to 0.3, and the workspace 0.28 to 0.29.

Program identity within the 0.29 line. The 0.29.1 security fixes are trace-identical for AES and branchless-equivalent for ML-KEM, the post-quantum sizing change derives dimensions production already used, and the expander relocation is bit-identical. These do not change program_id; the wire and program_id break is entirely the fixed-column migration.