Research Summary - Karada: an objective and truly decentralised Proof of Stake protocol

TLDR

  • This paper presents Karada, the first PoS protocol which guarantees complete decentralisation of consensus (i.e., it doesn’t require electing a subset of nodes in the form of a block-validating committee, allowing any number of nodes to share the task of validating blocks) in a network composed of an arbitrarily large number of nodes.
  • Karada allows for a computationally inexpensive comparison of the canonicity of any two forks by comparing them in terms of the amount of stake used in the course of their production. This way, a node (re)synchronising with the network can, under any plausible conditions, establish the canonical blockchain, which makes the Karada protocol the only objective PoS protocol.
  • By analysing potential attack vectors and providing relevant calculations, we find that Karada is secure under the most adversarial conditions.

Citation

Kuroi Hakuchō, “Karada: an objective and truly decentralised Proof of Stake protocol”, April 2023.

Link

Core Research Questions

  • How to design a permissionless PoS consensus protocol which allows an arbitrarily large amount of network participants to confirm, while taking part in reaching consensus in the network in an uninterrupted manner, the correct chain of blocks?
  • How to design an objective PoS consensus protocol?

Background

  • In any PoS protocol, a relatively small subset of nodes participating in sharing the task of validating transactions needs to be chosen either by using some sort of a verifiable random function to select them or by having some nodes delegate their right to participate to a set of delegates. In consequence, each time a block is produced, either a single node or a small group thereof confirms, through adding the block to a chain of blocks, the validity of all the blocks which precede it (i.e., the added block). In a PoS protocol, attempting to allow an unlimited number of nodes to be a part of the committee which obtains consensus on the canonical blockchain would result in a prohibitive communication complexity, which grows exponentially in respect to the number of nodes in the mentioned committee, i.e., it would require O(n²) communication (as each consensus participants would need to exchange messages related to achieving consensus with each other one). In turn, this would cause a bottleneck which would limit the potential level of network decentralisation.
  • In consequence of the above-mentioned, the consensus is, at each given time t, obtained by a relatively small committee of nodes c. Therefore, any self-consistent (i.e., valid according to the given protocol’s rules) blockchain version purportedly produced by c at t is as canonical as any other such version. Should two or more such versions be produced, there would be no effective measuring mechanism that would allow a node (re)synchronising with the network to quantitatively compare the canonicity of said two self-consistent blockchain extensions (as is possible in PoW by applying the “longest chain” rule). In such a situation, the only way for nodes to come to the same conclusion on which version of the blockchain is correct would be to rely on trusted, centralised oracle-like institutions, which would then decide on the canonical chain. In face of a conflict, the network would split and the only available recourse would be off-chain politics.

Summary

  • We propose a PoS protocol which allows for true decentralisation. Any number of nodes, even billions, can vote for the correct blockchain each time a new block is to be produced (in fact, the nodes vote explicitly on a chain of ordered block producers; this, however, translates into confirming implicitly a particular chain of blocks as well, as we discuss in the paper) and the version supported by the majority has the highest chance of being confirmed in said to-be-produced block, with no ensuing dilemma between scalability and decentralisation of consensus.
  • Furthermore, the same canonical chain will necessarily be established, in a computationally inexpensive way, by all nodes following the protocol, under any plausible conditions, thus making the protocol objective.

Method

  • The proposed protocol is presented in a detailed way.
  • Then, the correctness of our assumptions about the protocol’s behaviour and security is analysed, conclusions are being drawn, and supporting calculations are provided.

Results

  • In a synchronous network model, Karada is a permissionless Byzantine Fault tolerant protocol which comes with strong objectivity and solves the dilemma between scalability and decentralisation of consensus in a PoS consensus model.

Implications & Follow-ups

  • While PoS consensus protocols come with a wide variety of advantages over the PoW ones, it was previously unknown how they can avoid favouring either decentralisation (i.e., an increase in the share of nodes, out of all the network nodes, taking an active part in validating blocks) or scalability (i.e., an increase in the total number of nodes in the network) in relation to consensus. Karada can accomplish both simultaneously.
  • PoS protocols operate only under an assumption of weak subjectivity. It was previously unknown how an objective PoS protocol could be designed.

Applicability

  • The paper presents the first PoS consensus protocol which is perfectly decentralised while operating in a network of any size. It allows an arbitrarily large set of nodes to, each time a block is to be produced, take part in the consensus on the canonical chain of blocks which precede the to-be-produced block, where communication complexity required is approximately constant, i.e., O(1). In fact, it is the first method of achieving consensus between parties which don’t need to trust each other, where there is no need for either selecting some leaders (committees, validators, delegates, governments, board members, etc.) or using an external input (such as hashing power).
  • Furthermore, the protocol comes with an effective fork-choice under any plausible conditions, thus being the first PoS protocol with an objectivity comparable to that of PoW.
3 Likes