ark_marlin/ahp/
indexer.rs

1#![allow(non_snake_case)]
2
3use crate::ahp::{
4    constraint_systems::{arithmetize_matrix, MatrixArithmetization},
5    AHPForR1CS, Error, LabeledPolynomial,
6};
7use crate::Vec;
8use ark_ff::PrimeField;
9use ark_poly::{EvaluationDomain, GeneralEvaluationDomain};
10use ark_relations::r1cs::{
11    ConstraintSynthesizer, ConstraintSystem, OptimizationGoal, SynthesisError, SynthesisMode,
12};
13use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, SerializationError};
14use ark_std::{
15    io::{Read, Write},
16    marker::PhantomData,
17};
18use derivative::Derivative;
19
20use crate::ahp::constraint_systems::{
21    balance_matrices, make_matrices_square_for_indexer, num_non_zero,
22    pad_input_for_indexer_and_prover,
23};
24
25/// Information about the index, including the field of definition, the number of
26/// variables, the number of constraints, and the maximum number of non-zero
27/// entries in any of the constraint matrices.
28#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
29#[derivative(Clone(bound = ""), Copy(bound = ""))]
30pub struct IndexInfo<F> {
31    /// The total number of variables in the constraint system.
32    pub num_variables: usize,
33    /// The number of constraints.
34    pub num_constraints: usize,
35    /// The maximum number of non-zero entries in any constraint matrix.
36    pub num_non_zero: usize,
37    /// The number of input elements.
38    pub num_instance_variables: usize,
39
40    #[doc(hidden)]
41    f: PhantomData<F>,
42}
43
44impl<F: PrimeField> ark_ff::ToBytes for IndexInfo<F> {
45    fn write<W: Write>(&self, mut w: W) -> ark_std::io::Result<()> {
46        (self.num_variables as u64).write(&mut w)?;
47        (self.num_constraints as u64).write(&mut w)?;
48        (self.num_non_zero as u64).write(&mut w)
49    }
50}
51
52impl<F: PrimeField> IndexInfo<F> {
53    /// The maximum degree of polynomial required to represent this index in the
54    /// the AHP.
55    pub fn max_degree(&self) -> usize {
56        AHPForR1CS::<F>::max_degree(self.num_constraints, self.num_variables, self.num_non_zero)
57            .unwrap()
58    }
59}
60
61/// Represents a matrix.
62pub type Matrix<F> = Vec<Vec<(F, usize)>>;
63
64#[derive(Derivative)]
65#[derivative(Clone(bound = "F: PrimeField"))]
66/// The indexed version of the constraint system.
67/// This struct contains three kinds of objects:
68/// 1) `index_info` is information about the index, such as the size of the
69///     public input
70/// 2) `{a,b,c}` are the matrices defining the R1CS instance
71/// 3) `{a,b,c}_star_arith` are structs containing information about A^*, B^*, and C^*,
72/// which are matrices defined as `M^*(i, j) = M(j, i) * u_H(j, j)`.
73#[derive(CanonicalSerialize, CanonicalDeserialize)]
74pub struct Index<F: PrimeField> {
75    /// Information about the index.
76    pub index_info: IndexInfo<F>,
77
78    /// The A matrix for the R1CS instance
79    pub a: Matrix<F>,
80    /// The B matrix for the R1CS instance
81    pub b: Matrix<F>,
82    /// The C matrix for the R1CS instance
83    pub c: Matrix<F>,
84
85    /// Arithmetization of the A* matrix.
86    pub a_star_arith: MatrixArithmetization<F>,
87    /// Arithmetization of the B* matrix.
88    pub b_star_arith: MatrixArithmetization<F>,
89    /// Arithmetization of the C* matrix.
90    pub c_star_arith: MatrixArithmetization<F>,
91}
92
93impl<F: PrimeField> Index<F> {
94    /// The maximum degree required to represent polynomials of this index.
95    pub fn max_degree(&self) -> usize {
96        self.index_info.max_degree()
97    }
98
99    /// Iterate over the indexed polynomials.
100    pub fn iter(&self) -> impl Iterator<Item = &LabeledPolynomial<F>> {
101        ark_std::vec![
102            &self.a_star_arith.row,
103            &self.a_star_arith.col,
104            &self.a_star_arith.val,
105            &self.a_star_arith.row_col,
106            &self.b_star_arith.row,
107            &self.b_star_arith.col,
108            &self.b_star_arith.val,
109            &self.b_star_arith.row_col,
110            &self.c_star_arith.row,
111            &self.c_star_arith.col,
112            &self.c_star_arith.val,
113            &self.c_star_arith.row_col,
114        ]
115        .into_iter()
116    }
117}
118
119impl<F: PrimeField> AHPForR1CS<F> {
120    /// Generate the index for this constraint system.
121    pub fn index<C: ConstraintSynthesizer<F>>(c: C) -> Result<Index<F>, Error> {
122        let index_time = start_timer!(|| "AHP::Index");
123
124        let constraint_time = start_timer!(|| "Generating constraints");
125        let ics = ConstraintSystem::new_ref();
126        ics.set_optimization_goal(OptimizationGoal::Weight);
127        ics.set_mode(SynthesisMode::Setup);
128        c.generate_constraints(ics.clone())?;
129        end_timer!(constraint_time);
130
131        let padding_time = start_timer!(|| "Padding matrices to make them square");
132        pad_input_for_indexer_and_prover(ics.clone());
133        end_timer!(padding_time);
134        let matrix_processing_time = start_timer!(|| "Processing matrices");
135        ics.finalize();
136        make_matrices_square_for_indexer(ics.clone());
137        let matrices = ics.to_matrices().expect("should not be `None`");
138        let num_non_zero_val = num_non_zero::<F>(&matrices);
139        let (mut a, mut b, mut c) = (matrices.a, matrices.b, matrices.c);
140        balance_matrices(&mut a, &mut b);
141        end_timer!(matrix_processing_time);
142
143        let (num_formatted_input_variables, num_witness_variables, num_constraints, num_non_zero) = (
144            ics.num_instance_variables(),
145            ics.num_witness_variables(),
146            ics.num_constraints(),
147            num_non_zero_val,
148        );
149        let num_variables = num_formatted_input_variables + num_witness_variables;
150
151        if num_constraints != num_formatted_input_variables + num_witness_variables {
152            eprintln!(
153                "number of (formatted) input_variables: {}",
154                num_formatted_input_variables
155            );
156            eprintln!("number of witness_variables: {}", num_witness_variables);
157            eprintln!("number of num_constraints: {}", num_constraints);
158            eprintln!("number of num_non_zero: {}", num_non_zero);
159            return Err(Error::NonSquareMatrix);
160        }
161
162        if !Self::num_formatted_public_inputs_is_admissible(num_formatted_input_variables) {
163            return Err(Error::InvalidPublicInputLength);
164        }
165
166        let index_info = IndexInfo {
167            num_variables,
168            num_constraints,
169            num_non_zero,
170            num_instance_variables: num_formatted_input_variables,
171
172            f: PhantomData,
173        };
174
175        let domain_h = GeneralEvaluationDomain::new(num_constraints)
176            .ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
177        let domain_k = GeneralEvaluationDomain::new(num_non_zero)
178            .ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
179        let x_domain = GeneralEvaluationDomain::<F>::new(num_formatted_input_variables)
180            .ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
181        let b_domain = GeneralEvaluationDomain::<F>::new(3 * domain_k.size() - 3)
182            .ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
183
184        let a_arithmetization_time = start_timer!(|| "Arithmetizing A");
185        let a_star_arith = arithmetize_matrix("a", &mut a, domain_k, domain_h, x_domain, b_domain);
186        end_timer!(a_arithmetization_time);
187
188        let b_arithmetization_time = start_timer!(|| "Arithmetizing B");
189        let b_star_arith = arithmetize_matrix("b", &mut b, domain_k, domain_h, x_domain, b_domain);
190        end_timer!(b_arithmetization_time);
191
192        let c_arithmetization_time = start_timer!(|| "Arithmetizing C");
193        let c_star_arith = arithmetize_matrix("c", &mut c, domain_k, domain_h, x_domain, b_domain);
194        end_timer!(c_arithmetization_time);
195
196        end_timer!(index_time);
197        Ok(Index {
198            index_info,
199
200            a,
201            b,
202            c,
203
204            a_star_arith,
205            b_star_arith,
206            c_star_arith,
207        })
208    }
209}
ark_marlin/ahp/indexer.rs

ark_marlin/ahp/
indexer.rs
