3 ms·

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

by 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 nullc 6y ago

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).