bech32/primitives/
gf32.rs

1// SPDX-License-Identifier: MIT
2
3//! GF32 - Galois Field over 32 elements.
4//!
5//! Implements GF32 arithmetic, defined and encoded as in [BIP-173] "bech32".
6//!
7//! > A finite field is a finite set which is a field; this means that multiplication, addition,
8//! > subtraction and division (excluding division by zero) are defined and satisfy the rules of
9//! > arithmetic known as the field axioms.
10//!
11//! ref: <https://en.wikipedia.org/wiki/Finite_field>
12//!
13//! [BIP-173]: <https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki>
14
15use core::convert::{Infallible, TryFrom};
16use core::{fmt, num, ops};
17
18#[cfg(all(test, mutate))]
19use mutagen::mutate;
20
21use crate::error::write_err;
22
23/// Logarithm table of each bech32 element, as a power of alpha = Z.
24///
25/// Includes Q as 0 but this is false; you need to exclude Q because it has no discrete log. If we
26/// could have a 1-indexed array that would panic on a 0 index that would be better.
27#[rustfmt::skip]
28const LOG: [isize; 32] = [
29     0,  0,  1, 14,  2, 28, 15, 22,
30     3,  5, 29, 26, 16,  7, 23, 11,
31     4, 25,  6, 10, 30, 13, 27, 21,
32    17, 18,  8, 19, 24,  9, 12, 20,
33];
34
35/// Mapping of powers of 2 to the numeric value of the element.
36#[rustfmt::skip]
37const LOG_INV: [u8; 31] = [
38     1,  2,  4,  8, 16,  9, 18, 13,
39    26, 29, 19, 15, 30, 21,  3,  6,
40    12, 24, 25, 27, 31, 23,  7, 14,
41    28, 17, 11, 22,  5, 10, 20,
42];
43
44/// Mapping from numeric value to bech32 character.
45#[rustfmt::skip]
46const CHARS_LOWER: [char; 32] = [
47    'q', 'p', 'z', 'r', 'y', '9', 'x', '8', //  +0
48    'g', 'f', '2', 't', 'v', 'd', 'w', '0', //  +8
49    's', '3', 'j', 'n', '5', '4', 'k', 'h', // +16
50    'c', 'e', '6', 'm', 'u', 'a', '7', 'l', // +24
51];
52
53/// Mapping from bech32 character (either case) to numeric value.
54///
55/// E.g., 'z' is CHARS_LOWER[2] and is ASCII value 122 so CHARS_INV[122] == 2
56#[rustfmt::skip]
57const CHARS_INV: [i8; 128] = [
58    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
59    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
60    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
61    15, -1, 10, 17, 21, 20, 26, 30,  7,  5, -1, -1, -1, -1, -1, -1,
62    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
63     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1,
64    -1, 29, -1, 24, 13, 25,  9,  8, 23, -1, 18, 22, 31, 27, 19, -1,
65     1,  0,  3, 16, 11, 28, 12, 14,  6,  4,  2, -1, -1, -1, -1, -1,
66];
67
68/// An element in GF(32), the finite field containing elements `[0,31]` inclusive.
69#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
70#[repr(transparent)]
71pub struct Fe32(pub(crate) u8);
72
73impl Fe32 {
74    // These are a little gratuitous for a reference implementation, but it makes me happy to do it.
75    /// Numeric value maps to bech32 character: 0 == "q".
76    pub const Q: Fe32 = Fe32(0);
77    /// Numeric value maps to bech32 character: 1 == "p".
78    pub const P: Fe32 = Fe32(1);
79    /// Numeric value maps to bech32 character: 2 == "z".
80    pub const Z: Fe32 = Fe32(2);
81    /// Numeric value maps to bech32 character: 3 == "r".
82    pub const R: Fe32 = Fe32(3);
83    /// Numeric value maps to bech32 character: 4 == "y".
84    pub const Y: Fe32 = Fe32(4);
85    /// Numeric value maps to bech32 character: 5 == "9".
86    pub const _9: Fe32 = Fe32(5);
87    /// Numeric value maps to bech32 character: 6 == "x".
88    pub const X: Fe32 = Fe32(6);
89    /// Numeric value maps to bech32 character: 7 == "8".
90    pub const _8: Fe32 = Fe32(7);
91    /// Numeric value maps to bech32 character: 8 == "g".
92    pub const G: Fe32 = Fe32(8);
93    /// Numeric value maps to bech32 character: 9 == "f".
94    pub const F: Fe32 = Fe32(9);
95    /// Numeric value maps to bech32 character: 10 == "2".
96    pub const _2: Fe32 = Fe32(10);
97    /// Numeric value maps to bech32 character: 11 == "t".
98    pub const T: Fe32 = Fe32(11);
99    /// Numeric value maps to bech32 character: 12 == "v".
100    pub const V: Fe32 = Fe32(12);
101    /// Numeric value maps to bech32 character: 13 == "d".
102    pub const D: Fe32 = Fe32(13);
103    /// Numeric value maps to bech32 character: 14 == "w".
104    pub const W: Fe32 = Fe32(14);
105    /// Numeric value maps to bech32 character: 15 == "0".
106    pub const _0: Fe32 = Fe32(15);
107    /// Numeric value maps to bech32 character: 16 == "s".
108    pub const S: Fe32 = Fe32(16);
109    /// Numeric value maps to bech32 character: 17 == "3".
110    pub const _3: Fe32 = Fe32(17);
111    /// Numeric value maps to bech32 character: 18 == "j".
112    pub const J: Fe32 = Fe32(18);
113    /// Numeric value maps to bech32 character: 19 == "n".
114    pub const N: Fe32 = Fe32(19);
115    /// Numeric value maps to bech32 character: 20 == "5".
116    pub const _5: Fe32 = Fe32(20);
117    /// Numeric value maps to bech32 character: 21 == "4".
118    pub const _4: Fe32 = Fe32(21);
119    /// Numeric value maps to bech32 character: 22 == "k".
120    pub const K: Fe32 = Fe32(22);
121    /// Numeric value maps to bech32 character: 23 == "h".
122    pub const H: Fe32 = Fe32(23);
123    /// Numeric value maps to bech32 character: 24 == "c".
124    pub const C: Fe32 = Fe32(24);
125    /// Numeric value maps to bech32 character: 25 == "e".
126    pub const E: Fe32 = Fe32(25);
127    /// Numeric value maps to bech32 character: 26 == "6".
128    pub const _6: Fe32 = Fe32(26);
129    /// Numeric value maps to bech32 character: 27 == "m".
130    pub const M: Fe32 = Fe32(27);
131    /// Numeric value maps to bech32 character: 28 == "u".
132    pub const U: Fe32 = Fe32(28);
133    /// Numeric value maps to bech32 character: 29 == "a".
134    pub const A: Fe32 = Fe32(29);
135    /// Numeric value maps to bech32 character: 30 == "7".
136    pub const _7: Fe32 = Fe32(30);
137    /// Numeric value maps to bech32 character: 31 == "l".
138    pub const L: Fe32 = Fe32(31);
139
140    /// Iterator over all field elements, in alphabetical order.
141    #[inline]
142    pub fn iter_alpha() -> impl Iterator<Item = Fe32> {
143        [
144            Fe32::A,
145            Fe32::C,
146            Fe32::D,
147            Fe32::E,
148            Fe32::F,
149            Fe32::G,
150            Fe32::H,
151            Fe32::J,
152            Fe32::K,
153            Fe32::L,
154            Fe32::M,
155            Fe32::N,
156            Fe32::P,
157            Fe32::Q,
158            Fe32::R,
159            Fe32::S,
160            Fe32::T,
161            Fe32::U,
162            Fe32::V,
163            Fe32::W,
164            Fe32::X,
165            Fe32::Y,
166            Fe32::Z,
167            Fe32::_0,
168            Fe32::_2,
169            Fe32::_3,
170            Fe32::_4,
171            Fe32::_5,
172            Fe32::_6,
173            Fe32::_7,
174            Fe32::_8,
175            Fe32::_9,
176        ]
177        .iter()
178        .copied()
179    }
180
181    /// Creates a field element from a single bech32 character.
182    ///
183    /// # Errors
184    ///
185    /// If the input char is not part of the bech32 alphabet.
186    #[inline]
187    pub fn from_char(c: char) -> Result<Fe32, FromCharError> {
188        use FromCharError::*;
189
190        // i8::try_from gets a value in the range 0..=127 since char is unsigned.
191        let byte = i8::try_from(u32::from(c)).map_err(|_| NotAscii(c))?;
192        // Now we have a valid ASCII value cast is safe.
193        let ascii = byte as usize;
194        // We use -1 for any array element that is an invalid char to trigger error from u8::try_from
195        let u5 = u8::try_from(CHARS_INV[ascii]).map_err(|_| Invalid(c))?;
196
197        Ok(Fe32(u5))
198    }
199
200    /// Creates a field element from a single bech32 character.
201    ///
202    /// # Panics
203    ///
204    /// If the input character is not part of the bech32 alphabet.
205    pub fn from_char_unchecked(c: u8) -> Fe32 { Fe32(CHARS_INV[usize::from(c)] as u8) }
206
207    /// Converts the field element to a lowercase bech32 character.
208    #[inline]
209    pub fn to_char(self) -> char {
210        // Indexing fine as we have self.0 in [0, 32) as an invariant.
211        CHARS_LOWER[usize::from(self.0)]
212    }
213
214    /// Converts the field element to a 5-bit u8, with bits representing the coefficients
215    /// of the polynomial representation.
216    #[inline]
217    pub fn to_u8(self) -> u8 { self.0 }
218
219    fn _add(self, other: Fe32) -> Fe32 { Fe32(self.0 ^ other.0) }
220
221    // Subtraction is the same as addition in a char-2 field.
222    fn _sub(self, other: Fe32) -> Fe32 { self + other }
223
224    #[cfg_attr(all(test, mutate), mutate)]
225    fn _mul(self, other: Fe32) -> Fe32 {
226        if self.0 == 0 || other.0 == 0 {
227            Fe32(0)
228        } else {
229            let log1 = LOG[self.0 as usize];
230            let log2 = LOG[other.0 as usize];
231            Fe32(LOG_INV[((log1 + log2) % 31) as usize])
232        }
233    }
234
235    #[cfg_attr(all(test, mutate), mutate)]
236    fn _div(self, other: Fe32) -> Fe32 {
237        if self.0 == 0 {
238            Fe32(0)
239        } else if other.0 == 0 {
240            panic!("Attempt to divide {} by 0 in GF32", self);
241        } else {
242            let log1 = LOG[self.0 as usize];
243            let log2 = LOG[other.0 as usize];
244            Fe32(LOG_INV[((31 + log1 - log2) % 31) as usize])
245        }
246    }
247}
248
249impl fmt::Display for Fe32 {
250    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Display::fmt(&self.to_char(), f) }
251}
252
253impl From<Fe32> for u8 {
254    #[inline]
255    fn from(v: Fe32) -> u8 { v.0 }
256}
257
258macro_rules! impl_try_from {
259    ($($ty:ident)+) => {
260        $(
261            impl TryFrom<$ty> for Fe32 {
262                type Error = TryFromError;
263
264                /// Tries to create an [`Fe32`] type from a signed source number type.
265                ///
266                /// # Errors
267                ///
268                /// Returns an error if `value` is outside of the range of an `Fe32`.
269                #[inline]
270                fn try_from(value: $ty) -> Result<Self, Self::Error> {
271                    let byte = u8::try_from(value)?;
272                    if byte > 31 {
273                        Err(TryFromError::InvalidByte(byte))?;
274                    }
275                    Ok(Fe32(byte))
276                }
277            }
278        )+
279    }
280}
281impl_try_from!(u8 u16 u32 u64 u128 i8 i16 i32 i64 i128);
282
283impl AsRef<u8> for Fe32 {
284    #[inline]
285    fn as_ref(&self) -> &u8 { &self.0 }
286}
287
288/// Implements $op for the 2x2 matrix of type by ref to type
289macro_rules! impl_op_matrix {
290    ($op:ident, $op_fn:ident, $call_fn:ident) => {
291        impl ops::$op<Fe32> for Fe32 {
292            type Output = Fe32;
293            #[inline]
294            fn $op_fn(self, other: Fe32) -> Fe32 { self.$call_fn(other) }
295        }
296
297        impl ops::$op<Fe32> for &Fe32 {
298            type Output = Fe32;
299            #[inline]
300            fn $op_fn(self, other: Fe32) -> Fe32 { self.$call_fn(other) }
301        }
302
303        impl ops::$op<&Fe32> for Fe32 {
304            type Output = Fe32;
305            #[inline]
306            fn $op_fn(self, other: &Fe32) -> Fe32 { self.$call_fn(*other) }
307        }
308
309        impl ops::$op<&Fe32> for &Fe32 {
310            type Output = Fe32;
311            #[inline]
312            fn $op_fn(self, other: &Fe32) -> Fe32 { self.$call_fn(*other) }
313        }
314    };
315}
316impl_op_matrix!(Add, add, _add);
317impl_op_matrix!(Sub, sub, _sub);
318impl_op_matrix!(Mul, mul, _mul);
319impl_op_matrix!(Div, div, _div);
320
321impl ops::AddAssign for Fe32 {
322    #[inline]
323    fn add_assign(&mut self, other: Fe32) { *self = *self + other; }
324}
325
326impl ops::SubAssign for Fe32 {
327    #[inline]
328    fn sub_assign(&mut self, other: Fe32) { *self = *self - other; }
329}
330
331impl ops::MulAssign for Fe32 {
332    #[inline]
333    fn mul_assign(&mut self, other: Fe32) { *self = *self * other; }
334}
335
336impl ops::DivAssign for Fe32 {
337    #[inline]
338    fn div_assign(&mut self, other: Fe32) { *self = *self / other; }
339}
340
341/// A galois field error when converting from a character.
342#[derive(Copy, Clone, PartialEq, Eq, Debug)]
343#[non_exhaustive]
344pub enum FromCharError {
345    /// Tried to interpret a character as a GF32 element but it is not an ASCII character.
346    NotAscii(char),
347    /// Tried to interpret a character as a GF32 element but it is not part of the bech32 character set.
348    Invalid(char),
349}
350
351impl fmt::Display for FromCharError {
352    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
353        use FromCharError::*;
354
355        match *self {
356            NotAscii(c) => write!(f, "non-ascii char in field element: {}", c),
357            Invalid(c) => write!(f, "invalid char in field element: {}", c),
358        }
359    }
360}
361
362#[cfg(feature = "std")]
363impl std::error::Error for FromCharError {
364    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
365        use FromCharError::*;
366
367        match *self {
368            NotAscii(_) | Invalid(_) => None,
369        }
370    }
371}
372
373/// A galois field error when converting from an integer.
374#[derive(Copy, Clone, PartialEq, Eq, Debug)]
375#[non_exhaustive]
376pub enum TryFromError {
377    /// Tried to interpret an integer as a GF32 element but it could not be converted to an u8.
378    NotAByte(num::TryFromIntError),
379    /// Tried to interpret a byte as a GF32 element but its numeric value was outside of [0, 32).
380    InvalidByte(u8),
381}
382
383impl fmt::Display for TryFromError {
384    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
385        use TryFromError::*;
386
387        match *self {
388            NotAByte(ref e) => write_err!(f, "invalid field element"; e),
389            InvalidByte(ref b) => write!(f, "invalid byte in field element: {:#04x}", b),
390        }
391    }
392}
393
394#[cfg(feature = "std")]
395impl std::error::Error for TryFromError {
396    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
397        use TryFromError::*;
398
399        match *self {
400            NotAByte(ref e) => Some(e),
401            InvalidByte(_) => None,
402        }
403    }
404}
405
406impl From<num::TryFromIntError> for TryFromError {
407    #[inline]
408    fn from(e: num::TryFromIntError) -> Self { Self::NotAByte(e) }
409}
410
411impl From<Infallible> for TryFromError {
412    #[inline]
413    fn from(i: Infallible) -> Self { match i {} }
414}
415
416#[cfg(test)]
417mod tests {
418    use super::*;
419
420    #[test]
421    fn numeric_string() {
422        let s: String = (0..32).map(Fe32).map(Fe32::to_char).collect();
423        assert_eq!(s, "qpzry9x8gf2tvdw0s3jn54khce6mua7l");
424    }
425
426    // For what a "translation wheel" is refer to the codex32 book:
427    // https://github.com/BlockstreamResearch/codex32/blob/master/SSS32.ps
428    #[test]
429    fn translation_wheel() {
430        // 1. Produce the translation wheel by multiplying
431        let logbase = Fe32(20);
432        let mut init = Fe32(1);
433        let mut s = String::new();
434        for _ in 0..31 {
435            s.push(init.to_char());
436            init *= logbase;
437        }
438        // Can be verified against the multiplication disk, starting with P and moving clockwise
439        assert_eq!(s, "p529kt3uw8hlmecvxr470na6djfsgyz");
440
441        // 2. By dividing
442        let logbase = Fe32(20);
443        let mut init = Fe32(1);
444        let mut s = String::new();
445        for _ in 0..31 {
446            s.push(init.to_char());
447            init /= logbase;
448        }
449        // Same deal, but counterclockwise
450        assert_eq!(s, "pzygsfjd6an074rxvcemlh8wu3tk925");
451    }
452
453    // For what a "recovery wheel" is refer to the codex32 book:
454    // https://github.com/BlockstreamResearch/codex32/blob/master/SSS32.ps
455    #[test]
456    fn recovery_wheel() {
457        // Remarkably, the recovery wheel can be produced in the same way as the
458        // multiplication wheel, though with a different log base and with every
459        // element added by S.
460        //
461        // We spent quite some time deriving this, but honestly we probably could've
462        // just guessed it if we'd known a priori that a wheel existed.
463        let logbase = Fe32(10);
464        let mut init = Fe32(1);
465        let mut s = String::new();
466        for _ in 0..31 {
467            s.push((init + Fe32(16)).to_char());
468            init *= logbase;
469        }
470        // To verify, start with 3 and move clockwise on the Recovery Wheel
471        assert_eq!(s, "36xp78tgk9ldaecjy4mvh0funwr2zq5");
472    }
473
474    #[test]
475    fn reverse_charset() {
476        fn get_char_value(c: char) -> i8 {
477            let charset = "qpzry9x8gf2tvdw0s3jn54khce6mua7l";
478            match charset.find(c.to_ascii_lowercase()) {
479                Some(x) => x as i8,
480                None => -1,
481            }
482        }
483
484        let expected_rev_charset =
485            (0u8..128).map(|i| get_char_value(i as char)).collect::<Vec<_>>();
486
487        assert_eq!(&(CHARS_INV[..]), expected_rev_charset.as_slice());
488    }
489
490    #[test]
491    fn from_char() {
492        for c in &CHARS_LOWER[..] {
493            assert!(Fe32::from_char(*c).is_ok())
494        }
495    }
496
497    #[test]
498    fn from_upper_char() {
499        let lower = Fe32::from_char('q').expect("failed to create fe32 from lowercase ascii char");
500        let upper = Fe32::from_char('Q').expect("failed to create fe32 from uppercase ascii char");
501
502        assert_eq!(lower, upper);
503    }
504
505    #[test]
506    fn mul_zero() {
507        for c in &CHARS_LOWER[..] {
508            let fe = Fe32::from_char(*c).unwrap();
509            assert_eq!(fe._mul(Fe32::Q), Fe32::Q) // Fe32::Q == Fe32(0)
510        }
511    }
512
513    #[test]
514    #[should_panic]
515    fn div_zero() {
516        let _ = Fe32::P / Fe32::Q; // Fe32::Q == Fe32(0)
517    }
518
519    #[test]
520    fn div_self_zero() {
521        let fe = Fe32::Z; // Value of Z not meaningful to the test.
522        assert_eq!(Fe32::Q / fe, Fe32::Q) // Fe32::Q == Fe32(0)
523    }
524
525    #[test]
526    fn mul_one() {
527        for c in &CHARS_LOWER[..] {
528            let fe = Fe32::from_char(*c).unwrap();
529            assert_eq!(fe * Fe32::P, fe) // Fe32::P == Fe32(1)
530        }
531    }
532}
533
534#[cfg(kani)]
535mod verification {
536    use super::*;
537
538    #[kani::proof]
539    fn check_char_conversion() {
540        let any: char = kani::any();
541        // Checks that we can pass any char to from_char and not cause a panic ... I think.
542        if let Ok(fe) = Fe32::from_char(any) {
543            let got = fe.to_char();
544            let want = any.to_ascii_lowercase();
545            assert_eq!(got, want);
546        }
547    }
548}
bech32/primitives/gf32.rs

bech32/primitives/
gf32.rs
