Source-linked AI summary
Equilibria in the Tangle
Serguei Popov, Olivia Saa, Paulo Finardi
TL;DR
The paper asks whether participants who minimize their own costs can be incentivized to cooperate in the Tangle, a DAG-based system motivated by IOTA. It proves equilibrium existence results and simulates selfish attachment strategies, finding that they typically remain similar to the default despite a node-gain advantage in an extreme scenario.
Problem
The paper asks whether participants who minimize their own costs but use the network legitimately can be incentivized to cooperate rather than choose different attachment behavior.
Source: §1 · pp. 3–4Method
The paper proves existence of Nash equilibria for the Tangle game and numerically studies selfish attachment strategies against the default strategy.
Source: §3.2 · pp. 16–17, §5 · p. 31Results
Simulations find selfish strategies outperform non-selfish ones, with a 25% node-gain difference in the most extreme scenario, while selfish players typically choose strategies similar to default.
Source: §1 · p. 4, §5 · p. 31Takeaways & Limitations
In the studied simulations, selfish players typically choose attachment strategies similar to the default, indicating cooperation with the network rather than simply using it.
Source: §1 · p. 4The paper studies equilibria for a given cost tied to confirmation probability within a chosen time interval, and that probability depends heavily on the interval.
Source: §5 · p. 31
Abstract
from arXiv · showhide
We analyse the Tangle --- a DAG-valued stochastic process where new vertices get attached to the graph at Poissonian times, and the attachment's locations are chosen by means of random walks on that graph. These new vertices, also thought of as "transactions", are issued by many players (which are the nodes of the network), independently. The main application of this model is that it is used as a base for the IOTA cryptocurrency system (www.iota.org). We prove existence of "almost symmetric" Nash equilibria for the system where a part of players tries to optimize their attachment strategies. Then, we also present simulations that show that the "selfish" players will nevertheless cooperate with the network by choosing attachment strategies that are similar to the "recommended" one.
1 Introduction
The paper models the Tangle as a growing DAG whose transactions attach using random walks, motivated by its use in IOTA. It asks whether cost-minimizing participants can be incentivized to cooperate, and studies that question through Nash equilibria and simulations.
1 Introduction
- The Tangle models a growing transaction DAG in which new vertices arrive at Poissonian times and use random walks to choose attachment locations.The walks model network propagation delays.Source: §1 · p. 2
- IOTA uses a DAG ledger, in contrast to blockchain’s sequence of blocks; the paper motivates DAGs as a way to avoid throughput bottlenecks and transaction fees.The introduction also identifies consensus on valid blocks as difficult when blocks arrive frequently.Source: §1 · p. 2
- Network delays make it impractical to require transactions to approve only tips, while repeatedly approving old transactions could leave new transactions unapproved and halt the network.The paper frames reciprocal approval as an incentive problem: participants want others to help them, but may not care about helping others.Source: §1 · p. 3
- The paper asks whether cost-minimizing participants can choose behavior different from the default while still being incentivized to cooperate with the network.It proves existence of almost-symmetric Nash equilibria and reports that simulations typically show selfish players choosing strategies similar to the default.Source: §1 · p. 4
2 Description of the model
The Tangle is a growing rooted DAG whose transactions arrive over time and attach to earlier vertices. Its tip-selection walks model attachment under network delays, while the paper discusses confirmation, reissuance, and strategy trade-offs.
2 Description of the model
- The model’s states are finite rooted DAGs with a genesis vertex, two outgoing edges per non-genesis vertex, and every vertex connected by a directed path to genesis.Edge multiplicity is at most two.Source: §2 · p. 5
- Transactions arrive according to a Poisson process and add vertices that each approve two earlier vertices, while the graph grows without deleting vertices or edges.The two selected vertices may coincide.Source: §2 · p. 6
2.1 On attaching a new transaction to the Tangle
- The recommended tip-selection algorithm runs independent walks from genesis on the delayed tangle and stops each at a tip; their transitions use backtracking probability q and cumulative-weight-based preferences.The walk uses an exponential weighting function in the paper’s main case, and q < 1/2 ensures it reaches a tip almost surely.Source: §2.1 · pp. 7–8
- Tip-only approval is recommended but cannot be imposed by the protocol; larger α favors attack defense, whereas smaller α makes confirmation times more stable.The paper also describes a mixed-α strategy combining walks with different α values.Source: §2.1 · pp. 7, 12
- The authors give a heuristic, not a rigorous proof, for eventual approval behavior, and note that orphaning arguments require care because the relevant events are dependent.A transaction unconfirmed after K time units is called orphaned and may be reattached.Source: §2.1 · pp. 9–11
- p^-1λK is the average number of unconfirmed transactions under the stable-regime reissue model.Here p is the probability of confirmation K time units after first issuance.Source: §2.1 · pp. 11–12
3 Selfish nodes and Nash equilibria
This section establishes Nash-equilibrium existence under finite-memory and Markov-chain assumptions, and examines equilibrium costs and attachment strategies when many nodes act selfishly. It also defines computationally constrained strategies and a confirmation-based cost, proves cost-similarity and averaged-strategy properties, and gives an approximate unilateral-deviation bound while illustrating why greedy tip selection will not work.
3.1 Some further assumptions and definitions
- Selfish nodes seek to improve transaction confirmation time, while practical strategy spaces are restricted to methods using the last n1 transactions.The cost averages how often subsequent default tip-selection walks fail to reference a node’s transaction across M0 later transactions.Source: §3 · p. 12, §3.1 · pp. 14–15
3.2 Main results
- Under Assumptions L and D, the system has at least one Nash equilibrium.Assumption D requires the finite-state Markov chain to be irreducible and aperiodic; the paper notes a small perturbation can ensure this property.Source: §3.2 · p. 16
- For sufficiently large N, costs at any Nash equilibrium differ by less than ε across all selfish nodes.The threshold N0 depends on the default attachment strategy.Source: §3.2 · p. 16
- For sufficiently large N, any Nash equilibrium can be replaced by a common averaged strategy forming an ε-equilibrium, with equal costs across selfish nodes.The result supports using simulations with a single selfish strategy for large-player systems.Source: §3.2 · p. 17
3.3 Proofs
- The existence proof establishes continuity of the strategy-dependent stationary measure and cost, then applies Kakutani’s fixed-point theorem.Continuity follows from a finite irreducible, aperiodic Markov-chain argument; the proof models the selfish nodes’ aggregate strategy by their average.Source: §3.3 · pp. 17, 19
- The cost-similarity proof argues that a highest-cost node could adopt a lowest-cost node’s strategy, with its effect on other costs small when N is large.If the equilibrium costs remained far apart, that deviation would contradict the Nash condition.Source: §3.3 · pp. 19–20
- An external observer cannot distinguish N nodes using strategies (S1, . . . , SN) from one node using their averaged strategy.The proof identifies this equivalence as the immediate second part of Theorem 3.5.Source: §3.3 · p. 22
- For any fixed ε′ > 0, the symmetric profile’s cost is at most a unilateral deviator’s cost plus ε′ for all sufficiently large N.The proof gives C(1)(S, . . . , S) ≤ C(1)(˜S, S, . . . , S) + ε′.Source: §3.3 · p. 22
- Figure 4 illustrates why the “greedy” tip-selection strategy will not work.The figure marks the two “best” tips with larger circles.Source: Figure 4 · p. 23
4 Simulations
Simulations examine whether selfish attachment choices can harm the network, and show that equilibrium behavior remains close to the default strategy in the studied setting. In the one-dimensional game, the equilibrium depends on the cost curves and the fraction using the greedy strategy.
4 Simulations
- Simulations indicate selfish players choose strategies not much different from the default attachment strategy in the studied situation.The analysis assumes selfish nodes use a common strategy, as permitted by Theorem 3.5.Source: §4 · p. 23, §4.1 · p. 25
- Crowding around the two tips with the best exit probabilities can reduce selfish transactions’ chances of prompt approval.The simulations use the tip-selecting random walk and allow reattachment under stated criteria, with a procedure to prevent double spending.Source: §4 · pp. 23–24
- About 95% of transactions are approved before 5 seconds, so average costs are measured over roughly 10 seconds to include nearly all approvals.The simulations use M0 = 500 for λ = 50 and M0 = 250 for λ = 25.Source: §4 · p. 24, Figure 5 · p. 25
4.1 One dimensional Nash equilibria
- For the two-strategy game, equilibrium candidates occur where average costs match or where all selfish nodes choose the lower-cost strategy.A curve intersection is not sufficient: deviations to either side must increase costs for it to be an equilibrium.Source: §4.1 · p. 26
- For higher λh, the equilibrium uses a smaller proportion of transactions under S1, consistent with stronger overcrowding at higher arrival rates.In the mixed-strategy game, when γ ≤ ¯p, S1 has lower average cost than S0 and equilibrium occurs at θ0 = 1.Source: §4 · pp. 23–24, §4.1 · p. 27
- At α = 0.5, the S0 and S1 average costs do not meet at reasonable fractions, yet their absolute gains remain low.The equilibrium in this case is θ = 1.Source: §4.1 · p. 28, Figure 8 · p. 29
- The relative cost increase for S0 users from S1 transactions is below 25% even at larger simulated fractions, and can be negative.At low α, some S0 transactions share overcrowded tips while others face less competition; on average, honest-node costs can decrease.Source: §4.1 · p. 28, Figure 9 · p. 29
5 Conclusions and future work
The paper proves that almost-symmetric Nash equilibria exist and numerically locates them for a simple strategy and parameter range. Simulations find that selfish strategies can outperform non-selfish ones, while the conclusions remain bounded by the modeled settings and costs.
5 Conclusions and future work
- The paper proves existence of almost-symmetric Nash equilibria and numerically locates them for a simple space strategy over some parameter range.Source: §5 · p. 31
- 25% higher node gains in the most extreme scenario, but even when almost half of transactions came from selfish nodes, non-selfish players were not meaningfully harmed.The selfish strategy also has higher computational costs and requires monitoring tangle parameters.Source: §5 · p. 31
- The simulated results depend strongly on α, and the study evaluates only one cost tied to confirmation probability over a chosen time interval.Other time intervals with different practical meanings remain to be analyzed.Source: §5 · p. 31
- Quantitative and analytic study of multidimensional equilibria remains limited to a narrow range of α and p values.Further work also aims to optimize default tip selection to minimize costs imposed by selfish strategies.Source: §5 · p. 31
- The analysis covers selfish players who seek their own costs while using the network legitimately, not malicious players attempting disruption.The authors defer attacks against the network to subsequent work.Source: §5 · pp. 31–32