WebAssembly Module for Client-Side Merkle Tree Proof Generation with Rust SHA-256 at 15K Hashes/Second

[elizabetheonoja-art]

Problem Statement / Feature Objective

The dashboard's Merkle tree operations (PoR verification, batch asset inclusion proofs) are currently implemented in JavaScript, running at approximately 500 hashes/second on a field tablet. For tree depths of 20+ (1M+ leaves), generating a single Merkle proof takes over 2 seconds, blocking the main thread. A WebAssembly module compiled from a Rust implementation of SHA-256 Merkle tree operations must achieve at least 15,000 hashes/second, reducing proof generation to under 70 ms. The WASM module must expose tree construction, root computation, proof generation, and proof verification via a minimal C ABI.

Technical Invariants & Bounds

• WASM target: wasm32-unknown-unknown with -O3 optimization; binary size target < 250 KB gzipped.
• Hash throughput: 15,000 SHA-256 hashes/second on Snapdragon 7c (mid-range ARM tablet), measured with performance.now() averaged over 100 runs.
• Leaf input: 64 bytes (32 bytes meterId + 32 bytes consumption big-endian u256). Internal node: 64 bytes (left_hash || right_hash).
• Tree arity: binary Merkle tree with lexicographic sorting of sibling pairs at each level.
• WASM exports: merkle_build_tree(leaves_ptr, len) -> root_ptr; merkle_generate_proof(leaf_index) -> proof_ptr; merkle_verify_proof(root_ptr, proof_ptr, leaf_ptr) -> bool.
• Memory: WASM linear memory allocated up to 64 MB (enough for 1M leaves at 32 bytes each = 32 MB leaves + ~32 MB internal nodes).

Codebase Navigation Guide

• public/wasm/merkle_wasm.wasm - Compiled WASM binary; integrity SHA-256 hash stored in a .integrity file.
• public/wasm/merkle_wasm.js - Generated JS glue code (if using wasm-pack with --target web or no bundler).
• src/utils/wasmLoader.ts - Existing WASM loader; extended to support the Merkle module with instance caching.
• src/utils/merkleWasm.ts - TypeScript wrapper: alloc(size), dealloc(ptr), buildTree, generateProof, verifyProof.
• src/workers/merkleWorker.worker.ts - Web Worker that communicates with the WASM module off the main thread.
• src/tests/merkleWasm.bench.ts - Benchmark test measuring hash/sec, proof generation time, and proof size.
• rust/merkle/Cargo.toml - Rust project for the WASM module (if included in monorepo).

Implementation Blueprint

1. Create the Rust project in rust/merkle/ with a lib.rs exposing #[no_mangle] extern "C" functions. Use sha2 crate for SHA-256 hashing. Implement iterative tree construction with a scratch buffer for internal nodes.
2. Compile with wasm-pack build --target web --release. Copy the resulting .wasm, .js, and .integrity files to public/wasm/.
3. Extend src/utils/wasmLoader.ts with loadMerkleWasm(): fetch the .wasm binary, instantiate with WebAssembly.instantiateStreaming, cache the instance.
4. Build src/utils/merkleWasm.ts wrapper: allocUint8Array(data) copies data into WASM memory and returns the pointer; buildTree(leaves) returns { root, rootPtr }; generateProof(treePtr, leafIndex) returns proof as Uint8Array; verifyProof(root, proof, leaf) returns boolean.
5. In merkleWorker.worker.ts, receive { type: 'buildTree', leaves } or { type: 'generateProof', ... } from the main thread, call the WASM functions, return results. Use Transferable objects for ArrayBuffer passing.
6. Create the bench test: generate 1,000 random leaves, time tree construction over 50 iterations, compute average hash/sec. Assert >= 15,000.
7. Integrate with existing proof-of-reserve flow: replace JS Merkle implementation in src/utils/merkleTree.ts with the WASM-backed version when available, falling back to JS only if WASM instantiation fails.

[dev-king-001]

Good day maintainer, can you please assign me this issue.

[grantfox-oss]

🦊 GrantFox — @dev-king-001 has been assigned to this issue as part of the Official Campaign campaign!

Next steps:

1. Open a Pull Request referencing this issue (e.g., Closes #62)
2. Your PR will be reviewed by the Utility-Protocol maintainers

Good luck! Track your progress on GrantFox.

[grantfox-oss]

🎉 This issue has been marked as completed on GrantFox as part of the Official Campaign campaign!

@dev-king-001's PR #76 was approved and merged by @elizabetheonoja-art.

🏆 @dev-king-001: You earned 35 FoxPoints for this contribution! Your current tier: Explorer (468 total points). Track your full progress on GrantFox.

👏 Great work, @dev-king-001! Keep contributing to Utility-Protocol.