elements_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
7
8use core::fmt;
9use core::iter::FromIterator;
10
11use bitcoin_miniscript::expression::check_valid_chars;
12
13use crate::Error;
14
15const INPUT_CHARSET: &str =  "0123456789()[],'/*abcdefgh@:$%{}IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~ijklmnopqrstuvwxyzABCDEFGH`#\"\\ ";
16const CHECKSUM_CHARSET: &[u8] = b"qpzry9x8gf2tvdw0s3jn54khce6mua7l";
17
18fn poly_mod(mut c: u64, val: u64) -> u64 {
19    let c0 = c >> 35;
20
21    c = ((c & 0x7ffffffff) << 5) ^ val;
22    if c0 & 1 > 0 {
23        c ^= 0xf5dee51989
24    };
25    if c0 & 2 > 0 {
26        c ^= 0xa9fdca3312
27    };
28    if c0 & 4 > 0 {
29        c ^= 0x1bab10e32d
30    };
31    if c0 & 8 > 0 {
32        c ^= 0x3706b1677a
33    };
34    if c0 & 16 > 0 {
35        c ^= 0x644d626ffd
36    };
37
38    c
39}
40
41/// Compute the checksum of a descriptor
42/// Note that this function does not check if the
43/// descriptor string is syntactically correct or not.
44/// This only computes the checksum
45pub fn desc_checksum(desc: &str) -> Result<String, Error> {
46    let mut eng = Engine::new();
47    eng.input(desc)?;
48    Ok(eng.checksum())
49}
50
51/// Helper function for FromStr for various
52/// descriptor types. Checks and verifies the checksum
53/// if it is present and returns the descriptor string
54/// without the checksum
55pub(crate) fn verify_checksum(s: &str) -> Result<&str, Error> {
56    check_valid_chars(s)?;
57
58    let mut parts = s.splitn(2, '#');
59    let desc_str = parts.next().unwrap();
60    if let Some(checksum_str) = parts.next() {
61        let expected_sum = desc_checksum(desc_str)?;
62        if checksum_str != expected_sum {
63            return Err(Error::BadDescriptor(format!(
64                "Invalid checksum '{}', expected '{}'",
65                checksum_str, expected_sum
66            )));
67        }
68    }
69    Ok(desc_str)
70}
71
72/// An engine to compute a checksum from a string
73pub struct Engine {
74    c: u64,
75    cls: u64,
76    clscount: u64,
77}
78
79impl Default for Engine {
80    fn default() -> Self {
81        Self::new()
82    }
83}
84
85impl Engine {
86    /// Construct an engine with no input
87    pub fn new() -> Self {
88        Engine {
89            c: 1,
90            cls: 0,
91            clscount: 0,
92        }
93    }
94
95    /// Checksum some data
96    ///
97    /// If this function returns an error, the `Engine` will be left in an indeterminate
98    /// state! It is safe to continue feeding it data but the result will not be meaningful.
99    pub fn input(&mut self, s: &str) -> Result<(), Error> {
100        for ch in s.chars() {
101            let pos = INPUT_CHARSET.find(ch).ok_or_else(|| {
102                Error::BadDescriptor(format!("Invalid character in checksum: '{}'", ch))
103            })? as u64;
104            self.c = poly_mod(self.c, pos & 31);
105            self.cls = self.cls * 3 + (pos >> 5);
106            self.clscount += 1;
107            if self.clscount == 3 {
108                self.c = poly_mod(self.c, self.cls);
109                self.cls = 0;
110                self.clscount = 0;
111            }
112        }
113        Ok(())
114    }
115
116    /// Obtain the checksum of all the data thus-far fed to the engine
117    pub fn checksum_chars(&mut self) -> [char; 8] {
118        if self.clscount > 0 {
119            self.c = poly_mod(self.c, self.cls);
120        }
121        (0..8).for_each(|_| self.c = poly_mod(self.c, 0));
122        self.c ^= 1;
123
124        let mut chars = [0 as char; 8];
125        for j in 0..8 {
126            chars[j] = CHECKSUM_CHARSET[((self.c >> (5 * (7 - j))) & 31) as usize] as char;
127        }
128        chars
129    }
130
131    /// Obtain the checksum of all the data thus-far fed to the engine
132    pub fn checksum(&mut self) -> String {
133        String::from_iter(self.checksum_chars().iter().copied())
134    }
135}
136
137/// A wrapper around a `fmt::Formatter` which provides checksumming ability
138pub struct Formatter<'f, 'a> {
139    fmt: &'f mut fmt::Formatter<'a>,
140    eng: Engine,
141}
142
143impl<'f, 'a> Formatter<'f, 'a> {
144    /// Contruct a new `Formatter`, wrapping a given `fmt::Formatter`
145    pub fn new(f: &'f mut fmt::Formatter<'a>) -> Self {
146        Formatter {
147            fmt: f,
148            eng: Engine::new(),
149        }
150    }
151
152    /// Writes the checksum into the underlying `fmt::Formatter`
153    pub fn write_checksum(&mut self) -> fmt::Result {
154        use fmt::Write;
155        self.fmt.write_char('#')?;
156        for ch in self.eng.checksum_chars().iter().copied() {
157            self.fmt.write_char(ch)?;
158        }
159        Ok(())
160    }
161
162    /// Writes the checksum into the underlying `fmt::Formatter`, unless it has "alternate" display on
163    pub fn write_checksum_if_not_alt(&mut self) -> fmt::Result {
164        if !self.fmt.alternate() {
165            self.write_checksum()?;
166        }
167        Ok(())
168    }
169}
170
171impl<'f, 'a> fmt::Write for Formatter<'f, 'a> {
172    fn write_str(&mut self, s: &str) -> fmt::Result {
173        self.fmt.write_str(s)?;
174        self.eng.input(s).map_err(|_| fmt::Error)
175    }
176}
177
178#[cfg(test)]
179mod test {
180    use std::str;
181
182    use super::*;
183
184    macro_rules! check_expected {
185        ($desc: expr, $checksum: expr) => {
186            assert_eq!(desc_checksum($desc).unwrap(), $checksum);
187        };
188    }
189
190    #[test]
191    fn test_valid_descriptor_checksum() {
192        check_expected!(
193            "elwpkh(tprv8ZgxMBicQKsPdpkqS7Eair4YxjcuuvDPNYmKX3sCniCf16tHEVrjjiSXEkFRnUH77yXc6ZcwHHcLNfjdi5qUvw3VDfgYiH5mNsj5izuiu2N/1/2/*)",
194            "hkvr2vkj"
195        );
196        check_expected!(
197            "elpkh(tpubD6NzVbkrYhZ4XHndKkuB8FifXm8r5FQHwrN6oZuWCz13qb93rtgKvD4PQsqC4HP4yhV3tA2fqr2RbY5mNXfM7RxXUoeABoDtsFUq2zJq6YK/44'/1'/0'/0/*)",
198            "g7zpd3we"
199        );
200
201        // https://github.com/bitcoin/bitcoin/blob/7ae86b3c6845873ca96650fc69beb4ae5285c801/src/test/descriptor_tests.cpp#L352-L354
202        check_expected!(
203            "elsh(multi(2,[00000000/111'/222]xprvA1RpRA33e1JQ7ifknakTFpgNXPmW2YvmhqLQYMmrj4xJXXWYpDPS3xz7iAxn8L39njGVyuoseXzU6rcxFLJ8HFsTjSyQbLYnMpCqE2VbFWc,xprv9uPDJpEQgRQfDcW7BkF7eTya6RPxXeJCqCJGHuCJ4GiRVLzkTXBAJMu2qaMWPrS7AANYqdq6vcBcBUdJCVVFceUvJFjaPdGZ2y9WACViL4L/0))",
204            "9s2ngs7u"
205        );
206        check_expected!(
207            "elsh(multi(2,[00000000/111'/222]xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL,xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y/0))",
208            "uklept69"
209        );
210    }
211
212    #[test]
213    fn test_desc_checksum_invalid_character() {
214        let sparkle_heart = vec![240, 159, 146, 150];
215        let sparkle_heart = str::from_utf8(&sparkle_heart)
216            .unwrap()
217            .chars()
218            .next()
219            .unwrap();
220        let invalid_desc = format!("elwpkh(tprv8ZgxMBicQKsPdpkqS7Eair4YxjcuuvDPNYmKX3sCniCf16tHEVrjjiSXEkFRnUH77yXc6ZcwHHcL{}fjdi5qUvw3VDfgYiH5mNsj5izuiu2N/1/2/*)", sparkle_heart);
221
222        assert_eq!(
223            desc_checksum(&invalid_desc).err().unwrap().to_string(),
224            format!(
225                "Invalid descriptor: Invalid character in checksum: '{}'",
226                sparkle_heart
227            )
228        );
229    }
230}
elements_miniscript/descriptor/checksum.rs

elements_miniscript/descriptor/
checksum.rs
