Archive

Ineffective Theory

Links for July 2021

An extensive reading list on the economics of innovation.

Hayek on intellectuals, and indeed on the social construction of science. Relatedly, Musa al-Gharbi on a particular modern aspect of this dynamic.

Weights for a network of comparable performance to GPT-3 have been released.

The rust compiler is a SAT solver, although not a particularly fast one.

Some evidence that society is become more depressed-ish over time. See the Hacker News discussion for appropriate skepticism, but I don’t think anything mentioned there invalidates the conclusion that there’s a trend in written English towards more distorted phrasing and thinking. See also Scott Alexander: “He who has ears to hear, let him listen.”.

From Balaji Srinivasan, cryptocurrency as economic education.

Notes on Quantum Error Correction

I gave a set of two short lectures at Fermilab’s QCIPU summer school. The subject was quantum error correction. I’ve uploaded the notes, targeted to undergraduates being introduced to quantum computing for the first time, here.

Do not hesitate to email me to let me know how wrong the notes are.

Do cosmic rays cause domain name bit-flips?

Betteridge’s law strikes again. No, they really don’t — at least not at any appreciable rate.

Back in 2011, one Artem Dinaburg wrote about an unusual black-hat strategy: “bitsquatting”. Occupy domains that differ by a single bit from a frequently visited domain — like gnogle.com. Memory errors do occur occasionally, typically in the form of a single flipped bit, so you’ll get some traffic. (Go to that link for some justification of why these are almost always memory errors, rather than, say, being induced on the network.) A key part of this is choosing a domain with an absolutely enormous base level of traffic, so that even if a very small proportion of traffic gets redirected to your bit-flipped domain, you’re still getting something.

This works pretty well. Dinaburg reports that, after registering 32 domains, he logged tens of thousands of requests over about half a year. This leaves open the question of what’s causing these bit-flips. One explanation frequently put forward, including by Dinaburg himself, is that these bit-flips are caused by cosmic rays: high-energy particles that originate far away (typically elsewhere in our galaxy), travelling thousands of light-years just to redirect you from fbcdn.net to fbbdn.net. This speculation has been repeated all over the place, including on Wikipedia.

Let’s do some crude estimation. To get started, in the 90s, IBM supposedly estimated that cosmic rays should cause one bit-flip per 256 MB of RAM per month, or around one per 8 GB per day. The “per day” is very important, since cosmic rays will not preferentially strike just when you happen to be browsing. Taking this estimate seriously, you can see that a “GB-day” (or, more conveniently, a “bit-second”) is a sort of unit measuring how much opportunity there is for bit-flips. Apparently, there will be one cosmic-ray-induced bit-flip per $10^{16}$ bit-seconds of opportunity.

How many bit-seconds of opportunity are there? I can’t find super reliable statistics on the number of connections any of these big domains receives, but most seem to be on the order of 10 billion. As you’ll see, being off by a factor of 10 or 100 here doesn’t seem fatal.

Each request doesn’t take very long, and crucially, most of that time is network latency, which is irrelevant. Let’s be very conservative and say that there’s $10^{-1}$ seconds during which a single bit-flip might redirect you to gnogle.com or fbbdn.net or whatever. That means there are $10^{9}$ bit-seconds of opportunity for my squatting domain to receive a request, each day. Even with this conservative estimate, we’re missing something like a factor of $10^6$ before this is a significant contributor (at the one-percent level) to the requests Dinaburg received.

Now that all was taking IBM’s 1996 estimate at face value. I can’t find the original study, only a bunch of articles talking about it, and besides, it’s now 25 years out of date. Electronics have shrunk, including RAM. On the one hand, this presumably means lower energies are needed to flip a bit; on the other, there’s a much smaller surface area per bit!

Could we possibly make up that factor of $10^6$ by saying that “modern RAM is more vulnerable to cosmic rays”? Well, we’d need to raise that figure of one per 8 GB per day to something more like one per GB per second. This is easily checked: write a bunch of ones to RAM, wait a second, and then count how many ones there are. No, cosmic-ray-induced bit-flips aren’t nearly that frequent. (By the way, when I do that test, I never find any bit-flips. I’m pretty sure IBM’s estimate is far too pessimistic for modern computers.)

It’s very important that the cosmic ray flux is time-independent, and doesn’t care what you’re doing on the computer. This is not true of other sources of errors, which are more likely to occur if the bits in question are being actively manipulated. Even if half of all bit-flips are cosmic-ray-induced, these bit-flips will still not contribute to the fact that bitsquatting works, because almost all of them will occur in irrelevant places.