Skip to main content

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}