src/base58.h

   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 #ifndef BITCOIN_BASE58_H
  16 #define BITCOIN_BASE58_H
  17
  18 #include <string>
  19 #include <vector>
  20
  21 #include "chainparams.h"
  22 #include "bignum.h"
  23 #include "key.h"
  24 #include "script.h"
  25 #include "allocators.h"
  26
  27 static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
  28
  29 // Encode a byte sequence as a base58-encoded string
  30 inline std::string EncodeBase58(const unsigned char* pbegin, const unsigned char* pend)
  31 {
  32     CAutoBN_CTX pctx;
  33     CBigNum bn58 = 58;
  34     CBigNum bn0 = 0;
  35
  36     // Convert big endian data to little endian
  37     // Extra zero at the end make sure bignum will interpret as a positive number
  38     std::vector<unsigned char> vchTmp(pend-pbegin+1, 0);
  39     reverse_copy(pbegin, pend, vchTmp.begin());
  40
  41     // Convert little endian data to bignum
  42     CBigNum bn;
  43     bn.setvch(vchTmp);
  44
  45     // Convert bignum to std::string
  46     std::string str;
  47     // Expected size increase from base58 conversion is approximately 137%
  48     // use 138% to be safe
  49     str.reserve((pend - pbegin) * 138 / 100 + 1);
  50     CBigNum dv;
  51     CBigNum rem;
  52     while (bn > bn0)
  53     {
  54         if (!BN_div(&dv, &rem, &bn, &bn58, pctx))
  55             throw bignum_error("EncodeBase58 : BN_div failed");
  56         bn = dv;
  57         unsigned int c = rem.getulong();
  58         str += pszBase58[c];
  59     }
  60
  61     // Leading zeroes encoded as base58 zeros
  62     for (const unsigned char* p = pbegin; p < pend && *p == 0; p++)
  63         str += pszBase58[0];
  64
  65     // Convert little endian std::string to big endian
  66     reverse(str.begin(), str.end());
  67     return str;
  68 }
  69
  70 // Encode a byte vector as a base58-encoded string
  71 inline std::string EncodeBase58(const std::vector<unsigned char>& vch)
  72 {
  73     return EncodeBase58(&vch[0], &vch[0] + vch.size());
  74 }
  75
  76 // Decode a base58-encoded string psz into byte vector vchRet
  77 // returns true if decoding is successful
  78 inline bool DecodeBase58(const char* psz, std::vector<unsigned char>& vchRet)
  79 {
  80     CAutoBN_CTX pctx;
  81     vchRet.clear();
  82     CBigNum bn58 = 58;
  83     CBigNum bn = 0;
  84     CBigNum bnChar;
  85     while (isspace(*psz))
  86         psz++;
  87
  88     // Convert big endian string to bignum
  89     for (const char* p = psz; *p; p++)
  90     {
  91         const char* p1 = strchr(pszBase58, *p);
  92         if (p1 == NULL)
  93         {
  94             while (isspace(*p))
  95                 p++;
  96             if (*p != '\0')
  97                 return false;
  98             break;
  99         }
 100         bnChar.setulong(p1 - pszBase58);
 101         if (!BN_mul(&bn, &bn, &bn58, pctx))
 102             throw bignum_error("DecodeBase58 : BN_mul failed");
 103         bn += bnChar;
 104     }
 105
 106     // Get bignum as little endian data
 107     std::vector<unsigned char> vchTmp = bn.getvch();
 108
 109     // Trim off sign byte if present
 110     if (vchTmp.size() >= 2 && vchTmp.end()[-1] == 0 && vchTmp.end()[-2] >= 0x80)
 111         vchTmp.erase(vchTmp.end()-1);
 112
 113     // Restore leading zeros
 114     int nLeadingZeros = 0;
 115     for (const char* p = psz; *p == pszBase58[0]; p++)
 116         nLeadingZeros++;
 117     vchRet.assign(nLeadingZeros + vchTmp.size(), 0);
 118
 119     // Convert little endian data to big endian
 120     reverse_copy(vchTmp.begin(), vchTmp.end(), vchRet.end() - vchTmp.size());
 121     return true;
 122 }
 123
 124 // Decode a base58-encoded string str into byte vector vchRet
 125 // returns true if decoding is successful
 126 inline bool DecodeBase58(const std::string& str, std::vector<unsigned char>& vchRet)
 127 {
 128     return DecodeBase58(str.c_str(), vchRet);
 129 }
 130
 131
 132
 133
 134 // Encode a byte vector to a base58-encoded string, including checksum
 135 inline std::string EncodeBase58Check(const std::vector<unsigned char>& vchIn)
 136 {
 137     // add 4-byte hash check to the end
 138     std::vector<unsigned char> vch(vchIn);
 139     uint256 hash = Hash(vch.begin(), vch.end());
 140     vch.insert(vch.end(), (unsigned char*)&hash, (unsigned char*)&hash + 4);
 141     return EncodeBase58(vch);
 142 }
 143
 144 // Decode a base58-encoded string psz that includes a checksum, into byte vector vchRet
 145 // returns true if decoding is successful
 146 inline bool DecodeBase58Check(const char* psz, std::vector<unsigned char>& vchRet)
 147 {
 148     if (!DecodeBase58(psz, vchRet))
 149         return false;
 150     if (vchRet.size() < 4)
 151     {
 152         vchRet.clear();
 153         return false;
 154     }
 155     uint256 hash = Hash(vchRet.begin(), vchRet.end()-4);
 156     if (memcmp(&hash, &vchRet.end()[-4], 4) != 0)
 157     {
 158         vchRet.clear();
 159         return false;
 160     }
 161     vchRet.resize(vchRet.size()-4);
 162     return true;
 163 }
 164
 165 // Decode a base58-encoded string str that includes a checksum, into byte vector vchRet
 166 // returns true if decoding is successful
 167 inline bool DecodeBase58Check(const std::string& str, std::vector<unsigned char>& vchRet)
 168 {
 169     return DecodeBase58Check(str.c_str(), vchRet);
 170 }
 171
 172
 173
 174
 175
 176 /** Base class for all base58-encoded data */
 177 class CBase58Data
 178 {
 179 protected:
 180     // the version byte(s)
 181     std::vector<unsigned char> vchVersion;
 182
 183     // the actually encoded data
 184     typedef std::vector<unsigned char, zero_after_free_allocator<unsigned char> > vector_uchar;
 185     vector_uchar vchData;
 186
 187     CBase58Data()
 188     {
 189         vchVersion.clear();
 190         vchData.clear();
 191     }
 192
 193     void SetData(const std::vector<unsigned char> &vchVersionIn, const void* pdata, size_t nSize)
 194     {
 195         vchVersion = vchVersionIn;
 196         vchData.resize(nSize);
 197         if (!vchData.empty())
 198             memcpy(&vchData[0], pdata, nSize);
 199     }
 200
 201     void SetData(const std::vector<unsigned char> &vchVersionIn, const unsigned char *pbegin, const unsigned char *pend)
 202     {
 203         SetData(vchVersionIn, (void*)pbegin, pend - pbegin);
 204     }
 205
 206 public:
 207     bool SetString(const char* psz, unsigned int nVersionBytes = 1)
 208     {
 209         std::vector<unsigned char> vchTemp;
 210         DecodeBase58Check(psz, vchTemp);
 211         if (vchTemp.size() < nVersionBytes)
 212         {
 213             vchData.clear();
 214             vchVersion.clear();
 215             return false;
 216         }
 217         vchVersion.assign(vchTemp.begin(), vchTemp.begin() + nVersionBytes);
 218         vchData.resize(vchTemp.size() - nVersionBytes);
 219         if (!vchData.empty())
 220             memcpy(&vchData[0], &vchTemp[nVersionBytes], vchData.size());
 221         OPENSSL_cleanse(&vchTemp[0], vchData.size());
 222         return true;
 223     }
 224
 225     bool SetString(const std::string& str)
 226     {
 227         return SetString(str.c_str());
 228     }
 229
 230     std::string ToString() const
 231     {
 232         std::vector<unsigned char> vch = vchVersion;
 233         vch.insert(vch.end(), vchData.begin(), vchData.end());
 234         return EncodeBase58Check(vch);
 235     }
 236
 237     int CompareTo(const CBase58Data& b58) const
 238     {
 239         if (vchVersion < b58.vchVersion) return -1;
 240         if (vchVersion > b58.vchVersion) return  1;
 241         if (vchData < b58.vchData)   return -1;
 242         if (vchData > b58.vchData)   return  1;
 243         return 0;
 244     }
 245
 246     bool operator==(const CBase58Data& b58) const { return CompareTo(b58) == 0; }
 247     bool operator<=(const CBase58Data& b58) const { return CompareTo(b58) <= 0; }
 248     bool operator>=(const CBase58Data& b58) const { return CompareTo(b58) >= 0; }
 249     bool operator< (const CBase58Data& b58) const { return CompareTo(b58) <  0; }
 250     bool operator> (const CBase58Data& b58) const { return CompareTo(b58) >  0; }
 251 };
 252
 253 /** base58-encoded Bitcoin addresses.
 254  * Public-key-hash-addresses have version 0 (or 111 testnet).
 255  * The data vector contains RIPEMD160(SHA256(pubkey)), where pubkey is the serialized public key.
 256  * Script-hash-addresses have version 5 (or 196 testnet).
 257  * The data vector contains RIPEMD160(SHA256(cscript)), where cscript is the serialized redemption script.
 258  */
 259 class CBitcoinAddress;
 260 class CBitcoinAddressVisitor : public boost::static_visitor<bool>
 261 {
 262 private:
 263     CBitcoinAddress *addr;
 264 public:
 265     CBitcoinAddressVisitor(CBitcoinAddress *addrIn) : addr(addrIn) { }
 266     bool operator()(const CKeyID &id) const;
 267     bool operator()(const CScriptID &id) const;
 268     bool operator()(const CNoDestination &no) const;
 269 };
 270
 271 class CBitcoinAddress : public CBase58Data
 272 {
 273 public:
 274     bool Set(const CKeyID &id) {
 275         SetData(Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS), &id, 20);
 276         return true;
 277     }
 278
 279     bool Set(const CScriptID &id) {
 280         SetData(Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS), &id, 20);
 281         return true;
 282     }
 283
 284     bool Set(const CTxDestination &dest)
 285     {
 286         return boost::apply_visitor(CBitcoinAddressVisitor(this), dest);
 287     }
 288
 289     bool IsValid() const
 290     {
 291         bool fCorrectSize = vchData.size() == 20;
 292         bool fKnownVersion = vchVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS) ||
 293                              vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS);
 294         return fCorrectSize && fKnownVersion;
 295     }
 296
 297     CBitcoinAddress()
 298     {
 299     }
 300
 301     CBitcoinAddress(const CTxDestination &dest)
 302     {
 303         Set(dest);
 304     }
 305
 306     CBitcoinAddress(const std::string& strAddress)
 307     {
 308         SetString(strAddress);
 309     }
 310
 311     CBitcoinAddress(const char* pszAddress)
 312     {
 313         SetString(pszAddress);
 314     }
 315
 316     CTxDestination Get() const {
 317         if (!IsValid())
 318             return CNoDestination();
 319         uint160 id;
 320         memcpy(&id, &vchData[0], 20);
 321         if (vchVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS))
 322             return CKeyID(id);
 323         else if (vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS))
 324             return CScriptID(id);
 325         else
 326             return CNoDestination();
 327     }
 328
 329     bool GetKeyID(CKeyID &keyID) const {
 330         if (!IsValid() || vchVersion != Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS))
 331             return false;
 332         uint160 id;
 333         memcpy(&id, &vchData[0], 20);
 334         keyID = CKeyID(id);
 335         return true;
 336     }
 337
 338     bool IsScript() const {
 339         return IsValid() && vchVersion == Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS);
 340     }
 341 };
 342
 343 bool inline CBitcoinAddressVisitor::operator()(const CKeyID &id) const         { return addr->Set(id); }
 344 bool inline CBitcoinAddressVisitor::operator()(const CScriptID &id) const      { return addr->Set(id); }
 345 bool inline CBitcoinAddressVisitor::operator()(const CNoDestination &id) const { return false; }
 346
 347 /** A base58-encoded secret key */
 348 class CBitcoinSecret : public CBase58Data
 349 {
 350 public:
 351     void SetKey(const CKey& vchSecret)
 352     {
 353         assert(vchSecret.IsValid());
 354         SetData(Params().Base58Prefix(CChainParams::SECRET_KEY), vchSecret.begin(), vchSecret.size());
 355         if (vchSecret.IsCompressed())
 356             vchData.push_back(1);
 357     }
 358
 359     CKey GetKey()
 360     {
 361         CKey ret;
 362         ret.Set(&vchData[0], &vchData[32], vchData.size() > 32 && vchData[32] == 1);
 363         return ret;
 364     }
 365
 366     bool IsValid() const
 367     {
 368         bool fExpectedFormat = vchData.size() == 32 || (vchData.size() == 33 && vchData[32] == 1);
 369         bool fCorrectVersion = vchVersion == Params().Base58Prefix(CChainParams::SECRET_KEY);
 370         return fExpectedFormat && fCorrectVersion;
 371     }
 372
 373     bool SetString(const char* pszSecret)
 374     {
 375         return CBase58Data::SetString(pszSecret) && IsValid();
 376     }
 377
 378     bool SetString(const std::string& strSecret)
 379     {
 380         return SetString(strSecret.c_str());
 381     }
 382
 383     CBitcoinSecret(const CKey& vchSecret)
 384     {
 385         SetKey(vchSecret);
 386     }
 387
 388     CBitcoinSecret()
 389     {
 390     }
 391 };
 392
 393
 394 template<typename K, int Size, CChainParams::Base58Type Type> class CBitcoinExtKeyBase : public CBase58Data
 395 {
 396 public:
 397     void SetKey(const K &key) {
 398         unsigned char vch[Size];
 399         key.Encode(vch);
 400         SetData(Params().Base58Prefix(Type), vch, vch+Size);
 401     }
 402
 403     K GetKey() {
 404         K ret;
 405         ret.Decode(&vchData[0], &vchData[Size]);
 406         return ret;
 407     }
 408
 409     CBitcoinExtKeyBase(const K &key) {
 410         SetKey(key);
 411     }
 412
 413     CBitcoinExtKeyBase() {}
 414 };
 415
 416 typedef CBitcoinExtKeyBase<CExtKey, 74, CChainParams::EXT_SECRET_KEY> CBitcoinExtKey;
 417 typedef CBitcoinExtKeyBase<CExtPubKey, 74, CChainParams::EXT_PUBLIC_KEY> CBitcoinExtPubKey;
 418
 419 #endif // BITCOIN_BASE58_H