Trustworthy Reputation Games and Applications to Proof-of-Reputation Blockchains

Petros Drineas, Rohit Nema, Rafail Ostrovsky, Vassilis Zikas

TL;DR

This paper introduces a formal game-theoretic framework to help blockchains distill the collective "gut feelings" of their nodes into a reliable reputation system. By adapting the PageRank algorithm and designing a new class of "Trustworthy Reputation (TRep) games," the authors show how a decentralized network can incentivize users to report their true beliefs about which nodes are actually trustworthy.

What Problem Does This Paper Address?

In the world of decentralized ledgers and DeFi, trust is everything. Many modern "Layer-2" scaling solutions (like optimistic rollups) rely on the assumption that certain entities will behave honestly. However, relying on absolute trust in a system securing billions of dollars is a massive systemic risk.

Currently, blockchains often equate "trustworthiness" with "wealth" (Proof-of-Stake) or "computing power" (Proof-of-Work). But having a lot of money doesn't necessarily mean a node is reliable at performing specific technical tasks. The authors identify a major gap: How can a blockchain extract a meaningful reputation score from the collective beliefs of its participants while ensuring those participants don't lie to game the system?

Methods

The authors break the challenge into two sub-problems: Information Extraction (turning beliefs into a score) and Incentive Design (making sure those beliefs are reported truthfully).

  1. Designated PageRank: To solve the extraction problem, the authors adapt Google’s famous PageRank algorithm. In their version, "users" (nodes) provide "endorsements" (weighted links) to "servers" (the nodes being ranked). They fine-tune the algorithm’s "teleportation" mechanism so the random walk only resets to users, ensuring the final scores accurately reflect the relative trustworthiness of the servers.
  2. TRep Games: To solve the incentive problem, they introduce a new class of Bayesian games. In these games, a user's reward is proportional to their "contribution" to a server's reputation score, calculated using Personalized PageRank.
  3. Decoding Function: They define a formal "decoding" process that takes the strategies played by rational actors in the game and translates them back into a system-wide reputation vector.

Datasets

This is a theoretical paper focused on formal proofs and algorithm design. As such, it does not use standard empirical datasets or training sets. Instead, the authors use mathematical "benchmarks"—scenarios with perfect information or specific noise distributions—to prove that their mechanism recovers the "ground truth" of node trustworthiness.

Key Insights and Ideas

  • PageRank as a Trust Mirror: The "aha moment" is realizing that PageRank is essentially a way to distill importance from a network of opinions. If nodes are perfectly informed, PageRank doesn't just give an order; it perfectly recovers the ratios of trustworthiness between nodes.
  • Incentivizing the "Truth-Telling" Strategy: The authors prove that by tying rewards to a node's contribution to the final PageRank score, "truth-telling" (reporting your actual belief) becomes a Nash Equilibrium. If you lie to boost a friend, you likely decrease your own "contribution" score and lose rewards.
  • Robustness to Noise: One of the most important findings is that the system doesn't require everyone to be perfect. Even if nodes have "noisy" or slightly inaccurate beliefs, the collective PageRank output remains a very close approximation of the truth.
  • Hierarchical Information: The system works even if only a small subset of "veteran" nodes has perfect information, while "fresh" nodes are mostly guessing.

Key Results

  • Theorem 1 (Perfect Information): In a scenario where all users know the true trustworthiness of servers, the TRep game has a unique Nash Equilibrium that perfectly encodes the ground truth ratios.
  • Theorem 2 (Noisy Information): In a more realistic "noisy" setting, the authors prove that the system is $(\epsilon, f)$-decodable. This means that as the network scales, the blockchain can still recover a reputation vector that is "close" to the ground truth with high probability.
  • Application to PoR: The authors demonstrate how this can bootstrap a Proof-of-Reputation (PoR) blockchain, allowing it to select honest-majority committees without needing a pre-existing trust setup.

Limitations and Future Work

  • One-Shot vs. Repeated Games: The current analysis focuses on a "one-shot" game. In the real world, reputation is built over time. The authors note that extending this to repeated games is a vital next step.
  • Sensitivity to Misinformation: While the system handles random noise well, the authors leave the study of "adversarial misinformation" (coordinated attacks to tank a node's reputation) for future research.
  • Computational Overhead: Calculating Personalized PageRank for every reward distribution could be intensive; future work might look into more efficient approximations for on-chain execution.

Summary updated

Abstract

We investigate how a blockchain can distill the collective belief of its nodes regarding the trustworthiness of a (sub)set of nodes into a {\em reputation system} that reflects the probability of correctly performing a task. To address this question, we introduce a framework that breaks it down into two sub-problems: 1. (Information Extraction): How can the system distill trust information from a function of the nodes' true beliefs? 2. (Incentive Design): How can we incentivize nodes to truthfully report such information? To tackle the first sub-problem, we adapt, in a non-trivial manner, the well-known PageRank algorithm to our problem. For the second, we define a new class of games, called Trustworthy Reputation games (TRep games), which aim to extract the collective beliefs on trust from the actions of rational participants. We then propose a concrete TRep game whose utility function leverages Personalized PageRank and can be instantiated through a straightforward blockchain rewards mechanism. Building on this, we show how the TRep game enables the design of a reputation system. Such systems can enhance the robustness, scalability, and efficiency of blockchain and DeFi solutions. For instance, we demonstrate how such a system can be used within a Proof-of-Reputation blockchain.
BibTeX
@misc{drineas2025trustworthy,
  author = {Petros Drineas and Rohit Nema and Rafail Ostrovsky and Vassilis Zikas},
  title = {{Trustworthy Reputation Games and Applications to Proof-of-Reputation Blockchains}},
  year = {2025},
  eprint = {2505.14551},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.14551},
}
Figure