Avalanche Pre-Consensus: Making Zeroconf Secure

Yesterday Craig Wright published his plan for zeroconf transactions on the Bitcoin SV network. It reads like someone who has only thought about the issue for the first time just recently and ignores the years of research into the topic that has taken place in the Bitcoin space over the last decade. This article will be a partial response to his article but will also outline the direction we are heading to improve zeroconf in Bitcoin Cash.

The Problem

At present zeroconf payments are insecure on Bitcoin, Bitcoin Cash, Bitcoin SV and most other cryptocurrencies. They are insecure because an attacker can successfully get a double spend to confirm a non-trivial percentage of the time, meaning any merchant that accepts zeroconf payments runs an above normal risk of being defrauded.

There are roughly two broad categories of attacks someone can perform to try to double spend:

Fast Respend: This is where an attacker sends a payment to the merchant and at around the same time broadcasts a double spend to a different subset of nodes. This triggers a race to the miners between both transactions. Most likely some miners will see the legitimate payment first and others will see the double spend first making it roughly a 50/50 chance the double spend will get mined. This attack is very easy to do an has a good success rate. Fortunately for us it’s also the easiest to defend against as we can make it possible for the merchant to detect the double spend in a timely manner and decline the payment. More in this later.

Miner Bribe: The miner bribe is much harder to defend against. In this scenario the attacker doesn’t broadcast the double spend immediately, rather he waits for the merchant to accept the zeroconf payment and possibly until he’s out of the store and driving away with the merchandise before creating a transaction paying a much larger miner fee and sending it to the miners.

As an example, the attacker might be buying a $4,000 television and he can create a double spend paying a $2,000 transaction fee. If any miner accepts the double spend, he gets $2,000 and the attacker gets a $2,000 discount on the television. One would hope miners would be honest enough not to accept the bribe, but if even a small percentage of them do, say 10%, then it blows up zeroconf for everyone as an instant payment system where you can commit fraud with a 10% success rate isn’t usable.

Peter Rizun has done empirical research on this and found that attaching a bribe to a double spend on the Bitcoin Cash network does pretty significantly increase the probability that your double spend will get mined. This implies that a percentage of miners on the network today are happy to accept your bribe even though they are obviously aiding in fraud.

Solutions

Fast Respends
As I said above fast respends are the easiest class of attacks to defend against. Much of our focus at the last Bitcoin Cash developer retreat was focused around devising a double spend notification scheme that would relay cryptographic proofs that a double spend has taken place on the network allowing merchants to receive that proof and decline the payment.

The work flow would go like this:

• The merchant’s point of sale terminal serves a BIP70 payment request to the buyer.
• The buyer’s wallet creates a transaction and sends it directly back to the merchant. The merchant’s node inspects the transaction and makes sure it fulfills all the criteria for a zeroconf payment (it is not possible to create double spend proofs for all types of transactions, hence we need to restrict the set of acceptable transactions for zeroconf).
• The merchant broadcasts the transaction to the network.
• The merchant’s wallet then listens on the network for double spend notifications for the next 3–5 seconds.
• If no double spend notification comes off the wire during this period the POS terminal accepts the payment.
• If a double spend notification does come over the wire the POS terminal declines the payment and the cashier asks for another form of payment.
• If the payment was rejected but it still confirms the wallet sends the refund back to the buyer’s refund address provided with the BIP70 payment.

Thus once we’ve implemented double spend proof relaying and merchant software is configured to use it fast respend attacks will not be possible.

Craig Wright’s solution to the fast respend attack is to have the merchants query the mempools of all the miners to see if the tranaction exists in their mempools. While this would likely be just as effective at stopping fast respends as our double spend notification scheme, it assumes extreme miner centralization.

In a healthy functioning, decentralized mining network there would be thousands of miners, not two or three. Not only would it not be possible to query the mempools of thousands of miners in a timely manner, but it would not even be possible to know the IP addresses of the full set of miners. The set of miners is not, and definitely should not be, static. It’s a dynamic open membership system with free entry and exit. Thus even if you did query the mempool of all the miners you think you know of, there could always be others joining who you don’t know of.

Querying the mempools of miners likely makes sense for BSV as Craig Wright has repeatedly said that the goal of BSV is not decentralization. They openly accept and embrace mining centralization as a perfectly normal aspect of the system. For Bitcoin Cash, however, we are looking to go in the opposite direction. I’m personally likely going to work on decentralizing mining pools sometime within the next year or so and we’ve got other people in the space currently researching potential solutions.

Miner Bribe
In his article Wright doesn’t even touch on the subject of miner bribes. Presumably he thinks people can just sue a miner if they accept a bribe. Again, they probably can in BSV where there’s only expected to be a couple miners and where they are pushing this Miner ID™ system, but in decentralized currencies this isn’t a viable option. It’s trivial to upload a block to the network in such a way that it’s difficult to impossible to figure out who originated the block well after the fact.

What would be ideal is some kind of system where blocks that contain obvious double spends get orphaned. In March of this year Calvin Ayre’s Coingeek put out a press release announcing his mining pool is going to begin orphan blocks containing what they consider to be double spends. This announcement was met with ridicule by the technical community.

The reason here should be obvious, having each miner decide what is and is not a double spend on their own is a sure-fire way to cause chain splits and consensus failure.

See also Why orphaning blocks with double-spend transactions is dangerous by ABC developer Jason Cox.

If we are going to be orphaning blocks with double spends, we can’t just have every miner doing their own thing. There needs to be coordination. There needs to be a way for miners to come to a consensus, a pre-consensus, about what is and is not a double spend so that blocks containing double spends can be safely orphaned without risk of a chain split.

Enter Avalanche

Avalanche is a new consensus protocol that was first introduced earlier this year. It provides a novel way for nodes on a network to choose between two conflicting transactions and come to a consensus about which one should be included in the next block.

Using avalanche in Bitcoin Cash for miner coordination provides a very elegant, decentralized coordination mechanism that can potentially prevent miners from accepting double spend bribes and, when combined with double spend notifications, make zeroconf transactions very secure. In what follows I’ll introduce how avalanche works and provide a simple sketch of what avalanche in Bitcoin Cash would look like.

Avalanche Basics
Say we have two conflicting transactions ―transaction A and transaction B. We don’t particularly care which transaction we select (well technically we do but we’ll talk more about this later) but we really care about making sure all the nodes agree that either A is valid or B is valid. We want to avoid a scenario where some nodes think A is valid and others think B is valid.

So how does avalanche do this? Each node that is participating in the consensus process will pick a number of other nodes at random to query and ask them for their preference between A and B. Let’s say for this example each node picks eight random nodes.

If your node starts with an initial preference for transaction A (maybe A was first seen) and the majority of the nodes you query respond and say that they prefer A, then you keep your preference as transaction A. If the majority come back and say they prefer B, then you flip your preference to B. Every node in the network does the same thing.

This constitutes round 1. We are going to perform more rounds following exactly the same process. Each round we pick random nodes and either flip or don’t flip based on what the majority of the other nodes vote for.

Hopefully you can see what is going to happen… it’s going to kick off an avalanche! If the initial preference of the nodes was split 50/50 between A and B (maybe half saw A first and half saw B first) then the result of each of the rounds may be something like this:

Very quickly the system collapses to consensus.

The question you might have is what happens if some of the nodes are malicious? Can they attack this consensus process? The answer is rather interesting. Malicious nodes can try to disrupt the consensus process by not following the protocol and by flipping their votes strategically. However, even if most nodes on the network are malicious, even if 99% are malicious, the honest nodes that are following the protocol will still come to consensus if you are willing to extend the number of rounds.

But therein lies the catch, we don’t have an unlimited number of rounds to wait for consensus to finish. We need this to finish quickly. So in practice we have to put a hard limit on the number of rounds that we perform. This limit means that the network can withstand a certain percentage of malicious nodes and the honest nodes can still come to consensus, but if the percentage of malicious nodes goes above the threshold then they can cause the honest nodes to fall out of consensus with each other. The threshold is a tunable parameter. The more rounds you perform the higher threshold of malicious nodes you can withstand. The fewer rounds you perform the lower threshold you can withstand.

Thus the key to making avalanche work is you need some kind of anti-sybil mechanism that prevents just anyone from spinning up a bunch of nodes participating in the consensus process. Fortunately for us we have a pretty good anti-sybil mechanism in Bitcoin already ― proof-of-work.

Avalanche in Bitcoin Cash
There are probably several ways avalanche could be used for pre-consensus but here I’m going to sketch out a very simple and elegant way of using it.

• Proof-of-work is used as the anti-sybil mechanism. The miners of the last 100 blocks form the consensus group and participate in avalanche. This is a rolling membership group. Each new block a new miner is added to the group and the miner who mined block n-100 gets booted.
• If there are no double spends on the network, then Bitcoin Cash functions identically to how it currently functions. Miners receive transactions into their mempool, select which transactions to put into blocks, and broadcast solved blocks to the network. No avalanche messages are even sent between miners. To an outside observer, you wouldn’t even know avalanche is active.
• When a double spend makes it into the miner’s mempools, it triggers the avalanche process. Miners start sending avalanche queries to each other and perform n number of rounds. Eventually all miners will decide that either transaction A is valid and B is invalid or A is invalid and B is valid.
• If A is determined by avalanche to be valid and B invalid, miners are not required mine transaction A. Just like today, miners can still decide not to mine any given transaction. However, they are not allowed to mine transaction B. If a block is mined containing B it gets orphaned. Blocks that contain previously unannounced double spends must still go through avalanche before being accepted.
• Non-mining nodes don’t need to know anything about avalanche and any full node software that is not used for mining doesn’t need to support it. From the standpoint of non-mining nodes, avalanche is a softfork. The worst case scenario is a miner mines a block containing a transaction that was determined by avalanche to be a double spend. The other miners reject the block and continue building on the previous block, but full nodes don’t know that it has been rejected. Eventually the rest of the miners will extend chain beyond the orphan block and full nodes will experience a one block reorg. In practice we wouldn’t expect this to happen as all miners would use avalanche to avoid getting orphaned and losing money.
• Merchants would still need double spend detection to protect against fast respends but they could rest easy knowing that as long as they wait long enough for the payment to propagate to miner’s mempools (3–5 seconds) without detecting a double spend, that miners will not mine a later double spend even if it pays a bribe.

Is this a silver bullet?
Maybe. If a majority of miners vote for the first seen transaction in each avalanche round, then the minority will be forced to go along with it.

Today if 10% of miners want to accept the bribe, say, it completely blows up zeroconf for everyone. With avalanche if 10% want to accept a bribe they literally can’t as the majority of miners would orphan their blocks.

However, the downside is if the majority of miners want to accept the bribe, then avalanche will select the double spend transaction 100% of the time, also blowing up zeroconf.

How likely are the majority of miners to be dishonest and accept bribes to mine double spends? Seems rather unlikely to me though we can’t know for sure without seeing some empirical data. After all we are asking the people who stand to benefit financially from accepting bribes to vote on if they want to accept one, so at minimum there is a conflict of interest there.

We would have a final recourse if the miners start voting to accept bribes and that’s to add additional stake holders into the avalanche consensus group. In Bitcoin Cash we have other scarce resources besides proof-of-work that we can use for anti-sybil purposes. Utxos and coin age are two examples. And the holders of both of those are not the one’s who would be on the receiving end of the bribes so they would be less likely to vote in favor of accepting them.

Conclusion

A solution to the zeroconf problem has been ten years in the making and we’re finally standing on cusp of making it happen. This is really the byproduct of lots of research, testing, and experimentation by a lot of talented people. It’s a much more rigorous and much more well thought out solution to the problem than Craig Wright’s haphazard “Just query the mempool of miners and have miners independently orphan blocks and then sue people when things go wrong”.

The difference in the quality of research, proposal, and implementation between BCH and BSV really isn’t even comparable. Hopefully we’ll get to start taking these things for a test drive in 2019. Get ready!