That's impossible!

Distributed computing, like many mature areas of computer science, has its share of impossibility results.  I was lucky to be in the field before many of them were discovered, and because I'm basically a software builder, my research group built all sorts of distributed systems and tools.  Later, though, the theory community showed that some of those things were impossible, which leaves a puzzle: How can anything solve an impossible problem?  

Today, I thought it might be fun to explore an example.  I want to go deeply enough into the question to shed light on the limitations of what is feasible in computer networks and cloud datacenters.  At the same time, we'll also discover limitations on what can be modelled and proved, and even some limitations on the subtle ways that choices of wording (in English) can shape perceptions about what can and cannot be done.  

When we talk about consistency in a distributed system, people generally map the work to their favorite model. For fans of database models, this might be transactional serializability and the ACID properties: Atomicity, Correctness, Isolation and Durability.  Distributed systems researchers would point to State Machine Replication or Linearizability.  The systems I created also worry about dynamic changes to the pool of servers, and have a consistency mechanism called virtual synchrony: membership changes in atomic steps.  During a period when membership is stable (an epoch), we use state machine replication within the members.  Protocols like Paxos solve this part of the problem.

If you take a big step back and abstract, all of these forms of consistency boil down to forms of fault-tolerant consensus: we have some set of processes, and they propose various kinds of actions, and vote on what action to do next.  Consistency is the property that that they all decide the same thing.  Thus, anything we can say about fault-tolerant consensus sheds light on fundamental limitations that apply to databases, distributed systems, and all sorts of other settings.

Any mathematically-based discussion starts with a model.  For example, what does it mean to say that a failure has occurred?  The most obvious choice is to say that well, some component halts -- it crashes suddenly and without doing anything horrible right as it collapses.  But it is easy to come up with other failure models.  

For example, consider timing.  If a processor has a local clock that fails (drifts from the truth, or perhaps starts to show nonsense values), sometimes the remainder of the system stays healthy, even including the process on the machine with the faulty clock.  Yet that could cause the process running on that machine to "lie" about what time some event occurred, or to miss a deadline.  We tend to wrap all of these up, and call them timing faults.  

Communication faults are tricky to model too.  You may not be aware of this, but on Linux a process could send a message, but then the operating system or network could drop it.  Should we blame the process itself?  The network?  And should we say that the message wasn't sent, or wasn't received?  Worse, a network could split into parts that can't talk to each other: network "partitioning" failures.  

Then we get the "hit by a cosmic ray" issues.  Things like that (or more mundane problems like a power fluctuation) can cause the computer memory to flip bits.  As a result, a process could experience some form of data corruption.  And this doesn't even consider the case where the process is hijacked by a virus.  We tend to lump all such issues into what we call "malicious" failure models, but even within the malicious models, there is a range that includes whether or not one allows collusion, as opposed to a strictly isolated form of nefarious misbehavior: A virus that can infect one process might be able to infect every process running the same code, and then mount a coordinated attack on something else. In contrast, that bit flip is just a case of flakey hardware and would only impact a single process at a time.

There is a lot of work that explores this range of behaviors.  In fact one model, called the BAR model of failures, starts with these cases and then goes further by introducing incentives: are the participants out to cause chaos (a so-called byzantine case)?  Or are they altruistic?  Purely rational?  Crash failures are then layered in, giving a cross-product that you can study to yield an abundance of impossibility results for tasks like reaching agreement or electing a leader.  

For our purposes today, the result I want to discuss is one from a paper by Fischer, Lynch and Paterson called Impossibility of Consensus With One Faulty Process.  We often refer to this just as the FLP impossibility result, and it is arguably the most famous of all such results.   As the title suggests, the paper seemingly shows that agreement (consensus) is actually not possible if a system is at risk of crash failures.  On the face of it, the FLP assumptions about the network and the possible failures are very mild -- and the result seemingly implies that databases, Cornell's amazing new Derecho system, dozens of other Paxos-based systems, Blockchain solutions for Bitcoin (all of which can solve consensus) are "doing something impossible."  Indeed, FLP seems to imply that the very idea of consistency as a goal is hopeless: if we accept the title, don't waste your time building a database!  But as we will see, a lot centers on the details of what the words in that title actually mean.  The result is a real, valid, one.  It does apply to all of those kinds of systems.  But it doesn't mean we should pack up and head home.

The paper came out in 1985, which was an important year for me: it just happened to be the year when I wrote my first paper about a distributed system my students and I had created, one that implemented atomic multicast and Paxos and could be used to solve all sorts of practical agreement problems.  We called it Isis (as it turned out, an unfortunate choice).  Isis was released to the public, open source, and by 1987 or so it had a surprisingly wide uptake.  The system was ultimately used in the New York Stock Exchange to run the trading floor, was adopted in the French Air Traffic Control System where still is used for many purposes, and even into the Oracle database product, which launches Isis every time the Oracle cluster management system boots -- and this is just a few examples.  

As you can guess, right from the start I was getting questions about FLP, including in panel sessions at major conferences where this oddity was debated.  My mother (an academic) has a saying that academic debates become heated precisely because the issues really don't matter.  The big conference in systems, SOSP, was infamous in that time period for fireworks, very much validating my mother's point.  In retrospect, I would have to say that relatively few SOSP attendees cared in a deep sense about FLP.  But they were curious to understand the result:  The paper is short and easy to read, but surprisingly hard to map to any simple intuition about what it "means".  And let's face it: they also enjoyed lively panel debates.

Isis users didn't fuss too much about FLP: if they knew about it at all, they perceived it as an oddity.  For a decade, all those traders on the floor of the NYSE happily traded stocks.  Eventually the parts of the system that used Isis were phased out during a routine upgrade, but not because it had caused any issues -- in fact there wasn't a single disruption to trading during that entire ten-year period (crashes did occur, but Isis orchestrated self-healing recovery in every case).  

By now, the French ATC system has been safely guiding airplanes since 1995 and will probably not be upgraded before 2025: a 30 year run!  The designers of those platforms, and others, liked Isis both as a practical tool and because of its consistency-preserving consensus mechanisms.  Isis created a world of state machine replication elements, which enabled self-managed, self-healing applications.  Moreover, just as Isis itself could be described easily using the mathematics of state machine replication, those applications could also be proved correct and safe, even when components failed.  

For example, one obviously wants to be sure that an Air Traffic Control System guarantees that each plane and each airport runway will have a single designated controller who is responsible for managing it.  Isis allowed the French system to obtain this property.  Each flight should have a single active flight plan; any change to the flight plan subsumes the prior one.  Isis was central to their correctness proof for this property, too (one can think of an ATC system as centering on a log of flight plan versions, in which each change is a durable append to the log, and the current flight plan is always the version closest to the end of the log).  

ATC systems never generate huge loads, and for this reason it was also possible to quantify the system's performance profile, and even to show that performance was stable across a wide range of stress tests and failure sequences (one does this by designing tests that carefully measure delays and bandwidth even as failures are injected to mimic scenarios believed possible during actual operation).  This enabled the developers to convince skeptics that if the workstation used by some controller were to fail, someone else would take over the role within 30 seconds.   During certification, the French used red-teams that were free to pour over the protocols, the code, and the way the system used it.  Then they would often demand proofs for challenging scenarios they would construct.  Sometimes the best response included a mathematical argument, but more often, these red-teams wanted to see experimental responses: an experiment that would mimic the case they worried about, and ride it out successfully.  Over time, the system evolved to have an enormous range of unit tests and integration tests.  Isis passed every test... and yet, FLP sits there.   

Curiously, the one time I can remember this coming up, the red-team dismissed the FLP work, feeling that it made assumptions that didn't apply in an ATC setting (as we will see, FLP is posed in a very abstracted way, and assumes a very general model of the network).  Yet I still felt that I needed a really cogent answer.  Suppose that someone really were to challenge Isis in this way.  What would be the best possible way to respond and explain how Isis relates to the FLP result?  

In fact this was an actual worry for me.  Those customers trusted me, and under my guidance, we were using the Isis system for applications where it genuinely matters that the solution have safe, consistent, self-healing behavior, and within seconds too!   We had correctness proofs for the system (really, proofs of safety, not liveness, but the performance work had the flavor of a liveness claim).   FLP proclaimed this combination of guarantees to be impossible... how can that be?  Indeed, there were follow-on papers that appeared soon after FLP, pointing out that Isis and its version of Paxos were clearly subject to the FLP impossibility result.   I had no choice but to figure out the proper rebuttal.  

A great deal of the explanation centers on the FLP paper's approach to modelling the problem.  Earlier, I said a few words about their system model, but didn't mention the network, and I didn't explain how they define asynchronous execution.  So let's tackle those aspects first.  The FLP paper assumes a network that mimics several aspects of TCP.  Processes are permitted to send each other messages, and FLP assumes that these are sent over reliable network channels that never drop, corrupt or duplicate packets.  I mentioned earlier that Linux, and the network itself, can both drop messages.  But in fact if you use TCP, the TCP protocol itself compensates.  On the face of it, FLP seems to assume exactly what TCP guarantees in a standard networked system, like a cloud data center.  TCP, as you probably know, obtains this behavior by sequencing data, and then using explicit acknowledgments or complaints ("negative" acknowledgements) to trigger retransmissions and rate control.  Duplicates can be filtered out because TCP has already seen those bytes.  

On closer study, the FLP network model departs from TCP by allowing out-of-order delivery.  Moreover, this matters: their proof requires this property, because it involves delaying some messages and allowing others to skip past the delayed ones (we'll see how they use this feature in a moment).  For a while, it seemed plausible that this could be the key.  Perhaps state machine replication seems to be very possible because we run on TCP (mostly), and it delivers messages in order.  However in the end, it turned out that this particular aspect of the FLP model was unimportant.  FLP applies even to a protocol built over TCP or RDMA.

Another puzzle relates to the way the FLP model defines asynchronous behavior.  In the FLP description of processes, there are no clocks and indeed nothing even faintly resembling a clock: a set of processes could run the protocol for a billion years before achieving agreement, and this would be "just fine."  Obviously, an air traffic control system wouldn't be happy with billion year delays, so real systems like Isis and Derecho have timers built in: if some process isn't responsive, the others vote the silent one out.  To avoid a partitioning event (where our ATC system might split in half, with two subsets that each believe the other to have crashed, implying that two controllers would think themselves responsible for the same plane), we just require that in any such vote, a majority of the system has to "survive" long enough to vote in favor of the new membership.  The majority rule eliminates the risk of split-brain behaviors, which could threaten safety.   

These points, it turns out, are a bit more complicated than the one involving TCP.  The first thing to appreciate is that rapid responsiveness is very important in an ATC system.  When a pilot is approaching a landing strip, the ATC system is under a timed obligation to tell the pilot what to do: should plane A land first, or will plane B land first?  Can plane A to climb 2500 feet to avoid that thunderhead?  

Failures can threaten those quick responses, and this means that an ATC system may be in a hurry to kick out an unresponsive component.  Yet if a pilot was cleared to land, but then the original controller's computer freezes and a new controller takes over, he or she should know about that prior clearance.  This turns out to be the same requirement as the FLP rule that if any process decides v, then every process decides v.  This tells us that even though ATC systems are biased towards availability, the most fundamental aspect of the FLP way of defining consensus still applies.

What about clocks?  Real-world control systems like ATC platforms make heavy use of time, and take precautions to protect against errors that could be introduced by machines with faulty clocks.  FLP had no clocks... does this somehow take us out of the FLP scope?  One can imagine that it might: clocks enable timed actions, and we use timeout for fault detection: an ATC platform will give up on any tardy process and treat it as faulty, simply because we don't want the entire system to end up waiting for some very overloaded machine to catch up.   Doesn't FLP itself need a way to model the detection of failures?  And because timeouts are a form of non-determinism, how can we reconcile this use of time with the deterministic state machine model for the protocol itself?

As it turns out, FLP does have a way to handle non-determinism.  In the state machine formalism, processes are state machines, but FLP allows states to have null transition edges.  That is, if a process (call it p) is in some state s, FLP models p as having a set of possible next states that we could reach from s: perhaps, states s' or s'' (loop-back edges are fine, by the way, so one these could just be s itself).  Each such transition is described by an edge in a state transition graph, and these edges are labeled by a kind of pattern that will unambiguously tell us which transition to take.    Thus, when a message is available, we could either consume that message, or take a null transition: a non-deterministic event. 

Given that the behavior of a deterministic state machine is fully determined by its sequence of inputs, you can see that the real question centers on the decision as to whether the next input will be a message or a null.  FLP gives the network this power: they model the network as an active entity that makes its own decisions.  In general, the network has a set of messages ready to deliver, and decides which to deliver, in what order, and whether or not to deliver a null to some process rather than a message.  Thus, in the FLP model, timeouts are viewed as a network "decision" to deliver a null message in a state where the protocol may have been waiting for something else (perhaps p is waiting for a message from q, but instead gets a null, and interprets this to mean that a timeout has occurred).

FLP's network is unusually powerful.  In effect, it is able to scrutinize each and every message, selectively deciding when to deliver it.  There is an obligation to eventually deliver every message... but no bound on how long the network can first delay it.  And here, it turns out, is the crux of why FLP concludes that consensus is impossible, even though protocols based on the Paxos model solve consensus billions of times every day.  Real systems always timeout when a process has been unresponsive for more than a few seconds.  But FLP doesn't require the network to behave that way.  The network controls null transitions, yet it might not do so in a way that has anything to do with timeouts.  Here, then, is another possible candidate for explaining why FLP doesn't preclude building your favorite consensus-based technology: FLP's way of using nulls has no connection at all to timeouts, and doesn't actually model the way that timeouts are used in real systems.  And let me add: this is a very credible argument.  Many people invested years thinking about this exact argument, or ideas somewhat like this.

There is an old adage about big systems that if something can happen, it will happen.   The FLP authors would argue that their network simply schedules messages, that nulls are examples of places where a timeout could have occurred, and that because even TCP may have to retransmit a few times before a message gets through, that delayed delivery is a real and valid thing.  Thus any schedule FLP invents could arise in a real system, particularly if you imagine that a network link was somehow broken, then later repaired.   But as we will see (and one can easily turn the observation into a rigorous proof), the FLP network really has impossible superpowers, because the particular messages that end up being delayed this way, and the particular moments when a null transition occurs, need to be chosen with exquisite care.  Yes, each individual event could occur in the wild, but every one of them would be so unlikely that any sequence of them would be of zero probability: the probability of a sequence of unlikely events is the product of their probabilities, and with small probabilities, we approach zero exponentially quickly.    Yet just this kind of zero-probability sequence is the core of the FLP proof.

To see all of this in action, let's walk through a scenario that the FLP proof constructs.  Imagine that we have built a system that must vote on something, 0/1 and that we happen to be in a scenario with a near-tie.  Further, assume that we were given a tie-breaking rule.  Normally, there actually won't be a tie, but a failure could result in a tie, and then we would use the tie-breaker.  For example, perhaps we have 11 processes, 5 vote 0 and 6 vote 1.  The winner of this vote should be 1, but only if all of the 6 votes for 1 are tabulated.  If one crashes, we have a 5:5 tie, and the tie-breaking rule might award the win to 0.

FLP sets up this scenario, and the proof centers on delaying messages to confuse the protocol about whether to use its normal rule, or the tie-breaking rule.  They show that any fault tolerant protocol that can switch over and use its tie-breaking rule would require a few state-machine transitions during which, presumably, it would be internally reconfiguring to switch modes.  Then, just at this moment, FLP delivers the delayed vote, selecting some other message and delaying it instead.  In effect, just as the vote itself was a multi-step procedure, they are playing with the idea that switching to tie-breaking mode would also be a form of consensus: another multi-step procedure.

In a formal analysis they actually treat both of these as transitions from a state with two possible outcomes (0 or 1) to a state with just one decision.  And what they prove is that in any such state, a network can selectively delay some messages, and selectively deliver other messages (or nulls), and force the system back to a two-outcome condition.  Then they let the delayed messages through and attack again, in the identical way.  Thus, any decision is indefinitely delayed.

Interestingly, they can do this without any failures at all: they prove that any fault tolerant consensus protocol has a run in which no process fails, and yet even though nothing fails, no decision is ever reached!  But the key is that the network must have that superpower enabling it to selectively delay just the right messages at just the right instant, while also knowing just when to deliver the delayed messages, so that the network obligation to eventually deliver every message is respected.

From this, we can see that FLP authors actually meant something peculiar by their use of the word "impossibility."  In normal conversation, impossible means just what it sounds like.  If I tell you that it is impossible for a protocol that can only decide 0 or 1 to decide -1, we would all agree on this.  But given what I've described, if I claimed that it is impossible to build a network that has the properties assumed by FLP, you would probably agree with me.  The FLP authors would disagree: for them, "exponentially convergent to 0 probability" still leaves that tiny, ultra-unlikely bad case.  No matter how unlikely, if a system could exhibit some behavior, the FLP model would consider that it is possible for that behavior to occur. 

Conversely, in FLP, impossible also has a meaning... but not the meaning I might instinctively assume.  Think about the classic definition of correctness for a protocol, as Dijkstra first did: a correct algorithm is one that guarantees safety (nothing bad happens, using a predicate to define bad behavior), and liveness (something good eventually happens).  The FLP definition of impossibility centers on liveness: if you really dig deep, FLP is telling us that if we have a safe consensus protocol for some asynchronous distributed system, it cannot also be a live protocol.  A person could be forgiven for assuming from the paper's title that that there are no correct (safe) consensus protocols, but this is not what the paper actually does.  In fact it does the opposite: it assumes we have a safe protocol, and then shows that the protocol cannot also guarantee liveness, by pointing out that the zero-probability schedule discussed above is capable of delaying decisions indefinitely.

We arrive at a peculiar insight.  On the one hand, ATC systems and other similar distributed applications need to make quick progress: we don't want an ATC system to delay for a billion years before deciding who can land on runway 2-E.   This leads them to reconfigure if a process seems unresponsive, dropping that slow process to remain highly available.  At the same time, they do require safety guarantees, and those stem from the safety properties of consensus.  Due to the risk of network partitioning, we know this approach can't guarantee liveness, but we accept that because the frequency of network partitioning is very low -- data center power loss is a more common problem.

Then, on the other hand, we have FLP.  One could brush it to the side and say that well, FLP isn't relevant here.  But is that really correct?  FLP doesn't consider the network partitioning scenario we knew about (and that already precluded liveness, given our availability goals).  Yet FLP seems to be warning that even if we could somehow eliminate this exposure to a crash due to partitioning, there is actually is another "unstoppable" scenario, involving a peculiar network behavior, that no consensus protocol can defend against.  

But this leads to another insight: Reverting to Dijkstra, those of us who deliver safety-critical code to ATC organizations might actually want to prove that our systems are safe and live.  FLP teaches us that if you wish to prove that a system like Derecho will always make progress, you'll need to introduce some extra assumptions beyond the ones FLP employs.  Without extra assumptions, we can't create such proofs because if we could, we would have violated FLP.  How might those assumptions look?  Think of them as a list: "if there are no network partitions, and if the network has no way to selectively delay messages... ".  What would that list of conditions need to include?

There has been wonderful work on this question too: in a famous paper, Chandra and Toueg (later joined by Hadzilacos) described a very basic two-phase commit protocol for consensus, and worked out the weakest assumptions one can make that would still allow it to guarantee liveness: something they called the <>W failure detection oracle.  The plain-English name for <>W is "eventually weak", and in plain English, <>W is a failure detector that can make mistakes, but where eventually, some non-faulty process is recognized as healthy by all the other non-faulty processes.  This state needs to be sustained for long enough for the consensus protocol to terminate, and <>W expresses that by just saying "and we stay in this state forever".  

More recent work by Idit Keidar and her systems, notably Alex Shraer, showed that in real systems, one can generally assume a stronger failure detector called <>P.  This failure detector can make mistakes for a while, but eventually settles into a state in which it makes perfect failure discoveries for long enough to allow consensus to complete.  

In a real system, there is actually a way to create a <>P guarantee.  The trick centers on making sure that if any process suspects q of having failed, q really has crashed.  How do we solve that aspect?  The real but somewhat silly answer is that real systems reboot, reimage or replace malfunctioning components.  James Hamilton came up with this little adage, and we refer to it as "Hamilton's three R's."  In effect, we unplug q.  Voila!  That process has definitely failed.

In a setting where we can assume <>P, FLP would actually not apply.  Now, Derecho and similar systems can be shown to be both safe and live.   Of course, events that violate our assumptions can still crash the system -- network partitioning, loss of datacenter power -- but our proof would hold as long as those conditions for progress are maintained.   

If you really ponder the point, with a <>P solution based on Hamilton's three R's, FLP becomes a network partitioning attack: rather than delaying messages, it kills so many processes that Derecho would shut down, and Paxos would stop accepting new updates or letting applications learn (read) the committed part of the Paxos log.

All of this discussion... just to address one impossibility result.  In fact we have many others, and they come with oddities too.  For example, there are many such results for Byzantine Agreement, where we have a set of processes, and some subset of them can fail in any way you like, including malicious behavior crafted to disrupt the system.  But the Byzantine model normally is explored in networks with perfect clocks and perfect synchronization -- and we don't have such networks.  Moreover, with Byzantine solutions, if the number of faulty components reaches and then passes the assumed limit, all bets are off.

Let's generalize this to the broader question I posed at the start.  If distributed computing theory is full of these kinds of pitfalls and peculiar results, what does that tell us about the discipline as a science?    To me, the moral of the story is simply that theory motivated by real systems can shed valuable light but that one has to view these results with a degree of sophistication and caution: they might not mean quite what you would assume, even if the paper you are studying has an especially provocative title.  The mathematics teaches deep things, but it often isn't trivial to relate those insights back to your actual system.

But this also makes it very hard to teach this material, especially to students who distributed computing as an interesting curiosity, but not necessarily as a topic they really want to wrestle with.  While a comprehensive course would certainly delve deeply into the theory, the subtle nature of the result makes it very hard to include FLP in a more practical course, like my spring class on cloud computing.  For very practical students, when they hear that FLP says that consensus is impossible, there can be a tendency to jump wholeheartedly into Brewer's CAP model, with its "you can have two out of three" mantra. It happens that CAP is not a theorem and is often not even true, yet it can seem like a very simple and appealing rule of thumb.  CAP tells my students to just assume that consistency is hard and promises them (perhaps, falsely) that inconsistency is far easier.

I did spend part of one lecture on FLP this spring.  I worried that the course might otherwise be unbalanced -- that I needed to at least expose the students to a few of the most important theoretical results.  In that lecture, my main message was that one shouldn't take every paper's title at face value.  I get them to propose definitions of "impossible" and then surprised them with the FLP meaning of impossibility.  And I do think they understood the point: most later got a quiz question on this right.  A good tradeoff: after all, FLP really is a lovely bit of mathematics, and at least they heard about it.

Blockchain verification and the dangers of branching temporal logic models (very technical)

Many years ago, I worked with some colleagues on an ill-fated topic: we tried to write down a logical statement concerning the guarantees provided by atomic multicast systems that manage their own membership.  Today, we know how to do that, courtesy of Lamport’s Paxos specification and the proof methods he introduced.

But those were the Wild West days, and that particular project occurred before the Paxos specification was created.  Moreover, our atomic multicast (which actually could be configured as a Paxos protocol), also included some optional features Leslie omitted from Paxos, for good reason.  Those centered on a form of optimistic early delivery combined with barrier synchronization (analogous to a memory fence).

Our puzzle centered on expressions describing "all the possible" future behaviors that could arise with this rather complex optimistic form of early delivery.  The problem was that the set of future scenarios grew exponentially as new members join and existing members failed (or exited voluntarily).  Our logic needed to "account" for all of these possibilities.  In fact, the logic itself had a flaw, but even had we managed to write it down properly, we still would have had a semantic in which statements can only be interpreted within the “space” of future scenarios.  Since it is intractable to do model checking in an exponentially growing state space, such statements are often undecideable: they can have a true or false value and yet no decision procedure can be created that will terminate in bounded time.

A total mess.  We ultimately abandoned the effort, tails between our legs, and came to view it as an embarrassment.  The less said about it, the better!

Except... I sometimes tell the story, as a cautionary tale.

Not every technology suffers from the issue we encountered.  Lamport's way of formalizing Paxos avoids the issue by avoiding speculative "early delivery", which was the real issue in our early work.  This is one reason that Lamport's Paxos specification was such a success.

Transactional database models also have a better way of handling such problems: when we ask whether a database system is in a serializable state, the rule is to start by erasing all the uncommitted transactions, at which point serializability is defined as a property of the committed state.  This approach accepts that transactions could glimpse inconsistent states while executing: it isn't a problem so long as those transactions can't commit.  Moreover, it erases all the events that depend on future outcomes, neatly avoiding the whole issue our unfortunate effort ran up against.

Which brings us to BlockChain.  I'm intrigued by the recent work that seeks to put a kind of transactional database behavior "into" the BlockChain, by incorporating SQL-like statements into the transactions themselves, but then reevaluating them as the BlockChain steadily grows.

To appreciate why this poses the same problem I struggled with twenty years ago, think about a smart contract that says something along the following lines: "John agrees to sell me his horse, Bucky, for the sum of $1,500, and has accepted a $150 deposit.  If I haven't completed the purchase within a week, John agrees to return the deposit.  But in the meanwhile, John can continue to try and sell Bucky.  If he finds another buyer, he can cancel my transaction, but in that case must both return the deposit and also pay me an addition $100, to compensate me for my trouble."

The world is full of contracts like these.   Smart contracts can express things like rules for computing interest that depend on global interest rates.   We probably all remember 2008, when the world financial system melted down over issues with mortgage-backed  securities split into interest and principle.  The claim is that the expressive power of smart contracts is a good thing, because smart contracts can be analyzed by tools (compiler-style tools), and hence it should be possible to automatically identify risks. Risk managers would then have robust ways to compute their risk and hedge against it, and those hedging contracts (insurance deals) could also be carefully evaluated, etc.  Back in 2008, it wasn't the mortgage-backed securities that collapsed, per-se.  It was the insurance companies that insured them, but didn't hedge the "secondary" risk properly.

So... how does one attach a "formal meaning" to a smart contract?  Let's go back to John's sale of Bucky.  Notice that this contract depends on how things play out into the future.  For the coming week, the BlockChain will grow, and each new block added to the chain could bring events relevant to the contract.  John could decide to cancel the contract and sign a new contract with Sally (perhaps she is ready to pay more -- enough to more than compensate John for the $100 he'll forfeit).   I could show up with the remaining $1350, and head home with Bucky.  A week could pass, and John would have to return my $150 deposit.  And it gets worse: John could sign with Sally, but then Sally might cancel her deal, and perhaps John would then want to reinstate his deal with me.

Much as in that early work I tried to do, John's smart contract with me has a meaning that can depend on a branching future state: some large (maybe exponential) space of possibilities, each leading to its own proper interpretation of the correct "thing to do".  Should John hand Bucky over to me, or not?  Do I owe him $1,350, or does he owe me $150, or should it be $250?

Without much trouble, we can design sequences of smart contracts in which to know the proper outcome for my contract, I need to figure out the outcome of Sally's contract (and this then becomes an induction, because Sally's contract may depend on the outcome of Carl's contract).  This is precisely how my early work failed: you end up with scenarios that can be arbitrarily prolonged, and the total space of scenarios grows exponentially in the length of the future chain,  because of an endlessly longer sequence of new events that each depends on its own future outcomes.

Beyond all of which we have the issue of rollbacks: even if you accept the common wisdom and adopt the view that a BlockChain prefix has magically "committed" once it has been extended by six or more blocks, we still run into the problem that the suffix is unstable.  So we could have one suffix in which Sally's transaction finalizes, but it might then rollback, aborting that outcome and perhaps replacing it with one in which Sally cancels her purchase.

Should it trouble us that smart contracts on BlockChains might not have a tractable meaning -- a reduction to temporal logic -- if they include future references?  For that matter, even without future references, some of the aspects just mentioned would still arise.   Is this bad?

I think so: it seems to me that in computing, if we're learned one thing over the decades, it is the overarching importance of rigorous semantics.  If BlockChains with smart contracts can't be reduced to a stable logical framework in which proofs can be carried out without solving infeasible problems (evaluating logical formulas within exponentially growing state spaces is a well-known infeasible problem), then we are looking at a profoundly untrustworthy framework.

So beware, all of you rabid BlockChain investors!  If you are betting big on smart contracts, you owe it to yourselves to figure out a way to reduce the statements those contracts make to a stable, computationally feasible form.  You know what they say: those who fail to learn from the past are doomed to repeat it.  If you don't find a robust and tractable semantics for your technology, then someday, twenty years from you, too will be writing little blog postings about how your work once took a hopelessly wrong turn...  and that Professor Birman's sad story of his unfortunate foray into the theory of branching future executions should have warned you!

Magical Thinking and the Logical Foundations of BlockChains

During the past few years, I've been exposed to an unrelenting drumbeat for BlockChains.  The level of enthusiasm for this model, and the commercial mania around it, have all the elements of a "market bubble".  Just yesterday I saw a quote from a BlockChain/CyberCoin billionaire who believes that "BlockChain will replace the Internet."  Really?  But search for that phrase and you'll actually find that this guy is saying something many people believe.  Rational or not, there is a huge community totally convinced that the future will be a giant BlockChain.

The BlockChain buzz was evident at the recent conference I attended, where one speaker told us about a Berkeley spin-off based on BlockChain: Oasis, which just landed $45M in first-round "seed" funding.  Just think about that for a moment: how can such a number be justified?  I'm a skeptic.

Oasis apparently plans to build a secure infrastructure using BlockChain as the storage solution, but entirely secure from the ground up.  Presumably this is one reason Oasis needed so much cash: most companies these days just run on a public cloud like Azure or Amazon (or any of the others).  Building from the ground up will be expensive, but would let Oasis avoid a pitfall other startups share: because its competitors depend on existing datacenters, they are exposed to whatever security flaws those cloud platforms embody.

But can one build a secure data center from the ground up?  Let's focus purely on storage, since this seems to be the essence of the Oasis plan.  Could one build a new kind of secure data center that (only) provides secure storage using BlockChain, built from the ground up?

The first step is to reject the permissionless BlockChain model, which is too weak to guarantee freedom from rollbacks even years after a transaction seemingly commits: permissionless BlockChain systems with anonymous servers are insecure by design.  We want a minimal BlockChain solution, but if you take minimal to mean "anonymous, globally replicated, permissionless", my answer is that "it can't be done: it is impossible to create a trustworthy platform with that mix of properties and technologies."

Fortunately, the permissioned model avoids this risk. Moreover, it seems reasonable to assume that if the goal is to offer a data-center BlockChain product, the data center operator can control which machines can operate the solution.  This moves us from the BitCoin style of anonymous, amorphic, fully decentralized BlockChain to a more standard model of append-only files used by customers like banks.

Next, we should perhaps reject a standard cloud that offers encrypted append-only files. This is an interesting step in the analysis because a block chain really is just a secure append-only file, no matter what anyone might tell you (secured using SHA 256 hashes or similar block hashes, with proof-of-work if the system is permissionless, and then with the signatures entangled to prevent tampering).  Any file system could play that role, if you code the needed logic to generate records formatted this way and with the required chain of attestation.  Amazon and Azure and other cloud companies already offer extremely secure storage layers, including BlockChain services. But as noted, they do depend on other elements of the respective datacenter systems.  So out with the old, and in with the new!

Now, without knowing anything about the proprietary protocols that Oasis is presumably designing,  I can't say anything about how they plan to guarantee correctness.  But I can tell you how I would do it.  I would use a form of Paxos, and because I would want extreme speed, would go with the version of durable Paxos that we implemented in Cornell's Derecho system.  If I were chief architect at Oasis, I might want to build my own software (hence not use Derecho), but I would certainly adopt the Paxos specification, and prove that my software implements it.

Of course being a Derecho zealot, I'm going to make the case that using Derecho might be the smart move, even if you might have preferred to roll your own.

First, I should note that by using Paxos, Derecho is able to leverage decades of work on  proofs of correctness -- Derecho was implemented by fusing a  proved-correct version of Paxos  integrated with a proved-correct version of the virtual synchrony membership management model and a new reliable (but not atomic) multicast layer.  Then all of the data movement steps were mapped to the available storage (SSD or 3-D XPoint) and communications technologies (RDMA or TCP) in an efficient way.  Finally, Derecho uses specialized optimizations for code paths that turn out to be performance-critical.

Next, it is worth noting that Derecho is open source, hence can benefit from community contributions over time, and also that the system is extremely fast -- the fast such system ever created.  Further, it actually achieves minimal bounds for Paxos (Derecho's protocols are "optimal" in a formal sense).  Of course one can talk about smaller constants and so forth, but given the speed of the system, there is an obvious case to be made that the constants aren't showing any sign of being unreasonably large.  So Derecho is a genuinely interesting option!  Heck, maybe my students and I should try and raise $50M or so and jump into the commercial space!  

But now we run into the first of a series of issues: the protocols and proofs we are leveraging were all created in the usual way: on paper, by hand.  The mapping didn't modify the underlying logic, yet it required to adapt them to modern networking is by hand, too, and hence also needed to be proved by hand.  The same can be said about our dozens of optimizations.

Is there really a sensible way to argue that all of these hand-written proofs be accepted as somehow being "more trustworthy" than Amazon AWS or Azure?  After all, those are companies are serious about specifications too, and further, both have invested hundreds of millions of dollars in their testing and Q/A process.  Derecho is remarkably robust, and we would point to all those proofs as part of the reason, but even so, we do find bugs in our logic.

Now, if I had the money, one option might be to harden Derecho.  Aggressive testing, deep quality assurance and better documentation would be a breeze.   Starting with such a strong prototype, we could quickly end up with a professional-quality tool.  In fact I actually hope to do this, in the next year or so, if Derecho users are able to chip in to help with the costs.

But perhaps you still wouldn't be satisfied.  And indeed, today's state of the art goes much further: the very best approach is to only run code extracted from a machine-checked proof.  In effect, we compile the proof into the running system and take the developers entirely off the development path.

This, though, turns out to be infeasible for software as elaborate as Derecho, and would be even harder for whatever Oasis really plans to build.  The issue here is that as of today, the provers can't handle the style of code that we needed to use in order to create Derecho, and any full data-center infrastructure would have 10x more such code, and perhaps far more than just 10x.

Today's best provers actually can handle automated extraction of Paxos code from correctness proofs (this has been done using NuPRL here at Cornell, or IOA and Larch in Nancy Lynch's group at MIT, or IronFleet, using Dafny at Microsoft).  The resulting solutions are very robust in the sense that the logical proof structures that result are rock solid -- for what they cover.  Unfortunately, however, the resulting code is incredibly slow compared to Derecho.  Moreover, infrastructure aspects are much harder to formalize than data replication and consistency, so in some sense, Paxos is the "easy" part of the story.  Can we specify the system, fully?  Is the specification itself bullet-proof?  Bootstrap?  Other management tasks?  These steps are much harder than many people would expect.  They may not even be possible, in some cases!

This same pattern is evident in many projects that have formalized aspects of operating systems or runtime environments.  At MIT, Nick Zeldovich famously proved a very simple file system correct a few years ago.  It ran on Linux, but there is a Linux u-kernel called SEL4 that has been proved correct, and while it doesn't cover all of Linux, SEL4 probably has enough stuff in it to support Nick's provably correct file system.

Then you could perhaps use the proved version of the C compiler to compile the thing (C++ is considered to be too complex for existing provers).  Even better would be to just build the whole thing in a language like RUST or Dafny, where proof is much more central to the coding and compilation model.  With such help, you may actually manage to create a proved solution, for parts of your full system.  

But without exception, you'll end up with slow code compared to the best possible, and will have solved just a portion of the entire datacenter infrastructure.  We are decades from having data-center scale, provably correct , ultra-performant software systems.  Perhaps we'll never get there.

Moreover, even if we did manage to overcome these barriers, we would run into further questions.

One big issue is the hardware.  Think about any hardware component in the entire data center.  The routers.  Printers. Digital telephone systems.  Storage devices.

$45M may seem like a huge amount of money, but in fact it is a tiny drop in the bucket when you consider that companies like Intel spend billions on their VLSI chip fabrication factories.  So there is simply no question that Oasis will end up using components some other company created.

The problem is that these components tend to be software-defined, and this is becoming more and more of a standard story: Almost all hardware components have general-purpose, highly capable processors within them.  An entire separate computer, with its own memory, network interfaces and code.

Indeed, if you needed one CPU and DRAM unit just to operate the hardware, why not include two on the same board, or chip?  Who would notice?  And if you do this, why not drop malicious code into the second unit?  Your printer company may not even realize that it is selling compromised devices: I've heard of network chips that had entire secondary networking infrastructures built in, operated by entire stealth operating systems.  You can monitor your network as closely as you like.  You would never notice the stealth network, and its control logic!

So you can perhaps make the higher layers provably secure, but this issue of trust in the hardware limits the degree that the resulting system could be secure.

If you run a secure solution on compromised hardware, all bets are off.  The situation is a bit better if you trust the hardware: Intel has an approach called SGX that can do a bit better, and perhaps Oasis plans to leverage it, but if so, they will face performance challenges.  Sadly, SGX is quite slow.

But suppose they pull all of this off: a ground-up datacenter solution, minimal trust in the hardware, offering a BlockChain storage layer to customers.  Now we run into a new puzzle: the issue arises of how to draw the boundary between the trusted storage solution and the customer's application.

The problem here has to do with composing a trusted application with a trusted storage layer through some form of less-trusted layer of intermediary logic, like the runtime associated with the programming language.  Modern applications are coded in standard languages like Java, Python, C++, Ruby.  They use databases from big vendors like Oracle, web servers like Apache, and so forth... and each of brings its own millions of lines of logic and its own runtime environment.  Those presumably have flaws, hence an attacker could potentially compromise the application by compromising some element of the compiler or runtime, even if other aspects of the datacenter BlockChain storage solution magically were iron-clad.

And this is why I'm a skeptic: I don't see how such a picture can be secured, not today, and probably not in my lifetime.

I actually do believe in security, but I think that in modern systems, we get much more protection from diversity and multiple layers of monitoring than we do from automated techniques like verification.  We should definitely do verification where we can -- for systems like Derecho, it offers a path that can slash bug rates and greatly improve confidence in the correctness of the system relative to the promises it can legitimately make.  But to me we oversell the power of verification and proofs if we go further and allow people to believe that we have discovered a magic way to carry this idea to the limits and "prove the whole thing", whatever that thing may be.  BlockChains don't change this reality.

The Oasis folks will presumably read this blog, and I should emphasis that it isn't a personal criticism.  I'm a huge fan of the Berkeley security team and have been amazed by their accomplishments.  Amazing work has been done.  But even so, and without being hostile in any way at all, I do think we all share a need to be frank with the public about what technology can, and cannot, accomplish.

BlockChains are being oversold as a trivial way to get perfect security -- not by Oasis, but by the popular technology press, which seems to have a very dim understanding of the concept.  The press seems to think BlockChains are somehow "more" than secure file systems.  Yet if anything, they are "less"!

Perhaps we are seeing a superposition of two elements.  Clearly, we do have a community that was unaware of the concept of a tamper-proof append-only log protected using cryptography.  All sorts of folks who work in government, health care, manufacturing clearly feel that this is a revelation, and offers an answer to all their security worries.  And quite possibly some were actually not aware that we can use file systems in secure ways -- I'm glad they know, now, and if BlockChain helps them conceive of this, I'm all for it.

Then we have hype, driven by cryptocurrency valuations in the stratosphere, a technology press endlessly eager for the next big thing, and investors keen to make a killing.  In this marketplace, I see a lot of value that companies can bring to the table, particularly ones with exciting ideas for packaging this stuff to be useful, and some of this value is very real: HyperLedger and Ethereum and related tools are genuinely powerful.

But just the same, we need to stop claiming that BlockChain is a revolutionary invention.

My worry is that by overselling the same old file systems to a naïve community of infrastructure owners, we may end up with systems that are actually less secure than what they replace.  After all, a platform like Azure is actually remarkably secure today, managed professionally by a company obsessed with security (and nobody is paying me to say this, by the way!), and has such a diversity of technologies deployed that compromising it in a major way would be quite hard.  If some hospital were to abandon that and jump to BlockChain as its file system, the illusion of security may have replaced much stronger real security.  True, today's reality has its limits, but in fact  I would be far more comfortable seeing medical records hosted on Azure or AWS, than abandoning these professional solutions in favor of a storage product that uses BlockChain as a magic wand to solve all problems.

But clearly, the current climate (especially the technology press) is prone to magical thinking, and a bit weak on just what BlockChains are, and how they work, and what their logical foundations turn out to be.  And in light of that, I suppose that the amazingly high first round of Oasis investment makes a kind of sense.  A bubble?  Definitely.  And yet all valuations are measures of market sentiment.  So perhaps not an unreasonable bubble, given the modern business climate and the craze that BlockChain has engendered.

Why we need a "Bell's test" for BlockChains

Last fall, Scott Aaronson visited Cornell and gave a series of talks on quantum computing.  I asked him about quantum-encrypted fiber-optic communication: how can users be sure that the technology actually uses entanglement, and isn't just some form of standard communication link set up to mimic the API to a quantum one?

Background: Quantum cryptographic methods basically mix classic communication with a quantum source of completely secure "noise".  They use a normal PKI for endpoint authentication, but introduce a quantum device that sends entangled photos to the two endpoints.  By measuring some unknown property (usually, polarization), the endpoints extract a genuinely random sequence of 0 and 1 bits that both observe identically (entanglement),  Any intruder who attempts to spy on the system would disrupt the entanglement.  The shared sequence of random bits can then be used as the basis for end-to-end symmetric cryptography.

A vendor offering a product in this space needs to do much more than to provide an optical fiber that carries entangled photons.  One issue is that the endpoints need to synchronize to ensure that they perform the same test on the same photons.  This isn't easy at high data rates.  To work around the limit, you would probably use quantum entanglement to create a symmetric key shared by the endpoints, then employ that symmetric key as input to DES or some other high-speed symmetric cryptographic solution.

But suppose we  don't trust the vendor.  Could the hardware be designed to "cheat"?

Scott's answer:  Thus there are many ways to cheat.   For example, notice that the scheme outlined above starts with a completely unknown property: entangled photos with totally random polarization.  One could instead generate an entangled sequence with known polarization.

The user will have been fooled into using a key that the evil-doer generated (and hence, knows).  The user's secrets will actually be out in the open, for anyone (at least, anyone who knows the sequence) to read.

In fact, why even bother to entangle the photons? Why not just take a laser, polarize the output (again in a known way), and then beam the resulting (non-random, non-entangled) output through a half-silvered mirror, so that both endpoints can see the same signal.  A naïve user would measure polarizations, extract the same sequence from each end, and think that the device was working flawlessly.

Beyond this, one can imagine endpoint hardware that genuinely goes to all the trouble of extracting  random data from quantum-entangled photons, but then ignores the random input and substitutes some form of pre-computed key that the evil-doer computed months ago, and stored in a table for later use.  Here, the buyer can actually go to the trouble of verifying the entanglement, confirm that the device is genuinely intrusion-tolerance, and so forth.   Yet we would have zero security, because the broken endpoint logic ignores the quantum-random input.

Bell's Theorem.  Setting such cases to the side, Scott also pointed out that for the entangled photons on the fiber-optic cable, there actually is a good way to test that the device is working.   He explained that in the lab, physicists test such technologies by running a "Bell's Inequality" experiment.

As you may know, Bell's Theorem was proposed by John Stewart Bell as a way to test one of the theories about quantum entanglement -- some believed at the time that "hidden variables" were at the root of entanglement, and were actively exploring ways that such variables could arise.  Bell showed that true entanglement could be distinguished from a hidden variable system using a series of measurements that would yield different results for the two cases.  Scott's point was that could run a Bell's inequality experiment on the fiber.  It would give unambiguous evidence that the photons emerging from our fiber are genuinely entangled.

But a Bell's test would only cover the technology to the endpoints of the fiber carrying the entangled photons, and we could only run such a test with "unrestricted" access to the medium.  Very few products could possibly be deconstructed in this way.

Bottom line?  Clearly, it is vitally important that quantum encrypted communications technology be from a full-trusted vendor.  A compromised vendor could sell an undetectably flawed technology.

Why is this relevant to BlockChains?  A BlockChain technology is only as secure as the  cryptographic package used in its block-entanglement step.  Suppose, for example, that I created a cryptographic package called SHA 256, but instead of using the actual SHA 256 algorithm, implemented it in some trivial and insecure way.  As long as that package produces an random-looking hash of the input, of the proper length, one that varies for different inputs, you might be fooled.

What's the risk?  Well, if I could trick you into using my product, it would look like a BlockChain and seem secure.  Yet suppose that the chain included block X that has a transaction I find "awkward".  If my fake hashing system lacks a cryptographic property called "strong collision resistance", I could substitute block Y for X, modifying the stable body of the chain, and you wouldn't be able to prove that this tampering had occurred.  Obviously this defeats the whole point.

Now, if you were to check the output against a different, more trusted SHA 256 hash solution the values would differ.  Yet how many people audit their BlockChain products using a technology totally independent of anything the BlockChain vendor provided?  In this example, even using the SHA 256 code provided by your vendor is a mistake: the SHA 256 code is broken.

Moreover, there are other ways that one could potentially trick a user.  A SHA 256 hash computed on just a portion of the transaction record could look completely valid (would be valid, for that portion of the block), and yet would leave room for tampering with any bytes not covered by the hash.  Your audit would thus need to really understand the BlockChain data structure, which isn't as simple as you might expect.  Many BlockChain vendors use fairly complex data structures, and it isn't totally trivial to extract just the chain of blocks and hashes to audit that the hash actually covers the data in the block.  Any vendor-supplied code you use for this step, at all, would expose you to a risk that when you go to audit the chain, the vendor tool covers up any tampering.

My point?  This is a genuine risk.  An immense number of companies are jumping to use BlockChain for diverse mission-critical purposes.  These companies are relying on the guarantee that once the blocks in the chain become stable, nobody could tamper with the record.  Yet what we see here is that a BlockChain is only as good as the vendor and the cryptographic package, and that the chain can only be trusted if you have some way to independently test its integrity.  And you had better really run that test, often.

My advice to anyone working with BlockChain is to hire a trusted independent consultant to build a BlockChain test program that would audit the actual chain daily, using completely independent technology.  If the vendor is using AES 256 for hashing, your auditing company should find a very trustworthy AES 256 and base the audit on that.  If the chain uses some other hashing method, same goes for it -- this can work for any standards.

What if your vendor is offering a non-standard BlockChain that runs super-fast by virtue of using a new but proprietary hashing technology, or a new but non-standard secret data structure?  My advice is simple: if the vendor won't supply you with enough detail to let you audit the chain, don't trust it.

Blockchains and the new mythology

For two years now, the drumbeat of Blockchain technology has gradually dominated one area of systems after another: in the public eye, Blockchains are somehow the universal solution to every problem.  This I find very odd: the core BlockChain concept is technically flawed (I don’t want to repeat prior blogs, so I’ll simply point out that four or five of my older postings were on technical problems with the model).  The model doesn’t even fit many of the imagined uses.  And in actual fact, we see few examples of real uses, other than to support cryptocurrencies that run some risk of evaporating from your wallet.  Yet this dream of using BlockChain technology for everything that really matters has somehow taken hold.

BlockChain has evolved into a mythology.

I remember a talk by Michael Brody, the CTO of Verizon around 1998 (back when it was still part of the GTE empire).  He focused on the psychological wish for magic silver bullets that can slay every technical barrier.  In companies struggling with technology challenges, it can be very appealing to wish for miracles (and all too easy to worry that the other guy will find it first and win market dominance by so doing).  At the time, the silver bullets were client server architectures, CORBA, Paxos.  But the underlying pattern was similar: an overwhelming desire to believe, coupled with eyes closed against the limitations.

We see this now for artificial intelligence, too: how many self-driving cars will have to run down bicyclists and swerve into ongoing traffic before people realize that putting a robot in charge of a car is simply an overreach? The technology isn’t ready yet.

And so too with BlockChain.  Yet when I attend talks on Digital Agriculture, or the future of medicine, or banking, somehow the very term seems to command authority (and to shut down any skepticism the audience might normally have expressed).  In the New York Times on April 3, an article talked about BlockChain in all of these and many other “uses”, quoting one gushing entrepreneur as saying that BlockChain is a revolutionary, disruptive and nearly universal technology for storage, communication, security and safety.  Oh, and he suggests we use it for online voting, to repel those Russian hackers.  Come again?  All this from an append-only log, running on anonymous servers, and prone to rollbacks?

It does seem true that a permissioned BlockChain (one running on specified servers, probably in the machine room of a bank, or sold as a turn-key product by a storage or cloud vendor) would be a great place to log transactions that you want to keep on record indefinitely.  Moreover, a permissioned  Blockchain won’t roll back unexpectedly.  But the expert quoted by the NY Times apparently wants all sorts of digital information logged into indelible records, and seemingly has the permissionless variety of BlockChains in mind (he would never trust any single bank or company to host the chain).

Beyond the privacy issues raised by having your life logged in a globally shared place, we get the oddity of using a type of log that by construction is capable of spontaneously erasing itself.  It could even be erased deliberately by the same Russian hackers out to tamper with the election you are trying to protect!

Setting the technical issues to the side, the psychology of this article speaks to Brody’s old story of using silver bullets to slay dragons.  Technology has become so complex that it certainly can feel like magic, and magical thinking is a natural fit.  Nobody wants their illusions punctured.  No technology is perfect, but even this plays into the story: if you point to a flaw, like the tendency of permissionless Blockchain to roll back, Blockchain fans just assert that version 2.0 will fix that.

The dialog reminds me of science fiction.  We start with a conceit: “dilithium crystals and antimatter  enable faster than light travel” (and every other technical miracle the script writers could dream up).  The physics wouldn’t bear up under close scrutiny, but we don’t look too closely.  And from this starting point, we boldly go where no one has gone before.

But one can easily understand the motivation of a science fiction script writer.   Where I’m left puzzled is with the motivations of all these self-proclaimed experts.  are they deliberately lying?

Quite a few must know better. Yet somehow, this chance to be the expert seems to drive rational computer scientists to make wild claims, while brushing obvious concerns to the side.  While the scam endures, these people are becoming millionaires.

I imagine that it must be fun to be able to sound off at fashionable cocktail parties, too.  “Am I concerned by the opioid crisis?  Well, of course.   But in my view, the entire problem could be solved by using Blockchain to log every transaction involving these habit forming drugs...”

Down the road reality will impose itself.  But I guess that by then, these experts will have long since cashed out, bought Napa vineyards, and moved on to speculate in some other illusory commodity.

The Paradox of Trust in Permissionless BlockChain

A few days ago, I posted on work by my colleagues (Eyal, Sirer, Van Renesse and Gencer), who showed that most BitCoin mining is occurring in a fairly small number of data centers, mostly operating in China.

Why is this even possible?  To appreciate the context, it helps to realize that any BlockChain system that operates anonymously needs a way to protect against DDoS attacks (BlockChain assumes that some percentage of the participating computers are unhelpful and perhaps even malicious in a Byzantine sense, and hence could try to flood the system with nonsense of various kinds).  To this end, they employ two mechanisms: (1) A proof-of-work requirement, so that it takes some heavy computing to generate new blocks; (2) A cryptocurrency reward for solving those puzzles and placing new blocks at the end of the chain.  Basically, even though you don't trust some of the computers, you block bad behavior and incent good behavior. 

This is how new cryptocoins arise.  Unlike fiat currency, which is simply printed by the United States Treasury, or the Chinese Treasury, or the Swiss one, you need to earn your BitCoins or Ether coins, by mining.  While you can also obtain coins in transactions with other participants, for example by selling them chewing gum or some other high-value commodity, those are previously minted ones.

As cryptocurrencies have soared in value, one after another, the potential to become rich by playing a big role in coin mining wasn't lost on the kind of companies in a position to invest in doing that.  In fact it makes sense to jump in early: you mine lots of coins back when the chain had no real value, and later it turns out that you possess a resource valuable beyond all comprehension.

So, if you are the kind of company that builds data centers, data centers specifically for mining cybercurrency makes sense.  It became very appealing to pursue this form of reward by five years ago, and massive data centers emerged.  Gradually, they upped their game, deploying cutting edge hardware to gain a performance edge.  This pushed less-well-equipped miners out: Anyone who knows how to mine faster and cheaper can earn more and more of those precious bits. 

But it turns out that this dynamic favors places like China, which have inexpensive electric power and labor, yet also have the needed high-tech skills to actually create and run such a mining operation.  So (1) the mining quickly concentrates in a few places, and (2) they tend to be in China.  But that one-two story creates a new and unexpected threat.

The risk is that once a majority of BitCoin mining becomes concentrated in the hands of any small number of players, they can use their power to control which transactions are logged and when, or can offer preferred performance to their friends and penalize their enemies, or even force a rollback to really harm someone they dislike.  A rollback is pretty drastic: since the coins actually originate in blocks within the chain, if the block that minted a coin rolls back, that coin evaporates.  Worse, transactions won't automatically be reissued and performed in the new chain: a transaction becomes invalid if it uses even a fractional version of a non-existent coin.  So potentially, some coins evaporate and some transactions evaporate too.  Yet the chewing gum already changed hands, and has been chewed.  Can't roll that back...

The risk is definitely real.  First, the mere possibility of behaving like a cartel in order to extract more profit from the BlockChain is a powerful force in favor of the first players to explore doing so.  Of course, any cartel will quickly turn into a kind of BitCoin mafia, but the members will get very rich in the process.  So it will happen sooner or later, purely due to market forces.

As for making deals to favor some transactions, or trying to extort money in exchange for fair treatment, we are definitely already hearing stories along those lines today.

But the really extreme case hasn't occurred -- yet.  The scenario here starts with a political event, such as a trade war or a confrontation over the ultimate status of some Asian island-state, or even a border dispute.  It causes great tension between China and some other country that uses BitCoin (or some other cybercoin where Chinese data farms are doing much of the heavy lifting).  Then you have to imagine that China is so angry that it steps in, demands national control over the data centers within its own borders, and then sets out to use this control as leverage in their global political ambitions.  This escalates until they just wipe out some huge portion of the chain by aggressively mining to create an even longer portion.  Everyone expects roll-back events with a block or two, but nobody is prepared for roll-backs that might span days, weeks, months... even years.  Could it happen?  Apparently.

So rather than wander into a gloom and doom story again (I did that on a prior posting), I wan to comment on "hoist on one's own petard" aspect of this.  Is BitCoin in fact doomed, in some way, by the very principle of democratization and global fairness that Satoshi set out to achieve?

How did I ever come up with that idea?  Well, you need to think about Satoshi Nakamoto's missive, the document that inspired the entire endeavor.  The story was basically one of eliminating the monopoly power that governments hold over fiat currency in favor of a global and decentralized model: everyone would mine coins, and everyone would share the benefit.

But with this flipped situation where the economic incentives favor centralization, we can now see something that wasn't evident back then: a paradoxical outcome in which it turns out that the seeds of monopoly were actually hidden in the original premise!  We need a game theoretic analysis!  But it seems to me that BitCoin is turning out to be a game with an unexpected Nash Equilibrium: a state in which there is a small monopoly in total control of the BlockChain.

It all centers on a mistaken notion of trust.  In Satoshi's writings, the concept of trust is central.  Satoshi does not trust centralized government, leading him to invent a new ecosystem in which nobody needs to trust any at all.  Everyone runs the BlockChain software, nobody cares where it runs, or trusts the participants, yet the chain grows, and everyone can use it to buy and sell the flavor of bubblegum that they prefer, in perfect anonymity.   In concept, at least, there is no advantage to be had by modifying the protocol or attacking the chain.

But we can see how this neglected one aspect of trust: trust that the BlockChain software is run by large numbers of autonomous players, and that mining doesn't become concentrated in any pool that gets even close to controlling one third or more of the mining power.  The point about one third, by the way, arises from a different way of manipulating the system: in a previous result, the same authors managed to show that a cartel with one-third of the mining power can earn all the income by sharing certain kinds of information only within cartel participants (this is a slight violation of the protocol, but one you could implement with just a few lines of changes to the BitCoin code base).

Nobody would know that the cartel had pulled the trick off.  It would just start to win every single competition to place the next block.  By shifting through lots of aliases, it would be quite hard to prove that they were up to this.

Conclusion: It appears that the economics of cybercoin mining creates an unexpected pressure to concentrate mining power in a small number of players.  This in turn gives those players an incentive to form a cartel, in which case they can earn all the money, decide which transactions to clear and which to ignore.  And if they get really, really angry, they can collapse the entire BlockChain.

Would I worry about this, if I was invested in BitCoin?  Actually, I think the risk seems real and worrying enough to genuinely think about.  It could happen.  And if the chain were to collapse, all of that wealth would evaporate like so much pixie dust.

So why aren't the big players in a panic?  My guess is that they have profited so greatly from playing in the current high-risk ecosystem that BitCoin represents that they became inured to risk along the way.  BitCoin sometimes doubles in price (or loses 80% of its value) in minutes.  Maybe this blog posting will send it on some new gyration.  And these investors have learned that like a really great roller coaster, each stomach-wrenching downslope is followed by a giddy climb to previously unimagined heights.  They get hooked on it... and are unable to appreciate that giving some cartel power to collapse the whole thing is perhaps unwise -- like simply assuming that the rollercoaster framework is sound, while entrusting it to an unknown construction crew from out of town.  Did they loosen the bolts last night,  secretly?  You might not find out until the thing literally collapses underneath you, and by then it would be far too late to reconsider your willingness to take another ride!

So here's a shout-out to my friends who work on game theory.  Are BlockChain systems doomed to form cartel structures?  Or could one imagine a version of BlockChain in which membership is anonymous (permissionless), and yet cartels cannot arise?

One last observation.  Right now, nobody thinks of systems like Microsoft/VMWare/Facebook's Corfu logs as the basis for a BlockChain, primarily because they don't use proof of work, because they don't operate in a permissionless model.  Same for Derecho, the system we've been working on at Cornell: Derecho is a fast version of Paxos, but you wouldn't normally store HyperLedger records into it.

But why not?  Why shouldn't we create permissioned ledgers this way?  We would eliminate that rate limitation, which drives everyone crazy right now, and in fact would gain other advantages too: auditability, elimination of proof-of-work computations.  This would be good, right?  Rather than mint coins in exchange for mining, we could just stick with traditional fiat currency, but allow these ledgered transactions to talk about it: "For the sum of $1, Ken agrees to sell five packs of BubbleYum Chewing Gum to Ittay."    Maybe later we find a follow-on transaction: "The third party escrow agent confirms delivery of the gum", and after that, confirmation that the $1 changed hands.

Then we could focus on ways to run transactions that span multiple BlockChains.  Maurice Herlihy just published a paper on a protocol for doing that sort of transaction.  Even more interesting than the solution is the specification: if I run a private chain at bank branch A, and it interacts with your branch B of some other bank, how do I know that the transaction was safe, and valid?  And can we avoid creating an audit dependency between A's private log, and B's private log?  Would there be a role for an organization like SWIFT, to assist in clearing at the end of the working day?

You can see where this all leads... my colleagues in game theory would oblige me by proving that permissionless BlockChain is doomed to create high-risk monopolies that concentrate all the control in the hands of a few small cartel-like groups.  Bad news.  To save themselves from a total coin-ocalypse, everyone switches to permissioned models, and we work out the details for using those to host cryptocurrency.  My research group and I enhance Derecho until it stands alone as the ultimate solution for solving that problem (perhaps you didn't know this, but Derecho is provably optimal for Paxos, and in fact is demonstrably way faster than any previous Paxos system, too).  My students then go out and commercialize this...   I like this story!

So what about it, game theory people?  Is this BitCoin vulnerability inevitable in permissionless BlockChains?

Blockchains immune to cartels.

In my last blog posting, I reported on work by my colleagues that showed how concentrated Blockchain mining has become, with twenty data centers (mostly in China) doing the majority of the mining.  We saw that this makes it easy for China to attack the Blockchain in various ways.

A natural question is to ask why exactly this issue arises, and what can be done about it.

For Bitcoin and other permissionless Blockchain Systems, the central issue is “proof of work,” and it arises because of two factors: the rewards for mining, and worries about a form of DDoS vulnerability.  In Bitcoin, the miner that creates a block of transactions and is able to place it in the Blockchain by computing a nonce value that will result in a SHA5 hash with the requisite number of zeros is paid for the effort: the block will “issue” a new coin to the miner, and the value of the coin combines a fee on the transactions it contains, plus a small additional reward for placing the block itself.  

Because the cryptographic system used is not known to offer any computational shortcuts, computing the nonce is a brute force task: a miner computes a next block and then tests various nonce values until it finds one that results in a hash with the desired characteristic.  There is no way to avoid the brute force task of sifting through nonce values, at present.  This Bitcoin rewards computational power.  The more powerful your mining center, in terms of hashes it can compute per second, the more money (coins) you earn.

Could we imagine a Bitcoin or Blockchain protocol wired to locality, so that the right to create blocks could be fairly shared between miners in the USA, Canada, France, Russia, China, India, Uzbekistan,  etc?  Not really.  Doing this would just incent global mining consortia that would run proxy computers in those countries, but would outsource the actual nonce computation back to the farms in China, allowing the existing mining cartel to preserve its monopoly on the income, and its power to attack the global Blockchain.

So why, exactly, did we need proof of work?  The DDoS worry stems directly from the anonymity of Bitcoin: any computer that wishes to join the Bitcoin pool can do so just by downloading the proper software and attaching itself to the network, using a virtual “name” that isn’t tied to any physical computer address in a direct way.  Thus one real computer could fork off hundreds of clones, and they could generate huge rates of transactions by just selling bubblegum to one-another at preposterously high rates.  Bitcoin is designed to discourage such behavior: first, the fees paid to log transactions make it expensive to generate huge numbers of them.  And second, the intent of the hashing thing is to spread the odds of creating the next block broadly, “fairly.”  Here we can see a flaw in the design: fairness breaks down, and once a cartel gains control of the show, most other properties of anonymity and non-fiat currency characteristics are out the window too.

Better, it seems to me, would be a permissioned model in which non-anonymized players (call them “banks”) maintain local ledgers.  We would have a local ledger of transactions at Bank of America, another local one at the Bank of Russia, etc.  Individual branches could have their own local sub-ledgers.  I’m not proposing that these logs replicate all the transactions in the world.  Just local logs,  using hyperledger or a similar technology to record banking and business contracts and e-coin transactions.

Such a local ledger won’t need to be permissionless because a branch of the Alternatives Federal Credit Union knows perfectly well which machines play server roles.  So we can use membership management protocols, and in fact are looking at a problem like the one solved by Corfu, or by Derecho in its persistent mode.  Perhaps it would be wise to harden the solution against Byzantine attacks, also a solvable, classic problem.   

Then we could create a protocol for banks to talk to one another, more or less SWIFT (the widely used standard interbank protocol) but enhanced to deal with inter-bank transfers.  Here, I think we see an interesting distributed transaction problem: how would one specify the required properties?  For example, if I ask Alternatives Federal Credit Union to purchase euros for me, then wire them to my sister-in-law in Belgium to pay my share of our house for the summer vacation rental, the money moves through a chain of perhaps six banks.  Each wants to know that after a clearing delay (as short as possible: zero would be best) its own local log is finalized.  We don’t want a lingering dependency period during which the ledger for the international branch of Chase Bank somehow can’t be audited for correctness without also auditing the one at Alternatives FCU in Ithaca.

But this seems solvable to me.  We could then eliminate proof of work (banks do charge fees for transactions, so those will avoid DDoS scenarios, and there is no anonymity, so the fairness aspect is moot).  We would simply have found a clean way to introduce Blockchain technology into standard banking, with or without cryptocurrency (honestly, I’m not s big believer in the stuff, but one can have Blockchain solutions for any kind of contract, and if you want to treat large numbers as commodities with value, who am I to stop you?  In fact the earliest banks operated precisely that way: “... just present this unforgeable document to my brother in Milan, and he will give you two gold florins”).  It would work just as well for crates of oranges, or contracts describing mortgage-backed securities.

Bottom line: my colleagues have shown that in effect, Bitcoin is currently a cartel, ultimately controlled by China. All that stuff about anonymity and fairness?  Basically, a hoax, except that the end users do seem to be anonymous, hence Bitcoin remains very helpful for drug transactions, prostitution, money laundering, international weapons sales.  Stuff like that, where real cash and credit is “awkward”.   Tax evasion.  Yet we can have Blockchain solutions without anonymity, and doing so allows high transaction rates, eliminates the monopoly data mining element, gets rid of the wasted power and cooling for all that SHA5 hashing, and if you want e-coins,  you can have them too.  

So it all comes down to the permissionless model, which in turn is ultimately a political statement by Satoshi Nakamoto, stemming from his distrust of fiat currencies and his views about global political structures.  He favors anonymity as a kind of enabler for anarchy, and envisioned a new global political system fueled by a fiat-free currency.  Yet his vision stumbles, we now see, on it’s substitution of computing power for political power, leaving China in control.  I myself would prefer to just have a system that really works (I pay my taxes, and don’t engage in money laundering or Bitcoin barter for illicit stuff).  If Bitcoin and anonymous Blockchain Systems are at risk of foreign domination and attack, I say: enough with this pretense of anonymity!  Let’s just go with Blockchains!