Quantum Byzantine agreement

Last updated

Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, [1] is described below.

Contents

Introduction

The Byzantine Agreement protocol is a protocol in distributed computing. It takes its name from a problem formulated by Lamport, Shostak and Pease in 1982, [2] which itself is a reference to a historical problem. The Byzantine army was divided into divisions with each division being led by a General with the following properties:

(See [3] for the proof of the impossibility result). The problem usually is equivalently restated in the form of a commanding General and loyal Lieutenants with the General being either loyal or a traitor and the same for the Lieutenants with the following properties.

Byzantine failure and resilience

Failures in an algorithm or protocol can be categorized into three main types:

  1. A failure to take another execution step in the algorithm: This is usually referred to as a "fail stop" fault.
  2. A random failure to execute correctly: This is called a "random fault" or "random Byzantine" fault.
  3. An arbitrary failure where the algorithm fails to execute the steps correctly (usually in a clever way by some adversary to make the whole algorithm fail) which also encompasses the previous two types of faults; this is called a "Byzantine fault".

A Byzantine resilient or Byzantine fault tolerant protocol or algorithm is an algorithm that is robust to all the kinds of failures mentioned above. For example, given a space shuttle with multiple redundant processors, if the processors give conflicting data, which processors or sets of processors should be believed? The solution can be formulated as a Byzantine fault tolerant protocol.

Sketch of the algorithm

We will sketch here the asynchronous algorithm [1] The algorithm works in two phases:

All messages are sent and received in this round.
A coin flipping protocol is a procedure that allows two parties A and B that do not trust each other to toss a coin to win a particular object.

There are two types of coin flipping protocols

Verifiable secret sharing

The fail-stop protocol

Protocol quantum coin flip for player

  1. Round 1 generate the GHZ state on qubits and send the th qubit to the th player keeping one part
  2. Generate the state on qudits (quantum-computing components consistent of multiple qubits), an equal superposition of the numbers between 1 and . Distribute the qudits between all the players [1]
  3. Receive the quantum messages from all players and wait for the next communication round, thus forcing the adversary to choose which messages were passed.
  4. Round 2: Measure (in the standard base) all qubits received in round I. Select the player with the highest leader value (ties broken arbitrarily) as the "leader" of the round. Measure the leader's coin in the standard base.
  5. Set the output of the QuantumCoinFlip protocol: = measurement outcome of the leader's coin.

The Byzantine protocol

To generate a random coin assign an integer in the range [0,n-1] to each player and each player is not allowed to choose its own random ID as each player selects a random number for every other player and distributes this using a verifiable secret sharing scheme.

At the end of this phase players agree on which secrets were properly shared, the secrets are then opened and each player is assigned the value

This requires private information channels so we replace the random secrets by the superposition . In which the state is encoded using a quantum verifiable secret sharing protocol (QVSS). [5] We cannot distribute the state since the bad players can collapse the state. To prevent bad players from doing so we encode the state using the Quantum verifiable secret sharing (QVSS) and send each player their share of the secret. Here again the verification requires Byzantine Agreement, but replacing the agreement by the grade-cast protocol is enough. [6] [7]

Grade-cast protocol

A grade-cast protocol has the following properties using the definitions in [6] Informally, a graded broadcast protocol is a protocol with a designated player called “dealer” (the one who broadcasts) such that:

  1. If the dealer is good, all the players get the same message.
  2. Even if the dealer is bad, if some good player accepts the message, all the good players get the same message (but they may or may not accept it).

A protocol P is said to be achieve graded broadcast if, at the beginning of the protocol, a designated player D (called the dealer) holds a value v, and at the end of the protocol, every player outputs a pair such that the following properties hold:

  1. If D is honest, then = v and = 2 for every honest player .
  2. For any two honest players and .
  3. (Consistency) For any two honest players and , if and , then .

For the verification stage of the QVSS protocol guarantees that for a good dealer the correct state will be encoded, and that for any, possibly faulty dealer, some particular state will be recovered during the recovery stage. We note that for the purpose of our Byzantine quantum coin flip protocol the recovery stage is much simpler. Each player measures his share of the QVSS and sends the classical value to all other players. The verification stage guarantees, with high probability, that in the presence of up to faulty players all the good players will recover the same classical value (which is the same value that would result from a direct measurement of the encoded state).

Remarks

In 2007, a quantum protocol for Byzantine Agreement was demonstrated experimentally [8] using a four-photon polarization-entangled state. This shows that the quantum implementation of classical Byzantine Agreement protocols is indeed feasible.

Related Research Articles

<span class="mw-page-title-main">BQP</span> Computational complexity class of problems

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

In physics, the CHSH inequality can be used in the proof of Bell's theorem, which states that certain consequences of entanglement in quantum mechanics cannot be reproduced by local hidden-variable theories. Experimental verification of the inequality being violated is seen as confirmation that nature cannot be described by such theories. CHSH stands for John Clauser, Michael Horne, Abner Shimony, and Richard Holt, who described it in a much-cited paper published in 1969. They derived the CHSH inequality, which, as with John Stewart Bell's original inequality, is a constraint—on the statistical occurrence of "coincidences" in a Bell test—which is necessarily true if an underlying local hidden-variable theory exists. In practice, the inequality is routinely violated by modern experiments in quantum mechanics.

In computer science, communicating sequential processes (CSP) is a formal language for describing patterns of interaction in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi, based on message passing via channels. CSP was highly influential in the design of the occam programming language and also influenced the design of programming languages such as Limbo, RaftLib, Erlang, Go, Crystal, and Clojure's core.async.

In physics, a partition function describes the statistical properties of a system in thermodynamic equilibrium. Partition functions are functions of the thermodynamic state variables, such as the temperature and volume. Most of the aggregate thermodynamic variables of the system, such as the total energy, free energy, entropy, and pressure, can be expressed in terms of the partition function or its derivatives. The partition function is dimensionless.

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

In physics, the Clebsch–Gordan (CG) coefficients are numbers that arise in angular momentum coupling in quantum mechanics. They appear as the expansion coefficients of total angular momentum eigenstates in an uncoupled tensor product basis. In more mathematical terms, the CG coefficients are used in representation theory, particularly of compact Lie groups, to perform the explicit direct sum decomposition of the tensor product of two irreducible representations. The name derives from the German mathematicians Alfred Clebsch and Paul Gordan, who encountered an equivalent problem in invariant theory.

<span class="mw-page-title-main">Superdense coding</span> Two-bit quantum communication protocol

In quantum information theory, superdense coding is a quantum communication protocol to communicate a number of classical bits of information by only transmitting a smaller number of qubits, under the assumption of sender and receiver pre-sharing an entangled resource. In its simplest form, the protocol involves two parties, often referred to as Alice and Bob in this context, which share a pair of maximally entangled qubits, and allows Alice to transmit two bits to Bob by sending only one qubit. This protocol was first proposed by Charles H. Bennett and Stephen Wiesner in 1970 and experimentally actualized in 1996 by Klaus Mattle, Harald Weinfurter, Paul G. Kwiat and Anton Zeilinger using entangled photon pairs. Superdense coding can be thought of as the opposite of quantum teleportation, in which one transfers one qubit from Alice to Bob by communicating two classical bits, as long as Alice and Bob have a pre-shared Bell pair.

<span class="mw-page-title-main">Greenberger–Horne–Zeilinger state</span> "Highly entangled" quantum state of 3 or more qubits

In physics, in the area of quantum information theory, a Greenberger–Horne–Zeilinger state is a certain type of entangled quantum state that involves at least three subsystems. The four-particle version was first studied by Daniel Greenberger, Michael Horne and Anton Zeilinger in 1989, and the three-particle version was introduced by N. David Mermin in 1990. Extremely non-classical properties of the state have been observed. GHZ states for large numbers of qubits are theorized to give enhanced performance for metrology compared to other qubit superposition states.

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

In cryptography, a secret sharing scheme is publicly verifiable (PVSS) if it is a verifiable secret sharing scheme and if any party can verify the validity of the shares distributed by the dealer.

In verifiable secret sharing (VSS) the object is to resist malicious players, such as
(i) a dealer sending incorrect shares to some or all of the participants, and
(ii) participants submitting incorrect shares during the reconstruction protocol,cf. [CGMA85].
In publicly verifiable secret sharing (PVSS), as introduced by Stadler [Sta96], it is an explicit goal that not just the participants can verify their own shares, but that anybody can verify that the participants received correct shares. Hence, it is explicitly required that (i) can be verified publicly.

In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

In arithmetic, a complex-base system is a positional numeral system whose radix is an imaginary or complex number.

Entanglement distillation is the transformation of N copies of an arbitrary entangled state into some number of approximately pure Bell pairs, using only local operations and classical communication.

The Harrow–Hassidim–Lloyd algorithm or HHL algorithm is a quantum algorithm for numerically solving a system of linear equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

Consider two remote players, connected by a channel, that don't trust each other. The problem of them agreeing on a random bit by exchanging messages over this channel, without relying on any trusted third party, is called the coin flipping problem in cryptography. Quantum coin flipping uses the principles of quantum mechanics to encrypt messages for secure communication. It is a cryptographic primitive which can be used to construct more complex and useful cryptographic protocols, e.g. Quantum Byzantine agreement.

Quantum secret sharing (QSS) is a quantum cryptographic scheme for secure communication that extends beyond simple quantum key distribution. It modifies the classical secret sharing (CSS) scheme by using quantum information and the no-cloning theorem to attain the ultimate security for communications.

This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.

References

  1. 1 2 3 Michael Ben-Or; Avinatan Hassidim (2005). Fast quantum byzantine agreement. STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. Baltimore, MD, USA. pp. 481–485. doi:10.1145/1060590.1060662.
  2. Lamport, Leslie; Shostak, Robert; Pease, Marshall (1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. doi: 10.1145/357172.357176 . ISSN   0164-0925. S2CID   55899582.
  3. Fischer, Michael J.; Lynch, Nancy A.; Paterson, Michael S. (1985). "Impossibility of distributed consensus with one faulty process". Journal of the ACM. 32 (2): 374–382. doi: 10.1145/3149.214121 . ISSN   0004-5411. S2CID   207660233.
  4. Kerenidis, I.; Nayak, A. (2004). "Weak coin flipping with small bias". Information Processing Letters. 89 (3): 131–135. arXiv: quant-ph/0206121 . doi:10.1016/j.ipl.2003.07.007. ISSN   0020-0190. S2CID   14445949.
  5. Crépeau, Claude; Gottesman, Daniel; Smith, Adam (2002). Secure multi-party quantum computation. 34th ACM Symposium on the Theory of Computing, STOC. pp. 643–652. doi:10.1145/509907.510000.
  6. 1 2 Ben-Or, Michael; Pavlov, Elan; Vaikuntanathan, Vinod (2006). "Byzantine agreement in the full-information model in O(log n) rounds". Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. pp. 179–186. CiteSeerX   10.1.1.296.4133 . doi:10.1145/1132516.1132543. ISBN   1595931341. S2CID   6379620.
  7. Feldman, Pesech; Micali, Silvio (1997). "An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement". SIAM Journal on Computing. 26 (4): 873–933. doi:10.1137/S0097539790187084. ISSN   0097-5397.
  8. Gaertner, Sascha; Bourennane, Mohamed; Kurtsiefer, Christian; Cabello, Adán; Weinfurter, Harald (2008). "Experimental Demonstration of a Quantum Protocol for Byzantine Agreement and Liar Detection". Physical Review Letters. 100 (7): 070504. arXiv: 0710.0290 . Bibcode:2008PhRvL.100g0504G. doi:10.1103/PhysRevLett.100.070504. ISSN   0031-9007. PMID   18352533. S2CID   30443015.