md_codec/
bch.rs

1//! BIP 93 codex32 BCH primitives for HRP `"md"` (regular code only).
2//!
3//! Extracted from the v0.x `encoding` module; v0.11 needs only the regular-code
4//! checksum + verify (long code dropped along with v0.x).
5
6/// BCH(93,80,8) generator polynomial coefficients (5 × 65-bit).
7pub const GEN_REGULAR: [u128; 5] = [
8    0x19dc500ce73fde210,
9    0x1bfae00def77fe529,
10    0x1fbd920fffe7bee52,
11    0x1739640bdeee3fdad,
12    0x07729a039cfc75f5a,
13];
14
15/// MD-domain target residue (NUMS-style, top 65 bits of
16/// `SHA-256("shibbolethnums")`).
17pub const MD_REGULAR_CONST: u128 = 0x0815c07747a3392e7;
18
19/// Initial polymod residue. This value (`0x23181b3`) IS codex32/BIP-93's
20/// `ms32_polymod` initial residue — the reference `ms32_polymod` seeds its
21/// accumulator with exactly this constant, and [`GEN_REGULAR`] above is
22/// BIP-93's `ms32` generator, term for term. (It is **not** bech32/BIP-173's
23/// init `1`; that init belongs to a different code. Earlier notes here
24/// claiming md1 "deliberately deviates from codex32's init `1`" and that
25/// "only ms1 uses `1`" were both wrong: codex32's init is `0x23181b3`, and no
26/// constellation format — md1, mk1, or ms1 — uses `1`.)
27///
28/// All three constellation codes (md1, mk1, ms1) build on the codex32 `ms32`
29/// code. md1 and mk1 seed this init literally (mk1: `mk-codec`'s
30/// `string_layer::bch::POLYMOD_INIT`). ms1 (`ms-codec`) uses the mathematically
31/// **equivalent** formulation — codex32's literal `1` init with an
32/// `hrp_expand("ms")` prepend — because `0x23181b3` is exactly the fold of
33/// `hrp_expand("ms")` from `1`; a raw constant-diff against `ms-codec`'s
34/// `POLYMOD_INIT = 0x1` is therefore NOT a discrepancy. Cross-format domain
35/// separation comes entirely from the per-HRP **target** residue that each
36/// format XORs against the final polymod (md1 uses [`MD_REGULAR_CONST`], a
37/// NUMS-derived constant, in place of codex32's own `MS32_CONST`) — never from
38/// the init. Because this same value seeds both
39/// [`bch_create_checksum_regular`] and [`bch_verify_regular`], its contribution
40/// cancels between create and verify, so `polymod(valid codeword) ==
41/// MD_REGULAR_CONST` holds at every length for any fixed init.
42const POLYMOD_INIT: u128 = 0x23181b3;
43const REGULAR_SHIFT: u32 = 60;
44const REGULAR_MASK: u128 = 0x0fffffffffffffff;
45
46fn polymod_step(residue: u128, value: u128) -> u128 {
47    let b = residue >> REGULAR_SHIFT;
48    let mut new_residue = ((residue & REGULAR_MASK) << 5) ^ value;
49    for (i, &g) in GEN_REGULAR.iter().enumerate() {
50        if (b >> i) & 1 != 0 {
51            new_residue ^= g;
52        }
53    }
54    new_residue
55}
56
57/// Run the BCH polymod over `values` starting from `POLYMOD_INIT`.
58///
59/// Returns the final residue; callers XOR against the per-HRP target
60/// constant (e.g. [`MD_REGULAR_CONST`]) to produce a checksum or to
61/// verify one. Inputs are 5-bit symbols (`u8` in `0..32`); larger
62/// values are reduced modulo 32 by the underlying step.
63pub fn polymod_run(values: &[u8]) -> u128 {
64    let mut residue = POLYMOD_INIT;
65    for &v in values {
66        residue = polymod_step(residue, v as u128);
67    }
68    residue
69}
70
71/// BIP 173-style HRP expansion: `[c >> 5 for c in hrp] ++ [0] ++ [c & 31 for c in hrp]`.
72pub fn hrp_expand(hrp: &str) -> Vec<u8> {
73    let bytes = hrp.as_bytes();
74    let mut out = Vec::with_capacity(bytes.len() * 2 + 1);
75    for &c in bytes {
76        out.push(c >> 5);
77    }
78    out.push(0);
79    for &c in bytes {
80        out.push(c & 31);
81    }
82    out
83}
84
85/// 13-symbol regular-code BCH checksum over `hrp_expand(hrp) || data || [0; 13]`.
86pub fn bch_create_checksum_regular(hrp: &str, data: &[u8]) -> [u8; 13] {
87    let mut input = hrp_expand(hrp);
88    input.extend_from_slice(data);
89    input.extend(std::iter::repeat_n(0, 13));
90    let polymod = polymod_run(&input) ^ MD_REGULAR_CONST;
91    let mut out = [0u8; 13];
92    for (i, slot) in out.iter_mut().enumerate() {
93        *slot = ((polymod >> (5 * (12 - i))) & 0x1F) as u8;
94    }
95    out
96}
97
98/// Verify a regular-code BCH checksum over the data-part-with-checksum.
99pub fn bch_verify_regular(hrp: &str, data_with_checksum: &[u8]) -> bool {
100    if data_with_checksum.len() < 13 {
101        return false;
102    }
103    let mut input = hrp_expand(hrp);
104    input.extend_from_slice(data_with_checksum);
105    polymod_run(&input) == MD_REGULAR_CONST
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111    use bitcoin::hashes::{Hash, sha256};
112
113    /// Drift-guard: `MD_REGULAR_CONST` must reproduce from its documented
114    /// NUMS rule — the top 65 bits of `SHA-256("shibbolethnums")`. Mirrors
115    /// mk-codec's `consts::tests::nums_constants_reproduce_from_domain`
116    /// (and ms-codec's `tests/bch_all_lengths.rs::ms_regular_const_is_secretshare32_packed`).
117    /// Catches accidental drift if the domain string or the constant is
118    /// edited without the other — without this, a silent edit to either would
119    /// break cross-format domain separation undetected.
120    #[test]
121    fn md_regular_const_reproduces_from_nums_domain() {
122        let digest = sha256::Hash::hash(b"shibbolethnums");
123        let bytes = digest.as_byte_array();
124        // Leading 128 bits of the 256-bit digest as a big-endian u128, then
125        // the top 65 bits (shift right by 128 - 65 = 63).
126        let hi = u128::from_be_bytes(bytes[0..16].try_into().unwrap());
127        let derived = hi >> 63;
128        assert_eq!(
129            derived, MD_REGULAR_CONST,
130            "MD_REGULAR_CONST drift from SHA-256(\"shibbolethnums\") top-65-bits",
131        );
132    }
133}
md_codec/bch.rs

md_codec/
bch.rs
