Remove dependency of base58 on OpenSSL #4048

sipa commented at 10:03 PM on April 12, 2014: member

This completely removes the bignum-based base58 code, and replaces it with an implementation that directly operates on vectors of bytes / base58 numbers.

ghost commented at 10:30 PM on April 12, 2014: none

:+1:

laanwj commented at 5:35 AM on April 14, 2014: member

@gmaxwell we can be sure about that. DecodeBase58 is only called from two places in base58.h itself:

DecodeBase58(std::string) -> passed string.c_str() which is always zero-terminated
DecodeBase58Check(const char*) -> passes through its input which has always been a zero-terminated string

In general I too prefer APIs that explicitly pass the length of strings (or that use a string type with embedded length field like std::string), but it doesn't look like there is reason to change the API here.

gmaxwell commented at 5:37 AM on April 14, 2014: contributor

:) Yea the "will" was meant to include all future callers. Communication is hard.

laanwj commented at 6:00 AM on April 14, 2014: member

Right. It's especially useful to pass a length - or an begin* and end* pointer - if we want to be able to error out on NULs before the real end of the string (whose presence has triggered many browser bugs). It would also allow using std::string.data() and std::string.size() instead of c_str(), which is theoretically slighty more efficient.

Good to keep in mind, but let's not change the API and implementation at the same time, it would interfere with testing :)

The code looks straightforward and correct to me. It passes the tests and we have a fairly good testing suite in place for the Base58 functions.

luke-jr commented at 6:02 AM on April 14, 2014: member

Why reimplement DecodeBase58 and contribute to the current de-modularisation? Seems like a better idea to move libblkmaker's base58.c to its own library and add an encoder...

gmaxwell commented at 6:09 AM on April 14, 2014: contributor

A library for 74 lines of trivial code? It's kind of an odd duck, in that I don't know what else I'd put in a library with it except 'generic bitcoin stuff'.

laanwj commented at 6:14 AM on April 14, 2014: member

We definitely should move the Base58 stuff to a library when we library-ize Bitcoin Core. It's one of the useful functions for other projects. Removing the dependency on OpenSSL helps there, too.

However I certainly don't want to add a dependency on an external library for this (trivial) functionality.

luke-jr commented at 6:19 AM on April 14, 2014: member

@gmaxwell Everything needed to create a raw transaction spending to an address? :)

in src/base58.cpp:None in 6f55ae1898 outdated

  40 | +    // Skip spaces at the end.
  41 | +    while (isspace(*psz))
  42 | +        psz++;
  43 | +    if (*psz != 0)
  44 | +        return false;
  45 | +    // Skip header zeroes in b256.

laanwj commented at 7:15 AM on April 14, 2014:

I'd say 'leading zeroes'

sipa commented at 9:58 AM on April 14, 2014:

Done.

in src/base58.cpp:None in 6f55ae1898 outdated

  33 | +        for (std::vector<unsigned char>::reverse_iterator it = b256.rbegin(); it != b256.rend(); it++) {
  34 | +            carry += 58 * (*it);
  35 | +            *it = carry % 256;
  36 | +            carry /= 256;
  37 | +        }
  38 | +        psz++;

laanwj commented at 7:29 AM on April 14, 2014:

maybe add assert(carry == 0); to catch a bug that causes an overflow (same in EncodeBase58)

sipa commented at 9:58 AM on April 14, 2014:

Done.

sipa commented at 9:59 AM on April 14, 2014: member

@laanwj: I agree that the interface is dangerous (and inconsistent too... mixing c++ style and c style strings/iteration). I'd like to replace that, but let's do that separately.

I've addresses your comments too.

laanwj commented at 7:00 AM on April 16, 2014: member

ACK

laanwj commented at 7:07 AM on April 19, 2014: member

Needs rebase after #4014 (should be easy as it only affected comments)

sipa commented at 8:49 AM on April 19, 2014: member

Rebased.

in src/base58.cpp:None in 57e709a6e1 outdated

  21 | +        zeroes++;
  22 | +        psz++;
  23 | +    }
  24 | +    // Allocate enough space in big-endian base256 representation.
  25 | +    std::vector<unsigned char> b256;
  26 | +    b256.resize(strlen(psz) * 733 / 1000 + 1); // log(58) / log(256), rounded up.

theuni commented at 4:59 AM on April 22, 2014:

std::vector<unsigned char> b256(strlen(psz) * 733 / 1000 + 1)

Would avoid a realloc.

sipa commented at 7:03 AM on April 22, 2014:

I don't think empty-constructed vector do any allocation. Still, it can be written in one line.

in src/base58.cpp:None in 57e709a6e1 outdated

  11 | +/* All alphanumeric characters except for "0", "I", "O", and "l" */
  12 | +static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
  13 | +
  14 | +bool DecodeBase58(const char *psz, std::vector<unsigned char>& vch) {
  15 | +    // Skip leading spaces.
  16 | +    while (isspace(*psz))

theuni commented at 5:01 AM on April 22, 2014:

possible null pointer dereference?

sipa commented at 7:07 AM on April 22, 2014:

No, psz can't be NULL.

If you mean possible read beyond the end of the string: no, while(isspace ()) will stop at the terminating 0.

Reasons like this is why methods like these should use proper C++ techniques (use std::string, or at least begin/end iterators). But I prefer doing that separately, and not changing their interface now.

in src/base58.cpp:None in 57e709a6e1 outdated

  57 | +}
  58 | +
  59 | +std::string EncodeBase58(const unsigned char* pbegin, const unsigned char* pend) {
  60 | +    // Skip & count leading zeroes.
  61 | +    int zeroes = 0;
  62 | +    while (pbegin != pend && *pbegin == 0) {

theuni commented at 5:06 AM on April 22, 2014:

possible null pointer dereference?

sipa commented at 7:09 AM on April 22, 2014:

If you're passing in NULL, sure. Adding a comment in the .h file.

in src/base58.cpp:None in 57e709a6e1 outdated

  62 | +    while (pbegin != pend && *pbegin == 0) {
  63 | +        pbegin++;
  64 | +        zeroes++;
  65 | +    }
  66 | +    // Allocate enough space in big-endian base58 representation.
  67 | +    std::vector<unsigned char> b58;

theuni commented at 5:09 AM on April 22, 2014:

See previous note. Is there an advantage to using resize() that I'm unaware of?

sipa commented at 7:25 AM on April 22, 2014:

In the current code, not really. I'm changing it to first issue a .reserve(), so that everything happens in one allocation.

in src/base58.cpp:None in 57e709a6e1 outdated

  81 | +    // Skip leading zeroes in base58 result.
  82 | +    std::vector<unsigned char>::iterator it = b58.begin();
  83 | +    while (it != b58.end() && *it == 0)
  84 | +        it++;
  85 | +    // Translate the result into a string.
  86 | +    std::string str;

theuni commented at 5:10 AM on April 22, 2014:

std::string str(zeroes, '1');

sipa commented at 7:25 AM on April 22, 2014:

Also doing a reserve here first.

theuni commented at 5:11 AM on April 22, 2014: member

Sorry for the late review, I was pinged from one of my PRs so I figured I'd give it a quick look :)

sipa commented at 7:27 AM on April 22, 2014: member

Pushed an update to address @theuni's comments.

Replace DecodeBase58/EncodeBase58 with direct implementation.

This removes the bignum/OpenSSL dependency.

The base58 transformation code is also moved to a separate .cpp file.

b58be132c9

gmaxwell commented at 7:57 AM on April 22, 2014: contributor

Thought I ACKed this already.

gmaxwell referenced this in commit e2bff7df08 on Apr 22, 2014

gmaxwell merged this on Apr 22, 2014

gmaxwell closed this on Apr 22, 2014

BitcoinPullTester commented at 8:07 AM on April 22, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/b58be132c994b6f9b25cb4a702186ef96104953f for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

laanwj referenced this in commit 4def248b2b on May 9, 2014

DrahtBot locked this on Sep 8, 2021