hekate_crypto/
transcript.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::{DefaultHasher, Hasher};
6use alloc::vec::Vec;
7use core::fmt;
8use core::marker::PhantomData;
9use core::num::NonZeroU64;
10use hekate_math::TowerField;
11
12pub type Result<T> = core::result::Result<T, Error>;
13
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15pub enum Error {
16    /// Field is wider than a single hash output; a raw squeeze
17    /// cannot deliver enough entropy for a challenge.
18    FieldTooLargeForChallenge {
19        field_bytes: usize,
20        max_entropy_bytes: usize,
21    },
22    EmptyIndexRange,
23}
24
25impl fmt::Display for Error {
26    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27        match self {
28            Self::FieldTooLargeForChallenge {
29                field_bytes,
30                max_entropy_bytes,
31            } => write!(
32                f,
33                "field too large for transcript entropy: field_bytes={field_bytes}, max_entropy_bytes={max_entropy_bytes}",
34            ),
35            Self::EmptyIndexRange => write!(f, "index challenge over an empty range"),
36        }
37    }
38}
39
40/// Op-by-op trace of transcript activity, enabled under `transcript-trace`.
41/// Prover/verifier traces must match step-for-step or Fiat-Shamir diverges.
42#[cfg(feature = "transcript-trace")]
43#[derive(Clone, Debug, PartialEq, Eq)]
44pub enum TranscriptOp {
45    AppendMessage {
46        label: &'static [u8],
47        digest: [u8; 32],
48    },
49    AppendU64 {
50        label: &'static [u8],
51        value: u64,
52    },
53    AppendField {
54        label: &'static [u8],
55        digest: [u8; 32],
56    },
57    AppendFieldList {
58        label: &'static [u8],
59        count: u64,
60        digest: [u8; 32],
61    },
62    ChallengeField {
63        label: &'static [u8],
64    },
65    ChallengeIndices {
66        label: &'static [u8],
67        count: u64,
68    },
69}
70
71/// Fiat-Shamir transcript as a continuous hash chain:
72/// inputs update the running state; challenges are
73/// produced by finalizing a clone and re-absorbing the
74/// digest and each squeeze depends on every prior op.
75///
76/// Generic over `H`:
77/// SHA3 / Blake3 / SHA-256 backends are interchangeable.
78#[derive(Clone, Debug)]
79pub struct Transcript<H: Hasher = DefaultHasher> {
80    hasher: H,
81    #[cfg(feature = "transcript-trace")]
82    trace: Vec<TranscriptOp>,
83    _marker: PhantomData<H>,
84}
85
86impl<H: Hasher> Transcript<H> {
87    /// Create a new transcript with a domain separator.
88    pub fn new(label: &'static [u8]) -> Self {
89        let mut transcript = Self {
90            hasher: H::new(),
91            #[cfg(feature = "transcript-trace")]
92            trace: Vec::new(),
93            _marker: PhantomData,
94        };
95
96        transcript.absorb_label(b"hekate-transcript-v2");
97        transcript
98            .hasher
99            .update(&(label.len() as u64).to_le_bytes());
100        transcript.absorb_label(label);
101
102        transcript
103    }
104
105    #[cfg(feature = "transcript-trace")]
106    pub fn take_trace(&mut self) -> Vec<TranscriptOp> {
107        core::mem::take(&mut self.trace)
108    }
109
110    #[cfg(feature = "transcript-trace")]
111    pub fn trace(&self) -> &[TranscriptOp] {
112        &self.trace
113    }
114
115    /// Append labelled bytes. The length prefix is required
116    /// to block length-extension collisions between messages.
117    pub fn append_message(&mut self, label: &'static [u8], message: &[u8]) {
118        self.absorb_label(label);
119
120        self.hasher.update(&(message.len() as u64).to_le_bytes());
121        self.hasher.update(message);
122
123        self.pad(message.len());
124
125        #[cfg(feature = "transcript-trace")]
126        self.trace.push(TranscriptOp::AppendMessage {
127            label,
128            digest: payload_digest::<H>(message),
129        });
130    }
131
132    /// Append a `u64` for protocol context
133    /// (`num_rows`, `num_cols`, bus heights, …).
134    pub fn append_u64(&mut self, label: &'static [u8], value: u64) {
135        self.absorb_label(label);
136        self.hasher.update(&value.to_le_bytes());
137
138        #[cfg(feature = "transcript-trace")]
139        self.trace.push(TranscriptOp::AppendU64 { label, value });
140    }
141
142    pub fn append_field<F: TowerField>(&mut self, label: &'static [u8], element: F) {
143        self.absorb_label(label);
144
145        let bytes = element.to_bytes();
146        self.hasher.update(&bytes);
147
148        self.pad(bytes.len());
149
150        #[cfg(feature = "transcript-trace")]
151        self.trace.push(TranscriptOp::AppendField {
152            label,
153            digest: payload_digest::<H>(&bytes),
154        });
155    }
156
157    /// Append a list of field elements
158    /// (e.g. a polynomial's round coefficients).
159    /// Length-prefixed and serialized as `TowerField::to_bytes()`
160    /// for canonical, endian-agnostic hashing.
161    pub fn append_field_list<F: TowerField>(&mut self, label: &'static [u8], elements: &[F]) {
162        self.absorb_label(label);
163
164        self.hasher.update(&(elements.len() as u64).to_le_bytes());
165        self.hasher.update_fields(elements.iter().copied());
166
167        self.pad(elements.iter().map(|e| e.serialized_size()).sum());
168
169        #[cfg(feature = "transcript-trace")]
170        self.trace.push(TranscriptOp::AppendFieldList {
171            label,
172            count: elements.len() as u64,
173            digest: {
174                let mut digest_h = H::new();
175                digest_h.update_fields(elements.iter().copied());
176
177                digest_h.finalize()
178            },
179        });
180    }
181
182    /// Draw a field challenge via the wide-pipe Fiat-Shamir pattern:
183    /// finalize a clone of the running hasher (preserving full
184    /// internal entropy), then re-absorb the digest;
185    /// the next challenge depends on this one.
186    pub fn challenge_field<F: TowerField>(&mut self, label: &'static [u8]) -> Result<F> {
187        let digest = self.squeeze(label);
188
189        #[cfg(feature = "transcript-trace")]
190        self.trace.push(TranscriptOp::ChallengeField { label });
191
192        Self::bytes_to_field(&digest)
193    }
194
195    /// Draws `count` indices below `bound`, four per digest:
196    /// each 8-byte little-endian word modulo `bound`.
197    /// Errors with `EmptyIndexRange` if `bound` is zero.
198    pub fn challenge_indices(
199        &mut self,
200        label: &'static [u8],
201        count: usize,
202        bound: usize,
203    ) -> Result<Vec<usize>> {
204        let Some(bound) = NonZeroU64::new(bound as u64) else {
205            return Err(Error::EmptyIndexRange);
206        };
207
208        let mut indices = Vec::with_capacity(count);
209        while indices.len() < count {
210            let digest = self.squeeze(label);
211            let missing = count - indices.len();
212
213            indices.extend(
214                digest
215                    .as_chunks::<8>()
216                    .0
217                    .iter()
218                    .take(missing)
219                    .map(|word| (u64::from_le_bytes(*word) % bound) as usize),
220            );
221        }
222
223        #[cfg(feature = "transcript-trace")]
224        self.trace.push(TranscriptOp::ChallengeIndices {
225            label,
226            count: count as u64,
227        });
228
229        Ok(indices)
230    }
231
232    fn bytes_to_field<F: TowerField>(bytes: &[u8]) -> Result<F> {
233        let size = size_of::<F>();
234        let max_entropy_bytes = 32;
235
236        if size > max_entropy_bytes {
237            return Err(Error::FieldTooLargeForChallenge {
238                field_bytes: size,
239                max_entropy_bytes,
240            });
241        }
242
243        // SAFETY:
244        // every bit pattern is a valid
245        // binary-field element, so raw-copy
246        // from the digest is sound.
247        let mut elem = F::default();
248        unsafe {
249            let elem_ptr = &mut elem as *mut F as *mut u8;
250            core::ptr::copy_nonoverlapping(bytes.as_ptr(), elem_ptr, size);
251        }
252
253        Ok(elem)
254    }
255
256    fn squeeze(&mut self, label: &'static [u8]) -> [u8; 32] {
257        self.absorb_label(label);
258
259        let digest = self.hasher.clone().finalize();
260
261        self.hasher.update(&digest);
262
263        digest
264    }
265
266    fn absorb_label(&mut self, label: &'static [u8]) {
267        self.hasher.update(label);
268        self.pad(label.len());
269    }
270
271    fn pad(&mut self, len: usize) {
272        self.hasher.update(&[0u8; 8][..(8 - len % 8) % 8]);
273    }
274}
275
276#[cfg(feature = "transcript-trace")]
277fn payload_digest<H: Hasher>(bytes: &[u8]) -> [u8; 32] {
278    let mut h = H::new();
279    h.update(bytes);
280
281    h.finalize()
282}
283
284#[cfg(test)]
285mod tests {
286    use super::*;
287    use hekate_math::{Block128, CanonicalSerialize};
288
289    #[derive(Clone, Debug)]
290    struct Recorder {
291        bytes: Vec<u8>,
292    }
293
294    impl Hasher for Recorder {
295        const OUTPUT_SIZE: usize = 32;
296
297        fn new() -> Self {
298            Self { bytes: Vec::new() }
299        }
300
301        fn update(&mut self, data: &[u8]) {
302            self.bytes.extend_from_slice(data);
303        }
304
305        fn finalize(self) -> [u8; 32] {
306            DefaultHasher::digest(&self.bytes)
307        }
308
309        fn finalize_reset(&mut self) -> [u8; 32] {
310            DefaultHasher::digest(&core::mem::take(&mut self.bytes))
311        }
312    }
313
314    #[test]
315    fn stream_layout_matches_hand_built_bytes() {
316        let mut transcript = Transcript::<Recorder>::new(b"t");
317
318        transcript.append_message(b"root", &[0xAA; 32]);
319        transcript.append_message(b"odd", &[1, 2, 3]);
320        transcript.append_u64(b"num_rows", 7);
321        transcript.append_field(b"claim", Block128(5));
322        transcript.append_field_list(b"q", &[Block128(1), Block128(2)]);
323
324        let _: Block128 = transcript.challenge_field(b"alpha").unwrap();
325        let indices = transcript.challenge_indices(b"idx", 5, 1000).unwrap();
326
327        let mut expected = Vec::new();
328        expected.extend_from_slice(b"hekate-transcript-v2\0\0\0\0");
329        expected.extend_from_slice(&1u64.to_le_bytes());
330        expected.extend_from_slice(b"t\0\0\0\0\0\0\0");
331        expected.extend_from_slice(b"root\0\0\0\0");
332        expected.extend_from_slice(&32u64.to_le_bytes());
333        expected.extend_from_slice(&[0xAA; 32]);
334        expected.extend_from_slice(b"odd\0\0\0\0\0");
335        expected.extend_from_slice(&3u64.to_le_bytes());
336        expected.extend_from_slice(&[1, 2, 3, 0, 0, 0, 0, 0]);
337        expected.extend_from_slice(b"num_rows");
338        expected.extend_from_slice(&7u64.to_le_bytes());
339        expected.extend_from_slice(b"claim\0\0\0");
340        expected.extend_from_slice(&Block128(5).to_bytes());
341        expected.extend_from_slice(b"q\0\0\0\0\0\0\0");
342        expected.extend_from_slice(&2u64.to_le_bytes());
343        expected.extend_from_slice(&Block128(1).to_bytes());
344        expected.extend_from_slice(&Block128(2).to_bytes());
345        expected.extend_from_slice(b"alpha\0\0\0");
346
347        let digest = DefaultHasher::digest(&expected);
348        expected.extend_from_slice(&digest);
349
350        let mut words = Vec::new();
351        for _ in 0..2 {
352            expected.extend_from_slice(b"idx\0\0\0\0\0");
353
354            let digest = DefaultHasher::digest(&expected);
355            expected.extend_from_slice(&digest);
356
357            words.extend(
358                digest
359                    .as_chunks::<8>()
360                    .0
361                    .iter()
362                    .map(|w| u64::from_le_bytes(*w)),
363            );
364        }
365
366        assert_eq!(transcript.hasher.bytes, expected);
367        assert_eq!(
368            indices,
369            words[..5]
370                .iter()
371                .map(|w| (w % 1000) as usize)
372                .collect::<Vec<_>>()
373        );
374    }
375
376    #[test]
377    fn challenge_indices_rejects_empty_range() {
378        let mut transcript = Transcript::<DefaultHasher>::new(b"t");
379
380        assert_eq!(
381            transcript.challenge_indices(b"idx", 3, 0),
382            Err(Error::EmptyIndexRange)
383        );
384    }
385
386    #[test]
387    fn domain_labels_differing_in_trailing_zeros_diverge() {
388        let short = Transcript::<Recorder>::new(b"app");
389        let long = Transcript::<Recorder>::new(b"app\0");
390
391        assert_ne!(short.hasher.bytes, long.hasher.bytes);
392    }
393}
hekate_crypto/transcript.rs

hekate_crypto/
transcript.rs
