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

bitcoin/util/
base58.rs
