package Ġnet . cord a . core . crypto Ċ Ċ import Ġnet . cord a . core . crypto . Secure Hash . Companion . zero Hash Ċ import Ġnet . cord a . core . serialization . C ord a Serializable Ċ import Ġjava . util .* Ċ Ċ @ C ord a Serializable Ċ class ĠMer kle Tree Exception ( val Ġreason : ĠString ) Ġ: ĠException () Ġ{ ĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġ" Partial ĠMer kle ĠTree Ġexception . ĠReason : Ġ$ reason " Ċ } Ċ Ċ /** Ċ Ġ* ĠBuilding Ġand Ġverification Ġof ĠPartial ĠMer kle ĠTree . Ċ Ġ* ĠPartial ĠMer kle ĠTree Ġis Ġa Ġminimal Ġtree Ġneeded Ġto Ġcheck Ġthat Ġa Ġgiven Ġset Ġof Ġleaves Ġbelongs Ġto Ġa Ġfull ĠMer kle ĠTree . Ċ Ġ* Ċ Ġ* ĠExample Ġof ĠMer kle Ġtree Ġwith Ġ 5 Ġleaves . Ċ Ġ* Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠ Ġh 1 5 Ċ Ġ* ĠĠĠĠĠĠĠĠĠ Ġ/ ĠĠĠĠĠĠ Ġ\ Ċ Ġ* ĠĠĠĠĠĠĠĠ Ġh 1 4 ĠĠĠĠĠĠ Ġh 5 5 Ċ Ġ* ĠĠĠĠĠĠĠ Ġ/ Ġ Ġ\ ĠĠĠĠĠ Ġ/ Ġ Ġ\ Ċ Ġ* ĠĠĠĠĠ Ġh 1 2 Ġ Ġh 3 4 ĠĠ Ġh 5 0 Ġh 0 0 Ċ Ġ* ĠĠĠĠ Ġ/ Ġ\ ĠĠ Ġ/ Ġ\ ĠĠ Ġ/ Ġ\ Ġ Ġ/ Ġ\ Ċ Ġ* ĠĠĠ Ġl 1 Ġl 2 Ġl 3 Ġl 4 Ġl 5 Ġ 0 Ġ 0 ĠĠ 0 Ċ Ġ* Ċ Ġ* Ġl * Ġden ote Ġhashes Ġof Ġleaves , Ġh * Ġ- Ġhashes Ġof Ġnodes Ġbelow . Ġ 0 Ġden otes Ġzero Ġhash , Ġwe Ġuse Ġit Ġto Ġpad Ġnot Ġfull Ġbinary Ġtrees , Ċ Ġ* Ġso Ġthe Ġnumber Ġof Ġleaves Ġis Ġalways Ġa Ġpower Ġof Ġ 2 . Ċ Ġ* Ċ Ġ* ĠExample Ġof ĠPartial Ġtree Ġbased Ġon Ġthe Ġtree Ġabove . Ċ Ġ* Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠ Ġ___ Ċ Ġ* ĠĠĠĠĠĠĠĠĠ Ġ/ ĠĠĠĠĠĠ Ġ\ Ċ Ġ* ĠĠĠĠĠĠĠĠĠ Ġ_ ĠĠĠĠĠĠĠ Ġ_ Ċ Ġ* ĠĠĠĠĠĠĠ Ġ/ Ġ Ġ\ ĠĠĠĠĠ Ġ/ Ġ Ġ\ Ċ Ġ* ĠĠĠĠĠ Ġh 1 2 ĠĠ Ġ_ ĠĠĠĠ Ġ_ ĠĠ Ġh 0 0 Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠ Ġ/ Ġ\ ĠĠ Ġ/ Ġ\ Ċ Ġ* ĠĠĠĠĠĠĠĠĠ ĠI 3 Ġl 4 ĠI 5 Ġ 0 Ċ Ġ* Ċ Ġ* ĠWe Ġwant Ġto Ġcheck Ġl 3 Ġand Ġl 5 Ġ- Ġnow Ġturned Ġinto ĠInc ude d Leaf Ġ( I 3 Ġand ĠI 5 Ġabove ). ĠTo Ġverify Ġthat Ġthese Ġtwo Ġleaves Ġbelong Ġto Ċ Ġ* Ġthe Ġtree Ġwith Ġa Ġhash Ġroot Ġh 1 5 Ġwe Ġneed Ġto Ġprovide Ġa ĠMer kle Ġbranch Ġ( or Ġpartial Ġtree ). ĠIn Ġour Ġcase Ġwe Ġneed Ġhashes : Ċ Ġ* Ġh 1 2 , Ġl 4 , Ġ 0 Ġand Ġh 0 0 . ĠVerification Ġis Ġdone Ġby Ġhashing Ġthe Ġpartial Ġtree Ġto Ġobtain Ġthe Ġroot Ġand Ġchecking Ġit Ġagainst Ċ Ġ* Ġthe Ġobtained Ġh 1 5 Ġhash . ĠAdditionally Ġwe Ġstore Ġincluded Ġhashes Ġused Ġin Ġcalculation Ġand Ġcompare Ġthem Ġto Ġleaves Ġhashes Ġwe Ġgot Ċ Ġ* Ġ( there Ġcan Ġbe Ġa Ġdifference Ġin Ġobtained Ġleaves Ġordering Ġ- Ġthat 's Ġwhy Ġit 's Ġa Ġset Ġcomparison Ġnot Ġhashing Ġleaves Ġinto Ġa Ġtree ). Ċ Ġ* ĠIf Ġboth Ġequal ities Ġhold , Ġwe Ġcan Ġassume Ġthat Ġl 3 Ġand Ġl 5 Ġbelong Ġto Ġthe Ġtransaction Ġwith Ġroot Ġh 1 5 . Ċ Ġ*/ Ċ @ C ord a Serializable Ċ class ĠPartial Mer kle Tree ( val Ġroot : ĠPartial Tree ) Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġstructure Ġis Ġa Ġlittle Ġdifferent Ġthan Ġthat Ġof ĠMer kle ĠTree . ĊĠĠĠĠ Ġ* ĠPartial ĠTree Ġmight Ġnot Ġbe Ġa Ġfull Ġbinary Ġtree . ĠLe aves Ġrepresent Ġeither Ġoriginal ĠMer kle Ġtree Ġleaves ĊĠĠĠĠ Ġ* Ġor Ġcut Ġsubtree Ġnode Ġwith Ġstored Ġhash . ĠWe Ġdifferent iate Ġbetween Ġthe Ġleaves Ġthat Ġare Ġincluded Ġin Ġa Ġfiltered ĊĠĠĠĠ Ġ* Ġtransaction Ġand Ġleaves Ġthat Ġjust Ġkeep Ġhashes Ġneeded Ġfor Ġcalculation . ĠReason Ġfor Ġthis Ġapproach : Ġduring Ġverification ĊĠĠĠĠ Ġ* Ġit 's Ġeasier Ġto Ġextract Ġhashes Ġused Ġas Ġa Ġbase Ġfor Ġthis Ġtree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ C ord a Serializable ĊĠĠĠ Ġsealed Ġclass ĠPartial Tree Ġ{ ĊĠĠĠĠĠĠĠ Ġdata Ġclass ĠInclude d Leaf ( val Ġhash : ĠSecure Hash ) Ġ: ĠPartial Tree () ĊĠĠĠĠĠĠĠ Ġdata Ġclass ĠLeaf ( val Ġhash : ĠSecure Hash ) Ġ: ĠPartial Tree () ĊĠĠĠĠĠĠĠ Ġdata Ġclass ĠNode ( val Ġleft : ĠPartial Tree , Ġval Ġright : ĠPartial Tree ) Ġ: ĠPartial Tree () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġmer kle Root ĠRoot Ġof Ġfull ĠMer kle Ġtree . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġinclude Hashes ĠHas hes Ġthat Ġshould Ġbe Ġincluded Ġin Ġa Ġpartial Ġtree . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return ĠPartial ĠMer kle Ġtree Ġroot . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġ@ Throws ( IllegalArgumentException :: class , ĠMer kle Tree Exception :: class ) ĊĠĠĠĠĠĠĠ Ġfun Ġbuild ( mer kle Root : ĠMer kle Tree , Ġinclude Hashes : ĠList < Secure Hash >): ĠPartial Mer kle Tree Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġused Hashes Ġ= ĠArrayList < Secure Hash >() ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrequire ( zero Hash Ġ! in Ġinclude Hashes ) Ġ{ Ġ" Zero Ġhashes Ġshouldn 't Ġbe Ġincluded Ġin Ġpartial Ġtree ." Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcheck Full ( mer kle Root ) Ġ// ĠThrows ĠMer kle Tree Exception Ġif Ġit Ġis Ġnot Ġa Ġfull Ġbinary Ġtree . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtree Ġ= Ġbuild Partial Tree ( mer kle Root , Ġinclude Hashes , Ġused Hashes ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠToo Ġmany Ġincluded Ġhashes Ġor Ġdifferent Ġones . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( include Hashes . size Ġ!= Ġused Hashes . size ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠMer kle Tree Exception (" Some Ġof Ġthe Ġprovided Ġhashes Ġare Ġnot Ġin Ġthe Ġtree .") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠPartial Mer kle Tree ( tree . second ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠCheck Ġif Ġa ĠMer kle Tree Ġis Ġfull Ġbinary Ġtree . ĠReturns Ġthe Ġheight Ġof Ġthe Ġtree Ġif Ġfull , Ġotherwise Ġthrows Ġexception . ĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġcheck Full ( tree : ĠMer kle Tree , Ġlevel : ĠInt Ġ= Ġ 0 ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( tree ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠMer kle Tree . Leaf Ġ-> Ġlevel ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠMer kle Tree . Node Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġl 1 Ġ= Ġcheck Full ( tree . left , Ġlevel Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġl 2 Ġ= Ġcheck Full ( tree . right , Ġlevel Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( l 1 Ġ!= Ġl 2 ) Ġthrow ĠMer kle Tree Exception (" Got Ġnot Ġfull Ġbinary Ġtree .") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġl 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġroot ĠRoot Ġof Ġfull ĠMer kle Ġtree Ġwhich Ġis Ġa Ġbase Ġfor Ġa Ġpartial Ġone . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġinclude Hashes ĠHas hes Ġof Ġleaves Ġto Ġbe Ġincluded Ġin Ġthis Ġpartial Ġtree . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ param Ġused Hashes ĠHas hes Ġactually Ġused Ġto Ġbuild Ġthis Ġpartial Ġtree . ĊĠĠĠĠĠĠĠĠ Ġ* Ġ@ return ĠPair , Ġfirst Ġelement Ġindicates Ġif Ġin Ġa Ġsubtree Ġthere Ġis Ġa Ġleaf Ġthat Ġis Ġincluded Ġin Ġthat Ġpartial Ġtree . ĊĠĠĠĠĠĠĠĠ Ġ* ĠSecond Ġelement Ġrefers Ġto Ġthat Ġsubtree . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġbuild Partial Tree ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot : ĠMer kle Tree , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġinclude Hashes : ĠList < Secure Hash >, ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġused Hashes : ĠMutable List < Secure Hash > ĊĠĠĠĠĠĠĠ Ġ): ĠPair < Boolean , ĠPartial Tree > Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠMer kle Tree . Leaf Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root . hash Ġin Ġinclude Hashes ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġused Hashes . add ( root . hash ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( true , ĠPartial Tree . Included Leaf ( root . hash )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse ĠPair ( false , ĠPartial Tree . Leaf ( root . hash )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠMer kle Tree . Node Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Node Ġ= Ġbuild Partial Tree ( root . left , Ġinclude Hashes , Ġused Hashes ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Node Ġ= Ġbuild Partial Tree ( root . right , Ġinclude Hashes , Ġused Hashes ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Node . first Ġor Ġright Node . first ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThis Ġnode Ġis Ġon Ġa Ġpath Ġto Ġsome Ġincluded Ġleaves . ĠDon 't Ġstore Ġhash . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Tree Ġ= ĠPartial Tree . Node ( left Node . second , Ġright Node . second ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( true , Ġnew Tree ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThis Ġnode Ġhas Ġno Ġincluded Ġleaves Ġbelow . ĠCut Ġthe Ġtree Ġhere Ġand Ġstore Ġa Ġhash Ġas Ġa ĠLeaf . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Tree Ġ= ĠPartial Tree . Leaf ( root . hash ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( false , Ġnew Tree ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ@ param Ġmer kle Root Hash ĠHash Ġthat Ġshould Ġbe Ġchecked Ġfor Ġequality Ġwith Ġroot Ġcalculated Ġfrom Ġthis Ġpartial Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġhashes ToCheck ĠList Ġof Ġincluded Ġleaves Ġhashes Ġthat Ġshould Ġbe Ġfound Ġin Ġthis Ġpartial Ġtree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġverify ( mer kle Root Hash : ĠSecure Hash , Ġhashes ToCheck : ĠList < Secure Hash >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġused Hashes Ġ= ĠArrayList < Secure Hash >() ĊĠĠĠĠĠĠĠ Ġval Ġverify Root Ġ= Ġverify ( root , Ġused Hashes ) ĊĠĠĠĠĠĠĠ Ġ// ĠIt Ġmeans Ġthat Ġwe Ġobtained Ġmore / f ew er Ġhashes Ġthan Ġneeded Ġor Ġdifferent Ġsets Ġof Ġhashes . ĊĠĠĠĠĠĠĠ Ġif Ġ( hashes ToCheck . groupBy Ġ{ Ġit Ġ} Ġ!= Ġused Hashes . groupBy Ġ{ Ġit Ġ}) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġreturn Ġ( verify Root Ġ== Ġmer kle Root Hash ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRecursive Ġcalculation Ġof Ġroot Ġof Ġthis Ġpartial Ġtree . ĊĠĠĠĠ Ġ* ĠMod ifies Ġused Hashes Ġto Ġlater Ġcheck Ġfor Ġinclusion Ġwith Ġhashes Ġprovided . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġverify ( node : ĠPartial Tree , Ġused Hashes : ĠMutable List < Secure Hash >): ĠSecure Hash Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( node ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠPartial Tree . Included Leaf Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġused Hashes . add ( node . hash ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . hash ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠPartial Tree . Leaf Ġ-> Ġnode . hash ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠPartial Tree . Node Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġleft Hash Ġ= Ġverify ( node . left , Ġused Hashes ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġright Hash Ġ= Ġverify ( node . right , Ġused Hashes ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġleft Hash . hash Concat ( right Hash ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ