Economic Models of Consensus on Distributed Ledgers in Blockchain Technology
This study delves into Byzantine Fault Tolerance (BFT) protocols in the realm of distributed ledgers, exploring the complexities of achieving consensus in trusted adversarial environments. The research examines the classic problem in computer science where distributed nodes communicate to reach agreement without global knowledge. It also delves into the consensus game among computer nodes, shedding light on decision-making processes and strategies involved in maintaining distributed databases. The paper addresses the challenges posed by Byzantine nodes and the rationality of non-Byzantine nodes in trustless blockchain environments.
Uploaded on Sep 07, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
An Economic Model of Consensus on Distributed Ledgers Hanna Halaburda, NYU Stern Zhiguo He, Chicago Booth and NBER Jiasun Li, George Mason
Byzantine Fault Tolerance (BFT) in blockchains A classic problem A resurgence of interest Trusted adversarial environments
Byzantine Fault Tolerant (BFT) protocols Classic problem in computer science (since Lamport, Shostak, Pease `82) Distributed computer nodes communicate with each other to Reach consensus based on local information (no global knowledge) Byzantine nodes behave arbitrarily Stipulate honest strategies for non-Byzantine nodes Widely used in tech companies to maintain distributed databases
Byzantine Fault Tolerant (BFT) protocols Classic problem in computer science (since Lamport, Shostak, Pease `82) Distributed computer nodes communicate with each other to Reach consensus based on local information (no global knowledge) Byzantine nodes behave arbitrarily Stipulate honest strategies for non-Byzantine nodes Widely used in tech companies to maintain distributed databases This paper (given that blockchains live in trustless environments) Non-Byzantine nodes are rational Ambiguity averse (Knightian uncertain) about Byzantine strategies
Consensus game A game among a measure of n computer nodes: Nature randomly selects one node as the leader; Denote all other nodes as backups; Leader decides, for each backup, whether to send a message; e.g. new batch of transactions in a blockchain; problem.oblem. Each backup receiving message from leader (if yes), for each other node, whether to forward message; Each node then decides whether to commit to message based on its local information set. For simplicity, we study one round of synchronous peer communication in a single view. Lamport, Shostak and Pease (1982) study f rounds. Castro and Liskov (1999) (PBFT) study two rounds of communication with view changes. We also assume adequately close message delivery speeds to justify simultaneous moves in each step.
Consensus game A game among a measure of n computer nodes: Nature randomly selects one node as the leader; Denote all other nodes as backups; Leader decides, for each backup, whether to send a message; e.g. new batch of transactions in a blockchain; problem. Each backup receiving message from leader (if yes), for each other node, whether to forward message; Each node then decides whether to commit to message based on its local information set. For simplicity, we study one round of synchronous peer communication in a single view. Lamport, Shostak and Pease (1982) study f rounds. Castro and Liskov (1999) (PBFT) study two rounds of communication with view changes. We also assume adequately close message delivery speeds to justify simultaneous moves in each step.
Consensus game A game among a measure of n computer nodes: Nature randomly selects one node as the leader; Denote all other nodes as backups; Leader decides, for each backup, whether to send a message; e.g. new batch of transactions in a blockchain; Each backup receiving message from leader for each other node, whether to forward message; Each node then decides whether to commit to message based on its local information set. For simplicity, we study one round of synchronous peer communication in a single view. Lamport, Shostak and Pease (1982) study f rounds. Castro and Liskov (1999) (PBFT) study two rounds of communication with view changes. We also assume adequately close message delivery speeds to justify simultaneous moves in each step.
Consensus game A game among a measure of n computer nodes: Nature randomly selects one node as the leader; Denote all other nodes as backups; Leader decides, for each backup, whether to send a message; e.g. new batch of transactions in a blockchain; Each backup receiving message from leader decides, for each other node, whether to forward message; Each node then decides whether to commit to message based on its local information set. For simplicity, we study one round of synchronous peer communication in a single view. Lamport, Shostak and Pease (1982) study f rounds. Castro and Liskov (1999) (PBFT) study two rounds of communication with view changes. We also assume adequately close message delivery speeds to justify simultaneous moves in each step.
Consensus game A game among a measure of n computer nodes: Nature randomly selects one node as the leader; Denote all other nodes as backups; Leader decides, for each backup, whether to send a message; e.g. new batch of transactions in a blockchain; Each backup receiving message from leader decides, for each other node, whether to forward message; Each node then decides whether to commit to message based on its local information set. For simplicity, we study one round of synchronous peer communication in a single view. Lamport, Shostak and Pease (1982) study f rounds. Castro and Liskov (1999) (PBFT) study two rounds of communication with view changes. We also assume adequately close message delivery speeds to justify simultaneous moves in each step.
Two types of nodes Measure f of Byzantine nodes, who may take arbitrary actions; Measure n f of rational nodes, who maximize utilities: if consensus on message Succeeds Fails Commit to message R > 0 -c < 0 Not commit to message 0 0 Consensus succeeds iff almost all (measure n f) rational nodes commit A dynamic game of imperfect info. w/ cheap talk & coordination Solution concept: perfect Bayesian eqm + multi-priors over Byzantine strategies
Two types of nodes Measure f of Byzantine nodes, who may take arbitrary actions; Measure n f of rational nodes, who maximize utilities: ? if consensus on message ? ? Succeeds Fails Commit to message R > 0 -c < 0 Not commit to message 0 0 ? Consensus succeeds iff almost all (measure n f) rational nodes commit A dynamic game of imperfect info. w/ cheap talk & coordination Solution concept: perfect Bayesian eqm + multi-priors over Byzantine strategies
Two types of nodes Measure f of Byzantine nodes, who may take arbitrary actions; Measure n f of rational nodes, who maximize utilities: ? if consensus on message ? ? Succeeds Fails Commit to message R > 0 -c < 0 Not commit to message 0 0 ? Consensus succeeds iff almost all (measure n f) rational nodes commit A dynamic game of imperfect info. ( coordination & cheap talk ) Solution concept: perfect Bayesian eqm + multi-priors over Byzantine strategies
Ambiguity aversion Rational nodes are ambiguity averse towards Byzantine strategies assume worst case scenario Formally, a rational node ? at any information set ?? facing all possible Byzantine strategies in chooses action ai to maximize min ? [??(??,? ?;?)|??] if a Byzantine strategy profile consistent with ?? such that a positive measure of rational nodes does not commit, then ? will not commit
Characterizing all symmetric equilibria Consider a candidate symmetric equilibrium in which a rational leader sends message to each backup with prob. p a rational backup forwards message (if received) with prob. q a backup commits iff receiving k ?1 [0, (n f) q + f]messages, with one from the leader; or k ?0 [0, (n f) q + f]messages, none of which is from the leader. If ?1 ?0= , then a gridlock equilibrium (failed consensus) Our interest is in (successful) consensus equilibrium with p > 0 and q > 0
Inferences about the leader ? ? ?? + ?? #msg a rational backup receives ? ? ? + ? ? ? ??
? ? ? + ? about other rational nodes #msg another backup receives ? ? ?? + ?? #msg a rational backup receives ? ? ? + ? ? ? ??
? ? ? + ? if the leader is Byzantine ? about other rational nodes Byzantine nodes can coordinate: Deliver any number of msgs in this range with perfect precision #msg another backup receives ? ? ? ?? + ?? #msg a rational backup receives ? ? ? ? + ? ? ? ??
? ? ? + ? if the leader is rational ?? #msg another backup receives ? ? ? ?? + ?? #msg a rational backup receives ? ? ? ? + ? ? ? ??
The properties of a consensus equilibrium A consensus equilibrium has ?1 ?0= [ ? ? ??, ? ? ?? + ??] A rational backup who knows the leader is Byzantine always gets c from committing to message thus does not commit to message except for when ? = 1 and she receives exactly ? = ? ? ? + ? messages
? ? ?? + ?? ?) #msg a rational backup receives ? ? ? + ? ? ? ??
? ? ?? + ?? ?) #msg a rational backup receives ? ? ? + ? ? ? ??
? ? ?? + ?? ?) #msg a rational backup receives ? ? ? + ? ? ? ??
? ? ?? + ?? ) ?) #msg a rational backup receives 2? ? ? ? + ? ? ? ??
? ? ?? + ?? ) ?) #msg a rational backup receives 2? ? ? ? + ? ? ? ??
? ? ?? + ? ? ? ?? + ?? ) ) ?) #msg a rational backup receives 2? ? ? ? + ? ? ? ??
? ? ?? + ? ? ? ?? + ?? ) ) ?) #msg a rational backup receives 2? ? ? ? + ? ? ? ??
? ? ?? + ? ? ? ?? + ?? ) ) ?) #msg a rational backup receives 2? ? ? ? + ? ? ? ??
?? ? ? ?? + ?? #msg a rational backup receives ? ? ? + ? ? ? ??
Need to characterize conditions for reward/penalty ? and ? under which it is indeed preferred to commit in this interval ? ? ?? + ?? #msg a rational backup receives ? ? ? + ? ? ? ??
All symmetric equilibria A gridlock" equilibrium: discard communications and never commit Interval-??-equilibria indexed by ?,? (0,1] when 1 2? ? ? ??: ?? ? ? ?, 1 ?? A rational leader sends message to each backup with prob. ? [ A rational backup forwards message (if received) with prob. ? (0,1]; A rational backup commits iff receiving ? [ ? ? ??, ? ? ?? + ??] messages, receiving from the leader or not, i.e. ?0= ?1= [ ? ? ??, ? ? ?? + ??] Singleton-??-equilibria indexed by ? (0,1] when ? ? ? ??: A rational leader sends message to each backup with ? = 1; A rational backup forwards message (if received) with prob. ? 0,1 ; A rational backup commits iff receiving ? [ ? ? ?, ? ? ? + ?] messages, with one from the leader or ? ? ? + ? messages without any from the leader, i.e. ?1= ? ? ?, ? ? ? + ? and ?0= { ? ? ? + ?}. ? ? ?];
Message losses All messages sent are delivered with prob. ? < 1 A gridlock equilibrium still exists Singleton-?0-equilibria no longer exist Interval-?0-equilibria require higher ?/? to sustain for small ? Supporting ?/? regions expands as message loss prob. ? decreases
Implications Operational success of any blockchain depends on its design. Accounting for incentives in BFT consensus: All designs are subject to multiple equilibria concerns gridlock equilibria always exist possibility of system stuck Small probability of message loss significantly affects equilibria Existence of consensus equilibrium depends on R and c R and c may be restricted by the environment or can be within decision of the system designer
Relation to existing work BFT in CS info important but non-Byzantine nodes are honest Lamport, Shostak and Pease (1982), Catro and Liskov (1999) in Econ, focus mostly on PoW, PoS and delegated PoS Budish (2018), Cong, He and Li (2021), Saleh (2021), etc. PBF work in Econ cost of sending messages Amoussou-Guenou, Biais, Potop-Butucaru and Tucci-Piergiovanni (2020), Auer, Monnet and Shin (2021)
Our contribution An economic framework to analyze incentives in BFT protocols Guidance for maintaining reliable distributed ledgers among self- interested parties Focus on information imperfection, rather than, say, operating costs Intrinsic to the challenges faced by distributed systems Thank you!
