p3_commit/pcs/multilinear.rs
1//! Polynomial commitment scheme trait for multilinear polynomials.
2
3use core::fmt::Debug;
4
5use p3_field::{ExtensionField, Field};
6use serde::Serialize;
7use serde::de::DeserializeOwned;
8
9/// Polynomial commitment scheme for multilinear polynomials over the Boolean hypercube.
10///
11/// A multilinear polynomial in m variables is defined by its 2^m evaluations
12/// on {0,1}^m. This trait abstracts the three phases of a PCS:
13///
14/// - **Commit**: bind to a witness and return a public commitment plus
15/// prover-only auxiliary data.
16/// - **Open**: produce a proof for an agreed opening protocol using the
17/// prover data from commitment.
18/// - **Verify**: check the proof against the public commitment and opening
19/// protocol.
20pub trait MultilinearPcs<Challenge, Challenger>
21where
22 Challenge: ExtensionField<Self::Val>,
23{
24 /// Base field of the committed polynomials.
25 type Val: Field;
26
27 /// Succinct binding commitment sent to the verifier.
28 type Commitment: Clone + Serialize + DeserializeOwned;
29
30 /// Prover-side auxiliary data retained between commit and open.
31 /// Never sent to the verifier.
32 type ProverData;
33
34 /// Opening proof checked by the verifier.
35 type Proof: Clone + Serialize + DeserializeOwned;
36
37 /// Verification failure type.
38 type Error: Debug;
39
40 /// Configuration or budget failure during commitment or opening.
41 type ProverError: Debug;
42
43 /// Committed witness.
44 type Witness;
45
46 /// Public opening shapes agreed before commit.
47 type OpeningProtocol;
48
49 /// Number of variables m of the committed polynomials.
50 /// Every polynomial has 2^m evaluations.
51 fn num_vars(&self) -> usize;
52
53 /// Commit to a multilinear witness.
54 ///
55 /// The concrete witness representation is implementation-defined. It may
56 /// be a flat polynomial, a table layout, or another structure that expands
57 /// to multilinear evaluations over the Boolean hypercube.
58 ///
59 /// # Transcript
60 ///
61 /// The challenger is the sponge the whole proof shares.
62 ///
63 /// This phase owes it exactly one binding.
64 ///
65 /// ```text
66 /// required -> the commitment being returned, bound once
67 /// forbidden -> any other absorb, any sample, any grind
68 /// ```
69 ///
70 /// This method performs that binding by calling the scheme's own binding method.
71 ///
72 /// A verifier never reaches this one, so it calls that same binding method instead.
73 ///
74 /// Routing both sides through one call is what makes them interchangeable.
75 ///
76 /// An absorbed table height, or a batching challenge drawn here, desyncs the two sides.
77 ///
78 /// Neither side has a step out of place, so the caller sees an unexplained rejection.
79 ///
80 /// # Returns
81 ///
82 /// - A succinct commitment (e.g. a Merkle root).
83 /// - Opaque prover data consumed by `open`.
84 ///
85 /// Configuration and budget rejection must not mutate the challenger or consume
86 /// private randomness.
87 ///
88 /// A successful call still binds the commitment exactly once.
89 fn commit(
90 &self,
91 witness: Self::Witness,
92 challenger: &mut Challenger,
93 ) -> Result<(Self::Commitment, Self::ProverData), Self::ProverError>;
94
95 /// Bind a commitment into the transcript.
96 ///
97 /// # Overview
98 ///
99 /// The prover binds its commitment while producing it.
100 ///
101 /// A verifier never produces one.
102 ///
103 /// It calls this method instead, at the same point in the sponge stream.
104 ///
105 /// ```text
106 /// prover : commit(..) -> binds the root it produced
107 /// verifier: this method -> binds the root it was handed
108 /// ```
109 ///
110 /// # Soundness
111 ///
112 /// Every implementation's commit phase binds by calling this method, and so
113 /// does every verifier.
114 ///
115 /// Neither side can then drift from the other:
116 ///
117 /// - by absorbing a different value,
118 /// - in a different encoding,
119 /// - or under a different phase.
120 ///
121 /// A scheme whose binding is a typed phase keeps that phase here.
122 ///
123 /// The conformance tests pin the two against each other, so an implementation
124 /// that binds inside its commit phase instead is caught rather than trusted.
125 ///
126 /// # Arguments
127 ///
128 /// - `commitment`: the commitment to bind.
129 /// - `challenger`: sponge of the surrounding protocol, borrowed for the binding.
130 fn observe_commitment(&self, commitment: &Self::Commitment, challenger: &mut Challenger);
131
132 /// Produce an opening proof for the supplied opening protocol.
133 ///
134 /// Consumes the prover data returned by `commit`. The opening protocol is
135 /// public metadata shared with the verifier and determines which committed
136 /// values are opened.
137 ///
138 /// # Returns
139 ///
140 /// - The opening proof, including any implementation-specific claimed
141 /// evaluations needed by `verify`.
142 ///
143 /// Configuration and budget rejection leaves the challenger and private randomness
144 /// unchanged; it does not undo the preceding successful commitment.
145 fn open(
146 &self,
147 prover_data: Self::ProverData,
148 protocol: Self::OpeningProtocol,
149 challenger: &mut Challenger,
150 ) -> Result<Self::Proof, Self::ProverError>;
151
152 /// Verify an opening proof against a public commitment and opening protocol.
153 ///
154 /// The opening protocol must be the same public protocol used by the
155 /// prover when constructing the proof.
156 ///
157 /// The challenger must be in the same transcript state as the prover's
158 /// challenger was at the corresponding protocol step.
159 fn verify(
160 &self,
161 commitment: &Self::Commitment,
162 proof: &Self::Proof,
163 challenger: &mut Challenger,
164 protocol: Self::OpeningProtocol,
165 ) -> Result<(), Self::Error>;
166}