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).
Figures & tables
Table 1. Comparison of reputation approaches for agentic marketplaces. offered, partially offered, not offered.
Figure 1. The bipartite payment graph model. For querying buyer b : K(b) are known providers, C(b) are co-users sharing known providers, and Q(b) are candidate providers reachable through co-users. A 3-hop route b–p–b′–p′ carries three edge weights. Unconnected nodes ( b′′,p′′ ) remain unrated.
Figure 2. Cost of forging an edge by type under A1 – A2 . Internal edges within A cost only network fee ϵ while payments to external providers cost full value w+ϵ and edges incident to honest buyer b cannot be fabricated at any price.
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′ reads edges the adversary pays to itself.
Figure 4. Rating comparison on an example ( w(b,p)=4 , b1′ pays p and p′\8each,b^{\prime}{2}pays$1each).\Pi{\mathtt{flow}}sharesw(b,p),bottleneckingflowatb’soutgoingarc(\Pi_{\mathtt{flow}}=4).\Pi_{\mathtt{sum}}allocatesprivatecopiesperco−user,summingindependentflows(\Pi_{\mathtt{sum}}=4+1=5).\Pi_{\mathtt{amp}}poolsn_{p}=2copiesacrossco−userspayingp^{\prime},allowingb^{\prime}{1}todrawallavailablecapacity(\Pi{\mathtt{amp}}=8$ ).
Figure 5. Evaluation pipeline. From one snapshot of payments settled before T we measure both properties. Utility (top): the scheme ranks the candidates Q(b) , and we check where it places p+ , the first new provider b actually pays after T . Attack cost (bottom): we inject target provider p∗ and arbitrarily many Sybil identities that pay into b ’s known providers, rescore, and record the minimum spend that lifts p∗ to rank k .
Πflow
Πsum
Πamp
w(b,p)
AUC
P@1
AUC
P@1
AUC
P@1
dollars ( w_{\}$ )
0.747
4.8
0.859
19.4
0.859
22.5
dollars + fee ( w_{\\epsilon}$ )
0.758
4.8
0.871
20.0
0.869
22.8
log dollars ( wlog )
0.749
5.2
0.861
20.4
0.862
23.6
payments ( w# )
0.761
5.4
0.878
21.9
0.877
23.5
Baselines
AUC
P@1
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.
top 1
top 5
top 10
top 25
frac.
cost
frac.
cost
frac.
cost
frac.
cost
Baselines
Πuse†
5.263
\217{,}539$
0.178
\7{,}350$
0.021
\848$
0.008
\310$
Πspend
0.000
\0.02$
0.000
\0.02$
0.000
\0.02$
0.000
\0.02$
Πcf
0.009
\358$
0.003
\138$
0.002
\100$
0.001
\50$
Anduin Constructions
Table 3. Minimum cost to capture top- k rank across all buyers, reported in USD and as a fraction of combined spend of the 813 tested buyers ( \41{,}331).{}^{\dagger}\Pi_{\mathtt{use}}$ scores providers globally.
Figure 6. Utility versus manipulation cost. Horizontal: ranking accuracy ( P@1 ). Vertical: cost to capture rank 1 for all 813 buyers, as a fraction of their combined spend, under w_{\\epsilon}.Positionsareordinal,nottoscale;exactvaluesareinTables2and3.Only\Pi_{\mathtt{sum}}and\Pi_{\mathtt{amp}}arebothaccurateandexpensivetosubvert.\Pi_{\mathtt{cf}}matchestheiraccuracybutcosts$358tosubvert,and\Pi_{\mathtt{use}}isexpensiveonlybecauseitrankspoorly(P@1=3.7%$ ).
Πamp
τ (days)
candidates
coverage
AUC
P@1
P@1∣ 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
Table 4. Look-back window τ vs. utility on the fixed 813-buyer cohort under fee-inclusive dollar weighting ( w_{\\epsilon}).Candidates:meanlengthofcandidatelistQ(b).Coverage:fractionofbuyerswhosetruenextproviderappearssomewhereinQ(b);buyersoutsidecoveragealwayscountasmisses.P@1\mid\text{reachable}$ : top-1 precision conditioned on the true provider being reachable, isolating ranking quality from candidate generation quality.
top N
target spend
Πcf
Πflow
Πsum
Πamp
1
\12{,}612$
\1.86$
\289$
\289$
\mathbf{\291}$
10
\22{,}981$
\14$
\2{,}508$
\1{,}716$
\mathbf{\4{,}138}$
79
\37{,}566$
\53$
\4{,}096$
\3{,}183$
\mathbf{\5{,}490}$
813
\41{,}331$
\358$
\4{,}673$
\4{,}330$
\mathbf{\8{,}259}$
Table 5. Targeted attack cost on top- N buyers ranked by spend (rank 1, fee-inclusive dollar weight w_{\\epsilon},\epsilon=$0.017$ ).