nova_snark/provider/
keccak.rs

1//! This module provides an implementation of `TranscriptEngineTrait` using keccak256
2use crate::{
3  errors::NovaError,
4  traits::{Engine, PrimeFieldExt, TranscriptEngineTrait, TranscriptReprTrait},
5};
6use core::marker::PhantomData;
7use ff::PrimeField;
8use serde::{Deserialize, Deserializer, Serialize, Serializer};
9use sha3::{Digest, Keccak256};
10
11const PERSONA_TAG: &[u8] = b"NoTR";
12const DOM_SEP_TAG: &[u8] = b"NoDS";
13const KECCAK256_STATE_SIZE: usize = 64;
14const KECCAK256_PREFIX_CHALLENGE_LO: u8 = 0;
15const KECCAK256_PREFIX_CHALLENGE_HI: u8 = 1;
16
17/// Provides an implementation of `TranscriptEngine`
18#[derive(Debug, Clone)]
19pub struct Keccak256Transcript<E: Engine> {
20  round: u16,
21  state: [u8; KECCAK256_STATE_SIZE],
22  transcript: Keccak256,
23  /// Bytes absorbed since the last squeeze (used to reconstruct `transcript` on deserialize)
24  transcript_buffer: Vec<u8>,
25  _p: PhantomData<E>,
26}
27
28impl<E: Engine> Serialize for Keccak256Transcript<E> {
29  fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
30    use serde::ser::SerializeStruct;
31    let mut s = serializer.serialize_struct("Keccak256Transcript", 3)?;
32    s.serialize_field("round", &self.round)?;
33    s.serialize_field("state", &self.state.as_slice())?;
34    s.serialize_field("transcript_buffer", &self.transcript_buffer)?;
35    s.end()
36  }
37}
38
39impl<'de, E: Engine> Deserialize<'de> for Keccak256Transcript<E> {
40  fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
41    #[derive(Deserialize)]
42    struct Helper {
43      round: u16,
44      state: Vec<u8>,
45      #[serde(default)]
46      transcript_buffer: Vec<u8>,
47    }
48    let h = Helper::deserialize(deserializer)?;
49    let state: [u8; KECCAK256_STATE_SIZE] = h
50      .state
51      .try_into()
52      .map_err(|_| serde::de::Error::custom("invalid state length"))?;
53
54    // Replay buffered absorbs into a fresh Keccak256 to restore the hasher state
55    let mut transcript = Keccak256::new();
56    transcript.update(&h.transcript_buffer);
57
58    Ok(Keccak256Transcript {
59      round: h.round,
60      state,
61      transcript,
62      transcript_buffer: h.transcript_buffer,
63      _p: PhantomData,
64    })
65  }
66}
67
68fn compute_updated_state(keccak_instance: Keccak256, input: &[u8]) -> [u8; KECCAK256_STATE_SIZE] {
69  let mut updated_instance = keccak_instance;
70  updated_instance.update(input);
71
72  let input_lo = &[KECCAK256_PREFIX_CHALLENGE_LO];
73  let input_hi = &[KECCAK256_PREFIX_CHALLENGE_HI];
74
75  let mut hasher_lo = updated_instance.clone();
76  let mut hasher_hi = updated_instance;
77
78  hasher_lo.update(input_lo);
79  hasher_hi.update(input_hi);
80
81  let output_lo = hasher_lo.finalize();
82  let output_hi = hasher_hi.finalize();
83
84  #[cfg(not(feature = "evm"))]
85  return [output_lo, output_hi]
86    .concat()
87    .as_slice()
88    .try_into()
89    .unwrap();
90  #[cfg(feature = "evm")]
91  return [output_hi, output_lo]
92    .concat()
93    .as_slice()
94    .try_into()
95    .unwrap();
96}
97
98impl<E: Engine> Keccak256Transcript<E> {
99  /// Hash the transcript, update internal state, and return the raw 64-byte output.
100  ///
101  /// The only EVM/non-EVM differences (round byte order, output reversal) are
102  /// handled here so that `squeeze` and `squeeze_bits` stay cfg-free.
103  fn squeeze_raw(&mut self, label: &'static [u8]) -> Result<[u8; KECCAK256_STATE_SIZE], NovaError> {
104    #[cfg(not(feature = "evm"))]
105    let round_bytes = self.round.to_le_bytes();
106    #[cfg(feature = "evm")]
107    let round_bytes = self.round.to_be_bytes();
108
109    let input = [
110      DOM_SEP_TAG,
111      round_bytes.as_ref(),
112      self.state.as_ref(),
113      label,
114    ]
115    .concat();
116    #[allow(unused_mut)]
117    let mut output = compute_updated_state(self.transcript.clone(), &input);
118
119    self.round = self
120      .round
121      .checked_add(1)
122      .ok_or(NovaError::InternalTranscriptError)?;
123    self.state.copy_from_slice(&output);
124    self.transcript = Keccak256::new();
125    self.transcript_buffer.clear();
126
127    #[cfg(feature = "evm")]
128    output.reverse();
129
130    Ok(output)
131  }
132}
133
134impl<E: Engine> TranscriptEngineTrait<E> for Keccak256Transcript<E> {
135  fn new(label: &'static [u8]) -> Self {
136    let keccak_instance = Keccak256::new();
137    let input = [PERSONA_TAG, label].concat();
138    let output = compute_updated_state(keccak_instance.clone(), &input);
139
140    Self {
141      round: 0u16,
142      state: output,
143      transcript: keccak_instance,
144      transcript_buffer: Vec::new(),
145      _p: PhantomData,
146    }
147  }
148
149  fn squeeze(&mut self, label: &'static [u8]) -> Result<E::Scalar, NovaError> {
150    let output = self.squeeze_raw(label)?;
151    Ok(E::Scalar::from_uniform(&output))
152  }
153
154  fn absorb<T: TranscriptReprTrait<E::GE>>(&mut self, label: &'static [u8], o: &T) {
155    self.transcript.update(label);
156    self.transcript_buffer.extend_from_slice(label);
157    let repr = o.to_transcript_bytes();
158    self.transcript.update(&repr);
159    self.transcript_buffer.extend_from_slice(&repr);
160  }
161
162  fn dom_sep(&mut self, bytes: &'static [u8]) {
163    self.transcript.update(DOM_SEP_TAG);
164    self.transcript_buffer.extend_from_slice(DOM_SEP_TAG);
165    self.transcript.update(bytes);
166    self.transcript_buffer.extend_from_slice(bytes);
167  }
168
169  fn squeeze_bits(
170    &mut self,
171    label: &'static [u8],
172    num_bits: usize,
173    start_with_one: bool,
174  ) -> Result<E::Scalar, NovaError> {
175    assert!(num_bits >= 2);
176    assert!(
177      num_bits <= (E::Scalar::NUM_BITS - 1) as usize,
178      "num_bits must be < field bit-width to avoid overflow when setting MSB"
179    );
180
181    let output = self.squeeze_raw(label)?;
182
183    // Build scalar directly from raw hash bytes (little-endian)
184    let mut repr = <E::Scalar as PrimeField>::Repr::default();
185    let repr_bytes = repr.as_mut();
186    let num_full_bytes = num_bits / 8;
187    let remaining_bits = num_bits % 8;
188    repr_bytes[..num_full_bytes].copy_from_slice(&output[..num_full_bytes]);
189    if remaining_bits > 0 {
190      repr_bytes[num_full_bytes] = output[num_full_bytes] & ((1u8 << remaining_bits) - 1);
191    }
192    if start_with_one {
193      let msb_byte = (num_bits - 1) / 8;
194      let msb_bit = (num_bits - 1) % 8;
195      repr_bytes[msb_byte] |= 1u8 << msb_bit;
196    }
197    // Safe: num_bits < NUM_BITS, so value < 2^(NUM_BITS-1) < field modulus
198    Ok(E::Scalar::from_repr(repr).unwrap())
199  }
200}
201
202#[cfg(test)]
203mod tests {
204  use crate::{
205    provider::{
206      keccak::Keccak256Transcript, Bn256EngineKZG, GrumpkinEngine, PallasEngine, Secp256k1Engine,
207      Secq256k1Engine, VestaEngine,
208    },
209    traits::{Engine, PrimeFieldExt, TranscriptEngineTrait, TranscriptReprTrait},
210  };
211  use ff::PrimeField;
212  use rand::Rng;
213  use sha3::{Digest, Keccak256};
214
215  fn test_keccak_transcript_with<E: Engine>(expected_h1: &'static str, expected_h2: &'static str) {
216    let mut transcript: Keccak256Transcript<E> = Keccak256Transcript::new(b"test");
217
218    // two scalars
219    let s1 = <E as Engine>::Scalar::from(2u64);
220    let s2 = <E as Engine>::Scalar::from(5u64);
221
222    // add the scalars to the transcript
223    transcript.absorb(b"s1", &s1);
224    transcript.absorb(b"s2", &s2);
225
226    // make a challenge
227    let c1: <E as Engine>::Scalar = transcript.squeeze(b"c1").unwrap();
228    assert_eq!(hex::encode(c1.to_repr().as_ref()), expected_h1);
229
230    // a scalar
231    let s3 = <E as Engine>::Scalar::from(128u64);
232
233    // add the scalar to the transcript
234    transcript.absorb(b"s3", &s3);
235
236    // make a challenge
237    let c2: <E as Engine>::Scalar = transcript.squeeze(b"c2").unwrap();
238    assert_eq!(hex::encode(c2.to_repr().as_ref()), expected_h2);
239  }
240
241  #[test]
242  #[cfg(not(feature = "evm"))]
243  fn test_keccak_transcript() {
244    test_keccak_transcript_with::<PallasEngine>(
245      "5ddffa8dc091862132788b8976af88b9a2c70594727e611c7217ba4c30c8c70a",
246      "4d4bf42c065870395749fa1c4fb641df1e0d53f05309b03d5b1db7f0be3aa13d",
247    );
248
249    test_keccak_transcript_with::<Bn256EngineKZG>(
250      "9fb71e3b74bfd0b60d97349849b895595779a240b92a6fae86bd2812692b6b0e",
251      "bfd4c50b7d6317e9267d5d65c985eb455a3561129c0b3beef79bfc8461a84f18",
252    );
253
254    test_keccak_transcript_with::<Secp256k1Engine>(
255      "9723aafb69ec8f0e9c7de756df0993247d98cf2b2f72fa353e3de654a177e310",
256      "a6a90fcb6e1b1a2a2f84c950ef1510d369aea8e42085f5c629bfa66d00255f25",
257    );
258  }
259
260  #[test]
261  #[cfg(feature = "evm")]
262  fn test_keccak_transcript() {
263    test_keccak_transcript_with::<PallasEngine>(
264      "cc8899e834968eae4269b223856518ab44d04bd381b95fda44969eedcd233710",
265      "21dd7314db7c10274ef62a25175704ac9dc86dd3be2e87cad2fe44f95ec4271b",
266    );
267
268    test_keccak_transcript_with::<Bn256EngineKZG>(
269      "4bcc2d614503c68d32df47c87c7698bfdebb71bcd9c76b5a463f806ff7bec212",
270      "d7ee88576da267c5c38cc39063e98c517aacc7581cdb6e5924b19de8218b8f01",
271    );
272
273    test_keccak_transcript_with::<Secp256k1Engine>(
274      "788f8ff3cf50d6d1509dd923abd427f16cb934721a5c8883c47cd1cc228a0e71",
275      "011ffa1afa7d3342100ec63101f6be02ed784e503e36f74f0e74a28b30dc85fb",
276    );
277  }
278
279  #[test]
280  fn test_keccak_example() {
281    let mut hasher = Keccak256::new();
282    hasher.update(0xffffffff_u32.to_le_bytes());
283    let output: [u8; 32] = hasher.finalize().into();
284    assert_eq!(
285      hex::encode(output),
286      "29045a592007d0c246ef02c2223570da9522d0cf0f73282c79a1bc8f0bb2c238"
287    );
288  }
289
290  use super::{
291    DOM_SEP_TAG, KECCAK256_PREFIX_CHALLENGE_HI, KECCAK256_PREFIX_CHALLENGE_LO,
292    KECCAK256_STATE_SIZE, PERSONA_TAG,
293  };
294
295  fn compute_updated_state_for_testing(input: &[u8]) -> [u8; KECCAK256_STATE_SIZE] {
296    let input_lo = [input, &[KECCAK256_PREFIX_CHALLENGE_LO]].concat();
297    let input_hi = [input, &[KECCAK256_PREFIX_CHALLENGE_HI]].concat();
298
299    let mut hasher_lo = Keccak256::new();
300    let mut hasher_hi = Keccak256::new();
301
302    hasher_lo.update(&input_lo);
303    hasher_hi.update(&input_hi);
304
305    let output_lo = hasher_lo.finalize();
306    let output_hi = hasher_hi.finalize();
307
308    #[cfg(not(feature = "evm"))]
309    return [output_lo, output_hi]
310      .concat()
311      .as_slice()
312      .try_into()
313      .unwrap();
314    #[cfg(feature = "evm")]
315    return [output_hi, output_lo]
316      .concat()
317      .as_slice()
318      .try_into()
319      .unwrap();
320  }
321
322  #[cfg(not(feature = "evm"))]
323  fn squeeze_for_testing(
324    transcript: &[u8],
325    round: u16,
326    state: [u8; KECCAK256_STATE_SIZE],
327    label: &'static [u8],
328  ) -> [u8; 64] {
329    let input = [
330      transcript,
331      DOM_SEP_TAG,
332      round.to_le_bytes().as_ref(),
333      state.as_ref(),
334      label,
335    ]
336    .concat();
337    compute_updated_state_for_testing(&input)
338  }
339
340  #[cfg(feature = "evm")]
341  fn squeeze_for_testing(
342    transcript: &[u8],
343    round: u16,
344    state: [u8; KECCAK256_STATE_SIZE],
345    label: &'static [u8],
346  ) -> [u8; 64] {
347    let input = [
348      transcript,
349      DOM_SEP_TAG,
350      round.to_be_bytes().as_ref(),
351      state.as_ref(),
352      label,
353    ]
354    .concat();
355    let mut output = compute_updated_state_for_testing(&input);
356    output.reverse();
357    output
358  }
359
360  // This test is meant to ensure compatibility between the incremental way of computing the transcript above, and
361  // the former, which materialized the entirety of the input vector before calling Keccak256 on it.
362  fn test_keccak_transcript_incremental_vs_explicit_with<E: Engine>() {
363    let test_label = b"test";
364    let mut transcript: Keccak256Transcript<E> = Keccak256Transcript::new(test_label);
365    let mut rng = rand::thread_rng();
366
367    // ten scalars
368    let scalars = std::iter::from_fn(|| Some(<E as Engine>::Scalar::from(rng.gen::<u64>())))
369      .take(10)
370      .collect::<Vec<_>>();
371
372    // add the scalars to the transcripts,
373    let mut manual_transcript: Vec<u8> = vec![];
374    let labels = [
375      b"s1", b"s2", b"s3", b"s4", b"s5", b"s6", b"s7", b"s8", b"s9", b"s0",
376    ];
377
378    for i in 0..10 {
379      transcript.absorb(&labels[i][..], &scalars[i]);
380      manual_transcript.extend(labels[i]);
381      manual_transcript.extend(scalars[i].to_transcript_bytes());
382    }
383
384    // compute the initial state
385    let input = [PERSONA_TAG, test_label].concat();
386    let initial_state = compute_updated_state_for_testing(&input);
387
388    // make a challenge
389    let c1: <E as Engine>::Scalar = transcript.squeeze(b"c1").unwrap();
390
391    let c1_bytes = squeeze_for_testing(&manual_transcript[..], 0u16, initial_state, b"c1");
392    let to_hex = |g: E::Scalar| hex::encode(g.to_repr().as_ref());
393    assert_eq!(to_hex(c1), to_hex(E::Scalar::from_uniform(&c1_bytes)));
394  }
395
396  #[test]
397  fn test_keccak_transcript_incremental_vs_explicit() {
398    test_keccak_transcript_incremental_vs_explicit_with::<PallasEngine>();
399    test_keccak_transcript_incremental_vs_explicit_with::<VestaEngine>();
400    test_keccak_transcript_incremental_vs_explicit_with::<Bn256EngineKZG>();
401    test_keccak_transcript_incremental_vs_explicit_with::<GrumpkinEngine>();
402    test_keccak_transcript_incremental_vs_explicit_with::<Secp256k1Engine>();
403    test_keccak_transcript_incremental_vs_explicit_with::<Secq256k1Engine>();
404  }
405
406  /// Test that a fresh transcript round-trips through serde (JSON).
407  fn test_keccak_transcript_serde_fresh_with<E: Engine>() {
408    let transcript: Keccak256Transcript<E> = Keccak256Transcript::new(b"serde_test");
409    let json = serde_json::to_string(&transcript).unwrap();
410    let restored: Keccak256Transcript<E> = serde_json::from_str(&json).unwrap();
411
412    assert_eq!(transcript.round, restored.round);
413    assert_eq!(transcript.state, restored.state);
414  }
415
416  /// Test that round and state survive serialization after absorb + squeeze.
417  fn test_keccak_transcript_serde_after_ops_with<E: Engine>() {
418    let mut transcript: Keccak256Transcript<E> = Keccak256Transcript::new(b"serde_test");
419
420    let s1 = <E as Engine>::Scalar::from(42u64);
421    let s2 = <E as Engine>::Scalar::from(99u64);
422    transcript.absorb(b"s1", &s1);
423    transcript.absorb(b"s2", &s2);
424    let _c1: <E as Engine>::Scalar = transcript.squeeze(b"c1").unwrap();
425
426    // Capture state after operations
427    let round_before = transcript.round;
428    let state_before = transcript.state;
429
430    let json = serde_json::to_string(&transcript).unwrap();
431    let restored: Keccak256Transcript<E> = serde_json::from_str(&json).unwrap();
432
433    assert_eq!(round_before, restored.round);
434    assert_eq!(state_before, restored.state);
435  }
436
437  /// Test that pending absorbs survive serialization (squeeze after deserialize
438  /// must produce the same challenge as without the round-trip).
439  fn test_keccak_transcript_serde_mid_absorb_with<E: Engine>() {
440    let mut t1: Keccak256Transcript<E> = Keccak256Transcript::new(b"mid_absorb");
441    let s1 = <E as Engine>::Scalar::from(11u64);
442    let s2 = <E as Engine>::Scalar::from(22u64);
443    t1.absorb(b"a", &s1);
444    t1.absorb(b"b", &s2);
445    // Do NOT squeeze yet — there are pending absorbs in the hasher.
446
447    let json = serde_json::to_string(&t1).unwrap();
448    let mut t2: Keccak256Transcript<E> = serde_json::from_str(&json).unwrap();
449
450    // Now squeeze both and verify they produce the same challenge
451    let c1: <E as Engine>::Scalar = t1.squeeze(b"ch").unwrap();
452    let c2: <E as Engine>::Scalar = t2.squeeze(b"ch").unwrap();
453    assert_eq!(c1, c2);
454  }
455
456  /// Test that a transcript deserialized from JSON with a wrong-length state
457  /// produces an error instead of panicking.
458  fn test_keccak_transcript_serde_bad_state_with<E: Engine>() {
459    // Craft JSON with a state array of wrong length (32 instead of 64)
460    let bad_json = r#"{"round":0,"state":[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],"transcript_buffer":[]}"#;
461    let result = serde_json::from_str::<Keccak256Transcript<E>>(bad_json);
462    assert!(result.is_err());
463  }
464
465  /// Test bincode round-trip (used by Nova for proof serialization).
466  fn test_keccak_transcript_serde_bincode_with<E: Engine>() {
467    let mut transcript: Keccak256Transcript<E> = Keccak256Transcript::new(b"bincode_test");
468
469    let s = <E as Engine>::Scalar::from(7u64);
470    transcript.absorb(b"val", &s);
471    let _c: <E as Engine>::Scalar = transcript.squeeze(b"ch").unwrap();
472
473    let encoded = bincode::serde::encode_to_vec(&transcript, bincode::config::standard()).unwrap();
474    let (restored, _): (Keccak256Transcript<E>, _) =
475      bincode::serde::decode_from_slice(&encoded, bincode::config::standard()).unwrap();
476
477    assert_eq!(transcript.round, restored.round);
478    assert_eq!(transcript.state, restored.state);
479  }
480
481  #[test]
482  fn test_keccak_transcript_serde_fresh() {
483    test_keccak_transcript_serde_fresh_with::<PallasEngine>();
484    test_keccak_transcript_serde_fresh_with::<VestaEngine>();
485    test_keccak_transcript_serde_fresh_with::<Bn256EngineKZG>();
486    test_keccak_transcript_serde_fresh_with::<GrumpkinEngine>();
487    test_keccak_transcript_serde_fresh_with::<Secp256k1Engine>();
488    test_keccak_transcript_serde_fresh_with::<Secq256k1Engine>();
489  }
490
491  #[test]
492  fn test_keccak_transcript_serde_after_ops() {
493    test_keccak_transcript_serde_after_ops_with::<PallasEngine>();
494    test_keccak_transcript_serde_after_ops_with::<VestaEngine>();
495    test_keccak_transcript_serde_after_ops_with::<Bn256EngineKZG>();
496    test_keccak_transcript_serde_after_ops_with::<GrumpkinEngine>();
497    test_keccak_transcript_serde_after_ops_with::<Secp256k1Engine>();
498    test_keccak_transcript_serde_after_ops_with::<Secq256k1Engine>();
499  }
500
501  #[test]
502  fn test_keccak_transcript_serde_mid_absorb() {
503    test_keccak_transcript_serde_mid_absorb_with::<PallasEngine>();
504    test_keccak_transcript_serde_mid_absorb_with::<VestaEngine>();
505    test_keccak_transcript_serde_mid_absorb_with::<Bn256EngineKZG>();
506    test_keccak_transcript_serde_mid_absorb_with::<GrumpkinEngine>();
507    test_keccak_transcript_serde_mid_absorb_with::<Secp256k1Engine>();
508    test_keccak_transcript_serde_mid_absorb_with::<Secq256k1Engine>();
509  }
510
511  #[test]
512  fn test_keccak_transcript_serde_bad_state() {
513    test_keccak_transcript_serde_bad_state_with::<PallasEngine>();
514    test_keccak_transcript_serde_bad_state_with::<Bn256EngineKZG>();
515    test_keccak_transcript_serde_bad_state_with::<Secp256k1Engine>();
516  }
517
518  #[test]
519  fn test_keccak_transcript_serde_bincode() {
520    test_keccak_transcript_serde_bincode_with::<PallasEngine>();
521    test_keccak_transcript_serde_bincode_with::<VestaEngine>();
522    test_keccak_transcript_serde_bincode_with::<Bn256EngineKZG>();
523    test_keccak_transcript_serde_bincode_with::<GrumpkinEngine>();
524    test_keccak_transcript_serde_bincode_with::<Secp256k1Engine>();
525    test_keccak_transcript_serde_bincode_with::<Secq256k1Engine>();
526  }
527}
nova_snark/provider/keccak.rs

nova_snark/provider/
keccak.rs
