mmalone

Not rude at all. They're actually all good questions.

> Why? Why do your identifiers need to be cryptographically secure at all?

They don't have to be cryptographically secure. They just need to be unique. Using random identifiers are easier to generate than deterministic/semi-sequential identifiers which would require some form of coordination, which is a pain in the ass and a point of failure. We switched to a cryptographically secure PRNG because it is higher quality than the non-CS alternative.

> Well.....except that if you had done the former, you wouldn't have had to analyze collisions because, you know, they wouldn't have happened.

You're assuming a UUID library that didn't just use Math.random() under the hood. Many libraries at the time of this incident did. Either way it would have been work to find one we could trust, vs. 10 lines. Also, UUIDs are 36 characters and not suitable for some use cases like short identifiers that will appear in URLS (which might need to be typed oh phones, etc).

> why does the library need to be kept "up to date"?

We would have had to update it when someone realized it was using Math.random() under the hood, for instance. In general there's a certain amount of maintenance involved with any dependency.

> why couldn't you just build a dead simple add-on/module in C++

Because 10 lines of Javascript vs. that.

> it was all for naught.

The random identifier generation was relatively irrelevant / just a fun narrative around the real story, which was about the subtleties of PRNGs, doing your homework, and Math.random() being crappy. If you don't think that use case is legitimate, that's fine. There are lots of other use cases where Math.random() is problematic, like shuffling an array (for an unbiased shuffle of a length n array you need a cycle length of n!).

Unpredictability is irrelevant to a use case like shuffling an array. Moreover, your conjectured polynomial-time perfect CSPRNG may actually produce a less useful stream of entropy for this use case than a good non-CS PRNG because its cycle length may well be shorter, and all that matters is uniformity (which can actually be guaranteed, not just conjectured and measured empirically) and enough seed entropy to kick things off. Top it all off with the non-CS PRNG being perhaps orders of magnitude faster.

I'll repeat once again that I do think people should generally default to CSPRNGs, but I really don't understand why everyone involved in crypto insists that there are no valid use cases for non-CS PRNGs / that CSPRNGs are uniformly better for all use cases when it seems very obvious to me that they are not. I don't see any reason why a good PRNG and a good CSPRNG shouldn't exist in every standard library. Am I missing something?

If, by quality, you mean "indistinguishable from true randomness" then there are many valid metrics. One important metric that many non-CS PRNGs have, but many CSPRNGs do not have, is a provable deterministic cycle length for all seeds.

These characteristics don't just make Monte Carlo simulations converge quicker, they also do things like guarantee that your 52 deck shuffle will definitely produce the one shuffle that gives player two a royal flush on the flop in a round of texas hold 'em. Or, more generally, they guarantee that your Array.shuffle() method is unbiased for a reasonable sized array. In general you need true randomness and/or a long cycle linear-transformation PRNG to make those sorts of guarantees. It's also nice that they're fast. That said, I do also agree that the scenarios in which these things matter are rather rare, and most people should probably just use a CSPRNG by default.

Do you really think a CSPRNG is fast enough for your standard library's array shuffle though? Wouldn't you rather have something like xorshift1024* that's probably > an order of magnitude faster? Maybe a CSPRNG is fast enough... I don't have all the numbers. So this is an honest question.

Hahahahaha. I can't believe that either.

Looks like your first question has been answered!

Re: submitting a patch, there were several previous issues and discussions about Math.random() being problematic that were closed-wontfix or otherwise dismissed. It seemed like the general perception was that it was "good enough." It didn't make sense to me to open another similar ticket without a good analysis and whatnot.

I meant to file another issue before posting, but I forgot. There is an open issue now, however![1]

[1] https://code.google.com/p/chromium/issues/detail?id=559024

If you want to do something as trivial as an unbiased Fisher-Yates shuffle of an array, however, Math.random() is broken. And Math.random() doesn't have to be broken for things like UUIDs. Python and Ruby both have PRNGs that are suitable for such things.

We fucked up by not vetting the algorithm, that's definitely the primary lesson here. Mea culpa. I'm sure you would have done things differently, but V8 is a modern system and I don't think assuming a modern PRNG was completely unreasonable while quickly getting to MVP at a new startup.

FWIW xorshift1024* would almost certainly be faster than MWC1616 and it has no systematic failures on BigCrush. The only downside is that it uses more memory, but I think we can afford it. If not xorshift64* is also faster than MWC1616 and miles ahead of it in quality.

It's easier to generate a random identifier and if the generator is good the probability of a collision is lower than the probability that you HDD will fuck up in an uncorrectable way while storing the identifier (as I've pointed out elsewhere in thread). So the answer is that random identifiers are easier to do in a distributed system and, in reality, have the same guarantees.

The biggest problem is that they take up a lot of space. Plus you have to find a good library and vet it (there's nothing in the standard library). Or just write 10 lines of straightforward code.

If you go and look at node-uuid commit history it, too, used Math.random() back in the day.

It is mentioned! Without the `window.` part though ;).

Using node IDs and timestamps is just an additional safety factor. Statistically it's not necessary if you have a good generator. Even without those things our target collision probability is less than the expected uncorrectable error bit rate of a HDD.

Good PRNGs have equivalent entropy at each bit. With a good PRNG (even a non-CS PRNG) you shouldn't need to mix entropy to do scaling. You should still do rejection sampling[1] if you care about bias. It looks like a good scaling method might be added to the ECMA spec as part of the standard library thanks to some awesome people at Google.[2]

[1] https://gist.github.com/mmalone/d710793137ed0d6b8cb4

[2] https://twitter.com/mjmalone/status/667806963976134656

True of UUID1s, unless you bastardize them and use something other than MAC address. You could do UUID4s without leaking info.

Great point / good question. Here's why we didn't just use UUIDs:

* UUID generation still requires a good (CS)PRNG and should be vetted the same way you'd vet a (CS)PRNG.

* UUIDs are one-size-fits-all 36 character base-16 encoded strings. If you want a short random identifier that you can use in a URL (that people might need to type on a phone or something) they're not ideal. Re-encoding them and/or truncating them is as hard and error prone as just generating the randoms yourself.

* Researching a good UUID library and maintaining a dependency is harder than vetting the 10 lines of code required to do it yourself. Without a trusted standard library solution it's unclear which library to use (maybe not as true today as it was a couple years ago when this happened)

If UUIDs were available in the Javascript standard library we probably would have used them in some of the places that we currently use our own identifiers. We do use UUID4s in our Java services, for instance.

I'm guessing that UUIDs aren't standardized because the standards process is browser-centric and it's low priority in that context... but that's just a guess.

Edit: formatting.

It wasn't dependent on exact behavior. It was dependent on a sensible general contract. We rely on sensible implementations of general contracts all over the place in software development.

We did make an incorrect assumption that the PRNG (created by Google, who has a good reputation, and in what is probably the most popular software in the world) was high quality. That was a mistake, and we should have done more homework. However, there's no reason why the Math.random() implementation in V8 should _not_ be good enough to not have to worry about.

There's a difference between cryptographic security and quality. Cryptographically secure generators typically have (empirically verified) high quality from a statistical perspective, but they're not a general solution for all purposes. They're relatively slow, you can't seed them, and they don't typically have rigorous mathematical proofs of certain characteristics like equidistribution and cycle length.

The article doesn't suggest Math.random() should be cryptographically secure (although that is an option). Rather, it's a critique of the algorithm that's being used. There are better algorithms with no drawbacks that produce sequences you can safely assume have a statistically random distribution (even if the sequence is predictable and is therefore not cryptographically secure).

Calling a PRNG is way easier than any of the alternatives. Coordinating sequences on a bunch of nodes so that nobody overlaps is a pain in the ass, and a point of failure. Incorporating some notion of "machine ID" in the identifier makes it easier, but you still have to worry about multiple pieces of software on the same machine, for example. UUIDs are the a good solution, but you need a UUID library you trust, and they waste a lot of space / are overkill for many use cases.

All of that is sort of beside the point though. Pseudo-random sequences are useful for lots of things and the PRNG algorithm behind Math.random() is pretty crappy.

tl;dr: the algorithm powering V8's Math.random() is very poor quality. For many use cases you can't safely pretend its output is actually random. Don't use it for anything non-trivial that you care about. It should probably be fixed. In the meantime, use crypto.randomBytes() or crypto.getRandomValues() instead.

I was lead architect at SimpleGeo and spent most of the time working on our distributed geospatial database. I haven't looked at the MongoDB implementation in years, but at that time it was really a toy compared to what other people were doing. Basically, they used a space-filling curve to do dimensionality reduction and then stored geospatial data in the same b-tree index that they use for everything else. It's suitable for a lot of trivial use cases at scale, and even for non-trivial use cases at low data/throughput scale. But the architecture was (too lazy to determine if it still is) not suitable for large data set sizes, query throughput, or distribution for fault tolerance / improved locality, etc.

At the time it was really frustrating to here comments like yours since the MongoDB solution was superficially similar to the consumer, but was basically worse on every measurable dimension if you knew what you were doing. I hadn't heard of SpaceCurve before today, but I skimmed the linked article and some other stuff on the blog and it looks like this guy knows what he's talking about. My guess is it's a much better geospatial architecture than MongoDB's.

Betable | San Francisco | Full Time, ONSITE | https://jobs.lever.co/betable | Gambling platform for developers

Betable is transforming one of the most opaque and highest revenue-generating industries in the world - gambling and betting. Our vision is to democratize this $500bn industry, allowing any game developer to build legal gambling games without needing their own licenses and operate those games globally on any device.

We are Series A funded with exciting revenue, a small engineering team and a modern tech stack (Node, Angular, React, GO, Cassandra, Puppet, etc). We have strong values and awesome investors (True Ventures, Greylock, Venture51 etc). Come help us transform an industry!

Positions:

- Sr. Software Engineer - Web technologies - https://jobs.lever.co/betable/006263e7-3346-4c16-acf6-37d5f2...

- Sr. Software Engineer - Server technologies - https://jobs.lever.co/betable/c81cb400-f0e1-4dd0-bf21-f7b63b...

- Sr. Operations Engineer - Focused on devops - https://jobs.lever.co/betable/c879a3fe-86ee-4d09-91fc-cfa2ab...

- Engineering Manager, Operations - https://jobs.lever.co/betable/ce2588a3-2fb7-4f2d-9290-73bba8...

Not implying anything other than that it's a proper name. Meh.

I have to justify that that's what I mean when I say "god," or I have to justify that God created the universe? It is a common definition, so I figured you'd accept it.

The point is I'm not talking about a specific God or assuming anything about the nature of God like many religions do. Once you remove all that baggage God is just a term that means "the thing that created the universe." So to deny the existence of God you must deny that the universe was created by something. I don't see how you can make such a claim without any evidence. Last I checked there was no scientific explanation for the creation of the universe.

In a hypothetical world with no privacy and perfect information I'd just make my nuclear launch system (which also has perfect information) only launch when the right people ask them too. You can't pretend to be those people because you can't lie because the launch system would know because there's no privacy.

I don't know of any way to actually implement this in practice -- there probably isn't one -- but it's an interesting thought experiment. It's possible that privacy isn't a moral right and perhaps isn't necessary at all. The argument for privacy seems to be predicated on other people being immoral. If you could identify immoral people 100% accurately then perhaps the need for privacy goes away. In fact, if that were the status quo you might claim that keeping something private is immoral.

How are you defining God? Have we looked for God in all of the places that people believe God lives / controls?

The universe either came from somewhere or has always existed... If I define God as a "the thing that created the universe" how would you prove or disprove God's existence?

The argument is that privacy serves no purpose aside from facilitating lies, and lies are bad. One challenge that has been presented is that there's a difference between "lying" and "not telling the whole truth" but I believe both are "moral bads" and I don't really want to get into that regardless (the distinction between passive and active moral decisions has been debated endlessly by philosophers already -- google "killing vs. letting die," for instance).

I don't think it's infeasible to find a technology. I think it's infeasible to change our culture to be more accepting of the sorts of things that people choose to keep private. As long as people are persecuted for their completely normal beliefs and actions privacy has a place and keeping things private is justifiable. But if I were designing a utopia I think I'd try one with no privacy at all (everyone has access to the same set of facts about everyone / everything else) and see how things go.

Why do you think my position is immoral? How is it a flawed concept? You haven't presented a logical argument for your position -- that privacy is good. I'd love to hear one that doesn't include a clause where "some bad actor does something immoral because of lack of privacy."

Maybe P = NP, then we won't have a choice :)

Edit: spelling.

Eh... I don't get it? Why is privacy required where there is no trust? I see how the two are related but I see it kind of differently... it's hard not to trust someone when you know they're not hiding anything.

In a totally utopian sense I believe that privacy is bad. Practically it's probably impossible to implement society without privacy. I wouldn't share my email password because we're not living in a utopia and that information asymmetry would hurt me. However, if privacy went away social norms would have to change -- there would be a lot less hypocrisy -- and the things I'm keeping private right now wouldn't need to be private any longer.

Really privacy just facilitates lying.

Comcast is throttling / dropping traffic because they want Netflix to pay for bandwidth. You're right that they'd be getting paid twice for the same traffic, but ISPs already do this -- if Comcast and Netflix are connected via Level 3 they both have to pay Level 3 for the same traffic.

What if Comcast offered to host Open Connect devices for a fee -- would that be a violation of net neutrality? To me that just seems like the free market doing what free markets do (I'm ignoring for a moment that Comcast is basically a monopoly which is a legitimate problem).

What if Comcast throttled everyone _except_ Netflix. Is that really different than Comcast allowing _only_ Netflix to peer?

I don't think your conclusion logically follows. The free market argument would be that the fairest price is whatever Comcast can get netflix to pay (or vice-versa). From a policy perspective I don't see a reason to intervene except that both parties have unfair advantages relative to their competitors (and Comcast basically has a monopoly). However, if that's the reason to intervene on traffic shaping then I think it's a reason to intervene on peering relationships too. I'd love to be able to peer with Comcast, but I can't. That's not fair.

Still looks like peering to me: https://www.netflix.com/openconnect/guidelines

Even if you can colo with Comcast (which I can't find any information about online) you're still not direct-peering with their AS, which is what Netflix is asking for with Open Connect. I'm sure they'll also charge you for bandwidth. This is definitely different than putting a box in a colo facility. This is putting a box in a peering location and eliminating the transit cost and performance hit.

Unless I'm reading this incorrectly this is a peering arrangement, which is qualitatively different than just hosting a box in a DC run by Comcast (which doesn't exist, as far as I know, so I can't do it as a normal citizen). I could colo a box "near" Comcast, but I'll be more hops away (worse performance) and I'll have to purchase transit from some ISP that does peer with Comcast (more expensive).

Wanted to add a little bit more to my previous comment since I've been thinking about this for a while. The story I heard about broadcast was that they pursued this sort of peering arrangement with smaller ISPs so they didn't have to pay for transit -- basically to reduce their bandwidth bill. It was really a brilliant move on their part. Since then lots of other large bandwidth consumers have done the same.

I'm not against net neutrality but I do think the issue is more complicated than people make it out to be. Once you understand that this is common practice the position of Comcast, et al. does make more sense. If Netflix is saving a shit-ton of money and providing a better service to their customers by peering, and Comcast has less upside, why shouldn't Comcast charge Netflix for the privilege?