binius_iop/basefold/layout.rs
1// Copyright 2026 The Binius Developers
2
3//! Placement of each round's oracles inside the one oracle the round is committed as.
4//!
5//! # The ZK pad
6//!
7//! The query phase opens the codeword `Enc(M_r)` of every round oracle at up to `q =
8//! n_test_queries` positions, one per test query. The mask `ω_r` interleaved with a
9//! zero-knowledge round hides the folding phase, but not these symbols. Such a round therefore
10//! also carries a ZK pad: coordinates outside every constituent's extent, which the prover fills
11//! with uniform elements. The pad hides the opened symbols when, for every set of at most `q`
12//! positions, the symbols restricted to the pad are linearly independent functionals.
13//!
14//! Where the pad sits decides whether that holds. The encoder reads entry `i` of an `ℓ`-variate
15//! table as the coefficient of the novel basis polynomial `X_i`. It evaluates over a subspace `S`
16//! that contains 0, at index 0. Every `X_c` with `c ≥ 2^k` vanishes on `U_k = span(β_0, …,
17//! β_{k-1})`, so a symbol at a position in `U_k` reads only the entries `c < 2^k`. Those are the
18//! first entries of the table, which are the first entries of the round's largest constituent. No
19//! pad outside the extents reaches them.
20//!
21//! A zero-knowledge round is therefore committed reversed: entry `i` of its committed table is
22//! `M_r[σ(i)]`, where [`zk_commit_index`] gives `σ`, which complements the bits of `i`. Coefficient
23//! `c` of its codeword is then `M_r[2^ℓ - 1 - c]`. The pad is the top `q` coordinates of `M_r`, so
24//! it fills the coefficients `0..q`, whose basis polynomials span the polynomials of degree below
25//! `q`. Restricted to the pad, the symbols at `q` distinct positions are evaluations of those
26//! polynomials at distinct points, and these are linearly independent by interpolation.
27//!
28//! The opening runs on the committed table and does not see the reversal, except where the
29//! verifier evaluates a transparent: for a zero-knowledge round it does so at
30//! [`zk_commit_point`] of the round's point.
31
32use std::{cmp::Reverse, ops::Range};
33
34use binius_field::FieldOps;
35use binius_utils::checked_arithmetics::log2_ceil_usize;
36
37use crate::channel::{OracleSchedule, OracleSpec};
38
39/// How one round's oracles sit inside the round oracle `M_r` they are committed as.
40#[derive(Debug, Clone, PartialEq, Eq)]
41pub struct RoundLayout {
42 /// The base-2 logarithm of the round oracle's length.
43 pub log_len: usize,
44 /// Whether the round oracle is masked, which it is if any constituent is.
45 pub is_zk: bool,
46 /// Per constituent, in arrival order, the block it occupies.
47 ///
48 /// Constituent `i` of `2^ℓ_i` entries occupies `M_r[b_i · 2^ℓ_i .. (b_i + 1) · 2^ℓ_i]`, and
49 /// only its first `len_i` entries carry content.
50 pub block_offsets: Vec<usize>,
51 /// The length of the ZK pad, which is the top `pad_len` coordinates of `M_r`.
52 ///
53 /// It is `n_test_queries` for a zero-knowledge round and zero for any other. See the
54 /// [module documentation](self) for why the pad sits at the top.
55 pub pad_len: usize,
56}
57
58impl RoundLayout {
59 /// The spec of the round oracle itself.
60 pub const fn spec(&self) -> OracleSpec {
61 OracleSpec {
62 len: 1 << self.log_len,
63 is_zk: self.is_zk,
64 }
65 }
66
67 /// The coordinates of `M_r` that make up the ZK pad.
68 pub const fn pad(&self) -> Range<usize> {
69 let len = 1 << self.log_len;
70 len - self.pad_len..len
71 }
72}
73
74/// Lays out every round of a schedule.
75///
76/// Constituents are placed in nonincreasing order of `ℓ_i`, each at the lowest multiple of `2^ℓ_i`
77/// whose block avoids every extent already placed. An extent is the first `len_j` entries of a
78/// placed block, so a constituent may nest in the slack above another's content:
79///
80/// ```text
81/// [ private: 98332 of 2^17 | mask 2^9 | precommit 2^10 | unused | pad ]
82/// 0 98816 99328 100352 2^17 - q 2^17
83/// ```
84///
85/// A zero-knowledge round reserves its top `q = n_test_queries` coordinates as the ZK pad. The
86/// round oracle is the least power of two holding every block with the pad above every extent.
87/// With every `len_i` a full power of two, the blocks lie end to end, and a zero-knowledge round
88/// whose blocks fill a power of two grows to the next one to make room for its pad.
89pub fn layout_rounds(schedule: &OracleSchedule, n_test_queries: usize) -> Vec<RoundLayout> {
90 schedule
91 .rounds()
92 .map(|specs| layout_round(specs, n_test_queries))
93 .collect()
94}
95
96/// The coordinate of `M_r` that entry `index` of a zero-knowledge round's committed table holds.
97///
98/// The map complements the low `log_len` bits of `index`, which reverses the order of the round.
99/// It is its own inverse, so it also gives the entry that a coordinate is committed at. See the
100/// [module documentation](self) for why a zero-knowledge round is committed reversed.
101pub const fn zk_commit_index(index: usize, log_len: usize) -> usize {
102 index ^ ((1 << log_len) - 1)
103}
104
105/// The point over `M_r` that corresponds to `point` over a zero-knowledge round's committed table.
106///
107/// For any table `T` over the round, let `T'` be `T` reversed the way the round is committed,
108/// `T'[i] = T[zk_commit_index(i)]`. The multilinear extension of `T'` at `point` equals that of
109/// `T` at `zk_commit_point(point)`, which is `(1 - point[0], …, 1 - point[ℓ-1])`: complementing a
110/// bit of an index complements its coordinate.
111pub fn zk_commit_point<E: FieldOps>(point: &[E]) -> Vec<E> {
112 point
113 .iter()
114 .map(|coordinate| E::one() - coordinate)
115 .collect()
116}
117
118fn layout_round(specs: &[OracleSpec], n_test_queries: usize) -> RoundLayout {
119 let mut order = (0..specs.len()).collect::<Vec<_>>();
120 order.sort_by_key(|&i| Reverse(specs[i].len));
121
122 // Every placed extent as a half-open scalar range, kept sorted and disjoint.
123 let mut extents = Vec::<Range<usize>>::with_capacity(specs.len());
124 let mut block_offsets = vec![0; specs.len()];
125 let mut end = 1;
126 for i in order {
127 let log_block = specs[i].log_msg_len();
128
129 // Scan the extents in order for the lowest block that fits before the next one, hopping
130 // past each extent that it would overlap.
131 // Because the extents are sorted, the offset only moves forward, and the break index is
132 // also where the new extent is inserted.
133 let mut offset = 0;
134 let mut pos = extents.len();
135 for (j, extent) in extents.iter().enumerate() {
136 if (offset + 1) << log_block <= extent.start {
137 pos = j;
138 break;
139 }
140 offset = extent.end.div_ceil(1 << log_block);
141 }
142
143 let start = offset << log_block;
144 let extent = start..start + specs[i].len;
145 extents.insert(pos, extent);
146 end = end.max((offset + 1) << log_block);
147 block_offsets[i] = offset;
148 }
149
150 // The pad is the top `pad_len` coordinates, so the round must reach `pad_len` past the highest
151 // extent, which is the last one because the extents are sorted and disjoint.
152 let is_zk = specs.iter().any(|spec| spec.is_zk);
153 let pad_len = if is_zk { n_test_queries } else { 0 };
154 let content_end = extents.last().map_or(0, |extent| extent.end);
155 end = end.max(content_end + pad_len);
156
157 RoundLayout {
158 log_len: log2_ceil_usize(end),
159 is_zk,
160 block_offsets,
161 pad_len,
162 }
163}
164
165#[cfg(test)]
166mod tests {
167 use std::iter;
168
169 use super::*;
170
171 /// A query count small enough to keep the test shapes readable.
172 const N_TEST_QUERIES: usize = 32;
173
174 fn layout(specs: &[OracleSpec]) -> RoundLayout {
175 let schedule = OracleSchedule::from_rounds([specs.iter().copied()]);
176 let mut layouts = layout_rounds(&schedule, N_TEST_QUERIES);
177 assert_eq!(layouts.len(), 1);
178 layouts.pop().unwrap()
179 }
180
181 #[test]
182 fn spartan_shape_fits_one_round_of_its_largest_oracle() {
183 // [precommit 2^10, private 2^17 holding 98332, mask 2^9]: the small two nest in the
184 // private oracle's slack and the pad fits above them, so the round stays at 2^17 rather
185 // than growing to 2^18.
186 let layout = layout(&[
187 OracleSpec::new_zk(1 << 10),
188 OracleSpec::new_zk(98332),
189 OracleSpec::new_zk(1 << 9),
190 ]);
191 assert_eq!(layout.log_len, 17);
192 assert!(layout.is_zk);
193 assert_eq!(layout.block_offsets, [97, 0, 193]);
194 assert_eq!(layout.pad(), (1 << 17) - N_TEST_QUERIES..1 << 17);
195 }
196
197 #[test]
198 fn a_tenant_nests_in_another_tenants_slack() {
199 // The 2^4 oracle holds 9 entries and sits in the 2^5 one's slack at 16. The 2^2 oracle
200 // finds no room in the 2^5 one's slack, and nests in the 2^4 one's at 28. It alone is
201 // masked, which masks the whole round. Its extent ends at the round's top, so the pad
202 // grows the round to 2^6.
203 let layout = layout(&[
204 OracleSpec::new(15),
205 OracleSpec::new(9),
206 OracleSpec::new_zk(1 << 2),
207 ]);
208 assert_eq!(layout.log_len, 6);
209 assert!(layout.is_zk);
210 assert_eq!(layout.block_offsets, [0, 1, 7]);
211 assert_eq!(layout.pad(), 32..64);
212 }
213
214 #[test]
215 fn full_oracles_lie_end_to_end_and_grow_the_round() {
216 // 2^2 + 2^4 + 2^2 = 24, so the round grows to 2^5 with the largest first.
217 let layout = layout(&[
218 OracleSpec::new(1 << 2),
219 OracleSpec::new(1 << 4),
220 OracleSpec::new(1 << 2),
221 ]);
222 assert_eq!(layout.log_len, 5);
223 assert!(!layout.is_zk);
224 assert_eq!(layout.block_offsets, [4, 0, 5]);
225 }
226
227 #[test]
228 fn oracles_sharing_a_log_length_are_placed_longest_first() {
229 // Both oracles have log length 4, but the 16-entry one is longer, so it is placed first
230 // despite coming second.
231 let layout = layout(&[OracleSpec::new(9), OracleSpec::new(16)]);
232 assert_eq!(layout.log_len, 5);
233 assert_eq!(layout.block_offsets, [1, 0]);
234 }
235
236 #[test]
237 fn a_lone_oracle_is_its_own_round() {
238 let layout = layout(&[OracleSpec::new(5)]);
239 assert_eq!(layout.spec(), OracleSpec::new(1 << 3));
240 assert_eq!(layout.block_offsets, [0]);
241 }
242
243 #[test]
244 fn a_non_zk_round_carries_no_pad() {
245 let layout = layout(&[OracleSpec::new(1 << 10)]);
246 assert_eq!(layout.log_len, 10);
247 assert_eq!(layout.pad_len, 0);
248 assert!(layout.pad().is_empty());
249 }
250
251 #[test]
252 fn a_zk_round_with_slack_at_the_top_keeps_its_size() {
253 let layout = layout(&[OracleSpec::new_zk(900)]);
254 assert_eq!(layout.log_len, 10);
255 assert_eq!(layout.pad(), 1024 - N_TEST_QUERIES..1024);
256 }
257
258 #[test]
259 fn a_zk_round_without_slack_at_the_top_grows_for_its_pad() {
260 // The content ends 16 short of the top, which is not room enough for 32 pad coordinates.
261 let layout = layout(&[OracleSpec::new_zk(1024 - 16)]);
262 assert_eq!(layout.log_len, 11);
263 assert_eq!(layout.block_offsets, [0]);
264 assert_eq!(layout.pad(), 2048 - N_TEST_QUERIES..2048);
265 }
266
267 #[test]
268 fn the_pad_lies_above_every_extent() {
269 let shapes: [&[OracleSpec]; 4] = [
270 &[OracleSpec::new_zk(1 << 4)],
271 &[OracleSpec::new_zk(1 << 5), OracleSpec::new(1 << 5)],
272 &[
273 OracleSpec::new_zk(40),
274 OracleSpec::new(7),
275 OracleSpec::new(1 << 3),
276 ],
277 &[
278 OracleSpec::new(100),
279 OracleSpec::new_zk(1 << 6),
280 OracleSpec::new(3),
281 ],
282 ];
283 for specs in shapes {
284 let layout = layout(specs);
285 assert_eq!(layout.pad_len, N_TEST_QUERIES);
286 for (spec, &offset) in iter::zip(specs, &layout.block_offsets) {
287 let start = offset << spec.log_msg_len();
288 assert!(start + spec.len <= layout.pad().start, "{specs:?}");
289 }
290 }
291 }
292
293 #[test]
294 fn zk_commit_index_complements_the_bits() {
295 assert_eq!(zk_commit_index(0b001, 3), 0b110);
296 assert_eq!(zk_commit_index(0b110, 3), 0b001);
297 assert_eq!(zk_commit_index(0, 0), 0);
298 for log_len in 0..8 {
299 for index in 0..1 << log_len {
300 assert_eq!(zk_commit_index(zk_commit_index(index, log_len), log_len), index);
301 }
302 }
303 }
304
305 #[test]
306 fn the_reversal_puts_coordinate_c_from_the_top_on_coefficient_c() {
307 // The encoder reads entry `i` of the committed table as the coefficient `i`.
308 for log_len in 0..8 {
309 for coordinate in 0..1 << log_len {
310 let coefficient = zk_commit_index(coordinate, log_len);
311 assert_eq!(coefficient, (1 << log_len) - 1 - coordinate);
312 }
313 }
314 }
315}