halo2_proofs/
transcript.rs

Help
1//! This module contains utilities and traits for dealing with Fiat-Shamir
2//! transcripts.
3
4use blake2b_simd::{Params as Blake2bParams, State as Blake2bState};
5use group::ff::PrimeField;
6use std::convert::TryInto;
7
8use crate::arithmetic::{Coordinates, CurveAffine, FieldExt};
9
10use std::io::{self, Read, Write};
11use std::marker::PhantomData;
12
13/// Prefix to a prover's message soliciting a challenge
14const BLAKE2B_PREFIX_CHALLENGE: u8 = 0;
15
16/// Prefix to a prover's message containing a curve point
17const BLAKE2B_PREFIX_POINT: u8 = 1;
18
19/// Prefix to a prover's message containing a scalar
20const BLAKE2B_PREFIX_SCALAR: u8 = 2;
21
22/// Generic transcript view (from either the prover or verifier's perspective)
23pub trait Transcript<C: CurveAffine, E: EncodedChallenge<C>> {
24    /// Squeeze an encoded verifier challenge from the transcript.
25    fn squeeze_challenge(&mut self) -> E;
26
27    /// Squeeze a typed challenge (in the scalar field) from the transcript.
28    fn squeeze_challenge_scalar<T>(&mut self) -> ChallengeScalar<C, T> {
29        ChallengeScalar {
30            inner: self.squeeze_challenge().get_scalar(),
31            _marker: PhantomData,
32        }
33    }
34
35    /// Writing the point to the transcript without writing it to the proof,
36    /// treating it as a common input.
37    fn common_point(&mut self, point: C) -> io::Result<()>;
38
39    /// Writing the scalar to the transcript without writing it to the proof,
40    /// treating it as a common input.
41    fn common_scalar(&mut self, scalar: C::Scalar) -> io::Result<()>;
42}
43
44/// Transcript view from the perspective of a verifier that has access to an
45/// input stream of data from the prover to the verifier.
46pub trait TranscriptRead<C: CurveAffine, E: EncodedChallenge<C>>: Transcript<C, E> {
47    /// Read a curve point from the prover.
48    fn read_point(&mut self) -> io::Result<C>;
49
50    /// Read a curve scalar from the prover.
51    fn read_scalar(&mut self) -> io::Result<C::Scalar>;
52}
53
54/// Transcript view from the perspective of a prover that has access to an
55/// output stream of messages from the prover to the verifier.
56pub trait TranscriptWrite<C: CurveAffine, E: EncodedChallenge<C>>: Transcript<C, E> {
57    /// Write a curve point to the proof and the transcript.
58    fn write_point(&mut self, point: C) -> io::Result<()>;
59
60    /// Write a scalar to the proof and the transcript.
61    fn write_scalar(&mut self, scalar: C::Scalar) -> io::Result<()>;
62}
63
64/// We will replace BLAKE2b with an algebraic hash function in a later version.
65#[derive(Debug, Clone)]
66pub struct Blake2bRead<R: Read, C: CurveAffine, E: EncodedChallenge<C>> {
67    state: Blake2bState,
68    reader: R,
69    _marker: PhantomData<(C, E)>,
70}
71
72impl<R: Read, C: CurveAffine, E: EncodedChallenge<C>> Blake2bRead<R, C, E> {
73    /// Initialize a transcript given an input buffer.
74    pub fn init(reader: R) -> Self {
75        Blake2bRead {
76            state: Blake2bParams::new()
77                .hash_length(64)
78                .personal(b"Halo2-Transcript")
79                .to_state(),
80            reader,
81            _marker: PhantomData,
82        }
83    }
84}
85
86impl<R: Read, C: CurveAffine> TranscriptRead<C, Challenge255<C>>
87    for Blake2bRead<R, C, Challenge255<C>>
88{
89    fn read_point(&mut self) -> io::Result<C> {
90        let mut compressed = C::Repr::default();
91        self.reader.read_exact(compressed.as_mut())?;
92        let point: C = Option::from(C::from_bytes(&compressed)).ok_or_else(|| {
93            io::Error::new(io::ErrorKind::Other, "invalid point encoding in proof")
94        })?;
95        self.common_point(point)?;
96
97        Ok(point)
98    }
99
100    fn read_scalar(&mut self) -> io::Result<C::Scalar> {
101        let mut data = <C::Scalar as PrimeField>::Repr::default();
102        self.reader.read_exact(data.as_mut())?;
103        let scalar: C::Scalar = Option::from(C::Scalar::from_repr(data)).ok_or_else(|| {
104            io::Error::new(
105                io::ErrorKind::Other,
106                "invalid field element encoding in proof",
107            )
108        })?;
109        self.common_scalar(scalar)?;
110
111        Ok(scalar)
112    }
113}
114
115impl<R: Read, C: CurveAffine> Transcript<C, Challenge255<C>>
116    for Blake2bRead<R, C, Challenge255<C>>
117{
118    fn squeeze_challenge(&mut self) -> Challenge255<C> {
119        self.state.update(&[BLAKE2B_PREFIX_CHALLENGE]);
120        let hasher = self.state.clone();
121        let result: [u8; 64] = hasher.finalize().as_bytes().try_into().unwrap();
122        Challenge255::<C>::new(&result)
123    }
124
125    fn common_point(&mut self, point: C) -> io::Result<()> {
126        self.state.update(&[BLAKE2B_PREFIX_POINT]);
127        let coords: Coordinates<C> = Option::from(point.coordinates()).ok_or_else(|| {
128            io::Error::new(
129                io::ErrorKind::Other,
130                "cannot write points at infinity to the transcript",
131            )
132        })?;
133        self.state.update(coords.x().to_repr().as_ref());
134        self.state.update(coords.y().to_repr().as_ref());
135
136        Ok(())
137    }
138
139    fn common_scalar(&mut self, scalar: C::Scalar) -> io::Result<()> {
140        self.state.update(&[BLAKE2B_PREFIX_SCALAR]);
141        self.state.update(scalar.to_repr().as_ref());
142
143        Ok(())
144    }
145}
146
147/// We will replace BLAKE2b with an algebraic hash function in a later version.
148#[derive(Debug, Clone)]
149pub struct Blake2bWrite<W: Write, C: CurveAffine, E: EncodedChallenge<C>> {
150    state: Blake2bState,
151    writer: W,
152    _marker: PhantomData<(C, E)>,
153}
154
155impl<W: Write, C: CurveAffine, E: EncodedChallenge<C>> Blake2bWrite<W, C, E> {
156    /// Initialize a transcript given an output buffer.
157    pub fn init(writer: W) -> Self {
158        Blake2bWrite {
159            state: Blake2bParams::new()
160                .hash_length(64)
161                .personal(b"Halo2-Transcript")
162                .to_state(),
163            writer,
164            _marker: PhantomData,
165        }
166    }
167
168    /// Conclude the interaction and return the output buffer (writer).
169    pub fn finalize(self) -> W {
170        // TODO: handle outstanding scalars? see issue #138
171        self.writer
172    }
173}
174
175impl<W: Write, C: CurveAffine> TranscriptWrite<C, Challenge255<C>>
176    for Blake2bWrite<W, C, Challenge255<C>>
177{
178    fn write_point(&mut self, point: C) -> io::Result<()> {
179        self.common_point(point)?;
180        let compressed = point.to_bytes();
181        self.writer.write_all(compressed.as_ref())
182    }
183    fn write_scalar(&mut self, scalar: C::Scalar) -> io::Result<()> {
184        self.common_scalar(scalar)?;
185        let data = scalar.to_repr();
186        self.writer.write_all(data.as_ref())
187    }
188}
189
190impl<W: Write, C: CurveAffine> Transcript<C, Challenge255<C>>
191    for Blake2bWrite<W, C, Challenge255<C>>
192{
193    fn squeeze_challenge(&mut self) -> Challenge255<C> {
194        self.state.update(&[BLAKE2B_PREFIX_CHALLENGE]);
195        let hasher = self.state.clone();
196        let result: [u8; 64] = hasher.finalize().as_bytes().try_into().unwrap();
197        Challenge255::<C>::new(&result)
198    }
199
200    fn common_point(&mut self, point: C) -> io::Result<()> {
201        self.state.update(&[BLAKE2B_PREFIX_POINT]);
202        let coords: Coordinates<C> = Option::from(point.coordinates()).ok_or_else(|| {
203            io::Error::new(
204                io::ErrorKind::Other,
205                "cannot write points at infinity to the transcript",
206            )
207        })?;
208        self.state.update(coords.x().to_repr().as_ref());
209        self.state.update(coords.y().to_repr().as_ref());
210
211        Ok(())
212    }
213
214    fn common_scalar(&mut self, scalar: C::Scalar) -> io::Result<()> {
215        self.state.update(&[BLAKE2B_PREFIX_SCALAR]);
216        self.state.update(scalar.to_repr().as_ref());
217
218        Ok(())
219    }
220}
221
222/// The scalar representation of a verifier challenge.
223///
224/// The `Type` type can be used to scope the challenge to a specific context, or
225/// set to `()` if no context is required.
226#[derive(Copy, Clone, Debug)]
227pub struct ChallengeScalar<C: CurveAffine, T> {
228    inner: C::Scalar,
229    _marker: PhantomData<T>,
230}
231
232impl<C: CurveAffine, T> std::ops::Deref for ChallengeScalar<C, T> {
233    type Target = C::Scalar;
234
235    fn deref(&self) -> &Self::Target {
236        &self.inner
237    }
238}
239
240/// `EncodedChallenge<C>` defines a challenge encoding with a [`Self::Input`]
241/// that is used to derive the challenge encoding and `get_challenge` obtains
242/// the _real_ `C::Scalar` that the challenge encoding represents.
243pub trait EncodedChallenge<C: CurveAffine> {
244    /// The Input type used to derive the challenge encoding. For example,
245    /// an input from the Poseidon hash would be a base field element;
246    /// an input from the Blake2b hash would be a [u8; 64].
247    type Input;
248
249    /// Get an encoded challenge from a given input challenge.
250    fn new(challenge_input: &Self::Input) -> Self;
251
252    /// Get a scalar field element from an encoded challenge.
253    fn get_scalar(&self) -> C::Scalar;
254
255    /// Cast an encoded challenge as a typed `ChallengeScalar`.
256    fn as_challenge_scalar<T>(&self) -> ChallengeScalar<C, T> {
257        ChallengeScalar {
258            inner: self.get_scalar(),
259            _marker: PhantomData,
260        }
261    }
262}
263
264/// A 255-bit challenge.
265#[derive(Copy, Clone, Debug)]
266pub struct Challenge255<C: CurveAffine>([u8; 32], PhantomData<C>);
267
268impl<C: CurveAffine> std::ops::Deref for Challenge255<C> {
269    type Target = [u8; 32];
270
271    fn deref(&self) -> &Self::Target {
272        &self.0
273    }
274}
275
276impl<C: CurveAffine> EncodedChallenge<C> for Challenge255<C> {
277    type Input = [u8; 64];
278
279    fn new(challenge_input: &[u8; 64]) -> Self {
280        Challenge255(
281            C::Scalar::from_bytes_wide(challenge_input)
282                .to_repr()
283                .as_ref()
284                .try_into()
285                .expect("Scalar fits into 256 bits"),
286            PhantomData,
287        )
288    }
289    fn get_scalar(&self) -> C::Scalar {
290        let mut repr = <C::Scalar as PrimeField>::Repr::default();
291        repr.as_mut().copy_from_slice(&self.0);
292        C::Scalar::from_repr(repr).unwrap()
293    }
294}
295
296pub(crate) fn read_n_points<C: CurveAffine, E: EncodedChallenge<C>, T: TranscriptRead<C, E>>(
297    transcript: &mut T,
298    n: usize,
299) -> io::Result<Vec<C>> {
300    (0..n).map(|_| transcript.read_point()).collect()
301}
302
303pub(crate) fn read_n_scalars<C: CurveAffine, E: EncodedChallenge<C>, T: TranscriptRead<C, E>>(
304    transcript: &mut T,
305    n: usize,
306) -> io::Result<Vec<C::Scalar>> {
307    (0..n).map(|_| transcript.read_scalar()).collect()
308}
halo2_proofs/transcript.rs

halo2_proofs/
transcript.rs
