Skip to content

[CRITICAL][Tier-A] Reputation lazy Merkle-sum tree with incremental on-chain scoring #387

Open
Open
[CRITICAL][Tier-A] Reputation lazy Merkle-sum tree with incremental on-chain scoring#387
Labels
GrantFox OSSIssue tracked in GrantFox OSSMaybe RewardedIssue may be eligible for a GrantFox rewardThird CampaignCampaign: Third Campaigncritical

Description

@jotel-dev
jotel-dev
opened on Aug 18, 2026

Tier
Tier A · CRITICAL — Gas-efficient stateful aggregation.

Context
contracts/reputation/src/lib.rs compute_score iterates up to MAX_TRADES (200) sequential trades by calling get_trade_by_index + get_trade on the escrow contract for every single index. On a busy mainnet deployment this is ~200 cross-contract calls per compute_score. The score is recomputed from scratch every time, even when only one new trade changed.

Goal
Replace the linear scan with a Merkle-sum tree (MST) maintained by the escrow contract. Each leaf is a trade's (amount, status, timestamp). The root is updated atomically on release / refund / dispute_resolve. The reputation contract then validates a sparse Merkle proof (≤3 hashes) instead of scanning.

Non-goals
No off-chain indexer that feeds the tree (the root must be derivable purely from on-chain state).
No ZK proof for the score — the score is still computed in Solidity/Rust, just over a smaller tree.
No change to the external compute_score(address) API.

Data model
New types in contracts/reputation/src/lib.rs:

  • ReputationLeaf: (trade_id_hash, amount, status_bits, counterparty_hash, ledger)
  • ScoreProof: (leaf_index, sibling_hashes[..MAX_DEPTH], score_components)

New storage in contracts/escrow/src/lib.rs:

  • ReputationRoot(BytesN<32>) — current MST root, updated on terminal trade state changes.
  • ReputationLeaf(BytesN<32>) — leaf data for each completed/refunded trade.

Implementation plan

  1. Add MerkleSumTree module to contracts/escrow/src/lib.rs (or a shared htlc-core crate). Leaf hash = H(amount || status || counterparty_hash || ledger).
  2. In release, refund, batch_release, resolve_dispute, and fallback_after_timeout, update the MST root after flipping state. Use a helper update_reputation_root(env, trade_id, old_status, new_status, amount).
  3. Add a new read-only escrow contract method get_reputation_root() -> BytesN<32> and get_reputation_proof(address, max_trades) -> ScoreProof.
  4. Rewrite contracts/reputation/src/lib.rs compute_score to accept a ScoreProof from the caller (or fetch it via cross-contract call if the caller is the contract itself). Verify the MST path matches ReputationRoot.
  5. Add compute_score_incremental that only touches new leaves since the last cached score.
  6. Write contracts/reputation/src/mst_test.rs with randomized insertion/deletion/verification property tests.

Thresholds

  • MAX_TRADES can increase to 10,000 because MST verification is O(log n).
  • DECAY_TABLE index must be derived from the MST leaf's ledger field, not a global scan.

Acceptance criteria

  • compute_score executes in <500k instructions for 10,000 trades (benchmark under cargo test).
  • A proof with a single altered leaf fails MST verification.
  • Escrow terminal-state transitions still publish the same events; released / refunded / disp_res / disp_exp events are unchanged.
  • Existing get_score and get_score_breakdown read methods continue to work; they internally fetch and verify the MST proof.

Related files

  • contracts/reputation/src/lib.rs
  • contracts/escrow/src/lib.rs
  • contracts/htlc-core/src/lib.rs
  • contracts/reputation/src/test.rs
  • contracts/reputation/src/benchmarks.rs
  • packages/shared/src/index.ts

Contributor notes
A Merkle-sum tree is strictly better than a Merkle tree here because score math is additive. Reuse the Htlc trait's terminal-state transition points to keep MST updates atomic. Benchmark before and after — the gas delta is the selling point for mainnet.

Activity

  1. jotel-dev
    added
    critical
    on Aug 18, 2026

  2. Muhammadcodes112 commented on Aug 18, 2026

    @Muhammadcodes112
    Muhammadcodes112
    on Aug 18, 2026 – with GrantFox OSS

    I’ve assessed the scope of this issue and have a clear roadmap for the implementation. I can have this completed and tested by [Date/Time]. I'll ensure the code is well-documented and includes unit tests. Please go ahead and assign this to me.

  3. OZILSOLAR commented on Aug 18, 2026

    @OZILSOLAR
    OZILSOLAR
    on Aug 18, 2026 – with GrantFox OSS

    Hi team!!!!
    I would like to work on this issue!!!!!

  4. grantfox-oss
    added
    GrantFox OSSIssue tracked in GrantFox OSS
    Maybe RewardedIssue may be eligible for a GrantFox reward
    Third CampaignCampaign: Third Campaign
    on Aug 18, 2026
  5. grantfox-oss
    assigned
    Muhammadcodes112
    on Aug 18, 2026

  6. grantfox-oss commented on Aug 18, 2026

    @grantfox-oss
    grantfox-ossbot
    on Aug 18, 2026 – with GrantFox OSS

    🦊 GrantFox — @Muhammadcodes112 has been assigned to this issue as part of the Third Campaign campaign!

    Next steps:

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

    Good luck! Track your progress on GrantFox.

  7. jotel-dev
    unassigned
    Muhammadcodes112
    on Sep 7, 2026

  8. Ranjeet2063 commented on Sep 12, 2026

    @Ranjeet2063
    Ranjeet2063
    on Sep 12, 2026

    Hi @jotel-dev and maintainers,

    I would like to resolve this critical issue: [CRITICAL][Tier-A] Reputation lazy Merkle-sum tree with incremental on-chain scoring.

    Following my contribution on PR #475 (implementing the deterministic Merkle-Patricia Trie verifier), I have analyzed the gas bottleneck in contracts/reputation/src/lib.rs where linear scans across 200 sequential trades trigger cross-contract gas exhaustion.

    Proposed Architectural Execution Plan:

    1. On-Chain Sparse Merkle-Sum Tree (SMST) Engine:
      • Introduce a fixed-depth binary Merkle-Sum Tree directly in contracts/reputation/ & contracts/escrow/.
      • Each leaf node represents a trade entry packing (amount: i128, status: u32, timestamp: u64) into a canonical 32-byte leaf digest.
      • Intermediate nodes store both the cryptographic parent hash $H(\text{left} \mathbin{\Vert} \text{right})$ AND cumulative trade volume $V = V_{\text{left}} + V_{\text{right}}$.
    2. Atomic In-Place Root Updates in Escrow:
      • On state-transition events (release, refund, dispute_resolve), the escrow contract updates strictly the $O(\log N)$ branch path from leaf to root (depth 6 = strictly 6 SHA-256 rounds), maintaining an active state root under $&lt;45,000$ CPU instructions.
    3. Logarithmic Reputation Scoring:
      • Refactor compute_score(address) to consume sparse Merkle-sum inclusion proofs ($\le 3$ hashes).
      • Verifies authenticated cumulative volume and dispute rates in constant time without linear cross-contract loops.
    4. Soroban no_std Compliance & Testing:
      • Pure soroban_sdk::crypto implementation without heap allocations.
      • Comprehensive unit and adversarial property tests (root correctness across sequential updates, forged leaf rejection, sum-overflow invariants).

    Ready to begin implementation immediately and deliver a production-ready, 100% green CI pull request.

  9. rupesh-kumar-sah commented on Oct 1, 2026

    @rupesh-kumar-sah
    rupesh-kumar-sah
    on Oct 1, 2026

    Hi team,

    I would like to take on and implement this issue: [CRITICAL][Tier-A] Reputation lazy Merkle-sum tree with incremental on-chain scoring.

    Technical Implementation Roadmap:

    1. Formal Soroban Invariant Design: Audit storage layout (Instance, Persistent, Temporary) with strict TTL management and explicit require_auth guards.
    2. Core Rust WASM Implementation: Implement deterministic state transition handlers eliminating arithmetic overflow risks using checked/saturating math.
    3. Hermetic Testing Suite: Build comprehensive test cases in tests/ asserting authorized vs unauthorized invocations, mock auth environments, and edge value bounds.
    4. Gas & Footprint Optimization: Profile CPU/memory instruction budgets under Soroban host environment to ensure optimal runtime efficiency.

    I have worked extensively on similar architectures and can deliver this cleanly within 24 hours. Please assign to me!

  10. ranjeet150 commented on Oct 1, 2026

    @ranjeet150
    ranjeet150
    on Oct 1, 2026

    Hi team,

    I would like to take on and implement this issue: [CRITICAL][Tier-A] Reputation lazy Merkle-sum tree with incremental on-chain scoring.

    Technical Implementation Roadmap:

    1. Formal Soroban Invariant Design: Audit storage layout (Instance, Persistent, Temporary) with strict TTL management and explicit require_auth guards.
    2. Core Rust WASM Implementation: Implement deterministic state transition handlers eliminating arithmetic overflow risks using checked/saturating math.
    3. Hermetic Testing Suite: Build comprehensive test cases in tests/ asserting authorized vs unauthorized invocations, mock auth environments, and edge value bounds.
    4. Gas & Footprint Optimization: Profile CPU/memory instruction budgets under Soroban host environment to ensure optimal runtime efficiency.

    I have worked extensively on similar architectures and can deliver this cleanly within 24 hours. Please assign to me!

  11. ravimahatonp commented on Oct 1, 2026

    @ravimahatonp
    ravimahatonp
    on Oct 1, 2026

    Hi maintainers,

    I would like to take on and implement this issue: [CRITICAL][Tier-A] Reputation lazy Merkle-sum tree with incremental on-chain scoring.

    Technical Implementation Roadmap:

    1. Formal Soroban Invariant Design: Audit storage layout (Instance, Persistent, Temporary) with strict TTL management and explicit require_auth guards.
    2. Core Rust WASM Implementation: Implement deterministic state transition handlers eliminating arithmetic overflow risks using checked/saturating math.
    3. Hermetic Testing Suite: Build comprehensive test cases in tests/ asserting authorized vs unauthorized invocations, mock auth environments, and edge value bounds.
    4. Gas & Footprint Optimization: Profile CPU/memory instruction budgets under Soroban host environment to ensure optimal runtime efficiency.

    Ready to implement and deliver a production-grade PR following all repository standards. Please feel free to assign!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    GrantFox OSSIssue tracked in GrantFox OSSMaybe RewardedIssue may be eligible for a GrantFox rewardThird CampaignCampaign: Third Campaigncritical

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions