binius_core/protocols/evalcheck/
evalcheck.rs

1// Copyright 2023-2025 Irreducible Inc.
2
3use std::{
4	hash::Hash,
5	ops::{Deref, Range},
6	sync::Arc,
7};
8
9use binius_field::Field;
10use bytes::{Buf, BufMut};
11
12use super::error::Error;
13use crate::{
14	oracle::OracleId,
15	transcript::{TranscriptReader, TranscriptWriter},
16};
17
18/// This struct represents a claim to be verified through the evalcheck protocol.
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub struct EvalcheckMultilinearClaim<F: Field> {
21	/// Virtual Polynomial Oracle for which the evaluation is claimed
22	pub id: OracleId,
23	/// Evaluation Point
24	pub eval_point: EvalPoint<F>,
25	/// Claimed Evaluation
26	pub eval: F,
27}
28
29impl<F: Field> EvalcheckMultilinearClaim<F> {
30	pub fn isomorphic<FTgt: Field + From<F>>(&self) -> EvalcheckMultilinearClaim<FTgt> {
31		EvalcheckMultilinearClaim {
32			id: self.id,
33			eval_point: self.eval_point.isomorphic(),
34			eval: FTgt::from(self.eval),
35		}
36	}
37}
38
39#[repr(u32)]
40#[derive(Debug)]
41enum EvalcheckNumerics {
42	NewClaim = 1,
43	DuplicateClaim,
44}
45
46/// A hint is an instruction that the prover sends to the verifier, instructing them how to check
47/// the current claim efficiently.
48///
49/// There are many scenarios, based on the structure of the multilinear oracle set, where multiple
50/// evaluation claims reduce to the same subclaim. Deduplicating these and ensuring that the
51/// verifier only checks them once is an important performance feature. The data structures a
52/// verifier would need to deduplicate on their its own are complex, and so instead the prover
53/// sends hints to the verifier if it can check a claim more efficiently by reusing work.
54#[derive(Debug, Clone, PartialEq, Eq)]
55pub enum EvalcheckHint {
56	NewClaim,
57	DuplicateClaim(u32),
58}
59
60impl EvalcheckNumerics {
61	const fn from(x: u32) -> Result<Self, Error> {
62		match x {
63			1 => Ok(Self::NewClaim),
64			2 => Ok(Self::DuplicateClaim),
65			_ => Err(Error::EvalcheckSerializationError),
66		}
67	}
68}
69
70/// Serializes the `EvalcheckProof` into the transcript
71pub fn serialize_evalcheck_proof<B: BufMut>(
72	transcript: &mut TranscriptWriter<B>,
73	evalcheck: &EvalcheckHint,
74) {
75	match evalcheck {
76		EvalcheckHint::NewClaim => {
77			transcript.write(&(EvalcheckNumerics::NewClaim as u32));
78		}
79		EvalcheckHint::DuplicateClaim(index) => {
80			transcript.write(&(EvalcheckNumerics::DuplicateClaim as u32));
81			transcript.write(index);
82		}
83	}
84}
85
86/// Deserializes the `EvalcheckProof` object from the given transcript.
87pub fn deserialize_evalcheck_proof<B: Buf>(
88	transcript: &mut TranscriptReader<B>,
89) -> Result<EvalcheckHint, Error> {
90	let mut bytes = [0; size_of::<u32>()];
91	transcript.read_bytes(&mut bytes)?;
92	let as_enum = EvalcheckNumerics::from(u32::from_le_bytes(bytes))?;
93
94	match as_enum {
95		EvalcheckNumerics::NewClaim => Ok(EvalcheckHint::NewClaim),
96		EvalcheckNumerics::DuplicateClaim => {
97			let index = transcript.read()?;
98			Ok(EvalcheckHint::DuplicateClaim(index))
99		}
100	}
101}
102
103/// Data structure for efficiently querying and inserting evaluations of claims.
104///
105/// Equivalent to a `HashMap<(OracleId, EvalPoint<F>), T>` but uses vectors of vectors to store the
106/// data. This data structure is more memory efficient for small number of evaluation points and
107/// OracleIds which are grouped together.
108#[derive(Clone, Debug)]
109pub struct EvalPointOracleIdMap<T: Clone, F: Field> {
110	data: Vec<Vec<(EvalPoint<F>, T)>>,
111}
112
113impl<T: Clone, F: Field> EvalPointOracleIdMap<T, F> {
114	pub fn new() -> Self {
115		Self {
116			data: Default::default(),
117		}
118	}
119
120	/// Query the first value found for an evaluation point for a given oracle id.
121	///
122	/// Returns `None` if no value is found.
123	pub fn get(&self, id: OracleId, eval_point: &[F]) -> Option<&T> {
124		self.data
125			.get(id.index())?
126			.iter()
127			.find(|(ep, _)| **ep == *eval_point)
128			.map(|(_, val)| val)
129	}
130
131	/// Insert a new evaluation point for a given oracle id.
132	pub fn insert(&mut self, id: OracleId, eval_point: EvalPoint<F>, val: T) {
133		if id.index() >= self.data.len() {
134			self.data.resize(id.index() + 1, Vec::new());
135		}
136
137		if self.get(id, &eval_point).is_none() {
138			self.data[id.index()].push((eval_point, val))
139		}
140	}
141
142	/// Returns `true` if the map contains a value.
143	pub fn contains(&self, id: OracleId, eval_point: &EvalPoint<F>) -> bool {
144		self.get(id, eval_point).is_some()
145	}
146
147	/// Flatten the data structure into a vector of values.
148	pub fn flatten(mut self) -> Vec<T> {
149		self.data.reverse();
150
151		std::mem::take(&mut self.data)
152			.into_iter()
153			.flatten()
154			.map(|(_, val)| val)
155			.collect::<Vec<_>>()
156	}
157
158	pub fn clear(&mut self) {
159		self.data.clear()
160	}
161}
162
163impl<T: Clone, F: Field> Default for EvalPointOracleIdMap<T, F> {
164	fn default() -> Self {
165		Self {
166			data: Default::default(),
167		}
168	}
169}
170
171/// A wrapper struct for evaluation points.
172#[derive(Debug, Clone, Eq)]
173pub struct EvalPoint<F: Field> {
174	data: Arc<[F]>,
175	range: Range<usize>,
176}
177
178impl<F: Field> PartialEq for EvalPoint<F> {
179	fn eq(&self, other: &Self) -> bool {
180		self.data[self.range.clone()] == other.data[other.range.clone()]
181	}
182}
183
184impl<F: Field> Hash for EvalPoint<F> {
185	fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
186		self.data[self.range.clone()].hash(state)
187	}
188}
189
190impl<F: Field> EvalPoint<F> {
191	pub fn slice(&self, range: Range<usize>) -> Self {
192		assert!(self.range.len() >= range.len());
193
194		let new_range = self.range.start + range.start..self.range.start + range.end;
195
196		Self {
197			data: self.data.clone(),
198			range: new_range,
199		}
200	}
201
202	pub fn to_vec(&self) -> Vec<F> {
203		self.data[self.range.clone()].to_vec()
204	}
205
206	pub fn try_get_prefix(&self, suffix: &Self) -> Option<Self> {
207		let suffix_len = suffix.len();
208		let self_len = self.len();
209
210		if suffix_len > self_len {
211			return None;
212		}
213
214		if self.slice(self_len - suffix_len..self_len) == *suffix {
215			return Some(self.slice(0..self_len - suffix_len));
216		}
217		None
218	}
219
220	pub fn isomorphic<FTgt: Field + From<F>>(&self) -> EvalPoint<FTgt> {
221		self.to_vec()
222			.into_iter()
223			.map(FTgt::from)
224			.collect::<Vec<_>>()
225			.into()
226	}
227}
228
229impl<F: Field> From<Vec<F>> for EvalPoint<F> {
230	fn from(data: Vec<F>) -> Self {
231		let range = 0..data.len();
232		Self {
233			data: data.into(),
234			range,
235		}
236	}
237}
238
239impl<F: Field> From<&[F]> for EvalPoint<F> {
240	fn from(data: &[F]) -> Self {
241		let range = 0..data.len();
242		Self {
243			data: data.into(),
244			range,
245		}
246	}
247}
248
249impl<F: Field> Deref for EvalPoint<F> {
250	type Target = [F];
251
252	fn deref(&self) -> &Self::Target {
253		&self.data[self.range.clone()]
254	}
255}