winter_prover/constraints/commitment/
default.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use alloc::vec::Vec;
7use core::marker::PhantomData;
8
9use air::{proof::Queries, PartitionOptions};
10use crypto::{ElementHasher, VectorCommitment};
11use math::FieldElement;
12use tracing::info_span;
13
14use super::{ConstraintCommitment, RowMatrix};
15use crate::{CompositionPoly, CompositionPolyTrace, StarkDomain, DEFAULT_SEGMENT_WIDTH};
16
17// CONSTRAINT COMMITMENT
18// ================================================================================================
19
20/// Constraint evaluation commitment.
21///
22/// The commitment consists of two components:
23/// * Evaluations of composition polynomial columns over the LDE domain.
24/// * Vector commitment where each vector element corresponds to the digest of a row in the
25///   composition polynomial evaluation matrix.
26pub struct DefaultConstraintCommitment<
27    E: FieldElement,
28    H: ElementHasher<BaseField = E::BaseField>,
29    V: VectorCommitment<H>,
30> {
31    evaluations: RowMatrix<E>,
32    vector_commitment: V,
33    _h: PhantomData<H>,
34}
35
36impl<E, H, V> DefaultConstraintCommitment<E, H, V>
37where
38    E: FieldElement,
39    H: ElementHasher<BaseField = E::BaseField>,
40    V: VectorCommitment<H>,
41{
42    /// Creates a new constraint evaluation commitment from the provided composition polynomial
43    /// evaluations and the corresponding vector commitment.
44    pub fn new(
45        composition_poly_trace: CompositionPolyTrace<E>,
46        num_constraint_composition_columns: usize,
47        domain: &StarkDomain<E::BaseField>,
48        partition_options: PartitionOptions,
49    ) -> (Self, CompositionPoly<E>) {
50        // extend the main execution trace and build a commitment to the extended trace
51        let (evaluations, commitment, composition_poly) = build_constraint_commitment::<E, H, V>(
52            composition_poly_trace,
53            num_constraint_composition_columns,
54            domain,
55            partition_options,
56        );
57
58        assert_eq!(
59            evaluations.num_rows(),
60            commitment.domain_len(),
61            "number of rows in constraint evaluation matrix must be the same as the size \
62            of the vector commitment domain"
63        );
64
65        let commitment = Self {
66            evaluations,
67            vector_commitment: commitment,
68            _h: PhantomData,
69        };
70
71        (commitment, composition_poly)
72    }
73}
74
75impl<E, H, V> ConstraintCommitment<E> for DefaultConstraintCommitment<E, H, V>
76where
77    E: FieldElement,
78    H: ElementHasher<BaseField = E::BaseField> + core::marker::Sync,
79    V: VectorCommitment<H> + core::marker::Sync,
80{
81    type HashFn = H;
82    type VC = V;
83
84    /// Returns the commitment.
85    fn commitment(&self) -> H::Digest {
86        self.vector_commitment.commitment()
87    }
88
89    /// Returns constraint evaluations at the specified positions along with a batch opening proof
90    /// against the vector commitment.
91    fn query(self, positions: &[usize]) -> Queries {
92        // build batch opening proof to the leaves specified by positions
93        let opening_proof = self
94            .vector_commitment
95            .open_many(positions)
96            .expect("failed to generate a batch opening proof for constraint queries");
97
98        // determine a set of evaluations corresponding to each position
99        let mut evaluations = Vec::new();
100        for &position in positions {
101            let row = self.evaluations.row(position).to_vec();
102            evaluations.push(row);
103        }
104
105        Queries::new::<H, E, V>(opening_proof.1, evaluations)
106    }
107}
108
109fn build_constraint_commitment<E, H, V>(
110    composition_poly_trace: CompositionPolyTrace<E>,
111    num_constraint_composition_columns: usize,
112    domain: &StarkDomain<E::BaseField>,
113    partition_options: PartitionOptions,
114) -> (RowMatrix<E>, V, CompositionPoly<E>)
115where
116    E: FieldElement,
117    H: ElementHasher<BaseField = E::BaseField>,
118    V: VectorCommitment<H>,
119{
120    // first, build constraint composition polynomial from its trace as follows:
121    // - interpolate the trace into a polynomial in coefficient form
122    // - "break" the polynomial into a set of column polynomials each of degree equal to
123    //   trace_length - 1
124    let composition_poly = info_span!(
125        "build_composition_poly_columns",
126        num_columns = num_constraint_composition_columns
127    )
128    .in_scope(|| {
129        CompositionPoly::new(composition_poly_trace, domain, num_constraint_composition_columns)
130    });
131    assert_eq!(composition_poly.num_columns(), num_constraint_composition_columns);
132    assert_eq!(composition_poly.column_degree(), domain.trace_length() - 1);
133
134    // then, evaluate composition polynomial columns over the LDE domain
135    let domain_size = domain.lde_domain_size();
136    let composed_evaluations = info_span!("evaluate_composition_poly_columns").in_scope(|| {
137        RowMatrix::evaluate_polys_over::<DEFAULT_SEGMENT_WIDTH>(composition_poly.data(), domain)
138    });
139    assert_eq!(composed_evaluations.num_cols(), num_constraint_composition_columns);
140    assert_eq!(composed_evaluations.num_rows(), domain_size);
141
142    // finally, build constraint evaluation commitment
143    let commitment = info_span!(
144        "compute_constraint_evaluation_commitment",
145        log_domain_size = domain_size.ilog2()
146    )
147    .in_scope(|| composed_evaluations.commit_to_rows::<H, V>(partition_options));
148
149    (composed_evaluations, commitment, composition_poly)
150}
winter_prover/constraints/commitment/default.rs

winter_prover/constraints/commitment/
default.rs
