New Research Targets a Big Worry for Some Blockchains: Double-Spent Transactions

A trio of researchers say they’ve discovered a way to detect and punish dishonest blockchain participants, according to a paper published at the end of May.

“The (virtual) gold rush is on, and as in the Wild West of yore, the outlaws are ever present,” states the paper, entitled Polygraph: Accountable Byzantine Agreement. 

The authors — Vincent Gramoli and Pierre Civit of the University of Sydney, and Seth Gilbert of the National University of Singapore — developed the Polygraph protocol, which automates accountability in blockchains to hold participants accountable for double spending, a notoriously knotty issue in cryptography.

Though the double spend problem was supposedly solved by Satoshi’s white paper, published in 2008, the researchers discovered that disagreements caused by blockchain forks can lead to double spending if the resulting branches have conflicting transactions. 

They cite a zombie case:

“Byzantine nodes can override the General Polygraph Protocol by proposing directly two conflicting views to two different clients to then perform a double-spending attack. The coalition does not participate to the consensus in order to violate the liveness property…. Note that safety is also violated: When a client invokes the read() primitive, the coalition can answer arbitrary values, despite the non-termination of the legitimate consensus. The client is supposed to trust the coalition, like all the other clients who can forever receive a different output for the read() primitive. Hence, for t ≥ n − t0, the eventual prefix property is violated. This makes the blockchain vulnerable to a double-spending attack.”

Real-world focus

Yes, the paper is scholarly, but it also provides pragmatic solutions to real problems in current consensus mechanisms.

The group considers the growing threat of centralization on blockchains, caused by the collectivizing of hashing power. Under traditional Byzantine protocol agreements, if one party amasses more than one-third of total mining output they gain decision making authority. As an aside, the authors note that the largest Bitcoin mining pool today controls approximately 19 percent of total hashing power.

“We need a new sheriff in town to bring the guilty parties to justice. What if, instead of preventing bad behavior by a party that controls too much of the network power, we guarantee accountability,” write the authors.

Much in the way we prevent crime in the real world, we can prevent bad blockchain behavior via “defense-in-depth” — the basic Byzantine agreement protocol that prevents usurpation if the attacker has less than one-third of network control or if the network infrastructure is working to pass messages in time.

“Byzantine agreement protocols act as the locks on the bank doors, preventing the gangs from making off with the loot,” they wrote.

However, when these guarantees fail — and the authors suggest they can and do — the Polygraph protocol will intercept malicious behavior.

The Polygraph’s basic algorithm is based on the Byzantine agreement protocol, but goes further in that proceeds through asynchronous rounds, or a vote that receives democratic input.

“First, a reliable broadcaster is used to distribute the proposal values. Then, a second phase of communication is used to determine whether enough processes have converged on a single value. Finally the processes decide, if they can; and if not, they update their estimate in an attempt to converge on a single value.”

When a town isn’t big enough…

If the process determines that someone is pursuing illegal actions, the consensus can vote them off the network.

“Accountability has been overlooked in blockchains but it is actually key to security,” said Gramoli, who also serves as Red Belly Blockchain CEO. “The industry cannot accept blockchain to be a simple distributed system where valuable assets vanish as soon as a third of the participants form a coalition.”

Red Belly Blockchain has been funded by the Australian Research Council and developed by researchers of the Concurrent Systems Research Group at the University of Sydney and Data61-CSIRO.

Photo by Xiang Gao on Unsplash