Tài liệu An hierarchical deterministic wallet using ed25519 signature schema

VIETNAM NATIONAL UNIVERSITY - HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY FACULTY OF COMPUTER SCIENCE AND ENGINEERING BK TP.HCM BACHELOR OF ENGINEERING THESIS AN HIERARCHICAL DETERMINISTIC WALLET USING ED25519 SIGNATURE SCHEMA COMPUTER SCIENCE COMMITTEE 1 Supervisors: Dr. Nguyen An Khuong. Mr. Phan Son Tu, B.Eng. Examiner: Dr. Nguyen Tien Thinh. Students: Nguyen Nguyen Phuong 1712726 Nguyen Dinh Thang 1752503 Ho Chi Minh City, December 2021 ĈҤ,+Ӑ&48Ӕ&*,$73+&0  75ѬӠ1*ĈҤ,+Ӑ&%È&+.+2$ .+2$ .+ .70i\WtQK %Ӝ0Ð1 .+07 &Ӝ1*+Ñ$;­+Ӝ,&+Ӫ1*+Ƭ$9,ӊ71$0 ĈӝFOұS7ӵGR+ҥQKSK~F 1+,ӊ0 9Ө/8Ұ1È17Ӕ71*+,ӊ3 &K~ê 6LQKYLrQSK̫LGiQWͥQj\YjRWUDQJQK̭WFͯDE̫QWKX\͇WWUuQK +Ӑ9¬7Ç1 1*8<ӈ11*8<Ç13+ѬѪ1* +Ӑ9¬7Ç1 1*8<ӈ1ĈÎ1+7+Ҳ1* 0669  0669  1*¬1+ .+07 /Ӟ3 &/&. ĈҫXÿӅOXұQiQ³$+LHUDUFKLFDO'HWHUPLQLVWLF:DOOHWIRU(G´ 1JKLrQFӭXSKiWWULӇQ YtSKkQFҩS[iFÿӏQKGӵDWUrQOѭӧFÿӗFKӳNt(G 1KLӋPYө\rXFҫXYӅQӝLGXQJYjVӕOLӋXEDQÿҫX 6WXG\HOOLSWLFFXUYHFU\SWRJUDSK\VWXG\(GZDUGVFXUYH'LJLWDO6LJQDWXUH$OJRULWKP (G'6$ 6WXG\EORFNFKDLQWHFKQRORJ\ 6WXG\FU\SWRZDOOHW 'HVLJQ$+LHUDUFKLFDO'HWHUPLQLVWLF:DOOHWIRU(G ,PSOHPHQWDSURWRW\SHRIWKH'HVLJQHG+LHUDUFKLFDO'HWHUPLQLVWLF:DOOHWIRU(G 1Jj\JLDRQKLӋPYөOXұQiQ 1Jj\KRjQWKjQKQKLӋPYө +ӑWrQJLҧQJYLrQKѭӟQJGүQ 3KҫQKѭӟQJGүQ  76 1JX\ӉQ$Q.KѭѫQJ .KRD.+ .70i\WtQK +ѭӟQJGүQNLӃQWKӭFQӅQWҧQJ  .63KDQ6ѫQ7ӵ 'HVFDUWHV1HWZRUN +ѭӟQJGүQNƭWKXұW 1ӝLGXQJYj\rXFҫX/971ÿmÿѭӧFWK{QJTXD%ӝP{Q 1Jj\WKiQJQăP &+Ӫ1+,ӊ0%Ӝ0Ð1 *,Ҧ1*9,Ç1+ѬӞ1*'Ү1&+Ë1+ .êYjJKLU}K͕WrQ .êYjJKLU}K͕WrQ 3*676+XǤQK7ѭӡQJ1JX\rQ 3+̮1'¬1+&+2.+2$%͠0Ð1 1JѭӡLGX\ӋWFKҩPVѫEӝ ĈѫQYӏ 1Jj\EҧRYӋ ĈLӇPWәQJNӃW 1ѫLOѭXWUӳOXұQiQ 1JX\ӉQ$Q.KѭѫQJ 75ѬӠ1*ĈҤ,+Ӑ&%È&+.+2$ .+2$.+ .70È<7Ë1+ &Ӝ1*+Ñ$;­+Ӝ,&+Ӫ1*+Ƭ$ 9,ӊ71$0 ĈӝFOұS7ӵGR+ҥQKSK~F  1Jj\WKiQJQăP 3+,ӂ8&+Ҩ0%Ҧ29ӊ/971 'jQKFKRQJ˱ͥLK˱ͣQJG̳Q +ӑYjWrQ69 1JX\ӉQ1JX\rQ3KѭѫQJ Yj 1JX\ӉQĈuQK 7KҳQJ 0669  Yj  1JjQKFKX\rQQJjQK.+07 ĈӅWjL³$+LHUDUFKLFDO'HWHUPLQLVWLF:DOOHWIRU (G´ 1JKLrQFӭXSKiWWULӇQYtSKkQFҩS[iFÿӏQKGӵDWUrQOѭӧFÿӗFKӳNt(G +ӑWrQQJѭӡLKѭӟQJGүQ 1JX\ӉQ$Q.KѭѫQJ 7әQJTXiWYӅEҧQWKX\ӃWPLQK 6ӕWUDQJ  6ӕFKѭѫQJ  6ӕEҧQJVӕOLӋX 6ӕKuQKYӁ 6ӕWjLOLӋXWKDPNKҧR  3KҫQPӅPWtQKWRiQ +LӋQYұWVҧQSKҭP 7әQJTXiWYӅFiFEҧQYӁ 6ӕEҧQYӁ %ҧQ$ %ҧQ$ .KәNKiF 6ӕEҧQYӁYӁWD\ 6ӕEҧQYӁWUrQPi\WtQK 1KӳQJѭXÿLӇPFKtQKFӫD/971 Ɣ 7KHWKHVLVLVHDV\WRUHDGDOWKRXJKLWLVQRWZHOOZULWWHQWKHDXWKRUVKDYHYHU\JRRG VHOIVWXG\DELOLW\WRFRPSOHWHWKLVGLIILFXOWWKHVLV Ɣ 7KHDXWKRUVKDYHH[FHOOHQWXQGHUVWDQGLQJVRIHOOLSWLFFXUYHFU\SWRJUDSK\DQGEORFNFKDLQ WHFKQRORJ\(VSHFLDOO\WKH\DUHSURILFLHQWLQ6RODQDEORFNFKDLQ Ɣ 7KHDXWKRUVKDYHJRRGHQJLQHHULQJVNLOOVLQGHYHORSLQJEORFNFKDLQUHODWHGV\VWHP Ɣ 7KHV\VWHPLVGHVLJQHGWREHVFDODEOHIRUPDQ\EORFNFKDLQV Ɣ ,PSOHPHQWHGV\VWHPDOUHDG\KDVXVHULQWHUIDFHDQG$3, 1KӳQJWKLӃXVyWFKtQKFӫD/971 Ɣ 7KHV\VWHPLVQRWGHFHQWUDOL]HGHQRXJK Ɣ 7KHWKHVLVKDVQRW\HWLPSOHPHQWHGWKHEDVLFIXQFWLRQVRIDZDOOHWVXFKDVVHQGLQJDQG UHFHLYLQJWRNHQVEXWRQO\KDVWKHIXQFWLRQRIFUHDWLQJZDOOHWVLPSRUWLQJZDOOHWVDQG FKHFNLQJEDODQFH ĈӅQJKӏĈѭӧFEҧRYӋ 䖵 %әVXQJWKrPÿӇEҧRYӋ Ƒ .K{QJÿѭӧFEҧRYӋ Ƒ 0ӝWVӕFkXKӓL69SKҧLWUҧOӡLWUѭӟF+ӝLÿӗQJ D:K\(GZDUGFXUYHVDUHDOVRHOOLSWLFFXUYHVDOWKRXJKWKHLUIRUPVGRQRWFRQWDLQWHUPVRI GHJUHHLQYDULDEH [" E:KDWDUHWKHWUDGHRIIVLIZHXVH,3)6WRUHSODFHWKHFHQWUDOL]HGFOLHQWVHUYHU" F$VZHDUHVWLOOXVLQJVRPHOLEUDULVVXFKDV%,3LPSOHPHQWHGXVLQJ6HFSNGR WKH\HIIHFWRQWKHVHFXULW\RUSHUIRUPDQFHRQ\RXUV\VWHP" ĈiQKJLiFKXQJEҵQJFKӳJLӓLNKi7% *LӓL ĈLӇP .êWrQJKLU}KӑWrQ 1JX\ӉQ$Q.KѭѫQJ 75ѬӠ1*ĈҤ,+Ӑ&%È&+.+2$ KHOA KH & KT MÁY TÍNH &Ӝ1*+Ñ$;­+Ӝ,&+Ӫ1*+Ƭ$ 9,ӊ7 1$0 ĈӝFOұS- 7ӵGR- +ҥQK SK~F ---------------------------Ngày 26 tháng 12 QăP 2021 3+,ӂ8&+Ҩ0 %Ҧ29ӊ/971 'jQKFKRQJ˱ͥLK˱ͣQJG̳QSK̫QEL͏Q +ӑYjWrQ69 - NguyӉQ 1JX\ên PhѭѫQJ (1712726) - NguyӉQ Ĉình ThҳQJ  MSSV: Ngành (chuyên ngành): Khoa hӑF0áy tính ĈӅWjL A hierarchical deterministic wallet for ED25519 +ӑWrQQJѭӡL KѭӟQJ GүQSKҧQ ELӋQ NguyӉQ 7LӃQ 7KӏQK 7әQJ TXiWYӅEҧQ WKX\ӃW PLQK 6ӕWUang: 6ӕFKѭѫQJ 6ӕEҧQJ VӕOLӋX 6ӕKuQK YӁ 6ӕWjL OLӋX WKDP NKҧR 3KҫQ PӅP WtQK WRiQ +LӋQ YұW VҧQSKҭP 7әQJ TXiWYӅFiFEҧQYӁ - 6ӕEҧQYӁ %ҧQ $ %ҧQ $ .KәNKiF - 6ӕEҧQYӁYӁ WD\ 6ӕEҧQYӁWUrQ Pi\ WtQK 1KӳQJ ѭXÿLӇP FKtQK FӫD/971 - The thesis was written coherently. - For the thesis, students studied and developed a prototype of a hierarchical deterministic wallet for ED25519 (a type of elliptic curves that is used in elliptic-curve cryptography, one of the strongest public-key cryptographic system known today), which has not been well developed yet. - Cryptography protocols used for the wallets were discussed carefully in the thesis with full of details. - Students showed excellent comprehension of cryptography and the underlying mathematics as well as good programming skills. 1KӳQJ WKLӃX VyWFKtQK FӫD/971 - Minor typos appear quite frequently in the thesis. - Lack of discussion of the advantages/disadvantages of using HD wallets and the comparison with the currently existing HD wallets. ĈӅQJKӏ ĈѭӧFEҧRYӋ; %әVXQJ WKrP ÿӇEҧRYӋ† FkXKӓL 69SKҧL WUҧOӡL WUѭӟF+ӝL ÿӗQJ .K{QJ ÿѭӧFEҧRYӋ† a. What is the main difference between a HD wallet for SECP256K1 and a HD wallet for ED25519? b. What are the difficulties in adapting BIP32 protocol to the ED25519 case? c. ĈiQK JLi FKXQJ EҵQJ FKӳ JLӓL NKi7% GiӓL ĈLӇP 9.8/10 .êWrQJKL U}KӑWrQ Commitment We commit that the work in this dissertation was carried out following the requirements of the university’s regulations and has not been submitted for any other academic organizations. Except where indicated by specific reference in the text, the works are our own. Ho Chi Minh City, December 2021 Acknowledgement The completion of this study could not have been possible without the guidance and expertise of our supervisors. We would like to express our sincere gratitude to professor Nguyen An Khuong for his patience, motivation, and the immense amount of knowledge he led us to. No matter how many times we let him down because of our unprofessional result, he is still calm and continues to support us. We also want to thank the special supports from Mr. Phan Son Tu, who share with us valuable knowledge about the blockchain industry application while letting us work in his office. Besides that, we would like to show our appreciation to families and friends, who have greatly supported and encouraged us in this thesis and university life. 3 Abstract On the Internet, most of the financial applications apply the public key cryptography to verify users’s identities, manage their digital assets, authenticate and authorize them, etc. In a blockchain environment, this model is crucial to keep the system works, since there are no intermediaries nor the central database for management. However; the user has to keep track of a lot of key pairs for each asset and this is not efficient. To solve this problem, we use an hierarchical deterministic wallet (HD wallet), which can derive hundreds of child wallets from a single master key-pair. Currently, there are already multiple protocols for an HD wallet for Secp256k1 while those for Ed25519 are neither well-known nor well developed. In this thesis, we will try to analyze and build an HD wallet for Ed25519 signature schema. Contents Acknowledgement 1 Abstract 3 List of figures 7 List of tables 9 Chapter 1 INTRODUCTION 1.1 Overview . . . . . . . . . . 1.2 Objectives . . . . . . . . . 1.3 Scope of the study . . . . 1.4 Thesis structure . . . . . . . . . . 11 12 13 13 14 Chapter 2 BACKGROUND 2.1 Blockchain technology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Hierarchical deterministic wallet . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 16 17 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 3 PROTOCOLS AND RELATED WORKS 37 3.1 Related protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Chapter 4 SYSTEM DESIGN 67 4.1 The library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.2 The hierarchical deterministic web wallet . . . . . . . . . . . . . . . . . . . 70 Chapter 5 IMPLEMENTATION 91 5.1 The library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.2 The hierarchical deterministic web wallet . . . . . . . . . . . . . . . . . . . 95 Chapter 6 TESTING 109 6.1 The library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.2 The hierarchical deterministic web wallet . . . . . . . . . . . . . . . . . . . 114 Chapter 7 CONCLUSION AND DISCUSSION 7.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography 117 . 118 . 118 . 119 121 List of Figures 2.1 2.2 Montgomery ladder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Hash function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 Example of BIP32 key tree with depth 3 . . . . . . Example of the extended private key . . . . . . . . Master Extended Key generation Process . . . . . . Normal Extended Private Key generation process . Normal Extended Public Key generation process . . Hardened Extended Private Key generation process Relation in BIP32 normal derivation protocol . . . Master Extended Key generation Process . . . . . . Hardened Extended Public Key generation process Multiply process of Ed25519 . . . . . . . . . . . . . Master key generation process . . . . . . . . . . . . Private keypair derivation process . . . . . . . . . . Public keypair derivation process . . . . . . . . . . Random secret seed generation process . . . . . . . Example path of BIP44 . . . . . . . . . . . . . . . . Example tree of wallets from given path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 40 42 43 45 46 49 51 53 54 56 58 59 62 62 63 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 General library structure . . . . . . . . Testcase components . . . . . . . . . . Example of web wallet flow . . . . . . HD web wallet tree . . . . . . . . . . . Between users and Wallet provider . . Between users and blockchain networks Between users and Address service . . Request Data . . . . . . . . . . . . . . General JSON object of a Wallet . . . Usecase diagram . . . . . . . . . . . . Homepage design . . . . . . . . . . . . Create mnemonic . . . . . . . . . . . . Import mnemonic . . . . . . . . . . . . Main page . . . . . . . . . . . . . . . . List functionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 69 70 72 74 75 75 76 76 78 87 88 88 89 89 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 Typescript library structure . . . . . . . . . . . . COMPONENTS JSON example . . . . . . . . . . Different implementation in Montgomery Ladder . Overview of entire system . . . . . . . . . . . . . Homepage . . . . . . . . . . . . . . . . . . . . . . Create wallet page . . . . . . . . . . . . . . . . . Import wallet page . . . . . . . . . . . . . . . . . Wallet page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 94 94 96 103 104 105 106 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 LIST OF FIGURES 5.9 Transaction and search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.10 Delete wallet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.1 6.2 6.3 6.4 6.5 6.6 Testcase results with mocha . . . . . Test airdrop with Solana . . . . . . . Test balance with Solana . . . . . . . Test transaction with Solana . . . . . Transaction detail on Solana Explorer Coins transfered details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 112 112 112 113 113 List of Tables 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 Use case list . . . . . . . . . . . . Use case: Create new wallet. . . . Create new child wallet. . . . . . Delete wallet from the browser. . Search address. . . . . . . . . . . Modify addresses in the database. Make transaction. . . . . . . . . . Import wallet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 80 81 82 83 84 85 86 1 Introduction In this chapter, we are going to discuss the overview of the wallet we are creating. Thus, we are going to present the objectives, scope, and structure of this thesis. Contents 1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Scope of the study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Thesis structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 12 1.1 CHAPTER 1 Overview At the moment, blockchain is a robust trend in financial technology. Blockchain is atechnology that enables truthless digital currencies transaction without intermediaries. It helps to prevent the double-spending and solve the censorship problem in traditional finance. Similar to a transaction in a bank, you need to sign it to provide the proof of identity. In the blockchain system, you use a digital signatures schema. The private key is kept private and used to sign the transaction, while the public key is accessible by everyone, used to verify the signature. The sender can also use your public key as a public address to send cryptocurrency. The pair of keys is preserved and managed by using a cryptocurrency wallet, or crypto wallet for short. Some people may call it a digital wallet, but that is not entirely correct. A digital wallet (e-wallet) such as Momo and Paypal can hold users’s digital assets (government-issued currency) and link to their credit/debit cards. The banks apply the online banking service and allow the digital wallet to connect to users’s accounts, which means users are required to sign up the service first to use a digital wallet and they have to transfer indirectly through the banking system. On the other hand, crypto wallet has access to users’s crypto assets, and can help them to transfer cryptocurrencies directly because the blockchain system does not required a trusted third party nor any intermediary. All the transfer process takes in terms of minutes, no matter how far it is from you to the receiver. With some lightning-fast consensus like the Proof of History blockchain, it took less than 10 seconds. In the case of digital wallets or bank accounts, you have to wait for days before your transaction is confirmed, and it even worse when you decide to transfer to another country/state or cross-bank. The bank does have a solution for this problem (NAPAS, Visa, MasterCard,...) but you have to pay an extra fee for the service no matter how much you spend. That is why rather than the traditional stock markets, people are more likely to invest in the decentralized system since they have to stay home due to the COVID pandemic. The cryptocurrency still has some more advantages to traditional finance, but for the scope of our thesis, we won’t include them here. Another difference is that, crypto wallet does not hold any of users’s private information such as phone number, name, ID card, etc (also know as KYC). Therefore; users’s information is protected and will not be leaked even if the crypto wallet got hacked. In practical, the investors do not invest in a single market. They love to split their funds and put their money into multiple projects because one of the famous investment rule is “Don’t put all your eggs in one basket”. However; a crypto wallet creates a different key pair to sign for each transaction and each crypto wallet is connect to only one platform. The users have to create multiple wallet for each market, and they have to keep track of the used key pairs for both backing up and avoiding key leakage. This is inconvenience for both advanced users and investors since hundreds of transactions are made and hundreds of markets launch per day. Also, crypto wallet or digital wallet, they are still online applications that rely on the Internet. An advanced user acknowledges that the blockchain system and the internet is not a safe place. Both of the wallets are vulnerable to common attacks such as man-in-themiddle attack, phishing, social engineering, and more. These attacks are hard to prevent because they focus on the human factor: the users’s awareness. In addition, blockchain