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

Basic Information

• Paper ID: 2505.14551
• Title: Game of Trust: How Trustworthy Does Your Blockchain Think You Are?
• Authors: Petros Drineas (Purdue University), Rohit Nema (Stanford University), Rafail Ostrovsky (UCLA), Vassilis Zikas (Georgia Tech)
• Classification: cs.GT (Game Theory), cs.AI (Artificial Intelligence), cs.CR (Cryptography and Security)
• Publication Date: October 9, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2505.14551

Abstract

This paper investigates how to enable blockchains to extract reputation systems regarding the trustworthiness of node subsets from the collective beliefs of their nodes, systems that reflect the probability of correct task execution. The paper decomposes this problem into two sub-problems: (1) Information Extraction: How can the system extract trust information from a function of nodes' true beliefs? (2) Incentive Design: How can nodes be incentivized to truthfully report such information? To address the first sub-problem, the authors adapt the renowned PageRank algorithm in a non-trivial manner; to address the second, they define a new class of games—Trustworthy Reputation games (TRep games)—aimed at extracting collective beliefs about trust from the actions of rational participants.

Research Background and Motivation

Core Problem

The central challenge of blockchains and decentralized systems is the trust problem. Without a central authority, how can one determine which nodes deserve trust to execute specific tasks? This directly impacts system quality and efficiency.

Research Significance

1. Layer-2 Scaling Solution Requirements: Layer-2 solutions such as optimistic protocols rely on assumptions about the trustworthiness of specific entities, yet absolute trust presents systemic risks in systems managing billions of dollars in assets.
2. Limitations of Existing Approaches:
   • Traditional methods rely on collateral mechanisms, requiring trusted parties to provide collateral with economic penalties for deviating from honest execution
   • Existing reputation systems are typically ad-hoc and implicit, lacking rigorous formal analysis
   • Equating reputation with system resources (such as stake or computational power) fails to directly reflect trustworthiness

Research Motivation

The paper poses the core question: How can blockchains derive reputation systems for node subsets by extracting the system's collective beliefs about node trustworthiness?

Core Contributions

1. Conceptual Contribution: A systematic framework decomposing the complex problem into information extraction and incentive design sub-problems
2. Technical Contributions:
   • Proposes Designated PageRank algorithm, adapting PageRank for reputation extraction
   • Defines a new game category: Trustworthy Reputation games (TRep games)
   • Designs specific utility functions based on personalized PageRank
3. Theoretical Contributions:
   • Proves that PageRank output maintains reputation score proportions under perfect information
   • Establishes correspondence between Nash equilibrium and reputation extraction
   • Provides approximation guarantees under noisy information
4. Application Contribution: Demonstrates how to integrate TRep games into Proof-of-Reputation blockchains

Methodology Details

Task Definition

Input: Beliefs of n user nodes regarding the trustworthiness of m server nodes Output: A reputation score vector reflecting relative trustworthiness of servers Constraint: Incentivize users to truthfully report their beliefs

Model Architecture

1. Trustworthy Reputation Graphs (TRep Graphs)

Define a directed weighted graph $G = (V \cup \hat{V}, E, R)$, where:

• $V = \{v_1, \ldots, v_n\}$: Set of user nodes
• $\hat{V} = \{\hat{v}_1, \ldots, \hat{v}_m\}$: Set of server nodes
• $R = (R_1, \ldots, R_m)$: Vector of server trustworthiness scores
• Edge weights represent users' trust in other nodes

2. Designated PageRank Algorithm

To address the dangling node problem (server nodes with zero out-degree), the traditional PageRank is modified:

$\pi = \pi(1-\alpha)W_{out}^{-1}M + \frac{\alpha}{n} \cdot [1_{n \times 1}, 0_{m \times 1}]$

Key modifications:

• Restrict teleportation only to user nodes
• Server node PageRank values are directly determined by weighted contributions from user nodes

3. Trustworthy Reputation Games (TRep Games)

Define a synchronous Bayesian game: $G = (P, A = \prod_{i \in [n]} A_i, (u_i)_{i \in [n]}, (T_i)_{i \in [n]}, (R_j)_{j \in [m]})$

Where:

• Players: $P = (P_i)_{i \in [n]}$, n agents/players
• Action Space: $A_i = [m+n]$, each player can endorse any server or user
• Nature's State: $(R_j)_{j \in [m]}$, each $R_j \in [0,1]$ represents probability
• Utility Functions: Based on personalized PageRank contributions

4. Utility Function Design

Expected utility for player $P_i$: $E[u_i(s,r)] = \sum_{j \in [m]} r_j \cdot \omega^{-1}_{\hat{v}_j|V}(v_i)$

Where $\omega^{-1}_{\hat{v}_j|V}(v_i)$ is the relative contribution of user $v_i$ to server $\hat{v}_j$'s reputation score.

Technical Innovation Points

1. Non-trivial Adaptation of PageRank:
   • Addresses issues with traditional PageRank under asymmetric node roles
   • Introduces restricted teleportation mechanism
   • Provides theoretical guarantees for proportion preservation
2. Integration of Game Theory and Reputation Extraction:
   • First formal integration of game-theoretic reasoning with reputation extraction mechanisms
   • Designs incentive-compatible utility functions
   • Establishes correspondence between Nash equilibrium and reputation decoding
3. Decodability Concept:
   • Defines $(E,f)$-decodability, where $E$ is a set of strategy profiles and $f$ is a reputation function
   • Provides efficient decoding function $D$ such that $D(e) \simeq f(R_1, \ldots, R_m)$

Experimental Setup

Theoretical Analysis Scenarios

The paper primarily conducts theoretical analysis, considering three information scenarios:

1. Perfect Information: All users have complete knowledge of the natural state $R$
2. Hierarchical Information: Some users ($P_{perfect}$) possess perfect information while others have incomplete information
3. Consistent Noisy Information: All users have noisy but consistent estimates of the natural state

Evaluation Metrics

• Proportion Preservation: $\frac{\rho_i}{\rho_j} = \frac{R_i}{R_j}$
• Approximation Accuracy: Approximation error under $L_\infty$ norm
• Nash Equilibrium Properties: Uniqueness and existence

Experimental Results

Main Theoretical Results

1. Perfect Information Scenario (Theorem 1)

Theorem 3: $G_{perfect}$ is $(E_{NE}, f_1)$-decodable, where $f_1 = N$ (L1 normalization function).

Lemma 2: $G_{perfect}$ has a unique Nash equilibrium $s^* = (N(R), \ldots, N(R))$.

2. Hierarchical Information Scenario

When a subset of users with perfect information exists, $(E_{NE}, f_1)$-decodability is maintained and unaffected by other users' strategies.

3. Noisy Information Scenario (Theorem 2)

Theorem 4: $G_{noisy}$ is $(E_{tt}, f_2)$-decodable, where:

• $E_{tt}$ is the "truth-telling" strategy profile
• $f_2$ outputs with high probability a vector close to $N(R)$ under $L_\infty$ norm

Lemma 3: Assuming $\epsilon = O(1/n)$, truth-telling strategy is an $\epsilon'$-Nash equilibrium, where $\epsilon' = O(m^2/n)$.

Experimental Findings

1. Unique Nash Equilibrium: Unique symmetric Nash equilibrium exists under perfect information
2. Robustness: Under hierarchical information structure, strategies of perfectly informed users are unaffected by noisy users
3. Scalability: As the number of users increases ($n \gg m$), approximation error decreases monotonically
4. Proportion Preservation: Maintains relative trustworthiness relationships between servers across various scenarios

Related Work

Blockchain Reputation Systems

• Tokenized Reputation: Rewarding reputation tokens through stake delegation mechanisms
• Proof-of-Reputation: Enhancing consensus protocols using existing reputation systems
• This Paper's Distinction: Directly extracts reputation from participant beliefs rather than indirectly through resource measurement

PageRank Applications

• Traditional Applications: Web page importance ranking, recommendation systems
• Game-Theoretic Extensions: Strategic PageRank manipulation research
• This Paper's Innovation: Simultaneously uses PageRank for utility design and decoding, specifically targeting trust assessment

Reputation and Game Theory

• Reputation in Repeated Games: Reputation learning based on historical behavior
• Bayesian Optimal Design: Mechanism design under incomplete information
• This Paper's Contribution: New framework for learning external reputation in one-shot games

Conclusions and Discussion

Main Conclusions

1. Feasibility Verification: Blockchains can reliably extract reputation systems for their nodes through a systematic framework
2. Theoretical Guarantees: Provides formal performance guarantees under different information assumptions
3. Practicality: Can be directly integrated into existing PoR blockchain systems

Limitations

1. Static Assumptions: Current framework assumes static reputation without considering dynamic updates
2. Information Requirements: Requires users to have certain understanding of servers
3. Collusion Resistance: Insufficient analysis of robustness against adversarial strategic coalitions
4. Empirical Validation: Primarily theoretical analysis lacking large-scale empirical experiments

Future Directions

1. Dynamic Reputation Systems: Extend to repeated game settings allowing dynamic reputation updates
2. Different Graph Topologies: Study PageRank behavior under different network structures
3. Sensitivity Analysis: Explore sensitivity to misinformed users
4. Empirical Evaluation: Validate theoretical results in real blockchain environments

In-Depth Evaluation

Strengths

1. Theoretical Rigor:
   • Provides complete mathematical framework with rigorous proofs
   • Establishes formal connections between game theory and reputation systems
   • Gives theoretical guarantees across multiple information scenarios
2. Methodological Innovation:
   • Non-trivial adaptation of PageRank has both theoretical and practical value
   • Definition of TRep games fills a gap in the field
   • Clever design of incentive-compatible utility functions
3. Problem Importance:
   • Addresses core trust issues in blockchain and DeFi
   • Provides theoretical foundation for Layer-2 solutions
   • Possesses broad application prospects
4. Systematic Approach:
   • Systematically decomposes complex problems
   • Provides actionable solutions
   • Tight integration of theory and application

Weaknesses

1. Insufficient Empirical Validation:
   • Lacks large-scale numerical experiments
   • Not tested in real blockchain environments
   • Practical performance of theoretical results remains unverified
2. Assumption Limitations:
   • Static reputation assumption is overly idealized
   • Perfect information assumption difficult to satisfy in practice
   • Limited analysis of adversarial behavior
3. Scalability Considerations:
   • Computational complexity analysis insufficient
   • Performance in large-scale networks unknown
   • Storage and communication overhead insufficiently discussed
4. Robustness Analysis:
   • Insufficient analysis of resistance to strategic manipulation
   • Limited consideration of security threats like Sybil attacks
   • Unclear handling of extreme cases such as network partitions

Impact

1. Academic Contribution:
   • Pioneering formal study of blockchain reputation systems
   • Provides new paradigm for game theory applications in blockchain
   • May catalyze subsequent research directions
2. Practical Value:
   • Provides theoretical foundation for PoR blockchains
   • Applicable to DeFi credit assessment
   • Offers guidance for Layer-2 solutions
3. Reproducibility:
   • Theoretical results fully reproducible
   • Algorithm descriptions clear and detailed
   • Lacks open-source implementation

Applicable Scenarios

1. Proof-of-Reputation Blockchains: As core component of consensus mechanism
2. DeFi Credit Systems: Assessing creditworthiness of lending participants
3. Layer-2 Validator Selection: Selecting trustworthy validator nodes
4. Decentralized Governance: Allocating voting weights based on reputation
5. Supply Chain Management: Assessing supplier trustworthiness

References

The paper cites 72 related references, primarily including:

• Blockchain Fundamentals: Bitcoin, Ethereum, Algorand and other major blockchain systems
• PageRank Theory: Original PageRank papers and extended applications
• Game Theory: Bayesian games, reputation theory in repeated games
• Reputation Systems: Reputation mechanism research in computer science and social science
• Layer-2 Solutions: Optimistic Rollups, payment channels and other scaling solutions

Overall Assessment: This is a theoretically rigorous and highly innovative high-quality paper that provides important theoretical foundations for blockchain reputation systems. Despite some shortcomings in empirical validation, its theoretical contributions and application prospects make it an important work in the field.