Shrubs - A New Gas Efficient Privacy Protocol (Devcon5)

[Applause] everyone let's get started the my name is miracle chef Smith there we talked about shrubs some new suits have style gas efficient privacy protocol it's a mr. joint work with selling herbs and matter labs with a public folks first of all like privacy wine shops at all so maybe this is some quick context so seller is essentially a mobile-first and a theory which allows us to build a user experience like this and stove it has a lot of focus on like planked we use to change we have a stable point that's back to park by eat which is why it's relevant to the community and then we have a way to send a mistake phone numbers so all of that means that you want to send the payment to a friend say you want to kiss him back or coffee you can find them in your contact list and since hello maybe central that's where we spend say 500 dollars to them and since it's 2019 of course emoji and uncritically to pay for this transaction using the stable target itself and so the whole experience is quite quick it's fully decentralized this is going to go like mine it's like my protocol and so it allows you to recreate a venmo or PayPal experience that is fully permissionless will appear here so that's though and given that it has this really big focus on some of the things that are useful as a medium of exchange sending stable value we hypothesize that privacy is actually even more important for such a network Bank for points that are primarily store of elements and so we spent a fair amount of time thinking about that privacy or so and again solo is here a minute passed the DMV so everything that so we have three goals we wanted to make the balances of these reductions only private we didn't want the ability we wanted to keep the recipient and send their addresses as well isn't that common today in other theory based privacy no solutions and then finally we wanted all of this to work really well on mobile again it's mobile first so we want to look at seek apps and start reporting any cash into and we quickly run into a few issues so everyone the gas cost is perhaps not surprisingly quite high and number two the mobile support it's actually not that great except for this talk most our focus on the former and just kind of things a little bit about possible solutions for the light so maybe just some super quick background on Z cash just to get everyone on the same page so NC captures a number of operations one of which is the stealing operation so that's when you take one public the SEC and eternities for one private sector lean operation the way that you do that is you create a serial number and then you sent us and running this from somewhere and you can compute a commitment to that serial number yeah and then you create a public transaction that shares that commitment while spending and one sec and the miners will add that protection will take that SEC put it into a escrow pool but that's basically the private point and then adds this commitment to what's known and once that came in is a member country then it exists and that ones that exists in this private world of succession so here we go we have that so mixed up how do you then spending for this private point I think one of the easier things to understand is how do you turn it back into a public point so that's called shooting and I should have actually existed zero cash paper it's actually a little more than this but as we're turning this back into a public asset tea either side you to reveal the serial number to your commitment so let's assume we're using this amendment over here and then in your knowledge you have to prove that you know of surroundings you know of our such that this commitment cm appears in this and the way you do that is you construct a vertical path that goes up to the roof and inside it's not circuit if I could prove that this exists and then other full nodes or miners would then think this proof verified and they verified by giving them to prove the same are both leaders themselves and if the proof verifies then they add the serial number that you just revealed earlier to what's another fire step so that you can't spend that commitment again and then gives you the ones escrow it's be back of the private point and so if you wanted to them exactly privately you're in effect doing the deshielding operation in the shielding operation back-to-back so you first improve that you have one of these commitments and you create a new commitment usually it's not more or less made sense so why is this you know the answer is it's not difficult but it is expensive so if you were to use a tree that's around 32 above the time then this is quasi - news today he recommends a bigger tree but see - was being a steadily increasing their decides with every upgrade but if you were to have a tree of this height then you would require around 1.7 million gasps just to make an insert operation into this train so not even can't even kind of gas you need to verify the actual proof and this is assuming you're using the MC hash function in which we had to use in order to have official proving times devices so if you shot six this would be cheaper but it would just be very very expensive actually construct the proofs of constructor as actions on your phone so we've put them in C in our contract and if you include that and it takes everything gets it and this is even with optimizations to the J structure it's a bit of time did I make this quite efficient so again why is it expensive well if you insert one of these leaf nodes you have to compute the hashes going all the way up to the root and so that you can update the and that requires each ashes and depending how you're storing the tree and optimizing it's potentially up to each storage updates which is expensive and then of course as you make them to be bigger this nation support more total transactions and more expensive so how do we improve on this we came up with drugs and the basic idea is which we call a miracle shrub tree and in this destruction of the tree is not defined by the room but it's instead defined by the path to the right most non empty so that means to me basically the frontier of this tree that were filling from the left and going to the right and as an optimization instead of storing that entire path since some of the notes on that path may not have children on their right side we can actually store fewer notes and all page notes and so we only store in those units that actually calculate that's not responding and we call these notes required to reconstruct this this path adds shrubs and we call them that because if you include the path that's a bit like a stroke not quite a tree and so what does a proof look like you can this new beta structure so you basically have to construct the vertical proof that doesn't end up at the root but instead ends up at this frontier town so say that we want to but this note is part of the part of this site and then you construct the merkel path that doesn't go with a bitter an eclectic ghost to this note which is part of the frontier I need to do that you need this no just note that and verify that it matches what's there and then if you want to verify this proof you need to know the frontier one side of knowing just the old frontier or again s optimization the strobus that you can use to generate definitely so let's look at another example say that you want to verify this guy this guy go all the way up to the top well intersect the frontier and that's fine the root is part of the frontier as well works just before you just in my notes as part of your move and so in fact what we're doing is we're trading off the amount of work that you have to do to perform these inserts with the work that you have to do to verify these markers to verify which will prove you have to provide more public inputs which makes the verification a little bit more expensive but as well find that the trade off protection well worth it so it all comes down to the cost of inserts so what is an insert that look like and that was the expensive thing in traditional medical treatment say that we want to insert this over here so we just insert it into the next love I'm currently building the street from that's right and then we have to compute all the hashes and update all of the shrubs that are needed to construct this you frontier that exists and so look these are the shrubs needed to construct a frontier before we edit this note and these are the ones that are needed here after we have noted and since the only new struggle is that will actually snowed that we have already added you actually only need one updating zero ashes performance and sir that's pretty efficient and that translates into very good SATs now we're not going to be so lucky so let's imagine we have to update this and pick this we need compute the hash of this and the hash of this passionates and so in the expected case you end up having to do about 1.5 updates and about 1 hash on average so obviously their worst case comes by seller - or / drugs just questions it see the figure when you think that the verifying like you know you know whether you're in the right subtree here in the left subtree here is our fighter fire only has to fight as a publican but to proof the actual shrubs you need to construct the frontier and then in zero knowledge you're actually gonna prove that your node is connected so the verifier doesn't actually isn't able to wear folks coming back reforms we implemented a few variants of different countries and been to Russia for a free type of 32 levels and the basic implementation surprisingly is slow requiring 1.8 million guests or every insert it doesn't matter where in the GB you're inserting you're always going to the root of the tree and so it's always expensive then in the optimized case we're able to save a little bit of time or gas 1.

7 million got and then it rubs the worst a 16.7 but in the best case that can be as low as 45,000 absent is quite incredible and then in the mean case on average that's just under that's all just go for it and so the next question is okay so if you want to use this data structure and if you were to implement see catch what would the actual cost of agents actually mean and so we implemented the verification of the piece of that we brought six teams and we put these numbers so on average around 10,000 depending on the inputs you have to your for operation so you can have one or two inputs you're gonna have to add one or two entries to nullify ourselves for this we take around 26,000 or to prevent depends on return and then next we have to pre-process the in the public importance so in this case the public inputs for now these shrubs so this actually costs more than before before we only had but we've yet key one 108 this is gonna be a lot cheaper over the next five pork and so it's still pretty reasonable around 300,000 and finding out to do the actual verification which requires around for pairing operations that believe which adds another profit and so the total cost is around five hundred thousand pending on from you puts you up again which is about 2x more expensive and a step but you get no eligibility so all over here and Senator addresses right now right now we also look at that what this would look like a punk we didn't implement this like we did across 16 but we did his estimates and the reason is interesting because the processing of the public inputs it's a lot cheaper you don't have to do exponentiation and so this is actually quite cheaper unfortunately this ends up being a fair amount more expensive so the overall price overall cost of the gas is high country you're gonna have the less I guess that in here or versus your here that's Washington quite a bit more masculine so generally are hopeful that with some transitions we can lower this and potentially cheaper than she brought 16 with an even length I Oh so I mentioned mobile what about it so the nice thing is by using them see the tripping times are quite short that's quite elegant so you can construct these transactions in just a few seconds on a $200 phone but unfortunately for that my client so it's hard to know which productions are reviewable since they are encrypted you would have to try to decrypt every transaction in every block to find which is actually smashing so that's my client and it's also hard to know when you're hidden in which to be to construct those working groups going up to the frontier a full note in figured it's uh pretty easily as they see every transaction they maintain the piece of the tree that they care about the Constructors groups but my client you wouldn't want to actually various will note find those notes because I would reveal which so one solution is to use operators and to introduce the concept of a routine decryption key would allow for twice encrypt all transactions Center for you without even the transactions see the balances and the sender's trust any questions so the sides of the they've been a guess that you have to approve and I guess that you have to pay will be different depending on where you are in that country and so one way of actually making this a little bit more uniform is to use a gas token so that everyone contributes more or less the same on a gas and if you happen to be unlucky and go all the way to the room then mean on that guest or more than other folks equation it's not about the size of the pool it's more about the size and for you under the Bible as the ontology deter always fast-paced action that's what puppetry [Music] every joke have any differences I'm married so but I'm not the Restless chat why so you get slightly it was inspired by it's slightly different Boston but concept where you always come to please sighs a minute sit in or a Taser in a numerical Trina Merkley tree is a cryptographic accumulator which gives you a constant size commitment to vector phase and from this commitment is the root of the tree which wraps is also a generic accumulator with v with a with a with a commitment size proportional to this height of the tree and it's determined by the edge of a of the treatment of the entire edge with which you have the root the next and next element on the right yes and this edge is your commitment and you will have to pass this commitment so like all the items on the edge to the start but since we have a tree of fixed size we just dig the size of like do to it power 32 this size commitment will be also fixed which is just logarithm of this we should send it which which we can we can pass as inputs to the start or we can also optimize to just compress on a name in a hash thanks guys I think that's time but the outside [Applause] you