Merkle trees allow for on-chain verification of off-chain data. With the merkle root posted on-chain, the generation of proofs off-chain can provide verifiably true data.
The Merkle Library currently supports two different tree structures: Binary Trees and Sparse Trees. For information implementation specifications, please refer to the Merkle Tree Specification .
For implementation details on the Merkle Library please see the Sway Libs Docs .
In order to use the Merkle Library, Sway Libs must be added to the Forc.toml file and then imported into your Sway project. To add Sway Libs as a dependency to the Forc.toml file in your project please see the Getting Started .
To import the Binary Merkle Library to your Sway Smart Contract, add the following to your Sway file:
use sway_libs::merkle::binary::{leaf_digest, process_proof, verify_proof};
use sway_libs::merkle::common::{MerkleRoot, node_digest, ProofSet};To import the Sparse Merkle Library to your Sway Smart Contract, add the following to your Sway file:
use sway_libs::merkle::sparse::*;
use sway_libs::merkle::common::{MerkleRoot, ProofSet};Once imported, using the Binary Merkle Proof library is as simple as calling the desired function. Here is a list of function definitions that you may use.
leaf_digest() node_digest() process_proof() verify_proof() The Binary Proof currently allows for you to compute leaves and nodes of a merkle tree given the appropriate hash digest.
To compute a leaf use the leaf_digest() function:
fn compute_leaf(hashed_data: b256) {
let leaf: b256 = leaf_digest(hashed_data);
} To compute a node given two leaves, use the node_digest() function:
fn compute_node(leaf_a: b256, leaf_b: b256) {
let node: b256 = node_digest(leaf_a, leaf_b);
}NOTE Order matters when computing a node.
To compute a Merkle root given a proof, use the process_proof() function.
fn process(key: u64, leaf: b256, num_leaves: u64, proof: ProofSet) {
let merkle_root: MerkleRoot = process_proof(key, leaf, num_leaves, proof);
} To verify a proof against a merkle root, use the verify_proof() function.
fn verify(
merkle_root: MerkleRoot,
key: u64,
leaf: b256,
num_leaves: u64,
proof: ProofSet,
) {
assert(verify_proof(key, leaf, merkle_root, num_leaves, proof));
}To generate a Binary Merkle Tree and corresponding proof for your Sway Smart Contract, use the Fuel-Merkle crate.
To import the Fuel-Merkle crate, the following should be added to the project's Cargo.toml file under [dependencies]:
fuel-merkle = { version = "0.56.0" }NOTE Make sure to use the latest version of the fuel-merkle crate.
The following should be added to your Rust file to use the Fuel-Merkle crate.
use fuel_merkle::sparse::in_memory::MerkleTree as SparseTree;
use fuel_merkle::sparse::proof::ExclusionLeaf as FuelExclusionLeaf;
use fuel_merkle::sparse::proof::Proof as FuelProof;
use fuel_merkle::sparse::MerkleTreeKey as SparseTreeKey;
use fuels::types::{Bits256, Bytes};To create a merkle tree using Fuel-Merkle is as simple as pushing your leaves in increasing order.
// Create a new Merkle Tree and define leaves
let mut tree = SparseTree::new();
let leaves = ["A", "B", "C"].to_vec();
let leaf_to_prove = "A";
let key = SparseTreeKey::new(leaf_to_prove);
// Hash the leaves and then push to the merkle tree
for datum in &leaves {
let _ = tree.update(SparseTreeKey::new(datum), datum.as_bytes());
}To generate a proof for a specific leaf, you must have the index or key of the leaf. Simply call the prove function:
// Get the merkle root and proof set
let root = tree.root();
let fuel_proof: FuelProof = tree.generate_proof(&key).unwrap();
// Convert the proof from a FuelProof to the Sway Proof
let sway_proof: Proof = fuel_to_sway_sparse_proof(fuel_proof); Once the proof has been generated, you may call the Sway Smart Contract's verify_proof function:
// Call the Sway contract to verify the generated merkle proof
let result: bool = contract_instance
.methods()
.verify(
Bits256(root),
Bits256(*key),
Some(Bytes(leaves[0].into())),
sway_proof,
)
.call()
.await
.unwrap()
.value;
assert!(result); Once imported, using the Sparse Merkle Proof library is as simple as calling the desired function on the Proof type. Here is a list of function definitions that you may use.
root() verify() To explore additional utility and support functions available, please check out the Sway Libs Docs .
To compute a Sparse Merkle root given a proof, use the root() function. You must provide the appropriate MerkleTreeKey and leaf data. Please note that the leaf data should be Some if you are proving an inclusion proof, and None if your are proving an exclusion proof.
fn compute_root(key: MerkleTreeKey, leaf: Option<Bytes>, proof: Proof) {
let merkle_root: MerkleRoot = proof.root(key, leaf);
} To verify a proof against a merkle root, use the verify() function. You must provide the appropriate MerkleTreeKey, MerkleRoot, and leaf data. Please note that the leaf data should be Some if you are proving an inclusion proof, and None if your are proving an exclusion proof.
fn verify_proof(
root: MerkleRoot,
key: MerkleTreeKey,
leaf: Option<Bytes>,
proof: Proof,
) {
let result: bool = proof.verify(root, key, leaf);
assert(result);
} If you would like to verify an inclusion proof using only the SHA256 hash of the leaf data rather than the entire Bytes, you may do so as shown:
fn inclusion_proof_hash(key: MerkleTreeKey, leaf: b256, proof: Proof) {
assert(proof.is_inclusion());
// Compute the merkle root of an inclusion proof using the sha256 hash of the leaf
let root: MerkleRoot = proof.as_inclusion().unwrap().root_from_hash(key, leaf);
// Verifying an inclusion proof using the sha256 hash of the leaf
let result: bool = proof.as_inclusion().unwrap().verify_hash(root, key, leaf);
assert(result);
}To generate a Sparse Merkle Tree and corresponding proof for your Sway Smart Contract, use the Fuel-Merkle crate.
To import the Fuel-Merkle crate, the following should be added to the project's Cargo.toml file under [dependencies]:
fuel-merkle = { version = "0.56.0" }NOTE Make sure to use the latest version of the fuel-merkle crate.
The following should be added to your Rust file to use the Fuel-Merkle crate.
use fuel_merkle::sparse::in_memory::MerkleTree as SparseTree;
use fuel_merkle::sparse::proof::ExclusionLeaf as FuelExclusionLeaf;
use fuel_merkle::sparse::proof::Proof as FuelProof;
use fuel_merkle::sparse::MerkleTreeKey as SparseTreeKey;
use fuels::types::{Bits256, Bytes};To create a merkle tree using Fuel-Merkle is as simple as pushing your leaves in increasing order.
// Create a new Merkle Tree and define leaves
let mut tree = SparseTree::new();
let leaves = ["A", "B", "C"].to_vec();
let leaf_to_prove = "A";
let key = SparseTreeKey::new(leaf_to_prove);
// Hash the leaves and then push to the merkle tree
for datum in &leaves {
let _ = tree.update(SparseTreeKey::new(datum), datum.as_bytes());
}To generate a proof for a specific leaf, you must have the index or key of the leaf. Simply call the prove function:
// Get the merkle root and proof set
let root = tree.root();
let fuel_proof: FuelProof = tree.generate_proof(&key).unwrap();
// Convert the proof from a FuelProof to the Sway Proof
let sway_proof: Proof = fuel_to_sway_sparse_proof(fuel_proof); Once the proof has been generated, you may call the Sway Smart Contract's verify_proof function:
// Call the Sway contract to verify the generated merkle proof
let result: bool = contract_instance
.methods()
.verify(
Bits256(root),
Bits256(*key),
Some(Bytes(leaves[0].into())),
sway_proof,
)
.call()
.await
.unwrap()
.value;
assert!(result); The Rust SDK does not currently support the Proof type in Sway and will conflict with the Proof type in fuel-merkle. Therefore, you MUST import the Proof type from fuel-merkle as FuelProof.
To convert between the two types, you may use the following function:
pub fn fuel_to_sway_sparse_proof(fuel_proof: FuelProof) -> Proof {
let mut proof_bits: Vec<Bits256> = Vec::new();
for iterator in fuel_proof.proof_set().iter() {
proof_bits.push(Bits256(iterator.clone()));
}
match fuel_proof {
FuelProof::Exclusion(exlcusion_proof) => Proof::Exclusion(ExclusionProof {
proof_set: proof_bits,
leaf: match exlcusion_proof.leaf {
FuelExclusionLeaf::Leaf(leaf_data) => ExclusionLeaf::Leaf(ExclusionLeafData {
leaf_key: Bits256(leaf_data.leaf_key),
leaf_value: Bits256(leaf_data.leaf_value),
}),
FuelExclusionLeaf::Placeholder => ExclusionLeaf::Placeholder,
},
}),
FuelProof::Inclusion(_) => Proof::Inclusion(InclusionProof {
proof_set: proof_bits,
}),
}
}