snark_verifier/system/halo2/transcript/
evm.rs

Help
1//! Transcript for verifier on EVM.
2
3use crate::halo2_proofs;
4use crate::loader::evm::loader::MEM_PTR_START;
5use crate::{
6    loader::{
7        evm::{loader::Value, u256_to_fe, util::MemoryChunk, EcPoint, EvmLoader, Scalar, U256},
8        native::{self, NativeLoader},
9        Loader,
10    },
11    util::{
12        arithmetic::{Coordinates, CurveAffine, PrimeField},
13        hash::{Digest, Keccak256},
14        transcript::{Transcript, TranscriptRead},
15        Itertools,
16    },
17    Error,
18};
19use halo2_proofs::transcript::EncodedChallenge;
20use std::{
21    io::{self, Read, Write},
22    iter,
23    marker::PhantomData,
24    rc::Rc,
25};
26
27/// Transcript for verifier on EVM using keccak256 as hasher.
28#[derive(Debug)]
29pub struct EvmTranscript<C: CurveAffine, L: Loader<C>, S, B> {
30    loader: L,
31    stream: S,
32    buf: B,
33    _marker: PhantomData<C>,
34}
35
36impl<C> EvmTranscript<C, Rc<EvmLoader>, usize, MemoryChunk>
37where
38    C: CurveAffine,
39    C::Scalar: PrimeField<Repr = [u8; 0x20]>,
40{
41    /// Initialize [`EvmTranscript`] given [`Rc<EvmLoader>`] and pre-allocate an
42    /// u256 for `transcript_initial_state`.
43    pub fn new(loader: &Rc<EvmLoader>) -> Self {
44        let ptr = loader.allocate(0x20);
45        assert_eq!(ptr, MEM_PTR_START);
46        let mut buf = MemoryChunk::new(ptr);
47        buf.extend(0x20);
48        Self { loader: loader.clone(), stream: 0, buf, _marker: PhantomData }
49    }
50
51    /// Load `num_instance` instances from calldata to memory.
52    pub fn load_instances(&mut self, num_instance: Vec<usize>) -> Vec<Vec<Scalar>> {
53        num_instance
54            .into_iter()
55            .map(|len| {
56                iter::repeat_with(|| {
57                    let scalar = self.loader.calldataload_scalar(self.stream);
58                    self.stream += 0x20;
59                    scalar
60                })
61                .take(len)
62                .collect_vec()
63            })
64            .collect()
65    }
66}
67
68impl<C> Transcript<C, Rc<EvmLoader>> for EvmTranscript<C, Rc<EvmLoader>, usize, MemoryChunk>
69where
70    C: CurveAffine,
71    C::Scalar: PrimeField<Repr = [u8; 0x20]>,
72{
73    fn loader(&self) -> &Rc<EvmLoader> {
74        &self.loader
75    }
76
77    /// Does not allow the input to be a one-byte sequence, because the Transcript trait only supports writing scalars and elliptic curve points.
78    /// If the one-byte sequence `[0x01]` is a valid input to the transcript, the empty input `[]` will have the same transcript result as `[0x01]`.
79    fn squeeze_challenge(&mut self) -> Scalar {
80        let len = if self.buf.len() == 0x20 {
81            assert_eq!(self.loader.ptr(), self.buf.end());
82            let buf_end = self.buf.end();
83            let code = format!("mstore8({buf_end}, 1)");
84            self.loader.code_mut().runtime_append(code);
85            0x21
86        } else {
87            self.buf.len()
88        };
89        let hash_ptr = self.loader.keccak256(self.buf.ptr(), len);
90
91        let challenge_ptr = self.loader.allocate(0x20);
92        let dup_hash_ptr = self.loader.allocate(0x20);
93        let code = format!(
94            "{{
95            let hash := mload({hash_ptr:#x})
96            mstore({challenge_ptr:#x}, mod(hash, f_q))
97            mstore({dup_hash_ptr:#x}, hash)
98        }}"
99        );
100        self.loader.code_mut().runtime_append(code);
101
102        self.buf.reset(dup_hash_ptr);
103        self.buf.extend(0x20);
104
105        self.loader.scalar(Value::Memory(challenge_ptr))
106    }
107
108    fn common_ec_point(&mut self, ec_point: &EcPoint) -> Result<(), Error> {
109        if let Value::Memory(ptr) = ec_point.value() {
110            assert_eq!(self.buf.end(), ptr);
111            self.buf.extend(0x40);
112        } else {
113            unreachable!()
114        }
115        Ok(())
116    }
117
118    fn common_scalar(&mut self, scalar: &Scalar) -> Result<(), Error> {
119        match scalar.value() {
120            Value::Constant(_) if self.buf.ptr() == MEM_PTR_START => {
121                self.loader.copy_scalar(scalar, self.buf.ptr());
122            }
123            Value::Memory(ptr) => {
124                assert_eq!(self.buf.end(), ptr);
125                self.buf.extend(0x20);
126            }
127            _ => unreachable!(),
128        }
129        Ok(())
130    }
131}
132
133impl<C> TranscriptRead<C, Rc<EvmLoader>> for EvmTranscript<C, Rc<EvmLoader>, usize, MemoryChunk>
134where
135    C: CurveAffine,
136    C::Scalar: PrimeField<Repr = [u8; 0x20]>,
137{
138    fn read_scalar(&mut self) -> Result<Scalar, Error> {
139        let scalar = self.loader.calldataload_scalar(self.stream);
140        self.stream += 0x20;
141        self.common_scalar(&scalar)?;
142        Ok(scalar)
143    }
144
145    fn read_ec_point(&mut self) -> Result<EcPoint, Error> {
146        let ec_point = self.loader.calldataload_ec_point(self.stream);
147        self.stream += 0x40;
148        self.common_ec_point(&ec_point)?;
149        Ok(ec_point)
150    }
151}
152
153impl<C, S> EvmTranscript<C, NativeLoader, S, Vec<u8>>
154where
155    C: CurveAffine,
156{
157    /// Initialize [`EvmTranscript`] given readable or writeable stream for
158    /// verifying or proving with [`NativeLoader`].
159    pub fn new(stream: S) -> Self {
160        Self { loader: NativeLoader, stream, buf: Vec::new(), _marker: PhantomData }
161    }
162}
163
164impl<C, S> Transcript<C, NativeLoader> for EvmTranscript<C, NativeLoader, S, Vec<u8>>
165where
166    C: CurveAffine,
167    C::Scalar: PrimeField<Repr = [u8; 0x20]>,
168{
169    fn loader(&self) -> &NativeLoader {
170        &native::LOADER
171    }
172
173    fn squeeze_challenge(&mut self) -> C::Scalar {
174        let data = self
175            .buf
176            .iter()
177            .cloned()
178            .chain(if self.buf.len() == 0x20 { Some(1) } else { None })
179            .collect_vec();
180        let hash: [u8; 32] = Keccak256::digest(data).into();
181        self.buf = hash.to_vec();
182        u256_to_fe(U256::from_be_bytes(hash))
183    }
184
185    fn common_ec_point(&mut self, ec_point: &C) -> Result<(), Error> {
186        let coordinates =
187            Option::<Coordinates<C>>::from(ec_point.coordinates()).ok_or_else(|| {
188                Error::Transcript(io::ErrorKind::Other, "Invalid elliptic curve point".to_string())
189            })?;
190
191        [coordinates.x(), coordinates.y()].map(|coordinate| {
192            self.buf.extend(coordinate.to_repr().as_ref().iter().rev().cloned());
193        });
194
195        Ok(())
196    }
197
198    fn common_scalar(&mut self, scalar: &C::Scalar) -> Result<(), Error> {
199        self.buf.extend(scalar.to_repr().as_ref().iter().rev());
200
201        Ok(())
202    }
203}
204
205impl<C, S> TranscriptRead<C, NativeLoader> for EvmTranscript<C, NativeLoader, S, Vec<u8>>
206where
207    C: CurveAffine,
208    C::Scalar: PrimeField<Repr = [u8; 0x20]>,
209    S: Read,
210{
211    fn read_scalar(&mut self) -> Result<C::Scalar, Error> {
212        let mut data = [0; 32];
213        self.stream
214            .read_exact(data.as_mut())
215            .map_err(|err| Error::Transcript(err.kind(), err.to_string()))?;
216        data.reverse();
217        let scalar = C::Scalar::from_repr_vartime(data).ok_or_else(|| {
218            Error::Transcript(io::ErrorKind::Other, "Invalid scalar encoding in proof".to_string())
219        })?;
220        self.common_scalar(&scalar)?;
221        Ok(scalar)
222    }
223
224    fn read_ec_point(&mut self) -> Result<C, Error> {
225        let [mut x, mut y] = [<C::Base as PrimeField>::Repr::default(); 2];
226        for repr in [&mut x, &mut y] {
227            self.stream
228                .read_exact(repr.as_mut())
229                .map_err(|err| Error::Transcript(err.kind(), err.to_string()))?;
230            repr.as_mut().reverse();
231        }
232        let x = Option::from(<C::Base as PrimeField>::from_repr(x));
233        let y = Option::from(<C::Base as PrimeField>::from_repr(y));
234        let ec_point =
235            x.zip(y).and_then(|(x, y)| Option::from(C::from_xy(x, y))).ok_or_else(|| {
236                Error::Transcript(
237                    io::ErrorKind::Other,
238                    "Invalid elliptic curve point encoding in proof".to_string(),
239                )
240            })?;
241        self.common_ec_point(&ec_point)?;
242        Ok(ec_point)
243    }
244}
245
246impl<C, S> EvmTranscript<C, NativeLoader, S, Vec<u8>>
247where
248    C: CurveAffine,
249    S: Write,
250{
251    /// Returns mutable `stream`.
252    pub fn stream_mut(&mut self) -> &mut S {
253        &mut self.stream
254    }
255
256    /// Finalize transcript and returns `stream`.
257    pub fn finalize(self) -> S {
258        self.stream
259    }
260}
261
262/// [`EncodedChallenge`] implemented for verifier on EVM, which use input in
263/// big-endian as the challenge.
264#[derive(Debug)]
265pub struct ChallengeEvm<C>(C::Scalar)
266where
267    C: CurveAffine,
268    C::Scalar: PrimeField<Repr = [u8; 32]>;
269
270impl<C> EncodedChallenge<C> for ChallengeEvm<C>
271where
272    C: CurveAffine,
273    C::Scalar: PrimeField<Repr = [u8; 32]>,
274{
275    type Input = [u8; 32];
276
277    fn new(challenge_input: &[u8; 32]) -> Self {
278        ChallengeEvm(u256_to_fe(U256::from_be_bytes(*challenge_input)))
279    }
280
281    fn get_scalar(&self) -> C::Scalar {
282        self.0
283    }
284}
285
286impl<C, S> halo2_proofs::transcript::Transcript<C, ChallengeEvm<C>>
287    for EvmTranscript<C, NativeLoader, S, Vec<u8>>
288where
289    C: CurveAffine,
290    C::Scalar: PrimeField<Repr = [u8; 32]>,
291{
292    fn squeeze_challenge(&mut self) -> ChallengeEvm<C> {
293        ChallengeEvm(Transcript::squeeze_challenge(self))
294    }
295
296    fn common_point(&mut self, ec_point: C) -> io::Result<()> {
297        match Transcript::common_ec_point(self, &ec_point) {
298            Err(Error::Transcript(kind, msg)) => Err(io::Error::new(kind, msg)),
299            Err(_) => unreachable!(),
300            _ => Ok(()),
301        }
302    }
303
304    fn common_scalar(&mut self, scalar: C::Scalar) -> io::Result<()> {
305        match Transcript::common_scalar(self, &scalar) {
306            Err(Error::Transcript(kind, msg)) => Err(io::Error::new(kind, msg)),
307            Err(_) => unreachable!(),
308            _ => Ok(()),
309        }
310    }
311}
312
313impl<C, R: Read> halo2_proofs::transcript::TranscriptRead<C, ChallengeEvm<C>>
314    for EvmTranscript<C, NativeLoader, R, Vec<u8>>
315where
316    C: CurveAffine,
317    C::Scalar: PrimeField<Repr = [u8; 32]>,
318{
319    fn read_point(&mut self) -> io::Result<C> {
320        match TranscriptRead::read_ec_point(self) {
321            Err(Error::Transcript(kind, msg)) => Err(io::Error::new(kind, msg)),
322            Err(_) => unreachable!(),
323            Ok(value) => Ok(value),
324        }
325    }
326
327    fn read_scalar(&mut self) -> io::Result<C::Scalar> {
328        match TranscriptRead::read_scalar(self) {
329            Err(Error::Transcript(kind, msg)) => Err(io::Error::new(kind, msg)),
330            Err(_) => unreachable!(),
331            Ok(value) => Ok(value),
332        }
333    }
334}
335
336impl<C, R: Read> halo2_proofs::transcript::TranscriptReadBuffer<R, C, ChallengeEvm<C>>
337    for EvmTranscript<C, NativeLoader, R, Vec<u8>>
338where
339    C: CurveAffine,
340    C::Scalar: PrimeField<Repr = [u8; 32]>,
341{
342    fn init(reader: R) -> Self {
343        Self::new(reader)
344    }
345}
346
347impl<C, W: Write> halo2_proofs::transcript::TranscriptWrite<C, ChallengeEvm<C>>
348    for EvmTranscript<C, NativeLoader, W, Vec<u8>>
349where
350    C: CurveAffine,
351    C::Scalar: PrimeField<Repr = [u8; 32]>,
352{
353    fn write_point(&mut self, ec_point: C) -> io::Result<()> {
354        halo2_proofs::transcript::Transcript::<C, ChallengeEvm<C>>::common_point(self, ec_point)?;
355        let coords: Coordinates<C> = Option::from(ec_point.coordinates()).ok_or_else(|| {
356            io::Error::new(
357                io::ErrorKind::Other,
358                "Cannot write points at infinity to the transcript",
359            )
360        })?;
361        let mut x = coords.x().to_repr();
362        let mut y = coords.y().to_repr();
363        x.as_mut().reverse();
364        y.as_mut().reverse();
365        self.stream_mut().write_all(x.as_ref())?;
366        self.stream_mut().write_all(y.as_ref())
367    }
368
369    fn write_scalar(&mut self, scalar: C::Scalar) -> io::Result<()> {
370        halo2_proofs::transcript::Transcript::<C, ChallengeEvm<C>>::common_scalar(self, scalar)?;
371        let mut data = scalar.to_repr();
372        data.as_mut().reverse();
373        self.stream_mut().write_all(data.as_ref())
374    }
375}
376
377impl<C, W: Write> halo2_proofs::transcript::TranscriptWriterBuffer<W, C, ChallengeEvm<C>>
378    for EvmTranscript<C, NativeLoader, W, Vec<u8>>
379where
380    C: CurveAffine,
381    C::Scalar: PrimeField<Repr = [u8; 32]>,
382{
383    fn init(writer: W) -> Self {
384        Self::new(writer)
385    }
386
387    fn finalize(self) -> W {
388        self.finalize()
389    }
390}
snark_verifier/system/halo2/transcript/evm.rs

snark_verifier/system/halo2/transcript/
evm.rs
