openvm_continuations/verifier/
utils.rs

1use std::array;
2
3use openvm_native_compiler::prelude::*;
4use openvm_native_recursion::{config::outer::OuterConfig, hints::Hintable, types::InnerConfig};
5use openvm_stark_backend::p3_field::PrimeField32;
6use openvm_stark_sdk::{
7    openvm_stark_backend::p3_field::PrimeCharacteristicRing, p3_baby_bear::BabyBear,
8};
9use p3_bn254::Bn254;
10
11pub fn compress_babybear_var_to_bn254(
12    builder: &mut Builder<OuterConfig>,
13    var: [Var<Bn254>; DIGEST_SIZE],
14) -> Var<Bn254> {
15    let mut ret = SymbolicVar::ZERO;
16    let order = Bn254::from_u32(BabyBear::ORDER_U32);
17    let mut base = Bn254::ONE;
18    var.iter().for_each(|&x| {
19        ret += x * base;
20        base *= order;
21    });
22    builder.eval(ret)
23}
24
25pub(crate) fn assign_array_to_slice<C: Config>(
26    builder: &mut Builder<C>,
27    dst_slice: &[Felt<C::F>],
28    src: &Array<C, Felt<C::F>>,
29    src_offset: usize,
30) {
31    for (i, dst) in dst_slice.iter().enumerate() {
32        let pv = builder.get(src, i + src_offset);
33        builder.assign(dst, pv);
34    }
35}
36
37pub(crate) fn assign_slice_to_array<C: Config>(
38    builder: &mut Builder<C>,
39    dst: &Array<C, Felt<C::F>>,
40    src_slice: &[Felt<C::F>],
41) {
42    for (i, &src) in src_slice.iter().enumerate() {
43        builder.set_value(dst, i, src);
44    }
45}
46
47pub(crate) fn write_field_slice(arr: &[BabyBear; DIGEST_SIZE]) -> Vec<Vec<BabyBear>> {
48    arr.iter()
49        .flat_map(Hintable::<InnerConfig>::write)
50        .collect()
51}
52
53/// Returns 1 if lhs == rhs, 0 otherwise.
54pub(crate) fn eq_felt_slice<C: Config, const N: usize>(
55    builder: &mut Builder<C>,
56    lhs: &[Felt<C::F>; N],
57    rhs: &[Felt<C::F>; N],
58) -> Var<C::N> {
59    let sub_res: [Felt<C::F>; N] = array::from_fn(|i| builder.eval(lhs[i] - rhs[i]));
60    let var_res = sub_res.map(|f| builder.cast_felt_to_var(f));
61    let ret: Var<C::N> = builder.eval(C::N::ONE);
62    var_res.into_iter().for_each(|v| {
63        builder
64            .if_ne(v, C::N::ZERO)
65            .then(|builder| builder.assign(&ret, C::N::ZERO))
66    });
67    ret
68}
69
70#[derive(Clone)]
71pub(crate) struct VariableP2Compressor<C: Config> {
72    state: Array<C, Felt<C::F>>,
73    lhs: Array<C, Felt<C::F>>,
74    rhs: Array<C, Felt<C::F>>,
75}
76
77impl<C: Config> VariableP2Compressor<C> {
78    pub fn new(builder: &mut Builder<C>) -> Self {
79        Self {
80            state: builder.array(PERMUTATION_WIDTH),
81            lhs: builder.array(DIGEST_SIZE),
82            rhs: builder.array(DIGEST_SIZE),
83        }
84    }
85
86    pub fn compress(
87        &self,
88        builder: &mut Builder<C>,
89        lhs: &[Felt<C::F>; DIGEST_SIZE],
90        rhs: &[Felt<C::F>; DIGEST_SIZE],
91    ) -> [Felt<C::F>; DIGEST_SIZE] {
92        assign_slice_to_array(builder, &self.lhs, lhs);
93        assign_slice_to_array(builder, &self.rhs, rhs);
94        builder.poseidon2_compress_x(&self.state, &self.lhs, &self.rhs);
95        array::from_fn(|i| builder.get(&self.state, i))
96    }
97
98    pub fn compress_array(
99        &self,
100        builder: &mut Builder<C>,
101        lhs: &Array<C, Felt<C::F>>,
102        rhs: &Array<C, Felt<C::F>>,
103    ) -> Array<C, Felt<C::F>> {
104        let ret = builder.array(DIGEST_SIZE);
105        builder.poseidon2_compress_x(&self.state, lhs, rhs);
106        for i in 0..DIGEST_SIZE {
107            let v = builder.get(&self.state, i);
108            builder.set_value(&ret, i, v);
109        }
110        ret
111    }
112}
113
114#[derive(Clone)]
115pub(crate) struct VariableP2Hasher<C: Config> {
116    pub compressor: VariableP2Compressor<C>,
117    pub const_zeros: Array<C, Felt<C::F>>,
118    pub const_zero: Felt<C::F>,
119}
120
121impl<C: Config> VariableP2Hasher<C> {
122    pub fn new(builder: &mut Builder<C>) -> Self {
123        let const_zero: Felt<C::F> = builder.eval(C::F::ZERO);
124        let const_zeros = builder.array(DIGEST_SIZE);
125        for i in 0..DIGEST_SIZE {
126            builder.set_value(&const_zeros, i, const_zero);
127        }
128        Self {
129            compressor: VariableP2Compressor::new(builder),
130            const_zeros,
131            const_zero,
132        }
133    }
134    pub fn hash(
135        &self,
136        builder: &mut Builder<C>,
137        payload: &[Felt<C::F>; DIGEST_SIZE],
138    ) -> [Felt<C::F>; DIGEST_SIZE] {
139        self.compressor
140            .compress(builder, payload, &[self.const_zero; DIGEST_SIZE])
141    }
142    pub fn hash_array(
143        &self,
144        builder: &mut Builder<C>,
145        payload: &Array<C, Felt<C::F>>,
146    ) -> Array<C, Felt<C::F>> {
147        self.compressor
148            .compress_array(builder, payload, &self.const_zeros)
149    }
150
151    pub fn merkle_root(
152        &self,
153        builder: &mut Builder<C>,
154        values: &[Felt<C::F>],
155    ) -> [Felt<C::F>; DIGEST_SIZE] {
156        assert_eq!(values.len() % DIGEST_SIZE, 0);
157        assert!((values.len() / DIGEST_SIZE).is_power_of_two());
158        let buffer = builder.array(DIGEST_SIZE);
159        let mut leaves: Vec<_> = values
160            .chunks_exact(DIGEST_SIZE)
161            .map(|chunk| {
162                assign_slice_to_array(builder, &buffer, chunk);
163                self.hash_array(builder, &buffer)
164            })
165            .collect();
166        while leaves.len() > 1 {
167            leaves = leaves
168                .chunks_exact(2)
169                .map(|chunk| {
170                    self.compressor
171                        .compress_array(builder, &chunk[0], &chunk[1])
172                })
173                .collect();
174        }
175        array::from_fn(|i| builder.get(&leaves[0], i))
176    }
177}
openvm_continuations/verifier/utils.rs

openvm_continuations/verifier/
utils.rs
