Our SODA Paper on Proof-of-stake Blockchains

I’m pleased that our paper, titled “Linear consistency for proof-of-stake blockchains,” has been accepted at SODA 2020.

What is the Confirmation Time for Blockchains?

When you are selling a pizza and accepting Bitcoin, usually you wait “for a while” before you “confirm the transaction” and deliver the pizza. You are cautious because a fraudulent user may double spend—use the same bill to pay two different vendors.

If you wait for a while before confirming, the block having your transaction will get deeper and deeper in the blockchain, making it harder for a fraudulent buyer to double-spend the money you received.

But how long should you wait?

Waiting too long means that only a fraction of the transactions get confirmed in a given timeframe—not good for the hungry buyers or the network when we compare it against the “almost instant” confirmation time for regular credit card transactions.

Bitcoin’s Confirmation Time is Arbitrary.

The data in Bitcoin justifies the intuition that if you wait \displaystyle k blocks, the probability of cheating decreases as \displaystyle \exp(-\Omega(k)). Bitcoin recommends that you should wait at least “six blocks” before confirming. Why six? The choice six is arbitrary, and as of October 2018, there’s no mathematical proof justifying the choice of k.

As per https://en.bitcoin.it/wiki/Confirmation:

The classic bitcoin client will show a transaction as “n/unconfirmed” until the transaction is 6 blocks deep. Merchants and exchanges who accept bitcoins as payment can and should set their own threshold as to how many blocks are required until funds are considered confirmed.

[…] There is nothing special about the default, often-cited figure of 6 blocks. It was chosen based on the assumption that an attacker is unlikely to amass more than 10% of the hashrate, and that a negligible risk of less than 0.1% is acceptable. Both these figures are arbitrary, however; 6 blocks are overkill for casual attackers, and at the same time powerless against more dedicated attackers with much more than 10% hashrate.[1]

For transactions with confirmations, the website (https://people.xiph.org/~greg/attack_success.html) can be used to calculate the probability of a successful doublespend given a hashrate proportion and number of confirmations. In the reality of bitcoin mining today, more than 6 confirmations are required. (60 confirmations to have <1% odds of succeeding against an entity with 40% hash power).

The Proof-of-Stake Setting has a Provable Guarantee.

While Bitcoin is in the Proof-of-Work setting, the issue of confirmation time is present in the Proof-of-Stake setting as well. Unlike Bitcoin, however, some Proof-of-Stake blockchains have a provable guarantee on the confirmation time. In particular, in Ouroboros, the authors proved that if you wait k blocks, the probability of cheating decreases as \exp(-\Omega(\sqrt{k})).

Although it is good to have a provable bound, this particular bound leaves a lot to be desired: specifically, the \exp(-\Omega(\sqrt{k})) bound on the “bad probability” is “very loose” compared to the observed bad probability in the Proof-of-Work setting. i.e., \exp(-\Omega(k)).

Our Paper on the Confirmation Time for Proof-of-Stake Blockchains.

Our recent paper (available as a preprint) improves the previous bound: it mathematically shows that even in the Proof-of-Stake setting, the bad probability is at most \exp(-\Omega(k)) if you wait k blocks, matching the performance of the Proof-of-Work setting.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s