halo2_axiom/poly/ipa/
multiopen.rs

1//! This module contains an optimisation of the polynomial commitment opening
2//! scheme described in the [Halo][halo] paper.
3//!
4//! [halo]: https://eprint.iacr.org/2019/1021
5
6use super::*;
7use crate::{
8    poly::query::{exists_query_collision, Query},
9    transcript::ChallengeScalar,
10};
11use ff::Field;
12use std::collections::{BTreeMap, BTreeSet};
13
14mod prover;
15mod verifier;
16
17pub use prover::ProverIPA;
18pub use verifier::VerifierIPA;
19
20#[derive(Clone, Copy, Debug)]
21struct X1 {}
22/// Challenge for compressing openings at the same point sets together.
23type ChallengeX1<F> = ChallengeScalar<F, X1>;
24
25#[derive(Clone, Copy, Debug)]
26struct X2 {}
27/// Challenge for keeping the multi-point quotient polynomial terms linearly independent.
28type ChallengeX2<F> = ChallengeScalar<F, X2>;
29
30#[derive(Clone, Copy, Debug)]
31struct X3 {}
32/// Challenge point at which the commitments are opened.
33type ChallengeX3<F> = ChallengeScalar<F, X3>;
34
35#[derive(Clone, Copy, Debug)]
36struct X4 {}
37/// Challenge for collapsing the openings of the various remaining polynomials at x_3
38/// together.
39type ChallengeX4<F> = ChallengeScalar<F, X4>;
40
41#[derive(Debug)]
42struct CommitmentData<F, T: PartialEq> {
43    pub(crate) commitment: T,
44    pub(crate) set_index: usize,
45    pub(crate) point_indices: Vec<usize>,
46    pub(crate) evals: Vec<F>,
47}
48
49impl<F, T: PartialEq> CommitmentData<F, T> {
50    fn new(commitment: T) -> Self {
51        CommitmentData {
52            commitment,
53            set_index: 0,
54            point_indices: vec![],
55            evals: vec![],
56        }
57    }
58}
59
60type IntermediateSets<F, Q> = (
61    Vec<CommitmentData<<Q as Query<F>>::Eval, <Q as Query<F>>::Commitment>>,
62    Vec<Vec<F>>,
63);
64
65fn construct_intermediate_sets<F: Field + Ord, I, Q: Query<F>>(
66    queries: I,
67) -> Option<IntermediateSets<F, Q>>
68where
69    I: IntoIterator<Item = Q> + Clone,
70{
71    let queries = queries.into_iter().collect::<Vec<_>>();
72    if exists_query_collision(&queries) {
73        return None;
74    }
75    // Construct sets of unique commitments and corresponding information about
76    // their queries.
77    let mut commitment_map: Vec<CommitmentData<Q::Eval, Q::Commitment>> = vec![];
78
79    // Also construct mapping from a unique point to a point_index. This defines
80    // an ordering on the points.
81    let mut point_index_map = BTreeMap::new();
82
83    // Iterate over all of the queries, computing the ordering of the points
84    // while also creating new commitment data.
85    for query in queries.clone() {
86        let num_points = point_index_map.len();
87        let point_idx = point_index_map
88            .entry(query.get_point())
89            .or_insert(num_points);
90
91        if let Some(pos) = commitment_map
92            .iter()
93            .position(|comm| comm.commitment == query.get_commitment())
94        {
95            commitment_map[pos].point_indices.push(*point_idx);
96        } else {
97            let mut tmp = CommitmentData::new(query.get_commitment());
98            tmp.point_indices.push(*point_idx);
99            commitment_map.push(tmp);
100        }
101    }
102
103    // Also construct inverse mapping from point_index to the point
104    let mut inverse_point_index_map = BTreeMap::new();
105    for (&point, &point_index) in point_index_map.iter() {
106        inverse_point_index_map.insert(point_index, point);
107    }
108
109    // Construct map of unique ordered point_idx_sets to their set_idx
110    let mut point_idx_sets = BTreeMap::new();
111    // Also construct mapping from commitment to point_idx_set
112    let mut commitment_set_map = Vec::new();
113
114    for commitment_data in commitment_map.iter() {
115        let mut point_index_set = BTreeSet::new();
116        // Note that point_index_set is ordered, unlike point_indices
117        for &point_index in commitment_data.point_indices.iter() {
118            point_index_set.insert(point_index);
119        }
120
121        // Push point_index_set to CommitmentData for the relevant commitment
122        commitment_set_map.push((commitment_data.commitment, point_index_set.clone()));
123
124        let num_sets = point_idx_sets.len();
125        point_idx_sets.entry(point_index_set).or_insert(num_sets);
126    }
127
128    // Initialise empty evals vec for each unique commitment
129    for commitment_data in commitment_map.iter_mut() {
130        let len = commitment_data.point_indices.len();
131        commitment_data.evals = vec![Q::Eval::default(); len];
132    }
133
134    // Populate set_index, evals and points for each commitment using point_idx_sets
135    for query in queries {
136        // The index of the point at which the commitment is queried
137        let point_index = point_index_map.get(&query.get_point()).unwrap();
138
139        // The point_index_set at which the commitment was queried
140        let mut point_index_set = BTreeSet::new();
141        for (commitment, point_idx_set) in commitment_set_map.iter() {
142            if query.get_commitment() == *commitment {
143                point_index_set = point_idx_set.clone();
144            }
145        }
146        assert!(!point_index_set.is_empty());
147
148        // The set_index of the point_index_set
149        let set_index = point_idx_sets.get(&point_index_set).unwrap();
150        for commitment_data in commitment_map.iter_mut() {
151            if query.get_commitment() == commitment_data.commitment {
152                commitment_data.set_index = *set_index;
153            }
154        }
155        let point_index_set: Vec<usize> = point_index_set.iter().cloned().collect();
156
157        // The offset of the point_index in the point_index_set
158        let point_index_in_set = point_index_set
159            .iter()
160            .position(|i| i == point_index)
161            .unwrap();
162
163        for commitment_data in commitment_map.iter_mut() {
164            if query.get_commitment() == commitment_data.commitment {
165                // Insert the eval using the ordering of the point_index_set
166                commitment_data.evals[point_index_in_set] = query.get_eval();
167            }
168        }
169    }
170
171    // Get actual points in each point set
172    let mut point_sets: Vec<Vec<F>> = vec![Vec::new(); point_idx_sets.len()];
173    for (point_idx_set, &set_idx) in point_idx_sets.iter() {
174        for &point_idx in point_idx_set.iter() {
175            let point = inverse_point_index_map.get(&point_idx).unwrap();
176            point_sets[set_idx].push(*point);
177        }
178    }
179
180    Some((commitment_map, point_sets))
181}
halo2_axiom/poly/ipa/multiopen.rs

halo2_axiom/poly/ipa/
multiopen.rs
