PaperlayerView exact revision on arXiv

Source-linked AI summary

AgentValve: Sybil-Resilient Payment Authorization for Permissionless AI Markets

Jianting Zhang, Zhongtang Luo, Aniket Kate

arXiv:2610.12948v1cs.CR

TL;DR

Permissionless AI markets let agents pay providers autonomously, while malicious buyers can deliberately consume honest routing capacity and on-chain graph-wide path discovery is costly. AgentValve uses capacity-backed trust paths, atomic reservations, off-chain route discovery, and witness-commit verification. Its evaluation reports bounded exposure under large-scale Sybil attacks and lower admission costs with witness-commit.

  • Problem

    Permissionless AI markets let agents pay providers autonomously, while malicious buyers can deliberately consume honest routing capacity and graph-wide on-chain path discovery is costly.

    Source: §1 · pp. 1–2

  • Method

    AgentValve authorizes payments through finite-capacity trust paths, atomically reserves supporting capacity, and uses off-chain route discovery with witness-commit verification.

    Source: §1 · p. 2

  • Results

    Under attacks with up to 10,000 Sybil identities, exposure stayed within the fixed cut bound; witness-commit reduced admission cost by up to 40.8% versus a per-edge-record baseline.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The prototype’s guarantees remained effective under large-scale Sybil attacks while incurring practical on-chain costs.

    Source: §6 · p. 14

    Cut-bounded exposure limits snapshot risk, not cumulative fraud loss; neutral timeout resolution can restore capacity when buyers fail to report service failures before the deadline.

    Source: §6 · p. 14

Abstract

from arXiv · show

AI agents increasingly select and pay service providers without human review. In emerging permissionless markets, however, adversaries can create inexpensive identities and fabricate feedback to inflate provider reputation, making reputation-based payment authorization vulnerable to Sybil attacks and exposing clients to unbounded financial loss. This paper presents AgentValve, a protocol for Sybil-resilient payment authorization in permissionless AI markets. AgentValve builds on a trust network that represents reputation as finite capacity in a directed graph and authorizes payments through trust paths with sufficient available capacity. A smart contract atomically reserves the capacity supporting each admitted payment, bounding honest agents' payment exposure by the capacity they extend into the adversarial region, and thus creating identities or interactions entirely within that region cannot increase this bound. To limit capacity depletion by malicious senders, AgentValve combines payment-backed capacity creation with bounded route length, preventing attackers from depleting honest capacity without incurring corresponding payment costs. AgentValve further decouples off-chain route discovery from on-chain verification and introduces a witness-commit mechanism that reduces route verification to linear work while requiring only constant persistent state per admitted payment. We implement a AgentValve prototype and evaluate it using six months of Ethereum data and synthetic workloads. Experimental results show that under attacks with up to 10,000 synthetic Sybil identities and with chosen attackers, the payment exposure and capacity depletion remain bounded. Regarding practicality, the witness-commit mechanism lowers admission cost by up to 40.8% compared with baselines, and admitting common payments costs approximately \$0.04-\$0.21.

1 Introduction

AgentValve authorizes payments through finite-capacity trust paths to address risks in permissionless AI markets. It combines exposure bounds, bounded depletion, and scalable on-chain verification with prototype results showing bounded attacks and practical costs.

Motivation

  • Permissionless AI markets expose reputation-based provider selection and payment authorization to coordinated Sybil feedback that can inflate provider reputation and put client funds at risk.AgentValve models trust as finite capacity in a directed graph and admits payments only when paths can support their value.Source: §1 · pp. 1–2

Cut-bounded exposure

  • Honest agents’ aggregate exposure to adversarial providers is bounded by the capacity crossing the honest-to-adversarial cut, which identities or inflated capacities within the adversarial region cannot enlarge.The bound applies collectively to all adversarial identities.Source: §1 · p. 2

Concurrent payment authorization

  • Atomic reservation prevents concurrent payments from exceeding shared edge capacity, while feedback resolution releases capacity after positive or neutral outcomes and consumes it after negative feedback.This allows capacity associated with successful payments to be reused.Source: §1 · p. 2

Capacity depletion

  • Hmax limits depletion amplification: cumulative honest-to-honest capacity depletion is at most Hmax −1 times adversarial-to-honest payment value.Each path that depletes honest capacity must first cross into the honest region.Source: §1 · p. 2

On-chain verification

  • Off-chain pathfinders discover routes while the contract verifies them; witness-commit supports linear route verification and constant persistent receipt state per admitted payment.The witness aggregates repeated edge loads, and the contract stores a constant-size commitment rather than per-edge reservation records.Source: §1 · p. 2

Implementation and results

  • Up to 40.8%, witness-commit reduced admission cost versus a baseline that reconstructs and stores per-edge reservation records; common payments cost approximately $0.04–$0.21.Exposure stayed within the fixed cut bound under attacks with up to 10,000 Sybil identities, and constructed depletion workloads attained the amplification bound.Source: §1 · p. 2

2 Background, Related Work, and Motivation

This section motivates AgentValve by connecting blockchain execution constraints and reputation risks to trust networks. Prior work provides the capacity-based foundation for bounding the influence of Sybil identities.

2.1 Blockchain Execution Model

  • Replicated, metered blockchain execution makes graph-wide path discovery costly on-chain; AgentValve uses atomic execution, off-chain discovery, and finalized ledger data for verification and recovery.Transactions commit all state updates or none, and validators enforce execution and resource limits.Source: §2.1 · p. 3

2.2 Agent Registries and Reputation Risks

  • More than 98% of ERC-8004 feedback records lack declared payment proof or task linkage, and measured coordinated campaigns leave many rated agents without remaining feedback.A single ceiling-valued feedback record can move the median rated agent above the representative threshold of 90 at median gas costs of $0.055 on Ethereum, $0.0042 on BNB Chain, and $0.0027 on Base.Source: §2.2 · p. 3

2.3 Trust Networks

  • Trust-network flow is bounded by cut capacity, so identities or capacity added behind a cut cannot raise that bound; Ostra, SumUp, and Bazaar apply capacity constraints to limit resource use or risk.AgentValve builds on personalized flow and Bazaar’s reservation and feedback semantics, with off-chain routing and on-chain execution exemplified by Circles [7] and Trustlines [45].Source: §2.3 · pp. 3–4

3 System Model and Design Goals

AgentValve models payment authorization as trust-capacity accounting in a permissionless system. Its design goals address adversarial exposure and capacity depletion while requiring sound resolution and bounded on-chain work and state.

3 System Model and Design Goals

  • Payments are authorized by personalized trust capacity: admission atomically transfers value and reserves supporting capacity, while feedback resolves reservations and updates the trust network.Pathfinders compute candidate routes from public blockchain data, and the contract validates route-dependent state transitions.Source: §3 · p. 4, §3.1 · p. 4

3.1 System Model

  • The model uses a directed trust graph with available and reserved edge capacity, bounded route length and path count, and a witness recording aggregate loads on distinct route edges.Payment values and capacities share a fixed asset denomination, avoiding a price oracle.Source: §3.1 · p. 4

3.2 Threat Model and Assumptions

  • The adversary may create arbitrarily many Sybil identities and arbitrary internal trust relationships, but cannot compromise blockchain security; honest clients are assumed to resolve receipts before timeout.The model also assumes eventual timeout resolution and access to finalized admission data or load events.Source: §3.2 · p. 5

3.3 Security and Efficiency Goals

  • Cut-bounded exposure applies collectively to adversarial identities, while bounded depletion amplification limits honest-to-honest capacity consumed by malicious buyers relative to their payments to honest agents.These properties address complementary risks: client losses to adversarial providers and malicious buyers’ depletion of honest capacity.Source: §3.3 · p. 5
  • AgentValve targets route soundness and eventual resolution alongside verification and resolution costs that scale at most linearly with route size and constant persistent contract state per payment.The contract must reserve and later resolve exactly the route’s aggregate edge loads.Source: §3.3 · p. 5

4 AgentValve Design

AgentValve separates off-chain route discovery from on-chain verification and capacity reservation, then resolves reservations through feedback or timeout. Its design combines atomic accounting, payment-backed capacity, bounded routes, and compact route commitments.

4 AgentValve Design

  • Atomic reservations bound honest agents’ exposure by honest-to-adversarial cut capacity; payment-backed capacity and routes of at most Hmax edges bound depletion amplification to Hmax −1.Off-chain discovery, linear route verification, constant persistent state, and timeout resolution provide route soundness and eventual resolution.Source: §4 · p. 6

4.1 Protocol Initialization

  • Setup fixes route and resource limits, seeds finite available capacity from TrustRoots, and leaves the public interface open to any client after initialization.Initialization occurs once.Source: §4.1 · p. 6

4.2 Agent Registration and Trust Bootstrap

  • Clients register stable agent identities and bootstrap trust through TrustRoot capacity grants or seed payments that support a first purchase.Provider bootstrap capacity is tied to an irrecoverable fee of the same value, so Sybil identities cannot obtain it for free.Source: §4.2 · p. 6

4.3 Payment Admission and Capacity Reservation

  • A payment is admitted only with a feasible route carrying value W; admission transfers W, reserves aggregate edge loads atomically, and creates a receipt for resolution.Failed admission reverts without modifying AgentValve state.Source: §4.3 · p. 7

4.3.1 Compute–verify Decomposition

  • Route discovery runs off-chain, while the contract rejects stale, malformed, or infeasible pathfinder routes without changing trust-network state.The prototype pathfinder bounds path length by Hmax and the number of selected paths by Kmax.Source: §4.3.1 · p. 7

4.3.2 The Witness-commit Mechanism

  • A sorted edge-load witness lets the contract verify aggregate loads in O(L+U) work, then a hash commitment reduces persistent receipt state from O(U) to O(1).The resolver re-supplies the committed table, which is recoverable from public admission data for timeout resolution.Source: §4.3.2 · pp. 7–8

4.4 Feedback and Timeout Resolution

  • Sender feedback releases reserved capacity after positive or neutral feedback, permanently consumes it after negative feedback, and timeout resolution prevents indefinite reservations.Receiver feedback does not resolve reservations; negative receiver feedback can reduce reverse capacity.Source: §4.4 · p. 8

5 Implementation and Evaluation

The evaluation tests AgentValve’s security bounds, on-chain costs, and routing utility using Ethereum-derived and synthetic graphs. Across these settings, it measures Sybil exposure, capacity depletion, admission cost, and routing outcomes under bounded routes.

5.1 Sybil Exposure and Capacity Depletion

  • AgentValve’s exposure remains at cut capacity C as Sybil identities grow, while global-count and global-volume authorize mC for m identities.This holds in both the Ethereum-derived and synthetic settings.Source: §5.1 · p. 10, Figure 4 · p. 10
  • Ethereum-derived depletion amplification rises from 0.5 at Hmax = 2 to 3.6 at Hmax = 8, then falls to 3.06 at Hmax = 16.At Hmax = 16, downstream honest-edge capacity can bottleneck depletion despite greater adversarial payment.Source: §5.1 · p. 10, Figure 5 · p. 11
  • Synthetic worst-case depletion amplification equals Hmax −1, reaching 15 at Hmax = 16 and matching the bound.With equal-capacity edges, depleted capacity grows as DH = (Hmax −1)PA→H.Source: §5.1 · p. 10, Figure 5 · p. 11

5.2 On-Chain Execution Cost

  • At eight hops and eight paths, witness-commit saves 35.1% over witness-store and 40.8% over route-aggregation store.Across the tested routes, witness-commit reduces admission gas, with savings generally growing as route complexity increases.Source: §5.2 · p. 11, Figure 6 · p. 11
  • A one-hop, one-path admission consumes 168,741 gas, or approximately $0.04–$0.21 under the reported prices.This common-case route is 3.14× the route-free ERC-20 transferFrom baseline.Source: §5.2 · p. 11, Figure 6 · p. 11

5.3 Routing Utility and Pathfinder Scalability

  • On the Ethereum-derived graph, admission rises from 13% at (Hmax,Kmax) = (2,1) to 50% at (10,8).At (10,8), 44% of requests remain infeasible even under unrestricted maximum flow.Source: §5.3 · p. 12, Figure 7 · p. 13
  • On the Ethereum-derived graph, all three pathfinders achieve identical topology-feasible admission rates as Hmax rises from 2 to 10 at Kmax = 4.The reported rates range from 23.2% to 89.3%, indicating that route bounds dominate utility in this graph.Source: §5.3 · p. 12, Figure 7 · p. 13
  • On the 8,192-vertex synthetic graph, admission reaches 100% at (Hmax,Kmax) = (10,8); at (6,4), capacity-scaling BFS and repeated widest-path each admit 85%.Across synthetic graph sizes, allowing two paths maintains 98–100% admission at Hmax = 10.Source: §5.3 · p. 13, Figure 8 · p. 13

6 Conclusion and Discussion

AgentValve combines payment authorization guarantees against Sybil-driven exposure and malicious capacity depletion with efficient route verification. The discussion notes that exposure is a snapshot bound, the depletion accounting does not establish net attack cost, and reservation griefing remains a concern.

6 Conclusion and Discussion

  • AgentValve provides cut-bounded exposure and limits malicious capacity depletion through atomic route reservation, interaction-backed capacity creation, and bounded route length.Its exposure bound applies collectively to adversarial identities and cannot be enlarged through reputation manipulation confined to the adversarial region.Source: §6 · p. 14
  • The witness-commit mechanism enables linear route verification and constant persistent state per admitted payment.The prototype evaluation reports that the guarantees remain effective under large-scale Sybil attacks while incurring practical on-chain costs.Source: §6 · p. 14
  • The depletion factor (Hmax −1) is retained as a conservative upper bound, although cumulative payment accounting yields a tighter general bound of max{1,Hmax −2}.For negatively resolved ordinary routed payments, the factors are Hmax −2 for adversarial receivers and (Hmax −1)/2 for honest receivers; negatively resolved seed payments give a factor of 1.Source: §6 · p. 14
  • Cut-bounded exposure limits snapshot risk, not cumulative fraud loss; neutral timeout resolution can restore capacity after unreported service failures and permit repeated losses.Increasing the feedback timeout may reduce this risk but withholds capacity longer; the paper suggests adaptive timeouts as a possible direction.Source: §6 · p. 14
  • The depletion denominator counts gross protocol payments, so the bound does not establish a lower bound on net attack cost.Estimating net cost would require assumptions about service value, refunds, transaction fees, and opportunity costs.Source: §6 · p. 14
  • A malicious buyer can repeatedly reserve a route until feedback timeout and reserve it again after neutral resolution, denying capacity to honest buyers.Path-length and path-count bounds limit how much capacity a single payment can withhold; further mitigation remains future work.Source: §6 · p. 14

A Security and Complexity Analysis

The section proves AgentValve’s exposure, depletion, route-soundness, and eventual-resolution properties, then shows that it meets the efficiency goal.

A Security and Complexity Analysis

  • The section proves cut-bounded exposure, bounded depletion amplification, route soundness, and eventual resolution, and shows that AgentValve meets its efficiency goal.Source: A Security and Complexity Analysis · p. 16

A.1 Commitment and Capacity Accounting

AgentValve commits to an admitted route witness so it can be recovered and checked later, and maintains an invariant accounting for available, reserved, and total capacity.

A.1 Commitment and Capacity Accounting

  • A witness opens a receipt only when its encoding matches the stored commitment, and any party can reconstruct the admitted witness independently of the pathfinder.The witness is included in finalized admission calldata and load events.Source: §A.1 · p. 16
  • For every edge, total capacity equals available plus reserved capacity; admission atomically moves supporting loads into reservations, and resolution releases or consumes each reservation exactly once.Positive sender feedback additionally creates capacity on the sender-to-receiver edge; negative resolution consumes reserved capacity.Source: §A.1 · p. 17

A.2 Exposure and Depletion Bounds

The analysis bounds honest agents’ exposure by the honest-to-adversarial cut and bounds depletion of honest capacity relative to adversarial payments to honest agents. It also establishes route soundness and eventual resolution.

A.2 Exposure and Depletion Bounds

  • At a state, exposure from unresolved and jointly admissible payments is at most the available plus reserved capacity on the honest-to-adversarial cut; losses from previously resolved receipts are excluded.Atomic reservation prevents concurrent payments from reusing cut capacity.Source: §A.2 · p. 17
  • Holding honest-to-adversarial cut capacity fixed, adding adversarial identities or changing internal adversarial edges and capacities leaves the aggregate exposure bound unchanged.An explicit TrustRoot grant can increase the bound, but it charges an irrecoverable fee and draws from a periodically replenished grant budget.Source: §A.2 · pp. 17–18
  • For seed payments from adversarial senders, negative sender feedback consumes at most the value of those payments to honest receivers.The argument counts each negatively resolved seed payment as both depletion and a payment admitted by the protocol.Source: §A.2 · p. 18
  • AgentValve bounds depletion amplification by Hmax −1, where Hmax is the maximum route length.The route-level argument bounds honest-to-honest load for an adversarial sender by (Hmax −1) times the load crossing from the adversarial region into the honest region.Source: §A.2 · pp. 17–18
  • The depletion denominator is cumulative value transferred through the protocol from adversarial agents to honest agents, not adversarial net economic loss.Service value, refunds, reciprocal payments, and transfers outside the protocol are not deducted.Source: §A.2 · p. 18

A.3 Integrity and Liveness

  • Route soundness ensures admitted transactions are feasible at atomic admission, while eventual resolution prevents reservations from being held indefinitely under the stated maintenance assumption.After the feedback deadline, an honest party can resolve an outstanding role using the admitted witness when needed.Source: §A.3 · pp. 18–19

A.4 On-chain Complexity

Witness-commit bounds on-chain route verification by route parameters rather than trust-graph size, while keeping persistent receipt storage constant.

A.4 On-chain Complexity

  • Verification requires O(L(P)+U) work, bounded by O(KmaxHmax) and independent of trust-graph size.Route discovery is off-chain; verification processes only the submitted route, witness, and corresponding edge states.Source: §A.4 · p. 19
  • Witness-commit verifies route paths and edge loads in one scan, using O(U) auxiliary memory.The scan checks path structure and certificates, accumulates loads into indexed witness entries, and validates the claimed table against available capacity.Source: §A.4 · p. 19
  • Persistent receipt storage is O(1), while opening and resolving a routed receipt require O(U) witness data and work.The receipt stores a hash commitment and fixed-size metadata; resolution re-supplies the witness table.Source: §A.4 · p. 19
  • Seed receipts use O(1) persistent storage and O(1) admission and resolution work.A seed receipt identifies its single reserved edge and payment value through constant-size metadata, so it needs no route witness.Source: §A.4 · p. 19

B Additional Evaluation

The additional evaluation covers an Ethereum-derived graph and synthetic graphs with different stated sizes, edge counts, and capacity distributions.

B Additional Evaluation

  • The Ethereum-derived graph has 1,055 vertices, 1,628 directed edges, and median capacity 0.00494 ETH.It is derived from Ethereum data.Source: B Additional Evaluation · p. 20
  • Synthetic graphs have six directed edges per vertex, with capacities sampled uniformly from [10,100].Source: B Additional Evaluation · p. 20
  • The section evaluates topology-sensitive liquidity loss and transaction contention across Ethereum-derived and synthetic graph settings.Source: B Additional Evaluation · p. 20

B.1 Reachability under Capacity Depletion

Under equal unit-capacity depletion budgets, targeted edge removal reduces reachability more than random removal, with especially large losses on the Ethereum-derived graph.

B.1 Reachability under Capacity Depletion

  • The evaluation assigns unit capacity to each edge and compares unweighted-edgebetweenness-ranked removal with random removal, measuring directed reachable source–destination pairs.Random-removal evaluations use 20 attempts; targeted-removal evaluations are deterministic.Source: §B.1 · p. 20
  • At approximately 1% edge depletion, targeted versus random removal cuts reachable pairs by 36.08% versus 1.84% on Ethereum-derived graphs, and 0.49% versus 0.0024% on 2,048-vertex synthetic graphs.Figure 9 compares these topology settings under the same approximate depletion budget.Source: §B.1 · p. 20
  • On the Ethereum-derived graph, removing the highest-ranked edge eliminates 11.78% of reachable pairs, compared with 0.27% on average under random removal.The graph has 20,509 reachable ordered pairs before removal.Source: §B.1 · p. 20
  • This sensitivity test removes monetary heterogeneity, assumes access to suitable ingress capacity and routes, and measures reachability loss rather than lost payment value.The passage attributes the especially large Ethereum-derived loss to concentration in the current young ecosystem.Source: §B.1 · p. 20
  • Potential defenses include criticality-aware path scoring, edge-disjoint or low-overlap routes, and monitoring central edges; these remain open design problems.The passage also proposes reserving less of a bridge edge per transaction.Source: §B.1 · p. 20

B.2 Contention under Stale Route Snapshots

With delayed pathfinder snapshots and serialized admissions, fresh-route retries improve admission under contention, but larger transaction values and insufficient aggregate capacity still constrain success.

B.2 Contention under Stale Route Snapshots

  • On the controlled parallel graph, hotspot admission falls from 50.0% to 3.1% as transaction value increases from 5 to 80.The graph has eight independent source–destination groups, each connected by eight parallel two-hop branches.Source: §B.2 · p. 20
  • At 1,600 requests per block, four-block delay, and retry, uniform-demand admission falls from 100.0% at value 5 to 53.9% at value 80.Under hotspot demand, admission falls from 73.6% to 4.6% over the same value sweep.Source: §B.2 · p. 20, Figure 11 · p. 21
  • At 1,600 requests per block and four-block delay, retry raises admission from 84.2% to 100% under uniform demand and from 9.9% to 36.8% under hotspot demand.The comparison is on the 2,048-vertex synthetic graph; the hotspot gain is 26.9 percentage points.Source: §B.2 · p. 20, Figure 10 · p. 21
  • Retry mitigates stale-route failures but cannot overcome insufficient aggregate capacity, and larger transaction values expose this economic limit.The evaluation uses common snapshots within each block, serialized contract admissions, and two-block reservation locks.Source: §B.2 · pp. 20–21

C Dataset Collection and Processing

The dataset traces owner-to-owner Ethereum transfers during the ERC-8004 deployment window, filtering transactions and aggregating retained transfers into a directed graph. Its initialization optimistically treats each retained historical transfer as positively resolved under AgentValve.

C Dataset Collection and Processing

  • The collection spans blocks 24,339,871–25,664,244, from ERC-8004’s January 29, 2026 deployment through the August 2, 2026 cutoff.Transfer events reconstruct ownership intervals, allowing interactions to be retained only when an address owned a registered agent at the transaction’s exact block and position.Source: C Dataset Collection and Processing · p. 21
  • Of 491,079 raw owner interactions, filtering leaves 34,507 owner-to-owner candidates and ultimately 12,527 valid retained transactions.Filters exclude registry and burn addresses, non-owner endpoints, failed or reverted transactions, self-transfers, and zero, negative, or invalid values.Source: C Dataset Collection and Processing · p. 21, Figure 12 · p. 22
  • The final graph contains 1,055 owner vertices, 1,628 directed edges, and 12,527 retained transactions totaling 169.294 ETH.Each owner address represents one vertex annotated with its ERC-8004 agents, and edge capacity is the aggregate transferred value between owners.Source: C Dataset Collection and Processing · p. 21
  • The graph is an optimistic proxy: it treats every retained historical transfer as if its sender had positively resolved it under AgentValve.The construction preserves edge direction and excludes ERC-8004 feedback because it is not reliably bound to an interaction and is susceptible to fictitious activity.Source: C Dataset Collection and Processing · p. 21
  • The Ethereum-derived graph is sparse: only 1.844% of ordered owner pairs are reachable, and its largest weakly connected component has 213 vertices.The graph has 137 weakly connected components and 752 strongly connected components; the collection-window graph grows over time.Source: C Dataset Collection and Processing · p. 22, Figure 12 · p. 22
  • 10,899 of 12,527 retained transfers (87.0%) occur after an earlier transfer by the same owner pair.The remaining 1,628 transfers are the first retained transfer for their pair.Source: C Dataset Collection and Processing · p. 22
Loading 2610.12948v1…