betaFeedback

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:

  1. Empirical Dataset. A continuous 157-day x402 settlement dataset across 16 blockchains (66.1M payments, $6.1M volume).

  1. Graph Representation. A bipartite graph model of settled payments that derives personalized trust directly from transaction topology without requiring compelled ratings or protocol changes.

  1. System Framework. Criteria evaluating schemes jointly by predictive accuracy for future provider selection and bounded economic attack cost.

  1. Flow-Based Ratings. Three graph flow algorithms (Πflow\Pi_{\mathrm{flow}}, Πsum\Pi_{\mathrm{sum}}, and Πamp\Pi_{\mathrm{amp}}) with formal proofs establishing explicit expenditure lower bounds for Sybil attackers.

  1. Trace-Driven Evaluation. Empirical evaluation showing that Πamp\Pi_{\mathrm{amp}} 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.

ApproachNo New InfrastructureQuality SignalSybil-ResistantScales Without Human Effort
Curation [5, 6]◐ (reviewers)●●○
Credentials [4, 16]○ (issuer)○●●
Evaluation [8]◐ (evaluators)●●◐ (fee > payment)
Optional Ratings [9]●◐ (sparse)○●
Usage Ranking [6]●◐ (popularity)○●
Anduin●●●●

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 ≈\approx $270K for the second largest MPP [19, 26, 28]). Hence, we choose to evaluate our system on x402 data.

The Payment Graph

Let B={b1,b2,…}B = \{b_1, b_2, \ldots\} denote buyers and P={p1,p2,…}P = \{p_1, p_2, \ldots\} 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

G=(B∪P,E,w),E⊆B×PG = (B \cup P, E, w), \qquad E \subseteq B \times P

where an edge exists if bb paid pp within look-back window τ\tau. Because transactions flow strictly from BB to PP, the bipartite structure preserves payment direction, and we subsequently treat EE as an undirected edge set with edge weights w(b,p)w(b,p) reflecting volume over τ\tau.

Neighborhood of a query. A rating is computed relative to querying buyer b∈Bb \in B. We define three derived sets: known providers K(b)={p∈P∣(b,p)∈E}K(b) = \{p \in P \mid(b,p) \in E\} directly paid by bb; co-users C(b)={b′∈B∖{b}∣∃p∈K(b),(b′,p)∈E}C(b) = \{b' \in B \setminus\{b\} \mid\exists p \in K(b), (b',p) \in E\} sharing at least one known provider; and candidate providers Q(b)={p′∈P∣∃b′∈C(b),(b′,p′)∈E}Q(b) = \{p' \in P \mid\exists b' \in C(b), (b',p') \in E\} reachable via co-users that bb has not previously paid (Q(b)∩K(b)=∅)(Q(b) \cap K(b) = \varnothing).

Definition 3.1 (Route). A route from buyer bb to a candidate provider p′∈Q(b)p' \in Q(b) is a 3-hop path b−p−b′−p′b - p - b' - p' such that p∈K(b)p \in K(b) and each associated weight triple is (w(b,p),w(b′,p),w(b′,p′))(w(b,p), w(b',p), w(b',p')).

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 K(b)K(b), so bb 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.

The bipartite payment graph model

Figure 1. The bipartite payment graph model. For querying buyer bb: K(b)K(b) are known providers, C(b)C(b) are co-users sharing known providers, and Q(b)Q(b) are candidate providers reachable through co-users. A 3-hop route bb–pp–b′b'–p′p' carries three edge weights. Unconnected nodes (b′′b'', p′′p'') 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:

Π:G×B×P⟶R≥0,\Pi: G \times B \times P \longrightarrow\mathbb{R}_{\ge0},

where GG is the set of weighted bipartite payment graphs G=(B∪P,E,w)G=(B\cup P,E,w). Given graph GG, querying buyer bb, and candidate provider p′p', the scheme outputs a non-negative score ΠG(b,p′)\Pi_G(b,p'). The recommendation list presented to bb consists of candidates Q(b)Q(b) ordered by decreasing score, with ties broken at random. We write rank⁡Π(b,p′)\operatorname{rank}_{\Pi}(b,p') for the 1-indexed position of p′p' 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 A⊆B∪PA\subseteq B\cup P that seeks to inflate the rating of a targeted provider p∗∈Ap^*\in A. Operating strictly over the payment graph (E,w)(E,w), 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 AA) and transfer funds internally, each transaction costing base fee ϵ\epsilon.

A₂: Uncompromised known providers. For honest buyer bb, the adversary controls no provider in K(b)K(b).

Definition 4.2 (Cost of Edge Creation). For an adversary controlling address set AA, creating edge (b,p)(b,p) with weight ww where b∈Ab\in A incurs cost:

cost⁡(b,p,w)={ϵif p∈A,w+ϵif p∉A.\operatorname{cost}(b,p,w)= \begin{cases} \epsilon& \text{if }p\in A,\\ w+\epsilon& \text{if }p\notin A. \end{cases}

where ϵ\epsilon 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 AA remains under adversarial control (except some fee ϵ\epsilon), whereas payments to external addresses are permanently forfeited. In microtransaction markets, base fees ϵ\epsilon can be comparable to payment values, making security bounds functions of ϵ\epsilon.

Cost of forging an edge by type under $A_1$–$A_2$

Figure 2. Cost of forging an edge by type under A1A_1–A2A_2. Internal edges within AA cost only network fee ϵ\epsilon while payments to external providers cost full value w+ϵw+\epsilon and edges incident to honest buyer bb cannot be fabricated at any price.

Finally, we write G⇝G′G\leadsto G' when G′G' is reachable from GG via adversarial edge and identity additions in AA, and denote by χ(G,G′)\chi(G,G') 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 12\frac{1}{2}, measuring global ranking across candidate providers Q(b)Q(b). Our second metric, P@kP@k, evaluates a stricter condition: whether the true provider falls within the top kk recommendations. For evaluation, we fix a cutoff TT such that GG contains all payments settled strictly before TT, and payments after TT are held out. The ground truth p+p^{+} is the first provider outside K(b)K(b) that buyer bb pays strictly after TT.

Definition 4.3 (Utility). Let R={(b1,p1+),(b2,p2+),…}R = \{(b_1,p_1^{+}), (b_2,p_2^{+}), \ldots\} denote the set of buyer–provider pairs where bb adopts a new provider p+∉K(b)p^{+} \notin K(b). For a pair (b,p+)(b,p^{+}) sampled from RR and a candidate provider qq drawn uniformly at random from Q(b)∖{p+}Q(b) \setminus\{p^{+}\}, define utility:

AUC:=Pr⁡[ΠG(b,p+)>ΠG(b,q)]+12Pr⁡[ΠG(b,p+)=ΠG(b,q)]\mathrm{AUC} := \Pr[\Pi_G(b,p^{+}) > \Pi_G(b,q)] + \frac{1}{2}\Pr[\Pi_G(b,p^{+}) = \Pi_G(b,q)],

P@k:=Pr⁡[rank⁡Π(b,p+)≤k]P@k := \Pr[\operatorname{rank}_{\Pi}(b,p^{+}) \leq k].

AUC=12\mathrm{AUC} = \frac{1}{2} or P@k≈0P@k \approx0 indicate that a rating provides no predictive utility regarding new provider p+p^{+}.

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 p∗p^{*} and a querying buyer bb, the adversary’s minimum cost to achieve rank kk or higher is:

min⁡{χ(G,G′):G⇝G′, rank⁡ΠG′(b,p∗)≤k}\min\left\{ \chi(G,G') : G \rightsquigarrow G',\ \operatorname{rank}_{\Pi_{G'}}(b,p^{*}) \leq k \right\}

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 ϵ\epsilon, and propose its three graph-based rating constructions.

Choosing the Edge Weight

Definition 5.1 (Edge Weight Function). Let TT be a reference timestamp and P(b,p)={(t1,v1),(t2,v2),…}\mathcal{P}(b,p) = \{(t_1,v_1), (t_2,v_2), \ldots\} denote the set of settled payments from buyer bb to provider pp at or before TT, where each payment carries timestamp tit_i and value viv_i in USD. Let δ:R+→(0,1]\delta: \mathbb{R}^{+} \to(0,1] be a monotonically decreasing time-decay function. A weight function maps P(b,p)\mathcal{P}(b,p) to a positive number w(b,p)∈R+w(b,p) \in\mathbb{R}^{+}.

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 δ\delta, which we instantiate as a step function over the window τ\tau (δ(T−ti)=1\delta(T-t_i)=1 if T−ti≤τT-t_i \leq\tau, and 00 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 (w$w_{\$}). w$(b,p)=∑iδ(T−ti)viw_{\$}(b,p)=\sum_i \delta(T-t_i)v_i evaluates decayed dollar volume. Inflating this weight requires expending capital at an uncompromised provider, establishing a direct financial attack cost.

Monetary Weight with Fees (w$ϵw_{\$\epsilon}). w$ϵ(b,p)=∑iδ(T−ti)(vi+ϵ)w_{\$\epsilon}(b,p)=\sum_i \delta(T-t_i)(v_i+\epsilon) incorporates onchain settlement fee ϵ\epsilon. Because ϵ\epsilon is comparable to median microtransactions, w$ϵw_{\$\epsilon} acts as a volume-frequency hybrid. All empirical attack costs in Section 6 are denominated in w$ϵw_{\$\epsilon} to include this cost.

Damped Monetary Weight (wlog⁡w_{\log}). wlog⁡(b,p)=log⁡(1+∑ivi)w_{\log}(b,p)=\log(1+\sum_i v_i) dampens heavy-tailed payment distributions, preventing a single high-value transaction from dominating payment graph edges.

Transaction Frequency (w#w_{\#}). w#(b,p)=∑iδ(T−ti)w_{\#}(b,p)=\sum_i \delta(T-t_i) counts payment occurrences irrespective of monetary magnitude. Notably, manipulating w#w_{\#} costs only transaction fee ϵ\epsilon.

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 (Πuse\Pi_{\mathrm{use}}). Πuse(b,p′)=∣{b′′∈B∣(b′′,p′)∈E}∣\Pi_{\mathrm{use}}(b,p')=|\{b''\in B\mid(b'',p')\in E\}| counts the number of distinct buyers who have paid p′p'. Under Πuse\Pi_{\mathrm{use}} an adversary owning p′p' can execute nn self-directed payments at cost nϵn\epsilon, inflating its rank without upper bound.

Co-User Count (Πcf\Pi_{\mathrm{cf}}). Πcf(b,p′)=∣{b′∈C(b)∣(b′,p′)∈E}∣\Pi_{\mathrm{cf}}(b,p')=|\{b'\in C(b)\mid(b',p')\in E\}| implements collaborative filtering [17], while Πcf\Pi_{\mathrm{cf}} counts co-user identities rather than payment volume. An adversary can generate nn Sybils, each making a micropayment to some p∈K(b)p\in K(b) to qualify as a co-user and another payment to p′p' to register the edge, capturing top rank for cost 2nϵ2n\epsilon.

Co-User Volume (Πspend\Pi_{\mathrm{spend}}). Πspend(b,p′)=∑b′∈C(b)w(b′,p′)\Pi_{\mathrm{spend}}(b,p')=\sum_{b'\in C(b)}w(b',p') weights paths by volume into candidate provider p′p'. However, because w(b′,p′)w(b',p') measures co-user payments into p′p', an adversary can execute a small payment to some p∈K(b)p\in K(b) and a large self-payment to p′p', outranking honest candidates for cost 2ϵ2\epsilon.

Maximum Flow Rating: Πflow\Pi_{\mathrm{flow}}

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 Πflow\Pi_{\mathrm{flow}} 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 bb and candidate provider p′∈Q(b)p'\in Q(b), the query network N(b,p′)N(b,p') is the directed flow network obtained by orienting every route b→p→b′→p′b\to p\to b'\to p' as b→p→b′→p′b\to p\to b'\to p', with arc capacities w(b,p)w(b,p), w(b′,p)w(b',p), and w(b′,p′)w(b',p') respectively.

Our first score Πflow\Pi_{\mathrm{flow}} computes maximum network flow over N(b,p′)N(b,p'):

Πflow(b,p′):=maxflow⁡(N(b,p′),b→p′)(1)\Pi_{\mathrm{flow}}(b,p') := \operatorname{maxflow}(N(b,p'),b\to p') \tag*{(1)}

The capacity of each cut in N(b,p′)N(b,p') bounds the maximum flow from bb to p′p'. By assumption A2A_2, the adversary cannot alter arcs incident to bb, so the cut formed by arcs {b→p∣p∈K(b)}\{b\to p\mid p\in K(b)\} is immutable. Its total capacity β(G,b)=∑p∈K(b)w(b,p)\beta(G,b)=\sum_{p\in K(b)}w(b,p) therefore provides an adversary-resistant upper bound on Πflow(b,p′)\Pi_{\mathrm{flow}}(b,p') (formally proven in Theorem 5.2. This rating, however, can limit differentiation. If multiple candidate providers have maximum flow of β(G,b)\beta(G,b), they score equally and cannot be ranked.

Three counting rules and adversarial costs

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 p′p' reads edges the adversary pays to itself.

Summation Flow Rating: sum

While Πflow\Pi_{\mathrm{flow}} enforces strict security bounds, co-users share the same source arcs out of bb. 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. Πsum\Pi_{\mathrm{sum}} implements this by allowing buyer capacity for each co-user.

The bridge capacity bridge⁡(b,b′)=∑p∈K(b)min⁡(w(b,p),w(b′,p))\operatorname{bridge}(b,b') = \sum_{p \in K(b)} \min(w(b,p),w(b',p)) measures the aggregate two-hop capacity from bb to co-user b′b' through their shared known providers.

Considering a single co-user b′b', the paths through shared known providers are parallel and merge at b′b'. Therefore, total flow is limited by the bridge capacity on one side and the arc b′→p′b' \to p' on the other: min⁡(bridge⁡(b,b′),w(b′,p′))\min(\operatorname{bridge}(b,b'),w(b',p')). In the shared network N(b,p′)N(b,p'), co-users compete for the same source arcs out of bb, so the combined flow is at most the sum of these per-co-user values. Πsum\Pi_{\mathrm{sum}} realizes this sum exactly by treating each co-user independently, yielding Πsum(b,p′)≥Πflow(b,p′)\Pi_{\mathrm{sum}}(b,p') \ge\Pi_{\mathrm{flow}}(b,p'). Summing across co-users gives the Πsum\Pi_{\mathrm{sum}} rating:

Πsum(b,p′):=∑b′∈C(b)min⁡(bridge⁡(b,b′),w(b′,p′))(2)\Pi_{\mathrm{sum}}(b,p') := \sum_{b' \in C(b)} \min\left(\operatorname{bridge}(b,b'), w(b',p')\right) \tag*{(2)}

Amplified Flow Rating: amp

Under Πsum\Pi_{\mathrm{sum}}, each co-user’s contribution to p′p' is capped at w(b′,p′)w(b',p'), so a co-user with high bridge capacity but small payments to p′p' cannot fully use its capacity. This underuse of information suggests a slightly suboptimal rating capability. As illustrated in Figure 4, Πamp\Pi_{\mathrm{amp}} pools this capacity across co-users who have transacted with candidate p′p', allowing co-users with higher candidate provider payment volume to contribute more evidence.

Rating comparison on an example

Figure 4. Rating comparison on an example (w(b,p)=4w(b,p)=4, b1′b'_1 pays pp and p′p' $8 each, b2′b'_2 pays $1 each). Πflow\Pi_{\mathrm{flow}} shares w(b,p)w(b,p), bottlenecking flow at bb’s outgoing arc (Πflow=4\Pi_{\mathrm{flow}}=4). Πsum\Pi_{\mathrm{sum}} allocates private copies per co-user, summing independent flows (Πsum=4+1=5\Pi_{\mathrm{sum}}=4+1=5). Πamp\Pi_{\mathrm{amp}} pools np=2n_p=2 copies across co-users paying p′p', allowing b1′b'_1 to draw all available capacity (Πamp=8\Pi_{\mathrm{amp}}=8).

Let Na(b,p′)N_a(b,p') be a modified query network where the capacity of each arc b→pb \to p is scaled to np⋅w(b,p)n_p \cdot w(b,p) where np=∣{b′∈C(b)∣(b′,p)∈E∧(b′,p′)∈E}∣n_p = |\{b' \in C(b) \mid(b',p) \in E \land(b',p') \in E\}|. Define the amplified rating Πamp\Pi_{\mathrm{amp}}:

Πamp(b,p′):=maxflow⁡(Na(b,p′),b→p′)(3)\Pi_{\mathrm{amp}}(b,p') := \operatorname{maxflow}(N_a(b,p'), b \to p') \tag*{(3)}

Computational Complexity

For Πsum\Pi_{\mathrm{sum}}, bridge⁡(b,b′)\operatorname{bridge}(b,b') depends only on b′b' and not on the candidate provider, so it can be precomputed in O(∣K(b)∣⋅∣C(b)∣)O(|K(b)| \cdot|C(b)|) time, yielding O(1)O(1) evaluation per candidate. In contrast, Πflow\Pi_{\mathrm{flow}} and Πamp\Pi_{\mathrm{amp}} run Dinic’s max-flow algorithm [10] once per candidate provider on the localized query network N(b,p′)N(b,p') (not the global graph) which has V=∣K(b)∣+∣C(b)∣+2V = |K(b)| + |C(b)| + 2 nodes and E=O(∣K(b)∣⋅∣C(b)∣)E = O(|K(b)| \cdot|C(b)|) arcs, so each candidate costs O(V2E)O(V^2E).

Security Guarantees

We establish two core security bounds governing adversarial manipulation across our three constructions.

Theorem 5.1 (Budget-Bounded Rating Cap). Let G⇝G′G \leadsto G' be a graph transformation where the adversary spends mm dollars in payments to external providers outside AA. Under assumptions A1A_1 and A2A_2, Π(b,p∗)≤m\Pi(b,p^*) \le m for Π∈{Πflow,Πsum,Πamp}\Pi\in\{\Pi_{\mathrm{flow}},\Pi_{\mathrm{sum}},\Pi_{\mathrm{amp}}\} regardless of the number of Sybil identities created. This bound is tight.

Proof. Let A⊂B∪PA \subset B \cup P denote the set of adversary-controlled addresses, with target provider p∗∈Ap^* \in A. Under assumption A2A_2, the querying buyer’s trusted provider set K(b)K(b) satisfies K(b)∩A=∅K(b) \cap A = \varnothing. Since p∗p^* is adversary-controlled and has not provided real service to honest buyers, no honest co-user b′∉Ab' \notin A has paid p∗p^*; any such payment would reflect genuine service, not manipulation. Therefore, every route b→p→b′→p∗b \to p \to b' \to p^* passes through b′∈A∩C(b)b' \in A \cap C(b) and only adversarial co-users contribute flow toward p∗p^*.

Under Definition 4.2, each payment from an adversarial b′∈Ab' \in A to an honest provider p∉Ap \notin A costs w(b′,p)+ϵw(b',p) + \epsilon, permanently removing capital from AA. Let m=∑b′∈A∑p∈K(b)w(b′,p)m = \sum_{b' \in A} \sum_{p \in K(b)} w(b',p) denote the adversary’s total payments from AA directly to honest known providers. Fees ϵ\epsilon are excluded because they do not contribute to edge weight, so their inclusion would only increase true spend.

We consider each construction:

  1. Πflow\Pi_{\mathrm{flow}}: In the query network N(b,p∗)N(b,p^*), the boundary arcs {(p,b′)∣p∈K(b),b′∈A∩C(b)}\{(p,b') \mid p \in K(b), b' \in A \cap C(b)\} form a cut separating bb from p∗p^* with total capacity:

∑b′∈A∩C(b)∑p∈K(b)w(b′,p)=m.\sum_{b' \in A \cap C(b)} \sum_{p \in K(b)} w(b',p) = m.

By the Max-Flow Min-Cut Theorem, maximum flow is bounded by the capacity of any cut; since this cut has capacity mm, we have Πflow(b,p∗)≤m\Pi_{\mathrm{flow}}(b,p^*) \le m. (2) Πsum\Pi_{\mathrm{sum}}: By definition,

Πsum(b,p∗)=∑b′∈C(b)min⁡(bridge⁡(b,b′),w(b′,p∗)).\Pi_{\mathrm{sum}}(b,p^*)=\sum_{b'\in C(b)}\min(\operatorname{bridge}(b,b'),w(b',p^*)).

Honest co-users b′∉Ab'\notin A have never transacted with adversarial provider p∗p^*, so w(b′,p∗)=0w(b',p^*)=0 for all b′∉Ab'\notin A. Thus, only adversarial identities b′∈Ab'\in A contribute:

Πsum(b,p∗)=∑b′∈A∩C(b)min⁡(bridge⁡(b,b′),w(b′,p∗))≤∑b′∈A∩C(b)bridge⁡(b,b′).\begin{aligned} \Pi_{\mathrm{sum}}(b,p^*)=\sum_{b'\in A\cap C(b)}\min(\operatorname{bridge}(b,b'),w(b',p^*)) \\ &\le\sum_{b'\in A\cap C(b)}\operatorname{bridge}(b,b'). \end{aligned}

Recall the bridge definition:

bridge⁡(b,b′)=∑p∈K(b)min⁡(w(b,p),w(b′,p))≤∑p∈K(b)w(b′,p).\operatorname{bridge}(b,b')=\sum_{p\in K(b)}\min(w(b,p),w(b',p))\le\sum_{p\in K(b)}w(b',p).

Summing across all b′∈Ab'\in A:

Πsum(b,p∗)≤∑b′∈A∩C(b)∑p∈K(b)w(b′,p)=m.\Pi_{\mathrm{sum}}(b,p^*)\le\sum_{b'\in A\cap C(b)}\sum_{p\in K(b)}w(b',p)=m.

(3) Πamp\Pi_{\mathrm{amp}}: In Na(b,p∗)N_a(b,p^*), arc capacities leaving bb are scaled by np∗n_{p^*}. However, the cut separating K(b)K(b) from AA consists of the boundary arcs (p,b′)(p,b') for b′∈Ab'\in A, whose capacities remain w(b′,p)w(b',p) unscaled. Because these arcs form a cut separating bb from p∗p^* (similar to Πflow\Pi_{\mathrm{flow}} case above), max-flow cannot exceed their aggregate capacity mm. Hence Πamp(b,p∗)≤m\Pi_{\mathrm{amp}}(b,p^*)\le m.

To prove tightness, consider an adversary that instantiates nn Sybil buyers {b1′,…,bn′}⊂A\{b'_1,\ldots,b'_n\}\subset A, each paying an honest provider p∈K(b)p\in K(b) an amount m/nm/n, and executing a self-directed payment w(bi′,p∗)≥m/nw(b'_i,p^*)\ge m/n. When m/n≤w(b,p)m/n\le w(b,p), min⁡(w(b,p),w(bi′,p))=m/n\min(w(b,p),w(b'_i,p))=m/n. The bridge capacity for each identity is bridge⁡(b,bi′)=m/n\operatorname{bridge}(b,b'_i)=m/n. Summing across all nn identities yields ∑i=1n(m/n)=m\sum_{i=1}^{n}(m/n)=m, achieving the bound with equality. □

Theorem 5.2 (Spend-Bounded Cap). For any adversarially reachable graph G⇝G′G\rightsquigarrow G', Πflow\Pi_{\mathrm{flow}} evaluated on G′G' is bounded by buyer bb’s total historical spend on GG: Πflow(b,p′)≤β(G,b)=∑p∈K(b)w(b,p)\Pi_{\mathrm{flow}}(b,p')\le\beta(G,b)=\sum_{p\in K(b)}w(b,p) for all p′∈Q(b)p'\in Q(b).

Proof. The arcs {(b,p)∣p∈K(b)}\{(b,p)\mid p\in K(b)\} form a cut in N(b,p′)N(b,p') separating bb from any candidate provider p′p', with total capacity:

∑p∈K(b)w(b,p)=β(G,b).\sum_{p\in K(b)}w(b,p)=\beta(G,b).

By the Max-Flow Min-Cut Theorem, maximum flow is bounded by the capacity of any cut, so Πflow(b,p′)≤β(G,b)\Pi_{\mathrm{flow}}(b,p')\le\beta(G,b). Since settled transactions are immutably recorded on the public ledger, no adversary can alter or fabricate payments from bb, so β(G,b)\beta(G,b) is unchanged across all reachable graphs G′G'.

These theorems establish two structural cap categories. Theorem 5.1 gives an outlay-proportional cap mm for all three schemes: reputation inflation requires proportional real expenditure, so Sybil identities paying only base fees ee provide zero rating leverage. Theorem 5.2 gives a stricter buyer cap β(G,b)\beta(G,b) for Πflow\Pi_{\mathrm{flow}}, determined solely by bb’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 (τ=90\tau=90 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 ≥2\ge2 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 Q(b)Q(b) 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 p∗p^* 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 p∗p^*’s ranking. We solve for the minimum spend required for p∗p^* to achieve target rank kk, as illustrated in Figure 5.

Evaluation pipeline

Figure 5. Evaluation pipeline. From one snapshot of payments settled before TT we measure both properties. Utility (top): the scheme ranks the candidates Q(b)Q(b), and we check where it places p+p^{+}, the first new provider bb actually pays after TT. Attack cost (bottom): we inject target provider p∗p^{*} and arbitrarily many Sybil identities that pay into bb’s known providers, rescore, and record the minimum spend that lifts p∗p^{*} to rank kk.

Utility

We evaluate ranking accuracy using pairwise discrimination (AUC) and top-1 precision (P@1P@1), as defined in Definition 4.3; results appear in Table 2. AUC measures the probability of ranking true next provider p+p^+ above an unchosen candidate provider q∈Q(b)∖{p+}q \in Q(b) \setminus\{p^+\}. P@1P@1 measures the fraction of buyers for whom the true choice achieves first rank.

w(b,p)w(b,p)Πflow\Pi_{\mathrm{flow}}Πsum\Pi_{\mathrm{sum}}Πamp\Pi_{\mathrm{amp}}
AUCP@1P@1AUCP@1P@1AUCP@1P@1
dollars (w$w_{\$}) | 0.747 | 4.8 | 0.859 | 19.4 | 0.859 | 22.5
dollars + fee (w$ϵw_{\$\epsilon}) | 0.758 | 4.8 | 0.871 | 20.0 | 0.869 | 22.8
log dollars (wlog⁡w_{\log})0.7495.20.86120.40.86223.6
payments (w#w_{\#})0.7615.40.87821.90.87723.5
BaselinesAUCP@1P@1
Πuse\Pi_{\mathrm{use}}0.8073.7payments into p′p'
Πspend\Pi_{\mathrm{spend}}0.74912.1co-user spend at p′p'
Πcf\Pi_{\mathrm{cf}}0.88023.2co-users paying p′p'

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 w(b,p)w(b,p).

Transaction counting (w#w_{\#}) achieves the strongest AUC among flow constructions (Πsum\Pi_{\mathrm{sum}} 0.878, Πamp\Pi_{\mathrm{amp}} 0.877, Πflow\Pi_{\mathrm{flow}} 0.761), approaching the collaborative filtering Πcf\Pi_{\mathrm{cf}} baseline (0.880). All constructions exceed the random baseline (AUC = 0.5). Plain dollars (w$w_{\$}) 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.

Πamp\Pi_{\mathrm{amp}} achieves the highest top-1 precision—23.6% under wlog⁡w_{\log}—exceeding all baselines. Πflow\Pi_{\mathrm{flow}} is an outlier: despite AUC ≥0.75\ge0.75, its P@1P@1 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 (τ\tau). We evaluate look-back τ∈[15,90]\tau\in[15, 90] days on the same set of buyers for Πamp\Pi_{\mathrm{amp}}. Extending τ\tau monotonically increases AUC from 0.829 at 15 days to 0.869 at 90 days. P@1P@1 peaks at 30 days (24.7%) before candidate provider set expansion (304 →\rightarrow 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 (w$ϵw_{\$\epsilon}). We set base fee ϵ=$0.017\epsilon= \$0.017, 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 (Πspend\Pi_{\mathrm{spend}}) costs only a single fee ($0.017) via circular self-payments. Usage ranking (Πuse\Pi_{\mathrm{use}}) 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 (Πcf\Pi_{\mathrm{cf}}) is 23× cheaper to subvert than Πamp\Pi_{\mathrm{amp}} ($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 (Πsum\Pi_{\mathrm{sum}}) and $898 (Πflow\Pi_{\mathrm{flow}}) to reach all buyers, against just $50 under Πcf\Pi_{\mathrm{cf}}. This gap narrows as kk 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 Πcf\Pi_{\mathrm{cf}}, significantly less than Anđuin constructions, which require $3,183 (Πsum),$4,096(\Pi_{\mathrm{sum}}), \$4,096 (\Pi_{\mathrm{flow}}), and $5,490 ($\Pi_{\mathrm{amp}}). Further detail appears in Section 6.4.2 (Table 5).

top NNtarget spendΠcf\Pi_{\mathrm{cf}}Πflow\Pi_{\mathrm{flow}}Πsum\Pi_{\mathrm{sum}}Πamp\Pi_{\mathrm{amp}}
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-NN buyers ranked by spend (rank 1, fee-inclusive dollar weight w$εw_{\$ \varepsilon}, ε=$0.017\varepsilon= \$0.017).

Overall. Evaluating utility and attack cost jointly (Figure 6) establishes Πamp\Pi_{\mathrm{amp}} as best construction: baselines either collapse under cheap manipulation (Πcf\Pi_{\mathrm{cf}}) or yield poor predictive accuracy (Πuse\Pi_{\mathrm{use}}), whereas Πamp\Pi_{\mathrm{amp}} achieves high precision (P@1=22.8%P@1 = 22.8\%) while enforcing an attack cost equal to 20% of target buyer spend, both under

Utility versus manipulation cost

Figure 6. Utility versus manipulation cost. Horizontal: ranking accuracy (P@1P@1). Vertical: cost to capture rank 1 for all 813 buyers, as a fraction of their combined spend, under w$ϵw_{\$\epsilon}. Positions are ordinal, not to scale; exact values are in Tables 2 and 3. Only Πsum\Pi_{\mathrm{sum}} and Πamp\Pi_{\mathrm{amp}} are both accurate and expensive to subvert. Πcf\Pi_{\mathrm{cf}} matches their accuracy but costs $358 to subvert, and Πuse\Pi_{\mathrm{use}} is expensive only because it ranks poorly (P@1=3.7%P@1 = 3.7\%).

w$ϵw_{\$\epsilon}; with Πsum\Pi_{\mathrm{sum}}, it is the only scheme in the figure’s accurate-and-costly quadrant.

Extended Empirical Analyses {#sec:6.4}

Look-Back (τ\tau) Sensitivity {#sec:6.4.1}

We evaluate the impact of historical look-back duration τ∈[15,90]\tau\in[15, 90] 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 (w$ϵw_{\$\epsilon}).

Candidates is the mean number of providers on each buyer’s candidate list Q(b)Q(b); it grows with τ\tau 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 Q(b)Q(b); if it is absent, no rating can rank it first. P@1P@1 | reachable conditions only on buyers whose true provider was reachable, separating ranking quality from candidate generation quality. Extending τ\tau monotonically increases both coverage (from 70.5% at 15 days to 90.7% at 90 days) and ranking separation (AUC reaches 0.869). However, P@1P@1 peaks at τ=30\tau= 30 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.

τ\tau (days)candidatescoverageAUCP@1P@1P@1P@1 | reachable
1526170.5%0.82912.918.3
3030483.4%0.86024.729.6
4533787.2%0.86021.224.3
6035688.4%0.86321.524.3
7536889.7%0.86823.025.7
9038190.7%0.86922.825.1

Table 4. Look-back window τ\tau vs. utility on the fixed 813-buyer cohort under fee-inclusive dollar weighting (w$ϵw_{\$\epsilon}). Candidates: mean length of candidate list Q(b)Q(b). Coverage: fraction of buyers whose true next provider appears somewhere in Q(b)Q(b); buyers outside coverage always count as misses. P@1P@1 | 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-NN highest-spending buyers (ranked by 90-day transaction volume).

top 1top 5top 10top 25
frac.costfrac.costfrac.costfrac.cost
Baselines
Πuse\Pi_{\mathrm{use}}5.263$217,539 | 0.178 | $7,3500.021$848 | 0.008 | $310
Πspend\Pi_{\mathrm{spend}}0.000$0.02 | 0.000 | $0.020.000$0.02 | 0.000 | $0.02
Πcf\Pi_{\mathrm{cf}}0.009$358 | 0.003 | $1380.002$100 | 0.001 | $50
Anđuin Constructions
Πflow\Pi_{\mathrm{flow}}0.113$4,673 | 0.059 | $2,4200.041$1,701 | 0.022 | $898
Πsum\Pi_{\mathrm{sum}}0.105$4,330 | 0.034 | $1,4200.023$961 | 0.012 | $494
Πamp\Pi_{\mathrm{amp}}0.200$8,259 | 0.040 | $1,6610.028$1,145 | 0.013 | $554

Table 3. Minimum cost to capture top-kk rank across all buyers, reported in USD and as a fraction of combined spend of the 813 tested buyers ($41,331). Πuse\Pi_{\mathrm{use}} 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 (Πcf\Pi_{\mathrm{cf}}), an adversary can capture the single highest-spending buyer for $1.86 and the entire top decile (N=79N = 79, representing 91% of total market volume) for just $53. In contrast, flow-based constructions enforce substantial capital requirements. Subverting the top decile under Πamp\Pi_{\mathrm{amp}} requires $5,490 (14.6% of spend), $4,096 under Πflow\Pi_{\mathrm{flow}}, and $3,183 under Πsum\Pi_{\mathrm{sum}}. This confirms that flow-based ratings effectively price systemic market capture rather than single-buyer preferences.

6.4.3 Alternative Edge Weighting: Calendar Days (wdw_d). An alternative edge weight deferred from Section 5.1 counts distinct calendar days with settled transactions: wd(b,p)=∣{day⁡(ti)}∣w_d(b,p) = |\{\operatorname{day}(t_i)\}|. 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, wdw_d yields the highest ranking utility across all evaluated metrics, lifting Πamp\Pi_{\mathrm{amp}} to AUC = 0.881 and P@1P@1 = 25.5% (compared to 0.869 and 22.8% under w$εw_{\$ \varepsilon}), and lifting Πsum\Pi_{\mathrm{sum}} by a comparable margin.

However, we omit wdw_d from our primary attack cost benchmarking because temporal delay cannot be directly priced in financial terms. Forging a unit of wdw_d 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 K(b)K(b), co-users C(b)C(b), or reachable candidate providers Q(b)Q(b). 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 K(b)K(b) 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: Πflow\Pi_{\mathrm{flow}} which enforces strict rating ceilings on the buyer’s historical spend, Πsum\Pi_{\mathrm{sum}} which replicates capacity per co-user to improve rating efficacy and Πamp\Pi_{\mathrm{amp}} 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 methodEvent logsTop-level transaction to address
EIP-3009 directAuthorizationUsed and TransferToken contract.
Permit2 ExactSettled or SettledWithPermit, and TransferPermit2 Exact proxy: 0x402085c248eea27d92e8b30b2c58ed07f9e20001.
Permit2 UptoSettled or SettledWithPermit, and TransferPermit2 Upto proxy: 0x4020a4f3b7b90ccca423b9fabc0ce57c62400002.
MulticallA settlement event listed above and TransferNeither 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. [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. [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. [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. [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. [5]Circle. 2026. Introducing Circle Agent Stack: Financial Infrastructure for the Agentic Economy. Online. https://agents.circle.com
  6. [6]Coinbase and CDP. 2026. x402 Bazaar: discovery layer for payable HTTP APIs (docs). Online; docs. https://docs.cdp.coinbase.com/x402/bazaar
  7. [7]Coinbase and x402 Foundation. 2025. x402: HTTP-native payment protocol (homepage, foundation README, v2 spec). Online; website. https://www.x402.org/
  8. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [19]MPPSCan. 2026. MPPSCan: The Machine Payments Protocol Explorer. Live dashboard, https://mppscan.com/?d=0. Accessed 22 June 2026.
  20. [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. [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. [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. [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. [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. [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. [26]Tempo and Stripe. 2026. Machine Payments Protocol (MPP): spec, docs, and IETF Payment HTTP auth scheme. Online; spec. https://mpp.dev
  27. [27]World (Worldcoin). 2023. World Whitepapers. Online. https://whitepaper.world.org/ Whitepaper series; updated March 2026.
  28. [28]x402scan. 2026. x402scan: x402Scan: x402scan Explorer. Live dashboard, https://www.x402scan.com/ Accessed July 2026.
  29. [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. [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

Paper details

vlnc:W_wpn3auxa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents