3 ms·
I think people get consensus finality mixed up with eventual consistency. (To be fair, they do sound like similar things.) Nakamoto Consensus (used by Bitcoin
by troymc 10y ago
I think people get consensus finality mixed up with eventual consistency. (To be fair, they do sound like similar things.)
Nakamoto Consensus (used by Bitcoin and others) never reaches consensus finality, i.e. a point in time when you can be sure that consensus has been achieved. All you can do is estimate the probability that a block is in the final chain.
That said, Nakamoto Consensus has some really nice properties compared to classical consensus algorithms. For example, most "classical" BFT consensus algorithms have a worst-case message complexity of O(N^2) (or in some new highly-academic algorithms O(N polylog(N))). Nakamoto Consensus, in contrast, has O(N) worst-case message complexity. That's what enables Bitcoin (and the like) to scale so nicely to thousands of nodes.
Of course, if you're building a permissioned ledger with 25 nodes, that's irrelevant; the classical algorithms will work fine.
There's more discussion of this in the SCP paper: Luu, Loi, Viswesh Narayanan, Kunal Baweja, Chaodong Zheng, Seth Gilbert, and Prateek Saxena. "SCP: A Computationally-Scalable Byzantine Consensus Protocol For Blockchains."
- spdionis 10y agoWhat is polylog(N)?
- jey 10y agohttp://stackoverflow.com/a/1801162 http://stackoverflow.com/a/1801162
- lambda 10y agoLink for the lazy: https://eprint.iacr.org/2015/1168 https://eprint.iacr.org/2015/1168
- iambvk 10y agoIMO, more interesting property than the messaging complexity is, bitcoin (in theory) allows <50% malicious actors in the consensus group. Lamport BFT only allows <33% malicious actors. Of course, this comparison is not really fair because Lamport BFT achieves deterministic consensus, where as, bitcoin only gives probabilistic consensus. I hope there is room for Deterministic BFT with <50% malicious actors. > or in some new highly-academic algorithms O(N polylog(N)) Could you point me to this algorithm? I am not aware of any BFT solution other Lamport BFT.
- troymc 10y agoThere are many deterministic BFT protocols. PBFT is probably the most well-known. [1] The SCP paper points to several BFT protocols with message complexity of O(N polylog(N)), e.g. [2] [1] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, pages 173–186. USENIX Association, 1999. [2] Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. Load balanced scalable byzantine agreement through quorum building, with full information. In MarcosK. Aguilera, Haifeng Yu, Nitin H. Vaidya, Vikram Srinivasan, and RomitRoy Choudhury, editors, Distributed Computing and Networking, volume 6522 of Lecture Notes in Computer Science, pages 203–214. Springer Berlin Heidelberg, 2011.