Hacker News Reader

> This made me think... why are we using long, unwieldy base-16 hex strings at all? Why not use an alphabetic (non-numeric) base-46 string: 20 lowercase letters ([g-z]), 26 capital letters ([A-Z])? Then the new SHA256 hash strings end up being shorter than the old SHA1 strings, and there is no overlap with the [0-9a-f] range of the base-16 strings.

Are you sure? SHA1 hashes are 40 hex digits, and SHA256 hashes are 64 hex digits. But in base 46, 2^256-1 = 3ZS4A7V5Ki0LWg1f3Of06YNfgQXCA2P0Q6RACKhEIWQXe07, which is 47 base-46 digits long, so still longer than SHA1. (This is not your base 46, since it's using 0..9, A..Z, a..j.)

  import gmpy2
  gmpy2.digits(2**256-1, 46)
    -> '3ZS4A7V5Ki0LWg1f3Of06YNfgQXCA2P0Q6RACKhEIWQXe07'
  gmpy2.digits(gmpy2.mpz('f'*64, 16), 46) #same, but more clearly the "maximum" hash

edit: more code to try kelnos's proposed digits:

  gmpy_digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
  new_digits = 'ghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  ''.join(new_digits[gmpy_digits.index(d)] for d in gmpy2.digits(gmpy2.mpz('f'*64, 16), 46))
    -> 'jPIkqnLlAYgBMWhVjEVgmODVWGNsqiFgGmHqsAXuyMGNUgn'

I think hex strings are probably still better, as there's less ambiguity, and 47 characters isn't much shorter than 64 for practical purposes.

One of the mistakes Git made was that the hashes don't describe what algorithm was used to generate them. That makes backward compatibility and incremental upgrades harder. MultiHash is a solution for such issues: https://github.com/multiformats/multihash

You don’t need a specialised solution for this, just prefix the v1 of your hashing algorithm with some constant and then you can easily extend it.

Right. To get 256 bits down to 40 digits to match the length of the current hashes you need to use base 85. To get it shorter you need base 95. There are 94 non-space printing characters in ASCII and I doubt anyone wants to allow spaces so that’s probably out.

Yes, good point, my mental math does not check out.

Not sure what you mean by there being "less ambiguity" with hex strings though. Less ambiguous than what, and how?

If the current hashes are case insensitive (I have never seen a parser that wouldn’t accept both abad1dea and ABAD1DEA (And doing so would be a bad idea imho) then the uppercase A-F would overlap with the sha1 hashes.

A “g” prefix and then either hex or base35 or something similar should do it. It’s pretty annoying without a prefix since without it you can’t say whether a numeric string such as a date actually indicates a hash.

>>> This made me think... why are we using long, unwieldy base-16 hex strings at all?

Surprised you got ten answers to this comment and nobody was able to explain.

Hexadecimal encoding is widely used because computers work with bytes (8 bits). An hexadecimal character is 4 bits, so every byte is two hex characters.

It's trivial to encode (even by hand), it has no issue of padding. It can truly transit through anything that accepts alphanumeric characters. It's awesome.

edit: The most common alternative is base64 that encodes blocks of 3 bytes to 4 characters. Base64 has a bazillion issues due to padding and special characters +/=. If I had a dollar for every system I've seen using broken base64, I could buy a car. Saving a bit of space (200% in hex VS 134% size in base64) is almost never worth an order of magnitude more complexity. Do not invent your own encoding algorithm.

In this specific context though, nobody is going to be manually calculating the binary hash of the source tree and encoding it, so this advantage doesn't seem very relevant.

The proposed solution would still be alphanumeric, so it would share that advantage.

The problem isn't with the algorithm encoding it. The problem is with other software mangling it.

Base 64 has punctuation, it's case sensitive, and trimming a = off the end will (counterintuitively) result in a longer payload. All of this makes screwing around with commit hashes more complicated.

I think you've kind of missed the point, which is that a larger base would mean shorter hash strings.

Using a small base like 16 means the hashes are very long, and awkward to use in full. Using a larger base will make the hash shorter when it's in text form. A text representation of a 256 bit hash in base 16 is 64 characters long, but in base 46 it is only 47 characters long. Using the whole alphabet in lower and upper case, and the digits, would produce base 62, where a 256 bit hash would be 43 digits long.

Still a bit big and unwieldy IMHO, so sticking with hexadecimal seems sensible given its other advantages.

> Hexadecimal encoding is widely used because computers work with bytes (8 bits). An hexadecimal character is 4 bits, so every byte is two hex characters.

Yes, I'm aware (that electrical & computer engineering degree I have is occasionally good for something ;) ).

But the dominating factor in hashing a bunch of data is the hash function itself, not converting it into something displayable. Converting between binary and hex vs. binary and some other base string is optimizing the wrong part of the process.

And who is converting SHA1 hashes between hex and binary by hand? That doesn't seem like a thing people do.

Case is really annoying to deal with. The string form is for humans to read and type, among other things.

So that leaves you somewhere around base 32, which is fine but isn't a huge benefit over hex, and hex has the benefit of being standard.

> Case is really annoying to deal with. The string form is for humans to read and type, among other things.

If anyone is frequently typing out SHA1 hex strings by hand, that would be news to me.

Good idea!

Your downside is a major concern, but it would take all of 5 minutes to patch sha256sum to have a new output format, and another 3 months to have a PR approved. Ditto for most libraries, except where written into standards (and I'm not sure if that's anywhere). I'd expect Python 3.9 to not be a problem either. So it's not a big deal to address the concern.

If you want to do this well, though, the trick would be to come up with a human-friendly format. You can't use both '0' and 'O.' You can't use '1,' 'l,' and 'I.' Invest the time to do HCI work.

And, ideally, you'd have some form of internal check-summing, so you can easily flag most typos.

Performance is NOT a concern. Some folks here mentioned the some encoding formats are table lookups. In most cases, generating or verifying a cryptographically-secure hash is many orders of magnitude slower than an encode/decode of the key into any format. And if you're not generating/verifying, in most cases, it doesn't make any sense to encode/decode (just pass around the encoded key).

The human friendly format you're suggesting is Douglas Crockford' Base 32 encoding.

I disagree that his encoding is friendly.

I understand the compromises he made in order to make it less ambiguous, but regular users come across hashes sometimes, and unless you know it's his encoding, they're (often) smart enough to know that some characters look like others. So, when they go to recite the encoded value, they're still going to struggle "is that a 0 or an O?" etc.

We may know it doesn't make a difference, but someone who doesn't know it's explicitly his encoding (and the parameters he transposes) is still going to get hung up.

Lastly, the removal of "u" only prevents 1.5 offensive words from showing up, but I guess he chose it because he had to get rid of some letter to make it base32.

I think a base ~32 by removing all ambiguous characters and adding a non-separator punctuation mark would be ideal, frankly.

If we're worried about swear words then also remove the vowels and add 4 more punctuation mark.

IMHO

That's a !@#$ good idea for avoiding swear words :)

The larger alphabet codes are unwieldy to type/read out loud. Past 10+26=36 you run out of decent symbols (making case significant is not user fiendly), and even in that range you have confusing pairs like 1iI 0o.

My personal favorite is z-base-32. It has none of those issues, and is much more compact than hex. It's the perfect in-between.

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

Base-32 just encodes one more bit per symbol (5 instead of the 4 per symbol that hex does), so the improvement is rather minor.

52 characters vs 64 characters for a 32-byte public key is a decent improvement if you ask me. Or, more to the point, aiming for anything denser makes the alphabet less friendly.

the more characters you have in your alphabet the higher the risk of pairs that are difficult to tell appart

  0Oo
  1l

etc

https://en.wikipedia.org/wiki/Base58

Base58 has certain issues (lowercase-uppercase ambiguity) which is why we now have https://github.com/bitcoin/bips/blob/master/bip-0173.mediawi...

Can you elaborate on the ambiguity problem of Base58? I always thought that base58 was designed with this in mind as it does not include visually ambiguous letters such as "0", "O", "I", "l", etc..

That is true, but if somebody unfamiliar with the encoding writes down the characters or communicates them over the phone they have consider the case for every letter. That is a poor user experience.

None of the two examples you showed would apply to the proposed non-numeric base 46, since 0 and 1 would not be allowed.

Although it is true the potential risk may be higher, it is easy to find counterexamples where this potential risk does not matter. The 26 capital letters are easy to distinguish and allow you to use a base-26 system, while a base-2 system where the only two elements are 1 and l (or 0 and O) would be more difficult to use, for example.

The proposed base46 encoding has

  Oo
  Il

> If you wanted to even it out to 64 characters, you could create a "modified base-64"...

My go-to encoding is base64url in RFC 4648. It's simply base64 with - instead of + and _ instead of /. In a case like this where the length is known, you can omit the trailing "="s so no escaping is necessary.

https://tools.ietf.org/html/rfc4648#section-5

Great suggestion. This is one of my design pet peeves for anything related to banking / bill payments numbers that are long and unwieldy to type. The (eg. invoice) number 563466130 in base 35 is "9bh18y". The same number as 9BH18Y and so much easier to type. Base 35 for sha256 would however add 11 additional characters compared to the sha1 output length tho.

Same reason we use other "inefficient" protocols like json or HTTP and not "superior" binary alternatives.

So what do you think of CBOR being used in new IETF standards?

I don't think anything about it because I do not care. Just because binary protocols exist it does not undermine convenience of text protocols.

You are free to use CBOR for your configuration files for your next application. Then come back and tell us of your experiences.

Git uses text hashes in many, many places. This makes it convenient for the users which is very important design goal. I am pretty sure that replacing this with binary hashes would be insignificant performance improvement.

http2 is in fact binary, it's only converted to a text representation for human convenience when needed, the same can be done with other protocols.

HTTP 2 only recently reached 50% adoption.

My gut instinct is to use a power-of-2 base because it makes decoding a lot easier (and can be done in parallel). But I doubt that the hash codec is a big enough overhead to be concerned about.

Alternatively you can prepend the name of the hash used

And now you basically reinvented multihashes :)

https://multiformats.io/multihash/

I do not like multihash. I personally prefer base64 hashes and I also do not like how they include the length.

> the SHA256 hashes would be unambiguously not SHA1 hashes, even when abbreviated

Not if your hash happens to not include an 'h'.

The current SHA-1 representation uses hexadecimal, so only contains 0-9 and a-f.

Not sure I follow. If the SHA1 hashes use [0-9a-f], and the SHA256 hashes use [h-zA-Z] (or something along those lines), there is never any overlap in characters.

What is unwieldy about hex strings? If you'd want to solve this perhaps a prefix would be easier?

If you store them as strings instead of binary (which I'm guessing 99% of hashes are), they take up more DB space currently, and passing them round is slower, e.g. as etags etc.

I would guess that once compressed, binary represented as hex strings don't take much more space than base64 strings. Probably still a bit more than the compressed binary though.

You won't gain anything by compressing (binary) hashes.

Oh yes indeed.

This is about printing, not storage.

I wish hashes were more human-readable/human-writable.

maybe use a scheme where the prefix of the hash could be mapped to a common word.

So with a contrived example based on 100 and:

https://en.wikipedia.org/wiki/Most_common_words_in_English

the former hash 9221920 would break off "92" from 21920 and look in the word list to allow any of the following:

  9221920            old style hash could say just 92
  92-new-21920       or use 92 + 92nd most common word, "new"
  new-21920          or skip 92 which is redundant with "new"
  new                or just use new alone

obviously 100 and base 10 would have collisions, so use a larger number and constricted word lengths to find 256 or 4096 or 65535 words.

If you used a dictionary of 100 words, you would get a prefix collision every 100 commits, i.e., within days or weeks for even moderately busy projects. Using a larger list would just shift the problem by a bit. You could use tuples of words (like https://en.wikipedia.org/wiki/What3words for example) to avoid the problem. But then you'd be much longer than current Git hash prefixes.

And why? What would be the use? The two things I do with Git hashes: (a) copy and paste, for searching for something; (b) occasionally visually comparing hashes. Copy and paste works well, in fact in pretty much any terminal or other tool double click will select the whole hash, which wouldn't be as simple if the hash were multiple words with separators. Visual comparison might be marginally easier with familiar words, but for me it's a niche use case, so I don't think optimizing for it would be useful.

my last line addressed 100 words.

I also was trying to augment the current system, not replace it. so the "92" and the word "new" were equivalent and you could use one, or the other or both.

The basic idea I'm putting forward, is that I think it would be easier, on the command line, than copy-paste (which requires a mouse)

I can type words pretty fast, and I can keep a word in memory easily.

Remember it extends the current model without changing it.

Way, way bigger downside is that you've made encoding and decoding much more complicated than a simple table lookup.

Base32 and base64 both can easily be implemented using a lookup table.

Not the suggested base-46.