binius_core/protocols/greedy_evalcheck/
prove.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_field::{
4	ExtensionField, Field, PackedExtension, PackedField, PackedFieldIndexable, TowerField,
5};
6use binius_hal::ComputationBackend;
7use binius_math::EvaluationDomainFactory;
8use tracing::instrument;
9
10use super::error::Error;
11use crate::{
12	fiat_shamir::Challenger,
13	oracle::MultilinearOracleSet,
14	protocols::evalcheck::{
15		serialize_evalcheck_proof,
16		subclaims::{prove_bivariate_sumchecks_with_switchover, MemoizedData},
17		EvalcheckMultilinearClaim, EvalcheckProver,
18	},
19	transcript::{write_u64, ProverTranscript},
20	witness::MultilinearExtensionIndex,
21};
22
23pub struct GreedyEvalcheckProveOutput<'a, F: Field, P: PackedField, Backend: ComputationBackend> {
24	pub eval_claims: Vec<EvalcheckMultilinearClaim<F>>,
25	pub memoized_data: MemoizedData<'a, P, Backend>,
26}
27
28#[allow(clippy::too_many_arguments)]
29#[instrument(skip_all, name = "greedy_evalcheck::prove")]
30pub fn prove<'a, F, P, DomainField, Challenger_, Backend>(
31	oracles: &mut MultilinearOracleSet<F>,
32	witness_index: &'a mut MultilinearExtensionIndex<P>,
33	claims: impl IntoIterator<Item = EvalcheckMultilinearClaim<F>>,
34	switchover_fn: impl Fn(usize) -> usize + Clone + 'static,
35	transcript: &mut ProverTranscript<Challenger_>,
36	domain_factory: impl EvaluationDomainFactory<DomainField>,
37	backend: &Backend,
38) -> Result<GreedyEvalcheckProveOutput<'a, F, P, Backend>, Error>
39where
40	F: TowerField + ExtensionField<DomainField>,
41	P: PackedFieldIndexable<Scalar = F>
42		+ PackedExtension<F, PackedSubfield = P>
43		+ PackedExtension<DomainField>,
44	DomainField: TowerField,
45	Challenger_: Challenger,
46	Backend: ComputationBackend,
47{
48	let mut evalcheck_prover =
49		EvalcheckProver::<F, P, Backend>::new(oracles, witness_index, backend);
50
51	let claims: Vec<_> = claims.into_iter().collect();
52
53	// Prove the initial evalcheck claims
54	let evalcheck_proofs = evalcheck_prover.prove(claims)?;
55	write_u64(&mut transcript.decommitment(), evalcheck_proofs.len() as u64);
56	let mut writer = transcript.message();
57	for evalcheck_proof in &evalcheck_proofs {
58		serialize_evalcheck_proof(&mut writer, evalcheck_proof)
59	}
60
61	loop {
62		let new_sumchecks = evalcheck_prover.take_new_sumchecks_constraints().unwrap();
63		if new_sumchecks.is_empty() {
64			break;
65		}
66
67		// Reduce the new sumcheck claims for virtual polynomial openings to new evalcheck claims.
68		let new_evalcheck_claims =
69			prove_bivariate_sumchecks_with_switchover::<_, _, DomainField, _, _>(
70				evalcheck_prover.witness_index,
71				new_sumchecks,
72				transcript,
73				switchover_fn.clone(),
74				domain_factory.clone(),
75				backend,
76			)?;
77
78		let new_evalcheck_proofs = evalcheck_prover.prove(new_evalcheck_claims)?;
79
80		let mut writer = transcript.message();
81		for evalcheck_proof in &new_evalcheck_proofs {
82			serialize_evalcheck_proof(&mut writer, evalcheck_proof);
83		}
84	}
85
86	let committed_claims = evalcheck_prover
87		.committed_eval_claims_mut()
88		.drain(..)
89		.collect::<Vec<_>>();
90
91	Ok(GreedyEvalcheckProveOutput {
92		eval_claims: committed_claims,
93		memoized_data: evalcheck_prover.memoized_data,
94	})
95}
binius_core/protocols/greedy_evalcheck/prove.rs

binius_core/protocols/greedy_evalcheck/
prove.rs
