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// NB: This crate is empty if `alloc` is not enabled.
8#![cfg(feature = "alloc")]
9#![no_std]
10// Experimental features we need.
11#![cfg_attr(bench, feature(test))]
12// Coding conventions.
13#![warn(missing_docs)]
14#![warn(deprecated_in_future)]
15#![doc(test(attr(warn(unused))))]
16// Instead of littering the codebase for non-fuzzing and bench code just globally allow.
17#![cfg_attr(fuzzing, allow(dead_code, unused_imports))]
18#![cfg_attr(bench, allow(dead_code, unused_imports))]
19// Exclude lints we don't think are valuable.
20#![allow(clippy::incompatible_msrv)] // Has FPs and we're testing it which is more reliable anyway.
21
22extern crate alloc;
23
24#[cfg(bench)]
25extern crate test;
26
27#[cfg(feature = "std")]
28extern crate std;
29
30static BASE58_CHARS: &[u8] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
31
32pub mod error;
33
34#[cfg(not(feature = "std"))]
35pub use alloc::{string::String, vec::Vec};
36use core::fmt;
37#[cfg(feature = "std")]
38pub use std::{string::String, vec::Vec};
39
40use hashes::sha256d;
41use internals::array::ArrayExt;
42use internals::array_vec::ArrayVec;
43#[allow(unused)] // MSRV polyfill
44use internals::slice::SliceExt;
45
46use crate::error::{IncorrectChecksumError, TooShortError};
47
48#[rustfmt::skip]                // Keep public re-exports separate.
49#[doc(inline)]
50pub use self::error::{Error, InvalidCharacterError};
51
52#[rustfmt::skip]
53static BASE58_DIGITS: [Option<u8>; 128] = [
54    None,     None,     None,     None,     None,     None,     None,     None,     // 0-7
55    None,     None,     None,     None,     None,     None,     None,     None,     // 8-15
56    None,     None,     None,     None,     None,     None,     None,     None,     // 16-23
57    None,     None,     None,     None,     None,     None,     None,     None,     // 24-31
58    None,     None,     None,     None,     None,     None,     None,     None,     // 32-39
59    None,     None,     None,     None,     None,     None,     None,     None,     // 40-47
60    None,     Some(0),  Some(1),  Some(2),  Some(3),  Some(4),  Some(5),  Some(6),  // 48-55
61    Some(7),  Some(8),  None,     None,     None,     None,     None,     None,     // 56-63
62    None,     Some(9),  Some(10), Some(11), Some(12), Some(13), Some(14), Some(15), // 64-71
63    Some(16), None,     Some(17), Some(18), Some(19), Some(20), Some(21), None,     // 72-79
64    Some(22), Some(23), Some(24), Some(25), Some(26), Some(27), Some(28), Some(29), // 80-87
65    Some(30), Some(31), Some(32), None,     None,     None,     None,     None,     // 88-95
66    None,     Some(33), Some(34), Some(35), Some(36), Some(37), Some(38), Some(39), // 96-103
67    Some(40), Some(41), Some(42), Some(43), None,     Some(44), Some(45), Some(46), // 104-111
68    Some(47), Some(48), Some(49), Some(50), Some(51), Some(52), Some(53), Some(54), // 112-119
69    Some(55), Some(56), Some(57), None,     None,     None,     None,     None,     // 120-127
70];
71
72/// Decodes a base58-encoded string into a byte vector.
73///
74/// # Errors
75///
76/// Returns an error if the input contains an invalid base58 character (not in the base58 alphabet).
77#[allow(clippy::missing_panics_doc)] // Internal assertion, not user-controllable.
78pub fn decode(data: &str) -> Result<Vec<u8>, InvalidCharacterError> {
79    // 11/15 is just over log_256(58)
80    let mut scratch = Vec::with_capacity(1 + data.len() * 11 / 15);
81    // Build in base 256
82    for d58 in data.bytes() {
83        // Compute "X = X * 58 + next_digit" in base 256
84        if usize::from(d58) >= BASE58_DIGITS.len() {
85            return Err(InvalidCharacterError::new(d58));
86        }
87        let mut carry = match BASE58_DIGITS[usize::from(d58)] {
88            Some(d58) => u32::from(d58),
89            None => {
90                return Err(InvalidCharacterError::new(d58));
91            }
92        };
93        if scratch.is_empty() {
94            for _ in 0..scratch.capacity() {
95                scratch.push(carry as u8);
96                carry /= 256;
97            }
98        } else {
99            for d256 in &mut scratch {
100                carry += u32::from(*d256) * 58;
101                *d256 = carry as u8; // cast loses data intentionally
102                carry /= 256;
103            }
104        }
105        assert_eq!(carry, 0);
106    }
107
108    // Copy leading zeroes directly
109    let mut ret: Vec<u8> = data.bytes().take_while(|&x| x == BASE58_CHARS[0]).map(|_| 0).collect();
110    // Copy rest of string
111    ret.extend(scratch.into_iter().rev().skip_while(|&x| x == 0));
112    Ok(ret)
113}
114
115/// Decodes a base58check-encoded string into a byte vector verifying the checksum.
116///
117/// # Errors
118///
119/// * The input contains an invalid base58 character.
120/// * The decoded data is less than 4 bytes (too short for checksum verification).
121/// * The checksum does not match the expected value.
122pub fn decode_check(data: &str) -> Result<Vec<u8>, Error> {
123    let mut ret: Vec<u8> = decode(data)?;
124    let (remaining, &data_check) =
125        ret.split_last_chunk::<4>().ok_or(TooShortError { length: ret.len() })?;
126
127    let hash_check = *sha256d::Hash::hash(remaining).as_byte_array().sub_array::<0, 4>();
128
129    let expected = u32::from_le_bytes(hash_check);
130    let actual = u32::from_le_bytes(data_check);
131
132    if actual != expected {
133        return Err(IncorrectChecksumError { incorrect: actual, expected }.into());
134    }
135
136    ret.truncate(remaining.len());
137    Ok(ret)
138}
139
140const SHORT_OPT_BUFFER_LEN: usize = 128;
141
142/// Encodes `data` as a base58 string (see also `base58::encode_check()`).
143#[allow(clippy::missing_panics_doc)] // fmt::Write returns Result but String is infallible.
144pub fn encode(data: &[u8]) -> String {
145    let reserve_len = encoded_reserve_len(data.len());
146    let mut res = String::with_capacity(reserve_len);
147    if reserve_len <= SHORT_OPT_BUFFER_LEN {
148        format_iter(
149            &mut res,
150            data.iter().copied(),
151            &mut ArrayVec::<u8, SHORT_OPT_BUFFER_LEN>::new(),
152        )
153    } else {
154        format_iter(&mut res, data.iter().copied(), &mut Vec::with_capacity(reserve_len))
155    }
156    .expect("string doesn't error");
157    res
158}
159
160/// Encodes `data` as a base58 string including the checksum.
161///
162/// The checksum is the first four bytes of the sha256d of the data, concatenated onto the end.
163#[allow(clippy::missing_panics_doc)] // fmt::Write returns Result but String is infallible.
164pub fn encode_check(data: &[u8]) -> String {
165    let mut res = String::with_capacity(encoded_check_reserve_len(data.len()));
166    encode_check_to_writer(&mut res, data).expect("string doesn't fail");
167    res
168}
169
170/// Encodes a slice as base58, including the checksum, into a formatter.
171///
172/// The checksum is the first four bytes of the sha256d of the data, concatenated onto the end.
173///
174/// # Errors
175///
176/// Returns an error if the formatter fails to write the encoded string.
177pub fn encode_check_to_fmt(fmt: &mut fmt::Formatter, data: &[u8]) -> fmt::Result {
178    encode_check_to_writer(fmt, data)
179}
180
181fn encode_check_to_writer(fmt: &mut impl fmt::Write, data: &[u8]) -> fmt::Result {
182    let checksum = sha256d::Hash::hash(data);
183    let iter = data.iter().copied().chain(checksum.as_byte_array()[0..4].iter().copied());
184    let reserve_len = encoded_check_reserve_len(data.len());
185    if reserve_len <= SHORT_OPT_BUFFER_LEN {
186        format_iter(fmt, iter, &mut ArrayVec::<u8, SHORT_OPT_BUFFER_LEN>::new())
187    } else {
188        format_iter(fmt, iter, &mut Vec::with_capacity(reserve_len))
189    }
190}
191
192/// Returns the length to reserve when encoding base58 without checksum
193const fn encoded_reserve_len(unencoded_len: usize) -> usize {
194    // log2(256) / log2(58) ~ 1.37 = 137 / 100
195    unencoded_len * 137 / 100
196}
197
198/// Returns the length to reserve when encoding base58 with checksum
199const fn encoded_check_reserve_len(unencoded_len: usize) -> usize {
200    encoded_reserve_len(unencoded_len + 4)
201}
202
203trait Buffer: Sized {
204    fn push(&mut self, val: u8);
205    fn slice(&self) -> &[u8];
206    fn slice_mut(&mut self) -> &mut [u8];
207}
208
209impl Buffer for Vec<u8> {
210    fn push(&mut self, val: u8) { Self::push(self, val) }
211
212    fn slice(&self) -> &[u8] { self }
213
214    fn slice_mut(&mut self) -> &mut [u8] { self }
215}
216
217impl<const N: usize> Buffer for ArrayVec<u8, N> {
218    fn push(&mut self, val: u8) { Self::push(self, val) }
219
220    fn slice(&self) -> &[u8] { self.as_slice() }
221
222    fn slice_mut(&mut self) -> &mut [u8] { self.as_mut_slice() }
223}
224
225fn format_iter<I, W>(writer: &mut W, data: I, buf: &mut impl Buffer) -> Result<(), fmt::Error>
226where
227    I: Iterator<Item = u8> + Clone,
228    W: fmt::Write,
229{
230    let mut leading_zero_count = 0;
231    let mut leading_zeroes = true;
232    // Build string in little endian with 0-58 in place of characters...
233    for d256 in data {
234        let mut carry = u32::from(d256);
235        if leading_zeroes && carry == 0 {
236            leading_zero_count += 1;
237        } else {
238            leading_zeroes = false;
239        }
240
241        for ch in buf.slice_mut() {
242            let new_ch = u32::from(*ch) * 256 + carry;
243            *ch = (new_ch % 58) as u8; // cast loses data intentionally
244            carry = new_ch / 58;
245        }
246
247        while carry > 0 {
248            buf.push((carry % 58) as u8); // cast loses data intentionally
249            carry /= 58;
250        }
251    }
252
253    // ... then reverse it and convert to chars
254    for _ in 0..leading_zero_count {
255        buf.push(0);
256    }
257
258    for ch in buf.slice().iter().rev() {
259        writer.write_char(char::from(BASE58_CHARS[usize::from(*ch)]))?;
260    }
261
262    Ok(())
263}
264
265#[cfg(test)]
266mod tests {
267    use alloc::vec;
268
269    use hex_lit::hex;
270
271    use super::*;
272
273    #[test]
274    fn base58_encode() {
275        // Basics
276        assert_eq!(&encode(&[0][..]), "1");
277        assert_eq!(&encode(&[1][..]), "2");
278        assert_eq!(&encode(&[58][..]), "21");
279        assert_eq!(&encode(&[13, 36][..]), "211");
280
281        // Leading zeroes
282        assert_eq!(&encode(&[0, 13, 36][..]), "1211");
283        assert_eq!(&encode(&[0, 0, 0, 0, 13, 36][..]), "1111211");
284
285        // Long input (>128 bytes => has to use heap)
286        let res = encode(
287            "BitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBit\
288        coinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoin"
289                .as_bytes(),
290        );
291        let exp =
292            "ZqC5ZdfpZRi7fjA8hbhX5pEE96MdH9hEaC1YouxscPtbJF16qVWksHWR4wwvx7MotFcs2ChbJqK8KJ9X\
293        wZznwWn1JFDhhTmGo9v6GjAVikzCsBWZehu7bm22xL8b5zBR5AsBygYRwbFJsNwNkjpyFuDKwmsUTKvkULCvucPJrN5\
294        QUdxpGakhqkZFL7RU4yT";
295        assert_eq!(&res, exp);
296
297        // Addresses
298        let addr = hex!("00f8917303bfa8ef24f292e8fa1419b20460ba064d");
299        assert_eq!(&encode_check(&addr[..]), "1PfJpZsjreyVrqeoAfabrRwwjQyoSQMmHH");
300    }
301
302    #[test]
303    fn base58_decode() {
304        // Basics
305        assert_eq!(decode("1").ok(), Some(vec![0u8]));
306        assert_eq!(decode("2").ok(), Some(vec![1u8]));
307        assert_eq!(decode("21").ok(), Some(vec![58u8]));
308        assert_eq!(decode("211").ok(), Some(vec![13u8, 36]));
309
310        // Leading zeroes
311        assert_eq!(decode("1211").ok(), Some(vec![0u8, 13, 36]));
312        assert_eq!(decode("111211").ok(), Some(vec![0u8, 0, 0, 13, 36]));
313
314        // Addresses
315        assert_eq!(
316            decode_check("1PfJpZsjreyVrqeoAfabrRwwjQyoSQMmHH").ok().unwrap().as_slice(),
317            hex!("00f8917303bfa8ef24f292e8fa1419b20460ba064d")
318        );
319        // Non Base58 char.
320        assert_eq!(decode("¢").unwrap_err(), InvalidCharacterError::new(194));
321    }
322
323    #[test]
324    fn base58_roundtrip() {
325        let s = "xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs";
326        let v: Vec<u8> = decode_check(s).unwrap();
327        assert_eq!(encode_check(&v[..]), s);
328        assert_eq!(decode_check(&encode_check(&v[..])).ok(), Some(v));
329
330        // Check that empty slice passes roundtrip.
331        assert_eq!(decode_check(&encode_check(&[])), Ok(vec![]));
332        // Check that `len > 4` is enforced.
333        assert_eq!(decode_check(&encode(&[1, 2, 3])), Err(TooShortError { length: 3 }.into()));
334    }
335}
336
337#[cfg(bench)]
338mod benches {
339    use test::{black_box, Bencher};
340
341    #[bench]
342    pub fn bench_encode_check_50(bh: &mut Bencher) {
343        let data: alloc::vec::Vec<_> = (0u8..50).collect();
344
345        bh.iter(|| {
346            let r = super::encode_check(&data);
347            black_box(&r);
348        });
349    }
350
351    #[bench]
352    pub fn bench_encode_check_xpub(bh: &mut Bencher) {
353        let data: alloc::vec::Vec<_> = (0u8..78).collect(); // length of xpub
354
355        bh.iter(|| {
356            let r = super::encode_check(&data);
357            black_box(&r);
358        });
359    }
360}
base58ck/lib.rs

base58ck/
lib.rs
