openvm_algebra_guest/
lib.rs

Help
1#![no_std]
2extern crate self as openvm_algebra_guest;
3
4/// This is custom-1 defined in RISC-V spec document
5pub const OPCODE: u8 = 0x2b;
6pub const MODULAR_ARITHMETIC_FUNCT3: u8 = 0b000;
7pub const COMPLEX_EXT_FIELD_FUNCT3: u8 = 0b010;
8
9/// Modular arithmetic is configurable.
10/// The funct7 field equals `mod_idx * MODULAR_ARITHMETIC_MAX_KINDS + base_funct7`.
11#[derive(Debug, Copy, Clone, PartialEq, Eq, FromRepr)]
12#[repr(u8)]
13pub enum ModArithBaseFunct7 {
14    AddMod = 0,
15    SubMod,
16    MulMod,
17    DivMod,
18    IsEqMod,
19    SetupMod,
20}
21
22impl ModArithBaseFunct7 {
23    pub const MODULAR_ARITHMETIC_MAX_KINDS: u8 = 8;
24}
25
26/// Complex extension field is configurable.
27/// The funct7 field equals `fp2_idx * COMPLEX_EXT_FIELD_MAX_KINDS + base_funct7`.
28#[derive(Debug, Copy, Clone, PartialEq, Eq, FromRepr)]
29#[repr(u8)]
30pub enum ComplexExtFieldBaseFunct7 {
31    Add = 0,
32    Sub,
33    Mul,
34    Div,
35    Setup,
36}
37
38impl ComplexExtFieldBaseFunct7 {
39    pub const COMPLEX_EXT_FIELD_MAX_KINDS: u8 = 8;
40}
41
42/// Modular arithmetic traits for use with OpenVM intrinsics.
43extern crate alloc;
44
45use alloc::vec::Vec;
46use core::{
47    fmt::Debug,
48    iter::{Product, Sum},
49    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
50};
51
52pub use field::Field;
53#[cfg(not(target_os = "zkvm"))]
54use num_bigint::BigUint;
55pub use openvm_algebra_complex_macros as complex_macros;
56pub use openvm_algebra_moduli_macros as moduli_macros;
57pub use serde_big_array::BigArray;
58use strum_macros::FromRepr;
59
60/// Field traits
61pub mod field;
62/// Implementation of this library's traits on halo2curves types.
63/// Used for testing and also VM runtime execution.
64/// These should **only** be importable on a host machine.
65#[cfg(all(not(target_os = "zkvm"), feature = "halo2curves"))]
66mod halo2curves;
67
68/// Exponentiation by bytes
69mod exp_bytes;
70pub use exp_bytes::*;
71
72/// Division operation that is undefined behavior when the denominator is not invertible.
73pub trait DivUnsafe<Rhs = Self>: Sized {
74    /// Output type of `div_unsafe`.
75    type Output;
76
77    /// Undefined behavior when denominator is not invertible.
78    fn div_unsafe(self, other: Rhs) -> Self::Output;
79}
80
81/// Division assignment operation that is undefined behavior when the denominator is not invertible.
82pub trait DivAssignUnsafe<Rhs = Self>: Sized {
83    /// Undefined behavior when denominator is not invertible.
84    fn div_assign_unsafe(&mut self, other: Rhs);
85}
86
87/// Trait definition for OpenVM modular integers, where each operation
88/// is done modulo MODULUS.
89///
90/// Division is only defined over the group of units in the ring of integers modulo MODULUS.
91/// It is undefined behavior outside of this group.
92pub trait IntMod:
93    Sized
94    + Eq
95    + Clone
96    + Debug
97    + Neg<Output = Self>
98    + Add<Output = Self>
99    + Sub<Output = Self>
100    + Mul<Output = Self>
101    + DivUnsafe<Output = Self>
102    + Sum
103    + Product
104    + for<'a> Add<&'a Self, Output = Self>
105    + for<'a> Sub<&'a Self, Output = Self>
106    + for<'a> Mul<&'a Self, Output = Self>
107    + for<'a> DivUnsafe<&'a Self, Output = Self>
108    + for<'a> Sum<&'a Self>
109    + for<'a> Product<&'a Self>
110    + AddAssign
111    + SubAssign
112    + MulAssign
113    + DivAssignUnsafe
114    + for<'a> AddAssign<&'a Self>
115    + for<'a> SubAssign<&'a Self>
116    + for<'a> MulAssign<&'a Self>
117    + for<'a> DivAssignUnsafe<&'a Self>
118{
119    /// Underlying representation of IntMod. Usually of the form `[u8; NUM_LIMBS]`.
120    type Repr: AsRef<[u8]> + AsMut<[u8]>;
121    /// `SelfRef<'a>` should almost always be `&'a Self`. This is a way to include implementations of binary operations where both sides are `&'a Self`.
122    type SelfRef<'a>: Add<&'a Self, Output = Self>
123        + Sub<&'a Self, Output = Self>
124        + Neg<Output = Self>
125        + Mul<&'a Self, Output = Self>
126        + DivUnsafe<&'a Self, Output = Self>
127    where
128        Self: 'a;
129
130    /// Modulus as a Repr.
131    const MODULUS: Self::Repr;
132
133    /// Number of limbs used to internally represent an element of `Self`.
134    const NUM_LIMBS: usize;
135
136    /// The zero element (i.e. the additive identity).
137    const ZERO: Self;
138
139    /// The one element (i.e. the multiplicative identity).
140    const ONE: Self;
141
142    /// Creates a new IntMod from an instance of Repr.
143    /// Does not enforce the integer value of `bytes` must be less than the modulus.
144    fn from_repr(repr: Self::Repr) -> Self;
145
146    /// Creates a new IntMod from an array of bytes, little endian.
147    /// Does not enforce the integer value of `bytes` must be less than the modulus.
148    fn from_le_bytes(bytes: &[u8]) -> Self;
149
150    /// Creates a new IntMod from an array of bytes, big endian.
151    /// Does not enforce the integer value of `bytes` must be less than the modulus.
152    fn from_be_bytes(bytes: &[u8]) -> Self;
153
154    /// Creates a new IntMod from a u8.
155    /// Does not enforce the integer value of `bytes` must be less than the modulus.
156    fn from_u8(val: u8) -> Self;
157
158    /// Creates a new IntMod from a u32.
159    /// Does not enforce the integer value of `bytes` must be less than the modulus.
160    fn from_u32(val: u32) -> Self;
161
162    /// Creates a new IntMod from a u64.
163    /// Does not enforce the integer value of `bytes` must be less than the modulus.
164    fn from_u64(val: u64) -> Self;
165
166    /// Value of this IntMod as an array of bytes, little endian.
167    fn as_le_bytes(&self) -> &[u8];
168
169    /// Value of this IntMod as an array of bytes, big endian.
170    fn to_be_bytes(&self) -> Self::Repr;
171
172    /// Modulus N as a BigUint.
173    #[cfg(not(target_os = "zkvm"))]
174    fn modulus_biguint() -> BigUint;
175
176    /// Creates a new IntMod from a BigUint.
177    #[cfg(not(target_os = "zkvm"))]
178    fn from_biguint(biguint: BigUint) -> Self;
179
180    /// Value of this IntMod as a BigUint.
181    #[cfg(not(target_os = "zkvm"))]
182    fn as_biguint(&self) -> BigUint;
183
184    fn neg_assign(&mut self);
185
186    /// Doubles `self` in-place.
187    fn double_assign(&mut self);
188
189    /// Doubles this IntMod.
190    fn double(&self) -> Self {
191        let mut ret = self.clone();
192        ret += self;
193        ret
194    }
195
196    /// Squares `self` in-place.
197    fn square_assign(&mut self);
198
199    /// Squares this IntMod.
200    fn square(&self) -> Self {
201        let mut ret = self.clone();
202        ret *= self;
203        ret
204    }
205
206    /// Cubes this IntMod.
207    fn cube(&self) -> Self {
208        let mut ret = self.square();
209        ret *= self;
210        ret
211    }
212
213    /// VM specific concept: during guest execution, it is not enforced that the representation
214    /// of `Self` must be the unique integer less than the modulus. The guest code may sometimes
215    /// want to enforce that the representation is the canonical one less than the modulus.
216    /// the host to an honest host to provide the canonical representation less than the modulus.
217    ///
218    /// This function should enforce that guest execution proceeds **if and only if** `self`
219    /// is in the unique representation less than the modulus.
220    fn assert_reduced(&self);
221
222    /// Is the integer representation of `self` less than the modulus?
223    fn is_reduced(&self) -> bool;
224}
225
226// Ref: https://docs.rs/elliptic-curve/latest/elliptic_curve/ops/trait.Reduce.html
227pub trait Reduce: Sized {
228    /// Interpret the given bytes as an integer and perform a modular reduction.
229    fn reduce_le_bytes(bytes: &[u8]) -> Self;
230    fn reduce_be_bytes(bytes: &[u8]) -> Self {
231        Self::reduce_le_bytes(&bytes.iter().rev().copied().collect::<Vec<_>>())
232    }
233}
openvm_algebra_guest/lib.rs

openvm_algebra_guest/
lib.rs
