Framework and algorithms for identifying honest blocks in blockchain

English version

Autoři: Xu Wang ^aff001; Guohua Gan ^aff003; Ling-Yun Wu ^aff001
Působiště autorů: Key Laboratory of Management, Decision and Information Systems, Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China ^aff001; School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China ^aff002; Laboratory of Big Data and Blockchain, National Center for Mathematics and Interdisciplinary Sciences, Chinese Academy of Sciences, Beijing, China ^aff003; Beijing Taiyiyun Technology Co., Ltd., Beijing, China ^aff004; University of Science & Technology Beijing, Beijing, China ^aff005
Vyšlo v časopise: PLoS ONE 15(1)
Kategorie: Research Article
prolekare.web.journal.doi_sk: https://doi.org/10.1371/journal.pone.0227531

Souhrn

Blockchain technology gains more and more attention in the past decades and has been applied in many areas. The main bottleneck for the development and application of blockchain is its limited scalability. Blockchain with directed acyclic graph structure (BlockDAG) is proposed in order to alleviate the scalability problem. One of the key technical problems in BlockDAG is the identification of honest blocks which are very important for establishing a stable and invulnerable total order of all the blocks. The stability and security of BlockDAG largely depends on the precision of honest block identification. This paper presents a novel universal framework based on graph theory, called MaxCord, for identifying the honest blocks in BlockDAG. By introducing the concept of discord, the honest block identification is modelled as a generalized maximum independent set problem. Several algorithms are developed, including exact, greedy and iterative filtering algorithms. The extensive comparisons between proposed algorithms and the existing method were conducted on the simulated BlockDAG data to show that the proposed iterative filtering algorithm identifies the honest blocks both efficiently and effectively. The proposed MaxCord framework and algorithms can set the solid foundation for the BlockDAG technology.

Klíčová slova:

Data management – Markov models – Algorithms – Finance – Internet – Valleys – Graph theory – Directed acyclic graphs

Zdroje

1. Nakamoto S. Bitcoin: A peer-to-peer electronic cash system. 2008. Available from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.221.9986&rep=rep1&type=pdf

2. Iansiti M, Lakhani K R. The truth about blockchain. Harv Bus Rev. 2017; 95:118–127.

3. Crosby M, Nachiappan, Pattanayak P, Verma S, Kalyanaraman V. Blockchain technology: Beyond bitcoin. Applied Innovation. 2016; 2(6–10):71.

4. Bahga A, Madisetti V K. Blockchain platform for industrial internet of things. Journal of Software Engineering and Applications. 2016; 9(10):533.

5. Huh S, Cho S, Kim S. Managing IoT devices using blockchain platform. 19th international conference on advanced communication technology (ICACT), IEEE. 2017:464–467.

6. Zhang Y, Wen J. The IoT electric business model: Using blockchain technology for the internet of things. Peer Peer Netw Appl. 2017; 10(4):983–994.

7. Reyna A, Martín C, Chen J, Soler M, Diaz M. On blockchain and its integration with IoT Challenges and opportunities. Future Gener Comput Syst. 2018; 88:173–190.

8. Mettler M. Blockchain technology in healthcare: The revolution starts here. 18th International Conference on e-Health Networking, Applications and Services (Healthcom), IEEE. 2016:1–3.

9. Treleaven P, Brown R G, Yang D. Blockchain technology in finance. Computer. 2017; 50(9): 14–17.

10. Tapscott A, Tapscott D. How blockchain is changing finance. Harv Bus Rev. 2017; 1(9):2–5.

11. Kristoufek L. What are the main drivers of the Bitcoin price? Evidence from wavelet coherence analysis. PLoS ONE. 2015; 10(4):e0123923. doi: 10.1371/journal.pone.0123923 25874694

12. Kim Y B, Lee J, Park N, Choo J, Kim J, Kim CH. When Bitcoin encounters information in an online forum: Using text mining to analyse user opinions and predict value fluctuation. PLoS ONE. 2017; 12(5):e0177630. doi: 10.1371/journal.pone.0177630 28498843

13. Apte S, Petrovsky N. Will blockchain technology revolutionize excipient supply chain management? Journal of Excipients and Food Chemicals. 2016; 7(3):910.

14. Swan M. Blockchain: Blueprint for a new economy. O'Reilly Media, Inc; 2015.

15. Yli-Huumo J, Ko D, Choi S, Park S, Smolander K. Where is current research on blockchain technology?—a systematic review. PLoS ONE. 2016; 11(10):e0163477. doi: 10.1371/journal.pone.0163477 27695049

16. Zheng Z, Xie S, Dai H N, Chen X, Wang H. Blockchain challenges and opportunities: A survey. International Journal of Web and Grid Services. 2018; 14(4):352–375.

17. Li X, Jiang P, Chen T, Luo X, Wen Q. A survey on the security of blockchain systems. Future Gener Comput Syst. 2017.

18. Feng Q, He D, Zeadally S, Khan MK, Kumar N. A survey on privacy protection in blockchain system. Journal of Network and Computer Applications. 2019; 126:45–58.

19. Juhász P L, Stéger J, Kondor D, Vattay G. A Bayesian approach to identify Bitcoin users. PLoS ONE. 2018; 13(12):e0207000. doi: 10.1371/journal.pone.0207000 30543629

20. Nguyen G T, Kim K. A Survey about Consensus Algorithms Used in Blockchain. Journal of Information processing systems. 2018; 14(1).

21. Lin I C, Liao T C. A Survey of Blockchain Security Issues and Challenges. IJ Network Security. 2017, 19(5):653–659.

22. Decker C, Wattenhofer R. Information propagation in the bitcoin network. IEEE Thirteenth International Conference on P2P Computing. 2013:1–10.

23. Biais B, Bisiere C, Bouvard M, Casamatta C. The blockchain folk theorem. The Review of Financial Studies. 2019, 32(5):1662–1715.

24. Sompolinsky Y, Zohar A. Secure high-rate transaction processing in bitcoin. International Conference on Financial Cryptography and Data Security, Springer, Berlin, Heidelberg. 2015:507–527.

25. Lewenberg Y, Sompolinsky Y, Zohar A. Inclusive block chain protocols. International Conference on Financial Cryptography and Data Security, Springer, Berlin, Heidelberg. 2015:528–547.

26. Popov Serguei. The tangle. 2016. Available from: https://www.iota-wiki.com/download/iota_whitepaper.pdf

27. Pervez H, Muneeb M, Irfan MU, Haq IU. A comparative analysis of DAG-based blockchain architectures. 12th International Conference on Open Source Systems and Technologies, IEEE. 2018:27–34.

28. Bai Chong. State-of-the-art and future trends on blockchain based on DAG structure. International workshop on structured object-oriented formal language and method, Springer, Cham. 2018:183–196.

29. Sompolinsky Y, Zohar A. PHANTOM: A scalable block DAG protocol. IACR Cryptology ePrint Archive, Report. 2018, 104.

30. Tarjan R E, Trojanowski A E. Finding a maximum independent set. SIAM J Sci Comput. 1977; 6(3):537–546.

31. Feo T A, Resende M G C, Smith S H. A greedy randomized adaptive search procedure for maximum independent set. Operations Research. 1994; 42(5):860–878.

32. Xiao M, Nagamochi H. An exact algorithm for maximum independent set in degree-5 graphs. Discrete Applied Mathematics. 2016; 199:137–155.

33. Tsukiyama S, Ide M, Ariyoshi H, Shirakawa I. A new algorithm for generating all the maximal independent sets. SIAM J Sci Comput. 1977; 6(3):505–517.

Framework and algorithms for identifying honest blocks in blockchain

Souhrn

Klíčová slova:

Zdroje

PLOS One

Aktuální možnosti diagnostiky a léčby litiáz