Speculation considered harmful?

["Dave Farber" <dave () farber net>]

---------- Forwarded message ---------
From: Henry Baker <hbaker1 () pipeline com>
Date: Thu, Jan 4, 2018 at 1:47 PM
Subject: [Cryptography] Speculation considered harmful?
To: <cryptography () metzdowd com>

It is not just intel!!

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.

_______________________________________________
The cryptography mailing list
cryptography () metzdowd com
http://www.metzdowd.com/mailman/listinfo/cryptography



-------------------------------------------
Archives: https://www.listbox.com/member/archive/247/=now
RSS Feed: https://www.listbox.com/member/archive/rss/247/18849915-ae8fa580
Modify Your Subscription: https://www.listbox.com/member/?member_id=18849915&id_secret=18849915-aa268125
Unsubscribe Now: 
https://www.listbox.com/unsubscribe/?member_id=18849915&id_secret=18849915-32545cb4&post_id=20180105133456:1F154626-F247-11E7-8856-8E894FB59A16
Powered by Listbox: http://www.listbox.com