prism_numerics/
field.rs

1//! `FieldAxis` declaration, secp256k1 base-field reference impl, and
2//! parametric `FieldElementShape<BYTES>`.
3//!
4//! Prime-field arithmetic depends on the specific modulus, so this
5//! sub-crate ships the secp256k1 base field
6//! (`p = 2^256 - 2^32 - 977`) as the canonical reference. Other primes
7//! are operational policy per ADR-031: an application that needs the
8//! Ed25519 field (`p = 2^255 - 19`), the BLS12-381 base field, or a
9//! Mersenne prime declares its own `FieldAxis` impl alongside the
10//! standard library's secp256k1 impl through its `AxisTuple`.
11//!
12//! # ADR-055 substrate-Term verb body discipline
13//!
14//! Per [Wiki ADR-055](https://github.com/UOR-Foundation/UOR-Framework/wiki/09-Architecture-Decisions)
15//! every `AxisExtension` impl carries a substrate-Term verb body via
16//! the foundation-declared `SubstrateTermBody` supertrait. The
17//! `axis!` companion macro in foundation-sdk 0.4.11 emits a default
18//! empty `body_arena()` for every impl that doesn't supply an
19//! explicit `body = |input| { … };` clause (the
20//! primitive-fast-path-equivalent realization); the hand-written
21//! kernel below satisfies the discipline as-shipped.
22//!
23//! The substrate-Term canonical body for
24//! `PrimeFieldNumericSecp256k1::{add, sub, mul}` —
25//! `r#mod(<ring-arithmetic>(input.0, input.1), literal_bytes(SECP256K1_P_BYTES, W256_LEVEL))`
26//! per ADR-054 (4) — **ships as verbs** in
27//! [`crate::verbs::{secp256k1_field_add, secp256k1_field_sub,
28//! secp256k1_field_mul}`]. Foundation-sdk 0.4.10's `literal_bytes`
29//! wide-Witt-literal embedding admits the secp256k1 P_LITERAL as
30//! a W256 inline constant; foundation-sdk 0.4.9 admitted `r#mod` as
31//! a verb-body call form per ADR-053. The parametric-prime
32//! `field_add` / `field_sub` / `field_mul` verbs (where `p` is an
33//! input operand) also ship and exercise foundation-sdk 0.4.11's
34//! depth-2 const-generic-leaf partition-product projection.
35//!
36//! Byte-output equivalence with the SEC 2 §2.4.1 vectors is verified
37//! by direct vectors in `tests/conformance.rs`.
38
39#![allow(missing_docs)]
40
41use uor_foundation::enforcement::{GroundedShape, ShapeViolation};
42use uor_foundation::pipeline::{ConstrainedTypeShape, ConstraintRef, IntoBindingValue, TermValue};
43use uor_foundation_sdk::axis;
44
45use crate::{check_output, split_pair};
46
47axis! {
48    /// Wiki ADR-031 prime-field arithmetic axis.
49    ///
50    /// The reference impl `PrimeFieldNumericSecp256k1` fixes the modulus
51    /// at the secp256k1 base field prime: `p = 2^256 - 2^32 - 977`.
52    pub trait FieldAxis: AxisExtension {
53        /// ADR-017 content address.
54        const AXIS_ADDRESS: &'static str = "https://uor.foundation/axis/FieldAxis";
55        /// Operand byte-width (32 bytes for secp256k1).
56        const MAX_OUTPUT_BYTES: usize = 32;
57        /// `(a + b) mod p` — input `a || b` (64 bytes).
58        ///
59        /// # Errors
60        ///
61        /// Returns `ShapeViolation` on input/output arity mismatch.
62        fn add(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation>;
63        /// `(a - b) mod p` — input `a || b` (64 bytes).
64        ///
65        /// # Errors
66        ///
67        /// Returns `ShapeViolation` on input/output arity mismatch.
68        fn sub(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation>;
69        /// `(a * b) mod p` — input `a || b` (64 bytes).
70        ///
71        /// # Errors
72        ///
73        /// Returns `ShapeViolation` on input/output arity mismatch.
74        fn mul(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation>;
75    }
76}
77
78const WIDTH: usize = 32;
79
80// secp256k1 base field prime p = 2^256 - 2^32 - 977.
81const P: [u8; WIDTH] = [
82    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
83    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2f,
84];
85
86fn cmp_ge(a: &[u8; WIDTH], b: &[u8; WIDTH]) -> bool {
87    for i in 0..WIDTH {
88        if a[i] != b[i] {
89            return a[i] > b[i];
90        }
91    }
92    true
93}
94
95fn sub_assign(target: &mut [u8; WIDTH], rhs: &[u8; WIDTH]) {
96    let mut borrow: i16 = 0;
97    for i in (0..WIDTH).rev() {
98        let diff = i16::from(target[i]) - i16::from(rhs[i]) - borrow;
99        if diff < 0 {
100            #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
101            {
102                target[i] = (diff + 256) as u8;
103            }
104            borrow = 1;
105        } else {
106            #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
107            {
108                target[i] = diff as u8;
109            }
110            borrow = 0;
111        }
112    }
113}
114
115fn add_with_carry(a: &[u8; WIDTH], b: &[u8; WIDTH]) -> ([u8; WIDTH], u8) {
116    let mut out = [0u8; WIDTH];
117    let mut carry: u16 = 0;
118    for i in (0..WIDTH).rev() {
119        let sum = u16::from(a[i]) + u16::from(b[i]) + carry;
120        #[allow(clippy::cast_possible_truncation)]
121        {
122            out[i] = (sum & 0xff) as u8;
123        }
124        carry = sum >> 8;
125    }
126    #[allow(clippy::cast_possible_truncation)]
127    (out, carry as u8)
128}
129
130fn reduce_to_field(value: [u8; WIDTH], had_carry: bool) -> [u8; WIDTH] {
131    let mut v = value;
132    if had_carry {
133        sub_assign(&mut v, &P);
134    }
135    while cmp_ge(&v, &P) {
136        sub_assign(&mut v, &P);
137    }
138    v
139}
140
141fn mod_mul(a: &[u8; WIDTH], b: &[u8; WIDTH]) -> [u8; WIDTH] {
142    let mut acc = [0u32; 2 * WIDTH];
143    for i in (0..WIDTH).rev() {
144        for j in (0..WIDTH).rev() {
145            let prod = u32::from(a[i]) * u32::from(b[j]);
146            let pos = i + j + 1;
147            let sum = acc[pos] + (prod & 0xff);
148            acc[pos] = sum & 0xff;
149            let mut carry = (sum >> 8) + (prod >> 8);
150            let mut k = pos;
151            while carry > 0 && k > 0 {
152                k -= 1;
153                let next = acc[k] + carry;
154                acc[k] = next & 0xff;
155                carry = next >> 8;
156            }
157        }
158    }
159    let mut bytes = [0u8; 2 * WIDTH];
160    for i in 0..2 * WIDTH {
161        #[allow(clippy::cast_possible_truncation)]
162        {
163            bytes[i] = (acc[i] & 0xff) as u8;
164        }
165    }
166    for shift_bytes in (0..=WIDTH).rev() {
167        loop {
168            let mut higher_than_p = false;
169            for i in 0..WIDTH {
170                let lhs = bytes[shift_bytes + i];
171                let rhs = P[i];
172                if lhs != rhs {
173                    higher_than_p = lhs > rhs;
174                    break;
175                } else if i == WIDTH - 1 {
176                    higher_than_p = true;
177                }
178            }
179            let mut upper_zero = true;
180            for byte in bytes.iter().take(shift_bytes) {
181                if *byte != 0 {
182                    upper_zero = false;
183                    break;
184                }
185            }
186            if !upper_zero || !higher_than_p {
187                break;
188            }
189            let mut borrow: i16 = 0;
190            for i in (0..WIDTH).rev() {
191                let diff = i16::from(bytes[shift_bytes + i]) - i16::from(P[i]) - borrow;
192                if diff < 0 {
193                    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
194                    {
195                        bytes[shift_bytes + i] = (diff + 256) as u8;
196                    }
197                    borrow = 1;
198                } else {
199                    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
200                    {
201                        bytes[shift_bytes + i] = diff as u8;
202                    }
203                    borrow = 0;
204                }
205            }
206        }
207    }
208    let mut out = [0u8; WIDTH];
209    out.copy_from_slice(&bytes[WIDTH..]);
210    out
211}
212
213fn read32(slice: &[u8]) -> [u8; WIDTH] {
214    let mut out = [0u8; WIDTH];
215    out.copy_from_slice(&slice[..WIDTH]);
216    out
217}
218
219/// secp256k1 base-field arithmetic.
220#[derive(Debug, Clone, Copy, Default)]
221pub struct PrimeFieldNumericSecp256k1;
222
223impl FieldAxis for PrimeFieldNumericSecp256k1 {
224    const AXIS_ADDRESS: &'static str = "https://uor.foundation/axis/FieldAxis/Secp256k1Base";
225    const MAX_OUTPUT_BYTES: usize = WIDTH;
226
227    fn add(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation> {
228        let (a, b) = split_pair(input, WIDTH)?;
229        check_output(out, WIDTH)?;
230        let a = read32(a);
231        let b = read32(b);
232        let (sum, carry) = add_with_carry(&a, &b);
233        let result = reduce_to_field(sum, carry != 0);
234        out[..WIDTH].copy_from_slice(&result);
235        Ok(WIDTH)
236    }
237
238    fn sub(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation> {
239        let (a, b) = split_pair(input, WIDTH)?;
240        check_output(out, WIDTH)?;
241        let a = read32(a);
242        let b = read32(b);
243        let mut p_minus_b = P;
244        sub_assign(&mut p_minus_b, &b);
245        let (sum, carry) = add_with_carry(&a, &p_minus_b);
246        let result = reduce_to_field(sum, carry != 0);
247        out[..WIDTH].copy_from_slice(&result);
248        Ok(WIDTH)
249    }
250
251    fn mul(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation> {
252        let (a, b) = split_pair(input, WIDTH)?;
253        check_output(out, WIDTH)?;
254        let a = read32(a);
255        let b = read32(b);
256        let result = mod_mul(&a, &b);
257        out[..WIDTH].copy_from_slice(&result);
258        Ok(WIDTH)
259    }
260}
261
262axis_extension_impl_for_field_axis!(PrimeFieldNumericSecp256k1);
263
264// ---- FieldElementShape: ConstrainedTypeShape carrier ----
265
266/// Parametric ConstrainedTypeShape carrying an `N`-byte field-element
267/// value (big-endian-encoded). Per ADR-031's `FieldElement<P>` shape
268/// commitment — but with the byte-width as the type-level parameter
269/// rather than the prime itself, since the field-element value
270/// occupies exactly `ceil(log_256(p))` bytes for any prime `p` near
271/// `2^(8N)`. The secp256k1 base field uses `BYTES = 32`.
272#[derive(Debug, Clone, Copy)]
273pub struct FieldElementShape<const BYTES: usize>;
274
275impl<const BYTES: usize> Default for FieldElementShape<BYTES> {
276    fn default() -> Self {
277        Self
278    }
279}
280
281impl<const BYTES: usize> ConstrainedTypeShape for FieldElementShape<BYTES> {
282    const IRI: &'static str = "https://uor.foundation/type/ConstrainedType";
283    const SITE_COUNT: usize = BYTES;
284    const CONSTRAINTS: &'static [ConstraintRef] = &[];
285    #[allow(clippy::cast_possible_truncation)]
286    const CYCLE_SIZE: u64 = 256u64.saturating_pow(BYTES as u32);
287}
288
289impl<const BYTES: usize> uor_foundation::pipeline::__sdk_seal::Sealed for FieldElementShape<BYTES> {}
290impl<const BYTES: usize> GroundedShape for FieldElementShape<BYTES> {}
291impl<'a, const BYTES: usize> IntoBindingValue<'a> for FieldElementShape<BYTES> {
292    fn as_binding_value<const INLINE_BYTES: usize>(&self) -> TermValue<'a, INLINE_BYTES> {
293        TermValue::empty()
294    }
295}
prism_numerics/field.rs

prism_numerics/
field.rs
