research.logos.co/assets/js/04ed9dad.71d6fe31.js

"use strict";(self.webpackChunkresearch_logos_co=self.webpackChunkresearch_logos_co||[]).push([[2104],{17837:(s,e,a)=>{a.d(e,{A:()=>n});const n=a.p+"assets/images/vac101_binary_tree-f2600381c1537895a063761d315201ce.png"},21427:(s,e,a)=>{a.d(e,{A:()=>n});const n=a.p+"assets/images/vac101_tree-c39839d4050c3723ccde9d3622de2870.png"},28453:(s,e,a)=>{a.d(e,{R:()=>l,x:()=>r});var n=a(96540);const i={},t=n.createContext(i);function l(s){const e=n.useContext(t);return n.useMemo((function(){return"function"==typeof s?s(e):{...e,...s}}),[e,s])}function r(s){let e;return e=s.disableParentContext?"function"==typeof s.components?s.components(i):s.components||i:l(s.components),n.createElement(t.Provider,{value:e},s.children)}},51840:(s,e,a)=>{a.r(e),a.d(e,{assets:()=>h,contentTitle:()=>r,default:()=>d,frontMatter:()=>l,metadata:()=>n,toc:()=>m});var n=a(74721),i=a(74848),t=a(28453);const l={title:"Vac 101: Climbing Merkle Trees",date:new Date("2024-12-30T12:00:00.000Z"),authors:"marvin",published:!0,slug:"climbing-merkle-trees",categories:"research",toc_min_heading_level:2,toc_max_heading_level:4},r=void 0,h={authorsImageUrls:[void 0]},m=[{value:"Introduction",id:"introduction",level:2},{value:"Tree structure",id:"tree-structure",level:2},{value:"Merkle trees",id:"merkle-trees",level:2},{value:"Construction",id:"construction",level:3},{value:"Merkle tree intregrity",id:"merkle-tree-intregrity",level:3},{value:"Proof of membership",id:"proof-of-membership",level:3},{value:"Capped proof of membership",id:"capped-proof-of-membership",level:4},{value:"Extensions of Merkle trees",id:"extensions-of-merkle-trees",level:2},{value:"Sparse Merkle trees",id:"sparse-merkle-trees",level:3},{value:"Proof of nonmembership",id:"proof-of-nonmembership",level:3},{value:"Verkle Trees",id:"verkle-trees",level:3},{value:"References",id:"references",level:2}];function c(s){const e={a:"a",annotation:"annotation",h2:"h2",h3:"h3",h4:"h4",img:"img",li:"li",math:"math",mi:"mi",mn:"mn",mo:"mo",mpadded:"mpadded",mrow:"mrow",mspace:"mspace",msub:"msub",msubsup:"msubsup",msup:"msup",ol:"ol",p:"p",semantics:"semantics",span:"span",table:"table",tbody:"tbody",td:"td",th:"th",thead:"thead",tr:"tr",ul:"ul",...(0,t.R)(),...s.components};return(0,i.jsxs)(i.Fragment,{children:[(0,i.jsx)(e.p,{children:"In this post, we introduce a crucial data structure used throughout web3."}),"\n","\n",(0,i.jsx)(e.h2,{id:"introduction",children:"Introduction"}),"\n",(0,i.jsx)(e.p,{children:"A large amount of data is swapped between users on a blockchain in the form of transactions.\nOver the entire life of a blockchain,\nthe storage space required to maintain a copy of every transaction becomes untenable for most users.\nHowever, the integrity of a blockchain relies on a large pool of users that can validate the blockchain's history from its inception to its present state.\nThe data representing the blockchain's state is compressed.\nThis compression addresses the issue of scalability that would otherwise greatly restrict the pool of users."}),"\n",(0,i.jsxs)(e.p,{children:["Data compression alone is not the end goal.\nAs mentioned, it is essential for users to be able to validate the blockchain's history.\nThe property of compression and validation was solved in Bitcoin by the use of Merkle trees.\nMerkle trees were introduced first by Ralph Merkle in his dissertation [",(0,i.jsx)(e.a,{href:"https://www.ralphmerkle.com/papers/Thesis1979.pdf",children:"1"}),"].\nA Merkle tree is a data structure that compresses a digest of data to a constant size while still providing a method for proving membership of elements of the digest.\nA previous rlog[",(0,i.jsx)(e.a,{href:"https://research.logos.co/rlog/rln-light-verifiers/",children:"2"}),"] described how Merkle trees with their proof of membership could be used for lightweight clients for RLN."]}),"\n",(0,i.jsx)(e.h2,{id:"tree-structure",children:"Tree structure"}),"\n",(0,i.jsx)(e.p,{children:"A tree is a special data structure that organizes nodes so that there is exactly one path between any two nodes.\nThe trees that we consider can be arranged in layers with multiple nodes (children) merged into a single node (parent) in the preceding layer.\nA single node exists in the base layer;\nthis special node is called the root node.\nThe highest level of the tree consists of childless nodes called leaves."}),"\n",(0,i.jsx)(e.p,{children:(0,i.jsx)(e.img,{alt:"Image 1",src:a(21427).A+"",width:"1017",height:"456"})}),"\n",(0,i.jsx)(e.p,{children:"A binary tree has one additional property:\neach nonleaf node has exactly two children nodes.\nThat is, we assume that nodes in a binary tree are either a parent node with two children or a leaf.\nAs strange as it sounds, each child node has exactly one parental node."}),"\n",(0,i.jsx)(e.p,{children:(0,i.jsx)(e.img,{alt:"Image 2",src:a(17837).A+"",width:"940",height:"467"})}),"\n",(0,i.jsxs)(e.p,{children:["A binary tree with ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsx)(e.mi,{children:"n"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^n"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6644em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"})})]})})})})})]})]})})]})," leaves consists of ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{children:"+"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"n+1"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6667em",verticalAlign:"-0.0833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"n"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"+"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6444em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"})]})]})]})," layers.\nAdditionally, such a tree has ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{children:"+"}),(0,i.jsx)(e.mn,{children:"1"})]})]}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^{n+1}-1"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8974em",verticalAlign:"-0.0833em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.8141em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(e.span,{className:"mord mtight",children:[(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"}),(0,i.jsx)(e.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})]})})]})})})})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6444em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"})]})]})]})," nodes."]}),"\n",(0,i.jsx)(e.h2,{id:"merkle-trees",children:"Merkle trees"}),"\n",(0,i.jsx)(e.p,{children:"A Merkle tree is a specialized tree in which each node contains the evaluation of a hash function.\nMerkle trees are usually taken to have a binary tree structure.\nAs such, the presentation we provide in this section will be for binary trees."}),"\n",(0,i.jsx)(e.h3,{id:"construction",children:"Construction"}),"\n",(0,i.jsxs)(e.p,{children:["In this section, we show how Merkle trees are constructed to compress a digest ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"D"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"D"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"D"})]})})]}),".\nSuppose that the digest ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"D"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"D"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"D"})]})})]})," consists of ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsx)(e.mi,{children:"n"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^n"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6644em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"})})]})})})})})]})]})})]})," entries;\nwe assume that the digest ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"D"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"D"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"D"})]})})]})," has this many entries since a Merkle tree is a binary tree.\nAdditionally, each digest can be padded to ensure that ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"D"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"D"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"D"})]})})]})," has the desired number of entries."]}),"\n",(0,i.jsxs)(e.p,{children:["Each leaf of the Merkle tree contains the hash of a digest entry.\nEach parent node contains the hash of the concatenation of their child nodes.\nThrough this iterative construction, we reach the root of the tree.\nThe value contained in the root node is called the root hash.\nThe root hash is a compressed representation of the digest ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"D"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"D"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"D"})]})})]}),"."]}),"\n",(0,i.jsx)(e.p,{children:(0,i.jsx)(e.img,{alt:"Image 3",src:a(77730).A+"",width:"1035",height:"629"})}),"\n",(0,i.jsxs)(e.p,{children:["Each node in the Merkle tree is computed by taking a hash.\nSince a binary tree with ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsx)(e.mi,{children:"n"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^n"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6644em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"})})]})})})})})]})]})})]})," leaves has ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{children:"+"}),(0,i.jsx)(e.mn,{children:"1"})]})]}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^{n+1}-1"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8974em",verticalAlign:"-0.0833em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.8141em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(e.span,{className:"mord mtight",children:[(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"}),(0,i.jsx)(e.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})]})})]})})})})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6444em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"})]})]})]})," nodes,\nthen we need to evaluate ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{children:"+"}),(0,i.jsx)(e.mn,{children:"1"})]})]}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^{n+1}-1"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8974em",verticalAlign:"-0.0833em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.8141em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(e.span,{className:"mord mtight",children:[(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"}),(0,i.jsx)(e.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})]})})]})})})})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6444em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"})]})]})]})," hashes to construct the Merkle tree."]}),"\n",(0,i.jsx)(e.h3,{id:"merkle-tree-intregrity",children:"Merkle tree intregrity"}),"\n",(0,i.jsx)(e.p,{children:"A large quantity of data can be compressed to a single hash value.\nA natural question to ask is: could a clever party find another digest that yields a Merkle tree with the same root hash?\nIf possible, this would compromise the ledger since the blockchain's history could be altered.\nFortunately, Merkle trees are quite secure.\nIn fact, Merkle trees can be used to both bind and hide a digest."}),"\n",(0,i.jsxs)(e.p,{children:["The Merkle tree is able to bind a digest with one of the properties of hash functions (see our previous Vac 101 [",(0,i.jsx)(e.a,{href:"https://research.logos.co/rlog/vac101-fiat-shamir#hash-functions",children:"3"}),"] for information on hash functions).\nA hash function is collision resistant; it is infeasible for a malicious party to find two values share the same hash value."]}),"\n",(0,i.jsx)(e.p,{children:"This collision resistance property, essentially, fixes the input to each leaf and into their parent, their parent's parent, and so on."}),"\n",(0,i.jsx)(e.p,{children:"In certain applications,\nit may be desirable for the digest of a Merkle tree to be kept confidential.\nThis is achieved with the preimage resistant property of hash functions.\nA hash function is preimage resistant provided that it is difficult to reverse the hashing operation.\nIt would be necessary for a malicious party to find preimages to each node starting from the root node to determine the original digest."}),"\n",(0,i.jsx)(e.p,{children:"Now, we see that Merkle trees are secured structures that are tamper resistant."}),"\n",(0,i.jsx)(e.h3,{id:"proof-of-membership",children:"Proof of membership"}),"\n",(0,i.jsx)(e.p,{children:"An interesting and critical property of Merkle trees is their ability to prove that any piece of data is part of its digest.\nThis can be done with logarithmic storage and logarithmic computation time."}),"\n",(0,i.jsxs)(e.p,{children:["Suppose that we want to show that data ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," is part of the Merkle tree's digest.\nAdditionally, suppose that ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{hash}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"hash"})})]})})]})," is the hash function used to construct the tree.\nWe assume that the hash function ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{hash}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"hash"})})]})})]})," can be computed in constant-time for any input."]}),"\n",(0,i.jsxs)(e.p,{children:["Suppose that a prover provides data ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," to a verifier,\nand tells the verifier that ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," corresponds to the ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"i"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"i"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6595em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"i"})]})})]}),"th leaf of the Merkle tree.\nFor the verifier to be convinced that ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," is part of the digest, he needs to be able to construct the tree's root hash using ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{hash}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"hash"})})]})})]}),", ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"i"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"i"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6595em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"i"})]})})]}),", ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," and some additional information from the prover.\nSpecifically, the prover must provide the sibling hashes for each value that the verifier can compute.\nThis enables the verifier to compute the parents of the siblings that the prover provides and the values that he was able to produce himself.\nThe last of the computed parents is the root."]}),"\n",(0,i.jsxs)(e.p,{children:["The leaf index ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"i"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"i"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6595em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"i"})]})})]})," indicates whether a hash value provided by the prover is a left or right sibling.\nThis is done by looking at the binary expansion of ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"i"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"i"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6595em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"i"})]})})]}),"."]}),"\n",(0,i.jsxs)(e.p,{children:["The verifier can compute the leaf ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"})]}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"h_0 = \\mathsf{hash}(\\ell)"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:"="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"hash"})}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]})]})]}),".\nNext, using ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"h_0"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]})]})})]}),"'s sibling, ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msubsup,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"}),(0,i.jsx)(e.mo,{mathvariant:"normal",lspace:"0em",rspace:"0em",children:"\u2032"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"h'_0"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.2481em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsxs)(e.span,{className:"vlist",style:{height:"0.7519em"},children:[(0,i.jsxs)(e.span,{style:{top:"-2.4519em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]}),(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"\u2032"})})})]})]}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2481em"},children:(0,i.jsx)(e.span,{})})})]})})]})]})})]}),", provided by the prover,\nthe verifier can compute ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"})]}),(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2225"}),(0,i.jsxs)(e.msubsup,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"}),(0,i.jsx)(e.mo,{mathvariant:"normal",lspace:"0em",rspace:"0em",children:"\u2032"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"h_1 = \\mathsf{hash}(h_0 \\|h'_0)"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:"="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1.0019em",verticalAlign:"-0.25em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"hash"})}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mord",children:"\u2225"}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsxs)(e.span,{className:"vlist",style:{height:"0.7519em"},children:[(0,i.jsxs)(e.span,{style:{top:"-2.4519em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]}),(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"\u2032"})})})]})]}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2481em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]})]})]})," or ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(e.msubsup,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"}),(0,i.jsx)(e.mo,{mathvariant:"normal",lspace:"0em",rspace:"0em",children:"\u2032"})]}),(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2225"}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"h_1 = \\mathsf{hash}(h'_0 \\| h_0)"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:"="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1.0019em",verticalAlign:"-0.25em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"hash"})}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsxs)(e.span,{className:"vlist",style:{height:"0.7519em"},children:[(0,i.jsxs)(e.span,{style:{top:"-2.4519em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]}),(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"\u2032"})})})]})]}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2481em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mord",children:"\u2225"}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]})]})]}),"\ndepending on whether ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msubsup,{children:[(0,i.jsx)(e.mi,{children:"h"}),(0,i.jsx)(e.mn,{children:"0"}),(0,i.jsx)(e.mo,{mathvariant:"normal",lspace:"0em",rspace:"0em",children:"\u2032"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"h'_0"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.2481em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsxs)(e.span,{className:"vlist",style:{height:"0.7519em"},children:[(0,i.jsxs)(e.span,{style:{top:"-2.4519em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]}),(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"\u2032"})})})]})]}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2481em"},children:(0,i.jsx)(e.span,{})})})]})})]})]})})]})," is a left or right sibling.\nThis pathing continues until the verifier either successfully computes the root hash (in ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{children:"+"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"n+1"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6667em",verticalAlign:"-0.0833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"n"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"+"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6444em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"})]})]})]})," hashes) or fails to do so."]}),"\n",(0,i.jsxs)(e.p,{children:["The prover has to provide ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"n"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"n"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"n"})]})})]})," sibling nodes for the proof of membership."]}),"\n",(0,i.jsxs)(e.p,{children:["There is a key detail that is essential for the proof of membership to be secure.\nThe root hash has to be provided to the verifier prior to the selection of data ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]}),".\nOtherwise, the prover could generate a series of hash values (with the corresponding root hash) to forge a proof of membership."]}),"\n",(0,i.jsx)(e.h4,{id:"capped-proof-of-membership",children:"Capped proof of membership"}),"\n",(0,i.jsxs)(e.p,{children:["Polygon provides an implementation [",(0,i.jsx)(e.a,{href:"https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/src/hash/merkle_tree.rs",children:"4"}),"] of a shortened proof of membership with a slight modification.\nA specific layer of the Merkle tree is published instead of just the root hash.\nBy doing this, a capped proof of membership is just the path from leaf to the published layer."]}),"\n",(0,i.jsx)(e.h2,{id:"extensions-of-merkle-trees",children:"Extensions of Merkle trees"}),"\n",(0,i.jsx)(e.p,{children:"Merkle trees can be extended in multiple ways.\nIn this section, we explore a select few of these extensions."}),"\n",(0,i.jsx)(e.h3,{id:"sparse-merkle-trees",children:"Sparse Merkle trees"}),"\n",(0,i.jsx)(e.p,{children:"A sparse Merkle tree (SMT) is a special Merkle tree that can be used to represent digests with nonconsecutive entries.\nSpecifically, each digest entry has a particular leaf index.\nFor simplicity, we assume that the index value is computed by taking the hash of the entry.\nWe note that this is a sorted SMT."}),"\n",(0,i.jsxs)(e.p,{children:["Let ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"n"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"n"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"n"})]})})]})," denote the number of bits that a hash value can possess. This means that our SMT can have at most ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsx)(e.mi,{children:"n"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^n"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6644em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"})})]})})})})})]})]})})]})," leaves."]}),"\n",(0,i.jsxs)(e.p,{children:["An SMT is treated as a Merkle tree in which each entry is placed in the leaf corresponding to its hash value, and the other entries have a ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"u"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{null}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"null"})})]})})]})," marker inserted in.\nThis means that we can prove membership in the way described.\nHowever, we can also prove nonmembership of an element by showing that ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"u"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{null}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"null"})})]})})]})," is located in the element's hash location.\nThe crucial difference between a sorted and unsorted SMT is that the unsorted variant cannot be used to prove nonmembership."]}),"\n",(0,i.jsx)(e.p,{children:"We can take advantage of the sparse nature of SMTs to provide shortened proofs.\nSpecifically, it is unlikely for entries to cluster together.\nThus, it is efficient to maintain a list of values:"}),"\n",(0,i.jsxs)(e.table,{children:[(0,i.jsx)(e.thead,{children:(0,i.jsx)(e.tr,{children:(0,i.jsx)(e.th,{children:"Null values"})})}),(0,i.jsxs)(e.tbody,{children:[(0,i.jsx)(e.tr,{children:(0,i.jsx)(e.td,{children:(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"d"}),(0,i.jsx)(e.mn,{children:"0"})]}),(0,i.jsx)(e.mo,{children:":"}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"u"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.mo,{separator:"true",children:","})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"d_0 := \\mathsf{Hash(null)},"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:":="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"Hash"}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsx)(e.span,{className:"mord mathsf",children:"null"}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]}),(0,i.jsx)(e.span,{className:"mpunct",children:","})]})]})]})})}),(0,i.jsx)(e.tr,{children:(0,i.jsx)(e.td,{children:(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"d"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.mo,{children:":"}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"d"}),(0,i.jsx)(e.mn,{mathvariant:"sans-serif",children:"0"})]}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"\u2225"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"\u2225"}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"d"}),(0,i.jsx)(e.mn,{mathvariant:"sans-serif",children:"0"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.mo,{separator:"true",children:","})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"d_1 := \\mathsf{Hash(d_0 \\|\\| d_0)},"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:":="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"Hash"}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3089em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mord",children:"\u2225\u2225"}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3089em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"0"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]}),(0,i.jsx)(e.span,{className:"mpunct",children:","})]})]})]})})}),(0,i.jsx)(e.tr,{children:(0,i.jsx)(e.td,{children:(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"d"}),(0,i.jsx)(e.mn,{children:"2"})]}),(0,i.jsx)(e.mo,{children:":"}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"d"}),(0,i.jsx)(e.mn,{mathvariant:"sans-serif",children:"1"})]}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"\u2225"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"\u2225"}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"d"}),(0,i.jsx)(e.mn,{mathvariant:"sans-serif",children:"1"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.mo,{separator:"true",children:","})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"d_2 := \\mathsf{Hash(d_1 \\|\\| d_1)},"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"2"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:":="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"Hash"}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3089em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"1"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mord",children:"\u2225\u2225"}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3089em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"1"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]}),(0,i.jsx)(e.span,{className:"mpunct",children:","})]})]})]})})}),(0,i.jsx)(e.tr,{children:(0,i.jsx)(e.td,{children:(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u22ee"}),(0,i.jsx)(e.mpadded,{height:"0em",voffset:"0em",children:(0,i.jsx)(e.mspace,{mathbackground:"black",width:"0em",height:"1.5em"})})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\vdots"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1.53em",verticalAlign:"-0.03em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"\u22ee"}),(0,i.jsx)(e.span,{className:"mord rule",style:{borderRightWidth:"0em",borderTopWidth:"1.5em",bottom:"0em"}})]})]})})]})})}),(0,i.jsx)(e.tr,{children:(0,i.jsx)(e.td,{children:(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"d"}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{children:"1"})]})]}),(0,i.jsx)(e.mo,{children:":"}),(0,i.jsx)(e.mo,{children:"="}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"d"}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{mathvariant:"sans-serif",children:"2"})]})]}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"\u2225"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"\u2225"}),(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"d"}),(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{mathvariant:"sans-serif",children:"2"})]})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.mi,{mathvariant:"normal",children:"."})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"d_{n-1} := \\mathsf{Hash(d_{n-2} \\|\\| d_{n-2})}."})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.9028em",verticalAlign:"-0.2083em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(e.span,{className:"mord mtight",children:[(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"n"}),(0,i.jsx)(e.span,{className:"mbin mtight",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mord mtight",children:"1"})]})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(e.span,{className:"mrel",children:":="}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"Hash"}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3089em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(e.span,{className:"mord mtight",children:[(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"n"}),(0,i.jsx)(e.span,{className:"mbin mtight",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"2"})]})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mord",children:"\u2225\u2225"}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathsf",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3089em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(e.span,{className:"mord mtight",children:[(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"n"}),(0,i.jsx)(e.span,{className:"mbin mtight",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mord mathsf mtight",children:"2"})]})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]}),(0,i.jsx)(e.span,{className:"mord",children:"."})]})]})]})})})]})]}),"\n",(0,i.jsxs)(e.p,{children:["Each of the ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msub,{children:[(0,i.jsx)(e.mi,{children:"d"}),(0,i.jsx)(e.mi,{children:"i"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"d_i"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8444em",verticalAlign:"-0.15em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord mathnormal",children:"d"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.3117em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"i"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(e.span,{})})})]})})]})]})})]}),"'s represents the root hash of a Merkle tree with ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsx)(e.mi,{children:"i"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^i"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8247em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.8247em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",children:"i"})})]})})})})})]})]})})]})," leaves containing ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"u"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{null}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"null"})})]})})]}),".\nThese values can be used to shorten the time needed to construct an SMT and the length of proofs."]}),"\n",(0,i.jsx)(e.h3,{id:"proof-of-nonmembership",children:"Proof of nonmembership"}),"\n",(0,i.jsxs)(e.p,{children:["In the first Vac 101 [",(0,i.jsx)(e.a,{href:"https://research.logos.co/rlog/vac101-membership-with-bloom-filters-and-cuckoo-filters",children:"5"}),"], we examined Bloom and Cuckoo filters that could be used for proof of membership and nonmembership.\nHowever, the proof of membership may result in false positives due to collisions.\nThis would affect nonmembership proofs as well.\nSparse Merkle trees can be adapted to provide greater assurance that a given piece of data is not a member of the digest."]}),"\n",(0,i.jsxs)(e.p,{children:["Why is sorting essential?\nThe sorting mechanism of data can be arbitrarily chosen.\nHowever, it is essential that there are no gaps in the ordering.\nThe maximum number of elements that could ever exist in the digest must be known.\nA simple method for this is to use a hash function to provide fingerprints to the data.\nEach hash using either SHA-256 or Keccak has 256-bits.\nOur entire digest could consist of a maximum of ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsxs)(e.msup,{children:[(0,i.jsx)(e.mn,{children:"2"}),(0,i.jsx)(e.mn,{children:"256"})]})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"2^{256}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.8141em"}}),(0,i.jsxs)(e.span,{className:"mord",children:[(0,i.jsx)(e.span,{className:"mord",children:"2"}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsx)(e.span,{className:"vlist-t",children:(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.8141em"},children:(0,i.jsxs)(e.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:(0,i.jsx)(e.span,{className:"mord mtight",children:"256"})})})]})})})})})]})]})})]})," entries.\nThis assumes that our digest does not contain collisions."]}),"\n",(0,i.jsxs)(e.p,{children:["The fingerprint of a piece of data ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," indicates which leaf of the SMT it is contained in.\nThis means that a nonmembership of ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," in the SMT becomes a matter of proving that ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"u"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(e.mi,{mathvariant:"sans-serif",children:"l"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\mathsf{null}"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:(0,i.jsx)(e.span,{className:"mord mathsf",children:"null"})})]})})]})," is contained in ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]}),"'s location."]}),"\n",(0,i.jsxs)(e.p,{children:["It is crucial for the SMT to be sorted.\nOtherwise, a malicious party can append the entry ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{mathvariant:"normal",children:"\u2113"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\ell"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord",children:"\u2113"})]})})]})," to a random location.\nThis allows for the malicious party to provide contradictory proofs that prove both membership and nonmembership.\nWe note that the requirement that an SMT is sorted may be too strong of an assumption in centralized cases.\nHowever, sortedness is a necessary property of SMTs for decentralized systems."]}),"\n",(0,i.jsx)(e.h3,{id:"verkle-trees",children:"Verkle Trees"}),"\n",(0,i.jsxs)(e.p,{children:["A proof of membership grows in length as the Merkle tree grows.\nThe most obvious approach to remedy this scalability issue is to use Merkle trees in which each node has more than two children.\nHowever, this does not fix the issue.\nA proof of membership in a ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"k"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"k"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.03148em"},children:"k"})]})})]}),"-nary Merkle tree [",(0,i.jsx)(e.a,{href:"https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf",children:"6"}),"] (each node has ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsx)(e.mrow,{children:(0,i.jsx)(e.mi,{children:"k"})}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"k"})]})})}),(0,i.jsx)(e.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.03148em"},children:"k"})]})})]})," children) has a proof size ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsxs)(e.msub,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"log"}),(0,i.jsx)(e.mo,{children:"\u2061"})]}),(0,i.jsx)(e.mi,{children:"k"})]}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsx)(e.mi,{children:"n"}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"}),(0,i.jsx)(e.mo,{stretchy:"false",children:"("}),(0,i.jsx)(e.mi,{children:"k"}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{children:"1"}),(0,i.jsx)(e.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"\\log_k(n)(k-1)"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsxs)(e.span,{className:"mop",children:[(0,i.jsxs)(e.span,{className:"mop",children:["lo",(0,i.jsx)(e.span,{style:{marginRight:"0.01389em"},children:"g"})]}),(0,i.jsx)(e.span,{className:"msupsub",children:(0,i.jsxs)(e.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(e.span,{className:"vlist-r",children:[(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.242em"},children:(0,i.jsxs)(e.span,{style:{top:"-2.4559em",marginRight:"0.05em"},children:[(0,i.jsx)(e.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(e.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(e.span,{className:"mord mathnormal mtight",style:{marginRight:"0.03148em"},children:"k"})})]})}),(0,i.jsx)(e.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(e.span,{className:"vlist-r",children:(0,i.jsx)(e.span,{className:"vlist",style:{height:"0.2441em"},children:(0,i.jsx)(e.span,{})})})]})})]}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsx)(e.span,{className:"mord mathnormal",children:"n"}),(0,i.jsx)(e.span,{className:"mclose",children:")"}),(0,i.jsx)(e.span,{className:"mopen",children:"("}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.03148em"},children:"k"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"}),(0,i.jsx)(e.span,{className:"mclose",children:")"})]})]})]}),".\nThe multiple ",(0,i.jsxs)(e.span,{className:"katex",children:[(0,i.jsx)(e.span,{className:"katex-mathml",children:(0,i.jsx)(e.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(e.semantics,{children:[(0,i.jsxs)(e.mrow,{children:[(0,i.jsx)(e.mi,{children:"k"}),(0,i.jsx)(e.mo,{children:"\u2212"}),(0,i.jsx)(e.mn,{children:"1"})]}),(0,i.jsx)(e.annotation,{encoding:"application/x-tex",children:"k-1"})]})})}),(0,i.jsxs)(e.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.7778em",verticalAlign:"-0.0833em"}}),(0,i.jsx)(e.span,{className:"mord mathnormal",style:{marginRight:"0.03148em"},children:"k"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(e.span,{className:"mbin",children:"\u2212"}),(0,i.jsx)(e.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(e.span,{className:"base",children:[(0,i.jsx)(e.span,{className:"strut",style:{height:"0.6444em"}}),(0,i.jsx)(e.span,{className:"mord",children:"1"})]})]})]})," is the number of silbings that a node has on each layer.\nHence, the proof size grows faster than a logarithmic function of the digest size."]}),"\n",(0,i.jsxs)(e.p,{children:["An alternate approach is to use a different data structure: Verkle trees [",(0,i.jsx)(e.a,{href:"https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf",children:"6"}),"].\nA Verkle tree replaces hash functions with polynomial commitments [",(0,i.jsx)(e.a,{href:"https://ethresear.ch/t/using-polynomial-commitments-to-replace-state-roots/7095",children:"7"}),", ",(0,i.jsx)(e.a,{href:"https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html",children:"8"}),"].\nWe will explore Verkle trees in a future Vac 101 edition."]}),"\n",(0,i.jsx)(e.h2,{id:"references",children:"References"}),"\n",(0,i.jsxs)(e.ul,{children:["\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://www.ralphmerkle.com/papers/Thesis1979.pdf",children:"Secrecy, Authentication, and Public Key Systems"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"2",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://research.logos.co/rlog/rln-light-verifiers/",children:"Verifying RLN Proofs in Light Clients with Subtrees"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"3",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://research.logos.co/rlog/vac101-fiat-shamir#hash-functions",children:"Vac 101: Transforming an Interactive Protocol to a Noninteractive Argument"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"4",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/src/hash/merkle_tree.rs",children:"Capped merkle tree in Plonky2"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"5",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://research.logos.co/rlog/vac101-membership-with-bloom-filters-and-cuckoo-filters",children:"Vac 101: Membership with Bloom Filters and Cuckoo Filters"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"6",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf",children:"Verkle Trees"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"7",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://ethresear.ch/t/using-polynomial-commitments-to-replace-state-roots/7095",children:"Using polynomial commitments to replace state roots"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"8",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html",children:"KZG polynomial commitments"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(e.li,{children:["\n",(0,i.jsxs)(e.ol,{start:"9",children:["\n",(0,i.jsx)(e.li,{children:(0,i.jsx)(e.a,{href:"https://github.com/o1-labs/verkle-tree",children:"O1 labs' Verkle Tree repo"})}),"\n"]}),"\n"]}),"\n"]})]})}function d(s={}){const{wrapper:e}={...(0,t.R)(),...s.components};return e?(0,i.jsx)(e,{...s,children:(0,i.jsx)(c,{...s})}):c(s)}},74721:s=>{s.exports=JSON.parse('{"permalink":"/rlog/climbing-merkle-trees","source":"@site/rlog/2024-12-30-merkle-tree.mdx","title":"Vac 101: Climbing Merkle Trees","description":"In this post, we introduce a crucial data structure used throughout web3.","date":"2024-12-30T12:00:00.000Z","tags":[],"readingTime":9.68,"hasTruncateMarker":true,"authors":[{"name":"Marvin","github":"jonesmarvin8","key":"marvin","page":null}],"frontMatter":{"title":"Vac 101: Climbing Merkle Trees","date":"2024-12-30T12:00:00.000Z","authors":"marvin","published":true,"slug":"climbing-merkle-trees","categories":"research","toc_min_heading_level":2,"toc_max_heading_level":4},"unlisted":false,"prevItem":{"title":"Vac 2024 Year in Review","permalink":"/rlog/2024-recap"},"nextItem":{"title":"Large Message Handling in GossipSub: Potential Improvements","permalink":"/rlog/gsub-largemsg-improvements"}}')},77730:(s,e,a)=>{a.d(e,{A:()=>n});const n=a.p+"assets/images/vac101_merkle_tree-a7c86f78d5aa8016921924220d6005fc.png"}}]);