[tor-dev] [RFC] Proposal for the encoding of prop224 onion addresses

[Ian Goldberg]

On Mon, Jan 23, 2017 at 03:36:07PM +0200, George Kadianakis wrote:
> [D2] Checksum strength:
> 
>       In the suggested scheme we use a hash-based checksum of two bytes (16 bits).
>       This means that in case of an address typo, we have 1/65536 probability
>       to not detect the error (false negative). It also means that after 256
>       typos we will have 50% probability to miss an error (happy birthday!).

That doesn't sound right to me.  We're not comparing onion addresses
with each other; we're looking at them one at a time.  Birthday would
come in, for example, if we're asking "How many onion addresses would we
need to see before two have the same checksum?".  But if each false
negative happens with probability 1/65536 (which is correct), then it's
just the straightforward 32768 typos before we have 50% probability to
miss an error.

>       I feel like the above numbers are pretty good given the small checksum size.

Agree.

>       The alternative would be to make the checksum four bytes (like in
>       Bitcoin).  This would _greatly_ increase the strength of our checksum but
>       it would also increase our address length by 4 base32 characters (and
>       also force us to remove leading padding from base32 output). This is how
>       these 60-character addresses look like:
> 
>          tc2dty3zowj6oyhbyb5n3a2h3luztlx22hy2cwdvn37omsv7quy7rxiysn3a.onion
>          tbdczrndtadzdhb6iyemnxf7f4i6x7yojnunarlrvt2virtmrecmwgx5golq.onion
>          tc6pcgyorusw3jj5tosxakmcwfmcend2q4g2qnbjtkhuuh4dcgvs4rl4rdaa.onion
> 
>       You probably don't notice the size difference compared to the
>       56-character addresses, which perhaps is an argument for adopting a four
>       byte checksum. Let me know what you think about this.

Seems unnecessary to me.

> [D3] Do we like base32???
> 
>       In this proposal I suggest we keep the base32 encoding since we've been
>       using it for a while; but this is the perfect time to switch if we feel
>       the need to.
> 
>       For example, Bitcoin is using base58 which is much more compact than
>       base32, and also has much better UX properties than base64:
>          https://en.bitcoin.it/wiki/Base58Check_encoding#Background
> 
>       If we wanted to get a more compact encoding, we could adopt base58 or
>       make our own adaptation of it. In this proposal I'm using base32 for
>       everything, but I could be persuaded that now is the time to use a better
>       encoding.

Using base58 is likely to be fraught, since DNS names are "supposed" to
be case-insensitive; this onion address takes the place of a DNS name,
and who knows what software will just assume it's also case-insensitive.

   - Ian