Game of Trust: How Trustworthy Does Your Blockchain Think You Are?

Petros Drineas, Rohit Nema, Rafail Ostrovsky, Vassilis Zikas

TL;DR

This paper introduces a novel framework for blockchains to build a "trustworthy reputation system" by aggregating node beliefs about each other's trustworthiness. It achieves this by adapting the PageRank algorithm for information extraction and designing "Trustworthy Reputation games" (TRep games) to incentivize truthful reporting, ultimately enhancing blockchain robustness and efficiency.

What Problem Does This Paper Address?

Decentralized systems like blockchains inherently rely on trust. However, assuming absolute trust in all participants is problematic and risky, especially in systems managing significant assets. While some protocols use collateralization (like stake) or implicit trust mechanisms, this paper tackles the fundamental question: How can a blockchain system itself distill the collective belief of its nodes into a meaningful reputation system that reflects the probability of nodes performing tasks correctly? This involves two key challenges: extracting trust information from node beliefs and incentivizing nodes to report these beliefs truthfully.

Methods

The authors break down the problem into two sub-problems:

  1. Information Extraction: They adapt the PageRank algorithm (specifically, a weighted version) to process a graph where nodes represent blockchain participants and edge weights represent their beliefs about others' trustworthiness. This adapted PageRank is used to compute a system-wide reputation score. They also introduce Designated PageRank, which focuses on ranking a specific subset of nodes (e.g., servers) by modifying the graph structure to handle "sink" nodes (nodes with no outgoing edges).
  2. Incentive Design: To ensure nodes report their beliefs truthfully, they define a new class of games called Trustworthy Reputation (TRep) games. These are Bayesian games against "nature" (representing the true trustworthiness of nodes). The core idea is to design utility functions such that it becomes a Nash equilibrium for rational players to report their beliefs in a way that aligns with the PageRank-derived reputation. They propose specific utility functions leveraging Personalized PageRank and demonstrate how these can be implemented via blockchain rewards.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • PageRank as a Reputation Distiller: The paper ingeniously repurposes PageRank, a well-known algorithm for ranking web pages, to aggregate individual node beliefs into a collective reputation score. This is a novel application of a standard algorithm.
  • TRep Games for Truthful Reporting: The introduction of TRep games provides a formal game-theoretic framework to incentivize honest reporting. The design ensures that rational players are motivated to reveal their true beliefs about others' trustworthiness.
  • Decodability as a Formal Guarantee: The concept of "(E, f)-decodability" is introduced to formally guarantee that the players' strategies in TRep games can be decoded to reveal the underlying trustworthiness information. This provides a rigorous way to assess the effectiveness of the reputation system.
  • Hierarchical Information and Noisy Beliefs: The paper explores scenarios with imperfect or hierarchical information, showing that the system can still provide meaningful reputation estimates even when not all nodes are perfectly informed or when beliefs are noisy.

Key Results

  • The adapted PageRank algorithm can produce a ratio-preserving reputation score under perfect information, meaning the relative ordering of nodes by their computed reputation matches their true trustworthiness.
  • TRep games, with utilities based on Personalized PageRank, establish Nash equilibria where players' strategies encode their beliefs.
  • The proposed framework is shown to be (E, f)-decodable under various assumptions about information quality, meaning the blockchain can reliably extract reputation information.
  • The paper demonstrates how this framework can be applied to Proof-of-Reputation (PoR) blockchains, offering a concrete mechanism for bootstrapping and operating such systems.

Limitations and Future Work

  • Assumptions on Information: The current framework relies on certain assumptions about the nature of node beliefs (e.g., perfect information, consistent noise). The paper acknowledges that the robustness to more arbitrary or adversarial information structures is an open question.
  • Repeated Games and Dynamic Reputation: The current model primarily focuses on a one-shot game. Future work could explore extending the treatment to repeated games, allowing for dynamically updateable reputation systems.
  • Empirical Analysis: While the theoretical framework is strong, the paper suggests exploring the behavior of the PageRank model on different graph structures and topologies empirically.
  • Sensitivity to Misinformation: Investigating the sensitivity of the reputation system to misinformed users is highlighted as a crucial area for future research.

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{drineas2025game,
  author = {Petros Drineas and Rohit Nema and Rafail Ostrovsky and Vassilis Zikas},
  title = {{Game of Trust: How Trustworthy Does Your Blockchain Think You Are?}},
  year = {2025},
  eprint = {2505.14551},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.14551},
}
Figure