midnight_circuits/parsing/scanner/
substring_varlen.rs

1// This file is part of MIDNIGHT-ZK.
2// Copyright (C) 2025 Midnight Foundation
3// SPDX-License-Identifier: Apache-2.0
4// Licensed under the Apache License, Version 2.0 (the "License");
5// You may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7// http://www.apache.org/licenses/LICENSE-2.0
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14//! Variable-length substring checks.
15
16use midnight_proofs::{circuit::Layouter, plonk::Error};
17use num_bigint::BigUint;
18
19use super::{varlen::ScannerVec, ScannerChip, PARSING_MAX_LEN_BITS};
20use crate::{
21    field::AssignedNative,
22    instructions::{AssertionInstructions, AssignmentInstructions, RangeCheckInstructions},
23    types::AssignedByte,
24    vec::get_lims,
25    CircuitField,
26};
27
28impl<F> ScannerChip<F>
29where
30    F: CircuitField + Ord,
31{
32    /// Similar to [`check_bytes`](`ScannerChip::check_bytes`), but supports
33    /// variable-length inputs. If `sub` has known fixed length, use
34    /// [`check_bytes_varlen_partial`](`ScannerChip::check_bytes_varlen_partial`)
35    /// instead.
36    pub fn check_bytes_varlen<
37        const M_SEQ: usize,
38        const A_SEQ: usize,
39        const M_SUB: usize,
40        const A_SUB: usize,
41    >(
42        &self,
43        layouter: &mut impl Layouter<F>,
44        sequence: &ScannerVec<F, M_SEQ, A_SEQ>,
45        idx: &AssignedNative<F>,
46        sub: &ScannerVec<F, M_SUB, A_SUB>,
47    ) -> Result<(), Error> {
48        let ng = &self.native_gadget;
49
50        // Range-check idx to ensure packing injectivity.
51        ng.assert_lower_than_fixed(layouter, idx, &(BigUint::from(1u8) << PARSING_MAX_LEN_BITS))?;
52
53        // Index offsets: +seq_start and -sub_start, folded into packing LCs.
54        let idx_offsets = vec![
55            (F::ONE, sequence.limits.0.clone()),
56            (-F::ONE, sub.limits.0.clone()),
57        ];
58
59        let seq_native = sequence.buffer.to_vec();
60        let sub_native = sub.buffer.to_vec();
61        let flags = sub.padding_flags.to_vec();
62        let sub_entry = (idx.clone(), idx_offsets, sub_native, Some(flags));
63
64        self.sequence_cache
65            .borrow_mut()
66            .entry(seq_native)
67            .and_modify(|(calls, len)| {
68                *len += M_SUB;
69                calls.push(sub_entry.clone())
70            })
71            .or_insert_with(|| (vec![sub_entry], M_SUB));
72
73        Ok(())
74    }
75
76    /// Similar to [`check_bytes`](`ScannerChip::check_bytes`), but the sequence
77    /// is variable-length while `sub` is fixed-length. More efficient than
78    /// [`check_bytes_varlen`](`ScannerChip::check_bytes_varlen`).
79    pub fn check_bytes_varlen_partial<const M: usize, const A: usize>(
80        &self,
81        layouter: &mut impl Layouter<F>,
82        sequence: &ScannerVec<F, M, A>,
83        idx: &AssignedNative<F>,
84        sub: &[AssignedByte<F>],
85    ) -> Result<(), Error> {
86        if sub.is_empty() {
87            return Ok(());
88        }
89        let ng = &self.native_gadget;
90
91        // Range-check idx to ensure packing injectivity.
92        ng.assert_lower_than_fixed(layouter, idx, &(BigUint::from(1u8) << PARSING_MAX_LEN_BITS))?;
93
94        // Index offset: +seq_start, folded into packing LCs.
95        let idx_offsets = vec![(F::ONE, sequence.limits.0.clone())];
96
97        let seq_native = sequence.buffer.to_vec();
98        let sub_native: Vec<AssignedNative<F>> = sub.iter().map(AssignedNative::from).collect();
99
100        self.sequence_cache
101            .borrow_mut()
102            .entry(seq_native)
103            .and_modify(|(calls, len)| {
104                *len += sub_native.len();
105                calls.push((idx.clone(), idx_offsets.clone(), sub_native.clone(), None))
106            })
107            .or_insert_with(|| {
108                let sub_entry = (idx.clone(), idx_offsets, sub_native, None);
109                (vec![sub_entry], sub.len())
110            });
111
112        Ok(())
113    }
114
115    /// Asserts that two byte slices of variable length are element-wise equal.
116    /// Proceeds by testing equality of the lengths, and checks that `v2` is a
117    /// substring of `v1` at index 0. If either of the two vectors is also used
118    /// as the `sequence` argument of another substring check, putting it as the
119    /// `v1` argument is the most cost efficient.
120    pub fn assert_equal_varlen<
121        const M1: usize,
122        const A1: usize,
123        const M2: usize,
124        const A2: usize,
125    >(
126        &self,
127        layouter: &mut impl Layouter<F>,
128        v1: &ScannerVec<F, M1, A1>,
129        v2: &ScannerVec<F, M2, A2>,
130    ) -> Result<(), Error> {
131        self.native_gadget.assert_equal(layouter, v1.len(), v2.len())?;
132        if M1 == M2 && A1 == A2 {
133            for (x, y) in v1.buffer.iter().zip(v2.buffer.iter()) {
134                self.native_gadget.assert_equal(layouter, x, y)?;
135            }
136            Ok(())
137        } else {
138            let zero: AssignedNative<F> = self.native_gadget.assign_fixed(layouter, F::ZERO)?;
139            self.check_bytes_varlen(layouter, v1, &zero, v2)
140        }
141    }
142
143    /// Asserts that two byte slices of variable and fixed length, respectively,
144    /// are element-wise equal. Proceeds by testing equality of the lengths,
145    /// and checks equality of the varlen buffer with a padded slice.
146    pub fn assert_equal_varlen_partial<const M: usize, const A: usize>(
147        &self,
148        layouter: &mut impl Layouter<F>,
149        v1: &ScannerVec<F, M, A>,
150        v2: &[AssignedByte<F>],
151    ) -> Result<(), Error> {
152        self.native_gadget
153            .assert_equal_to_fixed(layouter, v1.len(), F::from(v2.len() as u64))?;
154        let l1 = v1.buffer[get_lims::<M, A>(v2.len())].iter();
155        let l2 = v2.iter().map(AssignedNative::from);
156        for (x, y) in l1.zip(l2) {
157            self.native_gadget.assert_equal(layouter, x, &y)?;
158        }
159        Ok(())
160    }
161}
162
163#[cfg(test)]
164mod test {
165    use ff::FromUniformBytes;
166    use midnight_proofs::{
167        circuit::{Layouter, SimpleFloorPlanner, Value},
168        dev::MockProver,
169        plonk::{Circuit, ConstraintSystem, Error},
170    };
171
172    use super::super::ScannerChip;
173    use crate::{
174        instructions::AssignmentInstructions, testing_utils::FromScratch, types::AssignedByte,
175        utils::circuit_modeling::circuit_to_json, CircuitField,
176    };
177
178    // ---- check_bytes_varlen_partial tests ----
179
180    /// Circuit: ScannerVec sequence (M=16) + fixed sub + idx.
181    #[derive(Clone, Debug)]
182    struct VarlenPartialCircuit<F: CircuitField> {
183        full: Value<Vec<u8>>,
184        sub: Vec<Value<u8>>,
185        idx: Value<F>,
186    }
187
188    impl<F: CircuitField> VarlenPartialCircuit<F> {
189        fn new(full: &[u8], sub: &[u8], idx: usize) -> Self {
190            Self {
191                full: Value::known(full.to_vec()),
192                sub: sub.iter().map(|&b| Value::known(b)).collect(),
193                idx: Value::known(F::from(idx as u64)),
194            }
195        }
196    }
197
198    impl<F> Circuit<F> for VarlenPartialCircuit<F>
199    where
200        F: CircuitField + FromUniformBytes<64> + Ord,
201    {
202        type Config = <ScannerChip<F> as FromScratch<F>>::Config;
203        type FloorPlanner = SimpleFloorPlanner;
204        type Params = ();
205
206        fn without_witnesses(&self) -> Self {
207            unreachable!()
208        }
209
210        fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
211            let instance_columns = [meta.instance_column(), meta.instance_column()];
212            ScannerChip::<F>::configure_from_scratch(
213                meta,
214                &mut vec![],
215                &mut vec![],
216                &instance_columns,
217            )
218        }
219
220        fn synthesize(
221            &self,
222            config: Self::Config,
223            mut layouter: impl Layouter<F>,
224        ) -> Result<(), Error> {
225            let scanner = ScannerChip::<F>::new_from_scratch(&config);
226            let ng = &scanner.native_gadget;
227
228            let sequence = scanner.assign_scanner_vec::<16, 1>(&mut layouter, self.full.clone())?;
229            let sub: Vec<AssignedByte<F>> = ng.assign_many(&mut layouter, &self.sub)?;
230            let idx = ng.assign(&mut layouter, self.idx)?;
231
232            scanner.check_bytes_varlen_partial(&mut layouter, &sequence, &idx, &sub)?;
233            scanner.load_from_scratch(&mut layouter)
234        }
235    }
236
237    fn varlen_partial_test(full: &[u8], sub: &[u8], idx: usize, must_pass: bool) {
238        type F = midnight_curves::Fq;
239        let circuit = VarlenPartialCircuit::<F>::new(full, sub, idx);
240        println!(
241            ">> [varlen_partial] [must{} pass] idx={idx}, sub len={}, full len={}",
242            if must_pass { "" } else { " not" },
243            sub.len(),
244            full.len(),
245        );
246        let result = MockProver::run(&circuit, vec![vec![], vec![]]);
247        match result {
248            Ok(p) => {
249                let verified = p.verify();
250                if must_pass {
251                    verified.expect("should have passed")
252                } else {
253                    assert!(verified.is_err(), "should have failed");
254                }
255            }
256            Err(e) => assert!(!must_pass, "Prover failed unexpectedly: {:?}", e),
257        }
258        println!("... ok!");
259    }
260
261    #[test]
262    fn test_check_bytes_varlen_partial() {
263        // Correct matches.
264        varlen_partial_test(b"hello world", b"hello", 0, true);
265        varlen_partial_test(b"hello world", b"world", 6, true);
266        varlen_partial_test(b"hello world", b"lo wo", 3, true);
267        varlen_partial_test(b"hello world", b"hello world", 0, true);
268        varlen_partial_test(b"abcdef", b"d", 3, true);
269
270        // Empty sub.
271        varlen_partial_test(b"hello", b"", 0, true);
272
273        // Wrong content.
274        varlen_partial_test(b"hello world", b"xyz", 0, false);
275        // Wrong index.
276        varlen_partial_test(b"hello world", b"world", 0, false);
277
278        // Performance test for the golden files (M=16, sub=5).
279        {
280            type F = midnight_curves::Fq;
281            let circuit = VarlenPartialCircuit::<F>::new(b"hello world", b"world", 6);
282            circuit_to_json::<F>(
283                "Scanner",
284                "varlen partial substring perf (M = 16, sub length = 5)",
285                circuit,
286            );
287        }
288    }
289
290    // ---- check_bytes_varlen tests ----
291
292    /// Circuit: two ScannerVecs (M_SEQ=16, M_SUB=8) + idx.
293    #[derive(Clone, Debug)]
294    struct VarlenFullCircuit<F: CircuitField> {
295        full: Value<Vec<u8>>,
296        sub: Value<Vec<u8>>,
297        idx: Value<F>,
298    }
299
300    impl<F: CircuitField> VarlenFullCircuit<F> {
301        fn new(full: &[u8], sub: &[u8], idx: usize) -> Self {
302            Self {
303                full: Value::known(full.to_vec()),
304                sub: Value::known(sub.to_vec()),
305                idx: Value::known(F::from(idx as u64)),
306            }
307        }
308    }
309
310    impl<F> Circuit<F> for VarlenFullCircuit<F>
311    where
312        F: CircuitField + FromUniformBytes<64> + Ord,
313    {
314        type Config = <ScannerChip<F> as FromScratch<F>>::Config;
315        type FloorPlanner = SimpleFloorPlanner;
316        type Params = ();
317
318        fn without_witnesses(&self) -> Self {
319            unreachable!()
320        }
321
322        fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
323            let instance_columns = [meta.instance_column(), meta.instance_column()];
324            ScannerChip::<F>::configure_from_scratch(
325                meta,
326                &mut vec![],
327                &mut vec![],
328                &instance_columns,
329            )
330        }
331
332        fn synthesize(
333            &self,
334            config: Self::Config,
335            mut layouter: impl Layouter<F>,
336        ) -> Result<(), Error> {
337            let scanner = ScannerChip::<F>::new_from_scratch(&config);
338            let ng = &scanner.native_gadget;
339
340            let sequence = scanner.assign_scanner_vec::<16, 1>(&mut layouter, self.full.clone())?;
341            let sub = scanner.assign_scanner_vec::<8, 1>(&mut layouter, self.sub.clone())?;
342            let idx = ng.assign(&mut layouter, self.idx)?;
343
344            scanner.check_bytes_varlen(&mut layouter, &sequence, &idx, &sub)?;
345            scanner.load_from_scratch(&mut layouter)
346        }
347    }
348
349    fn varlen_full_test(full: &[u8], sub: &[u8], idx: usize, must_pass: bool) {
350        type F = midnight_curves::Fq;
351        let circuit = VarlenFullCircuit::<F>::new(full, sub, idx);
352        println!(
353            ">> [varlen_full] [must{} pass] idx={idx}, sub len={}, full len={}",
354            if must_pass { "" } else { " not" },
355            sub.len(),
356            full.len(),
357        );
358        let result = MockProver::run(&circuit, vec![vec![], vec![]]);
359        match result {
360            Ok(p) => {
361                let verified = p.verify();
362                if must_pass {
363                    verified.expect("should have passed")
364                } else {
365                    assert!(verified.is_err(), "should have failed");
366                }
367            }
368            Err(e) => assert!(!must_pass, "Prover failed unexpectedly: {:?}", e),
369        }
370        println!("... ok!");
371    }
372
373    #[test]
374    fn test_check_bytes_varlen() {
375        // Correct matches.
376        varlen_full_test(b"hello world", b"hello", 0, true);
377        varlen_full_test(b"hello world", b"world", 6, true);
378        varlen_full_test(b"hello world", b"lo wo", 3, true);
379        varlen_full_test(b"abcdef", b"d", 3, true);
380
381        // Wrong content.
382        varlen_full_test(b"hello world", b"xyz", 0, false);
383        // Wrong index.
384        varlen_full_test(b"hello world", b"world", 0, false);
385
386        // Performance test for the golden files (M_SEQ=16, M_SUB=8, sub=5).
387        {
388            type F = midnight_curves::Fq;
389            let circuit = VarlenFullCircuit::<F>::new(b"hello world", b"world", 6);
390            circuit_to_json::<F>(
391                "Scanner",
392                "varlen full substring perf (M_SEQ = 16, M_SUB = 8, sub length = 5)",
393                circuit,
394            );
395        }
396    }
397}
midnight_circuits/parsing/scanner/substring_varlen.rs

midnight_circuits/parsing/scanner/
substring_varlen.rs
