As autonomous AI agents enter permissionless on‑chain markets, selecting trustworthy service providers remains a fundamental challenge. Existing reputation mechanisms rely on scarce resources such as human curation, identity credentials, or voluntary reviews, while simple volume‑based rankings are vulnerable to Sybil attacks. We investigate whether on‑chain payment histories alone can produce provider ratings that resist Sybil manipulation. Using a 157‑day dataset covering 66 million transactions worth $6.1 M across 16 blockchains, we model payment flows as a bipartite graph linking buyers and providers. A provider’s rating is derived from graph paths that intersect the buyer’s existing trusted network. Based on this model we propose three Sybil‑resistant rating algorithms: a max‑flow‑based rating and two relaxed variants that preserve rating quality while improving efficiency. Simulating adversaries over 813 buyers, we evaluate the algorithms and find that manipulating a rating costs about 20 % of the buyers’ total spend and is roughly 23 times harder than using the standard similarity rule (collaborative filtering).\n\nReview: Anduin demonstrates that direct inference of trustworthy scores from on‑chain payment graphs is feasible, and that max‑flow‑style techniques can dramatically raise the bar against Sybil attacks, offering a promising security foundation for decentralized service marketplaces.