nova_snark/
digest.rs

1//! This module provides digest computation functionality for public parameters.
2//!
3//! It includes:
4//! - `DigestComputer`: A type for computing digests of public parameters.
5//! - `Digestible`: A trait for types that can be digested with custom implementations.
6//! - `SimpleDigestible`: A marker trait for types that can be digested via serialization.
7
8use crate::constants::NUM_HASH_BITS;
9use bincode::{enc::write::Writer, error::EncodeError};
10use ff::PrimeField;
11use serde::Serialize;
12use sha3::{Digest, Sha3_256};
13use std::marker::PhantomData;
14
15/// Trait for components with potentially discrete digests to be included in their container's digest.
16pub trait Digestible {
17  /// Write the byte representation of Self in a byte buffer
18  fn write_bytes<W: Sized + Writer>(&self, byte_sink: &mut W) -> Result<(), EncodeError>;
19}
20
21/// Marker trait to be implemented for types that implement `Digestible` and `Serialize`.
22/// Their instances will be serialized to bytes then digested.
23pub trait SimpleDigestible: Serialize {}
24
25impl<T: SimpleDigestible> Digestible for T {
26  fn write_bytes<W: Sized + Writer>(&self, byte_sink: &mut W) -> Result<(), EncodeError> {
27    let config = bincode::config::legacy()
28      .with_little_endian()
29      .with_fixed_int_encoding();
30    // Note: bincode recursively length-prefixes every field!
31    bincode::serde::encode_into_writer(self, byte_sink, config)
32  }
33}
34
35/// A type for computing digests of public parameters.
36/// Uses SHA3-256 and maps the result to a field element.
37pub struct DigestComputer<'a, F: PrimeField, T> {
38  inner: &'a T,
39  _phantom: PhantomData<F>,
40}
41
42impl<'a, F: PrimeField, T: Digestible> DigestComputer<'a, F, T> {
43  fn hasher() -> Sha3_256 {
44    Sha3_256::new()
45  }
46
47  fn map_to_field(digest: &[u8]) -> F {
48    let bv = (0..NUM_HASH_BITS).map(|i| {
49      let (byte_pos, bit_pos) = (i / 8, i % 8);
50      let bit = (digest[byte_pos] >> bit_pos) & 1;
51      bit == 1
52    });
53
54    // turn the bit vector into a scalar
55    let mut digest = F::ZERO;
56    let mut coeff = F::ONE;
57    for bit in bv {
58      if bit {
59        digest += coeff;
60      }
61      coeff += coeff;
62    }
63    digest
64  }
65
66  /// Create a new `DigestComputer`
67  pub fn new(inner: &'a T) -> Self {
68    DigestComputer {
69      inner,
70      _phantom: PhantomData,
71    }
72  }
73
74  /// Compute the digest of a `Digestible` instance.
75  pub fn digest(&self) -> Result<F, EncodeError> {
76    struct Hasher(Sha3_256);
77    impl Writer for Hasher {
78      fn write(&mut self, bytes: &[u8]) -> Result<(), EncodeError> {
79        self.0.update(bytes);
80        Ok(())
81      }
82    }
83    let mut hasher = Hasher(Self::hasher());
84    self.inner.write_bytes(&mut hasher)?;
85    let bytes: [u8; 32] = hasher.0.finalize().into();
86    Ok(Self::map_to_field(&bytes))
87  }
88}
89
90#[cfg(test)]
91mod tests {
92  use super::{DigestComputer, SimpleDigestible};
93  use crate::{provider::PallasEngine, traits::Engine};
94  use ff::Field;
95  use once_cell::sync::OnceCell;
96  use serde::{Deserialize, Serialize};
97
98  type E = PallasEngine;
99
100  #[derive(Serialize, Deserialize)]
101  struct S<E: Engine> {
102    i: usize,
103    #[serde(skip, default = "OnceCell::new")]
104    digest: OnceCell<E::Scalar>,
105  }
106
107  impl<E: Engine> SimpleDigestible for S<E> {}
108
109  impl<E: Engine> S<E> {
110    fn new(i: usize) -> Self {
111      S {
112        i,
113        digest: OnceCell::new(),
114      }
115    }
116
117    fn digest(&self) -> E::Scalar {
118      self
119        .digest
120        .get_or_try_init(|| DigestComputer::new(self).digest())
121        .cloned()
122        .unwrap()
123    }
124  }
125
126  #[test]
127  fn test_digest_field_not_ingested_in_computation() {
128    let s1 = S::<E>::new(42);
129
130    // let's set up a struct with a weird digest field to make sure the digest computation does not depend of it
131    let oc = OnceCell::new();
132    oc.set(<E as Engine>::Scalar::ONE).unwrap();
133
134    let s2: S<E> = S { i: 42, digest: oc };
135
136    assert_eq!(
137      DigestComputer::<<E as Engine>::Scalar, _>::new(&s1)
138        .digest()
139        .unwrap(),
140      DigestComputer::<<E as Engine>::Scalar, _>::new(&s2)
141        .digest()
142        .unwrap()
143    );
144
145    // note: because of the semantics of `OnceCell::get_or_try_init`, the above
146    // equality will not result in `s1.digest() == s2.digest`
147    assert_ne!(
148      s2.digest(),
149      DigestComputer::<<E as Engine>::Scalar, _>::new(&s2)
150        .digest()
151        .unwrap()
152    );
153  }
154
155  #[test]
156  fn test_digest_impervious_to_serialization() {
157    let good_s = S::<E>::new(42);
158
159    // let's set up a struct with a weird digest field to confuse deserializers
160    let oc = OnceCell::new();
161    oc.set(<E as Engine>::Scalar::ONE).unwrap();
162
163    let bad_s: S<E> = S { i: 42, digest: oc };
164    // this justifies the adjective "bad"
165    assert_ne!(good_s.digest(), bad_s.digest());
166
167    let naughty_bytes = bincode::serde::encode_to_vec(&bad_s, bincode::config::legacy()).unwrap();
168
169    let retrieved_s: S<E> =
170      bincode::serde::decode_from_slice(&naughty_bytes, bincode::config::legacy())
171        .unwrap()
172        .0;
173    assert_eq!(good_s.digest(), retrieved_s.digest())
174  }
175}
nova_snark/digest.rs

nova_snark/
digest.rs
