# Merkle proof

In this chapter, we will implement a circuit able to validate the Merkle tree root hash.

At this stage of reading the book, you may be unfamiliar with some language concepts. So, if you struggle to understand some examples, you are welcome to read the rest of the book first, and then come back here.

Our circuit will accept the tree node path, address, and the balance available as the secret witness data. The public data will be the Merkle tree root hash.

## Creating a new project

Let's create a new circuit called `merkle-proof`:

``````zargo new merkle-proof
cd merkle-proof
``````

Now, you can open the project in your favorite IDE and go to `src/main.zn`, where we are going to start writing the circuit code.

## Defining types

Let's start by defining the secret witness data arguments and the public data return type.

``````struct PublicInput {
root_hash: [bool; 256],
}

fn main(
balance: field, // the balance stored in the node
merkle_path: [[bool; 256]; 10] // the hash path to the node
) -> PublicInput {
// ...
}
``````

As you can see, some complex types are used in several places of our code, so it is very convenient to create an alias for such type.

``````
# #![allow(unused_variables)]
#fn main() {
type Sha256Digest = [bool; 256];
#}``````

## Creating functions

Now, we will write a function to calculate the `sha256` hash of our balance. We need it to verify the balance stored within the leaf node at our Merkle tree path.

``````
# #![allow(unused_variables)]
#fn main() {
fn balance_hash(balance: field) -> Sha256Digest {
let bits = std::convert::to_bits(balance); // [bool; 254]
std::crypto::sha256(bits_padded) // [bool; 256] a.k.a. Sha256Digest
}
#}``````

The function accepts `balance` we passed as secret witness data, converts it into a bit array of length 254 (elliptic curve field length), and pads the array with 2 extra zero bits, since we are going to pass 256 bit vector to the `sha256` function.

We have also used here three functions from the Zinc standard library from three different modules. The `std::crypto::sha256`-like paths might seem a bit verbose, but we will solve this problem later.

At this stage, this is how our code looks like:

``````type Sha256Digest = [bool; 256];

struct PublicInput {
root_hash: Sha256Digest,
}

fn balance_hash(balance: field) -> Sha256Digest {
let bits = std::convert::to_bits(balance); // [bool; 254]
std::crypto::sha256(bits_padded) // [bool; 256] a.k.a. Sha256Digest
}

fn main(
balance: field, // the balance stored in the node
merkle_path: [Sha256Digest; 10] // the hash path to the node
) -> PublicInput {
let leaf_hash = balance_hash(balance);

// ...
}
``````

Now, we need a function to calculate a tree node hash:

``````
# #![allow(unused_variables)]
#fn main() {
fn merkle_node_hash(left: Sha256Digest, right: Sha256Digest) -> Sha256Digest {
let mut data = [false; 512]; // [bool; 512]

// Casting to u16 is needed to make the range types equal,
// since 0 will be inferred as u8, and 256 - as u16.
for i in 0 as u16..256 {
data[i] = left[i];
data[256 + i] = right[i];
}

std::crypto::sha256(data) // [bool; 256] a.k.a. Sha256Digest
}
#}``````

The Zinc standard library does not support array concatenation yet, so, for now, we will do it by hand, allocating an array to contain two leaf node digests, then put the digests together and hash them with `std::crypto::sha256`.

Finally, let's define a function to calculate the hash of the whole tree:

``````
# #![allow(unused_variables)]
#fn main() {
fn restore_root_hash(
leaf_hash: Sha256Digest,
merkle_path: [Sha256Digest; 10],
) -> Sha256Digest
{
let mut current = leaf_hash; // Sha256Digest

// Traverse the tree from the left node to the root node
for i in 0..10 {
// Multiple variables binding is not supported yet,
// so we going to store leaves as an array of two digests.
// If address[i] is 0, we are in the left node, otherwise,
// we are in the right node.
let left_and_right = if address[i] {
[current, merkle_path[i]] // [Sha256Digest; 2]
} else {
[merkle_path[i], current] // [Sha256Digest; 2]
};

// remember the current node hash
current = merkle_node_hash(left_and_right, left_and_right);
}

// return the root node hash
current
}
#}``````

Congratulations! Now we have a working circuit able to verify the Merkle proof!

``````// main.zn

type Sha256Digest = [bool; 256];

fn balance_hash(balance: field) -> Sha256Digest {
let bits = std::convert::to_bits(balance); // [bool; 254]
std::crypto::sha256(bits_padded) // [bool; 256] a.k.a. Sha256Digest
}

fn merkle_node_hash(left: Sha256Digest, right: Sha256Digest) -> Sha256Digest {
let mut data = [false; 512]; // [bool; 512]

// Casting to u16 is needed to make the range types equal,
// since 0 will be inferred as u8, and 256 - as u16.
for i in 0 as u16..256 {
data[i] = left[i];
data[256 + i] = right[i];
}

std::crypto::sha256(data) // [bool; 256] a.k.a. Sha256Digest
}

fn restore_root_hash(
leaf_hash: Sha256Digest,
merkle_path: [Sha256Digest; 10],
) -> Sha256Digest
{
let mut current = leaf_hash; // Sha256Digest

// Traverse the tree from the left node to the root node
for i in 0..10 {
// Multiple variables binding is not supported yet,
// so we going to store leaves as an array of two digests.
// If address[i] is 0, we are in the left node, otherwise,
// we are in the right node.
let left_and_right = if address[i] {
[current, merkle_path[i]] // [Sha256Digest; 2]
} else {
[merkle_path[i], current] // [Sha256Digest; 2]
};

// remember the current node hash
current = merkle_node_hash(left_and_right, left_and_right);
}

// return the root node hash
current
}

struct PublicInput {
root_hash: Sha256Digest,
}

fn main(
balance: field,
merkle_path: [Sha256Digest; 10]
) -> PublicInput {
let leaf_hash = balance_hash(balance);

let root_hash = restore_root_hash(
leaf_hash,
merkle_path,
);

PublicInput {
root_hash: root_hash,
}
}
``````

## Defining a module

Our `main.zn` module has got a little overpopulated by now, so let's move our functions to another one called `merkle`. At first, create a file called `merkle.zn` in the `src` directory besides `main.zn`. Then, move everything above the `PublicInput` definition to that file. Our `main.zn` will now look like this:

``````struct PublicInput {
root_hash: Sha256Digest, // undeclared `Sha256Digest`
}

fn main(
balance: field,
merkle_path: [Sha256Digest; 10] // undeclared `Sha256Digest`
) -> PublicInput {
let leaf_hash = balance_hash(balance); // undeclared `balance_hash`

let root_hash = restore_root_hash( // undeclared `restore_root_hash`
leaf_hash,
merkle_path,
);

PublicInput {
root_hash: root_hash,
}
}
``````

This code will not compile, as we have several items undeclared now! Let's define our `merkle` module and resolve the function paths:

``````mod merkle; // defined a module

struct PublicInput {
root_hash: merkle::Sha256Digest, // use a type declaration from `merkle`
}

fn main(
balance: field,
merkle_path: [merkle::Sha256Digest; 10] // use a type declaration from `merkle`
) -> PublicInput {
let leaf_hash = merkle::balance_hash(balance); // call a function from `merkle`

// call a function from `merkle`
let root_hash = merkle::restore_root_hash(
leaf_hash,
merkle_path,
);

PublicInput {
root_hash: root_hash,
}
}
``````

Perfect! Now all our functions and types are defined. By the way, let's have a glance at our `merkle` module, where you can find another improvement!

``````
# #![allow(unused_variables)]
#fn main() {
use std::crypto::sha256; // an import

type Sha256Digest = [bool; 256];

fn balance_hash(balance: field) -> Sha256Digest {
let bits = std::convert::to_bits(balance);
}

fn merkle_node_hash(left: Sha256Digest, right: Sha256Digest) -> Sha256Digest {
let mut data = [false; 512];

for i in 0 as u16..256 {
data[i] = left[i];
data[256 + i] = right[i];
}

sha256(data)
}

fn restore_root_hash(
leaf_hash: Sha256Digest,
merkle_path: [Sha256Digest; 10],
) -> Sha256Digest
{
let mut current = leaf_hash;

for i in 0..10 {
let left_and_right = if address[i] {
[current, merkle_path[i]]
} else {
[merkle_path[i], current]
};

current = merkle_node_hash(left_and_right, left_and_right);
}

current
}
#}``````

You may notice a `use` statement at the first line of code. It is an import statement which is designed to prevent using long repeated paths in our code. As you can see, now we call the standard library function like this `sha256(data)`, but not like that `std::crypto::sha256(data)`.

## Finalizing

Congratulations, you are an experienced Zinc developer! Now, you may build the circuit, generate and verify a proof, like it was explained in the previous chapter, and move on to reading the rest of the book!