3 ms·
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
by 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 agoI 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 agoI think I was confused between "baseX" as the specific program name and 'base X' as the base of the specific numbering system.