miniscript/descriptor/
checksum.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Descriptor checksum
4//!
5//! This module contains a re-implementation of the function used by Bitcoin Core to calculate the
6//! checksum of a descriptor. The checksum algorithm is specified in [BIP-380].
7//!
8//! [BIP-380]: <https://github.com/bitcoin/bips/blob/master/bip-0380.mediawiki>
9
10use core::convert::TryFrom;
11use core::fmt;
12use core::iter::FromIterator;
13
14use bech32::primitives::checksum::PackedFe32;
15use bech32::{Checksum, Fe32};
16
17pub use crate::expression::VALID_CHARS;
18use crate::prelude::*;
19use crate::Error;
20
21const CHECKSUM_LENGTH: usize = 8;
22const CODE_LENGTH: usize = 32767;
23
24/// Compute the checksum of a descriptor.
25///
26/// Note that this function does not check if the descriptor string is
27/// syntactically correct or not. This only computes the checksum.
28pub fn desc_checksum(desc: &str) -> Result<String, Error> {
29    let mut eng = Engine::new();
30    eng.input(desc)?;
31    Ok(eng.checksum())
32}
33
34/// Helper function for `FromStr` for various descriptor types.
35///
36/// Checks and verifies the checksum if it is present and returns the descriptor
37/// string without the checksum.
38pub(super) fn verify_checksum(s: &str) -> Result<&str, Error> {
39    for ch in s.as_bytes() {
40        if *ch < 20 || *ch > 127 {
41            return Err(Error::Unprintable(*ch));
42        }
43    }
44
45    let mut parts = s.splitn(2, '#');
46    let desc_str = parts.next().unwrap();
47    if let Some(checksum_str) = parts.next() {
48        let expected_sum = desc_checksum(desc_str)?;
49        if checksum_str != expected_sum {
50            return Err(Error::BadDescriptor(format!(
51                "Invalid checksum '{}', expected '{}'",
52                checksum_str, expected_sum
53            )));
54        }
55    }
56    Ok(desc_str)
57}
58
59/// An engine to compute a checksum from a string.
60pub struct Engine {
61    inner: bech32::primitives::checksum::Engine<DescriptorChecksum>,
62    cls: u64,
63    clscount: u64,
64}
65
66impl Default for Engine {
67    fn default() -> Engine { Engine::new() }
68}
69
70impl Engine {
71    /// Constructs an engine with no input.
72    pub fn new() -> Self {
73        Engine { inner: bech32::primitives::checksum::Engine::new(), cls: 0, clscount: 0 }
74    }
75
76    /// Inputs some data into the checksum engine.
77    ///
78    /// If this function returns an error, the `Engine` will be left in an indeterminate
79    /// state! It is safe to continue feeding it data but the result will not be meaningful.
80    pub fn input(&mut self, s: &str) -> Result<(), Error> {
81        for ch in s.chars() {
82            let pos = VALID_CHARS
83                .get(ch as usize)
84                .ok_or_else(|| {
85                    Error::BadDescriptor(format!("Invalid character in checksum: '{}'", ch))
86                })?
87                .ok_or_else(|| {
88                    Error::BadDescriptor(format!("Invalid character in checksum: '{}'", ch))
89                })? as u64;
90
91            let fe = Fe32::try_from(pos & 31).expect("pos is valid because of the mask");
92            self.inner.input_fe(fe);
93
94            self.cls = self.cls * 3 + (pos >> 5);
95            self.clscount += 1;
96            if self.clscount == 3 {
97                let fe = Fe32::try_from(self.cls).expect("cls is valid");
98                self.inner.input_fe(fe);
99                self.cls = 0;
100                self.clscount = 0;
101            }
102        }
103        Ok(())
104    }
105
106    /// Obtains the checksum characters of all the data thus-far fed to the
107    /// engine without allocating, to get a string use [`Self::checksum`].
108    pub fn checksum_chars(&mut self) -> [char; CHECKSUM_LENGTH] {
109        if self.clscount > 0 {
110            let fe = Fe32::try_from(self.cls).expect("cls is valid");
111            self.inner.input_fe(fe);
112        }
113        self.inner.input_target_residue();
114
115        let mut chars = [0 as char; CHECKSUM_LENGTH];
116        let mut checksum_remaining = CHECKSUM_LENGTH;
117
118        for checksum_ch in &mut chars {
119            checksum_remaining -= 1;
120            let unpacked = self.inner.residue().unpack(checksum_remaining);
121            let fe = Fe32::try_from(unpacked).expect("5 bits fits in an fe32");
122            *checksum_ch = fe.to_char();
123        }
124        chars
125    }
126
127    /// Obtains the checksum of all the data thus-far fed to the engine.
128    pub fn checksum(&mut self) -> String {
129        String::from_iter(self.checksum_chars().iter().copied())
130    }
131}
132
133/// The Output Script Descriptor checksum algorithm, defined in [BIP-380].
134///
135/// [BIP-380]: <https://github.com/bitcoin/bips/blob/master/bip-0380.mediawiki>
136#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
137enum DescriptorChecksum {}
138
139/// Generator coefficients, taken from BIP-380.
140#[rustfmt::skip]
141const GEN: [u64; 5] = [0xf5dee51989, 0xa9fdca3312, 0x1bab10e32d, 0x3706b1677a, 0x644d626ffd];
142
143impl Checksum for DescriptorChecksum {
144    type MidstateRepr = u64; // We need 40 bits (8 * 5).
145    const CHECKSUM_LENGTH: usize = CHECKSUM_LENGTH;
146    const CODE_LENGTH: usize = CODE_LENGTH;
147    const GENERATOR_SH: [u64; 5] = GEN;
148    const TARGET_RESIDUE: u64 = 1;
149}
150
151/// A wrapper around a `fmt::Formatter` which provides checksumming ability.
152pub struct Formatter<'f, 'a> {
153    fmt: &'f mut fmt::Formatter<'a>,
154    eng: Engine,
155}
156
157impl<'f, 'a> Formatter<'f, 'a> {
158    /// Contructs a new `Formatter`, wrapping a given `fmt::Formatter`.
159    pub fn new(f: &'f mut fmt::Formatter<'a>) -> Self { Formatter { fmt: f, eng: Engine::new() } }
160
161    /// Writes the checksum into the underlying `fmt::Formatter`.
162    pub fn write_checksum(&mut self) -> fmt::Result {
163        use fmt::Write;
164        self.fmt.write_char('#')?;
165        for ch in self.eng.checksum_chars().iter().copied() {
166            self.fmt.write_char(ch)?;
167        }
168        Ok(())
169    }
170
171    /// Writes the checksum into the underlying `fmt::Formatter`, unless it has "alternate" display on.
172    pub fn write_checksum_if_not_alt(&mut self) -> fmt::Result {
173        if !self.fmt.alternate() {
174            self.write_checksum()?;
175        }
176        Ok(())
177    }
178}
179
180impl<'f, 'a> fmt::Write for Formatter<'f, 'a> {
181    fn write_str(&mut self, s: &str) -> fmt::Result {
182        self.fmt.write_str(s)?;
183        self.eng.input(s).map_err(|_| fmt::Error)
184    }
185}
186
187#[cfg(test)]
188mod test {
189    use core::str;
190
191    use super::*;
192
193    macro_rules! check_expected {
194        ($desc: expr, $checksum: expr) => {
195            assert_eq!(desc_checksum($desc).unwrap(), $checksum);
196        };
197    }
198
199    #[test]
200    fn test_valid_descriptor_checksum() {
201        check_expected!(
202            "wpkh(tprv8ZgxMBicQKsPdpkqS7Eair4YxjcuuvDPNYmKX3sCniCf16tHEVrjjiSXEkFRnUH77yXc6ZcwHHcLNfjdi5qUvw3VDfgYiH5mNsj5izuiu2N/1/2/*)",
203            "tqz0nc62"
204        );
205        check_expected!(
206            "pkh(tpubD6NzVbkrYhZ4XHndKkuB8FifXm8r5FQHwrN6oZuWCz13qb93rtgKvD4PQsqC4HP4yhV3tA2fqr2RbY5mNXfM7RxXUoeABoDtsFUq2zJq6YK/44'/1'/0'/0/*)",
207            "lasegmfs"
208        );
209
210        // https://github.com/bitcoin/bitcoin/blob/7ae86b3c6845873ca96650fc69beb4ae5285c801/src/test/descriptor_tests.cpp#L352-L354
211        check_expected!(
212            "sh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))",
213            "ggrsrxfy"
214        );
215        check_expected!(
216            "sh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))",
217            "tjg09x5t"
218        );
219    }
220
221    #[test]
222    fn test_desc_checksum_invalid_character() {
223        let sparkle_heart = vec![240, 159, 146, 150];
224        let sparkle_heart = str::from_utf8(&sparkle_heart)
225            .unwrap()
226            .chars()
227            .next()
228            .unwrap();
229        let invalid_desc = format!("wpkh(tprv8ZgxMBicQKsPdpkqS7Eair4YxjcuuvDPNYmKX3sCniCf16tHEVrjjiSXEkFRnUH77yXc6ZcwHHcL{}fjdi5qUvw3VDfgYiH5mNsj5izuiu2N/1/2/*)", sparkle_heart);
230
231        assert_eq!(
232            desc_checksum(&invalid_desc).err().unwrap().to_string(),
233            format!("Invalid descriptor: Invalid character in checksum: '{}'", sparkle_heart)
234        );
235    }
236
237    #[test]
238    fn bip_380_test_vectors_checksum_and_character_set_valid() {
239        let tcs = vec![
240            "raw(deadbeef)#89f8spxm", // Valid checksum.
241            "raw(deadbeef)",          // No checksum.
242        ];
243        for tc in tcs {
244            if verify_checksum(tc).is_err() {
245                panic!("false negative: {}", tc)
246            }
247        }
248    }
249
250    #[test]
251    fn bip_380_test_vectors_checksum_and_character_set_invalid() {
252        let tcs = vec![
253            "raw(deadbeef)#",          // Missing checksum.
254            "raw(deadbeef)#89f8spxmx", // Too long checksum.
255            "raw(deadbeef)#89f8spx",   // Too short checksum.
256            "raw(dedbeef)#89f8spxm",   // Error in payload.
257            "raw(deadbeef)##9f8spxm",  // Error in checksum.
258            "raw(Ü)#00000000",         // Invalid characters in payload.
259        ];
260        for tc in tcs {
261            if verify_checksum(tc).is_ok() {
262                panic!("false positive: {}", tc)
263            }
264        }
265    }
266}
miniscript/descriptor/checksum.rs

miniscript/descriptor/
checksum.rs
