consider getting rid of base58

[MonsieurNicolas]

This is our last chance to do this or we'll regret it forever!

We should use a format like base32-zooko that has nice properties like:

• human friendly (case insensitive, avoids similar characters)
• uses bit wise logic and lookups (simple and fast)

http://philzimmermann.com/docs/human-oriented-base-32-encoding.txt

This would also resolve #273 (where there is no real solution other than use a different encoding in the database).

Here are the differences in size between encodings:
hex => 64 characters
base32 => 51 characters
base64 => 42 characters
base58 => 46 or 47 characters

[jedmccaleb]

rough consensus that we should use the RFC base32 and change the checksum to a normal CRC

[graydon]

I feel like I've been providing all the ammunition on this one, despite not really caring.

Our tendency so far has been to follow RFCs when they exist, so in this case https://tools.ietf.org/html/rfc4648 is the canonical encoding.

If we're going to do this -- especially if speed is any concern -- then we should also get rid of the double-sha256-truncated-to-32-bits "checksum" appended to the identifier. This is a pointlessly overpowered "check" against typos on the part of the user; a simple/cheap CRC32 (ISO 3309 / Gzip algorithm -- tons of libraries do this) or CRC16-CCITT or a check-digit scheme designed to catch real transposition/replacement errors (a la https://en.wikipedia.org/wiki/Check_digit ) is sufficient.

Since we probably want to avoid padding characters (ew =) we will want to land on an encoding-group multiple. Encoding-groups are 40 input bits => 8 output chars we'd probably be fine with 7 groups = 56 output chars = 280 input bits = 8 bits typecode/flags/whatever + 256 bits key + 16 bits CRC?

[MonsieurNicolas]

that sounds good and yes, I came up with the same conclusion on the encoding. with the RFC one it's very easy for somebody to understand which digits are allowed vs not and we avoid pushing logic to clients that would have to deal with denormalized forms.
As for the checksum: CRC-16 seems like a good candidate as, I think, it would basically detect any error of up to 16 bits (which includes any mutation of 3 consecutive digits) and other errors with some good probability.