kodieren/dekodieren Sie Base-58 C++

Ich habe einen Base-58-Encoder mit dieser Formel erstellt: https://www.youtube.com/watch?v=GedV3S9X89c&feature=youtu.be

Gibt es eine intelligentere Methode zum Codieren/Decodieren mit Base-58?

Ich habe irgendwo gelesen, dass Sie eine Bignum-Bibliothek benötigen, für die ich Boost verwende.

Mein Ziel ist es, zwischen diesen beiden zu konvertieren:

008D4D508F5BF2C28B20A3863405F05D3CD374B045E4B316E7
1Dt8ty59tU9LkrXG2ocWeSzKFAY8fu6jga

Was diese Website so einfach macht: http://lenschulwitz.com/base58

Ich weiß, dass der Bitcoin-Quellcode einen Base-58-Encoder/Decoder hat, aber ich weiß nicht, wie ich ihn erfolgreich implementieren kann.

Antworten (4)

Ich habe viele Male Base58-Codierung/Decodierung verwendet. Im Gegenteil, ich hasste es, eine BIGNUM-Bibliothek zu verwenden. Also habe ich den Basiskonvertierungsalgorithmus von Base-x verwendet. (Achten Sie darauf, die MIT-Lizenz zu respektieren) Es sollte einfach sein, es in jede Sprache zu übersetzen.

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;
}
Cool. Was wäre ein kurzes Beispiel für die Verwendung dieses Codes?
Verwenden Sie NICHT den obigen Code ... Es funktioniert ganz einfach nicht. Ich habe lange Zeit damit verbracht, meinen Code zu debuggen, nur um herauszufinden, dass es diese schreckliche Implementierung eines Base58-Encoders und -Decoders war. Hast du diesen Code überhaupt TESTEN, bevor du ihn hier eingefügt hast???
Duh, hatte immer encode aufgerufen, wobei das Ergebnisarray auf Null initialisiert war.
@MCCCS Es ist nicht das Ausgabearray, das auf Null initialisiert werden muss, sondern die unsigned char digits[len * 137 / 100]; Array, das wegen Übertrag funktioniert += (unsigned int) (digits[j]) << 8;
@MCCCS Auch Sie haben ein VIEL größeres Problem mit diesen Algorithmen. Wenn Sie mit Ihrem Encoder versuchen, Daten zu codieren, die mit 0 beginnen, oder sogar nur ein einzelnes 0-Byte, wird Ihre Ausgabe "11" codiert, wenn sie "1" sein sollte. Zweitens können Sie mit Ihrem Decoder, wenn Sie Zeichen außerhalb des ASCII-Bereichs angeben, beginnen, außerhalb Ihres 128-Byte-Mapping-Arrays zu lesen. Aus diesem Grund verwendet die Bitcoin-Implementierung 256 Bytes und es gibt eine Umwandlung in uint8_t.
@TheWelder Von Grund auf neu transkribierte Codierung.
@TheWelder Nein, digits[len * 137/100]muss nicht initialisiert werden. Sein erstes Element wird auf Null initialisiert und ist am Anfang digitslen1. Jedes Mal, wenn digitslenes erhöht wird, wird dem neuen Element ein Wert zugewiesen. Aber das spielt keine Rolle mehr.
@MCCCS Sie haben Recht, haben die zusätzliche Initialisierung des ersten Elements nicht bemerkt. Wie auch immer, ich habe meine Implementierung unten mit einem Fuzz-Tester hinzugefügt, um sicherzustellen, dass es funktioniert.

Ich habe BIGNUM von openssl verwendet, um hex mit base58 zu codieren

 #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;
}

und verwende es dann so:

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

"Dt8ty59tU9LkrXG2ocWeSzKFAY8fu6jga"
Ich habe immer noch ein Problem mit führenden Nullen. Ich versuche das auch zu beheben
Suchen Sie nach bestimmten führenden Nullen in der Eingabe ... for( int i=0 ; i<priv_hex.size() ; i++ ) { if( priv_hex[i] == 0 ) { v.push_back(0) ; } Sonst {Pause; } }

Habe meine eigene Implementierung hinzugefügt, komplett mit einem Fuzz-Tester, um sicherzustellen, dass es richtig funktioniert. (Der CodecMapping-Parameter wird bereitgestellt, damit Sie die Buchstabenfolge ändern können, wie ich es von Zeit zu Zeit tun musste.)

#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;
}

Für diejenigen, die ein bisschen Old Skool bevorzugen C, hier ist meine Interpretation der Antwort von @MarkusC

Ich habe versucht, den Code so nah wie möglich an seinem ursprünglichen Code zu halten - gibt bei Erfolg Null zurück oder -1oder -2wenn der Pufferspeicher knapp wird.

Ich habe eine von mir verwendete und eine von ihm bereitgestellte Testzeichenfolge beigefügt.

#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);
}
kodieren/dekodieren Sie Base-58 C++
AntwortenHierDatenschutz-Bestimmungen1y, 0v