Remove dependency of base58 on OpenSSL

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: 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: 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: 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:

0std::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: 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: 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: 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: 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

Remove dependency of base58 on OpenSSL #4048