Todd pointed out this paper on a new BFT protocol called Avalanche, designed for UTXO based ledger systems like Bitcoin and Corda. I figured I’d enjoy a relaxing end to the week by reading it.
Sybil attacks. The paper is somewhat contradictory on the topic of Sybil attacks. It defines the BFT consensus problem as a majority of nodes coming into agreement but ignores the problem of how to stop adversaries overwhelming the network with nodes that have the same owner. In fact the paper says at the start it doesn’t rely on a PKI, but I don’t understand that assertion because I can’t see how the algorithm works without one. The closest it gets is delegating to another paper I haven’t read yet called Fireflies in a kind of throwaway statement. I suspect this makes it useless as a competitor to Bitcoin, which is clearly where they want to go. However Corda does use a PKI and has the notion of a “doorman” which is tasked with blocking Sybil attacks. If you make it hard to create Sybil nodes, and Corda does, the algorithm might be very useful.
Performance. Can do >1000 tps with thousands of nodes. Performance appears to be within the range we currently target for the non-BFT case, so it’s competitive with ordinary CFT consensus. This is excellent and, AFAIK, a new result? Maybe Swirlds can go that fast, I’m not sure.
Assumption that double spends are always malicious. The paper calls non-conflicting transactions “virtuous transactions”, so no messing around there then. This is probably because they can’t provide liveness for conflicting transactions. The problem is there’s quite a few use cases and protocols where double spends can arise naturally, and it’s useful to let the miners/notary members just … pick one. If you can’t do that, then you may have to build a non-BFT locking protocol between participants on top, which is awkward. For instance any state where more than one party could legitimately update it simultaneously, like any state representing a deal either side may unilaterally exit, might experience this issue.
It might not be a problem in the end – the lack of liveness may be a theoretical concern rather than a practical one, especially if both transactions don’t literally appear simultaneously (this is typical in non-malicious double spend scenarios).
Not obviously open source. The paper says it’s implemented in 5000 lines of C++, but it makes no reference to the code being available anywhere for study. 5000 LOC of C++ is not so bad, it’d shrink if written in Kotlin I bet.
Clocks. Corda transactions come with a time window (bitcoin txns do too implicitly via the nLockTime field). It’s not totally clear to me how to integrate it with this framework, though I suspect it is possible.
Secure interlinks. Although it ignores the question of Sybil attacks the protocol does assume secure inter-node communication. Corda can provide this, Avalanche
by itself cannot. Again I do not see why they believe they can run in the absence of a PKI if they assume up front secure P2P communications - that requires key exchange.
Integrated signing. The protocol does not provide finality. Instead it’s probabilistic. The probability of failure can be made very, very low, so low it doesn’t actually matter. However the act of gathering signatures in a multi-sig context like we use would have to be added on top, as acceptance is purely local in the Avalanche protocol. So you’d have to wait until local probability crosses the acceptance threshold, then sign and submit the signature to some per-tx leader (but how to know the leader?). My guess is that we can redefine a tx in Avalanche to include the originator of the request as metadata, and per-node signatures can be submitted to the client until enough to meet the composite key constraints are gathered.
Membership change. The paper explicitly considers evolution of the group over time, which is a nice benefit – most BFT/CFT protocols can’t do this. However it’s not clear to me that this benefit is real due to their vague treatmeant of nodes vs participants, that is, if you don’t try to block Sybil attacks then membership changes are easy, and the reason Corda requires notary change transactions is to stop the composition of the notary cluster drifting over time into a Sybilled configuration. So whilst it’s nice to see this aspect considered during protocol design, without the backing of a hard PKI it’s not clear to me it has any meaning. Ultimately what people want from a BFT algorithm is assurances about individual people or companies and nodes are just a proxy for that. The underlying assumption behind all BFT algorithms is essentially social; you believe that most people are honest most of the time, and malicious behaviour is rare. For that assumption to be implemented algorithmically “nodes” and “people” must be tightly linked. Any protocol that doesn’t do that is inherently incomplete. Corda+Avalanche could provide that assurance, Avalanche on its own probably cannot.
In conclusion this paper may be a useful foundation for a new type of Corda notary. Behaviour in the presence of double spends needs careful examination. The protocol probably doesn’t work outside of something like Corda.
Have a good weekend everyone!