arXiv CSopen access

Decentralized network congestion control for DAG-based distributed ledger system

Decentralized network congestion control for DAG-based distributed ledger system

arXiv:2609.09961v1 [cs.CR] 9 Sep 2026

Mayank Pandey, Rachit Agarwal, Sandeep Kumar Shukla, Nishchal Kumar Verma IIT Kanpur, Kanpur, India {pandeym,rachitag,sandeeps,nishchal}@iitk.ac.in Abstract We propose a variable and behavior-based node-specific proof-of-work (PoW) model for a directed acyclic graph (DAG)-based distributed ledger technology (DLT) network to mitigate decentralized network congestion control. Network congestion control for centralized communication systems is an established field of study, with detailed and continuous research being done on the subject. However, attention to congestion control in decentralized networks is relatively recent and underexplored, especially with DLT, such as blockchain and DAG-based networks. For the DLT networks, the network congestion is caused by factors such as transaction spamming, an increase in the user base, and the launch of new tokens. We focus on the congestion caused by the spamming of transactions within the blockchain and DAG-based DLT network. Based on the network throughput of transactions per second and consensus procedure, the DAG-based DLT needs to control network spamming more than the blockchain network. The PoW model within the DLT consensus framework is a limited deterrent against spamming. Our model provides equal opportunities for all stakeholders regardless of their computational resources. It prevents and penalizes any node that attempts to spam or dominate the network with more than the prescribed number of transactions. Since the system nodes compete to issue transactions with finite network resources, we display the system behavior through a non-cooperative game. Further, we show that our model enforces prescribed behavior amongst the nodes through the proof of the existence of Nash equilibrium in the game.

1

Introduction

In this paper, we conceptualize and formulate a variable proof of work (PoW) model for a Directed Acyclic Graph (DAG)-based Distributed Ledger Technology (DLT) network to tackle the problem of decentralized network congestion control. Congestion control is a significant requirement for the seamless functioning of communication networks. For centralized systems, it is a well-studied area [1]. However, the congestion control for decentralized networks warrants a fresh and separate approach, especially after the advent of DLT networks. Few application-specific methods for the same exist, such as in vehicular network messaging [2]. However, broader and more in-depth work is still required to develop DLT networks’ congestion control methodologies. The DLT networks, such as blockchain, provide a new method for peer-to-peer transactions and communication with improved privacy and security [3]. However, network congestion is still possible in such systems. For example, an increase in the DLT user base leads to an increase in transaction-generating points. Additionally, a smart contract-based DLT network faces pressure when a new token gets launched due to the addition of assets and subsequent increases in the number of transactions over the network. Both aforementioned scenarios are not illicit behavior as they are part of the DLT operations. Apart from these two, the spamming of transactions by a malicious user also leads to the unnecessary hold of communication resources, causing congestion in the network. We focus on preventing transaction spamming to control congestion and ensure the seamless functioning of the DLT network. As we proceed, we look at the specific DLT features related to network traffic [4]. The functioning of a blockchain is dependent on miners or high stakeholders for transaction inclusion and confirmation through forming and adding blocks. The consensus process based on either PoW [5] or

1

proof of stake (PoS) [6] keeps essential communication to a bare minimum while verifying the transactions. The resource requirement for adding the blocks ensures that the miners or stakers are selective in terms of block formation and its broadcasting. At the individual level, the network traffic-dependent transaction fees discourage users from spamming the network and encourage them to post only relevant transactions. The miners or stakers use the transaction fees offered to decide whether to include the concerned transaction in the block. The PoW process is a limited deterrent against transaction spamming by restricting the broadcast of proposed block data. However, it also causes poor throughput compared to centralized systems. Another disadvantage is low scalability due to the competitive structure of the consensus process for including the block. It also leads to the isolation of low-resource users, such as those using IoT devices, and the discouragement of essential micro-transactions. Such shortcomings paved the way for the conception of DAG-based DLT networks. DAG based DLT offer a viable alternative to blockchain for decentralized transaction networks [7]. They have almost instantaneous transaction confirmation [8], ensuring the participation of almost all participants [9]. In a DAG-based DLT, the nodes collectively increase the speed throughput by adding their transactions and validating existing transactions. They cooperate and confirm each others’ transactions instead of competing to add their own set of transaction blocks like in blockchain [10]. Due to this, DAG-based networks are able to operate without the transaction fee requirement. Hence, throughput and scalability for the network are comparatively higher for DAG-based DLT [11]. However, the same characteristics of DAG-based DLT, which lead to scalability, also make the network vulnerable to transaction spamming by unscrupulous users and, subsequently, cause network congestion. While blockchain networks have the measures of PoW and transaction fees, DAG-based DLT lacks their equivalent of the same. It increases the individual user’s power in DAG-based DLT to add transactions. Therefore, we focus on network congestion in DAG-based DLT caused by transaction spamming. In DAG-based ledgers, a nominal PoW is required as a ”proof of verification and attachment” [12]. It differs from the blockchain’s PoW, which is the basis for competition between miners to add the block. DAG-based systems that use PoW based attachment include IOTA [13], Graphchain [14], Phantom [15], and Meshcash [16]. Originally, the objective of the nominal PoW does not include preventing transaction spamming. Therefore, theoretically, any node can attach any number of transactions to the DAG ledger. In real-time, it causes many issues. Firstly, the communication resources in the form of channel and network services are limited. A node with higher computational resources at its disposal can issue transactions at a much faster rate and spam the network, thereby restricting other users. Additionally, a group of nodes with significant resources can collude amongst themselves to get their invalid transactions, such as doublespending, verified by spamming the ledger. There is an upper limit on the available communication resources in terms of the number of transactions due to the periodic requirement of syncing the ledger. Above this limit, the network performance gets affected with users not being able to broadcast any additional transactions without delay [17]. It affects their inclusion in the ledger and sometimes invalidates the transaction itself due to the expiry of its validity [12]. Among the DAG-based DLT, the difficulty level of IOTA’s PoW process is variable and unique to the behavior of each participating node [12]. It is formulated to prevent transaction spamming only. However, its methodology is not sufficient to completely deter the users from spamming the IOTA ledger (also known as the Tangle). Besides IOTA’s PoW process for transaction attachment, there is no effective method to deter transaction spamming in DAG-based DLT networks. After observing the existing shortcomings, we proceed to provide a solution to prevent such spamming. To facilitate this, we propose a user reputation-based difficulty level model for the DAG-based DLT networks, which is also applicable to other DLT networks with modifications. We provide a detailed description of our methodology and prove its efficacy through the numerical simulations of the functioning based on a non-cooperative game. Through our proposed methodology, We achieve effective congestion control for DAG-based DLTs without compromising the overall scalability. Our contributions Our core contributions are listed below. • We propose a congestion control model for a DAG-based DLT network preventing transaction spamming by the nodes. It prescribes and establishes the ideal user behavior in terms of carrying out the 2

transactions. Our method provides every user with an equal opportunity to participate and imposes a penalty for deviating from the laid-down line of action. • We establish the efficacy of the prescribed user behavior through our model by the establishment of Nash equilibrium in a non-cooperative game with respect to the addition of transactions to the ledger. • Continuity of prescribed behavior in the event of a change in the network user composition is established through a uniform change in the Nash equilibrium. The remaining part of our manuscript is organized as follows. Section 2 provides the existing shortcomings in decentralized congestion control with the motivation for our proposed method. Section 3 describes the congestion control model for the decentralized system with a distributed DAG-based ledger. Section 4 shows the establishment of Nash equilibrium for cooperative behavior for stationary as well as dynamic sets of nodes. Section 5 demonstrates our model’s efficacy through numerical examples and the simulation. Finally, section 6 concludes our findings with a brief discussion.

2

Background and Existing shortcomings

In this section, we discuss the congestion control situation for DLT-based decentralized networks. For blockchain networks, the competition-based PoW, like in Bitcoin, acts as a deterrent against the spamming of proposed blocks. Similarly, the PoS consensus mechanism discourages spamming by enforcing block formation probability to be directly proportional to the cryptocurrency staked by the validator. In a traditional blockchain, the addition of a transaction to the ledger happens in stages. Firstly, the transaction goes into the pool of pending transactions. Then, from the pool, it is picked up by the miner or validator and added to the new block proposed for adding to the blockchain. The block reward and transaction fees on individual transactions act as incentives to carry out the whole process. The aforementioned methods and characteristics are either resource-consuming or high-stakes favoring. Nonetheless, they ensure the reluctance of blockchain users to unnecessarily clog the DLT network through spamming of transactions. In the DAG-based distributed ledger, the transactions either get added directly by the user (blockless) or after accumulation into the blocks. Instead of being a linear sequence like in blockchain, the ledger structure in DAG-based DLT is a dynamic, expanding, unidirectional graph without any loops. For block-based DAG, the decentralized network incorporates blocks instead of individual transactions in a DAG-based structure. The protocols for mining blocks are PoW-based. In Phantom [15], PoW-based mining for blocks is followed by a recursive k-clustering algorithm for their selection, which is competitive instead of cooperative. In Meshcash [16] and Spectre [18], nodes use PoW to create blocks in multiple rounds. Effectively, all blockbased DAG DLT networks use PoW as proof of attachment to prevent spamming. Also, they create different types of messages for transactions, voters, confirmation, and proposer information. For the consensus, the existing blockchain methods of transaction fees and the two-stage process of transaction pool and block formation apply to block-based DAGs. In the context of preventing transaction spamming, they are at par with the blockchain networks. Due to similarities with the blockchain process, block-based DAGs favor the users with high computational resources at their disposal. The normal nodes, such as low-resource users and IoT devices, are disadvantaged in such cases. Such disadvantages are being taken care of in blockless DAGs. Among the blockless DAG-based networks, IOTA [12] is currently the most popular with a generalized DAG-based ledger structure. There are other variants of IOTA, such as G-IOTA [19] and E-IOTA [20], with variations in the transaction verification process and attachment limit. In Graphchain [14], in addition to PoW, the transaction fees are left to collect for the users who attach their transactions to it and verify. Another type of blockless DAG structure is where the individual nodes maintain their multiple parallel chains of transactions with inter-chain connections when required, such as Hashgraph [21]. Such a structure is a restricted DAG ledger that favors high-resource nodes in forming longer chains and getting their transactions confirmed faster than others. For all the aforementioned DAG-based DLT networks, PoW is used as a deterrent against transaction spamming for congestion control. It is either nominal or adaptive. The adaptive PoW method is more responsive to transaction frequency than other networks. As we proceed, we explain how PoW works in the context of preventing transaction spamming. The congestion control model of IOTA in the form of adaptive 3

PoW difficulty level (di (t)) is given in equation (1), sourced from [12]. All the adaptive PoW methods are more or less similar in terms of formula. di (t) = d0 + ⌊γi × ai (t)⌋

(1)

Here, di (t) is assigned for the user ViN ∈ V N at time t, where V N is the set of users in the concerned DLT network. The term d0 is the base difficulty level, which is the same for all users across the network. ai (t) represents the number of transactions VN,i performed in the time period [t − m, t] for m ∈ N, while the term γi ∈ [0, 1] is associated with its reputation known as mana. Before returning to the role and significance of the aforementioned terms, we first explain the role of di (t) in the PoW-based process. In the PoW method, the user applies brute force technique to compute an output value within a prespecified range through hash function [22], where input is the transaction or block data as per the consensus requirements. The average computation time required for the same is proportional to the difficulty level. Suppose the standard output value has D number of binary digits and the difficulty level is di (t). It is used to set specific output targets, such as finding hash output with a value less than 2D−di (t) . The one given in equation (1) is IOTA’s PoW which is adaptive to the user reputation. As brute force is the only viable technique in this case, the average computational work required is proportional to 2di (t) . Therefore, if di (t) increases by 1, then the requirement gets doubled. In case of a decrease by 1, it gets halved. Hence, the average computational resource requirement Υi (t) is proportional to assigned difficulty level di (t) for the respective user ViN as shown in (2). Υi (t) ∝ 2di (t)

(2)

For the nominal PoW, we have di (t) = d0 , i.e., the difficulty level remains the same across the time for the concerned DLT network. The variable difficulty level, di (t), changes with time based on the parameters defined in the formula. Recalling from the equation (1), γi ∈ [0, 1] is associated with the term “mana”, used to represent reputation for IOTA users. The more mana a user has, the lesser the value of γi will be. The model for the pending mana and mana from [12] is given in (3). mi (t) = mi (0)e−γt + Mi (t) = Mi (0)e

αSi 1 − e−γt γ

(3)

−γt

In eq (3), the term mi (t) is the pending mana for node i at time t, while Mi (t) is the mana. Si is the amount of token node VN,i holds at time t, while α and γ are the generation and decay rate respectively. mi (t) is converted to Mi (t) when node i spends token. The reduction in mi (t) due to reduction in Si at time t gets added to Mi (t). The pending mana both generates and decays at a pre-decided rate, while the mana only decays. The mana Mi (t) is used to determine the reputation γi for node i at time t in (1) for the PoW difficulty level di (t). The equation (1) can also be used as a generalized model explaining different types of PoW methods. For instance, in Bitcoin, the variables in the term ⌊γi × ai (t)⌋ can represent the average time period between the addition of two successive blocks, based on PoW model given in [23]. The higher-than-intended time gap leads to a decrease in di (t), while the lower time gap increases it. The state-of-the-art PoW methods, as per the equation (1), favor the users having high resources based on the consensus process, whether the computational resource or cryptocurrency stake in the concerned network. The more the throughput in terms of transactions per second (TPS) is, the more the concerned DLT network is vulnerable to transaction spamming. Our objective is to create a congestion control method through the difficulty level, which controls spamming without either the support of variable transaction fees or any compromise on the network throughput capacity. Also, we aim to provide the methodology that is viable for all the PoW-based DLT networks, whether nominal or competitive. As we proceed, we describe in detail our proposed methodology followed by its validation in terms of fairness of transaction issuing opportunity.

4

Figure 1: Representation of GN and GL

3

Proposed congestion control method

To present the model, let us assume a dynamic decentralized system operating a distributed DAG-based DLT network represented as G(T ). For simplicity, we represent G(T ) as G with all its parameters being described for the time instance T . The system G is a combination of two dynamic graphs, GN and GL . Here, GN is the graph of connected participating nodes, while GL is the graph of the distributed ledger. GN is a bidirectional graph represented as GN = (V N , E N , AN ). Here, V N represents the decentralized network users as a set of nodes given by V N = {V1N , V2N , · · · , VnN }, numbered in the order of their joining the system. Let the cardinality of the set V N be given as n. It is a variable term as the users are free to join and leave the concerned DLT network. The expression E N ⊂ V N × V N represents the set of edges representing the communication channel between nodes. Further, AN is the n×n adjacency matrix depicting the information on connecting unidirectional edges, with the elements of matrix aN i,j ∈ {0, 1} depicting information of connection between nodes. On the other hand, GL has a DAG-shaped structure. It represents the distributed ledger of transactions defined as GL = (V L , E L , AL ). GL is dynamic and expands rapidly with time as new transactions are made. Here the set of nodes V L represents the transactions, given by V L = {V1L , V2L , · · · , VlL }, numbered in the order of their arrival or addition to the graph. Let the cardinality of the set V L be given as l, which is incremental as the new transactions continuously get added to the concerned ledger. The set of edges E L ⊂ V L × V L are unidirectional and always directed from the nodes added later towards the nodes added earlier. The l × l adjacency matrix AL stores the information on transaction attachment such that the elements of matrix aL i,j ∈ {0, 1}. The elements in V N create, issue, and add the transactions into the ledger GL . The users in V N are connected in a decentralized network, and each user has the information on the state of GL . The state of GL is updated continuously by the addition of new transactions by users in V N . Every transaction in V L is connected to at least two previously added transactions though edges belonging to E L . A depiction of a DAG-based DLT network is given in the figure 1. In GL , the transactions at the end which are not yet verified are referred to as ”tips”. Therefore, the procedure of selecting the existing transactions for verification and attachment is called the tip selection process. Before proceeding further, we would like to declare that we will use the terms ViN and i interchangeably, based on the requirement in representation. The functioning of our proposed method is explained through the conditions regarding the state of G given below. 1. The parameters n and l are time-variant terms, with the rate of change of l much higher than that of 5

n. 2. Initially, we proceed with the assumption that dn dt = 0, i.e., the number of users in the DLT system does not change. 3. Afterwards, we also test our method with dn dt ̸= 0 with the condition of existing users leaving the network and new users joining. 4. Each element of V L (transactions) stores some information, such as involved user addresses, amounts, and metadata. 5. Each element of E L (connecting edges between transactions) has unity weight. 6. A node in V N adds at least a predecided number of edges (2 in our case) in E L while adding a single node in V L . In the DLT network, the nodes in V N can add the transactions into GL up to a given limit during a particular time period due to real-time limits on communication resources [24]. This limit is represented through transactions per second (TPS), which is the average capacity of the concerned DLT network. Let the limit be represented as Λ number of transactions for a given time period of T seconds, with the average capacity being TΛ TPS. Each user in V N , after creating a transaction, selects a pre-decided number of the existing transactions in the GL to verify and attach its transaction to them. These existing transactions are referred to as tips. We keep the required number of tips at 2 as it is an acceptable number in most existing DAG-based DLT networks. After selection, the PoW is created according to the assigned difficulty level and attaches its transaction to the selected tips after their verification. Then it broadcasts the complete transaction state. There is a realistic possibility that a single or a group of malicious nodes with high computational resources would try to dominate the ledger by adding only their own transactions into GL by quickly solving the nominal PoW. The distributed ledger-based decentralized networks design their consensus protocol to mitigate such phenomenon. Let T1 , T2 , · · · T∞ be the successive discrete time instances with non-uniform periods between them. The structure of a transaction in V L is given in eq(4), where Ty , Tz < Tx . L L VxL (Tx ) = {VyL (Ty ), VzL (Tz ), DxL , Ex,y , Ex,z , νx }

(4)

Suppose a user ViN attaches a transaction VxL (Tx ) into GL , with Tx . The term DxL contains the data of the transaction VxL which contains the information such as which user issued the transaction, what is the value transferred and other system-specific information. The transactions VyL (Ty ) and VzL (Tz ) are the existing L L respectively. The term νx is and Ex,z transactions in GL to which VxL (Tx ) is attached through the edges Ex,y L the nonce value of transaction Vx (Tx ). It is computed and used in a similar way to the Bitcoin blockchain network. The nonce value νx is the proof of work (PoW) and the proof of attachment of a transaction into the DAG ledger. We aim to incur the minimum possible cost in terms of computational and communication resources with the penalty for crossing the limit. Therefore, we propose the user reputation-based difficulty level model for the decentralized network with a distributed DAG-based ledger. We present our methodology in a discrete-time frame with a uniform period. Let the time instances be represented as {0, T, 2T, · · · , (C −1)T, CT, · · · } with time period of T , where C ∈ N. Our method defines the user-specific difficulty level for the PoW required for transaction attachment based on the concerned user’s reputation. We define the reputation alloted for the user ViN for the time period [CT, (C + 1)T ] as RiN (CT ). It is generated based on the spending of tokens between the duration [(C − 1)T, CT ]. RiN (CT ) has two components; one is related to the value of spent tokens through their transactions, and the other is related to the number of transactions issued, both during the time period T . Here tokens refer to the cryptocurrency of the concerned DLT network. The values mentioned above are computed at regular intervals and remain fixed for a time period of T . We assume that the time synchronization across the nodes is uniform, i.e., Universal coordinated time [25]. The overall reputation model is given in (5), with the two components fiB (CT ) and fiw (wi (CT )) further defined. RiN (CT ) = F (fiB (CT ), fiw (wi (CT ))) 6

(5)

The component fiB (CT ) has the range of [0, 1], and it represents the relative value in terms of tokens transferred by ViN between the instance [(C −1)T, CT ], with respect to the total number of tokens transferred during that period. If ViN does not transfer any tokens during [(C −1)T, CT ], then fiB (CT ) = 1. On the other hand, if ViN is responsible for all the token transfers in the network during [(C − 1)T, CT ], then fiB (CT ) = 0. The model for formulating the value of fiB (CT ) is given in (6). Here, BiN (CT ) is the token balance of ViN at instance CT , while ∆B N (CT ) is the total token amount in the “sent” for all the transactions in the network during the duration [(C − 1)T, CT ]. The objective for fiB (CT ) is to reward the spending, but up to a certain limit. ( 1 if∆B N (CT ) = 0 B fi (CT ) = (6) max{0,BiN ((C−1)T )−BiN (CT )} 1− if∆B N (CT ) > 0 ∆B N (CT ) To encourage active participation, but discourage spamming beyond a certain point, the suitable function for the reputation fiw must be diminishing in structure represented via (8). Here, wi (CT ) is the number of transactions added by ViN to GL during the period [(C − 1)T, CT ]. The network capacity is divided among the users as in (7). Λ = nKcross + Kadd (7) Here, Kcross ∈ N is defined as the average transaction capacity of each user for n users in the system. Kadd << Kcross is the residual system capacity. Based on Kcross , we choose the value of the terms K0 , K1 and K2 to form a quadratic equation. The values are chosen such that one solution is Kcross , while the other is a random negative integer. The negative value gets discarded as the number of transactions cannot be negative. The transaction frequency-based reputation equation and Kcross as the only viable solution is given in (8). fiw (wi (CT )) = K0 + K1 wi (CT ) − K2 wi2 (CT ) p (8) K1 + K12 + 4K2 K0 Kcross = 2K2 L L The total number of transactions P added to V ∈ G between [(C − 1)T, CT ] is represented as W (CT ) = L L V (CT ) − V ((C − 1)T ) = i∈V N wi (CT ). In order for the decentralized network to work properly, the condition given is W (CT ) ≤ Λ. In theoretical terms, each node can unilaterally use the whole network resources for itself, i.e., wi (CT )max = Λ. We formulate the PoW difficulty level based on the reputation components fiB (CT ) and fiw (wi (CT )) to prevent spamming and network congestion. The proposed difficulty level equation for the node ViN for the period [CT, (C + 1)T ] based on the transaction frequency in the period [(C − 1)T, CT ] is given in (9).  w  dfi (wi (CT )) di (CT ) =d0 − dwi (CT ) (9) B w + ⌈fi (CT ) × (− min{0, fi (wi (CT )))}⌉

The term d0 is the base difficulty level. The derivative component is used for linear increment till wi (CT ) ≤ Kcross , while the third term is for quadratic increment when wi (CT ) > Kcross . For the transaction frequency wi (CT ) in the period [(C − 1)T, CT ], the node VN,i has to add transactions with PoW difficulty level di (CT ) for the entire period of [CT, (C + 1)T ]. From (9), the objective of ViN is to utilize minimum individual computational resources. The node has to find the balance between the transaction frequency wi (CT ) and the subsequently allotted difficulty level di (CT ). Meanwhile, the total number of transaction limit in a period T are restricted to Λ due to physical infrastructure and synchronization requirement of the network. The scenario is ideal to be represented as a non-cooperative game with a Nash equilibrium. Therefore, first we explain the system with the cases of the stationary and dynamic number of nodes and then we find the optimal solution using the designed non-cooperative game. Both fiB (CT ) and (−min(0, fiw (wi (CT )))) are ≥ 0. From (6), the condition for fiB (CT ) to become zero is given as BiN ((C − 1)T ) − BiN (CT ) = ∆B N (CT ). The condition is highly unlikely as it means only user ViN sent the tokens during the period [(C − 1)T, CT ]. This is highly unlikely to happen in a large decentralized network with multiple nodes. Therefore, we move to the term (−min(0, fiw (wi (CT )))) for its df w (wi (CT )) dfiw (wi (CT )) minimizing conditions. We solve for the term −⌊ idwt (CT becomes ) ⌋. From (8), the expression dwt (CT ) as

dfiw (wi (CT )) = K1 − 2K2 wi (CT ). The difficulty level di (CT ) values for varying ranges of wi (CT ) is listed dwt (CT )

7

) in appendix A. Our objective is to find the minimum value for the term wdii(CT (CT ) for 0 ≤ wi (CT ) ≤ Λ. On observing the values obtained for di (CT ) for the given range of wi (CT ), the local minima occurs at wi (CT ) = Kcross . We prove this condition as the ideal scenario for the concerned DLT network through non-cooperative game formulation, described in the upcoming section. As explained above, the system assigns a difficulty level for the period [CT, (C + 1)T ] after obtaining the transaction frequency input in the period [(C − 1)T, CT ] . Based on the observations, it is in the interest of a rational node ViN to keep wi (CT ) ≤ Kcross in order to optimize the combination of difficulty level vs. transaction frequency. From equation (2), we know that the increase or decrease in the difficulty level by 1 unit leads to the doubling or halving of the average resource requirement, respectively. For the total network capacity Λ, the optimal solution must be to utilize maximum capacity as well as provide a fair chance to each node. For wi (CT ) = Kcross , we have d0 − ⌊(K1 − 2K2 Kcross )⌋ = dcross . Then cross (CT ) ∝ 2dcross . the average resource requirement is represented as ΥK i cross −1 If wi (CT ) = Kcross − 1, then the subsequent resource requirement is represented as ΥK (CT ) ∝ i 2dcross −⌊2K2 ⌋ . On the other hand, for wi (CT ) = Kcross + 1, the subsequent difficulty level for the period [CT, (C + 1)T ]
B 2 cross +1 is given as ΥK (CT ) ∝ 2dcross × 2⌈fi (CT )×(−K0 −K1 (Kcross +1)+K2 (Kcross +1) ⌉ . i Based on the above observations, we represent the ratio of resource requirement for following and not following the prescribed behavior as given in equation (10). 2

cross ΥiKcross +1 (CT ) ≈ 2Kcross × ΥK (CT ) i

(10)

From equation (10), it is evident that there is considerably heavier burden of the computational resources for the period [CT, (C + 1)T ] if the ViN has wi (CT ) > Kcross by even 1. It prompts a rational node to keep within the prescribed limit to avoid a disproportionate burden on its computational resources for successive time periods. As we proceed, we discuss the case of reputation with a dynamic set of nodes.

3.1

Joining and leaving of nodes

Until now, we explored the scenario where the number of nodes is fixed, i.e., n is a constant value. We computed the PoW difficulty level allocation for the nodes for the period [CT, (C +1)T ] based on transactions done in the period [(C − 1)T, CT ]. N For the situation where a new node Vn+1 joins the network at a time instance falling in a particular time period, the reputation parameters get adjusted in the subsequent time period. For a generalized scenario, we assume that with the joining of the new node, the network capacity changes, i.e., either increases or decreases [24]. Suppose the new node joins during the time period [(C − 1)T, CT ]. In such a case, our methodology will allow the new node to start issuing transactions from the time period [CT, (C + 1)T ]. For the variable node case, we represent the network capacity without the new user as Λ(C−1)T for the period [(C − 1)T, CT ]. When the network capacity and the number of users change, the average network capacity also changes. The system defined values K0 , K1 and K2 update accordingly to the new capacity ΛCT starting from the period [CT, (C + 1)T . Let the system defined parameter values be represented as (C−1)T (C−1)T (C−1)T , K1 and K2 for the period [(C − 1)T, CT ]. The transaction frequency-based reputation K0 for the variable node set for the period [(C − 1)T, CT ] is represented via equation (11). A similar form of change follows if a node leaves the network. (C−1)T

fiw (wi (CT )) = K0

(C−1)T

+ K1

wi (CT )

(C−1)T 2 − K2 wi (CT )

(11)

With the change in the number of users and network capacity, the average network capacity, i.e., Kcross changes. For our purpose, let the number of users in the network before and after the change during the period [(C − 1)T, CT ] be n1 and n2 , respectively. In (12), we obtain the average network capacity for the (C−1)T (C−1)T period [(C − 1)T, CT ], where Kcross is the average capacity and Kadd is the residual capacity. (C−1)T

(C−1)T Λ(C−1)T = n1 Kcross + Kadd

8

(12)

For the time period starting [CT, (C + 1)T ] and onward, the average network capacity and, subsequently, reputation value parameters get updated according to n2 users. The updated network capacity and the average capacity are represented in (13) with the variables having the same meaning as in (12) for the updated time period. We provide a generalized scenario of the effect of change in user number coming from the period [CT, (C + 1)T ]. CT CT ΛCT = n2 Kcross + Kadd

(13)

The difficulty level model for the fixed set given in (9) will operate in the same way for the variable node set but with varying network parameters. Once we have the difficulty level model for Pow and adding transactions, we proceed to show that by following the proposed model and prescribed limits, the maximum possible transactions get added with the minimum possible total computational resource. We demonstrate the formulation of a non-cooperative game based on the variation of node reputation and prescribed limits in the difficulty level model. Subsequently, we establish the prominence of prescribed behavior through the establishment of Nash equilibrium in a non-cooperative game for both fixed and variable node sets.

4

Optimal Resource consumption via non-cooperative games

The scenario in the previous section for n users operating in a decentralized network is similar to a noncooperative game. The reasons behind the similarity are that there is no communication between the users regarding their respective strategies, i.e., no user tells others how many transactions it is planning to issue and add during a time period. The physical resource constraints put a limit on the total number of transactions that can be added to the ledger within a time period without causing a backlog. Also, there is no binding agreement between the users to limit their transactions. We demonstrate the efficient utilization of the network through the prescribed behavior by showing the process in the form of a non-cooperative game. As we proceed, we show that the only way to maximize the possible utilization of network resources with minimum possible computational resources is at a uniform Nash equilibrium.

4.1

Nash equilibrium for a fixed set of nodes

We define the non-cooperative game for the consideration in (14), whose payoff applies in the period [CT, (C+ 1)T ] based on the strategy carried out in the period [(C − 1)T, CT ]. Γ ≜ {V N , (wi (CT ))i∈V N , (Θi )i∈V N }

(14)

For the given game, we have the set of nodes V N = {V1N , V2N , · · · , VnN } as a set of players. The system dynamics for the game are given in equations (6), (7), (8), and (9). For ViN ∈ V N , wi (CT ) is the strategy of issuing the number of transactions in the period [(C − 1)T, CT ]. The payoff of the strategy applied in [(C − 1)T, CT ] for ViN is Θi , which gets allotted in the period [CT, (C + 1)T ]. The overall objective for the game in (14) is to utilize the full available network capacity in the current period as well as have optimal resource consumption for the subsequent period. The strategy vector for the system for the period [(C − 1)T, CT ] is given by w(CT ) ≜ [w1 (CT ), w2 (CT ), · · · , wn (CT )]T . We design the payoff function function Θi for ViN by combining the components Ui and Uav . For the component Ui in (15), the variable is wi (CT ). Ui = ζ1 wi (CT ) − ζ2 wi2 (CT ) Also, the component based on the average strategy of the network Uav is being given in (16). X  wi (CT ) + · · · 2 X wi (CT ) − ζ2 Uav = ζ1 n n N

(15)

(16)

i∈VN

i∈V

The general form of the utility function Θi ∈ ℜ is given below, where κ1 , κ2 > 0 are weightage parameters. Θi = κ1 Ui + κ2 Uav 9

(17)

The above equation can be derived into the quadratic payoff form similar to given in [26], [27]. We represent the payoff as given in (18). Θi = η1 wi (CT ) + η2 wi2 (CT ) + η3

j̸=i X

wj (CT )

j∈V N

+η4

j̸=i X

wj2 (CT ) + η5

j∈V N

j̸=i X

(18)

wi (CT )wj (CT )

i,j∈V N

  The value of the constants are given as η1 = κ1 ζ1 + κ2nζ1 , η2 = − κ1 ζ2 + κn2 2ζ2 , η3 = κ2nζ1 , η4 = − κn2 2ζ2 , and η5 = − 2κn22ζ2 . The payoff function is also given as Θi (wi (CT ), w−i (CT )), where w−i (CT ) is the strategy vector of {VjN }, ∀j ∈ V N , and j ̸= i. The condition for a strategy vector w∗ (CT ) to be the Nash equilibrium strategy ∀ ViN ∈ V N applied in the period [(C − 1)T, CT ] is given in (19). ∗ ∗ Θi (wi∗ (CT ), w−i (CT )) ≥ Θi (wi (CT ), w−i (CT ))

(19)

We define the condition for Nash equilibrium for the payoff function through the result given in Lemma 4.1. Lemma 4.1. For the non-cooperative game defined in (14) with a bounded strategy set and fixed number ζ1 = Kcross , then the strategy wi (CT ) = Kcross is the Nash of users for a DAG-based DLT network, if 2ζ 2 equilibrium ∀ViN ∈ V N . Proof. The detailed proof of the Lemma is given in Appendix B. Also, for the condition described in Lemma 4.1, the Nash equilibrium does not depend on the value κR , provided κ2 ̸= 0. Detailed proof of the same is given in the form of corollary 1 in Appendix B. From Lemma 4.1, we concur that the best scenario to utilize maximum network potential with minimum total computational resources across the system is when every node ∈ V N issue Kcross transactions in a time period T . If a node attempts to cross the given limit and cut another node’s share of transactions, he gets penalized in the subsequent period. The penalty is a disproportionately higher difficulty level as per (9). Therefore, it is in the best interest of every node to add transactions less than or equal to Kcross . Now, as we move forward, we discuss the case of the system with a dynamic set of nodes.

4.2

Nash equilibrium for variable node set

The equilibrium condition proved in Lemma 4.1 is based on the fixed number of players in the game. However, for the given decentralized system, any new node can join at any point. We prove that the requirement of model-prescribed behavior does not change. As we proceed, we will demonstrate the consistency of the requirement of prescribed behavior through the proof of uniform shift of the Nash equilibrium. The non-cooperative game for shift in the average capacity ΓCT (C−1)T in a variable node set is defined (N,(C−1)T ) in (20), where V is the effective set of players in the period [(C − 1)T, CT ] with |V (N,(C−1)T ) | = n1 , (N,CT ) while V is the effective user set for the period [CT, (C + 1)T ] with |V (N,CT ) | = n2 . The change from n1 to n2 occurs in the period [(C − 1)T, CT ], but comes to effect from the period [CT, (C + 1)T ]. The system dynamics for the updated game are defined in (11), (12) and (13); in addition to the ones for the game defined in (14) with the fixed set of players. The change in user set leads to the shift in average capacity in the period [CT, (C + 1)T ]. The difficulty level allotment is based on the node strategies with an updated set applied in the period [(C + 1)T, (C + 2)T ]. Therefore, the Nash equilibrium gets updated for the period [CT, (C + 1)T ]. (N,(C−1)T ) ΓCT , V (N,CT ) , (wi (CT ))i∈V (N,(C−1)T ) , (C−1)T ≜{V (wi ((C + 1)T ))i∈V (N,CT ) ,

(20)

(C−1)T (Θi )i∈V (N,(C−1)T ) , (ΘCT i )i∈V (N,CT ) }

For the given game, the set of players in successive periods, as well as the payoffs of successive periods, are the primary elements. We assess the shift in the Nash equilibrium through the result in Lemma 4.2. 10

Lemma 4.2. The shift in the Nash equilibrium for the game defined in (20), when the number of users change from n1 to n2 during the period [(C−1)T, CT ] will be equal to (C−1)T

ζ1 ((C−1)T ) = Kcross and 2ζ 2 ((C−1)T )

ζ1 (CT ) ζ1 (CT ) ζ1 ((C−1)T ) CT 2ζ2 (CT ) − 2ζ2 ((C−1)T ) , where 2ζ2 (CT ) = Kcross

.

Proof. Detailed proof of the Lemma is given in Appendix C. From Lemma 4.2, we concur that in the instance of change in the user set, the shift in the Nash equilibrium is uniform across the system. No particular node gets an advantage in terms of preferred transaction limit due to an increase or decrease in the cardinality of the user set. Therefore, our proposed PoW difficulty level model ensures the continuity of the enforcement of prescribed behavior for a dynamic set of nodes. As we proceed, we explain how our model works through a set of solved examples.

5

Numerical Examples

In this section, we demonstrate the efficacy of our model through numerical examples along with the analysis of the IOTA’s model. Note that the network in question is decentralized, so there is no administrative authority to regulate the flow or restrict the offenders. Example 1 (Analysis of IOTA congestion control model) In the IOTA’s model given in (1), the range for γi is obtained through either of the two ways, normalization or relativity. Either way, this parameter assigns a node ViN to have the γi in the range [0, 1]. As high as the node spending is in the preceding time period, the lower its value will be, i.e., closer to 0. For comparison, suppose we have two users ViN , VjN ∈ V N as part of the network. Suppose the previous spending of ViN enables it to have γi = 0.1, while the same for VjN is γj = 0.7. Now, if the number of transactions for i and j be ai (t) = aj (t) = 10, then we have the respective difficulty levels as di (t) = d0 + 1 and dj (t) = d0 + 7. The increment in di (t) by a factor of 1 leads to a doubling of the average computational efforts required. Due to the above results, ViN is able to put through its transactions almost instantly because of negligible change in assigned difficulty level. On the other hand, it becomes computationally very expensive for VjN to push its transactions instantaneously. In the above case, VjN has to wait for some time so that the value dj (t) comes down to a reasonable level for it. Therefore, the linearly increasing difficulty level provides respite to high stakeholders but discriminates against the users with low resources and spending power. Example 2 N Suppose we have a network of 10 users with the set given as V N = {V1N , · · · , V10 }. At present, we are proceeding with the assumption that neither a new node joins nor an existing node leaves. The time period for updating the reputation and level is T = 10 seconds. Suppose the network capacity is 100 transactions per second, leading to the values Λ = 1000 transactions, Kcross = 100, and Kadd = 0 for the period T . Also, let the current period be [4T, 5T ]. We form the transaction frequency-based reputation component fiw (wi (5T )) for the node ViN ∈ V N by taking Kcross with an invalid transaction value −20 shown in (21).

fiw (wi (5T )) = 1 + 0.04wi (5T ) − 0.0005wi2 (5T )

(21)

The figure 2 demonstrates the variation of fiw (wi (5T )) for different Λ values for 10 node system. We choose to proceed with the scenario of Λ = 1000 for the reputation model fiw (wi (5T )) in (21). The value of Ktan = 40. For 0 < wi (5T ) ≤ 100, the difficulty level assigned for the period [5T, 6T ] is represented in (22) by di (5T ) = d0 − ⌊(K1 − 2K2 wi (CT ))⌋ di (5T ) = d0 − ⌊(0.04 − 0.001wi (5T ))⌋

(22)

For wi (5T ) ≤ 40, di (5T ) = d0 . For 40 < wi (5T ) ≤ 100, di (5T ) = d0 + 1. For wi (5T ) > 100, the difficulty level is given in (23). di (5T ) = d0 + 1 + ⌈fiB (5T ) × (−1 − 0.04wi (CT ) + 0.0005wi2 (CT ))⌉ 11

(23)

Figure 2: Variation of transaction frequency based reputation

Figure 3: Variation of difficulty level with transaction frequency For wi (5T ) = 150, the difficulty level is given in (24). di (5T ) = d0 + 1 + ⌈fiB (5T ) × 4.25⌉

(24)

For fiB (5T ) = 0.2, the above expression will be equal to d0 + 2. It means that ViN has to do 80% of token spending during the period [4T, 5T ] for given level. Now, we have 10 users in the network, so the normal spending ratio is expected to be 10%. For this ratio, we have fiB (5T ) = 0.9 and subsequently di (5T ) = d0 + 1 + 4 = d0 + 5. For wi (5T ) = 125, the user ViN has to do 90% of the spending during the period [4T, 5T ] to keep the difficulty level at di (5T ) = d0 + 2. For 10% spending, di (5T ) = d0 + 3. The analysis above showing the variation of difficulty level with a transaction-based reputation for different proportions of spending is plotted in figure 3 for the base level d0 = 2. Example 3 To show the efficacy of prescribed behavior, we consider a system with 2 users ViN , VjN ∈ V N in the network with network capacity Λ = 210, we have Kcross = 100 and Kadd = 10. The time period for the difficulty level allotment is [4T, 5T ] based on transaction frequency in the period [3T, 4T ]. From Lemma 4.1 and corollary 1, we know that the values κ1 , κ2 ∈ ℜ+ do not have effect on the outcome. So we let the share of outcome for ζ1 = 100, let ζ1 = 100 and ζ2 = 0.5. the individual and average strategy be equal, i.e., κ1 = κ2 = 0.5. For 2ζ 2 N The payoff function Θi for Vi with the calculated parameter values is given in (25). In figure 4, the variation

12

Figure 4: Variation of ViN payoff (Θi )

Figure 5: Best response functions of ViN and VjN of Θi for different values of wi (4T ) and wj (4T ) is provided on a 3D plane with peak value of 5000. Θi = 75wi (4T ) − 0.3125wi2 (4T ) + 25wj (4T ) −0.0625wj2 (4T ) − 0.125wi (4T )wj (4T )

(25)

A similar payoff function can also be computed for VjN . From the payoff function, we derive the best response function for ViN as given in (26). Similar payoff and best response functions can also be computed for VjN . The existence of Nash equilibrium is demonstrated in figure 5, obtained at the point of intersection. bi (wj (4T )) = 120 − 0.2wj (4T )

(26)

From the best response functions, the Nash equilibrium is found to be 100, i.e., equal to Kcross . Example 4 After showing the efficacy of prescribed behavior through the establishment of Nash equilibrium, we proceed to show that the change in the set of nodes does not lead to any deviation. For 2 users ViN , VjN ∈ V (N,4T ) 4T in the network with network capacity Λ4T = 210 and n1 = 2, we have Kcross = 100 for the period [3T, 4T ]. ζ1 (4T ) Subsequently, 2ζ2 (4T ) = 100 can be taken as ζ1 (4T ) = 100 and ζ2 (4T ) = 0.5. When a new user VkN joins the system between this period, the user set now becomes ViN , VjN , VkN ∈ V (N,5T ) with n2 = 3 effective from 5T the period [4T, 5T ]. Suppose the updated network capacity is Λ5T = 250. The updated Kcross will be 80. ζ1 (5T ) Subsequently, 2ζ2 (5T ) = 80 can be written as ζ1 (5T ) = 80 and ζ2 (5T ) = 0.5. For κ1 = κ2 = 0.5, the payoff function Θ4T for ViN will be same as given in (25). i 13

Figure 6: Updated payoff of ViN for n2 = 3 node system

Figure 7: Best response functions for n1 = 2 and n2 = 3 node systems The updated payoff function Θ5T for n2 = 3 is given in (27). The distribution of the same is given in i figure 6. The distribution increases towards the higher end between the range of 70 − 90. To find out the new Nash equilibrium with the shift, we derive and plot the updated best response functions for the set V (N,4T ) and V (N,5T ) . 160 2.5 2 Θ5T wi (5T ) − w (5T ) i = 3 9 i 40 0.25 2 (27) + (wj (5T ) + wk (5T )) − (wj (5T ) + wk2 (5T )) 3 9 0.5 − (wi (5T )wj (5T ) + wj (5T )wk (5T ) + wk (5T )wi (5T )) 9 Now, we obtain the best response function for ViN ∈ V (N,5T ) as shown in (28). By extension the same for 5T VjN and VkN are b5T i (w−i (5T )) = 96 − 0.1(wj (5T ) + wk (5T )) and bk (w−k (5T )) = 96 − 0.1(wi (5T ) + wj (5T )) respectively. The plots for the best response functions with n1 = 2 and n2 = 3 are given in figure 7. b5T i (w−i (5T )) = 96 − 0.1(wj (5T ) + wk (5T ))

(28)

The unique solution for the set V (N,5T ) is wi (5T ) = wi (5T ) = wk (5T ) = 80, which the nash equilibrium for the given period. Therefore the shift in the nash equilibrium for the period [4T, 5T ] from the period [3T, 4T ] is |100 − 80| = 20. 14

6

Conclusion

In this paper, we formulate a variable PoW model based on user behavior for a DAG-based distributed ledger network. It serves as the proof of attachment for a transaction into the DAG ledger. Our motive is to provide a solution to enable decentralized congestion control for DLT networks. For DLT networks, spamming of transactions by an unscrupulous individual or a group of users is the main cause of network congestion. While it is restricted in blockchain networks through different sets of measures, spamming is a potential problem in DAG-based DLT networks. Hence, we move forward with the PoW methodology for the DAG DLT. The proposed method is a variable computational cost-based PoW difficulty level. We define the difficulty level for a time period based on the reputation built on transaction frequency and token spending in the previous period. It arranges for every user to have equal opportunities in terms of issuing transactions and establishes a prescribed transaction limit. For users violating the prescribed transaction limits, the model penalizes disproportionately by quadratic increase in the difficulty level value instead of linear. It prompts the nodes to stay within the prescribed limit when adding transactions into DLT. To show the efficacy of cooperative addition of transactions, we formulate the node behavior through a noncooperative game with a payoff based on the transaction frequency strategy. In the game, we establish the existence of a unique pure Nash equilibrium. When every node operates at Nash equilibrium, it utilizes the full potential of the available transaction limit with the minimum possible average computational resource. The model also works for a dynamic set of nodes, where the requirement of a uniform prescribed behavior remains the same. Overall, our proposed PoW difficulty level model is better for a DAG-based distributed ledger than one with a static or linearly increasing difficulty level.

Acknowledgement This work is partially funded by the National Blockchain Project (grant number NCSC/CS/2017518) at IIT Kanpur, sponsored by the National Cyber Security Coordinator’s office of the Government of India, the C3i Center funding from the Science and Engineering Research Board of the Government of India (grant number SERB/CS/2016466), and NSCS (National Security Council Secretariat).

References [1] S. H. Low, F. Paganini, J. C. Doyle, Internet congestion control, IEEE control systems magazine 22 (1) (2002) 28–43. [2] A. Balador, E. Cinque, M. Pratesi, F. Valentini, C. Bai, A. A. Gómez, M. Mohammadi, Survey on decentralized congestion control methods for vehicular communication, Vehicular Communications (2021) 100394. [3] A. Dorri, M. Steger, S. S. Kanhere, R. Jurdak, Blockchain: A distributed solution to automotive security and privacy, IEEE Communications Magazine 55 (12) (2017) 119–125. [4] X. Li, P. Jiang, T. Chen, X. Luo, Q. Wen, A survey on the security of blockchain systems, Future Generation Computer Systems 107 (2020) 841–853. doi:https://doi.org/10.1016/j.future.2017.08.020. URL https://www.sciencedirect.com/science/article/pii/S0167739X17318332 [5] D. Fullmer, A. S. Morse, Analysis of difficulty control in bitcoin and proof-of-work blockchains, in: 2018 IEEE Conference on Decision and Control (CDC), IEEE, 2018, pp. 5988–5992. [6] F. Saleh, Blockchain without waste: Proof-of-stake, The Review of financial studies 34 (3) (2021) 1156– 1190. [7] F. M. Benčić, I. P. Žarko, Distributed ledger technology: Blockchain compared to directed acyclic graph, in: 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), IEEE, 2018, pp. 1569–1570.

15

[8] H. Pervez, M. Muneeb, M. U. Irfan, I. U. Haq, A comparative analysis of dag-based blockchain architectures, in: 2018 12th International conference on open source systems and technologies (ICOSST), IEEE, 2018, pp. 27–34. [9] A. Reyna, C. Martı́n, J. Chen, E. Soler, M. Dı́az, On blockchain and its integration with iot. challenges and opportunities, Future generation computer systems 88 (2018) 173–190. [10] I. Kotilevets, I. Ivanova, I. Romanov, S. Magomedov, V. Nikonov, S. Pavelev, Implementation of directed acyclic graph in blockchain network to improve security and speed of transactions, IFAC-PapersOnLine 51 (30) (2018) 693–696. [11] H. Y. Wu, X. Yang, C. Yue, H.-Y. Paik, S. S. Kanhere, Chain or dag? underlying data structures, architectures, topologies and consensus in distributed ledger technology: A review, taxonomy and research issues, Journal of Systems Architecture 131 (2022) 102720. doi:https://doi.org/10.1016/j.sysarc.2022.102720. URL https://www.sciencedirect.com/science/article/pii/S1383762122002077 [12] S. Popov, H. Moog, D. Camargo, A. Capossele, V. Dimitrov, A. Gal, A. Greve, B. Kusmierz, S. Mueller, A. Penzkofer, et al., The coordicide, Accessed Jan (2020) 1–30. [13] W. F. Silvano, R. Marcelino, Iota tangle: A cryptocurrency to communicate internet-of-things data, Future Generation Computer Systems 112 (2020) 307–319. [14] X. Boyen, C. Carr, T. Haines, Graphchain: a blockchain-free scalable decentralised ledger, in: Proceedings of the 2nd ACM Workshop on Blockchains, Cryptocurrencies, and Contracts, 2018, pp. 21–33. [15] G. Srivastava, A. D. Dwivedi, R. Singh, Phantom protocol as the new crypto-democracy, in: IFIP International Conference on Computer Information Systems and Industrial Management, Springer, 2018, pp. 499–509. [16] I. Bentov, P. Hubáček, T. Moran, A. Nadler, Tortoise and hares consensus: the meshcash framework for incentive-compatible, scalable cryptocurrencies, in: International Symposium on Cyber Security Cryptography and Machine Learning, Springer, 2021, pp. 114–127. [17] X. Yang, G. de Veciana, Performance of peer-to-peer networks: Service capacity and role of resource sharing policies, Performance Evaluation 63 (3) (2006) 175–194, p2P Computing Systems. doi:https://doi.org/10.1016/j.peva.2005.01.005. URL https://www.sciencedirect.com/science/article/pii/S0166531605000143 [18] Y. Sompolinsky, Y. Lewenberg, A. Zohar, Spectre: A fast and scalable cryptocurrency protocol, Cryptology ePrint Archive, Paper 2016/1159, https://eprint.iacr.org/2016/1159 (2016). URL https://eprint.iacr.org/2016/1159 [19] G. Bu, O. Gurcan, M. Potop-Butucaru, G-iota: Fair and confidence aware tangle, in: IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2019, pp. 644–649. doi:10.1109/INFCOMW.2019.8845163. [20] G. Bu, W. Hana, M. Potop-Butucaru, E-iota: an efficient and fast metamorphism for iota, in: 2020 2nd Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS), 2020, pp. 9–16. doi:10.1109/BRAINS49436.2020.9223294. [21] L. Baird, Hashgraph consensus: fair, fast, byzantine fault tolerance, Swirlds Tech Report, Tech. Rep. (2016). [22] B. Preneel, Cryptographic hash functions, European Transactions on Telecommunications 5 (4) (1994) 431–448. [23] S. Nakamoto, Bitcoin whitepaper, URL: https://bitcoin. org/bitcoin. pdf-(: 17.07. 2019) 9 (2008) 15.

16

[24] X. Jin, Y.-K. Kwok, Network aware peer-to-peer media streaming: Capacity or proximity?, Computer Networks 69 (2014) 1–18. doi:https://doi.org/10.1016/j.comnet.2014.04.004. URL https://www.sciencedirect.com/science/article/pii/S1389128614001492 [25] G. Panfilo, F. Arias, The coordinated universal time (utc), Metrologia 56 (4) (2019) 042001. [26] P. Frihauf, M. Krstic, T. Basar, Nash equilibrium seeking in noncooperative games, IEEE Transactions on Automatic Control 57 (5) (2011) 1192–1207. [27] T. Dokka, H. Moulin, I. Ray, S. SenGupta, Equilibrium design in an n-player quadratic game, Review of Economic Design (2022) 1–20. [28] J. B. Rosen, Existence and uniqueness of equilibrium points for concave n-person games, Econometrica 33 (3) (1965) 520–534. URL http://www.jstor.org/stable/1911749 [29] D. M. Mandy, Leading principal minors and semidefiniteness, Economic Inquiry 56 (2) (2018) 1396–1398. [30] C. R. Johnson, R. A. Horn, Matrix analysis, Cambridge university press Cambridge, 1985. [31] E. K. Chong, S. H. Zak, An introduction to optimization, John Wiley & Sons, 2004. [32] D. Fudenberg, J. Tirole, Game Theory, MIT Press, Cambridge, MA, 1991. [33] G. Owen, Game theory, Emerald Group Publishing, 2013. [34] V. S. Varma, Y. Hayel, I.-C. Morărescu, A non-cooperative resource utilization game between two competing malware, IEEE Control Systems Letters 7 (2023) 67–72. doi:10.1109/LCSYS.2022.3186620.

A

Values of di (CT ) for different values of wi (CT ) df w (w (CT ))

i = K1 , while • The minimum value of wi (CT ) at any instance is zero. At wi (CT ) = 0, idwt (CT ) w fi (wi (CT )) = K0 . Therefore from eq(9), at wi (CT ) = 0, di (CT ) = d0 − ⌊K1 ⌋ is the minimum value of the difficulty level.

K1 , • As the number of messages increases, the value of di (CT ) increases. At wi (CT ) = 2K 2 At this point, di (CT ) = d0 .

dfiw (wi (CT )) = 0. dwt (CT )

• Afterwards, till wi (CT ) < Kcross , di (CT ) = d0 + ⌊2K2 wi (CT ) − K1 ⌋. K1 • Let 2K = Ktan . For wi (CT ) ≤ ⌊Ktan ⌋, the difficulty level will be given as di (CT ) = d0 − 2

j

dfiw (wi (CT )) dwt (CT )

k

= d0 − ⌊(K1 − 2K2 wi (CT ))⌋, where (K1 − 2K2 wi (CT )) > 0. • At wi (CT ) = ⌊Ktan ⌋, the difficulty level will become equal to the base level, i.e., d0 , represented as di (CT ) = d0 . • For ⌊Ktan ⌋ < wi (CT ) ≤ Kcross , the differential term will cause the addition to the base j level d0 as k (K1 − 2K2 wi (CT )) < 0. However, the representation will remain same, i.e., di (CT ) = d0 −

dfiw (wi (CT )) dwt (CT )

.

• For wi (CT ) > Kcross , where the jtransaction kcrosses the average suggested limit, the difficulty level   dfiw (wi (CT )) equation changes to di (CT ) = d0 − + fiB (CT ) × (−min(0, fiw (wi (CT )))) , also elaborated dwt (CT ) as equation (A.1).

w (CT )>Kcross

di i

(CT ) = d0 − ⌊(K1 − 2K2 wi (CT ))⌋+

⌈fiB (CT ) × (−K0 − K1 wi (CT ) + K2 wi2 (CT ))⌉ 17

(A.1)

B

Proof of Lemma 4.1

Lemma IV.1. For the non-cooperative game defined in (14) with a bounded strategy set and fixed number ζ1 = Kcross , then the strategy wi (CT ) = Kcross is the Nash of users for a DAG-based DLT network, if 2ζ 2 N N equilibrium ∀Vi ∈ V . Proof. A non-cooperative game has at least one pure strategy Nash equilibrium if its strategy set is compact and convex, and the payoff function is strictly concave and continuous in the strategy set for every user in the network [28]. Now, the strategy set for our defined game is given as wi (CT ) = [0, Λ]. Since the given strategy set is closed and bounded, it is compact. The convexity of any set Si depends on the condition in (B.1) being satisfied, for any Si1 , Si2 ∈ Si and for any θ ∈ [0, 1]. 0 ≤ θSi1 + (1 − θ)Si2 ≤ Λ

(B.1)

The set Si ∈ ℜ satisfies the above condition. Hence, it is convex ∀i ∈ V N . Using the payoff function Θi , we derive the Hessian matrix for the game. Further, we check whether the Hessian matrix is negative definite ∀s ∈ S or not. Here, S is the strategy space for the whole network. The Hessian matrix Hs is given in (B.2). For our case, Si = S, i.e. each node has identical strategy space. 

′′

Θ12 ′′ Θ22 .. .

Θn1

Θn2

′′

′′

′′

Θ11  Θ′′  21 Hs =  .  ..

′′

··· ··· .. .

′′  Θ1n ′′ Θ2n   ..  . 

···

Θnn

(B.2)

′′

2

′′

′′

Θi , ∀i, j ∈ VN . Now we compute the values of Θij to check the conditions. For Θij , Here Θij = ∂wi (CT∂ )∂w j (CT ) i first we compute ∂w∂Θ . j (CT )

i̸=j

X ∂Θi = η3 + 2η4 wj (CT ) + η5 wi ∂wj (CT ) N

(B.3)

i∈V

′′

Now, to find Θij for i ̸= j, we partially differentiate (B.3) by wi (CT ) as given in (B.4). ∂ 2 Θi κ2 ζ2 = η5 = −2 2 ∂wi (CT )∂wj (CT ) n

(B.4)

∂ 2 Θi κ2 ζ2 = 2η2 = −(2κ1 ζ2 + 2 2 ) ∂ 2 wi (CT ) n

(B.5)

′′

Θij = ′′

Similarly, we find Θii as given in (B.5). ′′

Θii =

To verify whether the Hessian matrix H(s) is negative definite or not, we check for its principal minors [29]. The condition for a matrix to be negative definite is that even order and odd order principal minors be positive and negative, respectively, based on Sylvester’s criteria in the context of real and symmetric matri′′ ′′ ces [30], [31]. Based on values obtained for Θii and Θij in H(s) ∀ i, j ∈ V N , we safely conclude that the given matrix is negative definite. Now, if the Hessian matrix is negative definite, then the respective payoff function is strictly concave and continuous [28]. Therefore, with establishing a compact and convex strategy set and the concave and continuous payoff function, the non-cooperative game defined in equation (14) has at least one Nash equilibrium. Now, we find the uniqueness of Nash equilibrium using the best response function [32]. We obtain the Nash equilibrium through proof by induction for the best response functions of each user. To start, let us have the case where we have 2 users, ViN and VjN in the network, i.e., n = 2. The utility (18) for ViN with

18

the substitution ζ1 = 2ζ2 Kcross is represented in (B.6). Θi = (2κ1 ζ2 Kcross + κ2 ζ2 Kcross )wi (CT ) κ2 ζ2 2 − (κ1 ζ2 + )wi (CT ) + κ2 ζ2 Kcross wj (CT ) 4 κ2 ζ2 κ 2 ζ2 2 wj (CT ) − wi (CT )wj (CT ) − 4 2

(B.6)

Let the ratio of the share of payoff be given as κκ12 = κR . For such a case, the payoff becomes as in (B.7). 1 Θi = κ2 ζ2 ((2κR Kcross + Kcross )wi (CT ) − (κR + )wi2 (CT ) 4 1 1 + Kcross wj (CT ) − wj2 (CT ) − wi (CT )wj (CT )) 4 2

(B.7)

To obtain the best response function, we compute the derivative of ViN ’s utility with respect to wi (CT ) and equate it to 0 [33]. ∂Θi = 2κR Kcross + Kcross ∂wi (CT ) (B.8) 1 1 − (2κR + )wi (CT ) − wj (CT ) = 0 2 2 The best response function for ViN is given as below. bi (wj (CT )) =

4κR Kcross + 2Kcross 1 − wj (CT ) 4κR + 1 4κR + 1

(B.9)

Similarly, for VjN , we obtain the best response function as (B.10). bj (wi (CT )) =

4κR Kcross + 2Kcross 1 − wi (CT ) 4κR + 1 4κR + 1

(B.10)

The Nash equilibrium for the best response equations (B.9) and (B.10) is the pair {wi∗ (CT ), wj∗ (CT )} such that wj∗ (CT ) = bj (wi∗ (CT )) and wi∗ (CT ) = bi (wj∗ (CT )) [34]. On solving, we obtain that the only solution for such a condition is wi∗ (CT ) = wj∗ (CT ) = Kcross . For generalized proof through induction, we assume that the Nash equilibrium is Kcross for n users in the system. Now, we proceed to obtain the Nash equilibrium for the system with n + 1 users. For the n users with V N = {V1N , · · · , VnN }, the payoff for ViN with the substitution ζ1 = 2ζ2 Kcross and κ1 = κR κ2 is given in (B.11). 2Kcross Θi = κ2 ζ2 ((2κR Kcross + )wi (CT ) n j̸=i 1 2Kcross X wj (CT ) − (κR + 2 )wi2 (CT ) + n n (B.11) N j∈V

j̸=i 1 X 2 2 − 2 wj (CT ) − 2 n n N j∈V

X

wi (CT )wj (CT ))

i,j∈[1,n]

The best response function for ViN is obtained by partial differentiation as given in (B.12). ∂Θi 2Kcross =(2κR Kcross + ) ∂wi (CT ) n − 2(κR +

j̸=i 1 2 X )w (CT ) − wj (CT )) = 0 i n2 n2 j∈[1,n]

19

(B.12)

bi (w−i (CT )) =

n2 κR Kcross + nKcross n2 κR + 1 j̸=i X 1 wj (CT ) − 2 n κR + 1

(B.13)

j∈[1,n]

For the Nash equilibrium, the solution for the above is bi (w−i (CT )) = wj (CT ) = Kcross , ∀j ∈ [1, n] − {i}. Now, we consider the scenario for n + 1 users with the same system conditions. The best response function for wi (CT ) in such case is given in (B.14). ((n + 1)2 κR + 1)bi (w−i (CT )) = (n + 1)2 κR Kcross + (n + 1)Kcross −

j̸=i X

(B.14)

wj (CT )

j∈[1,n+1]

Expanding (B.14), we get (B.15). (n2 κR + 1 + 2nκR + κR )bi (w−i (CT )) = n2 κR Kcross + nKcross + κR Kcross + 2nκR Kcross + Kcross −

j̸=i X

(B.15) wj (CT ) − wn+1 (CT )

j∈[1,n]

Using (B.13), we reduce (B.15) to (B.16). bi (w−i (CT )) = Kcross +

Kcross − wn+1 (CT ) 2nκR + κR

(B.16)

Similarly, the best response function for wn+1 (CT ) in terms of wi (CT ) is derived as in (B.17). bn+1 (w−(n+1) (CT )) = Kcross +

Kcross − wi (CT ) 2nκR + κR

(B.17)

Based on the best response functions given in (B.16) and (B.17), we form a similar set for all users in the ∗ ∗ system. For the aforementioned equations, the unique solution {w1∗ , · · · , wn+1 }, such that wi∗ = bi (w−i (CT )) ∀i ∈ [1, n + 1] is Kcross . Therefore, the value Kcross is the Nash equilibrium for the given scenario. Corollary 1. For the system described in Lemma 4.1, the nash equilibrium does not depend on the value κR , provided κ2 ̸= 0 Proof. In (B.16) and (B.17), we clearly see that wi (CT ) = wn+1 (CT ) = Kcross for the Nash equilibrium solution. The term κR in the denominator has no effect on the outcome as the numerator is equal to 0, while n > 0.

C

Proof of Lemma 4.2

Lemma IV.2. The shift in the Nash equilibrium for the game defined in (20), when the number of users change from n1 to n2 during the period [(C−1)T, CT ] will be equal to (C−1)T

ζ1 ((C−1)T ) CT Kcross and 2ζ = Kcross 2 ((C−1)T )

ζ1 (CT ) ζ1 ((C−1)T ) ζ1 (CT ) 2ζ2 (CT ) − 2ζ2 ((C−1)T ) , where 2ζ2 (CT ) =

.

Proof. Through the proof of Lemma 4.1, we deduce that for two users ViN , VjN ∈ V (N,(C−1)T ) , the Nash (C−1)T

equilibrium is Kcross

(C−1)T

ζ1 ((C−1)T ) in the period [(C − 1)T, CT ], with 2ζ = Kcross 2 ((C−1)T )

function for the user set V

(N,(C−1)T )

is given in (C.1). We proceed with the scenario of n1 = 2 and n2 = 3.

(C−1)T

(Θi

. The variable payoff

(C−1)T

)i∈V (N,(C−1)T ) = κ1 Ui 20

(C−1)T + κ2 Uav

(C.1)

For n1 = 2 in V (N,(C−1)T ) , the derived utility function is written in (C.2), where Θi ((C − 1)T ) is the payoff obtained from the strategy wi (CT ). (C−1)T )

(Θi

)i∈V (N,(C−1)T ) = η1 ((C − 1)T )wi ((C − 1)T )+

η2 ((C − 1)T )wi2 ((C − 1)T ) + η3 ((C − 1)T )

j̸=i X

wj ((C − 1)T )

j∈VN

+ η4 ((C − 1)T )

j̸=i X

(C.2) wj2 ((C − 1)T )

j∈V N

+ η5 ((C − 1)T )

X

wi ((C − 1)T )wj ((C − 1)T )

i,j∈V N

Now, suppose during [(C − 1)T, CT ], a new node VkN joins and starts issuing transactions from the period [CT, (C + 1)T ]. The user set now becomes V (N,CT ) = {ViN , VjN , VkN }. In such case, the network capacity CT and subsequently average capacity changes, let it be Kcross . The utility function also changes accordingly (C−1)T CT from (Θi )i∈V (N,(C−1)T ) to (Θi )i∈V (N,CT ) . The game parameters are then written in the following form for the period [CT, (C + 1)T ] with n2 users, with the values derived based on constant values of ) ) , η2 (CT ) = −(κ1 ζ2 (CT ) + κ2 ζ2n(CT ), static node set game. The values are η1 (CT ) = κ1 ζ1 (CT ) + κ2 ζ1n(CT 2 2 2

) ) , η4 (CT ) = − κ2 ζ2n(CT , and η5 (CT ) = − 2κ2 ζn22(CT ) . η3 (CT ) = κ2 ζ1n(CT 2 2 2

2

When the user set becomes V (N,CT ) , the utility function ΘCT for ViN for the period [CT, (C + 1)T ] will i be same as in (C.2) with updated constant values for n2 nodes. To assess the shift in the Nash equilibrium, first, we take the scenario of two users ViN and VjN in the network during the period [(C − 1)T, CT ]. From corollary 1, we know that the values of κR have no effect. Therefore, we take κ1 = κ2 = κ for the sake of simplicity. The best response function for ViN for the same period is derived as (C.3). (C−1)T

∂Θi (C−1)T = κζ2 ((C − 1)T )(3Kcross ∂wi ((C − 1)T ) 1 5 − wi ((C − 1)T ) − wj ((C − 1)T )) = 0 2 2

(C.3)

(C−1)T

From the proof of Lemma 4.1, we ascertain the Nash equilibrium for the period [(C −1)T, CT ] to be Kcross for n1 = 2. CT Now, we carry out the partial differentiation of ΘCT with the user set VN as shown below. i ∂ΘCT i = η1 (CT ) + 2η2 (CT )wi (CT ) ∂wi (CT ) +η5 (CT )(wj (CT ) + wk (CT ))

(C.4)

Assuming the equal share of individual and average strategy payoff, we take κ1 = κ2 = κ. Substituting the ζ1 (CT ) CT = Kcross , we deduce the below expression. value of weight parameters with the condition 2ζ 2 (CT ) ∂ΘCT κζ1 (CT ) i = κζ1 (CT ) + ∂wi (CT ) 3 κζ2 (CT ) − 2(κζ2 (CT ) + )wi (CT ) 9 2κζ2 (CT ) − (wj (CT ) + wk (CT )) 9 8K CT 20 2 = κζ2 (CT )( cross − wi (CT ) − (wj (CT ) + wk (CT ))) 3 9 9

(C.5)

Putting the partially differentiated equation equal to zero, we obtain the best response function of ViN with respect to strategies of VjN and VkN in (C.6). In a similar way, we can write the best response functions of 21

VjN and VkN with respect to the remaining two users’ strategies. CT bCT i (w−i (CT )) = 1.2Kcross − 0.1(wj (CT ) + wk (CT ))

(C.6)

CT Solving the best response functions, the strategy wi (CT ) = wj (CT ) = wk (CT ) = Kcross is found to be the (C−1)T CT new Nash equilibrium for the network. Therefore, the shift in the Nash equilibrium, i.e., |Kcross − Kcross | ζ1 ((C−1)T ) ζ1 (CT ) will be equal to | 2ζ2 (CT ) − 2ζ2 ((C−1)T ) |. If n1 = 3 and n2 = 2, i.e., a user leaves the system, the shift in the (C−1)T

CT Nash equilibrium will be |Kcross − Kcross | in a similar way. If we talk in generalized terms, the best response function for ViN is derived based on the observations from the lemma 4.1. For ViN ∈ V (N,(C−1)T ) with |V (N,(C−1)T ) | = n1 for the period [(C − 1)T, CT ], the best response function is given in (C.7). (C−1)T

(C−1)T

bi

−

(w−i ((C − 1)T )) =

1 ( n21 + 1

j̸=i X

n21 Kcross

(C−1)T

+ n1 Kcross 2 n1 + 1

(C.7)

wj ((C − 1)T ))

j∈V (N,(C−1)T )

We obtain the unique solution from the above set of equations, which is ∀ViN ∈ V (N,(C−1)T ) , wi ((C − 1)T ) = (C−1)T Kcross . Similarly, for ViN ∈ V (N,CT ) with |V (N,CT ) | = n2 for the period [CT, (C + 1)T ], the best response function based on Lemma 4.1 is given in (C.8). bCT i (w−i (CT )) =

CT CT n22 Kcross + n2 Kcross 2 n2 + 1

1 ( − 2 n2 + 1

j̸=i X

(C.8) wj (CT ))

j∈V (N,CT )

In a similar way as in the case of n1 users, we obtain the unique solution for the set of n2 users, which is CT ∀ViN ∈ V (N,CT ) , wi (CT ) = Kcross . From the set (C.7) and (C.8), the Nash equilibrium points for the user sets V (N,(C−1)T ) and V (N,CT ) are (C−1)T CT respectively. Based on the assumptions related to the parameters, the shift in the Nash Kcross and Kcross (C−1)T ζ1 (CT ) ζ1 ((C−1)T ) CT equilibrium, i.e., |Kcross − Kcross | will be equal to 2ζ − 2ζ . 2 (CT ) 2 ((C−1)T )

22