Securely building and verifying Merkle Trees with Solidity and Javascript - Ernesto García

entered in YouTube previously. And yeah, let's just talk about that. So, basically OpenZeppelin, if you already uh if you don't know us yet, we do security for the blockchain space. Uh we published um open-source library that we maintain with the most uh of the the highest security standards out there. So, if you probably have done some solidity in the past, you probably know us, right?

So, cool. Um aside from that, in the middle middle uh middle week hackathon, we have some bounties for you to to take a look to. This is basically using our platform, which is Defender, uh and it's focused on developer security operations. So, you can use plug whatever um project you're making, and once you you you have it done in Defender, you're participating. It's quite easy to set up, and we have some templates for using it with serverless, but that is another topic.

Okay. So, as I mentioned, you may just you may already know us because of the library of contracts, but we also have some other open-source efforts. In these open-source efforts, you will see that we have some other libraries, and that's what we are going to talk about today, which is the Merkle tree library that we just released in past November. And I'm going to tell you about the reasons why we released this library, and a cool story about uh hacking Merkle trees, right? Cool.

So, before starting, um quick presentation of myself. My name is Ernesto Garcia. You can find me in Twitter with um Ernesto GNw. And also I worked at Twitter uh sorry, I worked at Google before as an intern. I worked at the Google Cloud and Google Chrome teams.

And now I work at OpenZeppelin as a smart contract developer. I work at the library, so if you have any question regarding to it, we can you can find us at at our booth, and I can answer you any question you have. Okay? So, let's get started um and let's start by asking this question, which is what is a Merkle tree? So, probably some of you already know what is a Merkle tree.

A Merkle tree is basically a data structure that allows us to save information in a compressed way in a smart contract, right? So, you don't need to put all of the information in the smart contract. You just have to put the root hash, and that is enough to verify that some element is part of this Merkle tree. Going to the definition is this one, and as you can see, it is a tree. This is very vague.

In which every leaf, of course there are leaves, is labeled with a cryptographic hash of a data block. What does this mean? Maybe you don't know because this is quite complex to to grasp at first. But let me tell you how Merkle trees work in a very simple way. So, we start with a set of data, which was called a data block in the definition.

And let's say we have elements from A to I, like A, B, C, D, including any piece of information, okay? So, by starting with this, we can hash the information that is in in that leaf and convert it to a piece of information that we can use for further merging each value. So, in this way, we can like build up a tree, as you can see, and this tree will have a root state in which the root state is the hash of all the values that were contained in the Merkle tree. Of course, not all of the information about the elements in the Merkle tree stay in the root state, especially because the root state is just like an identifier of the information that is in the Merkle tree, right? This is important because by using a root state, that is enough for you to verify information on chain.

And this is because one assumption that we have around hashes, which is that you cannot know the pre-image of a hash, which is what you put into a function of a hash, and in order to get something else, right? You cannot know it beforehand. Uh that's the way hash works. So, talking about hash functions, you will see, or maybe you already know, that a function is basically just a piece of information, or let's call it like a transition function in which you map some values from a domain into a co-domain, right? Um one of the main properties of these hashes is that the the inverse operation, which is like mapping from the co-domain to the domain, is not possible that easy.

Is Well, it's actually possible. It's just that it's not feasible, and and yeah, it would take ages. So, the idea is that a good hash it is assumed to have what we call um the preimage no no less resistance, which is that you don't know what to put in the hash in order to get a desired result on the other side. So, to put some graphics on that, this is the way the function work. You put some preimage, you hash it, and you get an image after that.

The opposite operation is what is not possible. So, we rely on this assumption for multiple operations using hash, and this has something to do with the Merkle tree, because in the Merkle tree you can start with the data, and then build up to the root of the Merkle tree, right? This is useful because in this way you can prove you have values with just doing a computation that is uh a log n of the total amount of elements in the Merkle tree. The interesting thing is that you cannot do the opposite. I mean, you cannot start with the root state, and then get the values by like, let's say, unhashing the root state.

That is not possible, and that is like all of the security around the Merkle tree, right? Cool. Let's talk about proofs, which is basically, now that you know how a Merkle tree works, now you have to publish probably a proof on chain using OpenZeppelin contracts on or any other tooling. So, in order to build a proof, we have to first define what is a proof for a Merkle tree, right? And a Merkle a Merkle proof for a Merkle tree works in the following way.

So, you basically start with a with a piece of information that you want to prove that is in a Merkle tree. And in this case is called B, and let's say it's a tuple between address and you you in 256. So, we take this value, we apply a hash function, and then that we have Now that we have this uh hash value of our original element, we can start building our tree. How is this done? In the following way.

We start with our hash value of B, and then we can get rid of C and D. Why? Because it's not completely related to the piece of information we want to know. So, we start by hashing the hash of B and the hash of A, which is part of the proof. Okay?

With these two, we get the third one, and now we need the hash of CD, which then we combine, and then eventually we get the root state. So, that is the way in which we can prove information about uh what information being in a Merkle tree. And this is amazing because it can be done in um log n of the total amount of of elements, which is quite handy when you are like managing a lot of information that you have to put on chain. Okay? So, this is the root state, and if you compare it to what to what's on chain or to what you have put in a smart contract, you can validate that information is correct.

So, this is basically how they work. And some things to consider is that in order to make a proof, you have to make an array of values. As you can see, these are These are the values that we needed starting from B to combine with A and then with CD. So, you have a proof that is not the total amount of elements, but is good enough to process on chain. The way you process it is, as I mentioned, you take the leaf, you hash it, and then you combine the next hashes.

So, you end up having this root. Okay? Amazing. So, now let's uh have a look into what a proof like this looks in Solidity because it's quite different, especially when you are like working with JavaScript because you have like a library that is uh creating Merkle proofs or hashes of like any function that you want, but maybe the format and the types of these uh pieces of information don't match directly with whatever is in Solidity, right? So, we identified that as a problem and a a big problem from the developer experience standpoint.

So, basically we decided to like do some research on what are the main pain points around building Merkle trees and verifying on chain. And basically, what we uh what we noticed is that there is a big mismatch between the information that is in the let's say front end, if you have one and you're using JavaScript, you have to interact with values that are Solidity native. Like, for example, a bytes32, which is representing uh the array of proofs uh well, not proofs or the path to make the Merkle proof, right? So, this is not like directly mapped to JavaScript, and this is something that especially beginners don't know exactly how to translate because you have data types in JavaScript, and then you have different data types in Solidity. So, what we figured out is that number one, developer experience is complex.

Number two, there is no connection between the types. I mean, there are numbers in JavaScript, but we all have headaches with big number, for example, and how do you convert a big number into a bytes32 in a secure way. That is one question that you might have if you are starting with this. Um aside from that, we found out that that the interoperability with the tooling that is already used, such as ether yes, is also not quite uh familiar, especially for for this kind of uh verification process. And finally, the most important thing, which is the second pre-image attack that I'm going to tell you about next.

So, cool. Uh right now, we know how Merkle trees work. So, let's say that we have a piece of information called I, right? The way we prove that is in the Merkle tree is by hashing this function, and this is what we uh call the pre-image of the initial hash, right? So, we take the I value, we hash it into HI, and then look at this.

We have a second pre-image for the next uh the next hash. Why? Because we already know what H of E and H of I is, because that is part of the proof, right? So, the problem that comes with this is that someone can actually do something like this, which is taking one of the nodes and use it to prove information that is not actually true, right? You just have to provide this node and the proof uh or the path to build uh a fake proof using it.

So, although in most of the contexts in which this is a problem, it is not actually malleable because it uh it it usually depends on the message that sender. So, you have to figure out a message that sender that for some reason has to um has the same like uh configuration as uh one of the pre-pre-image you have. But, it still there is this um let's call it like at least probable enough to take care of it, right? So, we didn't found find any contract out there using these these mechanisms. So, this is basically just a theoretical attack.

So, please don't go and try to figure out how to hack someone using this, right? But, the problem is that yes, in fact, we have a flaw. It's something that is not quite uh evident for the user, especially when you are just like trying to do an NFT drop or something. You don't care about preimages and things like that, right? So, based on that, uh we decided to Okay, let's take a look to what is the common process of uh Merkle distributions for an NFT or or or an airdrop, and it always looks something like this, right?

You have a function, let's call it claim or let's call it mint of or how however you want, that is taking a proof, and this proof is validated using our uh our Merkle proof library that we have in OpenZeppelin, right? So, so far, so good uh until this point, but the problem is that uh as you can see, in this case, someone can like mint 100 tokens because they have a proof that is an actual valid proof, but since the second pre-image is known, you can actually use these two to mint a ridiculous amount of tokens that is produced by the randomization of the hash function, right? So, this is as as I said, this is not that useful because you will end up sending the tokens to an address that is uh unusable. You don't have the private key. But, if you think about it, you are like inflating um the supply of a system, which is not ideal, and of course, we want to avoid that um that problem.

So, the what happened is that we decided to like close the gap between what is going on in JavaScript and people that is building Merkle airdrops or NFT drops, and like make a whole end-to-end process easy for developers to use. So, this is how we came up with this library, and this library is basically an end-to-end approach of using and validating Merkle trees. So, you can take a look at Uh it is published on NPM. It's already like quite used by the community. Uh and also, like we have figured out that multiple people find it like really easy to use.

It's way better than other alternatives, and it's pretty straightforward when you're working with smart contracts. So, the way it works is um Oh, sorry. Some properties first and design decisions we we take before creating the library. So, number one, we decided that the tree should be shaped as a complete binary tree. This means that the only part that is incomplete of the tree is the the the last level of the tree.

And this is for security reasons. There are some considerations around uh unbalanced Merkle trees that you may want to avoid. So, what we did is, okay, let's just balance this um this Merkle tree automatically. Whenever you are adding information using the library, that's already done. So, you don't have to take care about it.

Uh point number two, the leaves are are sorted. And this is because the order in which you hash the things matters. So, basically, people can make mistakes in which they hash values in a different order, and they are not able to get a correct proof, or let's let's call it they publish a proof that is incorrect on chain, and they cannot change it anymore, okay? So, it's I mean, the developer experience of that, as I said, was like not the best one. So, right now, if you use this library, you will get everything sorted out for you.

Uh point number three is that the leaves are the result of uh of an ABI encoding, which means that everything that you do is in JavaScript is going to be like fully compatible with anything you do on Solidity. So, you have native support uh between conversion of types, or you can use directly the types that you will use in solidity such such as an address or an integer and you in 256 could be. Also, we're using the Keccak-256 function that is already built in in most of the tooling and that is also already built in in Ethereum. There is a precompile for that so people can just use it. And finally, the leaves are double hashed and this is to prevent the second preimage attack and I'm going to explain how this like uh removes that possibility from the scope.

So, how is this prevented? Basically, we take a piece of information and instead of doing one hash we do two. Why? Because if you hash it twice, it means that there is a fundamental difference between a node that is a leaf and a node that is an intermediary node. Why?

Because every leaf is hashed twice so if you try to use a a second preimage attack, you will just hash it once and the system will only do it once, right? So, the whole idea is like let's hash it again so people don't know what the preimage is. That's it. Okay, it's already built in. It's usually one design decision that developers needs to make before creating system like that so we decided to use put it built in in the library.

Um to exemplify uh ex exemplify yeah, how this works. Basically, we have a the same example that I show you in which you have a piece of information called A. You hash it and then you get a preimage. But the thing is this preimage is double hashed as you can see. So, right now if you take this same example, you will see that the next hash is not going to match because the first uh hashing in the claim function that you have in solidity will hash it twice.

So, there will be a mismatch naturally and this avoids any attack like that. Uh let me go back here because I see some people is confused. But as you can see here in line there is no number of lines, but here you can see we are just hashing once. If we hash twice, we avoid any pre-image attack because no pre-image is known for a double hash. You see what I mean?

There is only known pre-image double hash for the leaf values, which is which are the values that that we care about. Okay? Going back to this I hope now this makes more sense. Is it? Cool.

Amazing. So, the verification will basically fail because yeah, if you try to hash twice pre-image that is supposed to be hash once is not going to work. That's it. Cool. So, in this case what we recommend from now on is that instead of just hashing once in your claiming function, you don't have to change anything but this line.

As you can see the leaf calculation is changed by double hashing. And if you are asking why do we are using these bytes that concat is just basically to avoid memory because otherwise you have to copy into memory and then copy again. And yeah, this is an easy way and easy trick to not copy into memory. Cool. So, now that we have this leaf, we can use it with a Merkle proof library we have as we have done before without any other change, which is nice.

Okay. I already explained this, but you can take pictures if you want. But this is basically the whole idea behind creating a new JavaScript library for this is that you do not have to mess with this. Nice. And also another feature and this is an interesting thing to talk about is that property based testing has been quite hard I would say in the last couple years.

And we are also trying to to add a uh to integrate that into our development process. So, this library was also created and tested with uh property-based test, which is known for many of you as fuzzing, probably. And there are some cool libraries out there that you can use to fuzz things in JavaScript, which is nice because you always like usually fuzz everything that is in the smart contract, but you don't do the same with JavaScript. And usually JavaScript is also messy, right? Uh especially in front ends and data conversions, there are so many things that can go wrong in that place.

So, fuzzing in this context is also useful, especially for Merkle trees. Cool. So, in this context, we made a Merkle tree library to match exactly with the Merkle proof library that we have in OpenZeppelin contracts, and everything seems so easy since it is designed like that. Uh here's an example of how you can build a tree. As you can see, a step number one is adding values to a an array, and each one of these uh array elements is corresponding to a leaf.

So, in this case, this is only a two-leaves tree. And that's it. It's just an example. Um number two, you you construct a tree using our library, and you have to provide the information about the ABI ABI encoding for those values. So, as you can see, you don't have to worry about like any conversion between data types.

It is already built in, and under the hood is using ether.js, which is what you will be using if you are like building applications on Ethereum, right? Um step number three is calculating the root, so you can take this root and put it into a smart contract on chain and use this for validation in the future. Finally, you just have to write the uh the tree in any file, so you can like later use it for proving that some element is is inside it. Uh especially when you're building front ends, um if you already have claim an airdrop in which they use a Merkle tree, you probably will know that the front-end has to calculate the Merkle proof for you, so you can then claim, um, your airdrop, basically.

Nice. Uh, as you can see, this is ABI encoded, so it's quite easy. It's the same as if you were working directly with ABIs and using any other tooling such as web3.js or ether.js.

It's the same. Cool. So, in order to get a proof, let's say that you already built your, um, your application. You have the list of the people that is going to be benefit from the airdrop. Now, you have to add it to the, um, Merkle tree, loading it from a file.

And this is special This is especially designed like this because we noticed that mul- multiple people in the sta- in the in the space are using usually CSV. Why? Because it's the most easy easiest thing to do, right? You put everything into a CSV, export it, and let's use, uh, I don't know, any front-end that converts that into a Merkle tree, right? So, we made it easy.

Um, you can load everything from a JSON file, and I'm going to show you at the very end how you can actually parse CSV into JSON. Uh, nice. Step number two is just iterating through the through the leaves and get the proof for each one of your leaves. And that's it. So, if you have a front-end, you can just plug the, um, address of the user here, and you will get the proof for the user, so they can submit it on chain.

Uh, one thing that is also important to know is that this proof that is generated is ready to put into an smart contract. I mean, if you use this to generate the proof, then you can go to an smart contract and exactly as it was printed in the console, you can put it in Remix or in Etherscan or in the application that you are using, right? So, it's immediately use useful and it you don't need to do any any conversion or weird stuff in the middle. It's quite easy. Uh nice.

This is the example from the Solidity perspective. As you can see, it's quite the same as I already showed you before, but it includes some um let's say a small differences, which is that number one, we have to save the root state in the constructor. This This is for immutability purposes. We want to make sure the root is already there and nobody will change it after it's uh published. Then we add a function for verifying and we can put this function inside of any mint function or claim function.

And what it's doing is basically calculating the leaf in the same way that we did before. And also requiring that the proof is correct, uh which is this line. Number four, you can add all of the logic you want after that in a secure way. And that's it. You're ready to go with this uh Merkle tree configuration.

Um important things to know is that there is no second preimage attack, so you are safe. I mean, you don't even have to think about it because it is already included there in the library. And it's 100% ABI compatible the way ether.js is. And finally, you have a great developer experience.

Just a few lines of code and you're ready to go, which is pretty nice. Uh cool. Let's do a quick demo. Let's see how much time we have. I think we have like sort of like 10 minutes, so I think it's enough for running a quick test.

So, I'm going to open this repository here. Let me make some zoom. Is that okay? Amazing. Thank you.

So, as you can see, I have a CSV file here that includes the same example in the in the presentation, right? It includes the types as headers of the CSV and then the values comma separated. Um it's quite easy. You can export something like this from Excel or Google spreadsheet. Whatever is fine.

And is quite easy to use. So here I have two scripts. One of these is uh for building the tree and the other one is for actually generating the proof. And if we take a look the build tree should look almost exactly as the uh example that I showed you before. The only difference is that we are reading from the values.

csv and we are converting the CSV into a simple JSON that we can then input into our library for building Merkle trees. So what this is going to do is to like separate each each line. Let me put each line aside. Uh okay. So as you can see what this is doing is like removing any extra space because for example this uh four right here is an empty line.

We don't need it. And then we split four lines. So we end up with an array of values in which the first values are the data types uh equivalent to ether.js. And the rest of the values are just the leaves of the Merkle tree.

So the way we create a Merkle tree is by calling the standard Merkle tree dot of function just mapping the leaves uh and separating because they are like comma separated. We have to make them into an array. That's it. Um some encoding here. We print the Merkle root and then we can use that to put it into a smart contract.

Cool. So let's try it out. I'm going to open my terminal. And also some some zoom. So is that okay?

Yes. Nice. So what we have to do if you want to like check it out you have some instructions here. You just have to basically like populate a CSV and then run this command and you will get the Merkle root, right? So you can put this into your smart contract and then give proofs to everyone so they can claim their their tokens or their NFTs.

They can do it. Cool. So now that we have this Merkle root, the next thing we have to do is generating a proof, okay? So a proof is um it it's a way to well, actually prove that some data is there, but you have to actually provide what data of the tuple you are trying to prove for. Why?

Because we have two values for each leaf, which is the address and an amount. What if we want to generate a proof for an address? So we have to point out to the first element of the leaf, right? That is why we provide a type index, which is referring to the first value. And then a value, which is the um how do you call it?

Um Yeah, the isn't isn't a proof is the value that we're looking for, the address in this case? It will all make sense when I run it. So let's just run it with npm run generate proof. And as you can see, since uh each tuple is consistent of two values. Okay.

What I'm trying to prove for actually I think I need to run with with a zero here. Because this is the type index of the first element, which is the address, right? So we want to generate a proof for for the address 11111 and this is the way we do it. Let's see if it works. Yes.

So here you go, you have the value and you have the proof. Uh this proof is just one element because the the the Merkle tree we made is quite simple, but if you want to extend this into like multiple things, you can try it out. Just make sure you put different values in here because otherwise it could be a problem in the way we calculate the proof, especially because we don't know exactly which one of the elements you have because they are duplicated. That is something to consider. Okay?

So, that's basically it. This is the way you can plug everything into your front end in an easy way. So, yeah, let us know any comments and feel free to open issues in the repository. I'm going to be here around for any question you have. So, thank you very much.

Does anybody have any questions? Roman