src/base58.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2012 The Bitcoin Developers
   3 // Distributed under the MIT/X11 software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6
   7 //
   8 // Why base-58 instead of standard base-64 encoding?
   9 // - Don't want 0OIl characters that look the same in some fonts and
  10 //      could be used to create visually identical looking account numbers.
  11 // - A string with non-alphanumeric characters is not as easily accepted as an account number.
  12 // - E-mail usually won't line-break if there's no punctuation to break at.
  13 // - Double-clicking selects the whole number as one word if it's all alphanumeric.
  14 //
  15
  16 #include <string>
  17 #include <vector>
  18 #include "key.h"
  19 #include "script.h"
  20 #include "base58.h"
  21
  22 static const std::array<char, 58> digits = {
  23     '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F',
  24     'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W',
  25     'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'm',
  26     'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
  27 };
  28
  29 static const std::array<signed char, 128> characterMap = {
  30         -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  31         -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  32         -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
  33         -1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,-1,-1,-1,-1,
  34         -1, 9,10,11,12,13,14,15,16,-1,17,18,19,20,21,-1,
  35         22,23,24,25,26,27,28,29,30,31,32,-1,-1,-1,-1,-1,
  36         -1,33,34,35,36,37,38,39,40,41,42,43,-1,44,45,46,
  37         47,48,49,50,51,52,53,54,55,56,57,-1,-1,-1,-1,-1,
  38 };
  39
  40 // Encode a byte sequence as a base58-encoded string
  41 std::string EncodeBase58(const unsigned char* begin, const unsigned char* end)
  42 {
  43     // Skip & count leading zeroes.
  44     int zeroes = 0;
  45     int length = 0;
  46     while (begin != end && *begin == 0) {
  47         begin += 1;
  48         zeroes += 1;
  49     }
  50
  51     // Allocate enough space in big-endian base58 representation.
  52     auto base58Size = (end - begin) * 138 / 100 + 1; // log(256) / log(58), rounded up.
  53     std::vector<unsigned char> b58(base58Size);
  54
  55     while (begin != end) {
  56         int carry = *begin;
  57         int i = 0;
  58         // Apply "b58 = b58 * 256 + ch".
  59         for (auto b58it = b58.rbegin(); (carry != 0 || i < length) && (b58it != b58.rend());
  60              b58it++, i++) {
  61             carry += 256 * (*b58it);
  62             *b58it = carry % 58;
  63             carry /= 58;
  64         }
  65
  66         assert(carry == 0);
  67         length = i;
  68         begin += 1;
  69     }
  70
  71     // Skip leading zeroes in base58 result.
  72     auto it = b58.begin() + (base58Size - length);
  73     while (it != b58.end() && *it == 0) {
  74         it++;
  75     }
  76
  77     // Translate the result into a string.
  78     std::string str;
  79     str.reserve(zeroes + (b58.end() - it));
  80     str.assign(zeroes, digits[0]);
  81     while (it != b58.end()) {
  82         str += digits[*it];
  83         it += 1;
  84     }
  85     return str;
  86 }
  87
  88 // Encode a byte vector as a base58-encoded string
  89 std::string EncodeBase58(const std::vector<unsigned char>& vch)
  90 {
  91     return EncodeBase58(&vch[0], &vch[0] + vch.size());
  92 }
  93
  94 // Decode a base58-encoded string psz into byte vector vchRet
  95 // returns true if decoding is successful
  96 bool DecodeBase58(const char* psz, std::vector<unsigned char>& vchRet)
  97 {
  98     const auto* it = psz;
  99     const char* end = it + strlen(psz);
 100
 101     // Skip leading spaces.
 102     it = std::find_if_not(it, end, [](char c) { return std::isspace(c);});
 103
 104     // Skip and count leading zeros.
 105     std::size_t zeroes = 0;
 106     std::size_t length = 0;
 107     while (it != end && *it == digits[0]) {
 108         zeroes += 1;
 109         it += 1;
 110     }
 111
 112     // Allocate enough space in big-endian base256 representation.
 113     std::size_t base258Size = (end - it) * 733 / 1000 + 1; // log(58) / log(256), rounded up.
 114     std::vector<unsigned char> b256(base258Size);
 115
 116     // Process the characters.
 117    while (it != end && !std::isspace(*it)) {
 118         if (static_cast<unsigned char>(*it) >= 128) {
 119             // Invalid b58 character
 120             return false;
 121         }
 122
 123         // Decode base58 character
 124         int carry = characterMap[static_cast<unsigned char>(*it)];
 125         if (carry == -1) {
 126             // Invalid b58 character
 127             return false;
 128         }
 129
 130         std::size_t i = 0;
 131         for (auto b256it = b256.rbegin(); (carry != 0 || i < length) && (b256it != b256.rend());
 132              ++b256it, ++i) {
 133             carry += 58 * (*b256it);
 134             *b256it = static_cast<uint8_t>(carry % 256);
 135             carry /= 256;
 136         }
 137         assert(carry == 0);
 138         length = i;
 139         it += 1;
 140     }
 141
 142     // Skip trailing spaces.
 143     it = std::find_if_not(it, end, [](char c) { return std::isspace(c);});
 144     if (it != end) {
 145         // Extra charaters at the end
 146         return false;
 147     }
 148
 149     // Skip leading zeroes in b256.
 150     auto b256it = b256.begin() + (base258Size - length);
 151     while (b256it != b256.end() && *b256it == 0) {
 152         b256it++;
 153     }
 154
 155     // Copy result into output vector.
 156     vchRet.reserve(zeroes + (b256.end() - b256it));
 157     vchRet.assign(zeroes, 0x00);
 158     std::copy(b256it, b256.end(), std::back_inserter(vchRet));
 159
 160     return true;
 161 }
 162
 163 // Decode a base58-encoded string str into byte vector vchRet
 164 // returns true if decoding is successful
 165 bool DecodeBase58(const std::string& str, std::vector<unsigned char>& vchRet)
 166 {
 167     return DecodeBase58(str.c_str(), vchRet);
 168 }
 169
 170 // Encode a byte vector to a base58-encoded string, including checksum
 171 std::string EncodeBase58Check(const std::vector<unsigned char>& vchIn)
 172 {
 173     // add 4-byte hash check to the end
 174     std::vector<unsigned char> vch(vchIn);
 175     uint256 hash = Hash(vch.begin(), vch.end());
 176     vch.insert(vch.end(), (unsigned char*)&hash, (unsigned char*)&hash + 4);
 177     return EncodeBase58(vch);
 178 }
 179
 180 // Decode a base58-encoded string psz that includes a checksum, into byte vector vchRet
 181 // returns true if decoding is successful
 182 bool DecodeBase58Check(const char* psz, std::vector<unsigned char>& vchRet)
 183 {
 184     if (!DecodeBase58(psz, vchRet))
 185         return false;
 186     if (vchRet.size() < 4)
 187     {
 188         vchRet.clear();
 189         return false;
 190     }
 191     uint256 hash = Hash(vchRet.begin(), vchRet.end()-4);
 192     if (memcmp(&hash, &vchRet.end()[-4], 4) != 0)
 193     {
 194         vchRet.clear();
 195         return false;
 196     }
 197     vchRet.resize(vchRet.size()-4);
 198     return true;
 199 }
 200
 201 // Decode a base58-encoded string str that includes a checksum, into byte vector vchRet
 202 // returns true if decoding is successful
 203 bool DecodeBase58Check(const std::string& str, std::vector<unsigned char>& vchRet)
 204 {
 205     return DecodeBase58Check(str.c_str(), vchRet);
 206 }
 207
 208     CBase58Data::CBase58Data()
 209     {
 210         nVersion = 0;
 211         vchData.clear();
 212     }
 213
 214     CBase58Data::~CBase58Data()
 215     {
 216         // zero the memory, as it may contain sensitive data
 217         if (!vchData.empty())
 218             OPENSSL_cleanse(&vchData[0], vchData.size());
 219     }
 220
 221     void CBase58Data::SetData(int nVersionIn, const void* pdata, size_t nSize)
 222     {
 223         nVersion = nVersionIn;
 224         vchData.resize(nSize);
 225         if (!vchData.empty())
 226             memcpy(&vchData[0], pdata, nSize);
 227     }
 228
 229     const std::vector<unsigned char> &CBase58Data::GetData() const
 230     {
 231         return vchData;
 232     }
 233
 234     void CBase58Data::SetData(int nVersionIn, const unsigned char *pbegin, const unsigned char *pend)
 235     {
 236         SetData(nVersionIn, (void*)pbegin, pend - pbegin);
 237     }
 238
 239     bool CBase58Data::SetString(const char* psz)
 240     {
 241         std::vector<unsigned char> vchTemp;
 242         DecodeBase58Check(psz, vchTemp);
 243         if (vchTemp.empty())
 244         {
 245             vchData.clear();
 246             nVersion = 0;
 247             return false;
 248         }
 249         nVersion = vchTemp[0];
 250         vchData.resize(vchTemp.size() - 1);
 251         if (!vchData.empty())
 252             memcpy(&vchData[0], &vchTemp[1], vchData.size());
 253         OPENSSL_cleanse(&vchTemp[0], vchData.size());
 254         return true;
 255     }
 256
 257     bool CBase58Data::SetString(const std::string& str)
 258     {
 259         return SetString(str.c_str());
 260     }
 261
 262     std::string CBase58Data::ToString() const
 263     {
 264         std::vector<unsigned char> vch(1, nVersion);
 265         vch.insert(vch.end(), vchData.begin(), vchData.end());
 266         return EncodeBase58Check(vch);
 267     }
 268
 269     int CBase58Data::CompareTo(const CBase58Data& b58) const
 270     {
 271         if (nVersion < b58.nVersion) return -1;
 272         if (nVersion > b58.nVersion) return  1;
 273         if (vchData < b58.vchData)   return -1;
 274         if (vchData > b58.vchData)   return  1;
 275         return 0;
 276     }
 277
 278     bool CBitcoinAddress::Set(const CKeyID &id) {
 279         SetData(fTestNet ? PUBKEY_ADDRESS_TEST : PUBKEY_ADDRESS, &id, 20);
 280         return true;
 281     }
 282
 283     bool CBitcoinAddress::Set(const CScriptID &id) {
 284         SetData(fTestNet ? SCRIPT_ADDRESS_TEST : SCRIPT_ADDRESS, &id, 20);
 285         return true;
 286     }
 287
 288     bool CBitcoinAddress::Set(const CTxDestination &dest)
 289     {
 290         return boost::apply_visitor(CBitcoinAddressVisitor(this), dest);
 291     }
 292
 293     bool CBitcoinAddress::Set(const CMalleablePubKey &mpk) {
 294         std::vector<unsigned char> vchPubkeyPair = mpk.Raw();
 295         SetData(fTestNet ? PUBKEY_PAIR_ADDRESS_TEST : PUBKEY_PAIR_ADDRESS, &vchPubkeyPair[0], 68);
 296         return true;
 297     }
 298
 299     bool CBitcoinAddress::Set(const CBitcoinAddress &dest)
 300     {
 301         nVersion = dest.nVersion;
 302         vchData = dest.vchData;
 303         return true;
 304     }
 305
 306     bool CBitcoinAddress::IsValid() const
 307     {
 308         unsigned int nExpectedSize = 20;
 309         bool fExpectTestNet = false;
 310         bool fSimple = true;
 311         switch(nVersion)
 312         {
 313             case PUBKEY_PAIR_ADDRESS:
 314                 nExpectedSize = 68; // Serialized pair of public keys
 315                 fExpectTestNet = false;
 316                 fSimple = false;
 317                 break;
 318             case PUBKEY_ADDRESS:
 319                 nExpectedSize = 20; // Hash of public key
 320                 fExpectTestNet = false;
 321                 break;
 322             case SCRIPT_ADDRESS:
 323                 nExpectedSize = 20; // Hash of CScript
 324                 fExpectTestNet = false;
 325                 break;
 326
 327             case PUBKEY_PAIR_ADDRESS_TEST:
 328                 nExpectedSize = 68;
 329                 fExpectTestNet = true;
 330                 fSimple = false;
 331                 break;
 332             case PUBKEY_ADDRESS_TEST:
 333                 nExpectedSize = 20;
 334                 fExpectTestNet = true;
 335                 break;
 336             case SCRIPT_ADDRESS_TEST:
 337                 nExpectedSize = 20;
 338                 fExpectTestNet = true;
 339                 break;
 340
 341             default:
 342                 return false;
 343         }
 344
 345         // Basic format sanity check
 346         bool fSeemsSane = (fExpectTestNet == fTestNet && vchData.size() == nExpectedSize);
 347
 348         if (fSeemsSane && !fSimple)
 349         {
 350             // Perform dditional checking
 351             //    for pubkey pair addresses
 352             CMalleablePubKey mpk;
 353             mpk.setvch(vchData);
 354             return mpk.IsValid();
 355         }
 356         else
 357             return fSeemsSane;
 358     }
 359
 360     CTxDestination CBitcoinAddress::Get() const {
 361         if (!IsValid())
 362             return CNoDestination();
 363         switch (nVersion) {
 364         case PUBKEY_ADDRESS:
 365         case PUBKEY_ADDRESS_TEST: {
 366             uint160 id;
 367             memcpy(&id, &vchData[0], 20);
 368             return CKeyID(id);
 369         }
 370         case SCRIPT_ADDRESS:
 371         case SCRIPT_ADDRESS_TEST: {
 372             uint160 id;
 373             memcpy(&id, &vchData[0], 20);
 374             return CScriptID(id);
 375         }
 376         }
 377         return CNoDestination();
 378     }
 379
 380     bool CBitcoinAddress::GetKeyID(CKeyID &keyID) const {
 381         if (!IsValid())
 382             return false;
 383         switch (nVersion) {
 384         case PUBKEY_ADDRESS:
 385         case PUBKEY_ADDRESS_TEST: {
 386             uint160 id;
 387             memcpy(&id, &vchData[0], 20);
 388             keyID = CKeyID(id);
 389             return true;
 390         }
 391         case PUBKEY_PAIR_ADDRESS:
 392         case PUBKEY_PAIR_ADDRESS_TEST:
 393         {
 394             CMalleablePubKey mPubKey;
 395             mPubKey.setvch(vchData);
 396             keyID = mPubKey.GetID();
 397             return true;
 398         }
 399         default: return false;
 400         }
 401     }
 402
 403     bool CBitcoinAddress::IsScript() const {
 404         if (!IsValid())
 405             return false;
 406         switch (nVersion) {
 407         case SCRIPT_ADDRESS:
 408         case SCRIPT_ADDRESS_TEST: {
 409             return true;
 410         }
 411         default: return false;
 412         }
 413     }
 414
 415     bool CBitcoinAddress::IsPubKey() const {
 416         if (!IsValid())
 417             return false;
 418         switch (nVersion) {
 419         case PUBKEY_ADDRESS:
 420         case PUBKEY_ADDRESS_TEST: {
 421             return true;
 422         }
 423         default: return false;
 424         }
 425     }
 426
 427     bool CBitcoinAddress::IsPair() const {
 428         if (!IsValid())
 429             return false;
 430         switch (nVersion) {
 431         case PUBKEY_PAIR_ADDRESS:
 432         case PUBKEY_PAIR_ADDRESS_TEST: {
 433             return true;
 434         }
 435         default: return false;
 436         }
 437     }
 438
 439     void CBitcoinSecret::SetSecret(const CSecret& vchSecret, bool fCompressed)
 440     {
 441         assert(vchSecret.size() == 32);
 442         SetData(128 + (fTestNet ? CBitcoinAddress::PUBKEY_ADDRESS_TEST : CBitcoinAddress::PUBKEY_ADDRESS), &vchSecret[0], vchSecret.size());
 443         if (fCompressed)
 444             vchData.push_back(1);
 445     }
 446
 447     CSecret CBitcoinSecret::GetSecret(bool &fCompressedOut)
 448     {
 449         CSecret vchSecret;
 450         vchSecret.resize(32);
 451         memcpy(&vchSecret[0], &vchData[0], 32);
 452         fCompressedOut = vchData.size() == 33;
 453         return vchSecret;
 454     }
 455
 456     bool CBitcoinSecret::IsValid() const
 457     {
 458         bool fExpectTestNet = false;
 459         switch(nVersion)
 460         {
 461             case (128 + CBitcoinAddress::PUBKEY_ADDRESS):
 462                 break;
 463
 464             case (128 + CBitcoinAddress::PUBKEY_ADDRESS_TEST):
 465                 fExpectTestNet = true;
 466                 break;
 467
 468             default:
 469                 return false;
 470         }
 471         return fExpectTestNet == fTestNet && (vchData.size() == 32 || (vchData.size() == 33 && vchData[32] == 1));
 472     }
 473
 474     bool CBitcoinSecret::SetString(const char* pszSecret)
 475     {
 476         return CBase58Data::SetString(pszSecret) && IsValid();
 477     }
 478
 479     bool CBitcoinSecret::SetString(const std::string& strSecret)
 480     {
 481         return SetString(strSecret.c_str());
 482     }
 483
 484     CBitcoinSecret::CBitcoinSecret(const CSecret& vchSecret, bool fCompressed)
 485     {
 486         SetSecret(vchSecret, fCompressed);
 487     }
 488
 489