binius_circuits/lasso/
lasso.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use anyhow::{ensure, Error, Result};
4use binius_core::{
5	constraint_system::channel::{ChannelId, OracleOrConst},
6	oracle::OracleId,
7};
8use binius_field::{
9	as_packed_field::{PackScalar, PackedType},
10	ExtensionField, Field, PackedFieldIndexable, TowerField,
11};
12use itertools::{izip, Itertools};
13
14use crate::{
15	builder::{
16		types::{F, U},
17		ConstraintSystemBuilder,
18	},
19	transparent,
20};
21
22pub fn lasso<FC>(
23	builder: &mut ConstraintSystemBuilder,
24	name: impl ToString,
25	n_lookups: &[usize],
26	u_to_t_mappings: &[impl AsRef<[usize]>],
27	lookups_u: &[impl AsRef<[OracleId]>],
28	lookup_t: impl AsRef<[OracleId]>,
29	channel: ChannelId,
30) -> Result<()>
31where
32	FC: TowerField,
33	U: PackScalar<FC>,
34	F: ExtensionField<FC> + From<FC>,
35	PackedType<U, FC>: PackedFieldIndexable,
36{
37	if n_lookups.len() != lookups_u.len() {
38		Err(anyhow::Error::msg("n_vars and lookups_u must be of the same length"))?;
39	}
40
41	if n_lookups.iter().sum::<usize>() >= 1 << FC::N_BITS {
42		Err(anyhow::Error::msg("FC too small"))?;
43	}
44
45	if lookups_u
46		.iter()
47		.any(|oracles| oracles.as_ref().len() != lookup_t.as_ref().len())
48	{
49		Err(anyhow::Error::msg(
50			"looked up and lookup tables must have the same number of oracles",
51		))?;
52	}
53
54	builder.push_namespace(name);
55
56	let u_log_rows = lookups_u
57		.iter()
58		.map(|row_oracles| builder.log_rows(row_oracles.as_ref().iter().copied()))
59		.collect::<Result<Vec<_>, Error>>()?;
60
61	for (n_lookups, u_log_rows) in n_lookups.iter().zip(&u_log_rows) {
62		ensure!(*n_lookups <= 1 << *u_log_rows);
63	}
64
65	let t_log_rows = builder.log_rows(lookup_t.as_ref().iter().copied())?;
66	let lookup_o = transparent::constant(builder, "lookup_o", t_log_rows, Field::ONE)?;
67	let lookup_f = builder.add_committed("lookup_f", t_log_rows, FC::TOWER_LEVEL);
68	let lookups_r = u_log_rows
69		.iter()
70		.map(|&u_log_rows| builder.add_committed("lookup_r", u_log_rows, FC::TOWER_LEVEL))
71		.collect_vec();
72
73	let lookups_w = u_log_rows
74		.iter()
75		.zip(&lookups_r)
76		.map(|(u_log_rows, lookup_r)| {
77			Ok(builder.add_linear_combination(
78				"lookup_w",
79				*u_log_rows,
80				[(*lookup_r, FC::MULTIPLICATIVE_GENERATOR.into())],
81			)?)
82		})
83		.collect::<Result<Vec<_>, anyhow::Error>>()?;
84
85	if let Some(witness) = builder.witness() {
86		if u_log_rows.len() != u_to_t_mappings.len() {
87			Err(anyhow::Error::msg("u_log_rows and u_to_t_mappings must be of the same length"))?;
88		}
89
90		let mut lookup_f_witness = witness.new_column::<FC>(lookup_f);
91
92		let lookup_f_scalars = PackedType::<U, FC>::unpack_scalars_mut(lookup_f_witness.packed());
93
94		let alpha = FC::MULTIPLICATIVE_GENERATOR;
95
96		lookup_f_scalars.fill(FC::ONE);
97
98		for (u_to_t_mapping, &n_lookups, &lookup_r, &lookup_w) in
99			izip!(u_to_t_mappings, n_lookups, &lookups_r, &lookups_w)
100		{
101			let mut lookup_r_witness = witness.new_column::<FC>(lookup_r);
102			let mut lookup_w_witness = witness.new_column::<FC>(lookup_w);
103
104			let lookup_r_scalars =
105				PackedType::<U, FC>::unpack_scalars_mut(lookup_r_witness.packed());
106			let lookup_w_scalars =
107				PackedType::<U, FC>::unpack_scalars_mut(lookup_w_witness.packed());
108
109			lookup_r_scalars.fill(FC::ONE);
110			lookup_w_scalars.fill(alpha);
111
112			for (&index, r, w) in
113				izip!(u_to_t_mapping.as_ref(), lookup_r_scalars, lookup_w_scalars).take(n_lookups)
114			{
115				let ts = lookup_f_scalars[index];
116				*r = ts;
117				*w = ts * alpha;
118				lookup_f_scalars[index] *= alpha;
119			}
120		}
121	}
122
123	lookups_r
124		.iter()
125		.for_each(|lookup_r| builder.assert_not_zero(*lookup_r));
126
127	let oracles_prefix_t = lookup_t.as_ref().iter().copied();
128
129	// populate table using initial timestamps
130	builder.send(
131		channel,
132		1 << t_log_rows,
133		oracles_prefix_t
134			.clone()
135			.chain([lookup_o])
136			.map(OracleOrConst::Oracle),
137	)?;
138
139	// for every value looked up, pull using current timestamp and push with incremented timestamp
140	izip!(lookups_u, lookups_r, lookups_w, n_lookups).try_for_each(
141		|(lookup_u, lookup_r, lookup_w, &n_lookup)| -> Result<()> {
142			let oracle_prefix_u = lookup_u.as_ref().iter().copied();
143			builder.receive(
144				channel,
145				n_lookup,
146				oracle_prefix_u
147					.clone()
148					.chain([lookup_r])
149					.map(OracleOrConst::Oracle),
150			)?;
151			builder.send(
152				channel,
153				n_lookup,
154				oracle_prefix_u.chain([lookup_w]).map(OracleOrConst::Oracle),
155			)?;
156			Ok(())
157		},
158	)?;
159
160	// depopulate table using final timestamps
161	builder.receive(
162		channel,
163		1 << t_log_rows,
164		oracles_prefix_t
165			.chain([lookup_f])
166			.map(OracleOrConst::Oracle),
167	)?;
168
169	Ok(())
170}
binius_circuits/lasso/lasso.rs

binius_circuits/lasso/
lasso.rs
