3 Ways to Resolve Double Spending Errors

For all its apparent complexity, the Bitcoin Network solves just one problem: double spending. In a nutshell, this problem arises when the same electronic coin is respent.

Bitcoin requires that all transactions, without exception, be included in a shared public transaction log known as a “blockchain.” This mechanism ensures that the party spending the bitcoins really owns them, and also prevents double-counting and other fraud. The blockchain of verified transactions is built up over time as more and more transactions are added to it.

Bitcoin transactions take some time to verify because the process involves intensive number-crunching and complex algorithms that take up a great deal of computing power. It is, therefore, exceedingly difficult to duplicate or falsify the blockchain because of the immense amount of computing power that would be required to do so.

Hackers have tried to get around the Bitcoin verification system by using methods such as out-competing the blockchain security mechanism or using a double-spending technique that involves sending a fraudulent transaction log to a seller and another to the rest of the Bitcoin network.

These ploys have met with only limited success. In fact, most Bitcoin thefts so far have not involved double-counting, but rather have been due to users storing bitcoins without adequate safety measures.

Double Spending
Double spending means spending the same money twice. Double-spending is a potential problem in which the same digital currency can be spent more than once. This is possible because a digital token consists of a digital information can be reproduced relatively easily.

The greatest risk for double-spending comes in the form of a 51% attack, which can occur if a user controls more than 50% of the computing power maintaining the distributed ledgers of a cryptocurrency. If this user controls the blockchain they will be able to process transfer bitcoins to their wallet multiple times by reversing the blockchain ledger as though the initial transactions had never occurred.

This definition was provided by Investopedia.

Here, Rich Apodaca briefly presents Bitcoin’s solution to double spending security together with two others that have emerged since Bitcoin’s introduction. Collectively, these solutions are:

  1. Proof-of-Work (PoW, used by Bitcoin, Bitcoin Cash, and Litecoin);
  2. Proof-of-Stake (PoS, used by Cardano, Stellar, and eventually Ethereum);
  3. Ripple Consensus Process (RCP, used by Ripple).

Why study these solutions if your main interest lies with Bitcoin?

There are three answers. First, doing so affords greater insight into how and why Bitcoin works. Second, it’s not inconceivable that Bitcoin may move toward adopting a variation of something other than proof-of-work some day. Third, if you’re interested in evaluating alternatives to Bitcoin, one of the most important questions you’ll need to answer is how the system prevents double spending.

The Mint

As the Bitcoin white paper points out, double spending can be trivially solved by establishing a Mint. Think of the Mint as a piece of software running on a computer that follows a published protocol. All transactions must be submitted to the Mint.

The Mint appends each valid transaction it receives to a log. This update typically occurs as a batch of transactions called a “block.” When the Mint receives a new transaction, the log is consulted to make sure the same coin isn’t being spent again.

But a Mint suffers from two problems: (1) it creates a central point of failure; and (2) users must trust the Mint to process all transactions without bias.

Follow the Leader

The solutions to double spending I’ve described here attempt to solve the Mint’s problems through redundancy. In a nutshell, the Mint is replaced by a network of independent auditors. Each auditor receives the network’s transactions and so is qualified to detect double spending attempts.

But redundancy comes with a price: the network of auditors must agree among themselves about the order in which transactions appear in their respective logs. This is an aspect of a longstanding computer science problem known as Byzantine fault tolerance.

Fortunately, the problem can be boiled down to one simple goal: randomly choose a single auditor who will update the log and therefore decide on the order of transactions. I’ll call this auditor the Leader.

Double Spending
Proof-of-Work-Puzzle. A message and a nonce (left) are passed to a proof-of-work function (center), yielding a hash value candidate (upper right). Changing the nonce changes the hash value. Providing the nonce needed to generate a hash value within a target range constitutes a solution to the puzzle (bottom right).

In proof-of-work, the Leader is chosen through a cryptographic lottery. The first auditor to generate a block whose hash value falls below a target threshold wins. Hashing requires consumption of energy (“work”), giving the protocol its name. The probability of winning equals the auditor’s fractional hash rate relative to the rest of the network. The winner announces the winning block to the other auditors, who validate it and then move on to the next round.

In the event of a tie (two winning blocks are received at the same time), a receiving auditor declares the block that was seen first as the winner. The outcome of the next round then decides the winner. In particular, the block chosen by the winning auditor as the side to build on becomes the winner from the last round. In the event of another tie, the process continues until one chain or the other pulls ahead in terms of cumulative proof-of-work. In practice, ties are usually resolved within one block.

Auditors consume resources (equipment and energy) as a condition for joining the lottery. These costs must be repaid for the system to remain economically viable. In Bitcoin, Bitcoin Cash, and Litecoin, this compensation takes the form of a subsidy (new money creation) and transaction fees. As a result, double-spending security depends on the net revenue to auditors never falling below zero. This economic requirement dominates how a system using proof-of-work operates.

Proof-of-Stake

A random lottery is also used to select the Leader in proof-of-stake. The key difference is that the chance of winning is proportional to the relative wealth of an auditor compared to the others. An auditor proves ownership of funds by signing a message with the key(s) controlling them and adding this signature to all log updates. A weighted random selection process then chooses the Leader for each round.

Both proof-of-stake and proof-of-work require auditors to post collateral to participate. The main difference is the form this collateral takes. In proof-of-work, collateral consists of hardware and energy consumed on an ongoing basis. Proof-of-stake, in contrast, requires collateral in the form of value held on the network.

Early forms of proof-of-stake were vulnerable to the “nothing at stake” attack. To simplify, a Leader can announce with impunity two sibling blocks claiming the same parent. Proof-of-work punishes this behavior by requiring an auditor to split hash power between branches, thus reducing the chance of winning on any of them. Naive forms of proof-of-stake allow a Leader to produce multiple sibling blocks without penalty, thereby degrading double spend security.

This attack can be mitigated due to the fact that auditors identify themselves by signing all changes made to the log. An auditor that attempts to announce two or more versions of the update can, therefore, be identified. Other auditors can publish a proof to this effect, and subsequently, destroy the auditor’s deposit.

A second problem unique to proof-of-stake is the long-range attack. Here, an auditor obtains keys that previously held funds for the purpose of rewriting the log. Because these keys control no money at the time they’re bought, they are worthless to an owner who decides not to stake. However, in the hands of an attacker obtaining them, they can be used to create an alternative log of sufficient length to become dominant.

The practical difficulty of addressing both attacks explains the shortage of systems using secure proof-of-stake. One of the most important efforts along these lines is Ethereum’s Casper update, which was recently launched on a “testnet.” Another system to watch is Ouroboros, which is under development by the Cardano team.

Although proof-of-stake requires auditors to post collateral, it is not consumed in the same way as proof-of-work. For example, mining equipment depreciates as network difficulty increases. Likewise, electricity is irreversibly consumed during mining. In contrast, collateral is returned intact to honest proof-of-stake auditors.

This key economic difference suggests that proof-of-stake systems may offer comparable security as proof-of-work systems at less overall cost. In other words, auditors should require less compensation in terms of block rewards (money creation) and fees. Proof of such claims requires the long-term deployment of a secure proof-of-stake system.

Ripple Consensus Process

Both proof-of-stake and proof-of-work require some degree of trust in auditors as a collective unit. In proof-of-work, users trust that the majority of hash power is controlled by honest auditors. In proof-of-stake, users trust that the majority of staked funds belong to honest auditors.

The Ripple Consensus Process (RCP) takes this idea as the starting point for a fundamentally different approach in which auditors are explicitly trusted. Although many auditors may be available on the network, a user only trusts some of them while completely ignoring the rest.

In proof-of-work and proof-of-stake, auditors post collateral. The cost of doing so requires compensation that must be paid by the network. In RCP, auditors are explicitly trusted, eliminating the need for them to post collateral while at the same time eliminating the need for compensation.

As a result, RCP auditors lack most of the motivation to become Leader seen in proof-of-work and proof-of-stake systems. With no payout for Leaders, a very different selection protocol becomes possible.

RCP Leader selection begins by each auditor proposing to its trusted peers an update consisting of a set of transactions to be written into the log. After receiving all proposals, an auditor decides which one to use for the next round.

Priority is given to those proposals which have supermajority support. In other words, an auditor changes its choice based on whichever proposal gains the most support. This process continues through multiple rounds until a clear supermajority emerges. The threshold for this supermajority is adjustable, but the default used on the Ripple network is 80%.

This process has been called “avalanche” because of the way a single proposal rapidly becomes the preferred choice. The use of avalanche consensus, coupled with the fact that auditors only need to listen to a handful of trusted peers offers the potential for very fast transaction finalization. On the Ripple Network, for example, a transaction can be finalized within five seconds.

Notice that in contrast to proof-of-work and proof-of-stake, RCP offers no mechanism for initial distribution through Leader selection. This leaves only one option: the network creator receives all value at the inception of the network. This value is then distributed to users through a manual process.

Nor does RCP offer a mechanism to distribute transaction fees to auditors. Instead, the Ripple Network simply destroys value used for transaction fees. This results in the inevitable destruction of money during the normal course network operation.

 

Originally written by Richard L. Apodaca. You should also read Zcash Safer Than Bitcoin When Doing Business On the Dark Web.