base58ck/
lib.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Bitcoin base58 encoding and decoding.
4//!
5//! This crate can be used in a no-std environment but requires an allocator.
6
7#![no_std]
8// Experimental features we need.
9#![cfg_attr(docsrs, feature(doc_auto_cfg))]
10#![cfg_attr(bench, feature(test))]
11// Coding conventions.
12#![warn(missing_docs)]
13// Instead of littering the codebase for non-fuzzing code just globally allow.
14#![cfg_attr(fuzzing, allow(dead_code, unused_imports))]
15// Exclude lints we don't think are valuable.
16#![allow(clippy::needless_question_mark)] // https://github.com/rust-bitcoin/rust-bitcoin/pull/2134
17#![allow(clippy::manual_range_contains)] // More readable than clippy's format.
18
19#[macro_use]
20extern crate alloc;
21
22#[cfg(feature = "std")]
23extern crate std;
24
25static BASE58_CHARS: &[u8] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
26
27pub mod error;
28
29#[cfg(not(feature = "std"))]
30pub use alloc::{string::String, vec::Vec};
31use core::{fmt, iter, slice, str};
32#[cfg(feature = "std")]
33pub use std::{string::String, vec::Vec};
34
35use hashes::{sha256d, Hash};
36
37use crate::error::{IncorrectChecksumError, TooShortError};
38
39#[rustfmt::skip]                // Keep public re-exports separate.
40#[doc(inline)]
41pub use self::error::{Error, InvalidCharacterError};
42
43#[rustfmt::skip]
44static BASE58_DIGITS: [Option<u8>; 128] = [
45    None,     None,     None,     None,     None,     None,     None,     None,     // 0-7
46    None,     None,     None,     None,     None,     None,     None,     None,     // 8-15
47    None,     None,     None,     None,     None,     None,     None,     None,     // 16-23
48    None,     None,     None,     None,     None,     None,     None,     None,     // 24-31
49    None,     None,     None,     None,     None,     None,     None,     None,     // 32-39
50    None,     None,     None,     None,     None,     None,     None,     None,     // 40-47
51    None,     Some(0),  Some(1),  Some(2),  Some(3),  Some(4),  Some(5),  Some(6),  // 48-55
52    Some(7),  Some(8),  None,     None,     None,     None,     None,     None,     // 56-63
53    None,     Some(9),  Some(10), Some(11), Some(12), Some(13), Some(14), Some(15), // 64-71
54    Some(16), None,     Some(17), Some(18), Some(19), Some(20), Some(21), None,     // 72-79
55    Some(22), Some(23), Some(24), Some(25), Some(26), Some(27), Some(28), Some(29), // 80-87
56    Some(30), Some(31), Some(32), None,     None,     None,     None,     None,     // 88-95
57    None,     Some(33), Some(34), Some(35), Some(36), Some(37), Some(38), Some(39), // 96-103
58    Some(40), Some(41), Some(42), Some(43), None,     Some(44), Some(45), Some(46), // 104-111
59    Some(47), Some(48), Some(49), Some(50), Some(51), Some(52), Some(53), Some(54), // 112-119
60    Some(55), Some(56), Some(57), None,     None,     None,     None,     None,     // 120-127
61];
62
63/// Decodes a base58-encoded string into a byte vector.
64pub fn decode(data: &str) -> Result<Vec<u8>, InvalidCharacterError> {
65    // 11/15 is just over log_256(58)
66    let mut scratch = vec![0u8; 1 + data.len() * 11 / 15];
67    // Build in base 256
68    for d58 in data.bytes() {
69        // Compute "X = X * 58 + next_digit" in base 256
70        if d58 as usize >= BASE58_DIGITS.len() {
71            return Err(InvalidCharacterError { invalid: d58 });
72        }
73        let mut carry = match BASE58_DIGITS[d58 as usize] {
74            Some(d58) => d58 as u32,
75            None => {
76                return Err(InvalidCharacterError { invalid: d58 });
77            }
78        };
79        for d256 in scratch.iter_mut().rev() {
80            carry += *d256 as u32 * 58;
81            *d256 = carry as u8;
82            carry /= 256;
83        }
84        assert_eq!(carry, 0);
85    }
86
87    // Copy leading zeroes directly
88    let mut ret: Vec<u8> = data.bytes().take_while(|&x| x == BASE58_CHARS[0]).map(|_| 0).collect();
89    // Copy rest of string
90    ret.extend(scratch.into_iter().skip_while(|&x| x == 0));
91    Ok(ret)
92}
93
94/// Decodes a base58check-encoded string into a byte vector verifying the checksum.
95pub fn decode_check(data: &str) -> Result<Vec<u8>, Error> {
96    let mut ret: Vec<u8> = decode(data)?;
97    if ret.len() < 4 {
98        return Err(TooShortError { length: ret.len() }.into());
99    }
100    let check_start = ret.len() - 4;
101
102    let hash_check =
103        sha256d::Hash::hash(&ret[..check_start])[..4].try_into().expect("4 byte slice");
104    let data_check = ret[check_start..].try_into().expect("4 byte slice");
105
106    let expected = u32::from_le_bytes(hash_check);
107    let actual = u32::from_le_bytes(data_check);
108
109    if actual != expected {
110        return Err(IncorrectChecksumError { incorrect: actual, expected }.into());
111    }
112
113    ret.truncate(check_start);
114    Ok(ret)
115}
116
117/// Encodes `data` as a base58 string (see also `base58::encode_check()`).
118pub fn encode(data: &[u8]) -> String { encode_iter(data.iter().cloned()) }
119
120/// Encodes `data` as a base58 string including the checksum.
121///
122/// The checksum is the first four bytes of the sha256d of the data, concatenated onto the end.
123pub fn encode_check(data: &[u8]) -> String {
124    let checksum = sha256d::Hash::hash(data);
125    encode_iter(data.iter().cloned().chain(checksum[0..4].iter().cloned()))
126}
127
128/// Encodes a slice as base58, including the checksum, into a formatter.
129///
130/// The checksum is the first four bytes of the sha256d of the data, concatenated onto the end.
131pub fn encode_check_to_fmt(fmt: &mut fmt::Formatter, data: &[u8]) -> fmt::Result {
132    let checksum = sha256d::Hash::hash(data);
133    let iter = data.iter().cloned().chain(checksum[0..4].iter().cloned());
134    format_iter(fmt, iter)
135}
136
137fn encode_iter<I>(data: I) -> String
138where
139    I: Iterator<Item = u8> + Clone,
140{
141    let mut ret = String::new();
142    format_iter(&mut ret, data).expect("writing into string shouldn't fail");
143    ret
144}
145
146fn format_iter<I, W>(writer: &mut W, data: I) -> Result<(), fmt::Error>
147where
148    I: Iterator<Item = u8> + Clone,
149    W: fmt::Write,
150{
151    let mut ret = SmallVec::new();
152
153    let mut leading_zero_count = 0;
154    let mut leading_zeroes = true;
155    // Build string in little endian with 0-58 in place of characters...
156    for d256 in data {
157        let mut carry = d256 as usize;
158        if leading_zeroes && carry == 0 {
159            leading_zero_count += 1;
160        } else {
161            leading_zeroes = false;
162        }
163
164        for ch in ret.iter_mut() {
165            let new_ch = *ch as usize * 256 + carry;
166            *ch = (new_ch % 58) as u8;
167            carry = new_ch / 58;
168        }
169        while carry > 0 {
170            ret.push((carry % 58) as u8);
171            carry /= 58;
172        }
173    }
174
175    // ... then reverse it and convert to chars
176    for _ in 0..leading_zero_count {
177        ret.push(0);
178    }
179
180    for ch in ret.iter().rev() {
181        writer.write_char(BASE58_CHARS[*ch as usize] as char)?;
182    }
183
184    Ok(())
185}
186
187/// Vector-like object that holds the first 100 elements on the stack. If more space is needed it
188/// will be allocated on the heap.
189struct SmallVec<T> {
190    len: usize,
191    stack: [T; 100],
192    heap: Vec<T>,
193}
194
195impl<T: Default + Copy> SmallVec<T> {
196    fn new() -> SmallVec<T> { SmallVec { len: 0, stack: [T::default(); 100], heap: Vec::new() } }
197
198    fn push(&mut self, val: T) {
199        if self.len < 100 {
200            self.stack[self.len] = val;
201            self.len += 1;
202        } else {
203            self.heap.push(val);
204        }
205    }
206
207    fn iter(&self) -> iter::Chain<slice::Iter<T>, slice::Iter<T>> {
208        // If len<100 then we just append an empty vec
209        self.stack[0..self.len].iter().chain(self.heap.iter())
210    }
211
212    fn iter_mut(&mut self) -> iter::Chain<slice::IterMut<T>, slice::IterMut<T>> {
213        // If len<100 then we just append an empty vec
214        self.stack[0..self.len].iter_mut().chain(self.heap.iter_mut())
215    }
216}
217
218#[cfg(test)]
219mod tests {
220    use hex::test_hex_unwrap as hex;
221
222    use super::*;
223
224    #[test]
225    fn test_base58_encode() {
226        // Basics
227        assert_eq!(&encode(&[0][..]), "1");
228        assert_eq!(&encode(&[1][..]), "2");
229        assert_eq!(&encode(&[58][..]), "21");
230        assert_eq!(&encode(&[13, 36][..]), "211");
231
232        // Leading zeroes
233        assert_eq!(&encode(&[0, 13, 36][..]), "1211");
234        assert_eq!(&encode(&[0, 0, 0, 0, 13, 36][..]), "1111211");
235
236        // Long input (>100 bytes => has to use heap)
237        let res = encode(
238            "BitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBit\
239        coinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoin"
240                .as_bytes(),
241        );
242        let exp =
243            "ZqC5ZdfpZRi7fjA8hbhX5pEE96MdH9hEaC1YouxscPtbJF16qVWksHWR4wwvx7MotFcs2ChbJqK8KJ9X\
244        wZznwWn1JFDhhTmGo9v6GjAVikzCsBWZehu7bm22xL8b5zBR5AsBygYRwbFJsNwNkjpyFuDKwmsUTKvkULCvucPJrN5\
245        QUdxpGakhqkZFL7RU4yT";
246        assert_eq!(&res, exp);
247
248        // Addresses
249        let addr = hex!("00f8917303bfa8ef24f292e8fa1419b20460ba064d");
250        assert_eq!(&encode_check(&addr[..]), "1PfJpZsjreyVrqeoAfabrRwwjQyoSQMmHH");
251    }
252
253    #[test]
254    fn test_base58_decode() {
255        // Basics
256        assert_eq!(decode("1").ok(), Some(vec![0u8]));
257        assert_eq!(decode("2").ok(), Some(vec![1u8]));
258        assert_eq!(decode("21").ok(), Some(vec![58u8]));
259        assert_eq!(decode("211").ok(), Some(vec![13u8, 36]));
260
261        // Leading zeroes
262        assert_eq!(decode("1211").ok(), Some(vec![0u8, 13, 36]));
263        assert_eq!(decode("111211").ok(), Some(vec![0u8, 0, 0, 13, 36]));
264
265        // Addresses
266        assert_eq!(
267            decode_check("1PfJpZsjreyVrqeoAfabrRwwjQyoSQMmHH").ok(),
268            Some(hex!("00f8917303bfa8ef24f292e8fa1419b20460ba064d"))
269        );
270        // Non Base58 char.
271        assert_eq!(decode("¢").unwrap_err(), InvalidCharacterError { invalid: 194 });
272    }
273
274    #[test]
275    fn test_base58_roundtrip() {
276        let s = "xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs";
277        let v: Vec<u8> = decode_check(s).unwrap();
278        assert_eq!(encode_check(&v[..]), s);
279        assert_eq!(decode_check(&encode_check(&v[..])).ok(), Some(v));
280
281        // Check that empty slice passes roundtrip.
282        assert_eq!(decode_check(&encode_check(&[])), Ok(vec![]));
283        // Check that `len > 4` is enforced.
284        assert_eq!(decode_check(&encode(&[1, 2, 3])), Err(TooShortError { length: 3 }.into()));
285    }
286}
base58ck/lib.rs

base58ck/
lib.rs
