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