WorksComputer Science
Anduin: A sybil-resistant agentic marketplace reputation system
Abstract
As autonomous AI agents enter permissionless onchain markets, selecting new service providers remains a core challenge. Existing reputation systems depend on scarce resources like human curation, identity credentials, or voluntary reviews, while naive volume rankings are vulnerable to Sybil attacks. We evaluate whether existing onchain payment histories can yield provider ratings that are resilient against Sybil attacks. Using a 157-day dataset comprising 66M agentic transactions worth $6.1M across 16 blockchains, we model payment flows as a bipartite graph between buyers and providers. A provider's rating is derived from graph paths linked to a buyer's existing trusted network. We propose three Sybil-resistant rating algorithms: a max-flow rating and two relaxed algorithms optimized for stronger rating performance. Evaluating these algorithms against simulated adversaries across 813 buyers, we show that rating manipulation costs 20% of those buyers' total spend and is around 23x harder to manipulate than the standard similarity rule (collaborative filtering).
Introduction
AI agents are transacting autonomously, selecting and paying for online services to fulfill delegated tasks [7, 26]. Small, automated microtransactions suit traditional checkout rails poorly [18, 30], making onchain stablecoins the default settlement medium.
However, permissionless networks create a discovery dilemma: anyone can list an endpoint with arbitrary descriptions, leaving buyers unable to distinguish reliable providers from fraudulent or low-quality services. While human commerce relies on brand reputation, reviews, and legal recourse [20, 24], autonomous agents cannot efficiently access these datapoints. Current reputation solutions impose restrictive assumptions that undermine open markets: curation of the marketplace prohibits open participation [6], identity credentials attest to entity identity rather than service quality [4], escrowed evaluators can incur fees that dwarf the sub-cent payments evaluated [8], and voluntary onchain ratings are sparsely reported (< 4,000 ratings total) [29].
A naive alternative ranks providers by raw onchain usage—counting transactions, counterparties, or volume [6]. However, usage metrics are not effective against Sybil attacks [11]: an adversary can fund its own wallets and loop self-payments to inflate its rank. In active marketplaces, manipulating median reputation costs just $0.0027 (1/259th of median volume) [29]. Heavyweight solutions impose costs incompatible with micropayments, while lightweight defaults offer no Sybil protection.
In this work, we address the research question: Can a reputation system for agentic commerce be constructed purely from payments already settled onchain while rendering Sybil manipulation provably costly?
Defeating Sybil attacks is straightforward if protocols can be altered: deposits, proof-of-work, or credentials make synthetic identities costly. However, each requires participants to lock capital, burn compute, or obtain attestations and that both parties agree to a convention prior to transacting. We therefore consider whether Sybil security guarantees can be attained strictly from existing payment records without protocol changes.
We show that a graph-based flow measurement indeed achieves this. We assemble a continuous 157-day settlement dataset from x402, the largest agentic marketplace. It comprises 66,073,201 payments across 16 blockchains between March 23 and August 26, 2026 from 162,882 buyers and 50,390 providers, totalling $6.1M in volume at a median payment of $0.01.
From the data, we construct a bipartite buyer-provider graph. Drawing on graph-based reputation [22] and localized graph defenses [1, 15], our solution Anduin rates candidate providers by routing network flow from providers the buyer already pays (“known” providers). Because every path originates from the buyer’s established payments, an adversary cannot fabricate reputation via synthetic nodes; it must route capital into the buyer’s trusted neighborhood, economically bounding manipulation.
We present Anduin, a Sybil-resistant rating system for agentic commerce. Its construction and evaluation constitute five contributions:
Empirical Dataset. A continuous 157-day x402 settlement dataset across 16 blockchains (66.1M payments, $6.1M volume).
Graph Representation. A bipartite graph model of settled payments that derives personalized trust directly from transaction topology without requiring compelled ratings or protocol changes.
System Framework. Criteria evaluating schemes jointly by predictive accuracy for future provider selection and bounded economic attack cost.
Flow-Based Ratings. Three graph flow algorithms (, , and ) with formal proofs establishing explicit expenditure lower bounds for Sybil attackers.
Trace-Driven Evaluation. Empirical evaluation showing that predicts a buyer’s next provider first for 23.6% of buyers (vs. 3.7% for naive usage) while forcing a Sybil adversary
to spend 20% of target volume (vs. 0.9% for collaborative filtering).
The rest of the paper is organized as follows: § 2 surveys related work, § 3 provides background on agentic payments, § 4 formalizes rating schemes, § 5 presents our constructions, § 6 evaluates them empirically, and § 8 discusses implications.
Related Work
Agentic marketplaces are forums for autonomous buyers to engage unfamiliar providers. Navigating this environment requires evaluating service quality; however, every existing reputation mechanism imposes requirements that permissionless markets lack. We survey existing mechanisms by their properties, and the older family of graph-based reputation schemes which inform our design.
Curation. A curated registry of vetted providers (e.g., x402 Bazaar [5, 6]) offers Sybil resistance but scales poorly as service volume outpaces human auditability, creating dependence on a single authority’s judgment and capacity to approve new providers.
Identity Credentials. Proof-of-personhood primitives [4, 16] bound Sybils by certifying identity, rather than service quality. Moreover, human identity standards translate poorly to autonomous software agents [21, 27].
Per-Transaction Evaluation. Third-party evaluator escrows under EIP-8183 [8] provide quality checks but become prohibitively expensive for microtransactions, where evaluator fees and minimum thresholds (e.g., $1.00) dwarf typical $0.01 payments [13].
Optional Ratings. Registry standards like EIP-8004 [9] allow optional post-transaction ratings. However, active reporting is rare (< 4,000 ratings) [29], and optional feedback remains vulnerable to self-issued reviews.
Usage Ranking. Zero-overhead implemented approaches rank providers by transaction count, unique counterparties, or aggregate volume [6]. However, they offer no Sybil defense [11]: an adversary can loop funds internally to inflate rank at fee cost (§ 5.2), manipulating median scores for as little as $0.0027 [29].
Graph-Based Reputation and Max-Flow. Bazaar [23] proposed using max flow on traditional online markets to bound Sybil attacks. This mechanism classified a single proposed transaction as risky or safe by testing whether max-flow (across payment history) between buyer and seller exceeded the proposed transaction size. We want to discern between many new candidate providers, so flow values must discriminate among them rather than generate a binary safety classification. Unbounded flow allows many candidates to achieve the same maximum score, limiting the applicability of the mechanism as a rating. We therefore combine this max-flow approach with the literature consensus that localization can limit Sybils [2, 3, 22].
Summary Comparison. Table 1 evaluates existing reputation paradigms across the central requirements of permissionless agentic commerce. Existing Sybil-resistant designs rely on external infrastructure, while easily implementable approaches lack Sybil protection. Anduin bridges this gap by operating strictly over settled payment history while enforcing financial costs to manipulation.
Table 1. Comparison of reputation approaches for agentic marketplaces. ● offered, ◐ partially offered, ○ not offered.
Background
We formalize the notation and graph model used throughout the paper.
x402 Payment
x402 embeds payments within HTTP exchanges [7]: a server returns HTTP 402 Payment Required with pricing, and the buyer retries with a signed authorization header submitted onchain by a facilitator. Because settlement requires only a cryptographic signature rather than an interactive checkout, purchases occur autonomously without human intervention. Settlements occur in stablecoins (predominantly USDC) across EVM networks and Solana via designated facilitators or proxy contracts (for more details see Section A). x402 carries the vast majority of machine payment volume ($6.1M vs $270K for the second largest MPP [19, 26, 28]). Hence, we choose to evaluate our system on x402 data.
The Payment Graph
Let denote buyers and denote providers. The sets are disjoint, with any entity acting as both being modeled as two nodes. Settled payments thus define a weighted bipartite graph
where an edge exists if paid within look-back window . Because transactions flow strictly from to , the bipartite structure preserves payment direction, and we subsequently treat as an undirected edge set with edge weights reflecting volume over .
Neighborhood of a query. A rating is computed relative to querying buyer . We define three derived sets: known providers directly paid by ; co-users sharing at least one known provider; and candidate providers reachable via co-users that has not previously paid .
Definition 3.1 (Route). A route from buyer to a candidate provider is a 3-hop path such that and each associated weight triple is .
We confine our inference to this neighborhood; a candidate provider is reached exclusively via a co-user. Localizing trust to paths anchored at the buyer’s own payments allows us to bound an adversary’s influence. We do this by picking routes from , so may infer trust to a candidate provider if and only if it buys from the original buyer’s own known-provider. We use this payment to a known provider to bound our budget according to Theorem 5.1. Figure 1 illustrates the complete structural model.

Figure 1. The bipartite payment graph model. For querying buyer : are known providers, are co-users sharing known providers, and are candidate providers reachable through co-users. A 3-hop route ––– carries three edge weights. Unconnected nodes (, ) remain unrated.
Rating Schemes
This section defines a graph-based rating scheme, formalizes the adversary model, and establishes our evaluation criteria, utility and attack cost.
Graph-Based Rating Schemes
A rating is a system by which a buyer may discern between similar candidate providers. It is a method for a buyer to leverage existing information (i.e. the payment graph) to decide which provider to purchase from next. Formally:
Definition 4.1 (Rating Scheme). A rating scheme is an efficiently computable function:
where is the set of weighted bipartite payment graphs . Given graph , querying buyer , and candidate provider , the scheme outputs a non-negative score . The recommendation list presented to consists of candidates ordered by decreasing score, with ties broken at random. We write for the 1-indexed position of in this sorted list.
A rating scheme under Definition 4.1 must identify high-quality providers (utility) and make manipulation prohibitively expensive (attack cost). Neither metric is meaningful in isolation: a constant rating is tamper-proof but uninformative, while an accurate ranking that is trivially subverted is not useful in practice.
Threat Model
An adversary is a malicious entity controlling addresses that seeks to inflate the rating of a targeted provider . Operating strictly over the payment graph , the adversary’s sole attack mechanism is edge creation under two assumptions:
A₁: Permissionless entry. The adversary can create arbitrary buyer and provider identities (i.e., adding more elements to ) and transfer funds internally, each transaction costing base fee .
A₂: Uncompromised known providers. For honest buyer , the adversary controls no provider in .
Definition 4.2 (Cost of Edge Creation). For an adversary controlling address set , creating edge with weight where incurs cost:
where is the base onchain transaction and account generation fee.
As defined in Definition 4.2 and illustrated in Figure 2, value transferred between addresses within remains under adversarial control (except some fee ), whereas payments to external addresses are permanently forfeited. In microtransaction markets, base fees can be comparable to payment values, making security bounds functions of .

Figure 2. Cost of forging an edge by type under –. Internal edges within cost only network fee while payments to external providers cost full value and edges incident to honest buyer cannot be fabricated at any price.
Finally, we write when is reachable from via adversarial edge and identity additions in , and denote by the total cumulative cost under Definition 4.2.
Utility and Security Framework
Utility. Utility measures whether a scheme ranks the provider a buyer actually selects next higher than an unchosen alternative. For a naive random ranking, the expected pairwise ranking accuracy is , measuring global ranking across candidate providers . Our second metric, , evaluates a stricter condition: whether the true provider falls within the top recommendations. For evaluation, we fix a cutoff such that contains all payments settled strictly before , and payments after are held out. The ground truth is the first provider outside that buyer pays strictly after .
Definition 4.3 (Utility). Let denote the set of buyer–provider pairs where adopts a new provider . For a pair sampled from and a candidate provider drawn uniformly at random from , define utility:
,
.
or indicate that a rating provides no predictive utility regarding new provider .
Attack Cost. Attack cost measures the cost for an adversary to elevate a target provider to a given position in a buyer’s recommendation list. We formalize this as a minimum-cost optimization problem over adversary-constructable graphs.
Definition 4.4 (Attack Cost). For an adversary provider and a querying buyer , the adversary’s minimum cost to achieve rank or higher is:
Security against a Sybil attack in a permissionless marketplace takes the form of maximizing this attack cost.
Constructions
In this section, we describe Anduin’s edge weighting, evaluate three naive baselines that fail under simple Sybil manipulation at cost , and propose its three graph-based rating constructions.
Choosing the Edge Weight
Definition 5.1 (Edge Weight Function). Let be a reference timestamp and denote the set of settled payments from buyer to provider at or before , where each payment carries timestamp and value in USD. Let be a monotonically decreasing time-decay function. A weight function maps to a positive number .
Because the transaction record lacks explicit feedback ratings, buyer preference must be inferred behaviorally [14] via recency, frequency, and monetary volume [12]. We incorporate recency with decay , which we instantiate as a step function over the window ( if , and otherwise), leaving value and frequency as the primary weighting factors. We instantiate four weighting function variants alongside an operational variant inclusive of gas fees:
Monetary Weight (). evaluates decayed dollar volume. Inflating this weight requires expending capital at an uncompromised provider, establishing a direct financial attack cost.
Monetary Weight with Fees (). incorporates onchain settlement fee . Because is comparable to median microtransactions, acts as a volume-frequency hybrid. All empirical attack costs in Section 6 are denominated in to include this cost.
Damped Monetary Weight (). dampens heavy-tailed payment distributions, preventing a single high-value transaction from dominating payment graph edges.
Transaction Frequency (). counts payment occurrences irrespective of monetary magnitude. Notably, manipulating costs only transaction fee .
Baseline methods
We examine three intuitive baselines to motivate Anduin’s design. Each is a rating scheme under Definition 4.1, but can be subverted at a small cost.
Usage Ranking (). counts the number of distinct buyers who have paid . Under an adversary owning can execute self-directed payments at cost , inflating its rank without upper bound.
Co-User Count (). implements collaborative filtering [17], while counts co-user identities rather than payment volume. An adversary can generate Sybils, each making a micropayment to some to qualify as a co-user and another payment to to register the edge, capturing top rank for cost .
Co-User Volume (). weights paths by volume into candidate provider . However, because measures co-user payments into , an adversary can execute a small payment to some and a large self-payment to , outranking honest candidates for cost .
Maximum Flow Rating:
Baseline mechanisms fail because they infer based on features of the graph which an adversary can easily manipulate. To guarantee that Sybils cannot inject unearned trust, we constructed such that no candidate provider can receive more trust than the querying buyer b settled with its known providers. This system maps reputation to a maximum-flow problem over a localized query network.
Definition 5.2 (Query Network). For querying buyer and candidate provider , the query network is the directed flow network obtained by orienting every route as , with arc capacities , , and respectively.
Our first score computes maximum network flow over :
The capacity of each cut in bounds the maximum flow from to . By assumption , the adversary cannot alter arcs incident to , so the cut formed by arcs is immutable. Its total capacity therefore provides an adversary-resistant upper bound on (formally proven in Theorem 5.2. This rating, however, can limit differentiation. If multiple candidate providers have maximum flow of , they score equally and cannot be ranked.

Figure 3. The three counting rules, and what each costs an adversary. Following Figure 2: blue edges are honest payments, solid red edges are payments the adversary makes to an honest provider (costing full value), and dashed red edges are self-dealing between adversary-controlled addresses (costing only fees). All three rules fall for transaction fees alone, because none charges for the fabricated edges: usage counts any payment, counting co-users admits an identity on a payment of any size, and summing spend at reads edges the adversary pays to itself.
Summation Flow Rating: sum
While enforces strict security bounds, co-users share the same source arcs out of . Therefore, routing flow through one reduces the capacity available to others. In recommendation systems, however, multiple independent co-users choosing the same candidate suggests additional quality. implements this by allowing buyer capacity for each co-user.
The bridge capacity measures the aggregate two-hop capacity from to co-user through their shared known providers.
Considering a single co-user , the paths through shared known providers are parallel and merge at . Therefore, total flow is limited by the bridge capacity on one side and the arc on the other: . In the shared network , co-users compete for the same source arcs out of , so the combined flow is at most the sum of these per-co-user values. realizes this sum exactly by treating each co-user independently, yielding . Summing across co-users gives the rating:
Amplified Flow Rating: amp
Under , each co-user’s contribution to is capped at , so a co-user with high bridge capacity but small payments to cannot fully use its capacity. This underuse of information suggests a slightly suboptimal rating capability. As illustrated in Figure 4, pools this capacity across co-users who have transacted with candidate , allowing co-users with higher candidate provider payment volume to contribute more evidence.

Figure 4. Rating comparison on an example (, pays and $8 each, pays $1 each). shares , bottlenecking flow at ’s outgoing arc (). allocates private copies per co-user, summing independent flows (). pools copies across co-users paying , allowing to draw all available capacity ().
Let be a modified query network where the capacity of each arc is scaled to where . Define the amplified rating :
Computational Complexity
For , depends only on and not on the candidate provider, so it can be precomputed in time, yielding evaluation per candidate. In contrast, and run Dinic’s max-flow algorithm [10] once per candidate provider on the localized query network (not the global graph) which has nodes and arcs, so each candidate costs .
Security Guarantees
We establish two core security bounds governing adversarial manipulation across our three constructions.
Theorem 5.1 (Budget-Bounded Rating Cap). Let be a graph transformation where the adversary spends dollars in payments to external providers outside . Under assumptions and , for regardless of the number of Sybil identities created. This bound is tight.
Proof. Let denote the set of adversary-controlled addresses, with target provider . Under assumption , the querying buyer’s trusted provider set satisfies . Since is adversary-controlled and has not provided real service to honest buyers, no honest co-user has paid ; any such payment would reflect genuine service, not manipulation. Therefore, every route passes through and only adversarial co-users contribute flow toward .
Under Definition 4.2, each payment from an adversarial to an honest provider costs , permanently removing capital from . Let denote the adversary’s total payments from directly to honest known providers. Fees are excluded because they do not contribute to edge weight, so their inclusion would only increase true spend.
We consider each construction:
: In the query network , the boundary arcs form a cut separating from with total capacity:
By the Max-Flow Min-Cut Theorem, maximum flow is bounded by the capacity of any cut; since this cut has capacity , we have . (2) : By definition,
Honest co-users have never transacted with adversarial provider , so for all . Thus, only adversarial identities contribute:
Recall the bridge definition:
Summing across all :
(3) : In , arc capacities leaving are scaled by . However, the cut separating from consists of the boundary arcs for , whose capacities remain unscaled. Because these arcs form a cut separating from (similar to case above), max-flow cannot exceed their aggregate capacity . Hence .
To prove tightness, consider an adversary that instantiates Sybil buyers , each paying an honest provider an amount , and executing a self-directed payment . When , . The bridge capacity for each identity is . Summing across all identities yields , achieving the bound with equality. □
Theorem 5.2 (Spend-Bounded Cap). For any adversarially reachable graph , evaluated on is bounded by buyer ’s total historical spend on : for all .
Proof. The arcs form a cut in separating from any candidate provider , with total capacity:
By the Max-Flow Min-Cut Theorem, maximum flow is bounded by the capacity of any cut, so . Since settled transactions are immutably recorded on the public ledger, no adversary can alter or fabricate payments from , so is unchanged across all reachable graphs .
These theorems establish two structural cap categories. Theorem 5.1 gives an outlay-proportional cap for all three schemes: reputation inflation requires proportional real expenditure, so Sybil identities paying only base fees provide zero rating leverage. Theorem 5.2 gives a stricter buyer cap for , determined solely by ’s historical spend and unimpacted by adversarial budget.
Evaluation
We evaluate Anduin on real-world transactions across two dimensions: ranking accuracy (utility) and resilience against adversarial distortion (attack cost).
Anduin overview
Anduin takes the settlement ledger as input and produces a ranked candidate provider list for each querying buyer in four steps.
(1) Collecting Corpus. Following the criteria in Section A, we assemble onchain x402 stablecoin settlements (USDC/USDT) across 16 EVM networks and Solana over 157 days (March 23 to August 26, 2026), totaling 66.1M payments and $6.1M. Self-payments are removed.
(2) Snapshot and Population. We compute ratings over a 90-day look-back window ( days) ending June 21, 2026, 00:00 UTC. This window includes 24,429,942 distinct payments totaling $3.83M. We identify 136,646 buyers and 3,649 mature providers (paid by buyers). Our evaluation cohort comprises 813 buyers who subsequently adopt a previously uncontacted mature provider. These are the only buyers with a ground-truth label: of the 136,646, just 3,656 transact again in the following 30 days, and 813 of those first pay a mature provider they had never paid before.
(3) Candidate Generation. Candidate providers comprise all mature providers reachable via at least one co-user that the buyer has never paid. Across all buyers, lists average 381.4 candidate providers, with a median of 370 and a maximum of 747. Entering the top 25 requires outranking 93% of candidate providers.
(4) Measurement Framework. Utility is evaluated by checking whether each buyer’s actual next provider choice—the first new provider it pays in the 30 days after the cutoff—is ranked highly by the rating. Attack cost (§ 4.2) is measured by injecting a target provider into the snapshot; the attacker may then introduce arbitrarily many Sybil buyer identities that transact with the buyer’s known providers, building the graph needed to elevate ’s ranking. We solve for the minimum spend required for to achieve target rank , as illustrated in Figure 5.

Figure 5. Evaluation pipeline. From one snapshot of payments settled before we measure both properties. Utility (top): the scheme ranks the candidates , and we check where it places , the first new provider actually pays after . Attack cost (bottom): we inject target provider and arbitrarily many Sybil identities that pay into ’s known providers, rescore, and record the minimum spend that lifts to rank .
Utility
We evaluate ranking accuracy using pairwise discrimination (AUC) and top-1 precision (), as defined in Definition 4.3; results appear in Table 2. AUC measures the probability of ranking true next provider above an unchosen candidate provider . measures the fraction of buyers for whom the true choice achieves first rank.
| AUC | AUC | AUC | ||||
| dollars () | 0.747 | 4.8 | 0.859 | 19.4 | 0.859 | 22.5 | ||||||
| dollars + fee () | 0.758 | 4.8 | 0.871 | 20.0 | 0.869 | 22.8 | ||||||
| log dollars () | 0.749 | 5.2 | 0.861 | 20.4 | 0.862 | 23.6 |
| payments () | 0.761 | 5.4 | 0.878 | 21.9 | 0.877 | 23.5 |
| Baselines | AUC | |||||
| 0.807 | 3.7 | payments into | ||||
| 0.749 | 12.1 | co-user spend at | ||||
| 0.880 | 23.2 | co-users paying |
Table 2. Ranking utility across evaluated buyers under varying edge weights. Naive baselines do not vary by edge weight and are evaluated on the candidate provider set produced by the plain dollar weight.
Unlike the flow constructions, the baselines do not depend on edge weight functions—each assigns a score to a provider independently of the querying buyer, so they produce a single ranking independent of .
Transaction counting () achieves the strongest AUC among flow constructions ( 0.878, 0.877, 0.761), approaching the collaborative filtering baseline (0.880). All constructions exceed the random baseline (AUC = 0.5). Plain dollars () perform worst because most edges are dominated by a single transaction’s value: 51.1% of buyer–provider pairs share only one payment, and on 59.3% of all edges one payment accounts for more than 90% of total edge weight, so the weight reflects that transaction’s size rather than relationship strength.
achieves the highest top-1 precision—23.6% under —exceeding all baselines. is an outlier: despite AUC , its never exceeds 5.4%, as its minimum cut bottlenecks on the buyer’s outgoing arcs and produces multi-candidate ties for 78.0% of buyers.
Impact of Look-Back Window (). We evaluate look-back days on the same set of buyers for . Extending monotonically increases AUC from 0.829 at 15 days to 0.869 at 90 days. peaks at 30 days (24.7%) before candidate provider set expansion (304 381) increases rank competition too much. A 30-to-90 day window balances coverage and top-1 precision (more detail in Section 6.4.1).
Attack Cost
We evaluate economic attack resilience using fee-inclusive dollar weights (). We set base fee , the average per-transaction settlement fee across the chains settling x402 (however, the results are insensitive to the specific value). Costs are reported in two forms: absolute USD and as a fraction of the total spend of all 813 buyers combined ($41,331), so that attack costs can be read relative to the economic scale of the market being targeted.
Co-user spend () costs only a single fee ($0.017) via circular self-payments. Usage ranking () is expensive at rank 1 ($217,539) due to requiring 12.8M fees, but falls drastically at subsequent ranks: top-5 ($7,350), top-10 ($848), and top-25 ($310). Collaborative filtering () is 23× cheaper to subvert than ($358 vs. $8,259 for top-1 market capture). The flow constructions maintain meaningful costs across all target ranks. At the loosest threshold examined (top-25), an attacker must still spend between $494 () and $898 () to reach all buyers, against just $50 under . This gap narrows as increases but does not disappear.
Targeted Manipulation. The preceding analysis prices capturing every buyer simultaneously, but an adversary may instead target only the most valuable ones. Subverting the single largest buyer costs $291 under any construction (2.3% of that buyer’s spend). Extending to the top decile (79 buyers holding 91% of aggregate spend) costs only $53 under , significantly less than Anđuin constructions, which require $3,183 (\Pi_{\mathrm{flow}}), and $5,490 ($\Pi_{\mathrm{amp}}). Further detail appears in Section 6.4.2 (Table 5).
| top | target spend | ||||
| 1 | $12,612 | $1.86 | $289 | $289 | $291 | ||
| 10 | $22,981 | $14 | $2,508 | $1,716 | $4,138 | ||
| 79 | $37,566 | $53 | $4,096 | $3,183 | $5,490 | ||
| 813 | $41,331 | $358 | $4,673 | $4,330 | $8,259 |
Table 5. Targeted attack cost on top- buyers ranked by spend (rank 1, fee-inclusive dollar weight , ).
Overall. Evaluating utility and attack cost jointly (Figure 6) establishes as best construction: baselines either collapse under cheap manipulation () or yield poor predictive accuracy (), whereas achieves high precision () while enforcing an attack cost equal to 20% of target buyer spend, both under

Figure 6. Utility versus manipulation cost. Horizontal: ranking accuracy (). Vertical: cost to capture rank 1 for all 813 buyers, as a fraction of their combined spend, under . Positions are ordinal, not to scale; exact values are in Tables 2 and 3. Only and are both accurate and expensive to subvert. matches their accuracy but costs $358 to subvert, and is expensive only because it ranks poorly ().
; with , it is the only scheme in the figure’s accurate-and-costly quadrant.
Extended Empirical Analyses {#sec:6.4}
Look-Back () Sensitivity {#sec:6.4.1}
We evaluate the impact of historical look-back duration days on candidate provider reachability and predictive precision using the same 813 buyers evaluated in § 6, held fixed across all window sizes so that differences reflect only the rating’s look-back, not cohort composition. Table 4 summarizes performance metrics across window sizes under fee-inclusive dollar weighting ().
Candidates is the mean number of providers on each buyer’s candidate list ; it grows with as more co-users become visible and open new reachable providers. Coverage is the fraction of buyers for whom the true next provider appears anywhere in ; if it is absent, no rating can rank it first. | reachable conditions only on buyers whose true provider was reachable, separating ranking quality from candidate generation quality. Extending monotonically increases both coverage (from 70.5% at 15 days to 90.7% at 90 days) and ranking separation (AUC reaches 0.869). However, peaks at days (24.7% overall, 29.6% conditional on reachability): while longer windows capture richer history, they also expand candidate provider lists (304 at 30 days vs. 381 at 90 days), increasing competition at rank 1. In practice, a look-back of 30 to 90 days balances coverage against top-1 precision.
| (days) | candidates | coverage | AUC | | reachable | |
| 15 | 261 | 70.5% | 0.829 | 12.9 | 18.3 |
| 30 | 304 | 83.4% | 0.860 | 24.7 | 29.6 |
| 45 | 337 | 87.2% | 0.860 | 21.2 | 24.3 |
| 60 | 356 | 88.4% | 0.863 | 21.5 | 24.3 |
| 75 | 368 | 89.7% | 0.868 | 23.0 | 25.7 |
| 90 | 381 | 90.7% | 0.869 | 22.8 | 25.1 |
Table 4. Look-back window vs. utility on the fixed 813-buyer cohort under fee-inclusive dollar weighting (). Candidates: mean length of candidate list . Coverage: fraction of buyers whose true next provider appears somewhere in ; buyers outside coverage always count as misses. | reachable: top-1 precision conditioned on the true provider being reachable, isolating ranking quality from candidate generation quality.
Targeted Attack Cost
In addition to systemic market-wide attacks (Table 3), we evaluate the expenditure required to capture top rank for specific sub-cohorts of high-value buyers. Table 5 breaks down the minimum attack cost to achieve rank 1 when targeting the top- highest-spending buyers (ranked by 90-day transaction volume).
| top 1 | top 5 | top 10 | top 25 | |||||
| frac. | cost | frac. | cost | frac. | cost | frac. | cost | |
| Baselines | ||||||||
| 5.263 | $217,539 | 0.178 | $7,350 | 0.021 | $848 | 0.008 | $310 | |||||
| 0.000 | $0.02 | 0.000 | $0.02 | 0.000 | $0.02 | 0.000 | $0.02 | |||||
| 0.009 | $358 | 0.003 | $138 | 0.002 | $100 | 0.001 | $50 | |||||
| Anđuin Constructions | ||||||||
| 0.113 | $4,673 | 0.059 | $2,420 | 0.041 | $1,701 | 0.022 | $898 | |||||
| 0.105 | $4,330 | 0.034 | $1,420 | 0.023 | $961 | 0.012 | $494 | |||||
| 0.200 | $8,259 | 0.040 | $1,661 | 0.028 | $1,145 | 0.013 | $554 |
Table 3. Minimum cost to capture top- rank across all buyers, reported in USD and as a fraction of combined spend of the 813 tested buyers ($41,331). scores providers globally.
allow our payment graph to decompose multi-agent wallets into distinct vertices, aligning our graph representation with underlying agent intent.
Under collaborative filtering (), an adversary can capture the single highest-spending buyer for $1.86 and the entire top decile (, representing 91% of total market volume) for just $53. In contrast, flow-based constructions enforce substantial capital requirements. Subverting the top decile under requires $5,490 (14.6% of spend), $4,096 under , and $3,183 under . This confirms that flow-based ratings effectively price systemic market capture rather than single-buyer preferences.
6.4.3 Alternative Edge Weighting: Calendar Days (). An alternative edge weight deferred from Section 5.1 counts distinct calendar days with settled transactions: . In machine-to-machine commerce where an automated agent can execute hundreds of micro-transactions within seconds, counting distinct return days filters single-day payment bursts and captures sustained counterparty relationships.
Empirically, yields the highest ranking utility across all evaluated metrics, lifting to AUC = 0.881 and = 25.5% (compared to 0.869 and 22.8% under ), and lifting by a comparable margin.
However, we omit from our primary attack cost benchmarking because temporal delay cannot be directly priced in financial terms. Forging a unit of requires burning a transaction fee and waiting a calendar day. While time imposes a genuine physical constraint on adversaries, expressing attack costs as a fraction of calendar days creates an incommensurable comparison against dollar-denominated bounds.
Discussion
This section details considerations, limitations, and design extensions for graph-based agentic reputation.
Cold-Start Dynamics. A buyer without prior transaction history has no known providers , co-users , or reachable candidate providers . In this initial state, graph ratings are undefined across all providers, much like in collaborative filtering [25]. In agentic marketplaces, new buyers may initially bootstrap via curated allow-lists [5, 6]. Our graph framework improves naturally as transaction history accumulates: even a single settled payment populates and establishes a personalized recommendation. Similarly, newly listed providers remain unrated until adopted by at least one co-user.
Multi-Agent Wallets. When a single onchain address acts as a shared treasury for multiple distinct AI agents or providers, their transaction histories are conflated. This pools unrelated co-users and buyers, introducing noise to our recommendation. Adopting per-agent sub-account keys or signing metadata (e.g., ERC-4337 session keys or BIP-32 wallet key derivation conventions) would allow our payment graph to decompose multi-agent wallets into distinct vertices, aligning our graph representation with underlying agent intent.
Conclusion
This paper demonstrates that historically settled onchain payments can be harnessed to rank service providers in autonomous agentic markets without protocol modifications, external credentials, or manual curation. Using a 157-day continuous settlement dataset of 66.1M payments from the x402 marketplace, we modeled transactions as a bipartite payment graph and formalized the dual criteria of predictive accuracy (utility) and bounded expenditure (attack cost).
Anduin comprises three rating constructions derived from this graph model: which enforces strict rating ceilings on the buyer’s historical spend, which replicates capacity per co-user to improve rating efficacy and which pools capacity across co-users aligned on candidate transactions. Together, they demonstrate that localized graph flow can replace ad-hoc reputation heuristics while enforcing a market-scaled economic cost on Sybil manipulation.
Identification of x402 Settlements
We identify x402 settlements on EVM networks and Solana using a combination of event logs, transaction structure, and known facilitator and seller addresses.
EVM Settlements
We use the following rules to identify x402 transactions involving ERC-20 transfers of USDC and USDT:
| Settlement method | Event logs | Top-level transaction to address |
| EIP-3009 direct | AuthorizationUsed and Transfer | Token contract. |
| Permit2 Exact | Settled or SettledWithPermit, and Transfer | Permit2 Exact proxy: 0x402085c248eea27d92e8b30b2c58ed07f9e20001. |
| Permit2 Upto | Settled or SettledWithPermit, and Transfer | Permit2 Upto proxy: 0x4020a4f3b7b90ccca423b9fabc0ce57c62400002. |
| Multicall | A settlement event listed above and Transfer | Neither the token contract nor either Permit2 proxy; a residual category for routers, batchers, and other intermediaries. |
Table A.1.
Permit2 Exact and Upto emit the same settlement events and are distinguished by their x402-specific proxy addresses. These addresses provide sufficient evidence of x402 settlement without further facilitator or seller validation. By contrast, AuthorizationUsed is a generic EIP-3009 event. Direct EIP-3009 and Multicall candidates are therefore retained only when the top-level transaction from address is a known facilitator or the transfer recipient is a known x402 seller. Each qualifying Transfer log produces one record containing the buyer, seller, and amount, with the top-level transaction from address identifying the facilitator.
Solana Settlements
On Solana, we identify outgoing stablecoin transfers in which the fee payer differs from the transfer’s source authority. A transfer is retained when either the fee payer is a known facilitator or the destination is a known x402 seller.
Facilitator and Seller Sources
The initial list of known facilitator addresses is drawn from two public Dune dashboards and their underlying queries: x402 Analytics2, published by Hashed, and x402 Facilitators3, published by Dune. On EVM networks, the list is supplemented with addresses observed submitting settlements through the x402 Permit2 proxies. Known sellers are sourced from Coinbase’s public x402 discovery registry4, which publishes the payment addresses accepted by registered resources on each network.
Limitations
EIP-3009, Multicall, and Solana transactions involving both an unknown facilitator and an unregistered seller are not captured.
References
- [1]Lorenzo Alvisi, Allen Clement, Alessandro Epasto, Silvio Lattanzi, and Alessandro Panconesi. 2013. SoK: The Evolution of Sybil Defense via Social Networks. In 2013 IEEE Symposium on Security and Privacy (S&P). IEEE Computer Society, 382–396. doi:10.1109/SP.2013.33
- [2]Qiang Cao, Michael Sirivianos, Xiaowei Yang, and Tiago Pregueiro. 2012. Aiding the Detection of Fake Accounts in Large Scale Social Online Services. In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI). USENIX Association.
- [3]Alice Cheng and Eric Friedman. 2005. Sybilproof Reputation Mechanisms. In Proceedings of the 2005 ACM SIGCOMM Workshop on Economics of Peer-to-Peer Systems (P2PECON). Philadelphia, PA, USA. doi:10.1145/1080192.1080202DOI
- [4]Arka Rai Choudhuri, Sanjam Garg, Keewoo Lee, Hart Montgomery, Guru Vamsi Policharla, and Rohit Sinha. 2026. A Cryptographic Framework for Proof of Personhood. Cryptology ePrint Archive, Paper 2026/333. https://eprint.iacr.org/2026/333
- [5]Circle. 2026. Introducing Circle Agent Stack: Financial Infrastructure for the Agentic Economy. Online. https://agents.circle.com
- [6]Coinbase and CDP. 2026. x402 Bazaar: discovery layer for payable HTTP APIs (docs). Online; docs. https://docs.cdp.coinbase.com/x402/bazaar
- [7]Coinbase and x402 Foundation. 2025. x402: HTTP-native payment protocol (homepage, foundation README, v2 spec). Online; website. https://www.x402.org/
- [8]Davide Crapis, Bryan Lim, Tay Weixiong, and Chooi Zuhwa. 2026. ERC-8183: Agentic Commerce. Ethereum Improvement Proposals (ERC-8183). https://eips.ethereum.org/EIPS/eip-8183
- [9]Marco De Rossi, Davide Crapis, Jordan Ellis, and Erik Reppel. 2025. ERC-8004: Trustless Agents. Ethereum Improvement Proposals (ERC-8004). https://eips.ethereum.org/EIPS/eip-8004
- [10]E. A. Dinic. 1970. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Mathematics Doklady 11 (1970), 1277–1280.
- [11]John R. Douceur. 2002. The Sybil Attack. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS 2002). https://www.freehaven.net/anonbib/cache/sybil.pdfDOI
- [12]Peter S. Fader, Bruce G. S. Hardie, and Ka Lok Lee. 2005. RFM and CLV: Using Iso-Value Curves for Customer Base Analysis. Journal of Marketing Research 42, 4 (2005), 415–430.
- [13]Fellowship of Ethereum Magicians. 2026. ERC-8183: Agentic Commerce – Community Discussion Thread. Online forum thread. https://ethereum-magicians.org/t/erc-8183-agentic-commerce/27902
- [14]Yifan Hu, Yehuda Koren, and Chris Volinsky. 2008. Collaborative Filtering for Implicit Feedback Datasets. In IEEE International Conference on Data Mining (ICDM). 263–272.DOI
- [15]Gordon Liao, Ziming Zeng, Mira Belenkiy, and Jacob Hirshman. 2025. Transaction Proximity: A Graph-Based Approach to Blockchain Fraud Prevention. arXiv:2505.24284 https://arxiv.org/abs/2505.24284
- [16]Zibin Lin, Shengli Zhang, Guofu Liao, Dacheng Tao, and Taotao Wang. 2025. Binding Agent ID: Unleashing the Power of AI Agents with Accountability and Credibility. arXiv:2512.17538. https://arxiv.org/abs/2512.17538
- [17]Greg Linden, Brent Smith, and Jeremy York. 2003. Amazon.com Recommendations: Item-to-Item Collaborative Filtering. IEEE Internet Computing 7, 1 (2003), 76–80. doi:10.1109/MIC.2003.1167344
- [18]Shengchen Ling, Yajin Zhou, Lei Wu, and Cong Wang. 2026. How Agentic Is Agentic Commerce? A Population-Scale Measurement of x402 Adoption and Authenticity. arXiv:2607.12575. https://arxiv.org/abs/2607.12575
- [19]MPPSCan. 2026. MPPSCan: The Machine Payments Protocol Explorer. Live dashboard, https://mppscan.com/?d=0. Accessed 22 June 2026.
- [20]Chris Nosko and Steven Tadelis. 2015. The Limits of Reputation in Platform Markets: An Empirical Analysis and Field Experiment. NBER Working Paper 20830. National Bureau of Economic Research. https://www.nber.org/papers/w20830
- [21]Takumi Otsuka, Kentaro Toyoda, and Alex Leung. 2026. AI Identity: Standards, Gaps, and Research Directions for AI Agents. arXiv:2604.23280. https://arxiv.org/abs/2604.23280
- [22]Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report 1999-66. Stanford InfoLab.
- [23]Ansley Post, Vijit Shah, and Alan Mislove. 2011. Bazaar: Strengthening User Reputations in Online Marketplaces. In Proceedings of the 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’11). USENIX Association, Boston, MA.DOI
- [24]Paul Resnick and Richard Zeckhauser. 2002. Trust Among Strangers in Internet Transactions: Empirical Analysis of eBay’s Reputation System. The Economics of the Internet and E-Commerce (Advances in Applied Microeconomics, vol. 11) (2002), 127–157.
- [25]Imo Schein, Alexandrin Popescul, Lyle H. Ungar, and David M. Pennock. 2002. Methods and metrics for cold-start recommendations. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’02). ACM, 253–260.
- [26]Tempo and Stripe. 2026. Machine Payments Protocol (MPP): spec, docs, and IETF Payment HTTP auth scheme. Online; spec. https://mpp.dev
- [27]World (Worldcoin). 2023. World Whitepapers. Online. https://whitepaper.world.org/ Whitepaper series; updated March 2026.
- [28]x402scan. 2026. x402scan: x402Scan: x402scan Explorer. Live dashboard, https://www.x402scan.com/ Accessed July 2026.
- [29]Xihan Xiong, Zelin Li, Wei Wei, Qin Wang, William Knottenbelt, and Zhipeng Wang. 2026. Can Trustless Agents Be Trusted? An Empirical Study of the ERC-8004 Decentralized AI Agent Ecosystem. arXiv:2606.26028. https://arxiv.org/abs/2606.26028
- [30]Yuanzhe Zhang, Yuexin Xiang, Yuchen Lei, Qin Wang, Tian Qiu, Yujing Sun, Spiridon Zarkov, Tsz Hon Yuen, Andreas Deppeler, Jiangshan Yu, and Kwok-Yan Lam. 2026. SoK: Blockchain Agent-to-Agent Payments. arXiv:2604.03733 https://arxiv.org/abs/2604.03733