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