ZK Proofs & Merkle Trees

pub fn hash_audit_leaf(payload: &LeafPayload<'_>) -> H256 {
    let mut bytes = Vec::with_capacity(512);
    bytes.extend_from_slice(&payload.id.to_le_bytes());
    bytes.extend_from_slice(&payload.timestamp.to_le_bytes());
    push_string(&mut bytes, payload.intent_type);
    push_string(&mut bytes, payload.service);
    push_string(&mut bytes, payload.action);
    push_string(&mut bytes, payload.decision);

    match payload.reason {
        Some(reason) => {
            bytes.push(1);
            push_string(&mut bytes, reason);
        }
        None => bytes.push(0),
    }

    // Cost in microdollars (i64)
    match payload.cost_usd {
        Some(cost) if cost.is_finite() && cost >= 0.0 => {
            bytes.push(1);
            let micros = (cost * 1_000_000.0).round() as i64;
            bytes.extend_from_slice(&micros.to_le_bytes());
        }
        _ => bytes.push(0),
    }

    bytes.extend_from_slice(&payload.policy_version_hash);
    bytes.extend_from_slice(&payload.intent_hash);

    if let Some(hash) = payload.permit_hash {
        bytes.push(1);
        bytes.extend_from_slice(&hash);
    } else {
        bytes.push(0);
    }

    keccak256(&bytes)
}

pub fn compute_root_from_hashes(mut layer: Vec<H256>) -> H256 {
    if layer.is_empty() {
        return ZERO_H256;
    }

    while layer.len() > 1 {
        if layer.len() % 2 == 1 {
            let last = *layer.last().unwrap_or(&ZERO_H256);
            layer.push(last);  // Duplicate last leaf for odd count
        }

        let mut next_layer = Vec::with_capacity(layer.len() / 2);
        for pair in layer.chunks_exact(2) {
            next_layer.push(hash_pair(&pair[0], &pair[1]));
        }
        layer = next_layer;
    }

    layer[0]  // Root
}

pub fn merkle_path_for_leaf(conn: &Connection, leaf_position: u64) -> Vec<H256> {
    let mut layer = load_leaf_hashes(conn)?;
    let mut index = leaf_position as usize;
    let mut path = Vec::new();

    while layer.len() > 1 {
        if layer.len() % 2 == 1 {
            let last = *layer.last().unwrap_or(&ZERO_H256);
            layer.push(last);
        }

        let sibling = if index % 2 == 0 { index + 1 } else { index - 1 };
        path.push(layer[sibling]);

        let mut next_layer = Vec::with_capacity(layer.len() / 2);
        for pair in layer.chunks_exact(2) {
            next_layer.push(hash_pair(&pair[0], &pair[1]));
        }

        layer = next_layer;
        index /= 2;
    }

    Ok(path)
}

curl http://localhost:3000/api/audit/merkle/root

{
  "root": "0xabcdef1234567890abcdef1234567890abcdef1234567890abcdef1234567890",
  "leaf_count": 127,
  "last_entry_id": 127
}

curl http://localhost:3000/api/audit/merkle/proof/42

{
  "entry_id": 42,
  "leaf_hash": "0x123abc...",
  "proof": [
    "0x456def...",
    "0x789012...",
    "0xabcdef..."
  ],
  "root": "0xabcdef1234567890abcdef1234567890abcdef1234567890abcdef1234567890"
}

CREATE TABLE audit_merkle_nodes (
  entry_id INTEGER NOT NULL,
  level INTEGER NOT NULL,
  position INTEGER NOT NULL,
  is_leaf INTEGER NOT NULL,
  hash BLOB NOT NULL,
  PRIMARY KEY (level, position)
);

let leaf_hash = hash_audit_leaf(&leaf_payload);
let root = insert_leaf_and_new_parents(conn, entry_id, leaf_position, leaf_hash)?;

use tiny_keccak::{Hasher, Keccak};

pub fn keccak256(data: &[u8]) -> H256 {
    let mut hasher = Keccak::v256();
    hasher.update(data);
    let mut out = [0u8; 32];
    hasher.finalize(&mut out);
    out
}

id (8 bytes, LE) ||
timestamp (8 bytes, LE) ||
length(intent_type) (8 bytes, LE) || intent_type ||
length(service) (8 bytes, LE) || service ||
length(action) (8 bytes, LE) || action ||
length(decision) (8 bytes, LE) || decision ||
reason_present (1 byte) || [length(reason) || reason] ||
cost_present (1 byte) || [cost_micros (8 bytes, LE)] ||
policy_version_hash (32 bytes) ||
intent_hash (32 bytes) ||
permit_hash_present (1 byte) || [permit_hash (32 bytes)]

pub fn hash_pair(left: &H256, right: &H256) -> H256 {
    let mut bytes = [0u8; 64];
    bytes[..32].copy_from_slice(left);
    bytes[32..].copy_from_slice(right);
    keccak256(&bytes)
}

fn tree_height_for_leaf_count(leaf_count: u64) -> u32 {
    if leaf_count <= 1 {
        0
    } else {
        u64::BITS - (leaf_count - 1).leading_zeros()
    }
}

let mut current_hash = leaf_hash;
let mut current_level = 0u32;
let target_height = tree_height_for_leaf_count(leaf_position.saturating_add(1));

while current_level < target_height {
    let sibling_hash = get_node_hash(conn, current_level, sibling_position)?
        .unwrap_or(current_hash);
    
    let parent_hash = hash_pair(&left, &right);
    current_level += 1;
    current_position /= 2;
    
    insert_node(conn, entry_id, current_level, current_position, false, &parent_hash)?;
    current_hash = parent_hash;
}

import requests
import time
from web3 import Web3

FISHNET_URL = "http://localhost:3000"
CONTRACT_ADDRESS = "0x1234..."
RPC_URL = "https://base.sepolia.org"

w3 = Web3(Web3.HTTPProvider(RPC_URL))
contract = w3.eth.contract(address=CONTRACT_ADDRESS, abi=[...])

def publish_root():
    # Fetch current Merkle root
    resp = requests.get(f"{FISHNET_URL}/api/audit/merkle/root")
    data = resp.json()
    root = data["root"]
    leaf_count = data["leaf_count"]
    
    # Submit to smart contract
    tx = contract.functions.submitRoot(
        bytes.fromhex(root[2:]),  # Strip 0x prefix
        leaf_count
    ).build_transaction({
        "from": OWNER_ADDRESS,
        "nonce": w3.eth.get_transaction_count(OWNER_ADDRESS),
    })
    
    signed = w3.eth.account.sign_transaction(tx, OWNER_KEY)
    tx_hash = w3.eth.send_raw_transaction(signed.rawTransaction)
    
    print(f"Published root {root} (leaves: {leaf_count}) in tx {tx_hash.hex()}")

# Run every hour
while True:
    publish_root()
    time.sleep(3600)

cd ~/workspace/source/crates/server
cargo test merkle