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::{
43    AxisExtension, ConstrainedTypeShape, ConstraintRef, IntoBindingValue,
44};
45use uor_foundation_sdk::axis;
46
47use crate::{check_output, split_pair};
48
49axis! {
50    /// Wiki ADR-031 prime-field arithmetic axis.
51    ///
52    /// The reference impl `PrimeFieldNumericSecp256k1` fixes the modulus
53    /// at the secp256k1 base field prime: `p = 2^256 - 2^32 - 977`.
54    pub trait FieldAxis: AxisExtension {
55        /// ADR-017 content address.
56        const AXIS_ADDRESS: &'static str = "https://uor.foundation/axis/FieldAxis";
57        /// Operand byte-width (32 bytes for secp256k1).
58        const MAX_OUTPUT_BYTES: usize = 32;
59        /// `(a + b) mod p` — input `a || b` (64 bytes).
60        ///
61        /// # Errors
62        ///
63        /// Returns `ShapeViolation` on input/output arity mismatch.
64        fn add(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation>;
65        /// `(a - b) mod p` — input `a || b` (64 bytes).
66        ///
67        /// # Errors
68        ///
69        /// Returns `ShapeViolation` on input/output arity mismatch.
70        fn sub(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation>;
71        /// `(a * b) mod p` — input `a || b` (64 bytes).
72        ///
73        /// # Errors
74        ///
75        /// Returns `ShapeViolation` on input/output arity mismatch.
76        fn mul(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation>;
77    }
78}
79
80const WIDTH: usize = 32;
81
82// secp256k1 base field prime p = 2^256 - 2^32 - 977.
83const P: [u8; WIDTH] = [
84    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
85    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xfc, 0x2f,
86];
87
88fn cmp_ge(a: &[u8; WIDTH], b: &[u8; WIDTH]) -> bool {
89    for i in 0..WIDTH {
90        if a[i] != b[i] {
91            return a[i] > b[i];
92        }
93    }
94    true
95}
96
97fn sub_assign(target: &mut [u8; WIDTH], rhs: &[u8; WIDTH]) {
98    let mut borrow: i16 = 0;
99    for i in (0..WIDTH).rev() {
100        let diff = i16::from(target[i]) - i16::from(rhs[i]) - borrow;
101        if diff < 0 {
102            #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
103            {
104                target[i] = (diff + 256) as u8;
105            }
106            borrow = 1;
107        } else {
108            #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
109            {
110                target[i] = diff as u8;
111            }
112            borrow = 0;
113        }
114    }
115}
116
117fn add_with_carry(a: &[u8; WIDTH], b: &[u8; WIDTH]) -> ([u8; WIDTH], u8) {
118    let mut out = [0u8; WIDTH];
119    let mut carry: u16 = 0;
120    for i in (0..WIDTH).rev() {
121        let sum = u16::from(a[i]) + u16::from(b[i]) + carry;
122        #[allow(clippy::cast_possible_truncation)]
123        {
124            out[i] = (sum & 0xff) as u8;
125        }
126        carry = sum >> 8;
127    }
128    #[allow(clippy::cast_possible_truncation)]
129    (out, carry as u8)
130}
131
132fn reduce_to_field(value: [u8; WIDTH], had_carry: bool) -> [u8; WIDTH] {
133    let mut v = value;
134    if had_carry {
135        sub_assign(&mut v, &P);
136    }
137    while cmp_ge(&v, &P) {
138        sub_assign(&mut v, &P);
139    }
140    v
141}
142
143fn mod_mul(a: &[u8; WIDTH], b: &[u8; WIDTH]) -> [u8; WIDTH] {
144    let mut acc = [0u32; 2 * WIDTH];
145    for i in (0..WIDTH).rev() {
146        for j in (0..WIDTH).rev() {
147            let prod = u32::from(a[i]) * u32::from(b[j]);
148            let pos = i + j + 1;
149            let sum = acc[pos] + (prod & 0xff);
150            acc[pos] = sum & 0xff;
151            let mut carry = (sum >> 8) + (prod >> 8);
152            let mut k = pos;
153            while carry > 0 && k > 0 {
154                k -= 1;
155                let next = acc[k] + carry;
156                acc[k] = next & 0xff;
157                carry = next >> 8;
158            }
159        }
160    }
161    let mut bytes = [0u8; 2 * WIDTH];
162    for i in 0..2 * WIDTH {
163        #[allow(clippy::cast_possible_truncation)]
164        {
165            bytes[i] = (acc[i] & 0xff) as u8;
166        }
167    }
168    for shift_bytes in (0..=WIDTH).rev() {
169        loop {
170            let mut higher_than_p = false;
171            for i in 0..WIDTH {
172                let lhs = bytes[shift_bytes + i];
173                let rhs = P[i];
174                if lhs != rhs {
175                    higher_than_p = lhs > rhs;
176                    break;
177                } else if i == WIDTH - 1 {
178                    higher_than_p = true;
179                }
180            }
181            let mut upper_zero = true;
182            for byte in bytes.iter().take(shift_bytes) {
183                if *byte != 0 {
184                    upper_zero = false;
185                    break;
186                }
187            }
188            if !upper_zero || !higher_than_p {
189                break;
190            }
191            let mut borrow: i16 = 0;
192            for i in (0..WIDTH).rev() {
193                let diff = i16::from(bytes[shift_bytes + i]) - i16::from(P[i]) - borrow;
194                if diff < 0 {
195                    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
196                    {
197                        bytes[shift_bytes + i] = (diff + 256) as u8;
198                    }
199                    borrow = 1;
200                } else {
201                    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
202                    {
203                        bytes[shift_bytes + i] = diff as u8;
204                    }
205                    borrow = 0;
206                }
207            }
208        }
209    }
210    let mut out = [0u8; WIDTH];
211    out.copy_from_slice(&bytes[WIDTH..]);
212    out
213}
214
215fn read32(slice: &[u8]) -> [u8; WIDTH] {
216    let mut out = [0u8; WIDTH];
217    out.copy_from_slice(&slice[..WIDTH]);
218    out
219}
220
221/// secp256k1 base-field arithmetic.
222#[derive(Debug, Clone, Copy, Default)]
223pub struct PrimeFieldNumericSecp256k1;
224
225impl FieldAxis for PrimeFieldNumericSecp256k1 {
226    const AXIS_ADDRESS: &'static str = "https://uor.foundation/axis/FieldAxis/Secp256k1Base";
227    const MAX_OUTPUT_BYTES: usize = WIDTH;
228
229    fn add(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation> {
230        let (a, b) = split_pair(input, WIDTH)?;
231        check_output(out, WIDTH)?;
232        let a = read32(a);
233        let b = read32(b);
234        let (sum, carry) = add_with_carry(&a, &b);
235        let result = reduce_to_field(sum, carry != 0);
236        out[..WIDTH].copy_from_slice(&result);
237        Ok(WIDTH)
238    }
239
240    fn sub(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation> {
241        let (a, b) = split_pair(input, WIDTH)?;
242        check_output(out, WIDTH)?;
243        let a = read32(a);
244        let b = read32(b);
245        let mut p_minus_b = P;
246        sub_assign(&mut p_minus_b, &b);
247        let (sum, carry) = add_with_carry(&a, &p_minus_b);
248        let result = reduce_to_field(sum, carry != 0);
249        out[..WIDTH].copy_from_slice(&result);
250        Ok(WIDTH)
251    }
252
253    fn mul(input: &[u8], out: &mut [u8]) -> Result<usize, ShapeViolation> {
254        let (a, b) = split_pair(input, WIDTH)?;
255        check_output(out, WIDTH)?;
256        let a = read32(a);
257        let b = read32(b);
258        let result = mod_mul(&a, &b);
259        out[..WIDTH].copy_from_slice(&result);
260        Ok(WIDTH)
261    }
262}
263
264axis_extension_impl_for_field_axis!(PrimeFieldNumericSecp256k1);
265
266// ---- FieldElementShape: ConstrainedTypeShape carrier ----
267
268/// Parametric ConstrainedTypeShape carrying an `N`-byte field-element
269/// value (big-endian-encoded). Per ADR-031's `FieldElement<P>` shape
270/// commitment — but with the byte-width as the type-level parameter
271/// rather than the prime itself, since the field-element value
272/// occupies exactly `ceil(log_256(p))` bytes for any prime `p` near
273/// `2^(8N)`. The secp256k1 base field uses `BYTES = 32`.
274#[derive(Debug, Clone, Copy)]
275pub struct FieldElementShape<const BYTES: usize>;
276
277impl<const BYTES: usize> Default for FieldElementShape<BYTES> {
278    fn default() -> Self {
279        Self
280    }
281}
282
283impl<const BYTES: usize> ConstrainedTypeShape for FieldElementShape<BYTES> {
284    const IRI: &'static str = "https://uor.foundation/type/ConstrainedType";
285    const SITE_COUNT: usize = BYTES;
286    const CONSTRAINTS: &'static [ConstraintRef] = &[];
287    #[allow(clippy::cast_possible_truncation)]
288    const CYCLE_SIZE: u64 = 256u64.saturating_pow(BYTES as u32);
289}
290
291impl<const BYTES: usize> uor_foundation::pipeline::__sdk_seal::Sealed for FieldElementShape<BYTES> {}
292impl<const BYTES: usize> GroundedShape for FieldElementShape<BYTES> {}
293impl<const BYTES: usize> IntoBindingValue for FieldElementShape<BYTES> {
294    const MAX_BYTES: usize = BYTES;
295
296    fn into_binding_bytes(&self, _out: &mut [u8]) -> Result<usize, ShapeViolation> {
297        Ok(0)
298    }
299}
prism_numerics/field.rs

prism_numerics/
field.rs
