Portal de Periódicos da CAPES

An Optimal Stability Matching Algorithm for DAG Blockchain Based on Matching Theory

2021; Institution of Engineering and Technology; Volume: 30; Issue: 2 Linguagem: Inglês

10.1049/cje.2021.01.010

2075-5597

Xia Xu, Jianhua Huang, Hong Zheng, Tang Ruicong,

IoT and Edge/Fog Computing

Chinese Journal of ElectronicsVolume 30, Issue 2 p. 367-377 Original Research PaperFree Access An Optimal Stability Matching Algorithm for DAG Blockchain Based on Matching Theory Xia Xu, Corresponding Author skj865@outlook.com East China University of Science and Technology, Shanghai, 200237 ChinaSearch for more papers by this authorHuang Jianhua, Corresponding Author jhhuang@ecust.edu.cn East China University of Science and Technology, Shanghai, 200237 ChinaSearch for more papers by this authorZheng Hong, Corresponding Author zhenghong@ecust.edu.cn East China University of Science and Technology, Shanghai, 200237 ChinaSearch for more papers by this authorTang Ruicong, Corresponding Author ruicongtang@zju.edu.cn Hong Kong DAEX Blockchain Limited, Hong Kong, 999077 ChinaSearch for more papers by this author Xia Xu, Corresponding Author skj865@outlook.com East China University of Science and Technology, Shanghai, 200237 ChinaSearch for more papers by this authorHuang Jianhua, Corresponding Author jhhuang@ecust.edu.cn East China University of Science and Technology, Shanghai, 200237 ChinaSearch for more papers by this authorZheng Hong, Corresponding Author zhenghong@ecust.edu.cn East China University of Science and Technology, Shanghai, 200237 ChinaSearch for more papers by this authorTang Ruicong, Corresponding Author ruicongtang@zju.edu.cn Hong Kong DAEX Blockchain Limited, Hong Kong, 999077 ChinaSearch for more papers by this author First published: 01 March 2021 https://doi.org/10.1049/cje.2021.01.010 This work is supported by the National Science Foundation of China (No.61472139) and the Shanghai Science and Technology Commission (No.11511504403). AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinked InRedditWechat Abstract IOTA is a typical blockchain designed for IoT applications. The Markov chain monte carlo algorithm (MCMC) used in IOTA may lead to a large number of unverified blocks, which increases transaction delay to a certain extent. We propose a Stable matching algorithm (SMA) based on matching theory to stimulate nodes to verify blocks, thereby reducing the number of unverified blocks and the consensus delay. The structure of our IoT blockchain uses the Directed acyc1ic graph (DAG) to improve the transaction processing capability. The nodes in the network are abstracted as transaction issuers and transaction verifiers. A verification service scheduling system is used to assign transactions to the verifiers and achieve the optimal matching. We designed a trust evaluation mechanism which offers verifiers references and awards to check transactions. The simulation results show that SMA can significantly reduce the number of orphan blocks and improve the transaction throughput, which helps to improve the reliability of the IoT blockchain. I. Introduction The Internet of things (IoT) plays a very important role in modern life. Through information sensing devices, it connects any object to the network to realize intelligent identification, positioning, tracking, supervision and other functions. In recent years, services based on IoT have grown exponentially. It is expected that IoT will connect 30 billion devices by 2020[1]. Although IoT has greatly facilitated people's lives, IoT devices still need to identify and verify data to ensure the integrity of the transmitted data due to its spontaneity of data transmission. However, the huge number and resource constraints of IoT devices make it impossible for a centralized authentication agency to guarantee the integrity of the data in the network[2]. Blockchain has the characteristics of decentralization, non-tamperability, traceability, etc [3]. In recent years, researchers have begun to try to use blockchain technology to solve the performance bottleneck of the current IoT architecture and improve the security of IoT. Ref.[4] proposed a blockchain-based system to protect user privacy security in a smart home environment. Ref.[5] proposed a new application method for introducing blockchain into IoT, which uses smart contracts to control IoT devices to solve the synchronization and security under the C/S structure. Ref.[6] proposed a novel blockchain-based cross-domain authentication scheme to solve the obstacle to the development of services caused by unsafe and inefficient cross-domain authentication. Ref.[7] proposed a credit-based payment scheme and the corresponding optimal pricing strategy to maximize the benefits of the system and support frequent resource transactions. IoT Blockchain is a decentralized distributed ledger, meaning that the data generated by IoT devices needs to be agreed by all nodes before the data is added to the blockchain. However, the requirements of throughput, real-time response, and security in resource-constrained IoT make the consensus constrained by many factors[8]. Firstly, it is difficult to achieve network synchronization between thousands of low-bandwidth nodes in the IoT blockchain. Secondly, in the C/S structure based IoT blockchain, if a server is attacked by malicious nodes, the security of the IoT devices connected to the server cannot be guaranteed[9]. Finally, there is a contradiction between the real-time requirements of message processing in IoT environment and the consensus delay of traditional blockchains. To address the problems mentioned above, based on the DAG blockchain model, this paper introduces the matching theory into the consensus algorithm to assign transaction verifiers to transaction issuers to improve the verification efficiency of transactions. The concept of trust degree is introduced into the consensus algorithm to avoid the resource dependence of traditional consensus algorithms on IoT devices. The main contributions of this paper are as follows: 1) A DAG blockchain optimal stable matching algorithm based on matching theory is proposed to solve the contradiction between the performance limitations of IoT devices and the hardware overhead required to maintain the distributed ledger. 2) A trust evaluation scheme is introduced to conduct direct and indirect trust degree on transaction issuers to ensure the correctness of the transactions sent by issuers. 3) A consensus algorithm based on the trust evaluation is proposed for the IoT blockchain. The execution of the algorithm does not depend on the computing power of the nodes, which can meet the requirements of low-performance IoT devices participating in the consensus. The rest of the paper is organized as follows. The related work is described in Section II. Section III presents the network model. Section IV gives the consensus algorithm. Experimental results are discussed in Section V. Section VI presents the conclusion. II. Related Work 1. Consensus algorithms Consensus algorithms are the key to decentralized blockchains. They can be divided into two categories: proof-based algorithms and voting-based algorithms. The most classic proof-based algorithm is Proof of work (PoW) adopted by Bitcoin[10]. In Bitcoin, the work which a miner must do is to solve a cryptographic puzzle. Unfortunately, solving the puzzle is a very computing-hungry process that manifests in very high energy consumption. Ref.[11] proposed the Bitcoin-NG protocol to solve the problem of low throughput of Bitcoin. However, the leader election in Bitcoin-NG is PoW-based. Consequently, forks are still possible and consensus finality is not ensured. The consensus algorithms mentioned above more or less make the computing power as the proof. In order to reduce the energy consumption, several attempts have been made, such as Proof of stake (PoS) and its variants. PoS in Peercoin[12] uses each individual's equity (tokens) and uses a lucky factor to choose which miner has the right to add blocks to the blockchain, thus reducing energy consumption during mining. The creation of blocks in PoS is done by consuming the coin age. Its problem is that even if the nodes are not connected to the network, the coin age increases, and it is vulnerable to coinage accumulation attack. The other variants, such as Delegated proof of stake (DPoS), are proposed to mitigate the monopoly problem and make the system more secure by collecting votes from the member of the voting committee. Both PoW and PoS need more or less bandwidth resources and computing power. They are not suitable for resource-constrained IoTs. PBFT[13] is a typical voting based consensus algorithm which provides a solution to the Byzantine generals problem that exists in asynchronous networks. It reduces communication traffic among the nodes in order to improve the throughput. As a result, PBFT reaches practically minimal latencies allowed by the network. After PBFT, many BFT-like algorithms that further improve performance or robustness have been proposed, such as DBFT[14], HoneyBadger-BFT[15] and Tendermint[16]. In contrast to PBFT, where the client sends a new transaction directly to all nodes, the clients in Tendermint disseminate their transactions to the validating nodes using a gossip protocol. Tendermint's most significant difference from PBFT is the continuous rotation of the leader. However, there still exist some problems in BFT-based protocols. For example, when an attacker compromises some replicas inside a network and uses them as agents of a distributed Denial of service (DoS) attack, other replicas in the network have a similar risk attacked by DoS. In terms of the number of nodes, its scalability is often challenged. Therefore, the BFT-based protocols are not suitable for IoT environment. 2. DAG-based blockchains Directed acyclic graph (DAG)[17] is often used to handle dynamic programming and to find the shortest path in navigation due to its unique topology. One key characteristic of DAGs and the data processing flows that they model is that there can be multiple paths in the flow. In 2015, Zander[18] proposed a DAG-based blockchain structure that allows blocks to reference multiple predecessors. The DAG structure allows miners to create blocks concurrently, thus achieving high scalability in transaction throughput. DAGCoin was the first cryptocurrency designed by S. D. Lerner [19]. DAGCoin skips the stage of packaging block and allows each transaction to participate in transaction validation directly. In 2016, IOTA[20] was proposed by Bitcointalk. It employs DAG named Tangle to store transactions (TXs) instead of a blockchain. IOTA is a blockless distributed ledger developed to enable micropayments in IoT industry. It is believed to be suitable for asynchronous networks and solve the problems such as scalability and high TX fee in the traditional blockchain. Therefore, nodes do not need to achieve consensus on which valid TXs can be included in the ledger. However, IOTA does not have consensus finality. Hence, it is not clear yet that after how many direct or indirect approvals a TX is safe to be confirmed. In spite of all these features, IOTA still face other problems in its hash function "curl"[21]. By contrast, Byteball[22] adopts the concept of main chain/tree but uses authenticated witnessing nodes to determine the partial order of blocks at each user's view. It encourages the verification of multiple parent transaction units to form a digital signature hash network with the growth of transactions and avoid the double spend attack. However, the transaction confirmation time of Byteball is uncertain and there is the problem of insufficient expansion capacity. Compared to the chain structure blockchains, the DAG structure has two advantages. First is its speed. Any new transaction will have at least partial confirmations from peers almost instantly once released into the network, meaning no more long waits for miners to secure a new block. Secondly, DAG outperforms the chain structure in terms of scalability. DAG changes the chain structure of blockchains into a mesh topology. It can significantly improve the throughput by appending multiple blocks in parallel. III. Network Model 1. System model The DAG structure is used as our blockchain model, as shown in Fig.1. Each block in the model represents a transaction which must verify multiple previous transactions, and each edge represents a verification relationship. Compared to the chain-based blockchain, there are multiple paths that allow blocks to reference multiple predecessors in the DAG-based blockchain. The DAG structure allows blocks to be submitted to the blockchain concurrently and subsequent transactions directly verify previous historical transactions, thereby significantly increasing the throughput of blockchain network and reducing transaction latency. In the proposed structure, checkpoints are set at regular intervals to finalize transactions. In Fig.1, the white blocks indicate normal transactions sent by transaction issuers, each white block contains only one transaction, the gray blocks indicate checkpoints selected according to a fixed time length. Any route from the transactions sent after the checkpoints to the Genesis must pass through the checkpoints. The checkpoints can finally confirm previous transactions and clarify the confirmation time of a proposed transaction. However, in IOTA, each transaction must refer to the previous two transactions and its "TIPS" are constantly changing backwards. It is unclear how much time direct and indirect verification will take to confirm a transaction. In order to motivate a verifier to verify a transaction, a transaction issuer can set a certain amount of transaction fee when issuing the transaction. After verification, the verifier needs to send a transaction to refer to the approved transaction, and the transaction issued by the verifier can be transferred either to itself or to others. A single verifier can verify multiple transactions, and a single transaction can be verified by multiple verifiers. Fig. 1Open in figure viewerPowerPoint DAG-based blockchain model The parameters used in the proposed blockchain model are defined are as follows: IS(Issuer Set) : The transaction issuer set, i.e., IS = {IS1, IS2,…, ISM}. M is the total number of IS agents in the network. In this paper, member ISi of IS is also referred to as an IS agent which issues a transaction after setting a transaction fee. Transaction fee can encourage verifiers to verify the issued transaction. VS(Verifier Set) : The transaction verifier set, i.e., V S = {VS1, VS2, VS3, …, VSN}. N is the total number of V S agents in the network, member V Si of V S is also referred to as a VS agent which can verify K transactions at most. In order to obtain a transaction fee reward, a VS agent should choose previous K transactions for verification. We design a set of direct and indirect trust measures to finalize a transaction. By setting checkpoints, we can calculate the initial credibility of the transaction, and provide reference for subsequent direct and indirect trust metrics for the sender of the transaction. Assuming that there are m checkpoints, where n checkpoints can reach transaction tj by direct or indirect reference during the current checking period. The credibility of the IS agent in the current checking period is defined as Ctj = n/m. According to the method mentioned above and the historical data of transactions in the blockchain, the trusted or untrusted messages are distinguished by setting the threshold THR (0 ≤ THR ≤ 1). For credibility of transaction tj, while 0 ≤ Ct. ≤ THR, transaction tj is called the untrusted transaction {–T}; when THR ≤ Ctj. ≤ 1, transaction tj is called the credible transaction {T}. The detailed Continuous trusted transactions subsequence(CSTA) generation process is as shown in Algorithm 1. 2. Trust evaluation According to the principles of sociology, people are more convinced of the objects that are continuously credible and interact with them, and are not willing to believe those that are not credible, nor those that are unstable. For example, people are more inclined to believe in teams that win consecutively, rather than those that have failed consecutively. Therefore, we design a set of trust metrics to make direct trust metrics for transactions issued by those continuously trusted IS agents. Due to the subjectivity of direct trust evaluation and the lack of interaction between V S agents and IS agents, an indirect trust evaluation also needs to be introduced. The indirect trust value can be based on the reputation value obtained through interactions between V S agents and IS agents. Based on an indirect trust evaluation, a V S agent can get more useful information about its verification object. Algorithm 1 CTSA algorithm Input:the initial credibility sequence of transactions CS = {Ct1, Ct2,…, Ctn}, and transactions sequence TS = {t1, t2,…, tn} Output:CTS:Continuous trusted transactions subsequence While (1 ≤ i ≤ n){ if (THR ≤ Cti.≤ 1){ New vector ts; for(j=i, j 0 , ∀ r ∈ R e l . Let Li,j = {li,j,1, …, li,j,r, …, li,j,R} be the relation vector between V Si and V Sj. If li,j,1 = 1, it means that V Si and V Sj have a relationship r, otherwise li,j,1 = 0. For V Si, the indirect trust degree of ISs is based on the recommendation information which V Si collects from other V S agents. Generally, honest agents always give true feedbacks while malicious agents give false recommendations. Therefore, considering the weight of the recommendation, the trust degree of V Si on V Sj is related with the trust value and the similarity value between two V S agents in social network, which can be demonstrated by B e l i , j = v r × l i , j , r × S i m i , j max r ∈ R e l v r ( 7 ) (7) where Sim(i, j) is the similarity value between V Si and V Sj. Obviously, the closer the trust degree they measured on the same thing, the more similar they are. In this paper, the Pearson correlation (PCC) is used to measure the similarity between the given two VS agents i and j by comparing the trust degree on the transactions both agents have measured. The similarity value between V Si and V Sj is S i m i , j = ∑ s ∈ I N T i , j ( T r u last ( i , s ) - T r u i ¯ ) ( T r u last ( j , s ) - T r u j ¯ ) ∑ s ∈ I N T i , j ( T r u last ( i , s ) - T r u i ¯ ) 2 ∑ s ∈ I N T i , j ( T r u last ( j , s ) - T r u j ¯ ) 2 ( 8 ) (8) where Trulast (i, s) and Trulast (j, s) are the latest trust degree of V Si and V Sj on ISs respectively. T r u i ¯ and T r u i ¯ separately denote the average value of the trust degree that V Si and V Sj have ever rated on. INTi,j is the set of IS agents that have been verified by both V Si and V Sj. After obtaining the trust degree of a given ISs from V Sj and the trust degree of V Si on V Sj, the V Si should justify whether the ISs is trustworthy or not. If the IT(i, s) > 0.5, ISs is trustworthy, Otherwise, the ISs is not trustworthy and then the V Si should select another optimal candidate agent. The indirect trust degree of V Si on ISs can be calculated by the following equation: I T i , s = ∑ i , j ∈ V S , j ≠ i B e l ( i , j ) × D T ( j , s ) ∑ i , j ∈ V S , j ≠ i B e l ( i , j ) ( 9 ) (9) where DT(j, s) is the direct trust degree of V Sj on ISs. The total trust degree of V Si on ISs is a weighted combination of direct and indirect trust degree, which can be defined as follows: T ( i , s ) = (10) where N(i,s) is the interaction times between V Si and ISs, N(i, s) = 0 means that there is no interaction between the two agents, so the initial trust degree is 0.5. β is the weight factor, which can be obtained by β = 1 - e - N ( i , s ) 1 + e - N ( i , s ) ( 11 ) (11) Note that β ∈ (0, 1) and β increases with value of N(i, s) which is the interaction times between V Si and ISs. The more the interaction times, the greater the β and then V Si is more likely to believe the direct trust it has upon ISs. Thus, the effect of direct trust in Eq.(10) increases, which conforms to reality. IV. Consensus Process 1. System model The existing game strategies for blockchains usually aim at achieving Nash equilibrium through non-cooperative games among miners. They make miners consume energy to compete for accounting, and the throughput of the network cannot be improved. However, the computing power and bandwidth resources of IoT nodes are very limited, so the traditional non-cooperative game is not suitable for our proposed consensus model. Stable matching models are widely used in bilateral environments. For example, Ref.[23] proposed a one-to-one stable marriage matching model to find a stable match between the male and female collections. Ref.[24] introduced the matching theory for optimal resource allocation of wireless networks. Ref.[25] used the matching theory to provide a decentralized self-organizing solution for spectrum resource allocation in 5G. In this paper, the matching model is extended to the matching relationship between IS agents and V S agents, and a stable matching algorithm for IS and V S is proposed. This paper proposes a set of node trust metrics based on historical transactions issued by a IS agent. The matching between IS agents and V S agents is based on the utility of both sides, which is calculated based on the utility function derived from the trust evaluation scheme. The verification plan-aware problem for transaction verification in the blockchain can be modeled as a matching game. In order to improve the speed of transaction verification, a transaction verification scheduling system for IS agents and V S agents is proposed. In our proposed model, V S agents and IS agents interact under the assistance of the validation service scheduling system for verifying the transactions issued by IS agents, as shown in Fig.2. Fig. 2Open in figure viewerPowerPoint Validation service scheduling system IS and V S agents complete the response process of verifying reservation requests with the assistance of the scheduling system. Every V S agent chooses K (For example 1 or 2 as shown in Fig.2) transactions for verification. 2. Utility function Assume that there are M IS agents and N V S agents in the network, and let Ω be a N × M allocation matrix with element aij = {0, 1},Vi G N,j G M, aij = 1 means that ISj is assigned to V Si, and aij = 0 means that no assignment is between ISj and VSi. Meanwhile, one transaction issued by an IS agent can only be assigned to at most Kj V S agents, while V Si could offer verification opportunities to a fixed number P. Thus, we have two constrains, i.e., ∑ i = 1 N a i j ≤ K j ( 12 ) (12) ∑ j = 1 M a i j ≤ P ( 13 ) (13) To guarantee the throughput of transactions, the utility of verifying transactions issued by IS agents is considered from the following aspects. Firstly, V S agents prefer to verify the transactions issued by IS agents with high credit. Secondly, IS agents hope that the expense for transaction verification could be as few as possible. Thirdly, IS agents usually hope that the transactions they issued can be verified as soon as possible, and set the latest start verifying time tj considering their demand. Therefore, the utility function UI(i, j) that can be used to measure the utility of ISj is defined as: U I ( i , j ) = ( x j - p x j ) - C ( t j i ) ( 14 ) (14) where xj is the transaction amount and p is the fixed transaction fee for each unit price. The larger the transaction amount, the higher the transaction fee. C(·) function is a step function for measuring the cost due to delay, which is shown as C ( t j i ) = 0 , t j i ≤ t j C , t j i > t j ( 15 ) (15) If the verifying time tij is later than tj, the delay cost is a constant C, where C can be set by the IS agents to express their tolerance on the transaction validation process delay. Otherwise the delay cost is zero. We assume that IS agents are rational, which means, a i j · U I ( i , j ) > 0 , ∀ i ∈ N , j ∈ M ( 16 ) (16) For tractability, we assume that the unit transaction fee of each transaction issued by IS agents is the same, in other words, the unit transaction fee is p. In fact, rational V S agents always tend to verify the transactions with similar transaction amount it issued before. Meanwhile, we define UV (i,j) as the utility function of V Si that obtains from verifying transactions issued by ISj . Then we have U V ( i , j ) = p x j 1 + | x i ¯ - x j | ( 17 ) (17) where xi and xj are the average transaction amount issued by V Si previously and the current transaction amount issued by ISj, respectively. In our proposed model, the IS agents and V S agents can switch to each other. For higher utility, V S agents prefer highly trusted IS agents, and they also prefer the amount of transactions which are close to the average amount they issued before. Hence, the utility UV(i, j) of V Si offering verification opportunity to ISj has the following characteristic: U V ( i , j ) > U V ( i , j ' ) for T ( i , j ) > T ( i , j ' ) and | x i ¯ - x j | < | x i ¯ - x j ' | ( 18 ) (18) The objective of the system is to maximize the utilities of both IS agents and V S agents, β is a weight parameter which adjusts the impact of IS agents and V S agents. Thus, to maximize its utility as follows: max β ∑ i ∈ N ∑ j ∈ M a i j U I i , j + ( 1 - β ) ∑ j ∈ M ∑ i ∈ N a i j U I i , j ( 19 ) (19)