2

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.

2

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;
}
| improve this answer | |
  • 1
    Cool. What would be a quick example on how to use this code? – dalslandan200 Jun 21 '18 at 14:08
  • @dalslandan200 hastebin.com/ujepeduqus.cpp – MCCCS Jun 21 '18 at 14:13
  • DO NOT use the above code... It quite simply doesn't work. I've spent a long time debugging my code only to find out it was this God awful implementation of a Base58 encoder and decoder. Did you even TEST this code before you pasted it here??? – The Welder May 28 at 14:14
  • Duh, had always been calling encode with the result array initialized to zero. – MCCCS May 28 at 15:07
  • 1
    @MCCCS You're right, didn't notice the added initialisation of the first element. Anyway, have added my implementation below with a fuzz tester to ensure that it works. – The Welder Jun 7 at 13:25
1

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;
}
| improve this answer | |
0

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"
| improve this answer | |
  • I have sill a problem with leading zeros. I try to fix this as well – Markus Nov 18 '18 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.