BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Vincent Gramoli

Vincent Gramoli contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingCryptography and SecurityComputer Science and Game TheoryFormal Languages and Automata TheoryLogic in Computer ScienceOperating Systems

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

9 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

CollaChain: A BFT Collaborative Middleware for Decentralized Applications

The sharing economy is centralizing services, leading to misuses of the Internet. We can list growing damages of data hacks, global outages and even the use of data to manipulate their owners. Unfortunately, there is no decentralized web where users can interact peer-to-peer in a secure way. Blockchains incentivize participants to individually validate every transaction and impose their block to the network. As a result, the validation of smart contract requests is computationally intensive while the agreement on a unique state does not make full use of the network. In this paper, we propose Collachain, a new byzantine fault tolerant blockchain compatible with the largest ecosystem of DApps that leverages collaboration. First, the pariticipants executing smart contracts collaborate to validate the transactions, hence halving the number of validations required by modern blockchains (e.g., Ethereum, Libra). Second, the participants in the consensus collaborate to combine their block proposal into a superblock, hence improving throughput as the system grows to hundreds of nodes. In addition, Collachain offers the possibility to its users to interact securely with each other without downloading the blockchain, hence allowing interactions via mobile devices. Collachain is effective at outperforming the Concord and Quorum blockchains and its throughput peaks at 4500 TPS under a Twitter DApp (Decentralized Application) workload. Finally, we demonstrate Collachain's scalability by deploying it on 200 nodes located in 10 countries over 5 continents.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Holistic Verification of Blockchain Consensus

Blockchain has recently attracted the attention of the industry due, in part, to its ability to automate asset transfers. It requires distributed participants to reach a consensus on a block despite the presence of malicious (a.k.a. Byzantine) participants. Malicious participants exploit regularly weaknesses of these blockchain consensus algorithms, with sometimes devastating consequences. In fact, these weaknesses are quite common and are well illustrated by the flaws in the hand-written proofs of existing blockchain consensus protocols [63]. Paradoxically, until now, no blockchain consensus has been holistically verified using model checking. In this paper, we remedy this paradox by model checking for the first time a blockchain consensus used in industry. We propose a holistic approach to verify the consensus algorithm of the Red Belly Blockchain [20], for any number $n$ of processes and any number $f<n/3$ of Byzantine processes. We decompose directly the algorithm pseudocode in two parts -- an inner broadcast algorithm and an outer decision algorithm -- each modelled as a threshold automaton [36], and we formalize their expected properties in linear-time temporal logic. We then automatically check the inner broadcasting algorithm, under a carefully identified fairness assumption. For the verification of the outer algorithm, we simplify the model of the inner algorithm by relying on its checked properties. Doing so, we formally verify not only the safety properties of the Red Belly Blockchain consensus but also its liveness in about 70 seconds.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

SocChain: Blockchain with Swift Proportional Governance for Bribery Mitigation

Blockchain governance is paramount to leading securely a large group of users towards the same goal without disputes about the legitimacy of a blockchain instance over another. As of today, there is no efficient way of protecting this governance against an oligarchy. This paper aims to offer a new dimension to the security of blockchains by defining the Swift Proportional Governance problem. This problem is to rapidly elect governance users that proportionally represent voters without the risk of dictatorship. We then design and implement an open permissioned blockchain called SocChain (Social Choice Blockchain) that mitigates bribery by building upon results in social choice theory. We deploy SocChain and evaluate our new multi-winner election DApp running on top of it. Our results indicate that using our DApp, 150 voters can elect a proportionally representative committee of 150 members within 5 minutes. Hence we show that SocChain can elect as many representatives as members in various global organizations.

0 citations0 reviewsNo code linkedOpen access
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 &#34;double spending&#34;.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Concurrency-Optimal List-Based Set

Designing an efficient concurrent data structure is an important challenge that is not easy to meet. Intuitively, efficiency of an implementation is defined, in the first place, by its ability to process applied operations in parallel, without using unnecessary synchronization. As we show in this paper, even for a data structure as simple as a linked list used to implement the set type, the most efficient algorithms known so far are not concurrency-optimal: they may reject correct concurrent schedules. We propose a new algorithm for the list-based set based on a value-aware try-lock that we show to achieve optimal concurrency: it only rejects concurrent schedules that violate correctness of the implemented set type. We show empirically that reaching optimality does not induce a significant overhead. In fact, our implementation of the concurrency-optimal algorithm outperforms both the Lazy Linked List and the Harris-Michael state-of-the-art algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Anonymity Preserving Byzantine Vector Consensus

Collecting anonymous opinions finds various applications ranging from simple whistleblowing, releasing secretive information, to complex forms of voting, where participants rank candidates by order of preferences. Unfortunately, as far as we know there is no efficient distributed solution to this problem. Previously, participants had to trust third parties, run expensive cryptographic protocols or sacrifice anonymity. In this paper, we propose a resilient-optimal solution to this problem called AVCP, which tolerates up to a third of Byzantine participants. AVCP combines traceable ring signatures to detect double votes with a reduction from vector consensus to binary consensus to ensure all valid votes are taken into account. We prove our algorithm correct and show that it preserves anonymity with at most a linear communication overhead and constant message overhead when compared to a recent consensus baseline. Finally, we demonstrate empirically that the protocol is practical by deploying it on 100 machines geo-distributed in 3 continents: America, Asia and Europe. Anonymous decisions are reached within 10 seconds with a conservative choice of traceable ring signatures.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dispel: Byzantine SMR with Distributed Pipelining

Byzantine State Machine Replication (SMR) is a long studied topic that received increasing attention recently with the advent of blockchains as companies are trying to scale them to hundreds of nodes. Byzantine SMRs try to increase throughput by either reducing the latency of consensus instances that they run sequentially or by reducing the number of replicas that send messages to others in order to reduce the network usage. Unfortunately, the former approach makes use of resources in burst whereas the latter requires CPU-intensive authentication mechanisms. In this paper, we propose a new Byzantine SMR called Dispel (Distributed Pipeline) that allows any node to distributively start new consensus instances whenever they detect sufficient resources locally. We evaluate the performance of Dispel within a single datacenter and across up to 380 machines over 3 continents by comparing it against four other SMRs. On 128 nodes, Dispel speeds up HotStuff, the Byzantine fault tolerant SMR being integrated within Facebook&#39;s blockchain, by more than 12 times. In addition, we also test Dispel under isolated and correlated failures and show that the Dispel distributed design is more robust than HotStuff. Finally, we evaluate Dispel in a cryptocurrency application with Bitcoin transactions and show that this SMR is not the bottleneck.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Feasibility of Cross-Chain Payment with Success Guarantees

We consider the problem of cross-chain payment whereby customers of different escrows---implemented by a bank or a blockchain smart contract---successfully transfer digital assets without trusting each other. Prior to this work, cross-chain payment problems did not require this success, or any form of progress. We demonstrate that it is possible to solve this problem when assuming synchrony, in the sense that each message is guaranteed to arrive within a known amount of time, but impossible to solve without assuming synchrony. Yet, we solve a weaker variant of this problem, where success is conditional on the patience of the participants, without assuming synchrony, and in the presence of Byzantine failures. We also discuss the relation with the recently defined cross-chain deals.

0 citations0 reviewsNo code linkedOpen access