research.logos.co/assets/js/a71c3513.70ff5f0a.js

"use strict";(self.webpackChunkresearch_logos_co=self.webpackChunkresearch_logos_co||[]).push([[7483],{28096:(e,s,n)=>{n.r(s),n.d(s,{assets:()=>c,contentTitle:()=>l,default:()=>o,frontMatter:()=>r,metadata:()=>i,toc:()=>h});var i=n(51049),a=n(74848),t=n(28453);const r={title:"Verifying RLN Proofs in Light Clients with Subtrees",date:new Date("2024-05-03T12:00:00.000Z"),authors:"p1ge0nh8er",published:!0,slug:"rln-light-verifiers",categories:"research",toc_min_heading_level:2,toc_max_heading_level:4},l=void 0,c={authorsImageUrls:[void 0]},h=[{value:"Introduction",id:"introduction",level:2},{value:"Constraints and requirements",id:"constraints-and-requirements",level:2},{value:"Metrics on sync time for a tree with 2,653 leaves",id:"metrics-on-sync-time-for-a-tree-with-2653-leaves",level:2},{value:"Test bench",id:"test-bench",level:3},{value:"Metrics",id:"metrics",level:3},{value:"Proposed solution",id:"proposed-solution",level:2},{value:"Insertion",id:"insertion",level:3},{value:"Syncing",id:"syncing",level:3},{value:"Gas costs",id:"gas-costs",level:3},{value:"Events",id:"events",level:3},{value:"Proof of concept",id:"proof-of-concept",level:3},{value:"Future work",id:"future-work",level:2},{value:"Conclusion",id:"conclusion",level:2},{value:"References",id:"references",level:2}];function m(e){const s={a:"a",annotation:"annotation",code:"code",em:"em",h2:"h2",h3:"h3",img:"img",li:"li",math:"math",mi:"mi",mn:"mn",mo:"mo",mrow:"mrow",msup:"msup",ol:"ol",p:"p",semantics:"semantics",span:"span",ul:"ul",...(0,t.R)(),...e.components};return(0,a.jsxs)(a.Fragment,{children:[(0,a.jsx)(s.p,{children:"How resource-restricted devices can verify RLN proofs fast and efficiently."}),"\n","\n",(0,a.jsx)(s.h2,{id:"introduction",children:"Introduction"}),"\n",(0,a.jsxs)(s.p,{children:["Recommended previous reading: ",(0,a.jsx)(s.a,{href:"https://research.logos.co/rlog/rln-anonymous-dos-prevention",children:"Strengthening Anonymous DoS Prevention with Rate Limiting Nullifiers in Waku"}),"."]}),"\n",(0,a.jsx)(s.p,{children:"This post expands upon ideas described in the previous post,\nfocusing on how resource-restricted devices can verify RLN proofs fast and efficiently."}),"\n",(0,a.jsx)(s.p,{children:"Previously, it was required to fetch all the memberships from the smart contract,\nconstruct the merkle tree locally,\nand derive the merkle root,\nwhich is subsequently used to verify RLN proofs."}),"\n",(0,a.jsx)(s.p,{children:"This process is not feasible for resource-restricted devices since it involves a lot of RPC calls, computation and fault tolerance.\nOne cannot expect a mobile phone to fetch all the memberships from the smart contract and construct the merkle tree locally."}),"\n",(0,a.jsx)(s.h2,{id:"constraints-and-requirements",children:"Constraints and requirements"}),"\n",(0,a.jsxs)(s.p,{children:["An alternative solution to the one proposed in this post is to construct the merkle tree on-chain,\nand have the root accessible with a single RPC call.\nHowever, this approach increases gas costs for inserting new memberships and ",(0,a.jsx)(s.em,{children:"may"})," not be feasible until it is optimized further with batching mechanisms, etc."]}),"\n",(0,a.jsxs)(s.p,{children:["The other methods have been explored in more depth ",(0,a.jsx)(s.a,{href:"https://hackmd.io/@rymnc/rln-tree-storages",children:"here"}),"."]}),"\n",(0,a.jsx)(s.p,{children:"Following are the requirements and constraints for the solution proposed in this post:"}),"\n",(0,a.jsxs)(s.ol,{children:["\n",(0,a.jsx)(s.li,{children:"Cheap membership insertions."}),"\n",(0,a.jsx)(s.li,{children:"As few RPC calls as possible to reduce startup time."}),"\n",(0,a.jsx)(s.li,{children:"Merkle root of the tree is available on-chain."}),"\n",(0,a.jsx)(s.li,{children:"No centralized services to sequence membership insertions."}),"\n",(0,a.jsx)(s.li,{children:"Map inserted commitments to the block in which they were inserted."}),"\n"]}),"\n",(0,a.jsx)(s.h2,{id:"metrics-on-sync-time-for-a-tree-with-2653-leaves",children:"Metrics on sync time for a tree with 2,653 leaves"}),"\n",(0,a.jsx)(s.p,{children:"The following metrics are based on the current implementation of RLN in the Waku gen0 network."}),"\n",(0,a.jsx)(s.h3,{id:"test-bench",children:"Test bench"}),"\n",(0,a.jsxs)(s.ul,{children:["\n",(0,a.jsx)(s.li,{children:"Hardware: Macbook Air M2, 16GB RAM"}),"\n",(0,a.jsx)(s.li,{children:"Network: 120 Megabits/sec"}),"\n",(0,a.jsxs)(s.li,{children:["Nwaku commit: ",(0,a.jsx)(s.a,{href:"https://github.com/waku-org/nwaku/tree/e61e4ff90a235657a7dc4248f5be41b6e031e98c",children:"e61e4ff"})]}),"\n",(0,a.jsxs)(s.li,{children:["RLN membership set contract: ",(0,a.jsx)(s.a,{href:"https://sepolia.etherscan.io/address/0xF471d71E9b1455bBF4b85d475afb9BB0954A29c4#code",children:"0xF471d71E9b1455bBF4b85d475afb9BB0954A29c4"})]}),"\n",(0,a.jsx)(s.li,{children:"Deployed block number: 4,230,716"}),"\n",(0,a.jsx)(s.li,{children:"RLN Membership set depth: 20"}),"\n",(0,a.jsx)(s.li,{children:"Hash function: PoseidonT3 (which is a gas guzzler)"}),"\n",(0,a.jsx)(s.li,{children:"Max size of the membership set: 2^20 = 1,048,576 leaves"}),"\n"]}),"\n",(0,a.jsx)(s.h3,{id:"metrics",children:"Metrics"}),"\n",(0,a.jsxs)(s.ul,{children:["\n",(0,a.jsx)(s.li,{children:"Time to sync the whole tree: 4 minutes"}),"\n",(0,a.jsx)(s.li,{children:"RPC calls: 702"}),"\n",(0,a.jsx)(s.li,{children:"Number of leaves: 2,653"}),"\n"]}),"\n",(0,a.jsxs)(s.p,{children:["One can argue that the time to sync the tree at the current state is not ",(0,a.jsx)(s.em,{children:"that"})," bad.\nHowever, the number of RPC calls is a concern,\nwhich scales linearly with the number of blocks since the contract was deployed\nThis is because the implementation fetches all events from the contract,\nchunking 2,000 blocks at a time.\nThis is done to avoid hitting the block limit of 10,000 events per call,\nwhich is a limitation of popular RPC providers."]}),"\n",(0,a.jsx)(s.h2,{id:"proposed-solution",children:"Proposed solution"}),"\n",(0,a.jsx)(s.p,{children:"From a theoretical perspective,\none could construct the merkle tree on-chain,\nin a view call, in-memory.\nHowever, this is not feasible due to the gas costs associated with it."}),"\n",(0,a.jsxs)(s.p,{children:["To compute the root of a Merkle tree with ",(0,a.jsxs)(s.span,{className:"katex",children:[(0,a.jsx)(s.span,{className:"katex-mathml",children:(0,a.jsx)(s.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,a.jsxs)(s.semantics,{children:[(0,a.jsx)(s.mrow,{children:(0,a.jsxs)(s.msup,{children:[(0,a.jsx)(s.mn,{children:"2"}),(0,a.jsx)(s.mn,{children:"20"})]})}),(0,a.jsx)(s.annotation,{encoding:"application/x-tex",children:"2^{20}"})]})})}),(0,a.jsx)(s.span,{className:"katex-html","aria-hidden":"true",children:(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"0.8141em"}}),(0,a.jsxs)(s.span,{className:"mord",children:[(0,a.jsx)(s.span,{className:"mord",children:"2"}),(0,a.jsx)(s.span,{className:"msupsub",children:(0,a.jsx)(s.span,{className:"vlist-t",children:(0,a.jsx)(s.span,{className:"vlist-r",children:(0,a.jsx)(s.span,{className:"vlist",style:{height:"0.8141em"},children:(0,a.jsxs)(s.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,a.jsx)(s.span,{className:"pstrut",style:{height:"2.7em"}}),(0,a.jsx)(s.span,{className:"sizing reset-size6 size3 mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:"20"})})})]})})})})})]})]})})]})," leaves it costs approximately 2 billion gas.\nWith Infura and Alchemy capping the gas limit to 350M and 550M gas respectively,\nit is not possible to compute the root of the tree in a single call."]}),"\n",(0,a.jsxs)(s.p,{children:["Acknowledging that ",(0,a.jsx)(s.a,{href:"https://polygon.technology/blog/polygon-miden-state-model",children:"Polygon Miden"})," and ",(0,a.jsx)(s.a,{href:"https://penumbra.zone/blog/tiered-commitment-tree/",children:"Penumbra"})," both make use of a tiered commitment tree,\nwe propose a similar approach for RLN."]}),"\n",(0,a.jsx)(s.p,{children:"A tiered commitment tree is a tree which is sharded into multiple smaller subtrees,\neach of which is a tree in itself.\nThis allows scaling in terms of the number of leaves,\nas well as reducing state bloat by just storing the root of a subtree when it is full instead of all its leaves."}),"\n",(0,a.jsx)(s.p,{children:"Here, the question arises:\nWhat is the maximum number of leaves in a subtree with which the root can be computed in a single call?"}),"\n",(0,a.jsxs)(s.p,{children:["It costs approximately 217M gas to compute the root of a Merkle tree with ",(0,a.jsxs)(s.span,{className:"katex",children:[(0,a.jsx)(s.span,{className:"katex-mathml",children:(0,a.jsx)(s.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,a.jsxs)(s.semantics,{children:[(0,a.jsx)(s.mrow,{children:(0,a.jsxs)(s.msup,{children:[(0,a.jsx)(s.mn,{children:"2"}),(0,a.jsx)(s.mn,{children:"10"})]})}),(0,a.jsx)(s.annotation,{encoding:"application/x-tex",children:"2^{10}"})]})})}),(0,a.jsx)(s.span,{className:"katex-html","aria-hidden":"true",children:(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"0.8141em"}}),(0,a.jsxs)(s.span,{className:"mord",children:[(0,a.jsx)(s.span,{className:"mord",children:"2"}),(0,a.jsx)(s.span,{className:"msupsub",children:(0,a.jsx)(s.span,{className:"vlist-t",children:(0,a.jsx)(s.span,{className:"vlist-r",children:(0,a.jsx)(s.span,{className:"vlist",style:{height:"0.8141em"},children:(0,a.jsxs)(s.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,a.jsx)(s.span,{className:"pstrut",style:{height:"2.7em"}}),(0,a.jsx)(s.span,{className:"sizing reset-size6 size3 mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:"10"})})})]})})})})})]})]})})]})," leaves."]}),"\n",(0,a.jsxs)(s.p,{children:["This is a feasible number for a single call,\nand hence we propose a tiered commitment tree with a maximum of ",(0,a.jsxs)(s.span,{className:"katex",children:[(0,a.jsx)(s.span,{className:"katex-mathml",children:(0,a.jsx)(s.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,a.jsxs)(s.semantics,{children:[(0,a.jsx)(s.mrow,{children:(0,a.jsxs)(s.msup,{children:[(0,a.jsx)(s.mn,{children:"2"}),(0,a.jsx)(s.mn,{children:"10"})]})}),(0,a.jsx)(s.annotation,{encoding:"application/x-tex",children:"2^{10}"})]})})}),(0,a.jsx)(s.span,{className:"katex-html","aria-hidden":"true",children:(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"0.8141em"}}),(0,a.jsxs)(s.span,{className:"mord",children:[(0,a.jsx)(s.span,{className:"mord",children:"2"}),(0,a.jsx)(s.span,{className:"msupsub",children:(0,a.jsx)(s.span,{className:"vlist-t",children:(0,a.jsx)(s.span,{className:"vlist-r",children:(0,a.jsx)(s.span,{className:"vlist",style:{height:"0.8141em"},children:(0,a.jsxs)(s.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,a.jsx)(s.span,{className:"pstrut",style:{height:"2.7em"}}),(0,a.jsx)(s.span,{className:"sizing reset-size6 size3 mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:"10"})})})]})})})})})]})]})})]})," leaves in a subtree and the number of subtrees is ",(0,a.jsxs)(s.span,{className:"katex",children:[(0,a.jsx)(s.span,{className:"katex-mathml",children:(0,a.jsx)(s.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,a.jsxs)(s.semantics,{children:[(0,a.jsx)(s.mrow,{children:(0,a.jsxs)(s.msup,{children:[(0,a.jsx)(s.mn,{children:"2"}),(0,a.jsx)(s.mn,{children:"10"})]})}),(0,a.jsx)(s.annotation,{encoding:"application/x-tex",children:"2^{10}"})]})})}),(0,a.jsx)(s.span,{className:"katex-html","aria-hidden":"true",children:(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"0.8141em"}}),(0,a.jsxs)(s.span,{className:"mord",children:[(0,a.jsx)(s.span,{className:"mord",children:"2"}),(0,a.jsx)(s.span,{className:"msupsub",children:(0,a.jsx)(s.span,{className:"vlist-t",children:(0,a.jsx)(s.span,{className:"vlist-r",children:(0,a.jsx)(s.span,{className:"vlist",style:{height:"0.8141em"},children:(0,a.jsxs)(s.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,a.jsx)(s.span,{className:"pstrut",style:{height:"2.7em"}}),(0,a.jsx)(s.span,{className:"sizing reset-size6 size3 mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:"10"})})})]})})})})})]})]})})]}),".\nTherefore, the maximum number of leaves in the tree is ",(0,a.jsxs)(s.span,{className:"katex",children:[(0,a.jsx)(s.span,{className:"katex-mathml",children:(0,a.jsx)(s.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,a.jsxs)(s.semantics,{children:[(0,a.jsx)(s.mrow,{children:(0,a.jsxs)(s.msup,{children:[(0,a.jsx)(s.mn,{children:"2"}),(0,a.jsx)(s.mn,{children:"20"})]})}),(0,a.jsx)(s.annotation,{encoding:"application/x-tex",children:"2^{20}"})]})})}),(0,a.jsx)(s.span,{className:"katex-html","aria-hidden":"true",children:(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"0.8141em"}}),(0,a.jsxs)(s.span,{className:"mord",children:[(0,a.jsx)(s.span,{className:"mord",children:"2"}),(0,a.jsx)(s.span,{className:"msupsub",children:(0,a.jsx)(s.span,{className:"vlist-t",children:(0,a.jsx)(s.span,{className:"vlist-r",children:(0,a.jsx)(s.span,{className:"vlist",style:{height:"0.8141em"},children:(0,a.jsxs)(s.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,a.jsx)(s.span,{className:"pstrut",style:{height:"2.7em"}}),(0,a.jsx)(s.span,{className:"sizing reset-size6 size3 mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:(0,a.jsx)(s.span,{className:"mord mtight",children:"20"})})})]})})})})})]})]})})]})," (the same as the current implementation)."]}),"\n",(0,a.jsx)(s.p,{children:(0,a.jsx)(s.img,{alt:"img",src:n(57576).A+"",width:"631",height:"381"})}),"\n",(0,a.jsx)(s.h3,{id:"insertion",children:"Insertion"}),"\n",(0,a.jsx)(s.p,{children:"When a commitment is inserted into the tree it is first inserted into the first subtree.\nWhen the first subtree is full the next insertions go into the second subtree and so on."}),"\n",(0,a.jsx)(s.h3,{id:"syncing",children:"Syncing"}),"\n",(0,a.jsx)(s.p,{children:"When syncing the tree,\none only needs to fetch the roots of the subtrees.\nThe root of the full tree can be computed in-memory or on-chain."}),"\n",(0,a.jsx)(s.p,{children:"This allows us to derive the following relation:"}),"\n",(0,a.jsx)(s.span,{className:"katex-display",children:(0,a.jsxs)(s.span,{className:"katex",children:[(0,a.jsx)(s.span,{className:"katex-mathml",children:(0,a.jsx)(s.math,{xmlns:"http://www.w3.org/1998/Math/MathML",display:"block",children:(0,a.jsxs)(s.semantics,{children:[(0,a.jsxs)(s.mrow,{children:[(0,a.jsx)(s.mi,{children:"n"}),(0,a.jsx)(s.mi,{children:"u"}),(0,a.jsx)(s.mi,{children:"m"}),(0,a.jsx)(s.mi,{children:"b"}),(0,a.jsx)(s.mi,{children:"e"}),(0,a.jsx)(s.mi,{children:"r"}),(0,a.jsx)(s.mi,{mathvariant:"normal",children:"_"}),(0,a.jsx)(s.mi,{children:"o"}),(0,a.jsx)(s.mi,{children:"f"}),(0,a.jsx)(s.mi,{mathvariant:"normal",children:"_"}),(0,a.jsx)(s.mi,{children:"r"}),(0,a.jsx)(s.mi,{children:"p"}),(0,a.jsx)(s.mi,{children:"c"}),(0,a.jsx)(s.mi,{mathvariant:"normal",children:"_"}),(0,a.jsx)(s.mi,{children:"c"}),(0,a.jsx)(s.mi,{children:"a"}),(0,a.jsx)(s.mi,{children:"l"}),(0,a.jsx)(s.mi,{children:"l"}),(0,a.jsx)(s.mi,{children:"s"}),(0,a.jsx)(s.mo,{children:"="}),(0,a.jsx)(s.mi,{children:"n"}),(0,a.jsx)(s.mi,{children:"u"}),(0,a.jsx)(s.mi,{children:"m"}),(0,a.jsx)(s.mi,{children:"b"}),(0,a.jsx)(s.mi,{children:"e"}),(0,a.jsx)(s.mi,{children:"r"}),(0,a.jsx)(s.mi,{mathvariant:"normal",children:"_"}),(0,a.jsx)(s.mi,{children:"o"}),(0,a.jsx)(s.mi,{children:"f"}),(0,a.jsx)(s.mi,{mathvariant:"normal",children:"_"}),(0,a.jsx)(s.mi,{children:"f"}),(0,a.jsx)(s.mi,{children:"i"}),(0,a.jsx)(s.mi,{children:"l"}),(0,a.jsx)(s.mi,{children:"l"}),(0,a.jsx)(s.mi,{children:"e"}),(0,a.jsx)(s.mi,{children:"d"}),(0,a.jsx)(s.mi,{mathvariant:"normal",children:"_"}),(0,a.jsx)(s.mi,{children:"s"}),(0,a.jsx)(s.mi,{children:"u"}),(0,a.jsx)(s.mi,{children:"b"}),(0,a.jsx)(s.mi,{children:"t"}),(0,a.jsx)(s.mi,{children:"r"}),(0,a.jsx)(s.mi,{children:"e"}),(0,a.jsx)(s.mi,{children:"e"}),(0,a.jsx)(s.mi,{children:"s"}),(0,a.jsx)(s.mo,{children:"+"}),(0,a.jsx)(s.mn,{children:"1"})]}),(0,a.jsx)(s.annotation,{encoding:"application/x-tex",children:"number\\_of\\_rpc\\_calls = number\\_of\\_filled\\_subtrees + 1"})]})})}),(0,a.jsxs)(s.span,{className:"katex-html","aria-hidden":"true",children:[(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"1.0044em",verticalAlign:"-0.31em"}}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"n"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"u"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"mb"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"er"}),(0,a.jsx)(s.span,{className:"mord",style:{marginRight:"0.02778em"},children:"_"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"o"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.10764em"},children:"f"}),(0,a.jsx)(s.span,{className:"mord",style:{marginRight:"0.02778em"},children:"_"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"r"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"p"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"c"}),(0,a.jsx)(s.span,{className:"mord",style:{marginRight:"0.02778em"},children:"_"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"c"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"a"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.01968em"},children:"ll"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"s"}),(0,a.jsx)(s.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,a.jsx)(s.span,{className:"mrel",children:"="}),(0,a.jsx)(s.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"1.0044em",verticalAlign:"-0.31em"}}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"n"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"u"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"mb"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.02778em"},children:"er"}),(0,a.jsx)(s.span,{className:"mord",style:{marginRight:"0.02778em"},children:"_"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"o"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.10764em"},children:"f"}),(0,a.jsx)(s.span,{className:"mord",style:{marginRight:"0.02778em"},children:"_"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.10764em"},children:"f"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"i"}),(0,a.jsx)(s.span,{className:"mord mathnormal",style:{marginRight:"0.01968em"},children:"ll"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"e"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"d"}),(0,a.jsx)(s.span,{className:"mord",style:{marginRight:"0.02778em"},children:"_"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"s"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"u"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"b"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"t"}),(0,a.jsx)(s.span,{className:"mord mathnormal",children:"rees"}),(0,a.jsx)(s.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,a.jsx)(s.span,{className:"mbin",children:"+"}),(0,a.jsx)(s.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,a.jsxs)(s.span,{className:"base",children:[(0,a.jsx)(s.span,{className:"strut",style:{height:"0.6444em"}}),(0,a.jsx)(s.span,{className:"mord",children:"1"})]})]})]})}),"\n",(0,a.jsx)(s.p,{children:"This is a significant improvement over the current implementation,\nwhich requires fetching all the memberships from the smart contract."}),"\n",(0,a.jsx)(s.h3,{id:"gas-costs",children:"Gas costs"}),"\n",(0,a.jsxs)(s.p,{children:["The gas costs for inserting a commitment into the tree are the same as the current implementation except it consists of an extra SSTORE operation to store the ",(0,a.jsx)(s.code,{children:"shardIndex"})," of the commitment."]}),"\n",(0,a.jsx)(s.h3,{id:"events",children:"Events"}),"\n",(0,a.jsxs)(s.p,{children:["The events emitted by the contract are the same as the current implementation,\nappending the ",(0,a.jsx)(s.code,{children:"shardIndex"})," of the commitment."]}),"\n",(0,a.jsx)(s.h3,{id:"proof-of-concept",children:"Proof of concept"}),"\n",(0,a.jsxs)(s.p,{children:["A proof of concept implementation of the tiered commitment tree is available ",(0,a.jsx)(s.a,{href:"https://github.com/vacp2p/rln-contract/pull/37",children:"here"}),",\nand is deployed on Sepolia at ",(0,a.jsx)(s.a,{href:"https://sepolia.etherscan.io/address/0xE7987c70B54Ff32f0D5CBbAA8c8Fc1cAf632b9A5",children:"0xE7987c70B54Ff32f0D5CBbAA8c8Fc1cAf632b9A5"}),"."]}),"\n",(0,a.jsx)(s.p,{children:"It is compatible with the current implementation of the RLN verifier."}),"\n",(0,a.jsx)(s.h2,{id:"future-work",children:"Future work"}),"\n",(0,a.jsxs)(s.ol,{children:["\n",(0,a.jsx)(s.li,{children:"Optimize the gas costs of the tiered commitment tree."}),"\n",(0,a.jsx)(s.li,{children:"Explore using different number of leaves under a given node in the tree (currently set to 2)."}),"\n"]}),"\n",(0,a.jsx)(s.h2,{id:"conclusion",children:"Conclusion"}),"\n",(0,a.jsx)(s.p,{children:"The tiered commitment tree is a promising approach to reduce the number of RPC calls required to sync the tree and reduce the gas costs associated with computing the root of the tree.\nConsequently, it allows for a more scalable and efficient RLN verifier."}),"\n",(0,a.jsx)(s.h2,{id:"references",children:"References"}),"\n",(0,a.jsxs)(s.ul,{children:["\n",(0,a.jsx)(s.li,{children:(0,a.jsx)(s.a,{href:"https://github.com/rate-limiting-nullifier/circom-rln",children:"RLN Circuits"})}),"\n",(0,a.jsx)(s.li,{children:(0,a.jsx)(s.a,{href:"https://github.com/vacp2p/zerokit",children:"Zerokit"})}),"\n",(0,a.jsx)(s.li,{children:(0,a.jsx)(s.a,{href:"https://rfc.vac.dev/vac/32/rln-v1",children:"RLN-V1 RFC"})}),"\n",(0,a.jsx)(s.li,{children:(0,a.jsx)(s.a,{href:"https://rfc.vac.dev/vac/raw/rln-v2",children:"RLN-V2 RFC"})}),"\n",(0,a.jsx)(s.li,{children:(0,a.jsx)(s.a,{href:"https://hackmd.io/7cBCMU5hS5OYv8PTaW2wAQ?view",children:"RLN Implementers guide"})}),"\n",(0,a.jsx)(s.li,{children:(0,a.jsx)(s.a,{href:"https://research.logos.co/rlog/rln-anonymous-dos-prevention",children:"Strengthening Anonymous DoS Prevention with Rate Limiting Nullifiers in Waku"})}),"\n"]})]})}function o(e={}){const{wrapper:s}={...(0,t.R)(),...e.components};return s?(0,a.jsx)(s,{...e,children:(0,a.jsx)(m,{...e})}):m(e)}},28453:(e,s,n)=>{n.d(s,{R:()=>r,x:()=>l});var i=n(96540);const a={},t=i.createContext(a);function r(e){const s=i.useContext(t);return i.useMemo((function(){return"function"==typeof e?e(s):{...s,...e}}),[s,e])}function l(e){let s;return s=e.disableParentContext?"function"==typeof e.components?e.components(a):e.components||a:r(e.components),i.createElement(t.Provider,{value:s},e.children)}},51049:e=>{e.exports=JSON.parse('{"permalink":"/rlog/rln-light-verifiers","source":"@site/rlog/2024-05-03-rln-light-verifiers.mdx","title":"Verifying RLN Proofs in Light Clients with Subtrees","description":"How resource-restricted devices can verify RLN proofs fast and efficiently.","date":"2024-05-03T12:00:00.000Z","tags":[],"readingTime":4.82,"hasTruncateMarker":true,"authors":[{"name":"Aaryamann","twitter":"p1ge0nh8er","github":"rymnc","key":"p1ge0nh8er","page":null}],"frontMatter":{"title":"Verifying RLN Proofs in Light Clients with Subtrees","date":"2024-05-03T12:00:00.000Z","authors":"p1ge0nh8er","published":true,"slug":"rln-light-verifiers","categories":"research","toc_min_heading_level":2,"toc_max_heading_level":4},"unlisted":false,"prevItem":{"title":"RLN-v3: Towards a Flexible and Cost-Efficient Implementation","permalink":"/rlog/rln-v3"},"nextItem":{"title":"Strengthening Anonymous DoS Prevention with Rate Limiting Nullifiers in Waku","permalink":"/rlog/rln-anonymous-dos-prevention"}}')},57576:(e,s,n)=>{n.d(s,{A:()=>i});const i=n.p+"assets/images/light-rln-verifiers-f801999160884be6a1223ee7d76cebcf.png"}}]);