Cryptology ePrint Archive: Report 2018/981

PaLa: A Simple Partially Synchronous Blockchain

T-H. Hubert Chan and Rafael Pass and Elaine Shi

Abstract: Classical-style BFT protocols use two or more rounds of voting to confirm each block, e.g., in PBFT, they are called the “prepare” round and the “commit” round respectively. Recently, an elegant pipelining idea came out of the cryptocurrency community, i.e., if each block required two rounds of voting, why not piggyback the second round on the next block’s voting? We refer to this idea as the pipelined-BFT paradigm. We describe a simple partially synchronous blockchain protocol called PaLa that is inspired by the pipelined-BFT paradigm. In PaLa, a proposer proposes a block extending the freshest notarized chain seen so far. Consensus nodes vote on the proposal if certain conditions are met. When a block gains at least 2n 3 votes it becomes notarized. A block becomes finalized if the next immediate block becomes notarized too. We propose a conceptually simple and provably secure committee rotation algorithm for PaLa. We also describe a generalization called “doubly-pipelined PaLa” that is geared towards settings that require high throughput.

Category / Keywords: cryptographic protocols / consensus, blockchains

Date: received 11 Oct 2018, last revised 14 Oct 2018

Contact author: runting at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181018:121826 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]