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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
use itertools::Itertools;
use serde::{Deserialize, Serialize};
use std_shims::{vec, BTreeMap, Vec};
use thiserror::Error;
use super::utils::{next_decommitment_node, option_flatten_peekable};
use crate::core::fields::m31::BaseField;
use crate::core::utils::PeekableExt;
use crate::core::vcs::MerkleHasher;
#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, Eq, PartialOrd)]
pub struct MerkleDecommitment<H: MerkleHasher> {
/// Hash values that the verifier needs but cannot deduce from previous computations, in the
/// order they are needed.
pub hash_witness: Vec<H::Hash>,
/// Column values that the verifier needs but cannot deduce from previous computations, in the
/// order they are needed.
/// This complements the column values that were queried. These must be supplied directly to
/// the verifier.
pub column_witness: Vec<BaseField>,
}
impl<H: MerkleHasher> MerkleDecommitment<H> {
pub const fn empty() -> Self {
Self {
hash_witness: Vec::new(),
column_witness: Vec::new(),
}
}
}
pub struct MerkleVerifier<H: MerkleHasher> {
pub root: H::Hash,
pub column_log_sizes: Vec<u32>,
pub n_columns_per_log_size: BTreeMap<u32, usize>,
}
impl<H: MerkleHasher> MerkleVerifier<H> {
pub fn new(root: H::Hash, column_log_sizes: Vec<u32>) -> Self {
let mut n_columns_per_log_size = BTreeMap::new();
for log_size in &column_log_sizes {
*n_columns_per_log_size.entry(*log_size).or_insert(0) += 1;
}
Self {
root,
column_log_sizes,
n_columns_per_log_size,
}
}
/// Verifies the decommitment of the columns.
///
/// Returns `Ok(())` if the decommitment is successfully verified.
///
/// # Arguments
///
/// * `queries_per_log_size` - A map from log_size to a vector of queries for columns of that
/// log_size.
/// * `queried_values` - A vector of queried values according to the order in
/// [`MerkleProver::decommit()`].
/// * `decommitment` - The decommitment object containing the witness and column values.
///
/// # Errors
///
/// Returns an error if any of the following conditions are met:
///
/// * The witness is too long (not fully consumed).
/// * The witness is too short (missing values).
/// * Too many queried values (not fully consumed).
/// * Too few queried values (missing values).
/// * The computed root does not match the expected root.
///
/// [`MerkleProver::decommit()`]: crate::core::...::MerkleProver::decommit
pub fn verify(
&self,
queries_per_log_size: &BTreeMap<u32, Vec<usize>>,
queried_values: Vec<BaseField>,
decommitment: MerkleDecommitment<H>,
) -> Result<(), MerkleVerificationError> {
let Some(max_log_size) = self.column_log_sizes.iter().max() else {
return Ok(());
};
let mut queried_values = queried_values.into_iter();
// Prepare read buffers.
let mut hash_witness = decommitment.hash_witness.into_iter();
let mut column_witness = decommitment.column_witness.into_iter();
let mut last_layer_hashes: Option<Vec<(usize, H::Hash)>> = None;
for layer_log_size in (0..=*max_log_size).rev() {
let n_columns_in_layer = *self
.n_columns_per_log_size
.get(&layer_log_size)
.unwrap_or(&0);
// Prepare write buffer for queries to the current layer. This will propagate to the
// next layer.
let mut layer_total_queries = vec![];
// Queries to this layer come from queried node in the previous layer and queried
// columns in this one.
let mut prev_layer_queries = last_layer_hashes
.iter()
.flatten()
.map(|(q, _)| *q)
.collect_vec()
.into_iter()
.peekable();
let mut prev_layer_hashes = last_layer_hashes.as_ref().map(|x| x.iter().peekable());
let mut layer_column_queries =
option_flatten_peekable(queries_per_log_size.get(&layer_log_size));
// Merge previous layer queries and column queries.
while let Some(node_index) =
next_decommitment_node(&mut prev_layer_queries, &mut layer_column_queries)
{
prev_layer_queries
.peek_take_while(|q| q / 2 == node_index)
.for_each(drop);
let node_hashes = prev_layer_hashes
.as_mut()
.map(|prev_layer_hashes| {
{
// If the left child was not computed, read it from the witness.
let left_hash = prev_layer_hashes
.next_if(|(index, _)| *index == 2 * node_index)
.map(|(_, hash)| Ok(*hash))
.unwrap_or_else(|| {
hash_witness
.next()
.ok_or(MerkleVerificationError::WitnessTooShort)
})?;
// If the right child was not computed, read it to from the witness.
let right_hash = prev_layer_hashes
.next_if(|(index, _)| *index == 2 * node_index + 1)
.map(|(_, hash)| Ok(*hash))
.unwrap_or_else(|| {
hash_witness
.next()
.ok_or(MerkleVerificationError::WitnessTooShort)
})?;
Ok((left_hash, right_hash))
}
})
.transpose()?;
// If the column values were queried, read them from `queried_value`.
let (err, node_values_iter) = match layer_column_queries.next_if_eq(&node_index) {
Some(_) => (
MerkleVerificationError::TooFewQueriedValues,
&mut queried_values,
),
// Otherwise, read them from the witness.
None => (
MerkleVerificationError::WitnessTooShort,
&mut column_witness,
),
};
let node_values = node_values_iter.take(n_columns_in_layer).collect_vec();
if node_values.len() != n_columns_in_layer {
return Err(err);
}
layer_total_queries.push((node_index, H::hash_node(node_hashes, &node_values)));
}
last_layer_hashes = Some(layer_total_queries);
}
// Check that all witnesses and values have been consumed.
if hash_witness.next().is_some() {
return Err(MerkleVerificationError::WitnessTooLong);
}
if queried_values.next().is_some() {
return Err(MerkleVerificationError::TooManyQueriedValues);
}
if column_witness.next().is_some() {
return Err(MerkleVerificationError::WitnessTooLong);
}
let [(_, computed_root)] = last_layer_hashes.unwrap().try_into().unwrap();
if computed_root != self.root {
return Err(MerkleVerificationError::RootMismatch);
}
Ok(())
}
}
// TODO(ilya): Make error messages consistent.
#[derive(Clone, Copy, Debug, Error, PartialEq, Eq)]
pub enum MerkleVerificationError {
#[error("Witness is too short")]
WitnessTooShort,
#[error("Witness is too long.")]
WitnessTooLong,
#[error("too many Queried values")]
TooManyQueriedValues,
#[error("too few queried values")]
TooFewQueriedValues,
#[error("Root mismatch.")]
RootMismatch,
}