encode/decode Base-58 C++

Question

I have built a base-58 encoder using this formula: https://www.youtube.com/watch?v=GedV3S9X89c&feature=youtu.be

Is there a smarter way to encode/decode with base-58?

I read somewhere that you need a bignum library which I use Boost for.

My goal is to convert between these two:

008D4D508F5BF2C28B20A3863405F05D3CD374B045E4B316E7
1Dt8ty59tU9LkrXG2ocWeSzKFAY8fu6jga

Which so easily this website do: http://lenschulwitz.com/base58

I know bitcoin source code have a base-58 encoder/decoder, but I do not know how to implement it successfully.

Answer 1

I've used Base58 encoding/decoding many times. On the contrary, I hated using a BIGNUM library. So, I used Base-x's base conversion algorithm. (Make sure to respect the MIT license) It should be easy to translate it to any language.

const char * const ALPHABET =
    "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
const char ALPHABET_MAP[256] = {
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1,  0,  1,  2,  3,  4,  5,  6,  7,  8, -1, -1, -1, -1, -1, -1,
    -1,  9, 10, 11, 12, 13, 14, 15, 16, -1, 17, 18, 19, 20, 21, -1,
    22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, -1, -1, -1, -1, -1,
    -1, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, -1, 44, 45, 46,
    47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
};

const double iFactor = 1.36565823730976103695740418120764243208481439700722980119458355862779176747360903943915516885072037696111192757109;

// reslen is the allocated length for result, feel free to overallocate
int EncodeBase58(const unsigned char *source, int len, unsigned char result[], int reslen) {
    int zeros = 0, length = 0, pbegin = 0, pend;
    if (!(pend = len)) return 0;
    while (pbegin != pend && !source[pbegin]) pbegin = ++zeros;
    int size = 1 + iFactor * (double)(pend - pbegin);
    unsigned char b58[size];
    for (int i = 0; i < size; i++) b58[i] = 0;
    while (pbegin != pend) {
        unsigned int carry = source[pbegin];
        int i = 0;
        for (int it1 = size - 1; (carry || i < length) && (it1 != -1); it1--,i++) {
            carry += 256 * b58[it1];
            b58[it1] = carry % 58;
            carry /= 58;
        }
        if (carry) return 0;
        length = i;
        pbegin++;
    }
    int it2 = size - length;
    while ((it2-size) && !b58[it2]) it2++;
    if ((zeros + size - it2 + 1) > reslen) return 0;
    int ri = 0;
    while(ri < zeros) result[ri++] = '1';
    for (; it2 < size; ++it2) result[ri++] = ALPHABET[b58[it2]];
    result[ri] = 0;
    return ri;
}

// result must be declared (for the worst case): char result[len * 2];
int DecodeBase58(
    const unsigned char *str, int len, unsigned char *result) {
    result[0] = 0;
    int resultlen = 1;
    for (int i = 0; i < len; i++) {
        unsigned int carry = (unsigned int) ALPHABET_MAP[str[i]];
        if (carry == -1) return 0;
        for (int j = 0; j < resultlen; j++) {
            carry += (unsigned int) (result[j]) * 58;
            result[j] = (unsigned char) (carry & 0xff);
            carry >>= 8;
        }
        while (carry > 0) {
            result[resultlen++] = carry & 0xff;
            carry >>= 8;
        }
    }

    for (int i = 0; i < len && str[i] == '1'; i++)
        result[resultlen++] = 0;

    // Poorly coded, but guaranteed to work.
    for (int i = resultlen - 1, z = (resultlen >> 1) + (resultlen & 1);
        i >= z; i--) {
        int k = result[i];
        result[i] = result[resultlen - i - 1];
        result[resultlen - i - 1] = k;
    }
    return resultlen;
}

Answer 2

I used BIGNUM from openssl to encode hex with base58

 #include <string>
 #include <vector>
 #include <openssl/bn.h>

 string b58(const char *priv_hex)
 {
   char table[] = {'1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','J','K','L','M','N','P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

BIGNUM *base58 = NULL;

BIGNUM *resultExp = BN_new();
BIGNUM *resultAdd = BN_new();
BIGNUM *resultRem = BN_new();
BN_CTX *bn_ctx = BN_CTX_new();

BN_dec2bn(&base58, "58");

string endresult;
vector<int> v;

BN_hex2bn( &resultAdd, priv_hex );

while( !BN_is_zero(resultAdd) ) {
    BN_div(resultAdd, resultRem, resultAdd, base58, bn_ctx);
    char *asdf = BN_bn2dec(resultRem);
    v.push_back(atoi(asdf));
}

for (int i = (int)v.size()-1; i >= 0; i--) {
    endresult = endresult + table[v[i]];
}

BN_free(resultAdd);
BN_free(resultExp);
BN_free(resultRem);
BN_CTX_free(bn_ctx);

return endresult;
}

and then use it like this:

string ttest = "008D4D508F5BF2C28B20A3863405F05D3CD374B045E4B316E7";
const char *phex = ttest.c_str();
string ret = b58(phex);
cout << ret << endl;

"Dt8ty59tU9LkrXG2ocWeSzKFAY8fu6jga"

Answer 3

Have added my own implementation, complete with a fuzz tester to ensure that it works properly. (The CodecMapping parameter is provided so that you can change the alphabet string as I've had to do from time to time)

#include <vector>
#include <random>
#include <string>
#include <algorithm>
#include <iomanip>
#include <iostream>

inline static constexpr const uint8_t Base58Map[] = {
  '1', '2', '3', '4', '5', '6', '7', '8',
  '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G',
  'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q',
  'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',
  'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g',
  'h', 'i', 'j', 'k', 'm', 'n', 'o', 'p',
  'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
  'y', 'z' };
inline static constexpr const uint8_t AlphaMap[] = {
  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  0xff, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
  0xff, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0xff, 0x11, 0x12, 0x13, 0x14, 0x15, 0xff,
  0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0xff, 0xff, 0xff, 0xff, 0xff,
  0xff, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0xff, 0x2c, 0x2d, 0x2e,
  0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0xff, 0xff, 0xff, 0xff, 0xff };

using CodecMapping = struct _codecmapping
{
  _codecmapping(const uint8_t* amap, const uint8_t* bmap) : AlphaMapping(amap), BaseMapping(bmap) {}
  const uint8_t* AlphaMapping;
  const uint8_t* BaseMapping;
};

std::string Base58Encode(const std::vector<uint8_t>& data, CodecMapping mapping)
{
  std::vector<uint8_t> digits((data.size() * 138 / 100) + 1);
  size_t digitslen = 1;
  for (size_t i = 0; i < data.size(); i++)
  {
    uint32_t carry = static_cast<uint32_t>(data[i]);
    for (size_t j = 0; j < digitslen; j++)
    {
      carry = carry + static_cast<uint32_t>(digits[j] << 8);
      digits[j] = static_cast<uint8_t>(carry % 58);
      carry /= 58;
    }
    for (; carry; carry /= 58)
      digits[digitslen++] = static_cast<uint8_t>(carry % 58);
  }
  std::string result;
  for (size_t i = 0; i < (data.size() - 1) && !data[i]; i++)
    result.push_back(mapping.BaseMapping[0]);
  for (size_t i = 0; i < digitslen; i++)
    result.push_back(mapping.BaseMapping[digits[digitslen - 1 - i]]);
  return result;
}

std::vector<uint8_t> Base58Decode(const std::string& data, CodecMapping mapping)
{
  std::vector<uint8_t> result((data.size() * 138 / 100) + 1);
  size_t resultlen = 1;
  for (size_t i = 0; i < data.size(); i++)
  {
    uint32_t carry = static_cast<uint32_t>(mapping.AlphaMapping[data[i] & 0x7f]);
    for (size_t j = 0; j < resultlen; j++, carry >>= 8)
    {
      carry += static_cast<uint32_t>(result[j] * 58);
      result[j] = static_cast<uint8_t>(carry);
    }
    for (; carry; carry >>=8)
      result[resultlen++] = static_cast<uint8_t>(carry);
  }
  result.resize(resultlen);
  for (size_t i = 0; i < (data.size() - 1) && data[i] == mapping.BaseMapping[0]; i++)
    result.push_back(0);
  std::reverse(result.begin(), result.end());
  return result;
}

// Fuzz Testing the Encoder & Decoder
int main(int argc, char** argv)
{
  std::random_device device;
  std::mt19937 generator(device());
  std::uniform_int_distribution d1(1, 100);
  std::uniform_int_distribution d2(0, 255);
  CodecMapping mapping(AlphaMap, Base58Map);

  auto create_data = [&]() -> std::vector<uint8_t> {
    std::vector<uint8_t> data(d1(generator));
    std::cout << "Generating: " << std::dec << static_cast<int>(data.size()) << " points\nPoints:\n";
    for (uint8_t& v : data)
    {
      v = static_cast<uint8_t>(d2(generator));
      std::cout << std::uppercase << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(v);
    }
    std::cout << std::endl;
    return data;
  };

  std::vector<uint8_t> test_data, decoded_data;
  std::string encoded_data;
  size_t passed = 0;

  for (size_t i = 0; i < 1000; i++)    // Number of tests here!
  {
    test_data = create_data();
    encoded_data = Base58Encode(test_data, mapping);
    decoded_data = Base58Decode(encoded_data, mapping);

    std::cout << "Encoded\n" << encoded_data << "\nDecoded:\n";

    for (uint8_t d : decoded_data)
      std::cout << std::uppercase << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(d);

    std::cout << "\nTest Result: ";
    if (test_data.size() == decoded_data.size() && test_data == decoded_data)
    {
      std::cout << "PASSED\n";
      passed++;
    }
    else
    {
      std::cout << "FAILED\n";
      break;
    }
    std::cout << std::endl;
  }
  std::cout << "Passed Tests: " << std::dec << static_cast<int>(passed) << std::endl;
  return 0;
}

Answer 4

For those who prefer a bit of old skool C, here's my interpretation of @Markus' answer in C

I've tried to keep the code as close to his original code as possible - returns zero on success or -1 or -2 if it runs out of buffer space.

I've included a test string I use & one he provided.

#include <openssl/bn.h>
#include <string.h>

int b58(const char *priv_hex, char * endresult, int end_sz)
{
char table[] = {'1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H',
    'J','K','L','M','N','P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d',
    'e','f','g','h','i','j','k','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

BIGNUM *base58 = NULL;

BIGNUM *resultExp = BN_new();
BIGNUM *resultAdd = BN_new();
BIGNUM *resultRem = BN_new();
BN_CTX *bn_ctx = BN_CTX_new();
int v[300],v_len=0;

    BN_dec2bn(&base58, "58");
    BN_hex2bn( &resultAdd, priv_hex );
    memset(v,0,sizeof(v));

    while( !BN_is_zero(resultAdd) ) {
        BN_div(resultAdd, resultRem, resultAdd, base58, bn_ctx);
        char *asdf = BN_bn2dec(resultRem);
        if ((v_len+1) >= (int)sizeof(v)) return -1;
        v[v_len++] = atoi(asdf);
    }

    if (v_len >= (end_sz-1)) {
        *endresult = 0;
        return -2;
        }

    for(int i = 0;i<v_len;i++) endresult[v_len-i-1] = table[v[i]];
    endresult[v_len] = 0;

    BN_free(resultAdd);
    BN_free(resultExp);
    BN_free(resultRem);
    BN_CTX_free(bn_ctx);

    return 0;
}

main()
{
char * correct = "3MU5WsLWqbK6o9buaD4HtXK1KgozcV8BWj";
char * hex_src = "05d8f01b4132f0c3e290c30788d229811102820524dbc1f61c";
char res[250];

b58(hex_src,res,sizeof(res));
printf("ANS: %s\nTST: %s\n",res,correct);

char * test_q = "008D4D508F5BF2C28B20A3863405F05D3CD374B045E4B316E7";
char * test_ans = "Dt8ty59tU9LkrXG2ocWeSzKFAY8fu6jga";

b58(test_q,res,sizeof(res));
printf("ANS: %s\nTST: %s\n",res,test_ans);
}