Paul Madsen
https://www.hedera.com/blog/abft-for-correctness-and-liveness

In a Distributed Ledger Know-how (DLT), the consensus algorithm is the tactic by which the nodes (computer systems) are capable of come to an settlement (consensus) on the order of a set of transactions, and probably different info comparable to a timestamp for every transaction. For some consensus algorithms, it’s attainable to show that they’re Asynchronous Byzantine Fault Tolerant (ABFT).

For instance, the hashgraph consensus algorithm has a proof that it’s ABFT. However what does that imply, and what are the sensible implications? This weblog will discover what an ABFT proof can assure concerning the correctness, finality, and liveness of a consensus algorithm.

Correctness refers back to the skill of a community of nodes to forestall forks growing, the place completely different nodes disagree on the worth for which consensus is sought. Correctness is typically known as security.

Finality refers to a mannequin of consensus during which, as soon as a node determines a price for which consensus is sought, there isn’t any probability the node will subsequently reevaluate that call.

Liveness refers back to the skill of a community of nodes working a consensus algorithm having the ability to proceed in direction of establishing consensus for transactions, that’s the algorithm’s skill to proceed.

Correctness and liveness aren’t separable — it’s trivial to ensure correctness if liveness will not be a requirement, and trivial to progress in direction of consensus if correctness is sacrificed.

A consensus algorithm will typically make some kind of ensures over correctness, finality, and security if sure situations are true. Typically, the stronger the ensures, and the less and fewer restrictive the situations, the safer the algorithm. A consensus algorithm might have a mathematical proof that makes these situations clear, and demonstrates how the ensures emerge.

If a consensus algorithm has an ABFT proof, then there’ll exist a mathematical proof that if sure situations are true, then sure outcomes for correctness, finality, and liveness are assured.

The next is a method of writing the situations and outcomes for a typical ABFT proof:

ABFT Situations

  1. Greater than 2/Three of the nodes are trustworthy (non-Byzantine and non-faulty).
  2. It’s at all times true that any pair of trustworthy nodes will finally sync once more.
  3. An attacker could cause non-honest nodes to violate the protocol in arbitrary methods.
  4. An attacker can manipulate the web in arbitrary methods.

ABFT Outcomes

  1. Each trustworthy node will finally attain a consensus worth on each transaction and that worth won’t change.
  2. Each trustworthy node reaches the identical consensus worth on every transaction.

There are different types of ABFT situations, comparable to utilizing stake, and requiring that greater than 2/Three of the stake be owned by trustworthy nodes. However for simplicity, we are going to solely think about this type of ABFT right here.

Situation 1 requires that greater than 2/Three of the nodes are non-Byzantine, which suggests they comply with the protocol and don’t act maliciously. It additionally requires that they’re non-faulty, which suggests a node can crash and be offline for some time, but it surely should finally come again on-line and sync with the opposite nodes. An trustworthy node can’t crash and keep offline ceaselessly.

Situation 2 requires that any two trustworthy nodes will finally sync. After which they’ll finally sync once more. And so forth ceaselessly.

Situations Three and four merely say that an attacker might be highly effective sufficient to utterly management nodes and the web itself, so long as the primary two Situations nonetheless maintain.

Proofs of this type additionally assume that safe cryptography exists. In different phrases, the attacker can’t break the hash algorithm or the digital signature algorithm.

End result 1 is a assure of finality — there’s a second in time when every node is aware of the consensus worth with certainty, and won’t thereafter rethink that worth. It’s vital to notice that End result 1 doesn’t stipulate a specific timeframe for trustworthy nodes to find out a consensus worth — it says solely that trustworthy nodes will finally achieve this.

End result 2 is a assure of correctness — each node will attain the identical conclusion.

The ensures of outcomes 1 and a couple of solely apply if the situations are met. In fact, if all the nodes are malicious, then they’ll do something. However that may violate Situation 1, so the outcomes would not be assured. Equally, if all nodes are unable to speak with one another, then they gained’t have the ability to come to consensus on something. However that may violate Situation 2. So, so long as the Situations are met, the Outcomes are assured, which give sturdy outcomes for correctness and finality.

An ABFT proof makes completely different ensures about liveness than the ensures it makes for correctness or finality.

There are some broad ensures that it makes about liveness, and different ensures that it does not make about liveness. It’s helpful to undergo quite a lot of lessons of liveness assaults, and see that are dominated out and which aren’t.

A liveness assault is an try to forestall trustworthy nodes from reaching consensus.

On the whole, a liveness assault will consist of 1 (or a mix) of the next mechanisms:

  • The attacker is a node, and by refusing to take part in consensus, or by sending messages that break the foundations of the protocol, prevents different nodes from reaching consensus.
  • The attacker prevents trustworthy nodes from collaborating in consensus. This might take the type of a Denial of Service towards a number of trustworthy nodes that consumes the computing sources that may in any other case be used for consensus, or in any other case corrupting the trustworthy node’s laptop such that it could actually’t take part in consensus.
  • The attacker prevents, or slows, the transmission of consensus messages between trustworthy nodes as these messages journey over the community.

One method to cause concerning the liveness ensures an ABFT proof will or won’t make is to think about an attacker making a declare about their skill to forestall liveness and to find out if that declare is legitimate or not.

We’ll see that an ABFT proof will permit us to refute some claims about liveness assaults, however not others.

Every claimed assault will probably be labelled as both FALSE or TRUE.

Assault A — Byzantine nodes — FALSE CLAIM

The attacker makes the next declare:

I management malicious nodes which are lower than 1/Three of all of the nodes, and might direct these nodes to forestall the opposite trustworthy nodes from progressing in direction of consensus, both by having my nodes refusing to speak or in any other case breaking the foundations of the protocol. I can freeze the community for so long as the assault continues.

If this declare had been true and the assault had been attainable, it will imply that an attacker might freeze the community’s progress in direction of consensus for so long as the assault continues, so the community wouldn’t be dwell throughout that point. And the assault might proceed ceaselessly, and so freeze it ceaselessly, and forestall it from ever coming to consensus.

However the assault is unimaginable if there may be an ABFT proof. As a result of the ABFT proof says that it will come to consensus finally. The main points of the assault don’t matter. It doesn’t matter how the malicious nodes are violating the protocol. Regardless of how intelligent they’re, the assault will fail and so the declare is fake. The ABFT proof ensures that.

The assault doesn’t cease the trustworthy nodes from syncing so Situation 2 is true.

Moreover, as a result of lower than 1/Three nodes are Byzantine, Situation 1 is true as properly.

The ABFT proof then ensures End result 1, which ensures that each one trustworthy nodes will attain consensus on each transaction.

However the attacker was claiming that they might stop the above, that’s that, if the assault continued ceaselessly, the community can be frozen forever.

Consequently the declare is refuted by the ABFT proof.

Assault B — DDoS towards single node — FALSE CLAIM

The attacker makes the next declare:

I can launch a DDoS assault to close down a single trustworthy node at a time. Whereas a node is being DDoSed, no different nodes can sync with it. I additionally management malicious nodes (lower than 1/3), which know what’s going on, and might help me direct the assault to repeatedly change which node is being DDoSed. I can freeze the community for so long as the assault continues.

This can be a Distributed Denial of Service (DDoS) assault. The attacker has compromised many computer systems on the web, and might use them to flood a single laptop with so many packets that it shuts down for so long as the assault continues. It doesn’t matter how intelligent the attacker is when selecting the DDoS goal. It doesn’t matter that the attacker has a malicious node as a spy to assist select that focus on.

The assault remains to be unimaginable. So long as each pair of trustworthy nodes finally syncs, and greater than 2/Three of the nodes are trustworthy nodes, then it isn’t attainable for an attacker to freeze the community for so long as the assault continues. As a result of if it had been continued ceaselessly, all 4 Situations can be true, however the Outcomes wouldn’t be true. That’s dominated out by the ABFT proof. So this type of liveness assault is asserted unimaginable by the ABFT proof and the declare have to be false.

That is notably fascinating, as a result of the ABFT proof ensures resilience to a Comply with The Chief assault during which the attacker performs the above DDoS assault towards completely different nodes in sequence.

Some consensus algorithms have a ‘chief’, which is one node that’s handled in another way with respect to contribution to consensus from the opposite nodes — usually for some time period. The protocol may need the nodes take turns being chief. Or it would permit one node be the chief till it crashes, then one other node is elected to change into the brand new chief. It’s attainable that some protocols utilizing leaders can be susceptible to a liveness assault the place the chief is DDoSed, and as quickly as a brand new node turns into the chief, the DDoS assault switches to attacking the brand new chief. That may be a Comply with The Chief assault. For leader-based protocols during which the chief might be predicted, a Comply with The Chief assault might freeze all the community for so long as the assault continues, whereas solely DDoSing a single laptop at a time, and with solely a single malicious node appearing as a spy.

It’s even attainable {that a} protocol susceptible to such a Comply with the Chief assault might have a mathematical proof that it’s BFT. However it could actually’t have a proof that it’s ABFT as a result of an ABFT proof would assure that it’s secure from that assault. That is one vital means during which ABFT is stronger than simply BFT. A protocol with a BFT proof has assured correctness, but when the proof might be upgraded to ABFT, then the correctness assure might be expanded to incorporate some liveness ensures, as properly.

Assault C — Dynamic Partitioning — FALSE CLAIM

The attacker makes the next declare:

I can partition the community, the place some nodes can’t sync with different nodes. Sadly, I’m compelled to continually change the partitioning, in order that any two trustworthy nodes are often in the identical partition and sync with one another. I’ve a malicious node to behave as a spy and inform me what’s going on. I can freeze the community so long as the assault continues.

Once more, this assault will fail if there may be an ABFT proof.

At a given second in time, the partition will divide the nodes — probably into two equal halves such that neither half has the requisite 2/Three trustworthy nodes — despite the fact that there are that many trustworthy nodes as an entire.

However, as soon as the partition adjustments, then the combo of nodes between the 2 halves may also change. Two nodes that had been beforehand unable to sync will now have the opportunity to take action.

Any two trustworthy nodes will finally have the ability to sync so Situation 2 is happy.

If the assault had been continued ceaselessly, then all the Situations can be happy, and so the ABFT proof ensures End result 1 — which refutes the declare.

Assault D — Static partitioning — TRUE CLAIM

The attacker makes the next declare:

I can partition the community such that 1/Three of the nodes can’t sync with the opposite 2/3. I can freeze the community so long as the assault continues.

That is an assault on liveness that may succeed, even when there may be an ABFT proof.

If the partition doesn’t change, then there at all times be some trustworthy nodes which are unable to sync with another nodes throughout the partition. If the assault had been to proceed ceaselessly, then Situation 2, that any two trustworthy nodes would finally have the ability to sync, can be violated.

Consequently, the ABFT Proof can’t assure End result 1 and liveness might be compromised by this assault.

In truth, there’s a simple arithmetic proof that reveals no consensus algorithm might be safe within the case the place virtually 1/Three of the nodes are malicious and an attacker can partition the community. In such a case, you both need to sacrifice correctness or liveness. You’ll be able to’t have each. In an ABFT algorithm, correctness will probably be chosen and liveness sacrificed. The community will probably be frozen till the partition is healed, at which level it’s going to begin reaching consensus on new transactions once more.

There are a lot of comparable assaults that may also achieve success on liveness. Equivalent to:

Assault E — Broad DDoS — TRUE CLAIM

The attacker makes the next declare:

I can DoS 1/Three of the nodes and maintain then offline in the course of the assault. I can freeze the community so long as the assault continues.

This assault on liveness additionally succeeds, for a similar cause as above.

Assault F — Malware — TRUE CLAIM

The attacker makes the next declare:

I do know of bugs in Linux, Home windows, and MacOS that permit me to close down that laptop, and each node runs on a kind of working techniques, so I can shut down all of the nodes. I can freeze the community so long as the assault continues.

Once more, this succeeds for a similar cause as above, even when there may be an ABFT proof. And it is likely to be higher to say it this manner:

This liveness Assault F succeeds as a result of it isn’t an assault on the consensus algorithm, and the ABFT proof was solely concerning the resilience of the consensus algorithm.

Assault G — Corrupted node code — TRUE CLAIM

The attacker makes the next declare:

I do know of a bug within the code the nodes run, and management a malicious node that may ship a particular message to any trustworthy node that triggers the bug and crashes the machine. And I can proceed to use extra such bugs because the software program is patched. I can freeze the community so long as the assault continues.

In fact, this additionally succeeds — AFBT proof however — as a result of it has nothing to do with the consensus algorithm.

One of the best answer in the long term is to mathematically show that the code is appropriate, with a pc checking the mathematics proof. That is known as formal strategies. Step one is to formally outline the algorithm itself and have a pc verify that it’s really ABFT. This was achieved for hashgraph in Coq. The following step is to develop it in order that the pc checks a proof that the implementation code matches the definition. Or have a pc write the implementation code straight from the formal definition (proof by building). Both means, that’s how formal strategies can guarantee appropriate software program. This may be prolonged to proving the compiler is appropriate, the working system is appropriate, and the CPU is appropriate. Analysis on formal strategies is ongoing in any respect these layers of the stack. However it’s not but in widespread use.

Assault H — Firewall — TRUE CLAIM

The attacker makes the next declare:

I management the web and might delete each different bit passing by means of every router on the web. I can freeze the community so long as the assault continues.

On this case, every pair of trustworthy nodes nonetheless manages to ship an infinite variety of bits to one another. But when they’re utilizing TCP/IP, it could actually’t deal with the lack of 50% of the bits in each packet, and to allow them to by no means sync. Once more, this assault on liveness succeeds, regardless of the ABFT proof, as a result of Situation 2 fails.

Liveness might be regained by switching to an web protocol that makes use of error correcting codes able to dealing with the 50% bit loss. However once more, it’s best described as an assault on one thing aside from the consensus algorithm itself, so the ABFT proof gives no ensures on liveness right here.

For a consensus algorithm, an ABFT proof makes quite a lot of sturdy ensures about correctness, finality, and liveness. Every assure is proscribed in some methods, however nonetheless broad in different methods.

An ABFT proof makes some broad ensures about liveness — it guidelines out quite a lot of liveness assaults that might succeed towards some protocols which are solely BFT (not ABFT). However there are limits on how a lot ABFT can say about liveness: it doesn’t assist if 1/Three of the nodes are DDoSed or partitioned off. And it doesn’t assist with assaults that stop all of the trustworthy nodes from syncing, or that in some way shut down all these nodes. However for assaults on the consensus algorithm itself, the ABFT proof gives helpful ensures associated to liveness.




Learn the unique article right here