[Cryptography] Speculation considered harmful?

[Henry Baker]

As the horror of the profound vulnerability of nearly the entire installed base of x86 chips starts to sink in, manufacturers are starting to downplay the effect of fixes on system performance.

The reason I say "downplay" is that computer hardware isn't the only place where speculation is utilized in computer science -- or indeed in society at large.

Speculation is an extremely comman, and an entirely human, reaction to *latency*.  If the latency of some operation is too long, we pretend that the most common case is occurring and try to fix things later if/when we find out that we've been wrong.  (Indeed, evolution works precisely *because of speculation*.)

Thus, if we are copying a 10 GByte object using a tight loop, the chances of the loop continuing rather than stopping are 99.9999999%.  As I have argued sardonically in the past, most economic systems with 9 "9's" would have optimized away the stopping condition entirely; computer code compilers can't be allowed to do this!  So we are willing to do quite a lot of work to "undo" any mess that a flawed assumption might create, if the probability of making flawed assumptions is low enough.

This is called "optimistic concurrency control", and it is used *all over the place* -- not just inside of computer operating systems.

Every economic system utilizes the same trade-off: shutting down a factory is an incredibly chaotic mess, but with overwhelming probability the factory will continue producing day after day, so we optimize for that case.

Indeed, the 2009 financial crisis was deepened and lengthened by the (probably correct) assumption that if the banking system were allowed to shut down, the resulting chaos might just be worse than attempting to fix the system.  Unlike the situation that Intel/AMD/ARM now face, the U.S. Federal Reserve System was unwilling to take that risk, and we will continue to pretend that our financial system is sound.

The problem with eliminating speculation, though, is that it interacts *substantially* with security and privacy.  Our entire "free" society is built on the assumption that the vast majority of people will be good, and that the bad people can be (messily) rooted out before the harm that they cause becomes catastrophic.  We consciously made a trade-off between the efficiency gains from free people determining their own actions versus the heavy hand of a government intent on smothering any small ripple of chaos.

President Eisenhower said it best: "If you want total security, go to prison.  There you're fed, clothed, given medical care and so on.  The only thing lacking ... is freedom."

Our credit card system was originally based upon *trust*, which is a form of limited speculation.  Everyone in the system, from banks to merchants to card-holders assumed that the vast majority of transactions would be legitimate, and that the various fees would offset the small % of losses.  It's hard to imagine in this era of ubiquitous connectivity that there was initially *no* real-time validation of credit card charges!  However, over time, connectivity became better and better (every credit card terminal acquired a telephone or satellite modem), and so today nearly all such transactions are checked in real time.

Only in the 20th and 21st centuries have we had the luxury of speed-of-light communications and sub-second latencies, so that we can often replace *optimistic* concurrency control with *pessimistic* concurrency control.

When an ancient Roman general took his army over the horizon, he might be out of contact for *months*, so pessimistic concurrency control simply wasn't an option.  If he screwed up, the only option was to send *another general and another army* over the horizon to repair the damage that the first general and army had caused.

Ditto for 15th century sea captains.

NASA has the same problem with its various robot spacecraft -- multi-minute or multi-hour latencies simply don't allow "hovering helicopter management"; expect upcoming interplanetary economic systems to re-learn old lessons on speculation.

So now the question remains: how can we construct computer systems which enjoy the benefits of speculation without enabling wholesale compromise?

It isn't going to be easy, as there isn't a simple fix.

So-called "two phase commit protocols" attempt to gather all the information and resources necessary to *complete* a transaction prior to "committing" the transaction.  If the transaction can't be completed, than it must need to be "rolled back" -- a process of *undoing* any actions that were done during the gathering phase.

There's only one slight problem: you can't unring a bell: you can't "unlearn"/"forget" a bit that you learned during the gathering phase.  Or more precisely, you can't force a party to the transaction to forget such bits.

I don't have a clean solution to this "forgetting" problem, and I doubt that anyone else does, either.

We have similar "Ben Franklin" problems in crypto all the time: "three may keep a secret, if two of them are dead".  We can't shred entire computers every time an optimistic transaction must be rolled back.

Perhaps Zero Knowledge protocols may point the way towards a solution.  I'm not optimistic.