Source author record

Alejandro Ranchal-Pedrosa

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Computer Science and Game Theory

Catalog footprint

Research overview

2works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Basilic: Resilient Optimal Consensus Protocols With Benign and Deceitful Faults

The problem of Byzantine consensus has been key to designing secure distributed systems. However, it is particularly difficult, mainly due to the presence of Byzantine processes that act arbitrarily and the unknown message delays in general networks. Although it is well known that both safety and liveness are at risk as soon as $n/3$ Byzantine processes fail, very few works attempted to characterize precisely the faults that produce safety violations from the faults that produce termination violations. In this paper, we present a new lower bound on the solvability of the consensus problem by distinguishing deceitful faults violating safety and benign faults violating termination from the more general Byzantine faults, in what we call the Byzantine-deceitful-benign fault model. We show that one cannot solve consensus if $n\leq 3t+d+2q$ with $t$ Byzantine processes, $d$ deceitful processes, and $q$ benign processes. In addition, we show that this bound is tight by presenting the Basilic class of consensus protocols that solve consensus when $n > 3t+d+2q$ . These protocols differ in the number of processes from which they wait to receive messages before progressing. Each of these protocols is thus better suited for some applications depending on the predominance of benign or deceitful faults. Finally, we study the fault tolerance of the Basilic class of consensus protocols in the context of blockchains that need to solve the weaker problem of eventual consensus. We demonstrate that Basilic solves this problem with only $n > 2t+d+q$ , hence demonstrating how it can strengthen blockchain security.

preprint2022arXiv

TRAP: The Bait of Rational Players to Solve Byzantine Consensus

It is impossible to solve the Byzantine consensus problem in an open network of $n$ participants if only $2n/3$ or less of them are correct. As blockchains need to solve consensus, one might think that blockchains need more than $2n/3$ correct participants. But it is yet unknown whether consensus can be solved when less than $2n/3$ participants are correct and $k$ participants are rational players, which misbehave if they can gain the loot. Trading correct participants for rational players may not seem helpful to solve consensus since rational players can misbehave whereas correct participants, by definition, cannot. In this paper, we show that consensus is actually solvable in this model, even with less than $2n/3$ correct participants. The key idea is a baiting strategy that lets rational players pretend to misbehave in joining a coalition but rewards them to betray this coalition before the loot gets stolen. We propose TRAP, a protocol that builds upon recent advances in the theory of accountability to solve consensus as soon as $n>\max\bigl(\frac{3}{2}k+3t,2(k+t)\bigr)$ : by assuming that private keys cannot be forged, this protocol is an equilibrium where no coalition of $k$ rational players can coordinate to increase their expected utility regardless of the arbitrary behavior of up to $t$ Byzantine players. Finally, we show that a baiting strategy is necessary and sufficient to solve this, so-called rational agreement problem. First, we show that it is impossible to solve this rational agreement problem without implementing a baiting strategy. Second, the existence of TRAP demonstrates the sufficiency of the baiting strategy. Our TRAP protocol finds applications in blockchains to prevent players from disagreeing, that could otherwise lead to "double spending".

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.