hekate_program/
digest.rs

1// SPDX-FileCopyrightText: 2026 Andrei Kochergin <andrei@oumuamua.dev>
2// SPDX-FileCopyrightText: 2026 Oumuamua Labs <info@oumuamua.dev>
3// SPDX-License-Identifier: AGPL-3.0-only
4
5use crate::chiplet::ChipletDef;
6use crate::constraint::{BoundaryTarget, ConstraintAst, ConstraintExpr, ExprId};
7use crate::expander::ExpansionEntry;
8use crate::permutation::{BusKind, PermutationCheckSpec, Side, Source};
9use crate::{Air, FixedColumn, FixedShape, InlineKernelHint, Program};
10use alloc::string::String;
11use alloc::vec::Vec;
12use hekate_core::errors;
13use hekate_core::trace::ColumnType;
14use hekate_crypto::{DefaultHasher, Hasher};
15use hekate_math::TowerField;
16
17/// Chunk size only:
18/// the byte stream, hence the digest, is independent of it.
19const FLUSH_BYTES: usize = 64 * 1024;
20
21struct Absorb {
22    hasher: DefaultHasher,
23    buf: Vec<u8>,
24}
25
26impl Absorb {
27    fn new() -> Self {
28        Self {
29            hasher: DefaultHasher::new(),
30            buf: Vec::with_capacity(FLUSH_BYTES + 64),
31        }
32    }
33
34    fn update(&mut self, bytes: &[u8]) {
35        self.buf.extend_from_slice(bytes);
36
37        if self.buf.len() >= FLUSH_BYTES {
38            self.hasher.update(&self.buf);
39            self.buf.clear();
40        }
41    }
42
43    fn finalize(mut self) -> [u8; 32] {
44        self.hasher.update(&self.buf);
45
46        self.hasher.finalize()
47    }
48}
49
50/// Deterministic 32-byte structural ID. Witness-independent,
51/// num_rows-independent. Same program shape -> same ID.
52pub fn program_id<F: TowerField, P: Program<F>>(program: &P) -> errors::Result<[u8; 32]> {
53    Ok(program_id_of(
54        program,
55        &program.chiplet_defs()?,
56        &program.inline_chiplets()?,
57    ))
58}
59
60/// Hex-encoded `program_id` (64 lowercase chars, no prefix).
61pub fn program_id_hex<F: TowerField, P: Program<F>>(program: &P) -> errors::Result<String> {
62    const HEX: &[u8; 16] = b"0123456789abcdef";
63
64    let bytes = program_id::<F, P>(program)?;
65
66    let mut s = String::with_capacity(64);
67    for &b in bytes.iter() {
68        s.push(HEX[(b >> 4) as usize] as char);
69        s.push(HEX[(b & 0xf) as usize] as char);
70    }
71
72    Ok(s)
73}
74
75pub fn program_id_of<F: TowerField, P: Program<F>>(
76    program: &P,
77    chiplet_defs: &[ChipletDef<F>],
78    inline_chiplets: &[ChipletDef<F>],
79) -> [u8; 32] {
80    let mut h = Absorb::new();
81    h.update(b"hekate-program-id-v2");
82
83    let main_name = program.name();
84    h.update(&(main_name.len() as u64).to_le_bytes());
85    h.update(main_name.as_bytes());
86
87    absorb_layout(&mut h, program.column_layout());
88    absorb_ast::<F>(&mut h, &program.constraint_ast());
89    absorb_boundaries(&mut h, &program.boundary_constraints());
90    absorb_permutation_checks(&mut h, &program.permutation_checks());
91
92    h.update(&(chiplet_defs.len() as u64).to_le_bytes());
93
94    for cd in chiplet_defs {
95        absorb_chiplet_def::<F>(&mut h, cd);
96    }
97
98    if let Some(exp) = program.virtual_expander() {
99        h.update(&[1]);
100
101        absorb_expander(&mut h, exp);
102    } else {
103        h.update(&[0]);
104    }
105
106    absorb_fixed_columns(&mut h, &program.fixed_columns());
107
108    h.update(&(program.num_columns() as u64).to_le_bytes());
109    h.update(&(program.num_public_inputs() as u64).to_le_bytes());
110
111    absorb_inline_chiplets::<F>(&mut h, inline_chiplets, &program.inline_chiplet_kernels());
112
113    h.finalize()
114}
115
116fn absorb_chiplet_def<F: TowerField>(h: &mut Absorb, cd: &ChipletDef<F>) {
117    let name = Air::<F>::name(cd);
118
119    h.update(&(name.len() as u64).to_le_bytes());
120    h.update(name.as_bytes());
121
122    absorb_layout(h, cd.column_layout());
123
124    let cd_ast = cd.constraint_ast();
125    absorb_ast::<F>(h, &cd_ast);
126
127    absorb_boundaries(h, &cd.boundary_constraints());
128    absorb_permutation_checks(h, &cd.permutation_checks());
129    absorb_fixed_columns(h, &Air::<F>::fixed_columns(cd));
130
131    if let Some(exp) = cd.virtual_expander() {
132        h.update(&[1]);
133
134        absorb_expander(h, exp);
135    } else {
136        h.update(&[0]);
137    }
138}
139
140fn absorb_inline_chiplets<F: TowerField>(
141    h: &mut Absorb,
142    inline_chiplets: &[ChipletDef<F>],
143    inline_kernel_hints: &[InlineKernelHint],
144) {
145    h.update(&(inline_chiplets.len() as u64).to_le_bytes());
146
147    for cd in inline_chiplets {
148        absorb_chiplet_def::<F>(h, cd);
149    }
150
151    h.update(&(inline_kernel_hints.len() as u64).to_le_bytes());
152
153    for hint in inline_kernel_hints {
154        h.update(&(hint.chiplet_idx as u64).to_le_bytes());
155        h.update(&(hint.root_offset as u64).to_le_bytes());
156        h.update(&(hint.column_offset as u64).to_le_bytes());
157    }
158}
159
160fn absorb_layout(h: &mut Absorb, layout: &[ColumnType]) {
161    h.update(&(layout.len() as u64).to_le_bytes());
162
163    for ct in layout {
164        h.update(&[column_type_tag(*ct)]);
165    }
166}
167
168fn absorb_ast<F: TowerField>(h: &mut Absorb, ast: &ConstraintAst<F>) {
169    h.update(&(ast.arena.len() as u64).to_le_bytes());
170
171    for i in 0..ast.arena.len() {
172        absorb_expr(h, ast.arena.get(ExprId(i as u32)));
173    }
174
175    h.update(&(ast.roots.len() as u64).to_le_bytes());
176
177    for root in &ast.roots {
178        h.update(&root.0.to_le_bytes());
179    }
180}
181
182fn absorb_expr<F: TowerField>(h: &mut Absorb, expr: &ConstraintExpr<F>) {
183    match expr {
184        ConstraintExpr::Cell(cell) => {
185            h.update(&[0]);
186            h.update(&(cell.col_idx as u32).to_le_bytes());
187            h.update(&[cell.next_row as u8]);
188        }
189        ConstraintExpr::Const(val) => {
190            h.update(&[1]);
191            h.update(&val.to_bytes());
192        }
193        ConstraintExpr::Add(l, r) => {
194            h.update(&[2]);
195            h.update(&l.0.to_le_bytes());
196            h.update(&r.0.to_le_bytes());
197        }
198        ConstraintExpr::Mul(l, r) => {
199            h.update(&[3]);
200            h.update(&l.0.to_le_bytes());
201            h.update(&r.0.to_le_bytes());
202        }
203        ConstraintExpr::Scale(scalar, child) => {
204            h.update(&[4]);
205            h.update(&scalar.to_bytes());
206            h.update(&child.0.to_le_bytes());
207        }
208        ConstraintExpr::Sum(children) => {
209            h.update(&[5]);
210            h.update(&(children.len() as u64).to_le_bytes());
211
212            for c in children {
213                h.update(&c.0.to_le_bytes());
214            }
215        }
216    }
217}
218
219fn absorb_boundaries<F: TowerField>(
220    h: &mut Absorb,
221    boundaries: &[crate::constraint::BoundaryConstraint<F>],
222) {
223    h.update(&(boundaries.len() as u64).to_le_bytes());
224
225    for bc in boundaries {
226        h.update(&(bc.col_idx as u64).to_le_bytes());
227        h.update(&(bc.row_idx as u64).to_le_bytes());
228
229        match &bc.target {
230            BoundaryTarget::PublicInput(idx) => {
231                h.update(&[0]);
232                h.update(&(*idx as u64).to_le_bytes());
233            }
234            BoundaryTarget::Constant(v) => {
235                h.update(&[1]);
236                h.update(&v.to_bytes());
237            }
238        }
239    }
240}
241
242fn absorb_fixed_columns<F: TowerField>(h: &mut Absorb, fixed: &[FixedColumn<F>]) {
243    h.update(&(fixed.len() as u64).to_le_bytes());
244
245    for fc in fixed {
246        h.update(&(fc.col_idx as u64).to_le_bytes());
247
248        match &fc.shape {
249            FixedShape::LastRow => h.update(&[0]),
250            FixedShape::FirstRow => h.update(&[1]),
251            FixedShape::Custom(bits) => {
252                h.update(&[2]);
253                h.update(&(bits.len() as u64).to_le_bytes());
254
255                for &b in bits {
256                    h.update(&[b as u8]);
257                }
258            }
259            FixedShape::Periodic { period, values } => {
260                h.update(&[3]);
261                h.update(&(*period as u64).to_le_bytes());
262                h.update(&(values.len() as u64).to_le_bytes());
263
264                for v in values {
265                    h.update(&v.to_bytes());
266                }
267            }
268            FixedShape::Sparse(entries) => {
269                h.update(&[4]);
270                h.update(&(entries.len() as u64).to_le_bytes());
271
272                for (row, v) in entries {
273                    h.update(&(*row as u64).to_le_bytes());
274                    h.update(&v.to_bytes());
275                }
276            }
277            FixedShape::Dense(values) => {
278                h.update(&[5]);
279                h.update(&(values.len() as u64).to_le_bytes());
280
281                for v in values {
282                    h.update(&v.to_bytes());
283                }
284            }
285            FixedShape::Cadence {
286                stride,
287                count,
288                origin,
289                values,
290            } => {
291                h.update(&[6]);
292                h.update(&(*stride as u64).to_le_bytes());
293                h.update(&(*count as u64).to_le_bytes());
294                h.update(&(*origin as u64).to_le_bytes());
295                h.update(&(values.len() as u64).to_le_bytes());
296
297                for v in values {
298                    h.update(&v.to_bytes());
299                }
300            }
301            FixedShape::Segments(segments) => {
302                h.update(&[7]);
303                h.update(&(segments.len() as u64).to_le_bytes());
304
305                for seg in segments {
306                    h.update(&(seg.stride as u64).to_le_bytes());
307                    h.update(&(seg.count as u64).to_le_bytes());
308                    h.update(&(seg.origin as u64).to_le_bytes());
309                    h.update(&(seg.values.len() as u64).to_le_bytes());
310
311                    for v in &seg.values {
312                        h.update(&v.to_bytes());
313                    }
314                }
315            }
316        }
317    }
318}
319
320fn absorb_permutation_checks(h: &mut Absorb, checks: &[(String, PermutationCheckSpec)]) {
321    h.update(&(checks.len() as u64).to_le_bytes());
322
323    for (bus_id, spec) in checks {
324        h.update(&(bus_id.len() as u64).to_le_bytes());
325        h.update(bus_id.as_bytes());
326
327        absorb_perm_spec(h, spec);
328    }
329}
330
331fn absorb_perm_spec(h: &mut Absorb, spec: &PermutationCheckSpec) {
332    h.update(&[match spec.kind {
333        BusKind::Permutation => 0,
334        BusKind::Lookup => 1,
335    }]);
336
337    h.update(&(spec.sources.len() as u64).to_le_bytes());
338
339    for (source, label) in &spec.sources {
340        absorb_source(h, source);
341
342        h.update(&(label.len() as u64).to_le_bytes());
343        h.update(label);
344    }
345
346    match spec.selector {
347        Some(sel) => {
348            h.update(&[1]);
349            h.update(&(sel as u64).to_le_bytes());
350        }
351        None => h.update(&[0]),
352    }
353
354    match spec.recv_selector {
355        Some(sel) => {
356            h.update(&[1]);
357            h.update(&(sel as u64).to_le_bytes());
358        }
359        None => h.update(&[0]),
360    }
361
362    match spec.clock_waiver.as_deref() {
363        Some(reason) => {
364            h.update(&[1]);
365            h.update(&(reason.len() as u64).to_le_bytes());
366            h.update(reason.as_bytes());
367        }
368        None => h.update(&[0]),
369    }
370}
371
372fn absorb_source(h: &mut Absorb, source: &Source) {
373    match source {
374        Source::Column(idx) => {
375            h.update(&[0]);
376            h.update(&(*idx as u64).to_le_bytes());
377        }
378        Source::Columns(indices) => {
379            h.update(&[1]);
380            h.update(&(indices.len() as u64).to_le_bytes());
381
382            for idx in indices {
383                h.update(&(*idx as u64).to_le_bytes());
384            }
385        }
386        Source::RowIndexLeBytes(n) => {
387            h.update(&[2]);
388            h.update(&(*n as u64).to_le_bytes());
389        }
390        Source::Const(val) => {
391            h.update(&[3]);
392            h.update(&val.to_le_bytes());
393        }
394        Source::RowIndexByte(n) => {
395            h.update(&[4]);
396            h.update(&(*n as u64).to_le_bytes());
397        }
398        Source::PhaseColumn(idx) => {
399            h.update(&[5]);
400            h.update(&(*idx as u64).to_le_bytes());
401        }
402        Source::EmitRank(side) => {
403            h.update(&[6]);
404            h.update(&[match side {
405                Side::Request => 0,
406                Side::Response => 1,
407            }]);
408        }
409    }
410}
411
412fn absorb_expander(h: &mut Absorb, exp: &crate::expander::VirtualExpander) {
413    let entries = exp.expansion_entries();
414    h.update(&(entries.len() as u64).to_le_bytes());
415
416    for entry in &entries {
417        match *entry {
418            ExpansionEntry::ExpandBits { count, storage } => {
419                h.update(&[0]);
420                h.update(&(count as u64).to_le_bytes());
421                h.update(&[column_type_tag(storage)]);
422            }
423            ExpansionEntry::PassThrough { count, storage } => {
424                h.update(&[1]);
425                h.update(&(count as u64).to_le_bytes());
426                h.update(&[column_type_tag(storage)]);
427            }
428            ExpansionEntry::ControlBits { count } => {
429                h.update(&[2]);
430                h.update(&(count as u64).to_le_bytes());
431            }
432            ExpansionEntry::ReusePassThrough {
433                phy_col_start,
434                count,
435                storage,
436            } => {
437                h.update(&[3]);
438                h.update(&(phy_col_start as u64).to_le_bytes());
439                h.update(&(count as u64).to_le_bytes());
440                h.update(&[column_type_tag(storage)]);
441            }
442            ExpansionEntry::ReuseExpandBits {
443                phy_col_start,
444                count,
445                storage,
446            } => {
447                h.update(&[4]);
448                h.update(&(phy_col_start as u64).to_le_bytes());
449                h.update(&(count as u64).to_le_bytes());
450                h.update(&[column_type_tag(storage)]);
451            }
452        }
453    }
454}
455
456fn column_type_tag(ct: ColumnType) -> u8 {
457    match ct {
458        ColumnType::Bit => 0,
459        ColumnType::B8 => 1,
460        ColumnType::B16 => 2,
461        ColumnType::B32 => 3,
462        ColumnType::B64 => 4,
463        ColumnType::B128 => 5,
464    }
465}
466
467#[cfg(test)]
468mod tests {
469    use super::*;
470
471    #[test]
472    fn buffering_does_not_move_digest() {
473        let fields: Vec<Vec<u8>> = (0..FLUSH_BYTES / 4 + 17)
474            .map(|i| (i as u32).to_le_bytes().to_vec())
475            .collect();
476
477        let mut buffered = Absorb::new();
478        let mut direct = DefaultHasher::new();
479
480        for field in &fields {
481            buffered.update(field);
482            direct.update(field);
483        }
484
485        assert_eq!(buffered.finalize(), direct.finalize());
486    }
487}
hekate_program/digest.rs

hekate_program/
digest.rs
