Patent SG-11201908944W-A (SG)
Title: Constructing blockchain world state merkle patricia trie subtree
Inventor: ZHANG WENBIN
Filed: 2019-03-04
Abstract: 1 2 3 4 6 8 9 d value 5 7 a e ROOT: Extension Node prefix shared nibble(s) next node 0 a7 404 Values 45.0 ETH 1.00 WEI Keys a a 7 7 7 1 1 3 3 3 5 5 7 Branch Node Branch Node 0111MI0IIIM00E0'I0'E0EEI 11P1111111111111- 424 1422 406 (12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT) (19) World Intellectual Property Organization International Bureau (43) International Publication Date 31 May 2019 (31.05.2019) WIPO I PCT 11111111111110111111111111111101111101011111111111110111111111111111011111011110111111 (10) International Publication Number WO 2019/101230 A2 400 — c 410 (51) International Patent Classification: Not classified (21) International Application Number: PCT/CN2019/076814 (22) International Filing Date: 04 March 2019 (04.03.2019) (25) Filing Language: English (26) Publication Language: English (71) Applicant: ALIBABA GROUP HOLDING LIMITED [—/CN]; Fourth Floor, One Capital Place, P.O. Box 847, George Town, Grand Cayman (KY). (72) Inventor: ZHANG, Wenbin; Alibaba Group Legal De- partment 5/F, Building 3, No. 969 West Wen Yi Road, Yuhang District, Hangzhou, Zhejiang 311121 (CN). (74) Agent: BEIJING BESTIPR INTELLECTUAL PROP- ERTY LAW CORPORATION; Room 409, Tower B, Ka With Building, No. 9 Shangdi 3rd Street, Haidian District, Beijing 100085 (CN). (81) Designated States (unless otherwise indicated, for every kind of national protection available): AE, AG, AL, AM, AO, AT, AU, AZ, BA, BB, BG, BH, BN, BR, BW, BY, BZ, 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, HR, HU, ID, IL, IN, IR, IS, JO, JP, KE, KG, KH, KN, KP, KR, KW, KZ, LA, LC, LK, LR, LS, LU, LY, MA, MD, ME, MG, MK, MN, MW, MX, MY, MZ, NA, NG, NI, NO, NZ, OM, PA, PE, PG, PH, PL, PT, QA, RO, RS, RU, RW, SA, SC, SD, SE, SG, SK, SL, SM, ST, SV, SY, TH, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ, VC, VN, ZA, ZM, ZW. (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 MERKLE PATRICIA TRIE SUBTREE 402 420 Leaf Node prefix shared rubble(s) value 2 1355 45.0 ETH Extension Node prefix shared nibble(s) next node 0 d3 — 406 O M O ON O C Leaf Node prefix shared nibble(s) value 3 7 1.00 WE FIG. 4 (57) : 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 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. [Continued on next page] 412 WO 2019/101230 x2111111I 011111 H 111111 011111111011111010111 OIH 111110111 DIII 01 11 0 INIEMIE UG, ZM, ZW), Eurasian (AM, AZ, BY, KG, KZ, RU, TJ, TM), European (AL, AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI, 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 21(2)(a) without international search report and to be republished upon receipt of that report (Rule 48.2(g))