PolkaLeanIMT

Lean Incremental Merkle Tree on PolkaVM with poseidon-lite compatible hashing.

This implementation produces identical Merkle roots as the client-side poseidon-lite library, enabling seamless client-side tree reconstruction and proof generation for ZK circuits.

How to use:

Generate a eth key:

cast wallet new

fund: https://faucet.polkadot.io/

🎯 Key Features

• ✅ poseidon-lite compatible - Roots match exactly with client-side poseidon2() calculations
• ✅ External Poseidon calls - Calls deployed Poseidon contract for hashing
• ✅ Full LeanIMT algorithm - insert, root, size, has, indexOf
• ✅ Gas efficient - ~34K average gas per insert on Paseo Asset Hub
• ✅ PolkaVM compatible - Built with polkavm-derive and pallet-revive-uapi

📋 Deployed Contracts (Paseo Asset Hub)

Contract	Address	Purpose
PolkaVM LeanIMT	0xA74c50702794981fc4DDb101841137f08A8Eb0ba	Main LeanIMT contract
Poseidon Hash	0x1d165f6fE5A30422E0E2140e91C8A9B800380637	External Poseidon (poseidon-lite compatible)

🚀 Quick Start

Prerequisites

# Rust nightly toolchain
rustup install nightly-2024-11-19
rustup default nightly-2024-11-19

# PolkaVM toolchain
cargo install polkatool

# Node.js dependencies (for deployment)
cd ts && npm install && cd ..

Build

./build.sh

Deploy to Paseo

cd ts
export AH_PRIV_KEY="your_private_key"
npx ts-node deploy_leanimt.ts

📐 Architecture

┌─────────────────────────────────────────────────────────────┐
│              PolkaVM LeanIMT Contract                       │
│  Address: 0xA74c50702794981fc4DDb101841137f08A8Eb0ba       │
│                                                             │
│  insert(leaf) ────► poseidon_hash(left, right)              │
│  root() ──────────► returns current root                    │
│  size() ──────────► returns leaf count                      │
│  has(leaf) ───────► returns bool                            │
│  indexOf(leaf) ───► returns uint256                         │
└────────────────────────┬────────────────────────────────────┘
                         │ calls
                         ▼
┌─────────────────────────────────────────────────────────────┐
│              Poseidon Hash Contract                         │
│  Address: 0x1d165f6fE5A30422E0E2140e91C8A9B800380637       │
│                                                             │
│  hash(uint256[2]) → poseidon2(input)                        │
│  Compatible with circomlib / poseidon-lite                  │
└─────────────────────────────────────────────────────────────┘

✅ Poseidon Compatibility Verification

Input	poseidon-lite Output	On-Chain Poseidon Output	Match
[0, 0]	14744269619966411208579211824598458697587494354926760081771325075741142829156	Same	✅
[1, 2]	7853200120776062878684798364095072458815029376092732009249414926327459813530	Same	✅
[123, 456]	19620391833206800292073497099357851348339828238212863168390691880932172496143	Same	✅

📊 Gas Costs

Operation	Gas Used
First insert (depth 1)	~63,905
Second insert (depth 2)	~43,979
Third insert	~23,171
Fourth insert (depth 3)	~45,647
Subsequent inserts	~23,000 - 47,000
Average	~34,490

📁 Project Structure

PolkaLeanIMT/
├── src/
│   ├── lean_imt.rs           # Main LeanIMT contract
│   └── poseidon_test.rs      # Test contract for external Poseidon calls
├── ts/
│   ├── deploy_leanimt.ts     # Deployment and testing script
│   ├── package.json          # Node.js dependencies
│   └── tsconfig.json         # TypeScript configuration
├── .cargo/
│   └── config.toml           # Cargo build configuration
├── Cargo.toml                # Rust package manifest
├── build.sh                  # Build script
├── lean.md                   # Complete documentation
├── rust-toolchain.toml       # Rust toolchain pin
└── riscv64emac-unknown-none-polkavm.json  # Custom target spec

🔗 Integration with ShieldedPool

The PolkaVM LeanIMT is designed to replace the inline Solidity LeanIMT library in privacy pool contracts:

import {IPolkaVMLeanIMT} from "./IPolkaVMLeanIMT.sol";

contract FixedIlop {
    IPolkaVMLeanIMT public immutable leanIMT;
    
    constructor(address _leanIMT) {
        leanIMT = IPolkaVMLeanIMT(_leanIMT);
    }
    
    function deposit3(address asset, uint256 amount, bytes32 commitment) external payable {
        // ...
        uint256 newRoot = leanIMT.insert(uint256(commitment));
        validRoots[newRoot] = true;
        // ...
    }
}

📖 Documentation

See lean.md for complete documentation including:

• Detailed architecture diagrams
• Build and deployment instructions
• Poseidon compatibility verification
• Gas cost analysis
• Troubleshooting guide
• Client-side integration details

📜 License

MIT

External links

• LeanIMT Whitepaper
• poseidon-lite
• PoseidonPolkaVM
• PolkaVM
• circomlib