This library has not been audited ; use at your own risks.
Stars are highly appreciated! Thanks in advance.
This library is able to create and handle Merkle trees, using very efficient and specifics hashes for the Starknet blockchain. You can use :
- Pedersen hash (by default)
- Poseidon hash (the most efficient one)
You can also generates some Merkle proofs, store the tree, hash a leave of the tree, and many other things.
This library has been tested with success with trees up to 500 0000 leaves, each leave including 3 numbers.
This lib will be very useful if you have to code an airdrop.
npm install starknet-merkle-tree
import * as Merkle from "starknet-merkle-tree";
The Merkle tree will be created with an array of strings as input.
For an Airdrop, you needs a list of granted addresses, and optionally the quantity of token to distribute to each one.
// address + quantity (u256.low + u256.high)
const airdrop: Merkle.InputForMerkle[] = [
['0x69b49c2cc8b16e80e86bfc5b0614a59aa8c9b601569c7b80dde04d3f3151b79', '256','0'],
['0x3cad9a072d3cf29729ab2fad2e08972b8cfde01d4979083fb6d15e8e66f8ab1', '25','0'],
['0x27d32a3033df4277caa9e9396100b7ca8c66a4ef8ea5f6765b91a7c17f0109c', '56','0'],
['0x7e00d496e324876bbc8531f2d9a82bf154d1a04a50218ee74cdd372f75a551a', '26','0'],
['0x53c615080d35defd55569488bc48c1a91d82f2d2ce6199463e095b4a4ead551', '56','0'],
];
const tree = Merkle.StarknetMerkleTree.create(airdrop, Merkle.HashType.Poseidon);
const root = tree.root;
const inp = 3; // Nth leaf of the input list
// or
const inp = ['0x7e00d496e324876bbc8531f2d9a82bf154d1a04a50218ee74cdd372f75a551a', '26','0']; // leaf content
const proof = tree.getProof(inp);
const inp = 3; // Nth leaf of the input list
const inpData = tree.getInputData(inp);
const leafHash = Merkle.StarknetMerkleTree.leafHash(inpData, Merkle.HashType.Poseidon);
const inp = 3; // Nth leaf of the input list
const inpData = tree.getInputData(inp);
const isValid = tree.verify(inpData, proof);
You have to deploy a new instance of an existing smart-contract. There is one contract dedicated for Pedersen hash, and one other for Poseidon hash. These contracts are already declared in Starknet Mainnet, Goerli Testnet and Sepolia Testnet, with the following class hashes :
Tree hash | Class hash |
---|---|
Pedersen class hash | 0x4ff16c026ed3b1849563c95605ef8ee91ca403f2c680bda53e4f6717400b230 |
Poseidon class hash | 0x03e2efc98f902c0b33eee6c3daa97b941912bcab61b6162884380c682e594eaf |
So, you will not have to pay fees to declare this part of the airdrop code ; it's already made. You have to deploy this contract (called here contract 1) with only one parameter in the constructor : the tree root.
You have to create/declare/deploy your dedicated smart-contract (called here contract 2) to handle the Airdrop (list of already performed airdrops, distribution of tokens, timing, administration, etc..).
This contract 2 has to call the contract 1 to verify if the data are correct and are part of the Merkle tree.
Contract 1 is able to say if an address and the corresponding data are included in the tree or not. Just by storing a felt252 in Starknet, you can check that an address is included in a list of thousand of addresses, and trigger a distribution of token to this address.
You can find a documentation of this contract 1 here.
Some Typescript demo files are available here.
A demo DAPP for an Airdrop is available,. You can test it and analyze the source code here.
type InputForMerkle = string | string[];
enum HashType {
Pedersen = "Pedersen",
Poseidon = "Poseidon",
}
Creates a standard Merkle tree out of an array. Data are Hex strings or decimal strings.
const data: Merkle.inputForMerkle[] = [
['0x69b49c2cc8b16e80e86bfc5b0614a59aa8c9b601569c7b80dde04d3f3151b79', '256', '0'],
['0x3cad9a072d3cf29729ab2fad2e08972b8cfde01d4979083fb6d15e8e66f8ab1', '25', '0'],
['0x27d32a3033df4277caa9e9396100b7ca8c66a4ef8ea5f6765b91a7c17f0109c', '56', '0'],
['0x7e00d496e324876bbc8531f2d9a82bf154d1a04a50218ee74cdd372f75a551a', '26', '0'],
['0x53c615080d35defd55569488bc48c1a91d82f2d2ce6199463e095b4a4ead551', '56', '0'],
];
const tree = Merkle.StarknetMerkleTree.create(data, Merkle.HashType.Pedersen);
Returns a proof for the Nth value in the tree. Indices refer to the position of the values in the array from which the tree was constructed. Also accepts a value instead of an index, but this will be less efficient. It will fail if the value is not found in the tree.
const proof1 = tree.getProof(3);
const proof2 = tree.getProof(["0x43af5", '100']);
// result =
[
'0x40a6dba21b22596e979a1555a278ca58c11b5cd5e46f5801c1af8c4ab518845',
'0x7957d036cf1e60858a601df12e0fb2921114d4b5facccf638163e0bb2be3c34',
'0x12677ed42d2f73c92413c30d04d0b88e771bf2595c7060df46f095f2132eca2'
]
Returns a boolean that is true
when the proof verifies that the value is contained in the tree.
const result1 = tree.verify(3, proof);
const result2 = tree.verify(["0x34e67d", '100'], proof);
// result = true
Returns a description of the Merkle tree for distribution. It contains all the necessary information to reproduce the tree, find the relevant leaves, and generate proofs. You should distribute this to users in a web application so they can generate proofs for some leaves.
fs.writeFileSync('data/treeTestPoseidon.json', JSON.stringify(tree.dump(),undefined,2));
Loads the tree from a description previously saved or dumped.
const tree = Merkle.StarknetMerkleTree.load(
JSON.parse(fs.readFileSync('./src/scripts/merkleTree/treeTestPoseidon.json', 'ascii'))
);
Verify the consistency of the tree. Useful after a load(). Take care that this method is time-consuming. Throw an error if validation fail.
tree.validate();
The root of the tree is a commitment on the values of the tree. It can be published in a smart contract, to later prove that its values are part of the tree.
console.log(tree.root);
// result = 0x4bad3f80e8041eb3d32432fa4aed9f904db8c8ab34109879a99da696a0c5a81
Returns a visual representation of the tree that can be useful for debugging.
console.log(tree.render());
// result =
0) 0x4bad3f80e8041eb3d32432fa4aed9f904db8c8ab34109879a99da696a0c5a81
├─ 1) 0x4f9ffba9cb60723ecb53299f6b2359a9d32a1aa316ffcf83022c58d822abc55
│ ├─ 3) 0x1cd0fa9d323f2de54979140bab80cb8077ac24e098c685da5ac6a4d9a17c25c
│ │ ├─ 7) 0x6e5bfc0a35b74af4395c2a60a7735c0f0cbcfba515e91d4edd3f7ea70287cbc
│ │ └─ 8) 0x40a6dba21b22596e979a1555a278ca58c11b5cd5e46f5801c1af8c4ab518845
│ └─ 4) 0x7957d036cf1e60858a601df12e0fb2921114d4b5facccf638163e0bb2be3c34
└─ 2) 0x12677ed42d2f73c92413c30d04d0b88e771bf2595c7060df46f095f2132eca2
├─ 5) 0x77dc74ab2217383b4c2a772e491f8177277af576fd426f8c59f9c64d7ef258b
└─ 6) 0x707142fb4ad00584910740c7d8207669b429cb93ce1985870b5fa5096ced91c
return the nth data used for the tree creation.
const data= tree.getInputData(3);
// result = ['0x7e00d496e324876bbc8531f2d9a82bf154d1a04a50218ee74cdd372f75a551a', '26', '0']
Hash a leaf. Returns an hex string.
const leaf: InputForMerkle = ['0x7e00d496e324876bbc8531f2d9a82bf154d1a04a50218ee74cdd372f75a551a', '26', '0'];
const hashedLeaf: string = Merkle.hashDataToHex(leaf, Merkle.HashType.Pedersen);
// result = 0x6e5bfc0a35b74af4395c2a60a7735c0f0cbcfba515e91d4edd3f7ea70287cbc
Identical to
Merkle.StarknetMerkleTree.leafHash()
.Merkle.hashDataToBigint()
is similar, with abigint
result.
Calculate the Poseidon hash of an array of hex strings.
const hash: bigint = Merkle.computePoseidonHashOnElements(["0x10e", "0xc4", "0x1c"]);
Calculate the hash of 2 bigint.
const hash: bigint = Merkle.hashPair(200n, 300n, Merkle.HashType.Pedersen);
MIT
Documentation and this code from OpenZeppelin were an inspiration : repo