7 ms·
One of the comments mentioned that there was a suggestion (presumably rejected) to "rotate" the first character of the hex string for the SHA256 hashes by 16 ch
by kelnos 6y ago
One of the comments mentioned that there was a suggestion (presumably rejected) to "rotate" the first character of the hex string for the SHA256 hashes by 16 characters, so 0 becomes g, 1 becomes h, etc. (that way the SHA256 hashes would be unambiguously not SHA1 hashes, even when abbreviated).
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.
If you wanted to even it out to 64 characters, you could create a "modified base-64" that doesn't use [0-9a-f] and instead uses more special characters (though for convenience you'd want to choose characters that are shell-safe and possibly even URL-safe, which might make this not work). Alternatively you could use a subset for a base-32 representation.
The downside -- perhaps a significant one? -- is that you can't use standard tools like `sha256sum` or the representation conversion functions into the stdlib of many languages to generate these hashes; it would require custom code. Not sure if that's a concern, though.
- supakeen 6y agoWhat is unwieldy about hex strings? If you'd want to solve this perhaps a prefix would be easier?
- richbradshaw 6y agoIf 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.
- speedgoose 6y agoI 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.
- dependenttypes 6y agoYou won't gain anything by compressing (binary) hashes.
- speedgoose 6y agoOh yes indeed.
- Dylan16807 6y agoThis is about printing, not storage.
- Dylan16807 6y agoCase 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.
- kelnos 6y ago> 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.
- garmaine 6y agoWay, way bigger downside is that you've made encoding and decoding much more complicated than a simple table lookup.
- dependenttypes 6y agoBase32 and base64 both can easily be implemented using a lookup table.
- garmaine 6y agoNot the suggested base-46.
- moonchild 6y ago> the SHA256 hashes would be unambiguously not SHA1 hashes, even when abbreviated Not if your hash happens to not include an 'h'.
- globular-toast 6y agoMy 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.
- lmilcin 6y agoSame reason we use other "inefficient" protocols like json or HTTP and not "superior" binary alternatives.
- panpanna 6y agoSo what do you think of CBOR being used in new IETF standards?
- lmilcin 6y agoI 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.
- the8472 6y agohttp2 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.
- lmilcin 6y agoHTTP 2 only recently reached 50% adoption.
- grizzles 6y agoGreat 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.
- deleted 6y ago[deleted]
- dependenttypes 6y agoAlternatively you can prepend the name of the hash used
- capableweb 6y agoAnd now you basically reinvented multihashes :) https://multiformats.io/multihash/ https://multiformats.io/multihash/
- dependenttypes 6y agoI do not like multihash. I personally prefer base64 hashes and I also do not like how they include the length.
- VMG 6y agothe more characters you have in your alphabet the higher the risk of pairs that are difficult to tell appart 0Oo 1l etc
- ryanlol 6y agohttps://en.wikipedia.org/wiki/Base58 https://en.wikipedia.org/wiki/Base58
- VMG 6y agoBase58 has certain issues (lowercase-uppercase ambiguity) which is why we now have https://github.com/bitcoin/bips/blob/master/bip-0173.mediawiki https://github.com/bitcoin/bips/blob/master/bip-0173.mediawi...
- xurukefi 6y agoCan 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..
- VMG 6y agoThat 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.
- yiyus 6y agoNone 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.
- m463 6y agoI 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 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.
- tom_mellior 6y agoIf 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 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.
- m463 6y agomy 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.
- wegs 6y agoGood 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).
- marton78 6y agoThe human friendly format you're suggesting is Douglas Crockford' Base 32 encoding.
- dlkinney 6y agoI 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
- 6y ago
- user5994461 6y ago>>> 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.
- ptx 6y agoIn 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.
- deleted 6y ago[deleted]
- notriddle 6y agoThe 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.
- mkl 6y agoI 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.
- mkl 6y ago> 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.
- mathnmusic 6y agoOne 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 https://github.com/multiformats/multihash
- heavenlyblue 6y agoYou 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.
- tzs 6y agoRight. 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.
- alkonaut 6y agoIf 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.
- john-shaffer 6y ago> 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 https://tools.ietf.org/html/rfc4648#section-5
- yencabulator 6y agoThe 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-encoding.txt http://philzimmermann.com/docs/human-oriented-base-32-encodi...
- kzrdude 6y agoBase-32 just encodes one more bit per symbol (5 instead of the 4 per symbol that hex does), so the improvement is rather minor.
- yencabulator 6y ago52 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.