Quantum Byzantine agreement in blockchain: protocol, application and outlook

doi:10.12267/j.issn.2096-5931.2024.07.008

Abstract

Abstract:

Blockchain technology ensures data security, integrity, and traceability through decentralization and distributed databases, with core components including distributed ledgers, encryption technology, and consensus mechanisms. The Byzantine agreement protocol, as a key component, is crucial for maintaining the security and consistency of decentralized networks. However, the rapid development of quantum computing threatens the security of classical Byzantine agreement protocols and their inability to surpass the 1/3 fault tolerance bound, making the study of quantum Byzantine agreement protocols necessary. This paper discusses the challenges faced by classical Byzantine agreement protocols in the quantum computing era and introduces the development and practical challenges of detectable quantum Byzantine agreement. It focuses on the recently proposed new quantum Byzantine consensus protocol based on quantum digital signatures, which breaks the 1/3 fault-tolerance bound, offers information-theoretic security, and is experimentally feasible. Finally, it discusses the constraints of the blockchain trilemma on Byzantine agreement and looks forward to the development of quantum Byzantine agreement protocols and their prospects for decentralized communication and computation in quantum networks.

Key words: quantum Byzantine agreement, quantum digital signatures, quantum multiparty correlation, 1/3 fault-tolerance bound, quantum blockchain

CLC Number:

WENG Chenxun, LI Mingyang, YIN Hualei, CHEN Zengbing. Quantum Byzantine agreement in blockchain: protocol, application and outlook[J]. Information and Communications Technology and Policy, 2024, 50(7): 59-68.

Add to citation manager EndNote|Ris|BibTeX

URL:

http://ictp.caict.ac.cn/EN/10.12267/j.issn.2096-5931.2024.07.008

http://ictp.caict.ac.cn/EN/Y2024/V50/I7/59

Figures/Tables 5

References 49

[1]	LAMPORT L, SHOSTAK R, PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.
[2]	CASTRO M, LISKOV B. Practical Byzantine fault tolerance[C]// Proceedings of the Third Symposium on Operating Systems Design and Implementation. New Orleans: OsDI, 1999: 173-186.
[3]	CASTRO M, LISKOV B. Practical Byzantine fault tolerance and proactive recovery[J]. ACM Transactions on Computer Systems, 2002, 20(4): 398-461.
[4]	AUBLIN P-L, MOKHTAR S B, QUEMA V. RBFT: redundant Byzantine fault tolerance[C/OL]// 2013 IEEE 33rd International Conference on Distributed Computing Systems. Philadelphia, PA, USA: IEEE, 2013: 297-306[2024-06-03]. http://ieeexplore.ieee.org/document/6681599/.
[5]	MILLER A, XIA Y, CROMAN K, et al. The honey badger of BFT protocols[C/OL]// Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. Vienna Austria: ACM, 2016: 31-42[2024-06-03]. https://dl.acm.org/doi/10.1145/2976749.2978399.
[6]	YIN M, MALKHI D, REITER M K, et al. HotStuff: BFT consensus with linearity and responsiveness[C/OL]// Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. Toronto ON Canada: ACM, 2019: 347-356[2024-06-03]. https://dl.acm.org/doi/10.1145/3293611.3331591.
[7]	GUO B, LU Z, TANG Q, et al. Dumbo: faster asynchronous BFT protocols[C/OL]// Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Virtual Event USA: ACM, 2020: 803-818[2024-06-03]. https://dl.acm.org/doi/10.1145/3372297.3417262.
[8]	LU Y, LU Z, TANG Q, et al. Dumbo-MVBA: optimal multi-valued validated asynchronous Byzantine agreement, revisited[C/OL]// Proceedings of the 39th Symposium on Principles of Distributed Computing. Virtual Event Italy: ACM, 2020: 129-138[2024-06-03]. https://dl.acm.org/doi/10.1145/3382734.3405707.
[9]	PEASE M, SHOSTAK R, LAMPORT L. Reaching agreement in the presence of faults[J]. Journal of the ACM, 1980, 27(2): 228-234.
[10]	FISCHER M J, LYNCH N A, MERRITT M. Easy impossibility proofs for distributed consensus problems[J]. Distributed Computing, 1986, 1(1): 26-39.
[11]	KIKTENKO E O, POZHAR N O, ANUFRIEV M N, et al. Quantum-secured blockchain[J]. Quantum Science and Technology, 2018, 3(3): 035004.
[12]	SHOR P W. Algorithms for quantum computation: discrete logarithms and factoring[C/OL]// Proceedings 35th Annual Symposium on Foundations of Computer Science. Santa Fe, NM, USA: IEEE Computer Society Press, 1994: 124-134[2024-06-03]. http://ieeexplore.ieee.org/document/365700/.
[13]	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509.
[14]	O’BRIEN J L. Optical quantum computing[J]. Science, 2007, 318(5856): 1567-1570. pmid: 18063781
[15]	FEDOROV A K, KIKTENKO E O, LVOVSKY A I. Quantum computers put blockchain security at risk[J]. Nature, 2018, 563(7732): 465-467.
[16]	ARUTE F, ARYA K, BABBUSH R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, 2019, 574(7779): 505-510.
[17]	FITZI M, GISIN N, MAURER U. Quantum solution to the Byzantine agreement problem[J]. Physical Review Letters, 2001, 87(21): 217901.
[18]	GAERTNER S, BOURENNANE M, KURTSIEFER C, et al. Experimental demonstration of a quantum protocol for Byzantine agreement and liar detection[J]. Physical Review Letters, 2008, 100(7): 070504.
[19]	NEIGOVZEN R, RODÓ C, ADESSO G, et al. Multipartite continuous-variable solution for the Byzantine agreement problem[J]. Physical Review A, 2008, 77(6): 062307.
[20]	RAHAMAN R, WIEŚNIAK M, ŻUKOWSKI M, Quantum Byzantine agreement via hardy correlations and entanglement swapping[J]. Physical Review A, 2015, 92(4): 042302.
[21]	TAVAKOLI A, CABELLO A, ŻUKOWSKI M, et al. Quantum clock synchronization with a single qudit[J]. Scientific Reports, 2015, 5(1): 7982.
[22]	SMANIA M, ELHASSAN A M, TAVAKOLI A, et al. Experimental quantum multiparty communication protocols[J]. Npj Quantum Information, 2016, 2(1): 16010.
[23]	SUN X, KULICKI P, SOPEK M. Multi-party quantum Byzantine agreement without entanglement: 10[J]. Entropy, 2020, 22(10): 1152.
[24]	BEN-OR M, HASSIDIM A. Fast quantum Byzantine agreement[C/OL]// Proceedings of the Thirty-seventh annual ACM symposium on Theory of Computing. Baltimore MD USA: ACM, 2005: 481-485[2024-06-03]. https://dl.acm.org/doi/10.1145/1060590.1060662.
[25]	GOTTESMAN D, CHUANG I. Quantum digital signatures[J]. arXiv Preprint, arXiv: quant-ph/0105032, 2001.
[26]	CLARKE P J, COLLINS R J, DUNJKO V, et al. Experimental demonstration of quantum digital signatures using phase-encoded coherent states of light[J]. Nature Communications, 2012, 3(1): 1174.
[27]	DUNJKO V, WALLDEN P, ANDERSSON E. Quantum digital signatures without quantum memory[J]. Physical Review Letters, 2014, 112(4): 040502.
[28]	COLLINS R J, DONALDSON R J, DUNJKO V, et al. Realization of quantum digital signatures without the requirement of quantum memory[J]. Physical Review Letters, 2014, 113(4): 040502.
[29]	CROAL C, PEUNTINGER C, HEIM B. Free-space quantum signatures using heterodyne measurements[J]. Physical Review Letters, 2016, 117(10): 100503.
[30]	YIN H L, FU Y, CHEN Z B. Practical quantum digital signature[J]. Physical Review A, 2016, 93(3): 032316.
[31]	AMIRI R, WALLDEN P, KENT A, et al. Secure quantum signatures using insecure quantum channels[J]. Physical Review A, 2016, 93(3): 032325.
[32]	AN X B, ZHANG H, ZHANG C M, et al. Practical quantum digital signature with a gigahertz BB84 quantum key distribution system[J]. Optics Letters, 2019, 44(1): 139-142.
[33]	T HORNTON M, SCOTT H, CROAL C, et al. Continuous-variable quantum digital signatures over insecure channels[J]. Physical Review A, 2019, 99(3): 032341.
[34]	RICHTER S, THORNTON M, KHAN I, et al. Agile and versatile quantum communication: signatures and secrets[J]. Physical Review X, 2021, 11(1): 011038.
[35]	ZHAO W, SHI R, SHI J, et al. Multibit quantum digital signature with continuous variables using basis encoding over insecure channels[J]. Physical Review A, 2021, 103(1): 012410.
[36]	PUTHOOR I V, AMIRI R, WALLDEN P, et al. Measurement-device-independent quantum digital signatures[J]. Physical Review A, 2016, 94(2): 022328.
[37]	YIN H L, FU Y, LIU H, et al. Experimental quantum digital signature over 102 km[J]. Physical Review A, 2017, 95(3): 032334.
[38]	ROBERTS G L, LUCAMARINI M, YUAN Z L, et al. Experimental measurement-device-independent quantum digital signatures[J]. Nature Communications, 2017, 8(1): 1098.
[39]	ZHANG C H, ZHOU X, ZHANG C M, et al. Twin-field quantum digital signatures[J]. Optics Letters, 2021, 46(15): 3757-3760.
[40]	LU Y S, CAO X Y, WENG C X, et al. Efficient quantum digital signatures without symmetrization step[J]. Optics Express, 2021, 29(7): 10162-10171.
[41]	WENG C X, LU Y S, GAO R Q, et al. Secure and practical multiparty quantum digital signatures[J]. Optics Express, 2021, 29(17): 27661-27673.
[42]	YIN H L, FU Y, LI C L, et al. Experimental quantum secure network with digital signatures and encryption[J]. National Science Review, 2023, 10(4): nwac228.
[43]	LI B H, XIE Y M, CAO X Y, et al. One-time universal hashing quantum digital signatures without perfect keys[J]. Physical Review Applied, 2023, 20(4): 044011.
[44]	WENG C X, GAO R Q, BAO Y, et al. Beating the fault-tolerance bound and security loopholes for Byzantine agreement with a quantum solution[J]. Research, 2023, 6: 0272.
[45]	YIN H L, LIU P, DAI W W, et al. Experimental composable security decoy-state quantum key distribution using time-phase encoding[J]. Optics Express, 2020, 28(20): 29479-29485.
[46]	WALLDEN P, DUNJKO V, KENT A, et al. Quantum digital signatures with quantum-key-distribution components[J]. Physical Review A, 2015, 91(4): 042304.
[47]	ZHOU Q, HUANG H, ZHENG Z, et al. Solutions to scalability of blockchain: a survey[J]. IEEE Access, 2020, 8: 16440-16455.
[48]	JING X, QIAN C, WENG C X, et al. Experimental quantum Byzantine agreement on a three-user quantum network with integrated photonics[J]. arXiv Preprint, arXiv: 2403.11441, 2024.
[49]	PAING S N, SETIAWAN J W, ULLAH M A, et al. Counterfactual quantum Byzantine consensus for human-centric metaverse[J]. IEEE Journal on Selected Areas in Communications, 2024, 42(4): 905-918.

协议类型	检测量子拜占庭共识协议	基于QDS的量子拜占庭共识协议
安全性分析	未提供	提供
容错能力	仅限三方共识	n≥2f+1, ∀f∈N⁺
消息类型	单比特	多比特
实验资源	多粒子纠缠态或高维量子比特	弱相干态
是否需要额外假设	是	否

协议类型	检测量子拜占庭共识协议	基于QDS的量子拜占庭共识协议
安全性分析	未提供	提供
容错能力	仅限三方共识	n≥2f+1, ∀f∈N⁺
消息类型	单比特	多比特
实验资源	多粒子纠缠态或高维量子比特	弱相干态
是否需要额外假设	是	否