bitcoin/util/
base58.rs

1// Rust Bitcoin Library
2// Written in 2014 by
3//   Andrew Poelstra <apoelstra@wpsoftware.net>
4//
5// To the extent possible under law, the author(s) have dedicated all
6// copyright and related and neighboring rights to this software to
7// the public domain worldwide. This software is distributed without
8// any warranty.
9//
10// You should have received a copy of the CC0 Public Domain Dedication
11// along with this software.
12// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13//
14
15//! Base58 encoder and decoder
16
17use std::{error, fmt, str, slice, iter};
18
19use byteorder::{ByteOrder, LittleEndian};
20
21use bitcoin_hashes::{sha256d, Hash};
22
23/// An error that might occur during base58 decoding
24#[derive(Debug, PartialEq, Eq, Clone)]
25pub enum Error {
26    /// Invalid character encountered
27    BadByte(u8),
28    /// Checksum was not correct (expected, actual)
29    BadChecksum(u32, u32),
30    /// The length (in bytes) of the object was not correct
31    /// Note that if the length is excessively long the provided length may be
32    /// an estimate (and the checksum step may be skipped).
33    InvalidLength(usize),
34    /// Version byte(s) were not recognized
35    InvalidVersion(Vec<u8>),
36    /// Checked data was less than 4 bytes
37    TooShort(usize),
38    /// Any other error
39    Other(String)
40}
41
42impl fmt::Display for Error {
43    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
44        match *self {
45            Error::BadByte(b) => write!(f, "invalid base58 character 0x{:x}", b),
46            Error::BadChecksum(exp, actual) => write!(f, "base58ck checksum 0x{:x} does not match expected 0x{:x}", actual, exp),
47            Error::InvalidLength(ell) => write!(f, "length {} invalid for this base58 type", ell),
48            Error::InvalidVersion(ref v) => write!(f, "version {:?} invalid for this base58 type", v),
49            Error::TooShort(_) => write!(f, "base58ck data not even long enough for a checksum"),
50            Error::Other(ref s) => f.write_str(s)
51        }
52    }
53}
54
55impl error::Error for Error {
56    fn cause(&self) -> Option<&error::Error> { None }
57    fn description(&self) -> &'static str {
58        match *self {
59            Error::BadByte(_) => "invalid b58 character",
60            Error::BadChecksum(_, _) => "invalid b58ck checksum",
61            Error::InvalidLength(_) => "invalid length for b58 type",
62            Error::InvalidVersion(_) => "invalid version for b58 type",
63            Error::TooShort(_) => "b58ck data less than 4 bytes",
64            Error::Other(_) => "unknown b58 error"
65        }
66    }
67}
68
69/// Vector-like object that holds the first 100 elements on the stack. If more space is needed it
70/// will be allocated on the heap.
71struct SmallVec<T> {
72    len: usize,
73    stack: [T; 100],
74    heap: Vec<T>,
75}
76
77impl<T: Default + Copy> SmallVec<T> {
78    pub fn new() -> SmallVec<T> {
79        SmallVec {
80            len: 0,
81            stack: [T::default(); 100],
82            heap: Vec::new(),
83        }
84    }
85
86    pub fn push(&mut self, val: T) {
87        if self.len < 100 {
88            self.stack[self.len] = val;
89            self.len += 1;
90        } else {
91            self.heap.push(val);
92        }
93    }
94
95    pub fn iter(&self) -> iter::Chain<slice::Iter<T>, slice::Iter<T>> {
96        // If len<100 then we just append an empty vec
97        self.stack[0..self.len].iter().chain(self.heap.iter())
98    }
99
100    pub fn iter_mut(&mut self) -> iter::Chain<slice::IterMut<T>, slice::IterMut<T>> {
101        // If len<100 then we just append an empty vec
102        self.stack[0..self.len].iter_mut().chain(self.heap.iter_mut())
103    }
104}
105
106static BASE58_CHARS: &'static [u8] = b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
107
108static BASE58_DIGITS: [Option<u8>; 128] = [
109    None,     None,     None,     None,     None,     None,     None,     None,     // 0-7
110    None,     None,     None,     None,     None,     None,     None,     None,     // 8-15
111    None,     None,     None,     None,     None,     None,     None,     None,     // 16-23
112    None,     None,     None,     None,     None,     None,     None,     None,     // 24-31
113    None,     None,     None,     None,     None,     None,     None,     None,     // 32-39
114    None,     None,     None,     None,     None,     None,     None,     None,     // 40-47
115    None,     Some(0),  Some(1),  Some(2),  Some(3),  Some(4),  Some(5),  Some(6),  // 48-55
116    Some(7),  Some(8),  None,     None,     None,     None,     None,     None,     // 56-63
117    None,     Some(9),  Some(10), Some(11), Some(12), Some(13), Some(14), Some(15), // 64-71
118    Some(16), None,     Some(17), Some(18), Some(19), Some(20), Some(21), None,     // 72-79
119    Some(22), Some(23), Some(24), Some(25), Some(26), Some(27), Some(28), Some(29), // 80-87
120    Some(30), Some(31), Some(32), None,     None,     None,     None,     None,     // 88-95
121    None,     Some(33), Some(34), Some(35), Some(36), Some(37), Some(38), Some(39), // 96-103
122    Some(40), Some(41), Some(42), Some(43), None,     Some(44), Some(45), Some(46), // 104-111
123    Some(47), Some(48), Some(49), Some(50), Some(51), Some(52), Some(53), Some(54), // 112-119
124    Some(55), Some(56), Some(57), None,     None,     None,     None,     None,     // 120-127
125];
126
127/// Decode base58-encoded string into a byte vector
128pub fn from(data: &str) -> Result<Vec<u8>, Error> {
129    // 11/15 is just over log_256(58)
130    let mut scratch = vec![0u8; 1 + data.len() * 11 / 15];
131    // Build in base 256
132    for d58 in data.bytes() {
133        // Compute "X = X * 58 + next_digit" in base 256
134        if d58 as usize > BASE58_DIGITS.len() {
135            return Err(Error::BadByte(d58));
136        }
137        let mut carry = match BASE58_DIGITS[d58 as usize] {
138            Some(d58) => d58 as u32,
139            None => { return Err(Error::BadByte(d58)); }
140        };
141        for d256 in scratch.iter_mut().rev() {
142            carry += *d256 as u32 * 58;
143            *d256 = carry as u8;
144            carry /= 256;
145        }
146        assert_eq!(carry, 0);
147    }
148
149    // Copy leading zeroes directly
150    let mut ret: Vec<u8> = data.bytes().take_while(|&x| x == BASE58_CHARS[0])
151                                       .map(|_| 0)
152                                       .collect();
153    // Copy rest of string
154    ret.extend(scratch.into_iter().skip_while(|&x| x == 0));
155    Ok(ret)
156}
157
158/// Decode a base58check-encoded string
159pub fn from_check(data: &str) -> Result<Vec<u8>, Error> {
160    let mut ret: Vec<u8> = from(data)?;
161    if ret.len() < 4 {
162        return Err(Error::TooShort(ret.len()));
163    }
164    let ck_start = ret.len() - 4;
165    let expected = LittleEndian::read_u32(&sha256d::Hash::hash(&ret[..ck_start])[..4]);
166    let actual = LittleEndian::read_u32(&ret[ck_start..(ck_start + 4)]);
167    if expected != actual {
168        return Err(Error::BadChecksum(expected, actual));
169    }
170
171    ret.truncate(ck_start);
172    Ok(ret)
173}
174
175fn format_iter<I, W>(writer: &mut W, data: I) -> Result<(), fmt::Error>
176where
177    I: Iterator<Item = u8> + Clone,
178    W: fmt::Write
179{
180    let mut ret = SmallVec::new();
181
182    let mut leading_zero_count = 0;
183    let mut leading_zeroes = true;
184    // Build string in little endian with 0-58 in place of characters...
185    for d256 in data {
186        let mut carry = d256 as usize;
187        if leading_zeroes && carry == 0 {
188            leading_zero_count += 1;
189        } else {
190            leading_zeroes = false;
191        }
192
193        for ch in ret.iter_mut() {
194            let new_ch = *ch as usize * 256 + carry;
195            *ch = (new_ch % 58) as u8;
196            carry = new_ch / 58;
197        }
198        while carry > 0 {
199            ret.push((carry % 58) as u8);
200            carry /= 58;
201        }
202    }
203
204    // ... then reverse it and convert to chars
205    for _ in 0..leading_zero_count {
206        ret.push(0);
207    }
208
209    for ch in ret.iter().rev() {
210        writer.write_char(BASE58_CHARS[*ch as usize] as char)?;
211    }
212
213    Ok(())
214}
215
216fn encode_iter<I>(data: I) -> String
217where
218    I: Iterator<Item = u8> + Clone,
219{
220    let mut ret = String::new();
221    format_iter(&mut ret, data).expect("writing into string shouldn't fail");
222    ret
223}
224
225
226/// Directly encode a slice as base58
227pub fn encode_slice(data: &[u8]) -> String {
228    encode_iter(data.iter().cloned())
229}
230
231/// Obtain a string with the base58check encoding of a slice
232/// (Tack the first 4 256-digits of the object's Bitcoin hash onto the end.)
233pub fn check_encode_slice(data: &[u8]) -> String {
234    let checksum = sha256d::Hash::hash(&data);
235    encode_iter(
236        data.iter()
237            .cloned()
238            .chain(checksum[0..4].iter().cloned())
239    )
240}
241
242/// Obtain a string with the base58check encoding of a slice
243/// (Tack the first 4 256-digits of the object's Bitcoin hash onto the end.)
244pub fn check_encode_slice_to_fmt(fmt: &mut fmt::Formatter, data: &[u8]) -> fmt::Result {
245    let checksum = sha256d::Hash::hash(&data);
246    let iter = data.iter()
247        .cloned()
248        .chain(checksum[0..4].iter().cloned());
249    format_iter(fmt, iter)
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255    use hex::decode as hex_decode;
256
257    #[test]
258    fn test_base58_encode() {
259        // Basics
260        assert_eq!(&encode_slice(&[0][..]), "1");
261        assert_eq!(&encode_slice(&[1][..]), "2");
262        assert_eq!(&encode_slice(&[58][..]), "21");
263        assert_eq!(&encode_slice(&[13, 36][..]), "211");
264
265        // Leading zeroes
266        assert_eq!(&encode_slice(&[0, 13, 36][..]), "1211");
267        assert_eq!(&encode_slice(&[0, 0, 0, 0, 13, 36][..]), "1111211");
268
269        // Long input (>100 bytes => has to use heap)
270        let res = encode_slice(&"BitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBit\
271        coinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoinBitcoin".as_bytes());
272        let exp = "ZqC5ZdfpZRi7fjA8hbhX5pEE96MdH9hEaC1YouxscPtbJF16qVWksHWR4wwvx7MotFcs2ChbJqK8KJ9X\
273        wZznwWn1JFDhhTmGo9v6GjAVikzCsBWZehu7bm22xL8b5zBR5AsBygYRwbFJsNwNkjpyFuDKwmsUTKvkULCvucPJrN5\
274        QUdxpGakhqkZFL7RU4yT";
275        assert_eq!(&res, exp);
276
277        // Addresses
278        let addr = hex_decode("00f8917303bfa8ef24f292e8fa1419b20460ba064d").unwrap();
279        assert_eq!(&check_encode_slice(&addr[..]), "1PfJpZsjreyVrqeoAfabrRwwjQyoSQMmHH");
280      }
281
282      #[test]
283      fn test_base58_decode() {
284        // Basics
285        assert_eq!(from("1").ok(), Some(vec![0u8]));
286        assert_eq!(from("2").ok(), Some(vec![1u8]));
287        assert_eq!(from("21").ok(), Some(vec![58u8]));
288        assert_eq!(from("211").ok(), Some(vec![13u8, 36]));
289
290        // Leading zeroes
291        assert_eq!(from("1211").ok(), Some(vec![0u8, 13, 36]));
292        assert_eq!(from("111211").ok(), Some(vec![0u8, 0, 0, 13, 36]));
293
294        // Addresses
295        assert_eq!(from_check("1PfJpZsjreyVrqeoAfabrRwwjQyoSQMmHH").ok(),
296                   Some(hex_decode("00f8917303bfa8ef24f292e8fa1419b20460ba064d").unwrap()))
297    }
298
299    #[test]
300    fn test_base58_roundtrip() {
301        let s = "xprv9wTYmMFdV23N2TdNG573QoEsfRrWKQgWeibmLntzniatZvR9BmLnvSxqu53Kw1UmYPxLgboyZQaXwTCg8MSY3H2EU4pWcQDnRnrVA1xe8fs";
302        let v: Vec<u8> = from_check(s).unwrap();
303        assert_eq!(check_encode_slice(&v[..]), s);
304        assert_eq!(from_check(&check_encode_slice(&v[..])).ok(), Some(v));
305    }
306}
307
bitcoin/util/base58.rs

bitcoin/util/
base58.rs
