Byzantine Agreement: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
(Created page with "==Functionality Description== Byzantine agreement{{cn}} is about reaching agreement in a network of <math>n</math> players out of which <math>t</math> players may be faulty. E...")
 
(Task description of Byzantine Agreement)
Line 1: Line 1:
==Functionality Description==
==Functionality Description==
Byzantine agreement{{cn}} is about reaching agreement in a network of <math>n</math> players out of which <math>t</math> players may be faulty. Each player starts with an input bit <math>b_i</math> and the goal is for all correct players to output the same bit <math>d</math> [[agreement]], under the constraint that <math>d = b_i</math> at least for some node <math>i</math> [[validity]]. The [[hardness]] of this task depends on the [[failure model]] of the faulty (sometimes called [[adversary]]) players. In Byzantine agreement, the faulty players are assumed to show the most severe form of failure known as Byzantine failures. In this model, faulty players behave arbitrarily, can collude and even act maliciously trying to prevent correct players from reaching agreement. Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency amongst distributed data structures.
Byzantine agreement is a classical problem concerned with reaching agreement on a single bit of data in a network of <math>n</math> players, out of which <math>t</math> players may be faulty. Each player starts with an input bit <math>b_i</math> and the objective is that all non-faulty players to output the same bit <math>d</math> (''agreement''), under the constraint that <math>d = b_i</math> for some node <math>i</math> (''validity''). The difficulty of this task depends on the [[failure model]] of the faulty players. In Byzantine agreement, the faulty players are allowed to behave arbitrarily (including actively breaking the protocol, colluding etc). Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency among distributed data structures.


'''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]],  [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], consensus task, failure-resilient distributed computing.




'''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]],  [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], consensus task, failure-resilient distributed computing.


[[Category: Two Party Protocols]] [[Category: Quantum Enhanced Classical Functionality]] [[Category:Specific Task]]
==Protocols==
*[[Fast Quantum Byzantine Agreement]]: [[:Category: Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Quantum Computing Network Stage]]


==Protocols==
==Properties==
A Byzantine Agreement protocol is formally defined to satisfy the criteria ''agreement'', ''validity'' and ''termination''. Agreement simply requires every non-faulty player to output the same bit. Validity excludes the trivial solution of always outputting a specific bit, by requiring that the agreement value is at least proposed once. Termination means that any protocol is required to eventually finish. Formally, Byzantine agreement is achieved if


*[[BB84 Quantum Key Distribution]]: [[:Category: Prepare and Measure Network Stage|Prepare and Measure Network Stage]]
*''Agreement'': Every non-faulty player outputs the same bit <math>d</math>.
*[[Device Independent Quantum Key Distribution]]:[[:Category:Entanglement Distribution Network stage|Entanglement Distribution Network Stage]]
Device-Independent Quantum Key Distribution (DI-QKD) has better security guarantees than BB84 QKD.
[[Category: Prepare and Measure Network Stage]] [[Category:Entanglement Distribution Network stage]]


==Properties==
*''Validity'': The agreement value <math>d</math> is proposed by at least one node, i.e. <math>d = b_i</math> for some node <math>i</math>.
A quantum key distribution protocol is secure if it is ''correct'' and ''secret''. Correctness is the statement that Sender and Receiver share the same string of bits, namely the secret key, at the end of the protocol. Secrecy is the statement that the eavesdropper is totally ignorant about the final key.  


*'''Correctness''' A QKD protocol is <math>\epsilon_{\rm corr}</math>-correct if the probability that the final key of Sender differs from the final key of Receiver, is smaller than <math>\epsilon_{\rm corr}</math>
*''Termination'': The protocol will eventually terminate.


*'''Secrecy''' A QKD protocol is <math>\epsilon_{\rm sec}</math>-secret if for every input state it holds that
In Byzantine Agreement, node failures are modeled as [[Byzantine Failures]]. In this failure model, the failed nodes are allowed to behave arbitrarily, including maliciously trying to prevent the non-faulty nodes from reaching agreement. In particular, failed nodes can collude together.
<math> \frac{1}{2}{\|{\rho_{K_AE}}-{\tau_{K_A}\otimes \rho_E}\|}_1\leq \epsilon_{\rm sec},</math>
where <math>\tau_{K_A}=\frac{1}{|K_A|}\sum_{k}|{k}\rangle\langle{k}|_A</math> is the maximally mixed state in the space of strings <math>K_A</math>, and <math>{\|\cdot \|}_1</math> is the trace norm.


*A protocol implements a <math>(n,\epsilon_{\rm corr},\epsilon_{\rm sec},\ell)</math>-QKD if with <math>n</math> rounds it generates an <math>\epsilon_{\rm corr}</math>-correct and <math>\epsilon_{\rm sec}</math>-secret key of size <math>\ell</math> bits.


==Further Information==
==Further Information==
The security definition presented here, are proven to be sufficient to guarantee universal composability for standard QKD in (2). For device-independent quantum key distribution, attacks presented in (1) show that security can be compromised if the same devices are used to implement another instance of the protocol.
* Agreement problems are also studied in weaker failure models such as crash-failures.
#[https://arxiv.org/abs/1409.3525 PR (2014)] discusses security of various QKD schemes composed in other cryptographic protocols.
* Byzantine agreement is equivalent to the closely related problems of Byzantine Generals (in which only one player gets an input bit, which must be correctly communicated to all non-faulty players) and Interactive Consistency (in which all non-faulty players must correctly know the received input bit of each non-faulty player).
#[https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.110.010503 BCK (2013)] Analyses device independent QKD
* It is known that no protocol can solve Byzantine Agreement if the number of failures <math> t > n/3</math>.




<div style='text-align: right;'>''*contributed by Bas Dirke, Victoria Lipinska, Glaucia Murta and Jeremy Ribeiro''</div>
<div style='text-align: right;'>''*contributed by Bas Dirke''</div>

Revision as of 14:16, 23 April 2019

Functionality Description

Byzantine agreement is a classical problem concerned with reaching agreement on a single bit of data in a network of players, out of which players may be faulty. Each player starts with an input bit and the objective is that all non-faulty players to output the same bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} (agreement), under the constraint that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = b_i} for some node (validity). The difficulty of this task depends on the failure model of the faulty players. In Byzantine agreement, the faulty players are allowed to behave arbitrarily (including actively breaking the protocol, colluding etc). Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency among distributed data structures.

Tags: Quantum Enhanced Classical Functionality, Multi Party Protocols, Specific Task, consensus task, failure-resilient distributed computing.


Protocols

Properties

A Byzantine Agreement protocol is formally defined to satisfy the criteria agreement, validity and termination. Agreement simply requires every non-faulty player to output the same bit. Validity excludes the trivial solution of always outputting a specific bit, by requiring that the agreement value is at least proposed once. Termination means that any protocol is required to eventually finish. Formally, Byzantine agreement is achieved if

  • Agreement: Every non-faulty player outputs the same bit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} .
  • Validity: The agreement value Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} is proposed by at least one node, i.e. for some node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .
  • Termination: The protocol will eventually terminate.

In Byzantine Agreement, node failures are modeled as Byzantine Failures. In this failure model, the failed nodes are allowed to behave arbitrarily, including maliciously trying to prevent the non-faulty nodes from reaching agreement. In particular, failed nodes can collude together.


Further Information

  • Agreement problems are also studied in weaker failure models such as crash-failures.
  • Byzantine agreement is equivalent to the closely related problems of Byzantine Generals (in which only one player gets an input bit, which must be correctly communicated to all non-faulty players) and Interactive Consistency (in which all non-faulty players must correctly know the received input bit of each non-faulty player).
  • It is known that no protocol can solve Byzantine Agreement if the number of failures .


*contributed by Bas Dirke
Retrieved from "https://wiki.veriqloud.fr/index.php?title=Byzantine_Agreement&oldid=2101"