4 ms·

Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. Base32 doesn't have that p

by sedatk 6y ago

Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. Base32 doesn't have that problem.

floatingatoll 6y ago
Note, though, that content of a length sufficient to result in that performance degradation would not be "human-friendly" — and thus, not a viable use case for Base32H as it's specified here — no matter whether a 32 or 53 or whatever-base encoding scheme is used. (Technically, a book can be considered 'human friendly', but that's not the definition OP is using for that phrase, either.)
- yellowapple 6y ago
  To be clear, long Base32H numbers are definitely in scope (which is why the specification "recommends" a binary encoding scheme for this exact purpose, and why things like public keys/signatures are mentioned among the proposed use cases). Yeah, it'd suck for a human to have to manually record or dictate large-ish (more than 1kb / 1600 digits) sets of data, but it sucks at least a little bit less when you already know that everything can be assumed to be uppercase.
lifthrasiir 6y ago
> Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. This comment only applies to a naive scheme. There are various ways to avoid performance degradation with a minimal overhead; grouping characters so that they can represent (only slightly more than) the integral number of full bits is frequent.
- sedatk 6y ago
  Bitcoin uses the naive scheme, why?
  - lifthrasiir 6y ago
    Probably because: 1. There is no small power of 58 that is only slightly more than integral powers of 256. The closest one I can imagine is 57^11 ~= 1.1186 * 2^64. 2. Bitcoin addresses are short enough that trivial bignum calculation is not a bottleneck.
Thorrez 6y ago
Exponential? I would assume it would be more like O(n^3) or less, where n is the number of bits of the input.
- sedatk 6y ago
  Yes, polynomial would be more accurate, and I think it's O(N^2).
- dheera 6y ago
  You can also use it in a practically linear way, i.e. O(N*M^2) if you break your input into chunks of fixed size M and accept a very slight overhead in wasted bits.
nullc 6y ago
> Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. Only with an absurdly naive implementation. Base conversion with arbitrary (and even mixed) base can be done in entirely linear time. Base58 doesn't work that great for a wide collection of uses because the mixed case makes it extremely slow for e.g. spoken use. More modern Bitcoin addresses use BECH32 (https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0173.mediawi... a base 32-scheme whos characters and permutation were selected via machine optimization against a confusion matrix, in order to minimize the number of bit errors made by human transcription. It incorporates an error correcting scheme that adds 6 extra characters and guarantees detecting up-to 4 substitutions or transpositions (or 5 substitutions if they're all hamming-1 errors, such as q vs g, z vs 2, u vs v, etc.).
- sedatk 6y ago
  > Base conversion with arbitrary (and even mixed) base can be done in entirely linear time. Are you saying Bitcoin uses an O(N^2) implementation because they are naive? You need to propagate carry to the rest of the digits. I wonder how it’s possible for Base58 to be implemented in linear time. Do you have any sources I can read?
  - nullc 6y ago
    Bitcoin doesn't use base-58 in any performance relevant way, it's only used for user interfacy sort of stuff. Probably the most straight forward way to make fast base conversion is the way that most range coders in compression (which are effectively just fancy mixed-radix base converters) do it-- first store temporary digits of a larger size so that the there won't be any inter-digit carries, then make a second pass through to propagate the carries and generate the output. IIRC the approach in bitcoin core is related-- but it processes the carries eagerly rather than deferring them (which makes it asymptotically quadratic (the worst case), but the average case is fast).

by sedatk 6y ago

Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. Base32 doesn't have that problem.

floatingatoll 6y ago

Note, though, that content of a length sufficient to result in that performance degradation would not be "human-friendly" — and thus, not a viable use case for Base32H as it's specified here — no matter whether a 32 or 53 or whatever-base encoding scheme is used. (Technically, a book can be considered 'human friendly', but that's not the definition OP is using for that phrase, either.)

yellowapple 6y ago
To be clear, long Base32H numbers are definitely in scope (which is why the specification "recommends" a binary encoding scheme for this exact purpose, and why things like public keys/signatures are mentioned among the proposed use cases). Yeah, it'd suck for a human to have to manually record or dictate large-ish (more than 1kb / 1600 digits) sets of data, but it sucks at least a little bit less when you already know that everything can be assumed to be uppercase.

lifthrasiir 6y ago

> Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. This comment only applies to a naive scheme. There are various ways to avoid performance degradation with a minimal overhead; grouping characters so that they can represent (only slightly more than) the integral number of full bits is frequent.

sedatk 6y ago
Bitcoin uses the naive scheme, why?
- lifthrasiir 6y ago
  Probably because: 1. There is no small power of 58 that is only slightly more than integral powers of 256. The closest one I can imagine is 57^11 ~= 1.1186 * 2^64. 2. Bitcoin addresses are short enough that trivial bignum calculation is not a bottleneck.

Thorrez 6y ago

Exponential? I would assume it would be more like O(n^3) or less, where n is the number of bits of the input.

sedatk 6y ago
Yes, polynomial would be more accurate, and I think it's O(N^2).
dheera 6y ago
You can also use it in a practically linear way, i.e. O(N*M^2) if you break your input into chunks of fixed size M and accept a very slight overhead in wasted bits.

nullc 6y ago

> Base58 isn't suitable for general purpose encoding though as its performance degrades exponentially based on the length of the input. Only with an absurdly naive implementation. Base conversion with arbitrary (and even mixed) base can be done in entirely linear time. Base58 doesn't work that great for a wide collection of uses because the mixed case makes it extremely slow for e.g. spoken use. More modern Bitcoin addresses use BECH32 (https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0173.mediawi... a base 32-scheme whos characters and permutation were selected via machine optimization against a confusion matrix, in order to minimize the number of bit errors made by human transcription. It incorporates an error correcting scheme that adds 6 extra characters and guarantees detecting up-to 4 substitutions or transpositions (or 5 substitutions if they're all hamming-1 errors, such as q vs g, z vs 2, u vs v, etc.).

sedatk 6y ago
> Base conversion with arbitrary (and even mixed) base can be done in entirely linear time. Are you saying Bitcoin uses an O(N^2) implementation because they are naive? You need to propagate carry to the rest of the digits. I wonder how it’s possible for Base58 to be implemented in linear time. Do you have any sources I can read?
- nullc 6y ago
  Bitcoin doesn't use base-58 in any performance relevant way, it's only used for user interfacy sort of stuff. Probably the most straight forward way to make fast base conversion is the way that most range coders in compression (which are effectively just fancy mixed-radix base converters) do it-- first store temporary digits of a larger size so that the there won't be any inter-digit carries, then make a second pass through to propagate the carries and generate the output. IIRC the approach in bitcoin core is related-- but it processes the carries eagerly rather than deferring them (which makes it asymptotically quadratic (the worst case), but the average case is fast).