binius_core/protocols/greedy_evalcheck/
prove.rs

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

binius_core/protocols/greedy_evalcheck/
prove.rs
