Merkle Trees
Merkle Trees are data structures which became especially famous in the context of Bitcoin's Simple Payment Verification - see chapter 8 in the Bitcoin Whitepaper.
In general you can use Merkle Trees to proof / validate that a specific element is available at a specific index within an array (block, ...) - without the need to load the elements themselves.
Usage Example
deno run https://deno.land/x/merkletrees/usage-example.ts
import { MerkleTree, Helper } from "https://deno.land/x/merkletrees/mod.ts"
const exampleArray = ["dog", "horse", "cow", "chicken"]
const merkleTree = new MerkleTree(exampleArray)
const investigatedEntry = "dog"
const proofElements = merkleTree.getProofElements(exampleArray.indexOf(investigatedEntry))
const investigatedEntryHashed = Helper.sha256(investigatedEntry)
const rootHash = merkleTree.getRootHash()
const isValid = merkleTree.verify(proofElements, investigatedEntryHashed, rootHash, exampleArray.indexOf(investigatedEntry))
if (isValid) {
console.log(`we can be pretty sure that ${investigatedEntry} is in the array at index: ${exampleArray.indexOf(investigatedEntry)}`)
}
Unit Tests / Executable Specifications
You can execute the unit tests via:
deno test https://deno.land/x/merkletrees/src/merkle-tree.spec.ts
Explaining Merkle Trees
Merkle trees are built up by hashing the neighbour element up the ladder. In case of questions feel free to raise an issue.