ZK8: Tiered Merkle Topiary in Rust – finch – Penumbra Labs

Transcript

foreign we want ZK to be quick right but so what does that mean um when you say you want something to be fast you wonder like for whom and to do what so uh there's a couple of different options that might be available for this um a lot of people have spent a lot of time doing research and extremely excellent research on trying to make sure that clients can generate proofs efficiently there's some really wonderful work on that subject but also like we want to make sure that nodes can verify proofs efficiently we want to make sure that nodes can produce updated

state that can be made use of quickly and we want to make sure that clients can consume updated State quickly like there's an entire Pipeline and a network of things that need to happen in order for a fully integrated ZK system to be efficient for all people who participate in it um so what we observed in penumbra is that for a ZK blockchain like ourselves most users spend most of their time doing things other than generating proofs so uh if that's the case what are they doing um so I want to take a second and walk through what happens in the entire architecture of penumbra and and focus

on what it is that we're spending the most time doing in most use cases so um this is uh what it looks like conceptually we've broken down the client in the full node so penumbra to take a step back uh penumbra uh from the get-go we wanted to make sure that we designed things in a way that we prioritized clients as full first-class citizens of our ecosystem we wanted to make sure that we can run in restricted Computing environments like processors that are not as fast as a big desktop or a chunky server um like maybe mobile phones or a browser extension in wasm or things like that

um so we've broken out our client into a couple of different pieces we've got the custody service which has a particular interface that it talks to the wallet logic over um and that interface means that we can swap out different kinds of custody we've got a view service which has only the capability of viewing your transactions and not making transactions on your your behalf and that tells the wallet logic in clear text what things you're actually able to do and the only interface between the client and the rest of the network is that it receives viewing information in encrypted form from the penumbra Daemon and then it transmits transactions back to the

network by broadcasting them directly to tendermint which we use as our consensus engine and tenderment is speaking to the rest of the network all the tender mints having a group conversation so most of the time uh when you're sitting and you're doing things you're not actually spending most of your computational effort on constructing transactions if you are a normal user there are some like outlying use cases where like you might be doing quite a lot of like really rapid transaction making if you're uh like doing specialized trading Bots and things like that but most users aren't going to be doing this most users are going to be doing this quite a lot they're going to

be downloading the history of the chain and they're going to be trying to synchronize it with their state um so sync is something that's really really important to get right and get fast in particular unlike a transparent blockchain you can't just query the chain to find out what's going on so like um every client has to maintain their own copy of private State that's relevant to them so that they can generate proofs and those proofs have to be generated based on their fragment of private state so this view service needs to be quite efficient so the status quo is that we use Poseidon hash which is a snark friendly hash that I suspect many of you have

heard of um Poseidon is really great it's very friendly for making efficient snark proofs but it's slow in software it's uh 100 to a thousand times slower than doing very efficient cryptographic caches that don't have to support snarks in a traditional Merkel tree design we have to insert every commitment into the tree sequentially because if you skip any then your root hash is going to be different so you can't parallelize and you can't accelerate by uh by summarizing the number of updates that you have to do um additionally when you make an insertion you have to compute many

hashes you have to compute all of the hashes all the way down from the point at which you insert the leaf of your tree all the way back up to the root every time that you insert um and of course if you have a fully integrated ZK system like this when the client is synchronizing you don't want to lose all of your progress if they control C or if the computer crashes or any of this so you want to be repeatedly checkpointing your state and if you don't have a tree that supports serializing it efficiently then you're repeatedly persisting the entire State over and over again as one giant blob so this is not great um and in particular this status quo punishes users when the network succeeds

which is sort of the opposite of what we'd actually like to be the case we'd like to reward users for the network actually being successful um so why is this true well um so as number of transactions increases then proportionately to that the amount of hashing effort that any client has to do increases not proportionate to your own effort but proportionate to the amount of transactions that are globally happening on the network because you need to process everyone's commitments that have ever happened um I argue that like the State of Affairs that should exist is that the effort that you spend on synchronizing your state should scale roughly with only the amount of activity that you yourself are performing it should not matter how much everyone else is doing

it should only matter basically how much you are doing so how could things be instead well the Poseidon hash is as I said start friendly but slow in software so we use a wider rate rate for for the Poseidon function to make the tree wider and shorter so that means that we're doing less hashing all the way down so originally in a conventional Merkle tree design we have to insert every commitment sequentially so instead we come up we came up with a tree design that lets us skip most of the commitments and construct subtrees in parallel rather than sequentially um this problem of having to compute

many hashes every time you do an insertion led us naturally to design the tree to have a lazy Frontier which avoids most of the work on every insertion so that you only compute the frontier when you actually need to calculate the root of the tree and then of course we have to persist that updated state so instead of persisting the entire tree every single time that we want a checkpoint to disk we just serialize an incremental slice that represents everything that's changed since the last checkpoint so uh this design that I've outlined the like conceptual properties of we call the tiered commitment tree and instead of giving you a lot more bullet points about how it works I want to give you a

live demonstration so that you can visualize what it looks like inside my head like when I was thinking about constructing this talk um I wanted to uh I wanted to give you an intuition for what it feels like to see this work because when I was designing this tree I had all these pictures I had all these shapes rotating around in my brain and I wanted to show you the shape rotation so that you can actually understand what's up so um let's uh let's zoom in and see what's up this is a commitment um a note commitment here um and this is its hash above it so I can insert um so as I'm inserting these things I'm

inserting some of them by remembering what they're uh what they are and I'm inserting some of them by just remembering their hash as you can see if I don't remember things then they just get summarized because this is a sparse tree after all but I always preserve the things that are remembered and let me just um uh let me just insert a bunch more you can see like we we have this sparse tree structure here now if I make a spend then I'm never going to need to prove anything more about that commitment so I can just forget about it like that and then we get some more abbreviation like this

Etc so you can see that this is a fragment down here that we're viewing of what the authentication path is down to for example this commitment which is the 1226 commitment of the zeroth block of the zeroth epoch and so you can read all of these numbers as being Epoch slash block slash commitment within that block um so the the I I said this data structure is called the tiered commitment tree and that's because we represent it as a three-tiered structure where we have blocks within epochs within the global tree um so let's zoom out a little bit and say this is the end of the block we've inserted all of the commitments that are

relevant to this block so we start a new block um and we start inserting some commitments like this and uh you know like that and so we're going along and we don't see any commitments that are relevant to us so we've gotten to the end of this block and then we finish the block and so the entire block becomes summarized by a root hash because the tree after all is sparse so why do we have to do all of that work right why did we have to insert all of these commitments only to summarize it by the root hash well this seems like uh like we've done more work than we actually needed to and in fact we have so the penumbra architecture commits the

intermediate root hash of every block into our public Merkle tree the jellyfish Merkle tree uh borrowed from the the DM blockchain um and so what that means is that client synchronization can just stream the root hashes of each block provided that you don't actually uh need to know what any of the commitments are you can just insert the root hashes of each block and that means that you can accelerate by performing only one hash per block instead of Performing you know 1226 hashes um this is you know very advantageous you'll notice that uh here there are

some like little dots that represent the parts of the tree that never ever got filled in we use a like a placeholder padding because every node has exactly four children um so zooming out a little bit more you can see that this is actually just the first Epoch of many so we can finish the epoch and then start a new one so we're doing some work in the epoch and maybe we don't have any commitments in these blocks um uh and say that we didn't have any commitments there either so we just summarized a lot of blocks right um well uh can't we just apply the exact

same logic again um and in fact we can apply the exact same logic again so let's just summarize the epochs instead of working on uh insert on building them directly so we can just do this instead streaming each Epoch route and doing one insertion for Epoch and if our epochs are you know multiple days in length then this means that you do maybe a few hashes like under a hundred hashes in order to construct the local copy of your state for an entire year of chain activity and this is where the claim of like four million times faster than uh than the naive way of doing it comes from if you really filled up the tree if you had completely full

blocks and completely full epochs then you'd be about 2 to the 32 faster doing it this way than doing it naively I think that's a pretty reasonable speed up um I'm relatively happy with that so you might be wondering why is the frontier pink and that's actually a very deliberate part of this visualization it's because the frontier we haven't actually computed the hashes of the frontier but let's say that we want to witness the root of the frontier well we need to compute the authentication path all the way up to be able to know what this root hash is but if we were doing this every time then we'd be doing a lot of repeated work so instead we just don't do it until we actually ask for

what that route is another point that I wanted to make is as I was saying before we do incremental serialization so as you can see here like suppose that we're at this point and I like put a commitment there and I insert a thousand more things so you'll see that like um the part to the left of what I just did this part is basically unchanged all of the hashes haven't changed because the only things that change are the things on the frontier which we don't compute until we're ready to compute them and the things that we add Anew so what that means is that if we can serialize incrementally only the things that have been added then we can persist things using the actual minimum amount

of rights to disk so this reduced write amplification in our test Nets by like about a hundred times faster when we implemented this so about now uh the way that the the status the current status quo is that we're synchronizing on our test net set about like 10 000 blocks per second on this MacBook Air and that's only taking advantage of sequential computation that abbreviates blocks into their block hashes not taking advantage of epoch acceleration not doing any parallel acceleration and in the future we're going to be integrating fuzzy message detection which will mean that instead of streaming and trial decrypting everything in order to do this now trial

decryption is much much cheaper than doing hash computation but it still costs something to download things from the network we have this fuzzy message message detection capability that we're going to use to delegate the scanning of your relevant commitments to a third party who can only give you like a probabilistic ZK Bloom filter over uh what things you've uh you've got to detect and then you can only stream those bits and construct your tree so we estimate that you should be able to just like synchronized like that once we've implemented all of that so we don't anticipate that the fmd capability is going to be ready as of when we launch the mainnet but that's an upgrade that

we can perform after the fact because all of the cryptography is already there so we've got orders of magnitude to get better than 10 000 blocks a second um so uh you know I had I had some backup slides here in case the live demo didn't work so I'm just going to real quickly Zoom through those here's a nice visualization of what I mean by the incremental insertion like the the difference between this and this is just this so we only serialize this so I want to change tracks real quickly and note that this is extremely fast right you know 10 000 block a second is pretty pretty reasonable when we go to mainnet which is going to be soon TM uh

this tree had better be correct right because it's not like we can do a database migration after the fact because everybody's state is uh you know shielded and private and so it would be really really difficult to actually change the way that this data structure works after we deploy we want to be really really sure that things are actually implemented well and perfectly correctly as best as we can assure we really like types at penumbra we're building everything in Rust and so the way that this tree is constructed is using types to really guide the tree to be constructed as perfectly as possible without having to write tests our type system prevents us from constructing any

invalid trees whatsoever so just sort of dropping into rustlingo a little bit we use recursively defined traits or like inductively defined traits on nested generic types to write these structure preserving traversals over precisely shaped trees so what that just means is that we've written down some very very precise types that say the tree is exactly this tall and there are no dangling paths and the frontier is exactly this kind of shape and the complete part of the tree is exactly this kind of shape so that it's impossible to even compile an implementation of this tree that doesn't actually match the structure that we wanted to have and then the only bugs

that we can really have that are left you know knock on wood are bugs related to Computing the hashes themselves which are pretty easy to test so here's an example of what I mean by using these really precise types I I have this little comment here we have these nested generic types that say uh a tree an individual tier is exactly eight uh eight nodes deep followed by a leaf so you can't have anything that's the wrong depth and this actually gives us an efficiency boost at runtime because you don't have to branch on whether you're at the bottom or not and then we enumerate all of the possible patterns of children that you

can have of a leaf and if you if you notice you'll see that there's no possibility that you can have a node that doesn't have children because if you don't have children then you should be folded into the node above you and summarized so you don't have any dangling uh branches and that's preserved by the property of how the tree is structured so I want to say uh you know thanks for paying attention to this little demo but before we get to questions I want to invite you to play with this yourself while we're doing questions if there's question time so I actually am hosting this live at nct.penumbra.com.zone and if you go here we've got this live tree that you can play with on this screen because this is

reflecting everything that everyone is doing right now and with that I'm happy to go to questions [Applause] yes so it's nct.panumbra.zone yes the way that you're minimizing how is in which way is that different from like just the American mountain range doesn't it I'm not familiar with that work but I would be fascinated to hear about it

I'd love to yeah oh yeah and I'll try to repeat the question if anyone asks okay great I see hands off the computer someone's doing it [Music] maybe it's more on the is this working yep maybe it's more on the implementation but

um you showed some of the rust code that you have it looks quite complex like is do you have an approach to simplify that with macros or something like that um so uh the the rest code that I showed you uh is some of the more complex parts of it um like we Define there's this one module that defines like what's the structure of a node and there's uh this uh one other module that has this like deeply nested type you could write a procedural macro to generate this stuff but I'm not sure that you would actually save on lines of code written um because uh you don't you'd written the procedural macro and the length of that would be basically as long as the code that you've written there and I'm not sure that it would actually clarify the code it is something that I thought

about um and I think that if we were to generalize this to a use case other than our own we'd really want to do that because I want to then you'd want to be able to say like how many tiers do you want and how tall is each tier Etc um and so uh like I it would be entirely possible to do this it's just that it wasn't the right cost benefit trade-off for us at the moment so you you demoed some type level programming I'm not actually familiar with what it means to define a trait recursively but there's um sort of a wave of blog posts I've seen in the last two years or so about typical programming that you can do in

Rust that's made possible by literally generic Associated types I'm curious what previous experience you guys brought to bear on technical programming since it seems like a really new trend in Rust and then also are you using this generally for any data structures that you define or is it used more pervasively a crossword clue basis and sort of what's the design um so okay there's there's a couple of embedded questions there um and I'm gonna go in reverse order um so uh one of the things that is a challenge for us to figure out um that we that we've been uh trying to fine-tune as we're building this thing we want the thing to be real and we want it to be real as soon as possible so that means that we want to rapidly prototype stuff

um and sometimes when you use too many types what that does is it just like pours epoxy over the entire structure of your code and then you can't really rapidly iterate because everything is like Frozen in place and you have to just like like smash it to bits and try all over again um so we we sort of take this balanced approach between like do we want to um do we do we want to like really nail down this design and get it perfectly right in this exact place which for the Merkle free design is absolutely what we need um but uh but for other places in the code we we're a little bit more lacks and then we sort of are going to take an iterative approach to freeze things and make them be more more well-typed and

more better encoded Etc so you had another question that was before that and that was about like what kinds of type level programming we're using so this doesn't use generic Associated types we're using the stable rust compiler and the the only real trick here is that if you have a nested generic type so like I was showing you with the like node of node of node of node Leaf instead of defining something as a recursive type you define it as a nested generic type where the recursive parameter of the or the generic parameter of the generic type represents the points of recursion and then you can write a trait where the trait depends on the trait being itself being implemented

for the type parameter and that allows you to have an implementation that does like static dispatch all the way down to the leaf and so you get this like inductive function that's defined over this precisely shaped structure cool thank you and we got time for Friday one more question I guess that's what that's a really easy one how like is the source open code uh the other way around is the code open source that's what I'm trying to ask the code is open source everything we do at penumbra is completely open source so you can go to github.com penumbra and

this is uh in the penumbra slash penumbra monorepo um under the TCT tiered commitment tree uh directory and I would love to hear any of your comments please email me and thank you [Applause]