There are many dimensions:
Thanks for the summary:
1. Do we want the ability to encode all outputs in the blockchain, or just some of it (say, only the first 4 outputs in all txs)? hhanh00's scheme is easier to implement as it only encodes the first 4 outputs in a tx. My scheme is more complex and the length of all components are variable.
I guess the "target audience" is what matters (for me 4 outputs would be fine as I would be using it for "cold storage" which would have generally only 1 output anyway).
2. hhanh00's address is shorter than mine in some case, while the opposite in some other case.
I think 5 "words" is fine (whichever approach).
3. How many bits of checksum is needed? I proposed 20bits so the error tolerance is about 1 in a million. Should we use more? Could we squeeze a few bits for other purpose? (Satoshi used 32 bits in standard bitcoin address.)
As many as possible without adding an extra word.
4. Do we need a version bit (like in standard bitcoin address)? It will occupy 1 bit (which could be otherwise used for other purpose. In order to keep the address short, every bit is very valuable) but it makes potential future upgrade easier. Otherwise, future upgrade will need to use 2048 completely different words, or people have to denote the version of the address externally (e.g. using a URL like header)
A version bit seems reasonable to me.
5. Do we want miner to have the ability to mine a vanity address? My scheme disallows it in response to gmaxwell's comments (see first page). The other scheme allows miners to mine vanity address.
I am not quite sure of the implications of this - but it would be better to probably not allow it.
6. Do we want the addresses look like random (i.e. outputs/txs close to each other will have statistically unrelated addresses) or not?
If the point is to help someone remember the address then random is better so they don't get confused IMO.