CyLab research leads to blockchain paradigm shift

Right now, making a transaction on the Bitcoin blockchain involves paying a transaction fee to Bitcoin “miners,” people who maintain the blockchain. These miners record the transaction on the blockchain, and once it’s on record, the currency has officially changed hands. The proof is in the blockchain.

The holy grail for blockchain transaction mechanisms is for the mechanism to be both easy to use as well as secure from potential manipulation. New research out of CyLab shows that it’s literally impossible to have it both ways, at least in the traditional way of thinking about blockchains.

My paper shows that if you want both of these properties at the same time, it is impossible.

Hao Chung, Ph.D. student, Electrical and Computer Engineering

Hao Chung, a Ph.D. student in Electrical and Computer Engineering advised by CyLab’s Elaine Shi, presented these findings in a plenary talk this week at the ACM Conference on Economics and Computation (EC’22) in Boulder, Colorado.

“My paper shows that if you want both of these properties at the same time, it is impossible,” says Chung. “You can only choose one.”

If you want the system to be not manipulated by miners, Chung says, then the system will be very difficult to use. However, if you have a system that is very user-friendly, then it will be vulnerable to miner manipulation.

“How do we bypass this impossibility?” Chung asks. “We conceived a relaxed model.”

During a transaction, users put “bids” in as their transaction fees. Higher bids are typically prioritized by miners over lower bids, meaning that higher bids are recorded to the blockchain faster than lower bids.

Traditionally, Chung says, the blockchain research community thinks that an adversary can bias the system by overbidding and underbidding the system “for free”—free, meaning, with no consequences.

“This assumption makes sense if you just focus on one block, as if it were a single auction,” says Chung. “However, the blockchain itself is endless blocks. There is always another block after this block.”

So now, Chung says, if the strategic player considers the future—they may gain something now, but they may lose more in the future—this changes the potential to have a mechanism that is both easy to use and safe from manipulation.

“If the adversary also considers the possible loss in the future, they don’t want to exploit,” Chung says. “In this sense, we can have a transaction mechanism that satisfies both properties. 

Shi, Chung’s advisor, says the paper lays the scientific foundation for studying decentralized mechanism design.

“Fueled by blockchain and cryptocurrency applications, decentralized mechanism design is an exciting new area with lots of open questions,” says Shi. “Most blockchain projects adopt protocols with heuristic guarantees, and our work is laying the groundwork for mathematically reasoning about the incentive compatibility of decentralized protocols.”

Paper reference

Foundations of Transaction Fee Mechanism Design

• Hao Chung, Carnegie Mellon University
• Elaine Shi, Carnegie Mellon University