search

whyrusleeping / toychain

A quick and ugly hack at making a blockchain on ipfs. NOT MAINTAINED
MIT License
18 stars 8 forks source link

CRDTs for global consensus #1

Open drwasho opened 6 years ago

drwasho commented 6 years ago

Something I always wanted to ask is whether CRDTs could be used to come to eventual consensus on the state of the ledger?

whyrusleeping commented 6 years ago

Its an interesting idea. you could definitely use crdts to come to eventual consensus, but then the problem of finality becomes a lot blurrier. When can I be sure that my transaction has gone through?

Some systems like spectre: https://eprint.iacr.org/2016/1159.pdf move towards this, they don't have a single linear chain, but a dag of blocks (which is misleading, because ethereum is already a dag due to GHOST). I havent read their paper, but it seems interesting, And i'll bet they have some thoughts on this.

The most difficult thing i see in a CRDT based blockchain is figuring out how to merge two chains that have a double spend. Either one is invalid (and you have to determine which one) or both are valid and the offending transaction needs to not be applied (hard).

drwasho commented 6 years ago

It seems to me that the probability that a transaction is valid and without any conflicts is a function of time (which itself is partly a function of the network topology), and it could probably be represented as a probabilistic metric that is 'safe' above or below a certain threshold (rather than 'wait 10-60 minutes' in the case of Bitcoin).

The most difficult thing i see in a CRDT based blockchain is figuring out how to merge two chains that have a double spend.

Yep this is the ballgame, and hence the elegance of a blockchain. But interestingly Bitcoin handles the double-spend problem by hoping that the miner with sufficient PoW has likely received the first transaction in their mempool first, but there is no guarantee of this.

Again, I'm just spitballing here, but I wonder if the difficulty of a double-spend can be ameliorated by requiring multi-input transactions.

0zAND1z commented 5 years ago

We could use the nonce of the origin account to handle double spend in a way.

drwasho commented 5 years ago

In many ways I think Avalanche has achieved what I was thinking about for eventual consensus via CRDTs; let's see how it performs.