You have millions of unique images in your gallery, each representing a piece of private or personal data stored on your phone. After an incident, you lost your device, but it was returned to you after many months, with claims that the images hadn't been tampered with.

Verifying the authenticity of each image in this gallery could be difficult, right? How can they prove the images haven't been manipulated, or how can you confirm everything is as it should be? That's whereMerkle's proofs come into play, as they offer a solution to verify the integrity of large datasets without the need to inspect each item individually.

In this tutorial, you will learn about Merkle proofs, how to create them using aMerkle Tree, and how to implement Merkle proofs for whitelisting email addresses using JavaScript.

To understand how Merkle proofs help verify the authenticity and integrity of your data without the need to check each piece individually, such as your image gallery, as discussed earlier, you first need to understand the structure that underpins them: theMerkle Tree.

What is a Merkle Tree?

AMerkle Tree,also known as a hash tree, is a binary tree structure used to verify a data set's integrity effectively. It was a concept named after the computer scientistRalph Merkle,who patented it in 1979.

This binarytree structure has each leaf node representing a block of data or a piece of information. Instead of containing the data directly, the internal nodes hold a cryptographic hash of their child nodes. The tree is built by repeatedly hashing pairs of child nodes until a single root hash is achieved.

Components of Merkle Tree

Merkle Tree image by Teemu Kanstrén

A Merkle tree has three different components, as shown in the image above Merkle root, Merkle branches, and Merkle leaves. Let's take a look at what they are.

• Merkle root is derived from hashing together the child hashes beneath it and down to the leaves. It is a single hash on its own that represents the top of the Merkle tree, as shown in the image above and is often used to store block headers inblockchain content without downloading the entire block.

• In a Merkle tree, we haveMerkle branches, intermediate nodes between Merkle roots and Merkle leaves. Each branch node is created by hashing together the hashes of its child nodes. These branches form the connections between the leaves (where the data resides) and the Merkle root, making it easier to ensure that the Merkle tree can be efficiently traversed and verified.

• Merkle leaves are the nodes at the bottom layer of the Merkle tree. They contain hashes of the actual data stored. The leaves are the foundation of the Merkle tree, as their hashes are combined and rehashed to produce the hashes of the nodes above them, ultimately leading to the Merkle root.

Additionally, we have theData nodes, a layer representing how data is supplied to start the process before it hashed in the next layer(Merkle leaves), which is the Merkle leaves, as shown in the image.

What is a Merkle Proof?

A Merkle proof is a method used to verify the presence and integrity of specific data within a dataset using a Merkle tree. It comprises a single data block (leaf), a series of hashes from the tree (branches), and the Merkle root.

While Merkle proof is used to verify the presence of specific data within a dataset using a Merkle tree, here are some areas where Merkle proof can be applied.

• In a distributed system for data verification

• Secure communication protocols

• Data storage solution

• Cryptocurrencies and blockchain

Implementing a Merkle Proof for Whitelisting Email Addresses

Let's implement a Merkle proof for whitelisting email addresses in this section.

Prerequisite

• Node.js and its package manager NPM, version 18. Verify Node.js is installed by running the following terminal command:node -v && npm -v

• A basic understanding ofJavaScript

Project Setup and Installation

Navigate to any directory ofyour choice, and then run the following commands to create a new folder and change the directory into the folder:

mkdirmerkle-proof-tutorialcdmerkle-proof-tutorial

Next, you need to install themerkletreejs andcrypto-js libraries, which will be needed to create a Merkle tree and hash data using the following command:

npm i merkletreejs crypto-js

Create a new fileproof.js feel free to name it whatever you want, but for this tutorial, you will name itproof.js.

Import Libraries

You will be using themerkletreejs andcrypto-js libraries in this example to create a Merkle tree and hash the data, respectively.

Navigate into theproof.js file and add the following code snippet:

const{MerkleTree}=require('merkletreejs')constSHA256=require('crypto-js/sha256')

Create a List of Emails to Be Whitelisted

You need to create a list of emails to be whitelisted. In this example, you will add three emails, but it could be millions of emails, depending on the data you want to test with. Add the following code snippet to create an array of three email addresses:

//...// List of email addresses to be whitelistedconstemails=["example1@mail.com","example2@mail.com","example3@mail.com"];

Convert Emails to Hashes and Build the Merkle Tree

Next, you need to convert each email into a hash and create the Merkle tree using the hashed emails with the following code snippet:

//...// Convert each email into a hashconstleaves=emails.map(email=>SHA256(email));// Create the Merkle Tree using the hashed emailsconsttree=newMerkleTree(leaves,SHA256);// Get the root and convert it to a hexadecimal stringconstroot=tree.getRoot().toString('hex');

Add Function to Verify Whitelisted Emails

In the previous step, you created a tree for the addresses; next, you must create a function to prove if an email is part of the whitelisted emails.

Create a functionverifyEmail:

//...// Function to verify if an email is whitelistedconstverifyEmail=(email)=>{// Hash the email to be verifiedconsthashedEmail=SHA256(email);// Get the proof for the hashed email from the treeconstproof=tree.getProof(hashedEmail);// Verify the proof against the root of the tree; returns true if valid, false otherwiseconstverified=tree.verify(proof,hashedEmail,root);// Log the result to the consoleconsole.log(`${email} is${verified?"whitelisted":"not whitelisted"}.`);};

In the code snippet, you created a function verifying whether an email is whitelisted. To do this, you:

• Hashed the email to be verified using SHA256

• Got the proof for the hashed email using thegetProof method

• Verified the proof against the root of the tree

Here is what the complete code looks like:

const{MerkleTree}=require("merkletreejs");constSHA256=require("crypto-js/sha256");// List of email addresses to be whitelistedconstemails=["example1@mail.com","example2@mail.com","example3@mail.com"];// Convert each email into a hashconstleaves=emails.map((email)=>SHA256(email));// Create the Merkle Tree using the hashed emailsconsttree=newMerkleTree(leaves,SHA256);// Get the root and convert it to a hexadecimal stringconstroot=tree.getRoot().toString("hex");// Function to verify if an email is whitelistedconstverifyEmail=(email)=>{// Hash the email to be verifiedconsthashedEmail=SHA256(email);// Get the proof for the hashed email from the treeconstproof=tree.getProof(hashedEmail);// Verify the proof against the root of the tree; returns true if valid, false otherwiseconstverified=tree.verify(proof,hashedEmail,root);// Log the result to the consoleconsole.log(`${email} is${verified?"whitelisted":"not whitelisted"}.`);};

Test the Verification Function

In this section, you will test the verification function with a whitelisted and non-whitelisted email.

Test with a whitelisted email address by calling theverifyEmail function inside the script file.

//...verifyEmail("example2@mail.com");// Expected output: "example2@mail.com is whitelisted."

To run the script, use the following command:

node proof.js

The result printed on the console will return a response as shown below, indicating the email address is whitelisted because it is part of the emails we added to the email array.

Next, test with an email that is not whitelisted.

//...verifyEmail("x@mail.com");// Expected output: "x@mail.com is not whitelisted."

You should see a response indicating the email is not whitelisted, as shown below. This is because it wasn't part of the emails whitelisted, meaning there is no proof for the email address to indicate it was part of the tree.

Conclusion

In this tutorial, you learned about Merkle proofs, how they can be used to ensure the integrity of datasets in applications, how to create them using a Merkle Tree, and how to implement Merkle proofs for whitelisting email addresses using JavaScript.

References

• Merkle Tree

• Merkletreejs SDK