Skip to content

Merkle Proof System

Jump to bottom
RunTimeAdmin edited this page Nov 3, 2026 · 15 revisions

Merkle Proof System

**Referenced Files in This Document** - [merkle.js](https://github.com/RunTimeAdmin/Sigvara/blob/main/oracle/merkle.js) - [merkle.test.js](https://github.com/RunTimeAdmin/Sigvara/blob/main/oracle/merkle.test.js) - [index.js](https://github.com/RunTimeAdmin/Sigvara/blob/main/oracle/index.js) - [SigvaraReputation.sol](https://github.com/RunTimeAdmin/Sigvara/blob/main/src/SigvaraReputation.sol) - [SigvaraReputation.t.sol](https://github.com/RunTimeAdmin/Sigvara/blob/main/test/SigvaraReputation.t.sol) - [check-evidence-fixture.mjs](https://github.com/RunTimeAdmin/Sigvara/blob/main/scripts/check-evidence-fixture.mjs)

Table of Contents

  1. Introduction
  2. Project Structure
  3. Core Components
  4. Architecture Overview
  5. Detailed Component Analysis
  6. Dependency Analysis
  7. Performance Considerations
  8. Troubleshooting Guide
  9. Conclusion

Introduction

This document explains the Merkle tree proof system used by Sigvara to commit evidence batches to the blockchain and allow consumers to verify individual pieces of evidence without downloading entire batches. The system is split between:

  • An off-chain oracle implementation that builds Merkle trees from verified payment events, generates per-leaf proofs, and serves evidence payloads.
  • An on-chain reputation contract that stores a Merkle root for each agent and exposes a gas-efficient verification function.

The design ensures that anyone can independently rebuild the committed set from on-chain payment data, confirm that a specific payment was included in the score’s evidence, and detect if an oracle changes the set afterwards. The outcome in each leaf is not on the chain, so it is the oracle's report, and the root commits the oracle to it.

Project Structure

The Merkle proof system touches three main areas:

Area Responsibility Key files
Off-chain Merkle logic Leaf encoding, tree construction, sibling-path generation, local verification oracle/merkle.js
Oracle evidence API Builds JSON evidence bodies with roots, leaves, and proofs; caches results oracle/index.js
On-chain commitment and verification Stores evidence roots per agent; verifies Merkle proofs against finalized scores src/SigvaraReputation.sol
Cross-implementation fixture guard Ensures Solidity and JavaScript agree on leaf format, pair ordering, and odd-node handling scripts/check-evidence-fixture.mjs, test/SigvaraReputation.t.sol 
graph TB
A["Oracle process<br/>oracle/index.js"] --> B["Merkle builder<br/>oracle/merkle.js"]
A --> C["HTTP evidence response<br/>JSON body with root, leaves, proofs"]
D["On-chain reputation<br/>src/SigvaraReputation.sol"] --> E["OpenZeppelin MerkleProof.verify"]
F["Tests and fixtures<br/>test/SigvaraReputation.t.sol"] --> G["Fixture generator<br/>scripts/check-evidence-fixture.mjs"]
G --> B
F --> D
Loading

Diagram sources

Section sources

Core Components

The system has four core responsibilities:

  1. Evidence leaf encoding: Each payment event is encoded into a deterministic 32-byte leaf hash.
  2. Merkle tree construction: Leaves are combined into a binary tree with sorted-pair hashing and odd-node promotion.
  3. Proof generation: For each leaf, a sibling path is produced so consumers can recompute the root locally.
  4. On-chain verification: Consumers call a view function that checks whether a leaf belongs to the committed root.

Evidence Leaf Encoding

A leaf represents one verified payment. It commits to:

  • Transaction hash
  • Payer address
  • Amount
  • Settlement time in seconds
  • Outcome code

The outcome code distinguishes three states:

State Meaning Encoded value
Failed Payment recorded but work failed 0
Succeeded Payment recorded and work succeeded 1
Not reported No outcome on record: the payment was found on chain, or attested with neither an oracle token nor the payer's signature 2

The leaf is double-hashed using keccak256. This prevents an internal node from being mistaken for a leaf and guards against second preimage attacks.

Section sources

Tree Construction and Odd Nodes

The tree is built bottom-up:

  • Leaves are hashed payment records.
  • Internal nodes are created by hashing pairs.
  • Pair order is sorted lexicographically before hashing, matching OpenZeppelin’s Merkle proof expectations.
  • If a level has an odd number of nodes, the last node is promoted rather than duplicated.

Promotion is important: duplicating the odd leaf would create a malleability vulnerability where extending the tree could still produce the same root.

Section sources

Proof Generation

For a leaf at index i, the proof contains the sibling hashes needed to walk from the leaf up to the root. The sibling list is ordered exactly as expected by MerkleProof.verify:

  • Start at the leaf.
  • At each level, include the sibling of the current node.
  • Move to the parent index.
  • Stop when reaching the root.

If there is no sibling because the node was promoted at an odd position, that level contributes no sibling.

Section sources

On-Chain Verification

The reputation contract stores one Merkle root per agent under evidenceRoots. Consumers call verifyEvidence(didHash, leaf, proof) to check whether a leaf belongs to the live evidence set.

Important behavior:

  • If no root exists for the agent, verification returns false.
  • The proof is scoped to the agent’s didHash; it cannot be reused across agents.
  • The root becomes live only after finalization; it is not active while pending.
  • The live root is the one from the last finalized proposal, so it covers the payments as they stood then. A payment credited, given an outcome or pruned since changes what /evidence serves, not what was committed.
  • Slashing clears the evidence root along with the score.

Section sources

Architecture Overview

The end-to-end flow connects off-chain evidence building with on-chain commitment and consumer verification.

sequenceDiagram
participant Oracle as "Oracle"
participant Store as "Payment store"
participant Merkle as "merkle.js"
participant API as "Evidence API"
participant Chain as "SigvaraReputation.sol"
participant Consumer as "Verifier"
Oracle->>Store : Read verified payments
Oracle->>Merkle : buildTree(events)
Merkle-->>Oracle : {root, leaves, layers}
Oracle->>API : Build evidence body
API-->>Consumer : JSON with root, leaves, proofs
Oracle->>Chain : proposeReputation(didHash, score, evidenceRoot)
Chain-->>Chain : Challenge window
Chain-->>Chain : finalizeReputation()
Chain-->>Chain : Store evidenceRoot[didHash]
Consumer->>Chain : verifyEvidence(didHash, leaf, proof)
Chain-->>Consumer : bool
Loading

Diagram sources

Detailed Component Analysis

Off-Chain Merkle Implementation

The JavaScript module implements the canonical Merkle logic used by the oracle.

Key Functions

Function Purpose Notes
settledSeconds(event) Converts millisecond timestamps to block-aligned seconds Prevents mismatch between off-chain milliseconds and on-chain seconds
outcomeCode(success) Maps boolean or null success to uint8 Three-state encoding avoids collapsing “not reported” into “failed”
leafFor(event) Encodes and double-hashes a payment event Requires a settlement transaction hash. Builds the five 32-byte words by hand and caches the leaf against a frozen event
leafByAbi(event) Produces the same leaf through the ABI coder The definition of the encoding, and the fallback for anything leafFor does not recognise
hashPair(a, b) Sorted-pair keccak256 hash Matches OpenZeppelin’s Merkle proof semantics
buildTree(events) Builds layered Merkle tree Promotes odd nodes instead of duplicating them
rootFor(events) Returns the root of that tree Cached against a frozen array of frozen events
proofFor(tree, index) Produces sibling path for a leaf Ordered for MerkleProof.verify
verifyProof(leaf, proof, root) Local proof check Used by the oracle to refuse invalid proofs

Data Structures

  • Leaves: One per payment event, derived deterministically from the payment fields on the chain plus the reported outcome.
  • Layers: Array of arrays representing tree levels from leaves to root.
  • Tree object: Contains root, leaves, and layers.

Complexity

  • Building the tree: O(E log E) over E events.
  • Generating one proof: O(log E) siblings.
  • Verifying one proof on-chain: O(log E) hash operations.
flowchart TD
Start(["Build evidence batch"]) --> Encode["Encode each event into a leaf"]
Encode --> CheckEmpty{"Any events?"}
CheckEmpty --> |No| ZeroRoot["Return zero hash root"]
CheckEmpty --> |Yes| Layers["Create leaf layer"]
Layers --> Loop{"More than one node?"}
Loop --> |Yes| Pair["Sort pair and hash"]
Pair --> NextLayer["Push next layer"]
NextLayer --> Loop
Loop --> |No| Root["Root is top node"]
Root --> Done(["Return tree"])
Loading

Diagram sources

Section sources

Oracle Evidence API

The oracle builds a JSON evidence payload per agent and payment set. The payload includes:

  • Agent identifier
  • Committed evidence root
  • Event count
  • List of committed fields
  • Per-event evidence with leaf and proof

The evidence body is cached because it is a pure function of the underlying events. It is recomputed only when payments are credited, given an outcome or pruned. The route needs no token, because a commitment only its maker can open is not a commitment to anyone else, but it is limited to 60 requests per caller per minute, since a cache miss rebuilds the tree. The didHash is read in its one lowercase spelling, so an agent has a single cache entry.

flowchart TD
Input["Agent DID + events"] --> Tree["buildTree(events)"]
Tree --> Root["tree.root"]
Tree --> Leaves["tree.leaves"]
Input --> Proofs["proofFor(tree, i) for each i"]
Root --> Body["Evidence JSON"]
Leaves --> Body
Proofs --> Body
Body --> Cache["Cache per (agent, payment set)"]
Loading

Diagram sources

Section sources

On-Chain Reputation Contract

The reputation contract integrates Merkle proofs into the scoring lifecycle.

Commitment Lifecycle

  1. Oracle proposes a score with an evidenceRoot.
  2. The root is stored in the pending proposal.
  3. During the challenge window, the committee may reject the proposal.
  4. After the window, anyone can finalize. On main, finalization refuses a proposal whose proposer has since lost its authority, and the end of the window is fixed when the score is proposed.
  5. Finalization writes the root to evidenceRoots[didHash].
  6. Slash clears both the score and its evidence root.

Verification Interface

Consumers call verifyEvidence(didHash, leaf, proof). Internally, this reads the stored root and delegates to OpenZeppelin’s MerkleProof.verify.

PendingScore also records the proposer and its finalizableAt. The Arc testnet proxy has recorded both since 26 October 2026; a proposal made before then reads zero in both.

classDiagram
class SigvaraReputation {
+bytes32[] evidenceRoots
+proposeReputation(didHash, data, evidenceRoot)
+finalizeReputation(didHash)
+rejectReputation(didHash)
+zeroReputation(didHash)
+verifyEvidence(didHash, leaf, proof) bool
+getTotalScore(didHash) uint8
+getEarnedScore(didHash) uint8
}
class PendingScore {
+data ReputationData
+proposedAt uint256
+exists bool
+evidenceRoot bytes32
+proposer address
+finalizableAt uint256
}
class MerkleProof {
+verify(proof, root, leaf) bool
}
SigvaraReputation --> MerkleProof : "uses"
SigvaraReputation --> PendingScore : "stores"
Loading

Diagram sources

Section sources

Fixture Guard and Cross-Implementation Consistency

The repository includes a dedicated script that regenerates test fixtures from the same Merkle implementation used by the oracle. This prevents silent divergence between JavaScript and Solidity.

The fixture covers:

  • Root hash
  • Individual leaf hashes
  • Sibling node hash
  • Proof values used in tests

It runs as a gate and fails if the Solidity constants do not match the current Merkle output.

Section sources

Dependency Analysis

The Merkle proof system has clear boundaries and minimal coupling.

graph LR
JS["oracle/merkle.js"] --> API["oracle/index.js"]
API --> CHAIN["src/SigvaraReputation.sol"]
CHAIN --> OZ["@openzeppelin MerkleProof"]
TEST["test/SigvaraReputation.t.sol"] --> CHAIN
FIXTURE["scripts/check-evidence-fixture.mjs"] --> JS
Loading

Diagram sources

Coupling and Cohesion

  • merkle.js is self-contained and exports pure functions.
  • index.js depends on merkle.js to build evidence payloads.
  • SigvaraReputation.sol depends only on OpenZeppelin’s Merkle verification utility.
  • Tests and fixtures enforce cross-language consistency.

External Dependencies

  • Ethereum keccak256
  • ABI encoding for deterministic leaf construction
  • OpenZeppelin’s MerkleProof.verify

Section sources

Performance Considerations

Gas-Efficient Verification

On-chain verification uses OpenZeppelin’s optimized Merkle proof verifier. The cost is dominated by log E keccak256 operations, where E is the number of evidence leaves.

Recommendations:

  • Keep evidence batches reasonably sized to limit per-proof gas costs.
  • Avoid unnecessary branching in proof computation.
  • Serve complete proofs from the oracle so consumers do not need to reconstruct them.

Batch Size Limitations

The code does not impose a hard-coded maximum batch size. Practical limits come from:

  • Oracle CPU and memory usage when building trees.
  • HTTP payload size for evidence responses.
  • On-chain gas cost for verifying longer proofs.
  • Storage and caching overhead in the oracle service.

Proof Compression Techniques

The current implementation sends full sibling paths. Possible compression strategies include:

  • Bitmask-based sibling selection to reduce repeated sibling data.
  • Index-only proofs where the client reconstructs siblings from a compact representation.
  • Batch proofs for multiple leaves sharing common ancestors.

These are optimization opportunities rather than existing features.

Storage Optimization Strategies

  • Cache evidence bodies per (didHash, events) since they are pure functions of inputs.
  • Rebuild only when the underlying payment set changes. merkle.js also caches each leaf against its frozen event and each root against its frozen event array, so the epoch does not hash an agent's evidence again when none of it changed. Hashing 5,000 events took 1,450 ms before the leaf was built by hand and 480 ms after.
  • Avoid storing redundant fields already derivable from chain data.
  • Use deterministic serialization to keep cache keys stable.

Troubleshooting Guide

Common Verification Failures

Symptom Likely cause Resolution
verifyEvidence returns false even though the payment exists No root stored for the agent Ensure the score was proposed and finalized
Proof works locally but fails on-chain Mismatch in leaf encoding or pair ordering Run the fixture generator and compare outputs
Different operators publish different roots Outcome encoding changed, inconsistent timestamp handling, or one operator holds a payment or an outcome the other lacks Confirm outcomeCode and settledSeconds are consistent, then diff the two /evidence bodies
The root from /evidence differs from the one on chain Payments were credited, given an outcome or pruned after the last finalized proposal Compare with the root of the proposal that was finalized, not the live set
Proof for one agent verifies against another agent’s root Using wrong didHash Bind proofs to the correct agent identity
Old evidence remains usable after slash Evidence root should have been cleared Verify zeroReputation clears evidenceRoots

Debugging Steps

  1. Rebuild the leaf from the payment fields using the documented encoding.
  2. Recompute the Merkle root from the same event set.
  3. Generate the sibling path for the target leaf.
  4. Call verifyEvidence with the correct didHash, leaf, and proof.
  5. If the result differs, run scripts/check-evidence-fixture.mjs to detect drift.

The site's Agents page (sigvara.xyz/agents) runs steps 1 to 4 in the browser for any agent on Arc testnet: it rebuilds each leaf from the fields the primary's /evidence lists, rebuilds the root, compares it with the roots on chain (the finalized one, and a pending proposal's if there is one), and calls verifyEvidence for every payment the finalized root covers. oracle/explorer-merkle.test.js holds the page's rebuild and oracle/merkle.js to the same leaves, roots and proofs. The SDK's evidence.ts (from 1.0.0-alpha.15) is held to the contract test's fixture, which CI holds to oracle/merkle.js, and sigvara-mcp's sigvara_verify_evidence runs the same root check, confirming up to the last 100 covered payments with verifyEvidence.

Section sources

Conclusion

Sigvara’s Merkle proof system provides auditable evidence commitments for reputation scoring. The oracle builds deterministic leaves from payment data a verifier can read on chain plus the reported outcome, constructs a Merkle tree with safe odd-node handling, and serves per-leaf proofs. The on-chain contract stores a single root per agent and exposes a simple verification interface.

The most important guarantees are:

  • Roots commit to a specific set of evidence fields.
  • Consumers can prove inclusion of a payment without trusting the oracle’s full dataset.
  • Roots become live only after finalization.
  • Slashing removes evidence so terminated agents cannot reuse old proofs.
  • Cross-implementation fixtures prevent silent divergence between off-chain and on-chain logic.

Future improvements can focus on proof compression, batch verification, and explicit batch-size policies, but the current design already balances correctness, auditability, and gas efficiency.

Home

Overview

Protocol Architecture

Smart Contracts Reference

Oracle Service

Reputation System Design

TypeScript SDK

Integration Guides

Deployment and Operations

Development and Testing

Advanced Topics

Clone this wiki locally