Patent AU-2019203850-B2 (AU)
Title: Constructing blockchain world state merkle patricia trie subtree
Inventor: ZHANG WENBIN
IPC: G06F16/22
Filed: 2019-03-04
Granted: 2021-09-16
Abstract: 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 PROP
Not 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 420
ROOT: 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))