ترغب بنشر مسار تعليمي؟ اضغط هنا

FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures

67   0   0.0 ( 0 )
 نشر من قبل Serguei Popov
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

This paper presents a novel leaderless protocol (FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures) with a low communicational complexity and which allows a set of nodes to come to a consensus on a value of a single bit. The paper makes the assumption that part of the nodes are Byzantine, and are thus controlled by an adversary who intends to either delay the consensus, or break it (this defines that at least a couple of honest nodes come to different conclusions). We prove that, nevertheless, the protocol works with high probability when its parameters are suitably chosen. Along this the paper also provides explicit estimates on the probability that the protocol finalizes in the consensus state in a given time. This protocol could be applied to reaching consensus in decentralized cryptocurrency systems. A special feature of it is that it makes use of a sequence of random numbers which are either provided by a trusted source or generated by the nodes themselves using some decentralized random number generating protocol. This increases the overall trustworthiness of the infrastructure. A core contribution of the paper is that it uses a very weak consensus to obtain a strong consensus on the value of a bit, and which can relate to the validity of a transaction.



قيم البحث

اقرأ أيضاً

Byzantine fault-tolerant (BFT) state machine replication (SMR) has been studied for over 30 years. Recently it has received more attention due to its application in permissioned blockchain systems. A sequence of research efforts focuses on improving the commit latency of the SMR protocol in the common good case, including PBFT with $3$-round latency and $ngeq 3f+1$ and FaB with $2$-round latency and $ngeq 5f+1$. In this paper, we propose an authenticated protocol that solves $2$-round BFT SMR with only $ngeq 5f-1$ replicas, which refutes the optimal resiliency claim made in FaB for needing $n geq 5f+1$ for $2$-round PBFT-style BFT protocols. For the special case when $f=1$, our protocol needs only $4$ replicas, and strictly improves PBFT by reducing the latency by one round (even when one backup is faulty).
We present new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The celebrated PBFT state machine replication protocol tolerates $f$ Byzantine faults in an asynchronous setting us ing $3f+1$ replicas, and has since been studied or deployed by numerous works. In this work, we improve the Byzantine fault tolerance threshold to $n=2f+1$ by utilizing a relaxed synchrony assumption. We present a synchronous state machine replication protocol that commits a decision every 3 rounds in the common case. The key challenge is to ensure quorum intersection at one honest replica. Our solution is to rely on the synchrony assumption to form a post-commit quorum of size $2f+1$, which intersects at $f+1$ replicas with any pre-commit quorums of size $f+1$. Our protocol also solves synchronous authenticated Byzantine agreement in expected 8 rounds. The best previous solution (Katz and Koo, 2006) requires expected 24 rounds. Our protocols may be applied to build Byzantine fault tolerant systems or improve cryptographic protocols such as cryptocurrencies when synchrony can be assumed.
Partially synchronous Byzantine consensus protocols typically structure their execution into a sequence of views, each with a designated leader process. The key to guaranteeing liveness in these protocols is to ensure that all correct processes event ually overlap in a view with a correct leader for long enough to reach a decision. We propose a simple view synchronizer abstraction that encapsulates the corresponding functionality for Byzantine consensus protocols, thus simplifying their design. We present a formal specification of a view synchronizer and its implementation under partial synchrony, which runs in bounded space despite tolerating message loss during asynchronous periods. We show that our synchronizer specification is strong enough to guarantee liveness for single-sh
85 - Tung-Wei Kuo , Kung Chen 2019
In this paper, we give a deterministic two-step Byzantine consensus protocol that achieves safety and liveness. A two-step Byzantine consensus protocol only needs two communication steps to commit in the absence of faults. Most two-step Byzantine con sensus protocols exploit optimism and require a recovery protocol in the presence of faults. In this paper, we give a simple two-step Byzantine consensus protocol that does not need a recovery protocol.
In this note, we observe a safety violation in Zyzzyva and a liveness violation in FaB. To demonstrate these issues, we require relatively simple scenarios, involving only four replicas, and one or two view changes. In all of them, the problem is manifested already in the first log slot.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا