6 ms·

Base58

95 points by mrzool 8y ago

adzm 8y ago
I love interesting representations of binary data, base 58 included, but this article is so scant on details. I'm sure someone could even add a brief overview of the algorithm and samples and it's limitations and idiosyncrasies, such as how it handles things like padding etc.
- lifthrasiir 8y ago
  I think the article is good as is, because base58 is actually pretty dissimilar to most binary-to-text encodings. Surprisingly many encodings are just base 2^k (16, 32, 64 and 128 [1]), some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units). This is because binary-to-text encodings are not expected to use costly bigint operations for an arbitrary-length payload. Base36 and base58 are the only common exceptions, and for this reason I actually think that they should be termed "bigint-to-text" encodings. Given that base58 is actually just a big number with translated digits, the list of alphabets (actually, digits) is almost enough to decode base58 encodings. There is always an exception, of course: Bitcoin base58 calculates a minimal length from the original payload length so that it has to be "zero"-padded with one (which is the first alphabet, thus acts as a digit zero) [2]. This preserves the original payload length, but is still quadratically expensive and should be used for a reasonably short, known-length data like hashes. [1] This is actually not normally viable as a binary-to-text encoding, but base122 (http://blog.kevinalbs.com/base122 http://blog.kevinalbs.com/base122) does use this to exploit UTF-8 encoding. [2] https://en.bitcoin.it/wiki/Base58Check_encoding https://en.bitcoin.it/wiki/Base58Check_encoding (note that I've used a significantly simpler explanation here, the gist is same however)
  - eesmith 8y ago
    "Base36 and base58 are the only common exceptions" Isn't Ascii85/Base85 at least as common as those? Quoting the Wikipedia entry for it, "Its main modern uses are in Adobe's PostScript and Portable Document Format file formats, as well as in the patch encoding for binary files used by Git" Python includes it as part of the standard library. Using the example from the WP entry: >>> s = r"""<~9jqo^BlbD-BleB1DJ+*+F(f,q/0JhKF<GL>Cj@.4Gp$d7F!,L7@<6@)/0JDEF<G%<+EV:2F!, ... O<DJ+*.@<*K0@<6L(Df-\0Ec5e;DffZ(EZee.Bl.9pF"AGXBPCsi+DGm>@3BB/F*&OCAfu2/AKY ... i(DIb:@FD,*)+C]U=@3BN#EcYf8ATD3s@q?d$AftVqCh[NqF<G:8+EV:.+Cf>-FD5W8ARlolDIa ... l(DId<j@<?3r@:F%a+D58'ATD4$Bl@l3De:,-DJs`8ARoFb/0JMK@qB4^F!,R<AKZ&-DfTqBG%G ... >uD.RTpAKYo'+CT/5+Cei#DII?(E,9)oF*2M7/c~>""" >>> import base64 >>> base64.a85decode(s, adobe=True) b'Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.'
    - lifthrasiir 8y ago
      I have explicitly mentioned this: > [...] some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units). Base 85 does not use bigint, it is just a clever approximation of optimal encoding with 85 symbols.
      - eesmith 8y ago
        I think I was confused between "baseX" as the specific program name and 'base X' as the base of the specific numbering system.
- jerf 8y ago
  The best-kept secret Wikipedia is the references section. First reference probably answers all your questions. For those of you still in school, this is also how you "get around" the "Don't use Wikipedia" restriction on your school reports. You go to the Wikipedia article for whatever it is you're writing about, ignore it entirely and scroll down to the References, and go to town on those. 10 seconds of "research" and you've almost certainly got enough primary sources lined up to finish your report unless this is a thesis-level job. I scare-quote "get around" because this isn't even really "cheating", unless you're doing the assignment where you're explicitly instructed to use the library lookup system, in which case of course it is.
gallerdude 8y ago
There are many dimensions to utility.
decentralised 8y ago
Why base-58 instead of standard base-64 encoding? - Don't want 0OIl characters that look the same in some fonts and could be used to create visually identical looking data. - A string with non-alphanumeric characters is not as easily accepted as input. - E-mail usually won't line-break if there's no punctuation to break at. - Double-clicking selects the whole string as one word if it's all alphanumeric. https://github.com/bitcoin/bitcoin/blob/master/src/base58.h https://github.com/bitcoin/bitcoin/blob/master/src/base58.h
- athenot 8y ago
  This is a similar encoding as airline reservation numbers, except it also has lowercase characters. But the requirements are very similar. It's amazing how much confusion is removed by suppressing ambiguities between number 0 vs. letter O and number 1 vs. letter I. For reservation numbers, doing away with case makes it easier to speak the number over the phone.
  - jimktrains2 8y ago
    Crockford base32?
  - decentralised 8y ago
    It's amazing how user experience can be affected from this deep in the stack.
  - kulahan 8y ago
    It might be interesting to see a form of encoding that removes similar-sounding letters/numbers as well. No more "A" or "J", "B" or "D", "3" or "T" confusion. Just stuff with a distinct sound!
- strainer 8y ago
  Knocking out similar characters is a good idea but could be done to base32 to make it a little handier. I don't feel adding case sensitivity is worth a 15% reduction in string length.
classichasclass 8y ago
I'm actually using base 58 to encode numbers for the gopher URL shortner with the Ripple alphabet. It works as advertised, and is great for an old protocol like this. gopher://fld.gp/1/gopher/shorten (shortened URL example: gopher://fld.gp/1j/r or http://fld.gp/1j/r http://fld.gp/1j/r )
TazeTSchnitzel 8y ago
Reminds me of Crockford's https://www.crockford.com/wrmg/base32.html https://www.crockford.com/wrmg/base32.html
- nayuki 8y ago
  When the new SegWit feature was introduced to Bitcoin, it came with a new address format called Bech32. https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0173.mediawi...
dtf 8y ago
Not to be confused with Base85. https://en.wikipedia.org/wiki/Ascii85 https://en.wikipedia.org/wiki/Ascii85 (used with various alphabets for denser binary encoding in PDF, git binary patches, and the scene files of the Arnold renderer).
- stcredzero 8y ago
  In my personal project, I'm using my own Base92 encoding. I wonder why Base85 stops at 85? In particular, you can implement Base92 with one table lookup and one conditional exception. (Which could also be implemented as a table lookup to save branch prediction misses.)
manigandham 8y ago
Neat. Side note, there's another project called HashIds with many language implementations for encoding integers (or array of integers) into simple alphanumeric strings, and decoding back again. https://hashids.org/ https://hashids.org/
diggan 8y ago
If you can't get enough of Base-encodings, there is a project called "multibase" (https://github.com/multiformats/multibase https://github.com/multiformats/multibase) that lets you encode which Base-encoding you are using, together with the data itself, so it's easier to know what data you are received/sending. The basic format is `<varint-base-encoding-code><base-encoded-data>` and the "varint-base-encoding-code" comes from https://github.com/multiformats/multibase/blob/master/multibase.csv https://github.com/multiformats/multibase/blob/master/multib...
_eht 8y ago
I'm more of a fan of BasE91 and I believe more people should be using it.
- gpvos 8y ago
  Why? It's only a minuscule improvement over ASCII85, which is a well-established encoding. I couldn't find a rationale for it anywhere.
ur-whale 8y ago
Base58 isn't a great choice from an implementation point of view. It basically requires a bignum library (or a specialized version that can do divisions of arbitrary long numbers by 58), and conversion is slow as hell. Either you end up pulling in a full bignum library, or you have to use error-prone, clunky specialized code you don't have time to try and understand and verify. Of all the design choices Satoshi made, this is far from the best one.
- eesmith 8y ago
  The implementations at https://github.com/search?q=Base58 https://github.com/search?q=Base58 don't look like they use a bignum package, nor do that look particularly slow or complicated. The main encoding loop for https://github.com/luke-jr/libbase58/blob/master/base58.c https://github.com/luke-jr/libbase58/blob/master/base58.c is: for (i = zcount, high = size - 1; i < binsz; ++i, high = j) { for (carry = bin[i], j = size - 1; (j > high) || carry; --j) { carry += 256 * buf[j]; buf[j] = carry % 58; carry /= 58; } }
  - ur-whale 8y ago
    There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.
    - ChrisLomont 8y ago
      That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems. Many compilers even expand the code inline to generate fix size divides into mult and shift. Here's a 4 year old Hacker news thread on compiler tricks then [1]. They're even better now. [1] https://news.ycombinator.com/item?id=8368639 https://news.ycombinator.com/item?id=8368639
      - 8y ago
carapace 8y ago
oO0 I1l B8 S5 b6G
eknkc 8y ago
Take a look at the node js library ‘base-x’ https://github.com/cryptocoinjs/base-x https://github.com/cryptocoinjs/base-x Which can do base58 and any base you throw at it using the same algorithm.
adambrenecki 8y ago
Another neat encoding is the base-20 character set that Open Location Codes ("plus codes") use: > The characters that are used in Open Location Codes were chosen by computing all possible 20 character combinations from 0-9A-Z and scoring them on how well they spell 10,000 words from over 30 languages. This was to avoid, as far as possible, Open Location Codes being generated that included recognisable words. The selected 20 character set is made up of "23456789CFGHJMPQRVWX". https://github.com/google/open-location-code/blob/master/docs/olc_definition.adoc#open-location-code https://github.com/google/open-location-code/blob/master/doc...
wizawu 8y ago
I've replaced UUID v4 with nanoid + base58 in the last several projects. https://www.npmjs.com/package/nanoid-base58 https://www.npmjs.com/package/nanoid-base58
- GordonS 8y ago
  What's the advantage here?

95 points by mrzool 8y ago

adzm 8y ago

I love interesting representations of binary data, base 58 included, but this article is so scant on details. I'm sure someone could even add a brief overview of the algorithm and samples and it's limitations and idiosyncrasies, such as how it handles things like padding etc.

lifthrasiir 8y ago
I think the article is good as is, because base58 is actually pretty dissimilar to most binary-to-text encodings. Surprisingly many encodings are just base 2^k (16, 32, 64 and 128 [1]), some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units). This is because binary-to-text encodings are not expected to use costly bigint operations for an arbitrary-length payload. Base36 and base58 are the only common exceptions, and for this reason I actually think that they should be termed "bigint-to-text" encodings. Given that base58 is actually just a big number with translated digits, the list of alphabets (actually, digits) is almost enough to decode base58 encodings. There is always an exception, of course: Bitcoin base58 calculates a minimal length from the original payload length so that it has to be "zero"-padded with one (which is the first alphabet, thus acts as a digit zero) [2]. This preserves the original payload length, but is still quadratically expensive and should be used for a reasonably short, known-length data like hashes. [1] This is actually not normally viable as a binary-to-text encoding, but base122 (http://blog.kevinalbs.com/base122 http://blog.kevinalbs.com/base122) does use this to exploit UTF-8 encoding. [2] https://en.bitcoin.it/wiki/Base58Check_encoding https://en.bitcoin.it/wiki/Base58Check_encoding (note that I've used a significantly simpler explanation here, the gist is same however)
- eesmith 8y ago
  "Base36 and base58 are the only common exceptions" Isn't Ascii85/Base85 at least as common as those? Quoting the Wikipedia entry for it, "Its main modern uses are in Adobe's PostScript and Portable Document Format file formats, as well as in the patch encoding for binary files used by Git" Python includes it as part of the standard library. Using the example from the WP entry: >>> s = r"""<~9jqo^BlbD-BleB1DJ+*+F(f,q/0JhKF<GL>Cj@.4Gp$d7F!,L7@<6@)/0JDEF<G%<+EV:2F!, ... O<DJ+*.@<*K0@<6L(Df-\0Ec5e;DffZ(EZee.Bl.9pF"AGXBPCsi+DGm>@3BB/F*&OCAfu2/AKY ... i(DIb:@FD,*)+C]U=@3BN#EcYf8ATD3s@q?d$AftVqCh[NqF<G:8+EV:.+Cf>-FD5W8ARlolDIa ... l(DId<j@<?3r@:F%a+D58'ATD4$Bl@l3De:,-DJs`8ARoFb/0JMK@qB4^F!,R<AKZ&-DfTqBG%G ... >uD.RTpAKYo'+CT/5+Cei#DII?(E,9)oF*2M7/c~>""" >>> import base64 >>> base64.a85decode(s, adobe=True) b'Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.'
  - lifthrasiir 8y ago
    I have explicitly mentioned this: > [...] some have converged to base 85 (because 85^5 / 2^32 ~= 1.03, i.e. just enough to represent 4 octets in 5 units). Base 85 does not use bigint, it is just a clever approximation of optimal encoding with 85 symbols.
    - eesmith 8y ago
      I think I was confused between "baseX" as the specific program name and 'base X' as the base of the specific numbering system.
jerf 8y ago
The best-kept secret Wikipedia is the references section. First reference probably answers all your questions. For those of you still in school, this is also how you "get around" the "Don't use Wikipedia" restriction on your school reports. You go to the Wikipedia article for whatever it is you're writing about, ignore it entirely and scroll down to the References, and go to town on those. 10 seconds of "research" and you've almost certainly got enough primary sources lined up to finish your report unless this is a thesis-level job. I scare-quote "get around" because this isn't even really "cheating", unless you're doing the assignment where you're explicitly instructed to use the library lookup system, in which case of course it is.

gallerdude 8y ago

There are many dimensions to utility.

decentralised 8y ago

Why base-58 instead of standard base-64 encoding? - Don't want 0OIl characters that look the same in some fonts and could be used to create visually identical looking data. - A string with non-alphanumeric characters is not as easily accepted as input. - E-mail usually won't line-break if there's no punctuation to break at. - Double-clicking selects the whole string as one word if it's all alphanumeric. https://github.com/bitcoin/bitcoin/blob/master/src/base58.h https://github.com/bitcoin/bitcoin/blob/master/src/base58.h

athenot 8y ago
This is a similar encoding as airline reservation numbers, except it also has lowercase characters. But the requirements are very similar. It's amazing how much confusion is removed by suppressing ambiguities between number 0 vs. letter O and number 1 vs. letter I. For reservation numbers, doing away with case makes it easier to speak the number over the phone.
- jimktrains2 8y ago
  Crockford base32?
- decentralised 8y ago
  It's amazing how user experience can be affected from this deep in the stack.
- kulahan 8y ago
  It might be interesting to see a form of encoding that removes similar-sounding letters/numbers as well. No more "A" or "J", "B" or "D", "3" or "T" confusion. Just stuff with a distinct sound!
strainer 8y ago
Knocking out similar characters is a good idea but could be done to base32 to make it a little handier. I don't feel adding case sensitivity is worth a 15% reduction in string length.

classichasclass 8y ago

I'm actually using base 58 to encode numbers for the gopher URL shortner with the Ripple alphabet. It works as advertised, and is great for an old protocol like this. gopher://fld.gp/1/gopher/shorten (shortened URL example: gopher://fld.gp/1j/r or http://fld.gp/1j/r http://fld.gp/1j/r )

TazeTSchnitzel 8y ago

Reminds me of Crockford's https://www.crockford.com/wrmg/base32.html https://www.crockford.com/wrmg/base32.html

nayuki 8y ago
When the new SegWit feature was introduced to Bitcoin, it came with a new address format called Bech32. https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0173.mediawi...

dtf 8y ago

Not to be confused with Base85. https://en.wikipedia.org/wiki/Ascii85 https://en.wikipedia.org/wiki/Ascii85 (used with various alphabets for denser binary encoding in PDF, git binary patches, and the scene files of the Arnold renderer).

stcredzero 8y ago
In my personal project, I'm using my own Base92 encoding. I wonder why Base85 stops at 85? In particular, you can implement Base92 with one table lookup and one conditional exception. (Which could also be implemented as a table lookup to save branch prediction misses.)

manigandham 8y ago

Neat. Side note, there's another project called HashIds with many language implementations for encoding integers (or array of integers) into simple alphanumeric strings, and decoding back again. https://hashids.org/ https://hashids.org/

diggan 8y ago

If you can't get enough of Base-encodings, there is a project called "multibase" (https://github.com/multiformats/multibase https://github.com/multiformats/multibase) that lets you encode which Base-encoding you are using, together with the data itself, so it's easier to know what data you are received/sending. The basic format is `<varint-base-encoding-code><base-encoded-data>` and the "varint-base-encoding-code" comes from https://github.com/multiformats/multibase/blob/master/multibase.csv https://github.com/multiformats/multibase/blob/master/multib...

_eht 8y ago

I'm more of a fan of BasE91 and I believe more people should be using it.

gpvos 8y ago
Why? It's only a minuscule improvement over ASCII85, which is a well-established encoding. I couldn't find a rationale for it anywhere.

ur-whale 8y ago

Base58 isn't a great choice from an implementation point of view. It basically requires a bignum library (or a specialized version that can do divisions of arbitrary long numbers by 58), and conversion is slow as hell. Either you end up pulling in a full bignum library, or you have to use error-prone, clunky specialized code you don't have time to try and understand and verify. Of all the design choices Satoshi made, this is far from the best one.

eesmith 8y ago
The implementations at https://github.com/search?q=Base58 https://github.com/search?q=Base58 don't look like they use a bignum package, nor do that look particularly slow or complicated. The main encoding loop for https://github.com/luke-jr/libbase58/blob/master/base58.c https://github.com/luke-jr/libbase58/blob/master/base58.c is: for (i = zcount, high = size - 1; i < binsz; ++i, high = j) { for (carry = bin[i], j = size - 1; (j > high) || carry; --j) { carry += 256 * buf[j]; buf[j] = carry % 58; carry /= 58; } }
- ur-whale 8y ago
  There's a divmod by 58 in there. That's dog slow compared to the shifts a power of two basis would require - even when the compiler gets smart about it because it's a constant.
  - ChrisLomont 8y ago
    That divmod can be replaced with table walking like CRC code does for division and remainder of fixed values, which is certainly fast, and does not require bignums. Unless you now want to claim all CRC code is also slow as hell or requires bignums. These are solved problems. Many compilers even expand the code inline to generate fix size divides into mult and shift. Here's a 4 year old Hacker news thread on compiler tricks then [1]. They're even better now. [1] https://news.ycombinator.com/item?id=8368639 https://news.ycombinator.com/item?id=8368639
    - 8y ago

carapace 8y ago

oO0 I1l B8 S5 b6G

eknkc 8y ago

Take a look at the node js library ‘base-x’ https://github.com/cryptocoinjs/base-x https://github.com/cryptocoinjs/base-x Which can do base58 and any base you throw at it using the same algorithm.

adambrenecki 8y ago

Another neat encoding is the base-20 character set that Open Location Codes ("plus codes") use: > The characters that are used in Open Location Codes were chosen by computing all possible 20 character combinations from 0-9A-Z and scoring them on how well they spell 10,000 words from over 30 languages. This was to avoid, as far as possible, Open Location Codes being generated that included recognisable words. The selected 20 character set is made up of "23456789CFGHJMPQRVWX". https://github.com/google/open-location-code/blob/master/docs/olc_definition.adoc#open-location-code https://github.com/google/open-location-code/blob/master/doc...

wizawu 8y ago

I've replaced UUID v4 with nanoid + base58 in the last several projects. https://www.npmjs.com/package/nanoid-base58 https://www.npmjs.com/package/nanoid-base58

GordonS 8y ago
What's the advantage here?