[tor-dev] Remaining 4 bits in prop224 addresses

[Jesse V]

On 12/06/2016 11:24 AM, George Kadianakis wrote:
> I'd be interested in both a version field and a checksum to be part of
> the encoding of the onion address. I also don't mind extending the
> encoding by a character or two if that will make it more useful (there
> is little difference between 54 and 56 characters).

Sure, I don't see a problem with this. It's unlikely that we will need a
full byte for a version number. What if addresses are 53 characters
long, instead of 52? Now you have nine bits to work with. We could use
four of them for a version number and five for checksum. Alternatively,
if addresses are 54 characters, then we have 14 bits. Then we could use
four or five for versions and 9 or 10 for checksum.

> WRT version field, should it be a single value/bitmap or should it be
> able to denote support for multiple versions?

I'm not entirely sure what you mean by a bitmap here. It's unlikely that
we will need to denote new versions, but if we have some room, it could
be useful in case we need to.

> WRT checksum, how much of the address can we protect using a checksum of
> 1 or 2 bytes? My error-correcting-codes fu is a bit rusty, and I'm not
> sure how many errors we can detect/correct. Anyone can do some digging
> here and prepare a table, so that we can take an informed decision?
> Perhaps the bitcoin community has already done this for us.

We don't have enough room for an error-correcting Hamming code or
something like that. If we do want to use a simple checksum, I'm simply
concerned about ensuring that the address is correct. A simple code
won't be able to prevent from intentional modification, but it can help
with accidental typos to some degree. If we do want to use a checksum, I
suggest that we base it on a cryptographic hash function, such as SHA-2
or SHA-3.

If we use 54-character addresses, then we have room for up to 16
versions, and 10 bits of checksum, which gives us a 1/1024 chance of NOT
identifying a typo, right? Maybe the birthday paradox comes into play here.

-- 
Jesse

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 720 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20161206/1788002a/attachment.sig>