1use std::{
5 cmp::Ordering,
6 collections::HashMap,
7 mem,
8 ops::{Index, IndexMut},
9};
10
11use binius_field::Field;
12use binius_utils::checked_arithmetics::log2_ceil_usize;
13use smallvec::{SmallVec, smallvec};
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
16pub enum WireKind {
17 Constant,
18 InOut,
19 Derived,
23 Precommit,
24 Private,
25}
26
27impl WireKind {
28 pub const fn segment(self) -> WitnessSegment {
31 match self {
32 WireKind::Constant | WireKind::InOut | WireKind::Derived => WitnessSegment::Public,
33 WireKind::Precommit => WitnessSegment::Precommit,
34 WireKind::Private => WitnessSegment::Private,
35 }
36 }
37
38 pub fn is_public(self) -> bool {
46 self.segment() == WitnessSegment::Public
47 }
48}
49
50#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
51pub struct ConstraintWire {
52 pub(crate) kind: WireKind,
53 pub(crate) id: u32,
54}
55
56impl ConstraintWire {
57 pub const fn inout(id: u32) -> Self {
61 Self {
62 kind: WireKind::InOut,
63 id,
64 }
65 }
66
67 pub const fn id(&self) -> u32 {
69 self.id
70 }
71
72 pub const fn precommit(id: u32) -> Self {
74 Self {
75 kind: WireKind::Precommit,
76 id,
77 }
78 }
79}
80
81#[derive(Debug, Clone)]
82pub struct Operand<W>(SmallVec<[W; 4]>);
83
84impl<W> Default for Operand<W> {
85 fn default() -> Self {
86 Operand(SmallVec::new())
87 }
88}
89
90impl<W: Copy + Ord> Operand<W> {
91 pub fn new(mut term: SmallVec<[W; 4]>) -> Self {
92 term.sort_unstable();
93
94 let has_duplicate_wire = term.windows(2).any(|w| w[0] == w[1]);
95 let term = if has_duplicate_wire {
96 term.chunk_by(|a, b| a == b)
97 .flat_map(|group| {
98 let last_even_idx = group.len() / 2 * 2;
101 group[last_even_idx..].iter().copied()
102 })
103 .collect()
104 } else {
105 term
106 };
107
108 Self(term)
109 }
110
111 pub fn len(&self) -> usize {
112 self.0.len()
113 }
114
115 pub fn is_empty(&self) -> bool {
116 self.0.is_empty()
117 }
118
119 pub fn wires(&self) -> &[W] {
120 &self.0
121 }
122
123 pub fn merge(&mut self, rhs: &Self) -> (Operand<W>, Operand<W>) {
124 let lhs = mem::take(&mut self.0);
126 let dst = &mut self.0;
127
128 let mut lhs_iter = lhs.into_iter().peekable();
129 let mut rhs_iter = rhs.0.iter().copied().peekable();
130
131 let mut additions = Operand::default();
132 let mut removals = Operand::default();
133
134 loop {
135 match (lhs_iter.peek(), rhs_iter.peek()) {
136 (Some(next_lhs), Some(next_rhs)) => {
137 match next_lhs.cmp(next_rhs) {
138 Ordering::Equal => {
139 let wire = lhs_iter.next().expect("peek returned Some");
141 let _ = rhs_iter.next().expect("peek returned Some");
142
143 removals.0.push(wire);
144 }
145 Ordering::Less => dst.push(lhs_iter.next().expect("peek returned Some")),
146 Ordering::Greater => {
147 let wire = rhs_iter.next().expect("peek returned Some");
148 additions.0.push(wire);
149 dst.push(wire);
150 }
151 }
152 }
153 (Some(_), None) => dst.push(lhs_iter.next().expect("peek returned Some")),
154 (None, Some(_)) => {
155 let wire = rhs_iter.next().expect("peek returned Some");
156 additions.0.push(wire);
157 dst.push(wire);
158 }
159 (None, None) => break,
160 }
161 }
162
163 (additions, removals)
164 }
165}
166
167impl<W> From<W> for Operand<W> {
168 fn from(value: W) -> Self {
169 Operand(smallvec![value])
170 }
171}
172
173#[derive(Debug, Clone)]
174pub struct MulConstraint<W> {
175 pub a: Operand<W>,
176 pub b: Operand<W>,
177 pub c: Operand<W>,
178}
179
180#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
181pub enum WitnessSegment {
182 Public,
184 Precommit,
187 Private,
190}
191
192#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
193pub struct WitnessIndex {
194 pub segment: WitnessSegment,
195 pub index: u32,
196}
197
198impl WitnessIndex {
199 pub const fn public(index: u32) -> Self {
200 Self {
201 segment: WitnessSegment::Public,
202 index,
203 }
204 }
205
206 pub const fn precommit(index: u32) -> Self {
207 Self {
208 segment: WitnessSegment::Precommit,
209 index,
210 }
211 }
212
213 pub const fn private(index: u32) -> Self {
214 Self {
215 segment: WitnessSegment::Private,
216 index,
217 }
218 }
219}
220
221pub struct Witness<F> {
222 public: Vec<F>,
223 precommit: Vec<F>,
224 private: Vec<F>,
225}
226
227impl<F> Witness<F> {
228 pub const fn new(public: Vec<F>, precommit: Vec<F>, private: Vec<F>) -> Self {
229 Self {
230 public,
231 precommit,
232 private,
233 }
234 }
235
236 pub fn public(&self) -> &[F] {
237 &self.public
238 }
239
240 pub fn precommit(&self) -> &[F] {
241 &self.precommit
242 }
243
244 pub fn private(&self) -> &[F] {
245 &self.private
246 }
247}
248
249impl<F> Index<WitnessIndex> for Witness<F> {
250 type Output = F;
251
252 fn index(&self, index: WitnessIndex) -> &Self::Output {
253 match index.segment {
254 WitnessSegment::Public => &self.public[index.index as usize],
255 WitnessSegment::Precommit => &self.precommit[index.index as usize],
256 WitnessSegment::Private => &self.private[index.index as usize],
257 }
258 }
259}
260
261impl<F> IndexMut<WitnessIndex> for Witness<F> {
262 fn index_mut(&mut self, index: WitnessIndex) -> &mut Self::Output {
263 match index.segment {
264 WitnessSegment::Public => &mut self.public[index.index as usize],
265 WitnessSegment::Precommit => &mut self.precommit[index.index as usize],
266 WitnessSegment::Private => &mut self.private[index.index as usize],
267 }
268 }
269}
270
271#[derive(Debug, Clone)]
279pub struct ConstraintSystem<F: Field> {
280 constants: Vec<F>,
281 n_inout: u32,
282 n_precommit: u32,
283 n_private: u32,
284 log_public: u32,
285 mul_constraints: Vec<MulConstraint<WitnessIndex>>,
286 one_wire_index: u32,
287}
288
289impl<F: Field> ConstraintSystem<F> {
290 pub const fn new(
292 constants: Vec<F>,
293 n_inout: u32,
294 n_precommit: u32,
295 n_private: u32,
296 log_public: u32,
297 mul_constraints: Vec<MulConstraint<WitnessIndex>>,
298 one_wire_index: u32,
299 ) -> Self {
300 Self {
301 constants,
302 n_inout,
303 n_precommit,
304 n_private,
305 log_public,
306 mul_constraints,
307 one_wire_index,
308 }
309 }
310
311 pub fn constants(&self) -> &[F] {
312 &self.constants
313 }
314
315 pub const fn n_inout(&self) -> u32 {
316 self.n_inout
317 }
318
319 pub const fn n_precommit(&self) -> u32 {
320 self.n_precommit
321 }
322
323 pub const fn n_private(&self) -> u32 {
324 self.n_private
325 }
326
327 pub const fn log_public(&self) -> u32 {
328 self.log_public
329 }
330
331 pub const fn n_public(&self) -> u32 {
332 1 << self.log_public
333 }
334
335 pub fn mul_constraints(&self) -> &[MulConstraint<WitnessIndex>] {
336 &self.mul_constraints
337 }
338
339 pub const fn one_wire(&self) -> WitnessIndex {
340 WitnessIndex {
341 segment: WitnessSegment::Public,
342 index: self.one_wire_index,
343 }
344 }
345
346 pub fn validate(&self, witness: &Witness<F>) {
348 let operand_val = |operand: &Operand<WitnessIndex>| {
349 operand.wires().iter().map(|&idx| witness[idx]).sum::<F>()
350 };
351
352 for MulConstraint { a, b, c } in &self.mul_constraints {
353 assert_eq!(operand_val(a) * operand_val(b), operand_val(c));
354 }
355 }
356}
357
358#[derive(Debug, Clone, Copy)]
364pub struct BlindingInfo {
365 pub n_dummy_constraints: usize,
367}
368
369const N_DUMMY_CONSTRAINTS: usize = 2;
391
392impl Default for BlindingInfo {
393 fn default() -> Self {
394 Self {
395 n_dummy_constraints: N_DUMMY_CONSTRAINTS,
396 }
397 }
398}
399
400#[derive(Debug, Clone)]
401pub struct WitnessLayout<F: Field> {
402 pub(crate) constants: Vec<F>,
403 n_inout: u32,
404 n_derived: u32,
405 n_precommit: u32,
406 n_private: u32,
407 log_public: u32,
408 log_precommit: u32,
409 log_private: u32,
410 derived_index_map: HashMap<u32, u32>,
411 private_index_map: HashMap<u32, u32>,
412}
413
414impl<F: Field> WitnessLayout<F> {
415 pub fn sparse(
416 constants: Vec<F>,
417 n_inout: u32,
418 n_precommit: u32,
419 derived_alive: &[bool],
420 private_alive: &[bool],
421 ) -> Self {
422 let n_constants = constants.len() as u32;
423 let log_precommit = log2_ceil_usize(n_precommit as usize) as u32;
424
425 let derived_index_map = derived_alive
429 .iter()
430 .enumerate()
431 .filter(|(_, alive)| **alive)
432 .enumerate()
433 .map(|(new_idx, (id, _))| (id as u32, new_idx as u32))
434 .collect::<HashMap<_, _>>();
435
436 let n_derived = derived_index_map.len() as u32;
437 let n_public = n_constants + n_inout + n_derived;
438 let log_public = log2_ceil_usize(n_public as usize) as u32;
439
440 let private_index_map = private_alive
441 .iter()
442 .enumerate()
443 .filter(|(_, alive)| **alive)
444 .enumerate()
445 .map(|(new_idx, (id, _))| (id as u32, new_idx as u32))
446 .collect::<HashMap<_, _>>();
447
448 let n_private = private_index_map.len() as u32;
449 let log_private = log2_ceil_usize(n_private as usize) as u32;
450
451 Self {
452 constants,
453 n_inout,
454 n_derived,
455 n_precommit,
456 n_private,
457 log_public,
458 log_precommit,
459 log_private,
460 derived_index_map,
461 private_index_map,
462 }
463 }
464
465 pub fn with_blinding(self, info: BlindingInfo) -> Self {
466 let blinding_size = 3 * info.n_dummy_constraints;
471
472 let total_precommit = self.n_precommit as usize + blinding_size;
473 let log_precommit = log2_ceil_usize(total_precommit) as u32;
474
475 let total_private = self.n_private as usize + blinding_size;
476 let log_private = log2_ceil_usize(total_private) as u32;
477
478 Self {
479 log_precommit,
480 log_private,
481 ..self
482 }
483 }
484
485 pub const fn public_size(&self) -> usize {
486 1 << self.log_public as usize
487 }
488
489 pub const fn precommit_size(&self) -> usize {
490 1 << self.log_precommit as usize
491 }
492
493 pub const fn private_size(&self) -> usize {
494 1 << self.log_private as usize
495 }
496
497 pub const fn n_constants(&self) -> usize {
498 self.constants.len()
499 }
500
501 pub const fn n_inout(&self) -> usize {
502 self.n_inout as usize
503 }
504
505 pub const fn n_derived(&self) -> usize {
506 self.n_derived as usize
507 }
508
509 pub const fn n_precommit(&self) -> usize {
510 self.n_precommit as usize
511 }
512
513 pub const fn n_private(&self) -> usize {
514 self.n_private as usize
515 }
516
517 pub const fn log_public(&self) -> u32 {
518 self.log_public
519 }
520
521 pub const fn log_precommit(&self) -> u32 {
522 self.log_precommit
523 }
524
525 pub const fn log_private(&self) -> u32 {
526 self.log_private
527 }
528
529 pub fn get(&self, wire: &ConstraintWire) -> Option<WitnessIndex> {
530 match wire.kind {
531 WireKind::Constant => {
532 assert!((wire.id as usize) < self.constants.len());
533 Some(WitnessIndex::public(wire.id))
534 }
535 WireKind::InOut => {
536 assert!(wire.id < self.n_inout);
537 Some(WitnessIndex::public(self.constants.len() as u32 + wire.id))
538 }
539 WireKind::Derived => self.derived_index_map.get(&wire.id).map(|&derived_idx| {
540 WitnessIndex::public(self.constants.len() as u32 + self.n_inout + derived_idx)
541 }),
542 WireKind::Precommit => {
543 assert!(wire.id < self.n_precommit);
544 Some(WitnessIndex::precommit(wire.id))
545 }
546 WireKind::Private => self
547 .private_index_map
548 .get(&wire.id)
549 .map(|&id| WitnessIndex::private(id)),
550 }
551 }
552}
553
554#[cfg(test)]
555mod tests {
556 use smallvec::smallvec;
557
558 use super::*;
559
560 #[test]
561 fn test_wires_added_mod2() {
562 let w = [
564 ConstraintWire {
565 kind: WireKind::Constant,
566 id: 0,
567 },
568 ConstraintWire {
569 kind: WireKind::InOut,
570 id: 0,
571 },
572 ConstraintWire {
573 kind: WireKind::Private,
574 id: 0,
575 },
576 ConstraintWire {
577 kind: WireKind::Private,
578 id: 1,
579 },
580 ];
581
582 let input = smallvec![w[0], w[2], w[2], w[3], w[3], w[1], w[2], w[1], w[3], w[3]];
586 let operand = Operand::new(input);
587
588 assert_eq!(operand.wires(), &[w[0], w[2]]);
590 }
591
592 #[test]
593 fn test_sorting_when_no_duplicates() {
594 let w = [
596 ConstraintWire {
597 kind: WireKind::Constant,
598 id: 0,
599 },
600 ConstraintWire {
601 kind: WireKind::InOut,
602 id: 0,
603 },
604 ConstraintWire {
605 kind: WireKind::Private,
606 id: 0,
607 },
608 ConstraintWire {
609 kind: WireKind::Private,
610 id: 1,
611 },
612 ];
613
614 let input = smallvec![w[2], w[3], w[0], w[1]];
616 let operand = Operand::new(input);
617
618 assert_eq!(operand.wires(), &[w[0], w[1], w[2], w[3]]);
620 }
621
622 #[test]
623 fn test_merge() {
624 let w = [
626 ConstraintWire {
627 kind: WireKind::Constant,
628 id: 0,
629 },
630 ConstraintWire {
631 kind: WireKind::InOut,
632 id: 0,
633 },
634 ConstraintWire {
635 kind: WireKind::Private,
636 id: 0,
637 },
638 ConstraintWire {
639 kind: WireKind::Private,
640 id: 1,
641 },
642 ];
643
644 let mut lhs = Operand(smallvec![w[0]]);
646 let rhs = Operand(smallvec![]);
647 let (additions, removals) = lhs.merge(&rhs);
648 assert_eq!(lhs.wires(), &[w[0]]);
649 assert_eq!(additions.wires(), &[]);
650 assert_eq!(removals.wires(), &[]);
651
652 let mut lhs = Operand(smallvec![]);
654 let rhs = Operand(smallvec![w[0]]);
655 let (additions, removals) = lhs.merge(&rhs);
656 assert_eq!(lhs.wires(), &[w[0]]);
657 assert_eq!(additions.wires(), &[w[0]]);
658 assert_eq!(removals.wires(), &[]);
659
660 let mut lhs = Operand(smallvec![w[0]]);
662 let rhs = Operand(smallvec![w[0]]);
663 let (additions, removals) = lhs.merge(&rhs);
664 assert_eq!(lhs.wires(), &[]);
665 assert_eq!(additions.wires(), &[]);
666 assert_eq!(removals.wires(), &[w[0]]);
667
668 let mut lhs = Operand(smallvec![w[0]]);
670 let rhs = Operand(smallvec![w[1]]);
671 let (additions, removals) = lhs.merge(&rhs);
672 assert_eq!(lhs.wires(), &[w[0], w[1]]);
673 assert_eq!(additions.wires(), &[w[1]]);
674 assert_eq!(removals.wires(), &[]);
675
676 let mut lhs = Operand(smallvec![w[0]]);
678 let rhs = Operand(smallvec![w[0], w[1]]);
679 let (additions, removals) = lhs.merge(&rhs);
680 assert_eq!(lhs.wires(), &[w[1]]);
681 assert_eq!(additions.wires(), &[w[1]]);
682 assert_eq!(removals.wires(), &[w[0]]);
683
684 let mut lhs = Operand(smallvec![w[0], w[2]]);
686 let rhs = Operand(smallvec![w[1], w[3]]);
687 let (additions, removals) = lhs.merge(&rhs);
688 assert_eq!(lhs.wires(), &[w[0], w[1], w[2], w[3]]);
689 assert_eq!(additions.wires(), &[w[1], w[3]]);
690 assert_eq!(removals.wires(), &[]);
691
692 let mut lhs = Operand(smallvec![w[0], w[2]]);
694 let rhs = Operand(smallvec![w[0], w[1], w[2], w[3]]);
695 let (additions, removals) = lhs.merge(&rhs);
696 assert_eq!(lhs.wires(), &[w[1], w[3]]);
697 assert_eq!(additions.wires(), &[w[1], w[3]]);
698 assert_eq!(removals.wires(), &[w[0], w[2]]);
699 }
700}