Practical Byzantine Agreement

How might we use a blockchain to solve a real-world Byzantine agreement problem?

The Problem

Let’s start with a simple, practical problem. Say there’s a TCP connection between two machines. During the life of this connection, they agree to do something. Perhaps responsibility for delivery of an email will be transferred. Perhaps one side will debit some funds that the other side will credit.

At some point, the two sides have agreed on what will done, they just have to agree to do it. The situation we need to avoid is where one side believes they agreed to do it and the other side believes they did not complete the agreement process.

Depending on the precise way you state the requirements, a solution can range from difficult to provably impossible. In the provably impossible case, the requirements are such that if both sides are ever to irrevocably commit eventually, one side must irrevocably commit first, and neither side can do so safely unless the other side has already done so.

 

The Solution

In the cases where a solution is possible, the solution is to permit some commonly-viewable event to trigger both sides to agree to perform the action. One general sends a message to the other side, “If you see a red rocket over the hill between us, attack at dawn”. The second general sends a message back, “Got it. Red rocket, attack.” The first general sends a messenger to go to the hill and launch the rocket. If that entire process succeeds, they both attack. If it fails, neither does.

A blockchain can provide an source of commonly-viewable events. One side can tell the other that the event occurs if each side acknowledges on the blockchain by a particular block. The other side accepts by placing its acknowledgement on the blockchain. Each side knows what it should do as soon as it has confirmed that both confirmations will or won’t appear by the specified block.

This has both possible failure modes and limitations. The possible failure modes are mostly limited to the failure of the blockchain to meet the exact requirements it was designed to meet. Transactions not getting into the blockchain don’t cause the algorithm to fail, but the failure of the blockchain to produce blocks does. And any kind of reorganization or double spend type problem causes the algorithm to fail.

The limitation is that there is no particular guarantee of timing. If, for example, one side loses connectivity to the blockchain, it has to preserve its ability to either act or not act potentially indefinitely until it can regain connectivity to the blockchain. For the types of problems I’m talking about here, that’s not a problem. For a real world “attack at dawn” situation, that’s a big problem.

An actual crypto-currency blockchain could be used for this purpose, but it’s unnecessarily heavy and it makes more sense to use systems built for this exact purpose. A purpose-built Byzantine agreement network can make such agreements as cheap as a DNS query. That is, you could get them routinely from a library without even thinking about the costs involved.

TCP does not guarantee that either both sides will see the normal closure of a connection or neither side will. That’s unfortunate because if it did, it would be trivial to develop protocols where nothing actually happens unless the connection normally closes and coordination would be automatic just by that design. This kind of approach could reasonably guarantee such coordination, providing agreement to any protocol built on top of it so long as it follows the “decide what to do, actually do it on normal close” method.

Unless the blockchain (or agreement network) itself fails, you are guaranteed eventual agreement. In non-failure cases, both sides can rapidly agree and move on. In cases where a side fails but the blockchain does not, the non-failing side still rapidly knows what the failing side will eventually do.

 

Payments

This is also sufficient for payment escrow and is the concept behind how ILP’s atomic mode works. The agreement network can be long-standing or ephemeral and need not know the substance of the transaction.

The agreement network can produce a threshold signature confirming that the transaction either will or will not take place. This provides the needed “proof of absence” to demonstrate that something did not occur within the required time frame and ensures that things like clock skew will not result in one side believing the conditions were met and the other side believing they were not.

This eases the painful tradeoff inherent in choosing an escrow lock time. The sender of a payment wants a short lock time because otherwise failure of the connector can hold their funds or the connector can maliciously delay the transaction and execute it only if exchange rate changes favor them. The connector wants a longer lock time because otherwise network or ledger failures can cause them to make their part of the payment but fail to get paid because they cannot complete the mechanics of the protocol before the lock expires.

With a mutually-trusted agreement network, no lock time is needed. A comfortable time to permit all sides to commit can be specified with the agreement network agreeing that either the commitments were or were not made. There is no need for a long lock time to protect the connector. So long as the agreement network reaches an agreement in a reasonable time frame, both sides needs are met. The sender gets a short lock time unless the network fails. The connector is assured that either both sides will execute or neither will.