mmalone

The linked TOC is long and I've only skimmed it, but I wouldn't call Erlang a data parallel language per se. When I hear "data parallel" I'm thinking of a language with abstract data types (ADTs) for lists, and maybe sets, bags, and dictionaries too. There are also language intrinsics like join, map, etc. that can and will automatically be optimized and will "lift" computations into a parallel or distributed context for you. There are various minimal sets of core datatypes and intrinsics that a language can provide to achieve this.

The closest thing that most programmers are familiar with is a relational database. Imagine a language that treats certain data structures like an RDBMS treats a table and does the sort of optimizations that a query optimizer does when you run an intrinsic (either statically at compile time or dynamically at runtime). That's data parallelism.

Erlang has facilities to make this sort of thing possible, but last I looked it doesn't do it for you.

If anyone who's actually an expert wants to step in and correct my assumptions please do so!

The short answer is that there is really no good general purpose way to deal with asynchronous communication in a "restful" HTTP API. All solutions have major drawbacks. This is one of the biggest shortfalls of rest/http in my experience. People tend to switch to other protocols to address these use cases (this is a common reason for adopting message bus infrastructure like Kafka as part of a SOA).

Personally, I consider it metaphysical because it says something about provability (since, deep down, proofs and programs are the same thing). Truth beyond proof (or at least beyond what's feasible to prove) is bizarre and mysterious.

Metaphysics (and physics) is concerned with uncovering the fundamental truths of the universe. Computational complexity indicates this may be unachievable.

Interesting that he was a systems theory guy. My dad was a civil/mechanical engineer and was way into systems theory in the 60s and 70s. The idea, from what I've gathered, is to apply an engineer's toolkit to natural / social science problems. I've got a couple of his old (way out of print) books on systems theory and they're fascinatingly relevant to software development -- particularly for big complex distributed systems. They had to deal with poorly specified problems, emergent behavior, "fuzzy" logic, failure, etc. All problems you face in a real complex software system. These ideas don't get enough press.

This is a topic I researched a long time ago. I don't trust my memory enough to summarize any findings or recommend specific papers, but here are a couple of bookmarks I've kept around:

- http://www.cl.cam.ac.uk/teaching/1011/R201/

- http://www.ppig.org/

If you're designing a programming language or programming tools, another resource that I've found helpful is this collection of syntax choices across languages:

- http://rigaux.org/language-study/syntax-across-languages/

Oh, one more thought since I didn't really address state leak. Let's pretend we're in a C-like language that is not memory safe. You're not reseeding and you don't have forward secrecy. Someone finds a buffer overflow and manages to get your CSPRNG state. Now they can recover the sequence of randomness you've handed out in the past (maybe they're access tokens, for instance). It's not a trivial attack, but it's plausible.

If you don't like the buffer overflow example, let's make it a misconfigured website that leaks the state in an error message or stack trace served to an end user.

The simpler design is probably to just fill a pool of entropy from urandom in user-space and give out numbers from that pool, thus amortizing the syscall overhead. Even that would be not-quite-as-good-as-urandom (still more that could go wrong), but it's probably as close as you can easily get.

Incorrect. You may be thinking of the "/dev/random vs. /dev/urandom" argument, which says it's stupid to _block_ on reseeding based on some arbitrary heuristic (and which I agree with). However, that doesn't mean reseeding is unnecessary. Even a CSPRNG cycles and you need to reseed before it does so or the wheels start to come off. Generators become less random looking even before cycling. The general rule is that you shouldn't use more than sqrt(cycle length) from a single generator.

If you use a secure n-bit block cipher in counter mode, for instance (generally considered a "good CSPRNG") then the generated numbers start to become distinguishable from random after 2^(n/2) generated blocks due to lack of collisions. This is a weak statement, but the point is any proofs that assume randomness (likely all proofs of hardness of crypto reversal) no longer hold. If you don't reseed before this point then you're doing it wrong. Other desirable characteristics of CSPRNGs, like forward secrecy, may require periodic (or frequent) reseeding depending on algorithm.

Best practice for a source of secure "randomness" is to use an entropy accumulator that finds as much "true entropy" as it can and constantly mixes that into a pool (while protecting against injection attacks), then to use a good CSPRNG algorithm to "stretch" the available entropy since true entropy is a scarce resource. That's what urandom and OpenSSL do, for instance (see Yarrow/Fortuna for a good design).

A lot of thought has been put into the design of urandom. Pulling one random seed from urandom and stretching it forever in user-space is _not_ equivalent. You could probably design something in user-space that _is_ as secure, but it's not trivial.

Yep and with the new SplittableRandom they seem to have opted for a more subjective definition with a guaranteed minimum cycle length and passing marks on Diehard. Seems like a happy middle ground.

It's not just the initial seeding, you also need correct reseeding, you need to make sure the state doesn't leak somehow, and you need to make sure you're actually getting the seed data securely. If you're doing something that's crypto related there really are a lot of things you can screw up in user space. Using urandom directly is your best bet. It's not fake secure, it's just non-trivial to get right.

Eh, I'm not sure where you're getting your numbers. Here's a quick test using node 0.10.40 on my machine:

  mmalone$ node
  > var f = function() {
  ... s = Date.now()
  ... for (var i = 0; i < 1000000; i++) {Math.random()}
  ... return Date.now() - s
  ... }
  undefined
  > f()
  3
  > f()
  1
  > f()
  1
  >

So I'm getting a couple milliseconds for 1,000,000 numbers. I'm also toying around with a PRNG package in Go currently so I have some numbers there too:

  BenchmarkXorshift128p-8                  	500000000	         2.98 ns/op
  BenchmarkXorshift1024s-8                 	300000000	         4.62 ns/op
  BenchmarkXorshift4096s-8                 	300000000	         4.44 ns/op
  BenchmarkXorshift4096ss-8                	200000000	         6.29 ns/op
  BenchmarkUint64sFromCryptoRandIdiomatic-8	  200000	     10736 ns/op
  BenchmarkUint64sFromCryptoRandUnsafe-8   	  200000	      8081 ns/op

Go's crypto source pulls from urandom. This is more like what I'd expect in terms of performance. The difference is orders of magnitude, but we're still talking about microseconds so I think your argument is still valid. A proper CSPRNG is not "as fast" but it is probably "fast enough" for most use cases.

It's complicated. For starters, if you're looking for a _secure_ PRNG most practitioners would strongly advise _against_ the system you described[1]. There's a difference between a cryptographically secure algorithm and a secure system. For the overall system to be secure you need to make sure the seed data is secured, which you're bound to fail at unless you really know what you're doing.

Providing a "cryptographically secure but not really secure" alternative implemented in user space alongside a "really secure" alternative that's been thoroughly vetted would likely just add to the confusion. If you _really_ need secure numbers you should be using the really secure one. The really secure one is almost definitely going to require a syscall worth of overhead, at least, so it's _definitely_ going to be slower than a PRNG like xorshift128+ which literally takes a single digit number of CPU cycles.

Now to answer your question, if you're just talking about a CSPRNG algorithm they're probably fast enough for almost every use case. I think there's still an argument for some things like array shuffling, but those implementations could go out of their way to use the non-CS algorithm as an optimization. Unfortunately in Javascript land there's aren't many batteries included, so if you switched Math.random() to use a CSPRNG most people would end up using it for trivial stuff like shuffling arrays. If you're talking about a secure system... it's probably still fast enough for most things, but it's less obvious.

[1]http://sockpuppet.org/blog/2014/02/25/safely-generate-random...

The algorithm that V8 chose to replace the current generator, xorshift128+, passes BigCrush and can produce a random uint64 in just over 1 nanosecond on a modern processor (that's ~7GB/s). Seems like a good choice. Not sure how it compares to something like ChaCha20 on performance, but I'm guessing it compares favorably (though it's unlikely to be your bottleneck either way).

Since I wrote the above linked article there's been a bunch of discussion, some of which has been about using crypto to back Math.random(). I'm sort of torn on that front - I feel like a good PRNG is useful for some stuff (like array shuffles), but maybe not? Maybe there are undiscovered (or even discovered, but not well known) vulnerabilities that justify CSPRNG even there, as there are with hash collision vulnerabilities.

Anyways, what I learned is that the benchmarks (particularly SunSpider, it seems) are putting pressure on implementors to (over)emphasize Math.random() performance, but nothing is really pressuring them to produce good quality. Sounds like the best thing to do might be to put some quality requirements in the ECMA spec to balance the performance pressures. Check out my recent Twitter likes for more details. I'm @mjmalone.

You don't need to check for duplicates with UUI4s if you have a good source of entropy. I'm not sure where you're getting your information, but here's what Wikipedia has to say, for instance[1]:

"To put these numbers into perspective, the annual risk of a given person being hit by a meteorite is estimated to be one chance in 17 billion,[4] which means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%."

There seems to be some sort of collective delusion that UUIDs magically appear somehow. Most UUID libraries are very small packages that contain code nearly identical to the code we're using. Many of the libraries that existed at the time this problem occurred actually used Math.random() under the hood. Moreover, we need our code to produce variable length identifiers for different use cases. Since we already need it, it's sensible to re-use it for a case where UUIDs might also be used.

In some places (when we're producing much shorter IDs, for instance, or in extremely critical sections of code) we do check the database for duplicates. In our Java-based accounting system we even use UUID1s for transaction IDs. I understand the trade offs. The code in question was being used to generate correlation identifiers for log tracking. The performance hit of checking for dupes would have been a waste.

PRNGs work find for many use cases. Please cite some source or at least give me some reasonable argument to believe otherwise.

[1] https://en.wikipedia.org/wiki/Universally_unique_identifier#...

There are legitimate reasons to have / not have some form of node id, and/or a timestamp, in an identifier. One reason to have them is that you don't need as good a PRNG. However, with a good PRNG the collision probabilities are astronomically low either way.

The point of the comparison to HDD error rates is meant to indicate that the collision probability is well within what is typically considered an acceptable risk level. There's a higher probability of much worse things happening, and I accept those risks for similar pragmatic reasons. Why should I behave any differently in this case? I do encourage anyone implementing this sort of system to do the math themselves and take whatever precautions they deem necessary. I've done so and decided that the additional complexity and space trade off of the alternative approaches make them inferior for our use cases. That doesn't mean ours is universally the best choice. That's why we have UUID1 and UUID4, for instance.

Applied Cryptography is a good book. I first read it more than 15 years ago :). Schneier actually designed the CSPRNG that is used by OS X. It's called Yarrow and is SHA based. It does more or less what you suggest, but with many subtle improvements to mitigate attacks. It has features that you're unlikely to properly reproduce in user-space. Trying to improve its output by re-hashing in user-space is, even if done properly, unnecessary. If you screw something up and do it improperly you could easily reduce the quality of the generator.

I'm not sure how your link is relevant. If there's not enough entropy on the system for the kernel, there's not enough for you either.

Meh. You should just use all of that random unique-ish stuff to properly seed your PRNG. You're trying to improve the generator "randomly," which is generally dangerous and can be counterproductive. Better to rely on sound theory and good practice / keep it simple. Leave all that craziness to the kernel entropy pool and just use it as a seed.

Just familiarity. Mostly I just can't recommend something I don't know much about. The SIMD variant of MT is architecture specific, I thought? Other newer variants of MT/WELL generators and PCG are probably all good options. Also xorshift*.

But I know that MT is a very good algorithm and using it has a certain pragmatic appeal - you make a lot of people's lives easier because when they Google to learn more about your generator they'll find good information quickly.

In other words the code itself is, in principal, fine. The PRNG it used was not fine. Had it used a CSPRNG there would not be a problem, and generating identifiers in this manner is perfectly safe and not an anti-pattern. Hashing the output of an already good (CS)PRNG is the real anti-pattern. It can only reduce entropy and make things worse.

I've acknowledged the incorrect assumptions / taken blame for not doing proper diligence on the PRNG. What I'm saying here is that the identifier generation technique is not, in principal, flawed. It is a common technique and it has many legitimate use cases. It's simple enough that pulling in a dependency to solve it for you is not an obviously better alternative.

True randomness and a crypto-strength PRNG are good options here, but they're not necessary. There are peer reviewed proofs that show something like MT19937 is suitable (perhaps even better suited) for this sort of task. See the deeply nested comment thread ITT for more of that debate.

Sure but I don't immediately see how that equates to a proof of its ability to produce every combination of, say, 52 consecutive numbers... Just that it will produce every possible individual number. In PRNG-parlance it shows 1-dimensional equidistribution but not 52-dimensional (or generally (k, w)-dimensional) equidistribution. Or is there another pigeonhole step I'm missing?

Ok, I get the seed/state space vs. cycle length bit. So it can theoretically generate all of the permutations of a shuffle if you re-key/re-seed periodically. But you can't guarantee that it actually will, right? It is possible that, for all 2^128 keys, and in all 2^128 cycles there are some shuffles that AES will never generate (in other words, some sequences of 52 numbers that will never be generated) so you effectively have a 0% chance of hitting them.

From a cryptanalysis standpoint I think that's consistent -- the probability of generating any particular single shuffle is astronomically low, so the difference between the actual probability and 0% is probably outside the realm of what's computationally feasible. But with something like MT19937 I can show that its at least possible for every outcome to have a non-zero probability. Perhaps this is just interesting academically, but maybe not if you're actually playing a card game for instance?

Good idea! But it looks like you re-invented a SHA/counter based CSPRNG :). That's not necessarily a bad thing, but there are probably library CSPRNGs that work as well and hide some details. Also, it's not generally any more or less likely to produce collisions than the method we're using. The probability of collision is dependent on the hash function / PRNG being used.

1. In this case we're arguing semantics. Fine, it's not broken, but it's still bad and there are better alternatives with no drawbacks. Arguing to keep it is sort of like arguing to keep an O(n) algorithm that has an O(log n) alternative that's also more intuitive and easier to code. If you still don't believe me, here's what Brendan Eich thinks[1].

2. I've addressed the standard solution / UUID question elsewhere[2]. The way we were generating identifiers is not an anti-pattern. It's a pattern. It's the standard way to produce a random string from an alphabet. If you look at the source code of any website, from HN to Google, I guarantee you will find an almost identical piece of code somewhere. The code is simple, but that doesn't make it bad.

[1] https://twitter.com/BrendanEich/status/667735502691373056

[2] https://news.ycombinator.com/item?id=10605977

I generally trust peer reviewed formal mathematical proofs that show something won't "fail" in a particular, relevant, way. If you don't then you probably shouldn't be on a computer. The code I'm relying on makes the same sorts of assumptions that keep your data secure. It is inconsistent to trust it in one place but not in another.

I don't see the need for belt-and-suspenders here and there are legit reasons not to add host/time to an identifier. That's why we have UUID1 and UUID4.

MT only fails LinearComp systematically. It is not a bad generator, it is a very good generator. The biggest problem is the "escape from zero-land" stuff where it's biased towards zero for a while if its seed is mostly zeros, but other generators have the same problem (though not to the same extent) and it's still statistically very unlikely to be a problem and it self corrects as the sequence runs.

Comparing to ChaCha20, which is a CSPRNG, is a little apples/oranges.

You're generating a random number (the UUID) then you're hashing it. It can't possibly have more entropy, and there's a chance two inputs to the hash will collide thus reducing entropy.

Hashing a counter is actually a variety of CSPRNG. Basically you're re-seeding a hash-based PRNG with whatever PRNG the UUID code uses at each run. It's well known that an PRNG cannot have more entropy than its seed. Hence, it will at best have the same entropy, and probably have slightly less.

Exactly, it's as hard and error prone as generating the randoms yourself. The solution you described requires an analysis of the hash function to determine collision probability, diligence to find a sha-256 implementation (circa a few years ago), review of said implementation, another analysis to figure out your truncation, then a proper implementation resulting in ~the same amount of code, except this time slower and with less entropy.

That's all fair-ish, and I think I need to learn more about CS alternatives. Necessary cycle length is relative. For crypto it seems like the definition is "big enough that it generates keys that are infeasible to predict," or "big enough that it can be used to stretch entropy a long ways for a cipher" for all practical purposes. But even the AES generator you cited sounds like it would be incapable of generating an unbiased shuffle of a deck of cards, which has 52! or ~2^225 unique shuffles... For a use case like this it's hard for me to wrap my head around using anything other than a good non-CS PRNG or true randomness. If you believe otherwise I'm truly interested in your thoughts, links, etc.

Another case where a long cycle length is useful would be the sort of scenario in my post, at much larger scale. If you have thousands of machines re-seeding at every service restart and then generating sequences of millions or billions of random numbers from a sequence, and you want a vanishingly small probability that those sequences will never overlap, could you use a CSPRNG?

Re: the generator properties, do you _really_ believe that? I mean, good non-CS PRNGs usually have fairly rigorous presentations and pass statistical tests. They aren't as sexy as crypto stuff, and maybe don't get the eyeballs, but they're relatively straightforward proven math whereas all of the CSPRNG results are based on conjecture. It seems at least as likely that some unexpected property of a CSPRNG will be discovered, a la RC4.

For the record, we are not and at no point have we ever used the Node.js PRNG to generate random numbers for our gambling games. That is an entirely separate, audited, and carefully controlled system. This code was unrelated to gambling. In fact, it was not even consumer facing.

If the attacker might gain something by being able to predict the next ID in the sequence then you should be using a CSPRNG. That's not a problem here. There's nothing for them to gain.

It absolutely is sensible. Adding node IDs and timestamps leaks information. If you add a hash function now you have two problems -- the hash of a random value is actually a _new_ random value with entirely different characteristics. You're falling into another trap. Which is why you might not want another layer of safety -- you're introducing another layer of complexity and another place to fuck up. You had good intentions, but in the scenario you described you've just introduced an additional point of failure with limited upside. Why wouldn't you do the math and implement the simpler solution using a generator that won't fail?

As I've said elsewhere, the likelihood of collision with our identifiers is lower than the uncorrectable error bit rate of a HDD. In other words, it's more likely for a perfect deterministic method to generate a collision because there was a hardware failure persisting it to disk. Or, more pragmatically, the risk is far below the level that any sensible person should ever be worried about.