# Positional Merkle Tree

## 为什么不用普通 Merkle

OpenZeppelin 的标准 `MerkleProof.verify` 只用 `(leaf, root, proof)` 三参数：

```solidity
function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf)
    internal pure returns (bool)
{
    bytes32 computedHash = leaf;
    for (uint256 i = 0; i < proof.length; i++) {
        bytes32 proofElement = proof[i];
        if (computedHash <= proofElement) {
            computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
        } else {
            computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
        }
    }
    return computedHash == root;
}
```

这个版本用 `<=` 比较决定左右顺序 — 同样的 `(leaf, proof)` 可以对应**任意 leaf index**。对于 PoB 反证场景这是个问题：

> Aggregator 提交了一个含 1000 leaves 的 batch。Challenger 想证明"第 42 号 leaf 的 agentId 与 batch.agentId 不一致"。如果用 OZ 标准 verify，攻击者可以给一个不同 index 的同 leaf 做 proof。

我们需要 **leafIndex 也参与验证**。

## PositionalMerkleProof 算法

```solidity
// contracts/src/libraries/PositionalMerkleProof.sol
library PositionalMerkleProof {
    function verify(
        bytes32 root,
        bytes32 leaf,
        uint256 index,
        bytes32[] calldata proof
    ) internal pure returns (bool) {
        bytes32 computedHash = leaf;
        uint256 idx = index;
        
        for (uint256 i = 0; i < proof.length; i++) {
            bytes32 sibling = proof[i];
            if (idx % 2 == 0) {
                // current is left child
                computedHash = keccak256(abi.encodePacked(computedHash, sibling));
            } else {
                // current is right child
                computedHash = keccak256(abi.encodePacked(sibling, computedHash));
            }
            idx /= 2;
        }
        
        return computedHash == root;
    }
}
```

关键差异：

* 用 `idx % 2` 判断左右，**不依赖** value 比较
* 每爬一层 `idx /= 2`
* 同一 leaf 在不同 index 会算出不同 root

## Tree 构建（链下）

```rust
// baby-pob-aggregator/src/merkle.rs
fn positional_merkle_root(leaves: &[[u8; 32]]) -> [u8; 32] {
    if leaves.is_empty() { return [0u8; 32]; }
    
    let mut nodes = leaves.to_vec();
    while nodes.len() > 1 {
        let new_len = (nodes.len() + 1) / 2;
        let mut next = Vec::with_capacity(new_len);
        for i in 0..new_len {
            let left = nodes[i * 2];
            let right_idx = i * 2 + 1;
            if right_idx < nodes.len() {
                let right = nodes[right_idx];
                // 关键：always 左在前 (positional)
                next.push(keccak256_concat(&left, &right));
            } else {
                // odd leaf: promote single
                next.push(left);
            }
        }
        nodes = next;
    }
    nodes[0]
}

fn build_proof(leaves: &[[u8; 32]], target_index: usize) -> Vec<[u8; 32]> {
    let mut proof = Vec::new();
    let mut nodes = leaves.to_vec();
    let mut idx = target_index;
    
    while nodes.len() > 1 {
        let sibling_idx = if idx % 2 == 0 { idx + 1 } else { idx - 1 };
        if sibling_idx < nodes.len() {
            proof.push(nodes[sibling_idx]);
        } else {
            proof.push([0u8; 32]); // promote-single 场景的占位
        }
        // build next layer
        nodes = layer_up(&nodes);
        idx /= 2;
    }
    proof
}
```

## 处理奇数 leaf

当某层 leaf 数为奇数，最后一个 leaf "提升"到上层（不与任何 sibling 配对）。这是 L2BridgeContract 也用的标准 promote-single 模式：

```solidity
// L2BridgeContract.sol L211-214
if (right < len) {
    bytes32 a = nodes[left];
    bytes32 b = nodes[right];
    nodes[i] = keccak256(abi.encodePacked(a, b));
} else {
    nodes[i] = nodes[left]; // promote single
}
```

## 跨语言 Byte-Pin

Rust + Solidity + TypeScript 三栈用同一组测试 vector 锁住 encoding：

```rust
// baby-pob-aggregator/tests/merkle_compat.rs
#[test]
fn test_known_root_5_leaves() {
    let leaves = [
        keccak256(b"leaf0"), keccak256(b"leaf1"),
        keccak256(b"leaf2"), keccak256(b"leaf3"),
        keccak256(b"leaf4"),
    ];
    let root = positional_merkle_root(&leaves);
    
    // 跨语言锁定值（与 Solidity test 一致）
    assert_eq!(
        hex::encode(root),
        "abc123...known_value"
    );
}
```

```solidity
// test/utils/MerkleTreeHelper.sol
function test_knownRoot5Leaves() public {
    bytes32[] memory leaves = new bytes32[](5);
    leaves[0] = keccak256("leaf0");
    // ...
    bytes32 root = MerkleTreeHelper.positionalRoot(leaves);
    assertEq(root, 0xabc123...known_value);
}
```

任何一栈改了 encoding，另外两栈编译期/runtime fail。

## 复杂度

| 操作                               | 复杂度             | 实测 (chain 391 gas) |
| -------------------------------- | --------------- | ------------------ |
| build root (off-chain, n leaves) | O(n)            | —                  |
| build proof (off-chain)          | O(log n)        | —                  |
| verify (on-chain)                | O(log n) keccak | \~1500 gas/level   |
| verify (1024 leaves)             | 10 levels       | \~15000 gas        |

## 已知限制

1. **不支持 sparse merkle**：当前是 dense (顺序索引)，不能省略中间空 leaf
2. **不支持 incremental update**：每次新 batch 必须从 scratch 重算 root
3. **不支持 sub-tree extraction proof**：challenger 必须知道全部 leaves 才能 build proof

主网升级建议：评估 Verkle tree 或 SMT (Sparse Merkle Tree) 替代以支持 stateful sequence。

## 相关

* [L0 PoB 行为记录](/protocol-mechanics/pob-behavior-recording.md) — Merkle tree 在 PoB 中的应用
* [Fraud-Proof 机制](/protocol-mechanics/fraud-proof-mechanism.md) — challenger 如何用 proof 反证
* `contracts/src/libraries/PositionalMerkleProof.sol` — 完整实现


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yellowpaper.axblade.io/algorithms/merkle-tree-positional.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.