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, 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    }
399}
400
401fn absorb_expander(h: &mut Absorb, exp: &crate::expander::VirtualExpander) {
402    let entries = exp.expansion_entries();
403    h.update(&(entries.len() as u64).to_le_bytes());
404
405    for entry in &entries {
406        match *entry {
407            ExpansionEntry::ExpandBits { count, storage } => {
408                h.update(&[0]);
409                h.update(&(count as u64).to_le_bytes());
410                h.update(&[column_type_tag(storage)]);
411            }
412            ExpansionEntry::PassThrough { count, storage } => {
413                h.update(&[1]);
414                h.update(&(count as u64).to_le_bytes());
415                h.update(&[column_type_tag(storage)]);
416            }
417            ExpansionEntry::ControlBits { count } => {
418                h.update(&[2]);
419                h.update(&(count as u64).to_le_bytes());
420            }
421            ExpansionEntry::ReusePassThrough {
422                phy_col_start,
423                count,
424                storage,
425            } => {
426                h.update(&[3]);
427                h.update(&(phy_col_start as u64).to_le_bytes());
428                h.update(&(count as u64).to_le_bytes());
429                h.update(&[column_type_tag(storage)]);
430            }
431            ExpansionEntry::ReuseExpandBits {
432                phy_col_start,
433                count,
434                storage,
435            } => {
436                h.update(&[4]);
437                h.update(&(phy_col_start as u64).to_le_bytes());
438                h.update(&(count as u64).to_le_bytes());
439                h.update(&[column_type_tag(storage)]);
440            }
441        }
442    }
443}
444
445fn column_type_tag(ct: ColumnType) -> u8 {
446    match ct {
447        ColumnType::Bit => 0,
448        ColumnType::B8 => 1,
449        ColumnType::B16 => 2,
450        ColumnType::B32 => 3,
451        ColumnType::B64 => 4,
452        ColumnType::B128 => 5,
453    }
454}
455
456#[cfg(test)]
457mod tests {
458    use super::*;
459
460    #[test]
461    fn buffering_does_not_move_digest() {
462        let fields: Vec<Vec<u8>> = (0..FLUSH_BYTES / 4 + 17)
463            .map(|i| (i as u32).to_le_bytes().to_vec())
464            .collect();
465
466        let mut buffered = Absorb::new();
467        let mut direct = DefaultHasher::new();
468
469        for field in &fields {
470            buffered.update(field);
471            direct.update(field);
472        }
473
474        assert_eq!(buffered.finalize(), direct.finalize());
475    }
476}
hekate_program/digest.rs

hekate_program/
digest.rs
