Fixed Bits of Version 4 UUID (2015) | Hacker News Reader

Fixed Bits of Version 4 UUID (2015)

susam.net

34 pointssusam23 comments

I don't get why this is interesting. The RFC for UUID type 4 says the digit "4" must be set on the 14th byte. The loop checks to see if this is the case, and loops if it is. Unsurprisingly the UUID generator returns valid type 4 UUIDs so the loop is infinite.

This is like making a blog post called "From Integers to Infinite Loops" and then creating a loop that tests if 1==1. I mean, yes it's an infinite loop, but why is that worth blogging about?

PS: I tried commenting this on the actual site as well.

> The RFC for UUID type 4 says the digit "4" must be set on the 14th byte. The loop checks to see if this is the case, and loops if it is.

The RFC for UUID type 4 states that bits 48 through 51 (0-based indexing) are set to 4, resulting in the character at position 14 (0-based indexing) of the hyphenated string representation being '4'.

Also, this post does a little more than that. It also notes that the version 4 UUIDs we use in software today are variant 10₂ UUIDs. This is quite unsurprising too because the other variants are reserved. There is a second infinite loop in the post that demonstrates this by testing the two bits that represent the variant number.

> why is that worth blogging about?

Hello! I am the author of this post. This is my weblog, so I log about things that I find interesting here. In this case, the interesting thing for me was not so much that we can make an infinite loop out of a triviality but the triviality itself, i.e., not all bits of variant 10₂ of version 4 UUIDs are random, and then finding the sections in the RFC that define these bits.

The infinite loops only serve as demos that there are definitely six bits that are not random. Indeed the infinite loop is just testing whether a version 4 variant 10₂ UUID is a version 4 variant 10₂ UUID and that is bound to be an infinite loop. However, I also wanted to document on my weblog where exactly the version and variant bits are located along with references to the relevant sections of the RFC. That is slightly less trivial than documenting that 1 is 1.

I understand this is not going to be interesting to everyone. But this is my weblog, so I don't have to subscribe to others' notion of what is interesting to decide what I must add to my own weblog.

I believe a more meaningful question would be whether this post is worthy of HN or not. Well, the moderators and the community determine that by voting with their fingers. In this case, it looks like this post is indeed not too interesting for HN, so I would have agreed with you if that were your point.

I agree with both of you. It is quite weak article with weird jump to the infinite loop. But then again you are right too - it's your blog you can write whatever you want. Don't get discouraged and keep doing what you like!

Thank you for your comment! About the weird jump to the infinite loop, it is meant to be a quick-and-dirty demonstration of the fixed bits. It serves as an alternative to visually checking the fixed bits and confirming that they agree with the RFC.

However, after reading some of the comments here, I realise that the original title of the post was creating the impression that the post may contain something more interesting than its actual content which is simply a discussion of the fact that there are six fixed bits in version 4 UUIDs. I have now updated the title of my post to: Fixed Bits of Version 4 UUID.

P.S. Thanks to @dang for making the corresponding update to the title of this story on HN.

Thank you for taking the criticism positively :)

The question is more why this is HN worthy. The fact that people blog about trivial results should be celebrated. After all, it is blogging.

Indeed. I think one potential cure to what most people here recognized as the enshittification of the internet would be if people just blogged about things that interested them, regardless of whether some third-party thinks the topic(s) merited.

I’ve been using uuids for over a decade and didn’t realize there were fixed bits in version 4. I learned something and am thankful it was posted here. Much more interesting than a lot of other submissions.

I'm sort of curious how the theory that "1" is most likely to be the first digit of a random number applies to this.

Does anyone know or can expand on what I'm talking about?

This depends on the distribution, for a uniform distribution all 16 hex digits are equally likely in every position.

Also for benford's law to show up you want your data to span several orders of magnitude (so e.g. you have numbers in tens, hundreds and thousands) and for a datapoint to be about as likely to give an n-digit number as a n+1-digit number, not everywhere and not exactly but it needs to dominate over there being ten times times as many of them with each step.

I believe that that theory is about un-padded numbers. It doesn't apply to fixed-length numbers generated in the full range. Because 010 would have a leading 0 rather than a leading 1. Since the first byte of a UUID is random and can be any of the allowed values it has no bias in the first digit.

That's Benford's law, but I don't think it applies here. From Wikipedia:

> Benford's Law tends to be most accurate when values are distributed across multiple orders of magnitude, especially if the process generating the numbers is described by a power law (which is common in nature).

it definitely shows up in 8-bit and 32-bit stuff though, doesn't it? There's just a lot less of those numbers where the leading digit (in decimal) is larger than 3 or so.

Assuming you aren't 0 padding, there are 111 unsigned 8-bit integers beginning with 1 (1, 10-19, and 100-199), 67 beginning with 2 (2, 20-29, and 200-255); all of the other digits appear 11 times (in single-digit form and as the leading digit in the tens place for their "decade") except 0, which appears first only in 0 itself. Unsigned 32-bit integers will have 1, 2, and 3 tied for first with 4 far back in fourth place and 5-9 in even the more distant penultimate position (with 0 still being last).

If you're dealing with signed integers, you'll have an even more lopsided distribution in favor of 1 for both 8-bit and 32-bit numbers (assuming you don't count the negative sign). And of course, all of this is assuming base ten; you can make things even more uniform by using binary!

well yeah, no one would want to argue that a leading '1' wasn't pretty predominant in unpadded binary ;)

thank you for the good, concise, starter breakdown of why this is a feature of decimal math.

It doesn't apply.

Isn't it a similar observation, though?

I've spent a lot of time thinking about random numbers, and how to pull random booleans out of pseudo-random numbers. No one would ever choose UUIDs to serve as a source of randomness. But the observation that "4" comes out really often in UUIDs is on par with the observation that you can't just take the first digit of a 32-bit unsigned, un-padded random number and expect it to be an equally weighted random between 1 and 9. Right? So doesn't that relate?

No it isn’t. This is that the standard says you will always have 4 in this position. Distribution of randomness has no involvement.

oh. So if you always know there's a 4 there and then you can trigger infinite recursion based on that... what's the big insight here?

That's a few minutes I'll never get back.

I assumed there was a bug in the spec or something, but no.

UUIDs: awkward, pointless cargo cult.

- the dash formatting is meaningless

- the only useful variant other than "all random" is "time sortable" and it's only part of uuidV7

- hexadecimal is neither compact nor human friendly

The dashes serve humans eyeballing uuids, not computers. You can remove the uuid in your language of choice and I’m confident it will be able to parse.

How are uuids pointless?

Hexadecimal is much more human friendly than say, binary.

- The specific divisions of the dashes is meaningless and asymmetrical for legacy reasons

- Hexadecimal is bloated compared to other encodings, low entropy per digit, inefficient when e.g. embedded in URLs

- Is not memorable for humans, does not use the entire alphabet, and has no redundancy or checksum to detect typoes.

Pretty much anything else would be better, and is. Hence, it is a cargo cult.

I've never seen a database so unusable as one that was indexed by non sortable uuids.

I hate it every time I have to use it. It signals bad taste and is a warning sign to look out for more pointless code drudgery.

Reply on news.ycombinator.com