Constructing blockchain world state merkle patricia trie subtree

摘要

#$%^&*AU2019203850A120200917.pdf#####(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT) (19) World Intellectual Property (1) Organization11111111111111111111111I111111111111li1111iiiiii International Bureau (10) International Publication Number (43) International Publication Date W O 2019/101230 A2 31 May 2019 (31.05.2019) W IPO I PCT (51) International Patent Classification: (74) Agent: BEIJING BESTIPR INTELLECTUAL PROPNot classified ERTY LAW CORPORATION; Room 409, Tower B, Ka (21) International Application Number: Wah Building, No. 9 Shangdi 3rd Street, Haidian District, PCT/CN2019/076814 Beijing 100085 (CN). (22) International Filing Date: (81) Designated States (unless otherwise indicated, for every 04 March 2019 (04.03.2019) kind ofnational protection available): AE, AG, AL, AM, AO, AT, AU, AZ, BA, BB, BG, BH, BN, BR, BW, BY, BZ, (25) Filing Language: English CA, CH, CL, CN, CO, CR, CU, CZ, DE, DJ, DK, DM, DO, DZ, EC, EE, EG, ES, FI, GB, GD, GE, GH, GM, GT, HN, (26)PublicationLanguage: English HR, HU, ID, IL, IN, IR, IS, JO, JP, KE, KG, KH, KN, KP, (71) Applicant: ALIBABA GROUP HOLDING LIMITED KR, KW, KZ, LA, LC, LK, LR, LS, LU, LY, MA, MD, ME, [-/CN]; Fourth Floor, One Capital Place, P.O. Box 847, MG, MK, MN, MW, MX, MY, MZ, NA, NG, NI, NO, NZ, George Town, Grand Cayman (KY). OM, PA, PE, PG, PH, PL, PT, QA, RO, RS, RU, RW, SA, SC, SD, SE, SG, SK, SL, SM, ST, SVSY, TH, TJ, TM, TN, (72) Inventor: ZHANG, Wenbin; Alibaba Group Legal De- TR, TT, TZ,UA, UG, US, UZ, VC, VN, ZA, ZM, ZW. partment 5/F, Building 3, No. 969 West Wen Yi Road, Yuhang District, Hangzhou, Zhejiang 311121 (CN). (84) Designated States (unless otherwise indicated, for every kind of regional protection available): ARIPO (BW, GH, GM, KE, LR, LS, MW, MZ, NA, RW, SD, SL, ST, SZ, TZ, (54) Title: CONSTRUCTING BLOCKCHAIN WORLD STATE MERLE PATRICIA TRIE SUBTREE F402 420ROOT: Extension Node Keys Values 4O0 prefx shared nibble(s) next node a71 1 355 45.0 ETH 422 0 a7 7 7d 33 O7 100 WEl 424 Branch Node 404 0112131415167 893abcde f au 410 Leaf Node Extension Node 408 prefix shared nibble(s) value prefix shared nibble(s) nextnode - [j 1355 5. ETH 0 d3 Branch Node 406 0 1 2 3 4 5 6 7 8 91 al b c dl el f Ivalue 412 Leaf Node preix shared nibble(s) I value 3 7 _1.00 WVE FIG. 4 O (57) Abstract: Implementations of this specification include traversing a world-state MPT in multiple iterations, and, at each iteration, for a current node of the world-state MPT, executing one of: marking the current node as an account node and storing an address of the current node in the address list, determining that the current node is an extension node, and moving to a next iteration of the traversal O setting the current node to a node referenced by the extension node, and marking the current node as a transition node, and storing an address of the current node in the address list; creating a sub-tree of the world-state MPT based on the address list, a root node of the sub-tree including a root node of the world-state MPT, and one or more child nodes of the sub-tree corresponding to nodes of the world-state MPT having an address stored in the address list.W O 20 19/10 123 0 A 2 ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| UG, ZM, ZW), Eurasian (AM, AZ, BY, KG, KZ, RU, TJ, TM), European (AL, AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, Fl, FR, GB, GR, HR, HU, IE, IS, IT, LT, LU, LV, MC, MK, MT, NL, NO, PL, PT, RO, RS, SE, SI, SK, SM, TR), OAPI (BF, BJ, CF, CG, CI, CM, GA, GN, GQ, GW, KM, ML, MR, NE, SN, TD, TG). Published: - upon request of the applicant, before the expiration of the time limit referred to in Article 2](2)(a) - without international search report and to be republished upon receipt of that report (Rule 48.2(g))