1//! This module provides an implementation of TranscriptEngineTrait using keccak256
  2use crate::traits::PrimeFieldExt;
  3use crate::{
  4  errors::NovaError,
  5  traits::{Group, TranscriptEngineTrait, TranscriptReprTrait},
  6};
  7use core::marker::PhantomData;
  8use sha3::{Digest, Keccak256};
  9
 10const PERSONA_TAG: &[u8] = b"NoTR";
 11const DOM_SEP_TAG: &[u8] = b"NoDS";
 12const KECCAK256_STATE_SIZE: usize = 64;
 13const KECCAK256_PREFIX_CHALLENGE_LO: u8 = 0;
 14const KECCAK256_PREFIX_CHALLENGE_HI: u8 = 1;
 15
 16/// Provides an implementation of TranscriptEngine
 17#[derive(Debug, Clone)]
 18pub struct Keccak256Transcript<G: Group> {
 19  round: u16,
 20  state: [u8; KECCAK256_STATE_SIZE],
 21  transcript: Keccak256,
 22  _p: PhantomData<G>,
 23}
 24
 25fn compute_updated_state(keccak_instance: Keccak256, input: &[u8]) -> [u8; KECCAK256_STATE_SIZE] {
 26  let mut updated_instance = keccak_instance;
 27  updated_instance.input(input);
 28
 29  let input_lo = &[KECCAK256_PREFIX_CHALLENGE_LO];
 30  let input_hi = &[KECCAK256_PREFIX_CHALLENGE_HI];
 31
 32  let mut hasher_lo = updated_instance.clone();
 33  let mut hasher_hi = updated_instance;
 34
 35  hasher_lo.input(input_lo);
 36  hasher_hi.input(input_hi);
 37
 38  let output_lo = hasher_lo.result();
 39  let output_hi = hasher_hi.result();
 40
 41  [output_lo, output_hi]
 42    .concat()
 43    .as_slice()
 44    .try_into()
 45    .unwrap()
 46}
 47
 48impl<G: Group> TranscriptEngineTrait<G> for Keccak256Transcript<G> {
 49  fn new(label: &'static [u8]) -> Self {
 50    let keccak_instance = Keccak256::new();
 51    let input = [PERSONA_TAG, label].concat();
 52    let output = compute_updated_state(keccak_instance.clone(), &input);
 53
 54    Self {
 55      round: 0u16,
 56      state: output,
 57      transcript: keccak_instance,
 58      _p: Default::default(),
 59    }
 60  }
 61
 62  fn squeeze(&mut self, label: &'static [u8]) -> Result<G::Scalar, NovaError> {
 63    // we gather the full input from the round, preceded by the current state of the transcript
 64    let input = [
 65      DOM_SEP_TAG,
 66      self.round.to_le_bytes().as_ref(),
 67      self.state.as_ref(),
 68      label,
 69    ]
 70    .concat();
 71    let output = compute_updated_state(self.transcript.clone(), &input);
 72
 73    // update state
 74    self.round = {
 75      if let Some(v) = self.round.checked_add(1) {
 76        v
 77      } else {
 78        return Err(NovaError::InternalTranscriptError);
 79      }
 80    };
 81    self.state.copy_from_slice(&output);
 82    self.transcript = Keccak256::new();
 83
 84    // squeeze out a challenge
 85    Ok(G::Scalar::from_uniform(&output))
 86  }
 87
 88  fn absorb<T: TranscriptReprTrait<G>>(&mut self, label: &'static [u8], o: &T) {
 89    self.transcript.input(label);
 90    self.transcript.input(&o.to_transcript_bytes());
 91  }
 92
 93  fn dom_sep(&mut self, bytes: &'static [u8]) {
 94    self.transcript.input(DOM_SEP_TAG);
 95    self.transcript.input(bytes);
 96  }
 97}
 98
 99#[cfg(test)]
100mod tests {
101  use crate::{
102    provider::bn256_grumpkin::bn256,
103    provider::keccak::Keccak256Transcript,
104    traits::{Group, PrimeFieldExt, TranscriptEngineTrait, TranscriptReprTrait},
105  };
106  use ff::PrimeField;
107  use rand::Rng;
108  use sha3::{Digest, Keccak256};
109
110  fn test_keccak_transcript_with<G: Group>(expected_h1: &'static str, expected_h2: &'static str) {
111    let mut transcript: Keccak256Transcript<G> = Keccak256Transcript::new(b"test");
112
113    // two scalars
114    let s1 = <G as Group>::Scalar::from(2u64);
115    let s2 = <G as Group>::Scalar::from(5u64);
116
117    // add the scalars to the transcript
118    transcript.absorb(b"s1", &s1);
119    transcript.absorb(b"s2", &s2);
120
121    // make a challenge
122    let c1: <G as Group>::Scalar = transcript.squeeze(b"c1").unwrap();
123    assert_eq!(hex::encode(c1.to_repr().as_ref()), expected_h1);
124
125    // a scalar
126    let s3 = <G as Group>::Scalar::from(128u64);
127
128    // add the scalar to the transcript
129    transcript.absorb(b"s3", &s3);
130
131    // make a challenge
132    let c2: <G as Group>::Scalar = transcript.squeeze(b"c2").unwrap();
133    assert_eq!(hex::encode(c2.to_repr().as_ref()), expected_h2);
134  }
135
136  #[test]
137  fn test_keccak_transcript() {
138    test_keccak_transcript_with::<pasta_curves::pallas::Point>(
139      "5ddffa8dc091862132788b8976af88b9a2c70594727e611c7217ba4c30c8c70a",
140      "4d4bf42c065870395749fa1c4fb641df1e0d53f05309b03d5b1db7f0be3aa13d",
141    );
142
143    test_keccak_transcript_with::<bn256::Point>(
144      "9fb71e3b74bfd0b60d97349849b895595779a240b92a6fae86bd2812692b6b0e",
145      "bfd4c50b7d6317e9267d5d65c985eb455a3561129c0b3beef79bfc8461a84f18",
146    );
147  }
148
149  #[test]
150  fn test_keccak_example() {
151    let mut hasher = Keccak256::new();
152    hasher.input(0xffffffff_u32.to_le_bytes());
153    let output: [u8; 32] = hasher.result().try_into().unwrap();
154    assert_eq!(
155      hex::encode(output),
156      "29045a592007d0c246ef02c2223570da9522d0cf0f73282c79a1bc8f0bb2c238"
157    );
158  }
159
160  use super::{
161    DOM_SEP_TAG, KECCAK256_PREFIX_CHALLENGE_HI, KECCAK256_PREFIX_CHALLENGE_LO,
162    KECCAK256_STATE_SIZE, PERSONA_TAG,
163  };
164
165  fn compute_updated_state_for_testing(input: &[u8]) -> [u8; KECCAK256_STATE_SIZE] {
166    let input_lo = [input, &[KECCAK256_PREFIX_CHALLENGE_LO]].concat();
167    let input_hi = [input, &[KECCAK256_PREFIX_CHALLENGE_HI]].concat();
168
169    let mut hasher_lo = Keccak256::new();
170    let mut hasher_hi = Keccak256::new();
171
172    hasher_lo.input(&input_lo);
173    hasher_hi.input(&input_hi);
174
175    let output_lo = hasher_lo.result();
176    let output_hi = hasher_hi.result();
177
178    [output_lo, output_hi]
179      .concat()
180      .as_slice()
181      .try_into()
182      .unwrap()
183  }
184
185  fn squeeze_for_testing(
186    transcript: &[u8],
187    round: u16,
188    state: [u8; KECCAK256_STATE_SIZE],
189    label: &'static [u8],
190  ) -> [u8; 64] {
191    let input = [
192      transcript,
193      DOM_SEP_TAG,
194      round.to_le_bytes().as_ref(),
195      state.as_ref(),
196      label,
197    ]
198    .concat();
199    compute_updated_state_for_testing(&input)
200  }
201
202  // This test is meant to ensure compatibility between the incremental way of computing the transcript above, and
203  // the former, which materialized the entirety of the input vector before calling Keccak256 on it.
204  fn test_keccak_transcript_incremental_vs_explicit_with<G: Group>() {
205    let test_label = b"test";
206    let mut transcript: Keccak256Transcript<G> = Keccak256Transcript::new(test_label);
207    let mut rng = rand::thread_rng();
208
209    // ten scalars
210    let scalars = std::iter::from_fn(|| Some(<G as Group>::Scalar::from(rng.gen::<u64>())))
211      .take(10)
212      .collect::<Vec<_>>();
213
214    // add the scalars to the transcripts,
215    let mut manual_transcript: Vec<u8> = vec![];
216    let labels = vec![
217      b"s1", b"s2", b"s3", b"s4", b"s5", b"s6", b"s7", b"s8", b"s9", b"s0",
218    ];
219
220    for i in 0..10 {
221      transcript.absorb(&labels[i][..], &scalars[i]);
222      manual_transcript.extend(labels[i]);
223      manual_transcript.extend(scalars[i].to_transcript_bytes());
224    }
225
226    // compute the initial state
227    let input = [PERSONA_TAG, test_label].concat();
228    let initial_state = compute_updated_state_for_testing(&input);
229
230    // make a challenge
231    let c1: <G as Group>::Scalar = transcript.squeeze(b"c1").unwrap();
232
233    let c1_bytes = squeeze_for_testing(&manual_transcript[..], 0u16, initial_state, b"c1");
234    let to_hex = |g: G::Scalar| hex::encode(g.to_repr().as_ref());
235    assert_eq!(to_hex(c1), to_hex(G::Scalar::from_uniform(&c1_bytes)));
236  }
237
238  #[test]
239  fn test_keccak_transcript_incremental_vs_explicit() {
240    test_keccak_transcript_incremental_vs_explicit_with::<pasta_curves::pallas::Point>();
241    test_keccak_transcript_incremental_vs_explicit_with::<bn256::Point>();
242  }
243}