1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//! Prover
use crate::ml_sumcheck::data_structures::ListOfProductsOfPolynomials;
use crate::ml_sumcheck::protocol::verifier::VerifierMsg;
use crate::ml_sumcheck::protocol::IPForMLSumcheck;
use ark_ff::Field;
use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
use ark_std::{cfg_iter_mut, vec::Vec};
#[cfg(feature = "parallel")]
use rayon::prelude::*;
/// Prover Message
#[derive(Clone, CanonicalSerialize, CanonicalDeserialize)]
pub struct ProverMsg<F: Field> {
/// evaluations on P(0), P(1), P(2), ...
pub(crate) evaluations: Vec<F>,
}
/// Prover State
pub struct ProverState<F: Field> {
/// sampled randomness given by the verifier
pub randomness: Vec<F>,
/// Stores the list of products that is meant to be added together. Each multiplicand is represented by
/// the index in flattened_ml_extensions
pub list_of_products: Vec<(F, Vec<usize>)>,
/// Stores a list of multilinear extensions in which `self.list_of_products` points to
pub flattened_ml_extensions: Vec<DenseMultilinearExtension<F>>,
/// Number of variables
pub num_vars: usize,
/// Max number of multiplicands in a product
pub max_multiplicands: usize,
/// The current round number
pub round: usize,
}
impl<F: Field> IPForMLSumcheck<F> {
/// initialize the prover to argue for the sum of polynomial over {0,1}^`num_vars`
///
/// The polynomial is represented by a list of products of polynomials along with its coefficient that is meant to be added together.
///
/// This data structure of the polynomial is a list of list of `(coefficient, DenseMultilinearExtension)`.
/// * Number of products n = `polynomial.products.len()`,
/// * Number of multiplicands of ith product m_i = `polynomial.products[i].1.len()`,
/// * Coefficient of ith product c_i = `polynomial.products[i].0`
///
/// The resulting polynomial is
///
/// $$\sum_{i=0}^{n}C_i\cdot\prod_{j=0}^{m_i}P_{ij}$$
///
pub fn prover_init(polynomial: &ListOfProductsOfPolynomials<F>) -> ProverState<F> {
if polynomial.num_variables == 0 {
panic!("Attempt to prove a constant.")
}
// create a deep copy of all unique MLExtensions
let flattened_ml_extensions = polynomial
.flattened_ml_extensions
.iter()
.map(|x| x.as_ref().clone())
.collect();
ProverState {
randomness: Vec::with_capacity(polynomial.num_variables),
list_of_products: polynomial.products.clone(),
flattened_ml_extensions,
num_vars: polynomial.num_variables,
max_multiplicands: polynomial.max_multiplicands,
round: 0,
}
}
/// receive message from verifier, generate prover message, and proceed to next round
///
/// Main algorithm used is from section 3.2 of [XZZPS19](https://eprint.iacr.org/2019/317.pdf#subsection.3.2).
pub fn prove_round(
prover_state: &mut ProverState<F>,
v_msg: &Option<VerifierMsg<F>>,
) -> ProverMsg<F> {
if let Some(msg) = v_msg {
if prover_state.round == 0 {
panic!("first round should be prover first.");
}
prover_state.randomness.push(msg.randomness);
// fix argument
let i = prover_state.round;
let r = prover_state.randomness[i - 1];
cfg_iter_mut!(prover_state.flattened_ml_extensions).for_each(|multiplicand| {
*multiplicand = multiplicand.fix_variables(&[r]);
});
} else if prover_state.round > 0 {
panic!("verifier message is empty");
}
prover_state.round += 1;
if prover_state.round > prover_state.num_vars {
panic!("Prover is not active");
}
let i = prover_state.round;
let nv = prover_state.num_vars;
let degree = prover_state.max_multiplicands; // the degree of univariate polynomial sent by prover at this round
#[cfg(not(feature = "parallel"))]
let zeros = (vec![F::zero(); degree + 1], vec![F::zero(); degree + 1]);
#[cfg(feature = "parallel")]
let zeros = || (vec![F::zero(); degree + 1], vec![F::zero(); degree + 1]);
// generate sum
let fold_result = ark_std::cfg_into_iter!(0..1 << (nv - i), 1 << 10).fold(
zeros,
|(mut products_sum, mut product), b| {
// In effect, this fold is essentially doing simply:
// for b in 0..1 << (nv - i) {
for (coefficient, products) in &prover_state.list_of_products {
product.fill(*coefficient);
for &jth_product in products {
let table = &prover_state.flattened_ml_extensions[jth_product];
let mut start = table[b << 1];
let step = table[(b << 1) + 1] - start;
for p in product.iter_mut() {
*p *= start;
start += step;
}
}
for t in 0..degree + 1 {
products_sum[t] += product[t];
}
}
(products_sum, product)
},
);
#[cfg(not(feature = "parallel"))]
let products_sum = fold_result.0;
// When rayon is used, the `fold` operation results in a iterator of `Vec<F>` rather than a single `Vec<F>`. In this case, we simply need to sum them.
#[cfg(feature = "parallel")]
let products_sum = fold_result.map(|scratch| scratch.0).reduce(
|| vec![F::zero(); degree + 1],
|mut overall_products_sum, sublist_sum| {
overall_products_sum
.iter_mut()
.zip(sublist_sum.iter())
.for_each(|(f, s)| *f += s);
overall_products_sum
},
);
ProverMsg {
evaluations: products_sum,
}
}
}