midnight_transient_crypto/
repr.rs

1// This file is part of midnight-ledger.
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//! This module deals with representing data as sequences of binary objects for
15//! use in persistent hashing, and as field elements for use in proofs,
16//! primarily through the [`FieldRepr`], [`BinaryHashRepr`], and
17//! [`FromFieldRepr`] traits.
18
19use crate::curve::{FR_BYTES, FR_BYTES_STORED, Fr};
20use crate::hash::hash_to_field;
21use base_crypto::repr::{BinaryHashRepr, MemWrite};
22use base_crypto::time::Timestamp;
23pub use derive::{FieldRepr, FromFieldRepr};
24use serialize::{Deserializable, Serializable, VecExt};
25use storage_core::Storable;
26use storage_core::db::DB;
27
28/// A type this implements this can be transformed into an iterator of [`Fr`]s.
29pub trait FieldRepr {
30    /// Writes out `self` as a sequence of [Fr] elements.
31    /// As a general rule of thumb, this should usually produces a known number of elements.
32    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W);
33    /// The size of a value when represented as field elements.
34    fn field_size(&self) -> usize;
35    /// Writes the hash repr into a vector
36    fn field_vec(&self) -> Vec<Fr> {
37        let mut res = Vec::with_bounded_capacity(self.field_size());
38        self.field_repr(&mut res);
39        res
40    }
41}
42
43/// A type than can be parsed from a sequence of [`Fr`]s.
44pub trait FromFieldRepr: Sized {
45    /// The number of elements this type can be reconstructed from.
46    const FIELD_SIZE: usize;
47    /// Attempts to parse from a slice of [`FIELD_SIZE`](Self::FIELD_SIZE) elements.
48    fn from_field_repr(repr: &[Fr]) -> Option<Self>;
49}
50
51impl BinaryHashRepr for Fr {
52    fn binary_repr<W: MemWrite<u8>>(&self, writer: &mut W) {
53        writer.write(&self.as_le_bytes())
54    }
55    fn binary_len(&self) -> usize {
56        FR_BYTES
57    }
58}
59
60macro_rules! tuple_repr {
61    ($head:ident$(, $tail:ident)*) => {
62        #[allow(unused_parens, non_snake_case)]
63        impl<$head: FieldRepr$(, $tail: FieldRepr)*> FieldRepr for ($head, $($tail),*) {
64            fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
65                let ($head, $($tail),*) = self;
66                $head.field_repr(writer);
67                $($tail.field_repr(writer);)*
68            }
69            fn field_size(&self) -> usize {
70                let ($head, $($tail),*) = self;
71                $head.field_size() $(+ $tail.field_size())*
72            }
73        }
74        #[allow(unused_parens, non_snake_case)]
75        impl<$head: FromFieldRepr$(, $tail: FromFieldRepr)*> FromFieldRepr for ($head, $($tail),*) {
76            const FIELD_SIZE: usize = <$head as FromFieldRepr>::FIELD_SIZE$( + <$tail as FromFieldRepr>::FIELD_SIZE)*;
77            fn from_field_repr(repr: &[Fr]) -> Option<Self> {
78                if repr.len() != Self::FIELD_SIZE {
79                    return None;
80                }
81                let __head_size = <$head as FromFieldRepr>::FIELD_SIZE;
82                let $head = <$head as FromFieldRepr>::from_field_repr(&repr[..__head_size])?;
83                let ($($tail, )*) = <($($tail, )*) as FromFieldRepr>::from_field_repr(&repr[__head_size..])?;
84                Some(($head, $($tail),*))
85            }
86        }
87        tuple_repr!($($tail),*);
88    };
89    () => {
90        impl FieldRepr for () {
91            fn field_repr<W: MemWrite<Fr>>(&self, _: &mut W) {
92            }
93            fn field_size(&self) -> usize {
94                0
95            }
96        }
97        impl FromFieldRepr for () {
98            const FIELD_SIZE: usize = 0;
99            fn from_field_repr(repr: &[Fr]) -> Option<Self> {
100                if repr.is_empty() {
101                    Some(())
102                } else {
103                    None
104                }
105            }
106        }
107    };
108}
109
110tuple_repr!(A, B, C, D, E, F, G, H, I, J, K, L);
111
112impl FromFieldRepr for [u8; 32] {
113    const FIELD_SIZE: usize = 2;
114    fn from_field_repr(repr: &[Fr]) -> Option<Self> {
115        if repr.len() != 2 {
116            return None;
117        }
118        let repr0 = repr[0].0.to_bytes_le();
119        let repr1 = repr[1].0.to_bytes_le();
120        if repr0[1..].iter().any(|ch| *ch != 0) {
121            return None;
122        }
123        if repr1[31..].iter().any(|ch| *ch != 0) {
124            return None;
125        }
126        let mut res = [0u8; 32];
127        res[31..].copy_from_slice(&repr0[..1]);
128        res[0..31].copy_from_slice(&repr1[..31]);
129        Some(res)
130    }
131}
132
133/// Converts a sequence of field elements into a corresponding byte vector.
134/// Guarantees that the results [`FieldRepr`] matches the input.
135pub fn bytes_from_field_repr(repr: &mut &[Fr], n: usize) -> Option<Vec<u8>> {
136    let stray = n % FR_BYTES_STORED;
137    let chunks = n / FR_BYTES_STORED;
138    let expected_size = chunks + (stray != 0) as usize;
139    if repr.len() < expected_size {
140        return None;
141    }
142    let mut res = vec![0u8; n];
143    let bytes_from = |slice: &mut [u8], k, f: Fr| {
144        let repr = f.as_le_bytes();
145        if repr[k..].iter().any(|b| *b != 0) {
146            None
147        } else {
148            slice.copy_from_slice(&repr[..k]);
149            Some(())
150        }
151    };
152    if stray > 0 {
153        bytes_from(&mut res[n - stray..], stray, repr[0])?;
154        *repr = &repr[1..];
155    }
156    for i in 0..chunks {
157        bytes_from(
158            &mut res[i * FR_BYTES_STORED..(i + 1) * FR_BYTES_STORED],
159            FR_BYTES_STORED,
160            repr[chunks - 1 - i],
161        )?;
162    }
163    *repr = &repr[chunks..];
164    Some(res)
165}
166
167impl FieldRepr for [u8] {
168    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
169        let mut slice = self;
170        while !slice.is_empty() {
171            let len = slice.len();
172            let stray = len % FR_BYTES_STORED;
173            if stray != 0 {
174                writer.write(&[Fr::from_le_bytes(&slice[len - stray..])
175                    .expect("Must fall in storable byte range")]);
176                slice = &slice[..len - stray];
177            } else {
178                let start = len - usize::min(FR_BYTES_STORED, len);
179                writer
180                    .write(&[Fr::from_le_bytes(&slice[start..])
181                        .expect("Must fall in storable byte range")]);
182                slice = &slice[..start];
183            }
184        }
185    }
186    fn field_size(&self) -> usize {
187        self.len().div_ceil(FR_BYTES_STORED)
188    }
189}
190
191impl<const N: usize> FieldRepr for [u8; N] {
192    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
193        <[u8]>::field_repr(self, writer)
194    }
195    fn field_size(&self) -> usize {
196        self.len() / FR_BYTES_STORED
197            + if self.len().is_multiple_of(FR_BYTES_STORED) {
198                0
199            } else {
200                1
201            }
202    }
203}
204
205impl<T: FieldRepr> FieldRepr for Vec<T> {
206    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
207        for e in self.iter() {
208            e.field_repr(writer);
209        }
210    }
211    fn field_size(&self) -> usize {
212        self.iter().map(|e| e.field_size()).sum()
213    }
214}
215
216// An odd one out, the assumption is this is a dynamically-sized string.
217impl FieldRepr for str {
218    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
219        writer.write(&[hash_to_field(self.as_bytes())]);
220    }
221    fn field_size(&self) -> usize {
222        1
223    }
224}
225
226macro_rules! via_from_field {
227    ($($ty:ty),*) => {
228        $(
229            impl FieldRepr for $ty {
230                fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
231                    writer.write(&[Fr::from(*self)]);
232                }
233                fn field_size(&self) -> usize {
234                    1
235                }
236            }
237
238            impl FromFieldRepr for $ty {
239                const FIELD_SIZE: usize = 1;
240                fn from_field_repr(repr: &[Fr]) -> Option<Self> {
241                    if repr.len() == 1 {
242                        Some(repr[0].try_into().ok()?)
243                    } else {
244                        None
245                    }
246                }
247            }
248        )*
249    }
250}
251
252via_from_field!(u128, u64, u32, u16, u8, i128, i64, i32, i16, i8, Fr, bool);
253
254impl FieldRepr for Timestamp {
255    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
256        self.to_secs().field_repr(writer)
257    }
258    fn field_size(&self) -> usize {
259        self.to_secs().field_size()
260    }
261}
262
263impl<T: FieldRepr> FieldRepr for Option<T> {
264    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
265        match self {
266            Some(v) => {
267                writer.write(&[1u8.into()]);
268                v.field_repr(writer);
269            }
270            None => writer.write(&[0u8.into()]),
271        }
272    }
273    fn field_size(&self) -> usize {
274        match self {
275            Some(v) => 1 + v.field_size(),
276            None => 1,
277        }
278    }
279}
280
281impl FieldRepr for [Fr] {
282    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
283        writer.write(self);
284    }
285    fn field_size(&self) -> usize {
286        self.len()
287    }
288}
289
290impl<const N: usize> FieldRepr for [Fr; N] {
291    fn field_repr<W: MemWrite<Fr>>(&self, writer: &mut W) {
292        writer.write(self)
293    }
294    fn field_size(&self) -> usize {
295        N
296    }
297}
298
299#[cfg(test)]
300mod tests {
301    use super::*;
302
303    #[test]
304    fn bytes_field_repr_matches_compact() {
305        let test_vector = b" 0 1 2 3 4 5 6 7 8 9101112131415161718192021222324252627282930";
306        assert_eq!(
307            test_vector.field_vec(),
308            vec![
309                Fr::from_le_bytes(b"5161718192021222324252627282930")
310                    .expect("known value must be in range"),
311                Fr::from_le_bytes(b" 0 1 2 3 4 5 6 7 8 910111213141")
312                    .expect("known value must be in range"),
313            ]
314        )
315    }
316
317    #[test]
318    fn byte32_encoding() {
319        let test_vector = b" 0 1 2 3 4 5 6 7 8 9101112131415";
320        assert_eq!(
321            <[u8; 32]>::from_field_repr(&test_vector.field_vec()),
322            Some(*test_vector)
323        );
324    }
325}
midnight_transient_crypto/repr.rs

midnight_transient_crypto/
repr.rs
