Topics

Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies

Dave Hudson
 

From: <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...>
Reply-To: "corda-dev@groups.io" <corda-dev@groups.io>
Date: Friday, 18 May 2018 at 18:01
To: "corda-dev@groups.io" <corda-dev@groups.io>
Subject: [corda-dev] Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies

 

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).

 

Virtuous is an amusing choice of term.

 

As a protocol designer, knowing that a notary will resolve potentially conflicting transactions makes it possible to imagine substantially more interesting solutions to problems (and this was a design consideration when we came up with some of the netting solutions last year).

 

I also tend to come back to an observation that most of the “byzantine” behaviour I’ve ever seen in distributed systems has resulted from implementation mistakes in code – we should think careless rather than malicious. I’ve certainly seen this result in back-to-back conflicting messages being issued by system, and in this case we’re reliant on the notary to prevent harm, and to signal back the problem.

 

 

Regards,

Dave

 

www.r3.com/email-disclaimer

Thomas Schroeter
 

Increased double spend rates are not a problem anymore (bug fixed, the “consecutive counter” of conflict sets wasn’t updated in the simulation). I’ll check the code into experimental.

 

From: <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...>
Reply-To: "corda-dev@groups.io" <corda-dev@groups.io>
Date: Wednesday, 23 May 2018 at 11:08
To: "corda-dev@groups.io" <corda-dev@groups.io>
Subject: Re: [corda-dev] Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies

 

Thanks Thomas, that’s very interesting. Can you check the code into experimental please, so we have it all together.

 

·         With increased double spend rate in the simulation, the performance drops. Perhaps because the implementation is missing “no-op transactions” that would support the acceptance of virtuous transactions, or another implementation problem or bug. I’ll investigate more.

Can you characterise this performance drop further? How quickly do double spends resolve if they’re far apart in time?

www.r3.com/email-disclaimer

Mike Hearn
 

Thanks Thomas, that’s very interesting. Can you check the code into experimental please, so we have it all together.

 

·         With increased double spend rate in the simulation, the performance drops. Perhaps because the implementation is missing “no-op transactions” that would support the acceptance of virtuous transactions, or another implementation problem or bug. I’ll investigate more.

Can you characterise this performance drop further? How quickly do double spends resolve if they’re far apart in time?

_._,_._,_

www.r3.com/email-disclaimer

Thomas Schroeter
 

I’ve put together a simulation of the protocol. Here’s what I’ve learned from the implementer’s perspective. I focussed mainly on measuring how long it takes for a transaction to get accepted and the ratio of accepted transactions to total number of transactions in the DAG. I’ve added a check to ensure that the same single transaction of each conflict set gets accepted by all nodes of the cluster.

 

  • Parent selection is crucial to shape the DAG. Small tweaks to the parent selection algorithm result in bad shapes, e.g. a linear chain or too much branching. Both lead to bad performance.
  • With increased double spend rate in the simulation, the performance drops. Perhaps because the implementation is missing “no-op transactions” that would support the acceptance of virtuous transactions, or another implementation problem or bug. I’ll investigate more.

Transactions that don’t get accepted in time should be re-submitted with different parents, a feature that I’ve not implemented yet.

https://github.com/thschroeter/avalanche

Have a good day!

Thomas

 

From: <corda-dev@groups.io> on behalf of "Mike Hearn via Groups.Io" <mike@...>
Reply-To: "corda-dev@groups.io" <corda-dev@groups.io>
Date: Friday, 18 May 2018 at 18:01
To: "corda-dev@groups.io" <corda-dev@groups.io>
Subject: [corda-dev] Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies

 

https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV

 

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!

 

thanks,

-mike

 

 

 

www.r3.com/email-disclaimer

www.r3.com/email-disclaimer

Mike Hearn
 

https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV

 

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!

 

thanks,

-mike

 

 

 

www.r3.com/email-disclaimer