# A Partitioned DAG Distributed Ledger with Local Consistency for Vehicular Reputation Management

Authors: Naipeng Li; Yuchun Guo; Yishuai Chen; Jinchuan Chai
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Vehicular reputation maintenance with distributed ledger is aimed at establishing trust among vehicles randomly meeting in a Vehicular Ad-hoc Network (VANET). It is, however, challenging in VANET, as congested areas in road networks, brought by traffic tides or accidents, challenge the ledger performance. Meanwhile, the reputation update is highly dependent on transaction consensus of the distributed ledger. To solve the problem, this paper proposes deploying directed acyclic graph- (DAG-) based distributed ledgers on vehicles, which use the vehicular distribution to adapt the unpredictable reputation update. Specifically, we first propose a partitioned DAG-based distributed ledger to manage vehicular reputation in partitioned VANET. Secondly, we introduce a novel reputation evaluation method to encourage vehicles to contribute to VANET interaction and ledger consensus maintenance, which can remedy the topology churn of the ledger network due to the mobility of VANET. Finally, we design a reputation update method based on the consistency of transactions in the partition to facilitate trust establishment. Experimental results on a real-world dataset show that the proposed ledger and reputation update method is effective and feasible in the large-scale dynamic VANET.


---

## Body

## 1. Introduction

With the rapid evolution of Vehicular Ad-hoc Networks (VANETs) and intelligent technology, intelligent vehicles have further demands for exchanging information with surrounding smart objects like other intelligent vehicles, smart traffic lights, and Road Side Units (RSUs) [1, 2]. However, the unique features of VANETs, such as high mobility and volatility, make the antiattack and privacy protection become major concerns [17]. Establishing the trust for received information or connectable nodes needs a vehicular reputation management system. Recently, due to providing privacy protection and decentralized trust among unfamiliar vehicles [17], employing Distributed Ledger Technologies (DLTs), such as blockchain, for vehicular reputation management has become a hot research topic [1, 4, 6, 9].Nevertheless, a vehicular reputation management system with distributed ledger also faces two challenges. The first challenge is ledger maintenance. To maintain the consistency of the transaction, the distributed ledger needs consensus mechanisms like Proof of Work (PoW) [7] or Proof of Stake (PoS) [8] in the blockchain ledger. However, it is challenging for the VANET node to satisfy the requirements of consensus mechanisms, e.g., computing power and stable communication route [6]. The second challenge is trust establishment. Evaluating the other’s reputation is an excellent way to establish trust for an interaction. A node can evaluate reputation for one time when the interaction begins rather than assessing the context of each exchanging message. However, the VANET, a decentralized network, challenges the reputation update.Existing studies for vehicular reputation management are mainly based on the blockchain platform [6, 20]. There are two kinds of nodes in a blockchain platform, the full node and the simplified node. The former keeps the entire blockchain ledger and composes the backbone blockchain network. The latter only creates and consumes transactions that store reputation ratings on others or some nodes’ historical behaviors but do not maintain the ledger. The researchers use the RSUs as the full nodes to satisfy computational and stable bandwidth resources and the vehicles as the simplified nodes to quantify and encapsulate the vehicular interactive behaviors into the transactions [3, 5, 6, 9, 17, 20]. However, it is tricky for an RSU-based blockchain ledger to guarantee timely reputation updates. Vehicles can only connect and issue transactions to nearby vehicles or RSUs [21]. When a traffic jam or accident occurs, the vehicle density will dramatically increase in the spot and overload adjacent RSUs, which delays the consensus of the ledger and update of reputation.Distributed ledger with a directed acyclic graph- (DAG-) based architecture seems to have better scalability than traditional blockchain architectures, which provide promising solutions to solve the issue of uneven reputation update workload. Firstly, the DAG-based distributed ledger (DDL) has a higher throughput than the blockchain. Instead of competing for the block-level consensus, DDL verifies and approves the transactions in different parts of the ledger network parallelly with homogenous nodes. A DDL node is required to approve recently issued transactions to help these pending transactions receive enough approvals quickly. Secondly, some DDL systems, such as the Tangle [10], are designed for the IoT scenario composed of low-resource nodes, e.g., vehicles. Although some works have been done on DDL-enabled VANET, they mainly carried out the feasibility tests [13, 14], and two key issues have still not been properly solved. (1) DDL needs to sort the parallelly approved transactions [11], but this brings about the complexity of the design. (2) DDL requires enough nodes to ensure the high throughput and security of the ledger. It is a challenge to guarantee this in the mobile VANET.To address the above challenges, this paper proposes a partitioned DDL with local consistency for reputation management in VANETs. We designed the ledger and reputation update method based on the insight of spatiotemporal sensitivity. On the one hand, limited by the sensing range, some interactions occur only between the nearby vehicles [12]. For example, the traffic lights at an intersection are only helpful for nearby vehicles that also only these vehicles can check the trustworthiness of light information instantly. On the other hand, unlike financial applications, reputation management in VANETs does not require a transaction to reach a consensus among all nodes. Specifically, a vehicle needs someone’s reputation only when establishing trust with a meeting vehicle, so the vehicles with different routes do not need each other’s reputation in practice. We argue that a vehicle could independently choose which vehicles to follow according to its own itinerary needs. Ensuring the related transactions are consistent among the vehicles in a particular range is enough. The main contributions of this paper include the following.
(i)
We design a partitioned DAG-based distributed ledger based on the Tangle architecture for reputation management in the VANETs(ii)
We present a vehicular reputation evaluation method by assessing the node’s interactive quality and the contribution to maintaining the transaction consensus(iii)
We propose a reputation update method based on local transactional consistency to reduce the update latency and improve the trust establishment(iv)
To demonstrate the effectiveness of the proposed ledger framework, we conduct the simulations on a real-world dataset, and simulation results reveal that the proposed framework is effective and feasible in the large-scale VANETs and the reputation update delay also converges when the VANETs size is growing exponentiallyThe remainder of this paper is organized as follows. Section2 surveys the existing reputation system for VANETs and summarises the related DDL works. Section 3 describes the framework overview and system model. The details of the proposed ledger are carried out in Section 4. Section 5 proposes the reputation definition and update method. We conduct simulations and discuss the numeric results in Section 6. Finally, Section 7 concludes the paper.


## 2. Related Work

In this section, we classify existing DLT-based reputation/trust management systems and present existing works about expanding the throughput of the distributed ledger systems.


### 2.1. DLT-Enabled Reputation/Trust Management in VANET

In a DLT-enabled reputation/trust management system in VANET, the distributed ledger helps the vehicles build the consensus of the data, trust, or opinion related to the participant’s reputation. The state-of-the-art systems can be classified into two categories: access-to-trust system and evaluate-to-trust system. We introduce them in detail as follows:(1)
Access-to-trust systemAccess-to-trust systems require that any nodes get permission first before they are considered trustworthy and build trusted communication [15, 16]. In general, the systems maintain a white list or black list to control this communication permission. Lu et al. [17] utilize two blockchains to record the workflow of the Certificate Authority (CA) and management history of all vehicles separately, and the former monitors the credibility of the CA, and the latter maintains the reputation of the system nodes and assists the CA in the issuance of certificates. With the development of smart contract [18], Javaid et al. [4] and Liu et al. [19] all adopted the smart contract to control the registering and access of the honest vehicles, and only the vehicles with permission can communicate with each other freely. Furthermore, Wang et al. [20] use smart contracts to manage the access of vehicles, and vehicles can obtain the evaluation results of the other vehicle’s reputation by submitting the request to the specific smart contract. To overcome the dynamic network size of the VANET, Javaid et al. [4] modified the Proof of Work (PoW) mechanism to adapt to the incoming traffic generated by the vehicles. Kudva et al. [22], Khalid et al. [23], and Liu et al. [19] build their systems based on the consortium blockchain platform, which operates only with a fixed number of preauthorized nodes so it can assign to some powerful nodes to keep the performance of their ledger system. All of the above works focus on communication efficiency but lack investigation into the incentives of the nodes in a decentralized system.
(2)
Evaluate-to-trust systemEvaluate-to-trust systems directly assess the credibility of the transmitted data, including based on the voting of different data sources about the same event, the reputation of the source sender, or even the empirical probability of the event occurrence. Kang et al. [24]use the interaction frequency, event timelines, and trajectory similarity of the source vehicles to evaluate their message’s credibility; Road Side Units (RSUs) collect the reputation opinions or other shared data and ensure the consensus of these records by PoW. To solve similar problems, Yang et al. [6] use the location of the sending vehicles to evaluate the message’s credibility, and RSUs collect multiple messages that report the same event from different vehicles, calculate the sending vehicles’ offsets, and add them to the blockchain through a consensus mechanism combining PoW and Proof of Stake (PoS). Based on the above work, Lu et al. [1] required the vehicles, in addition, to continue to collect the opinions on the event after receiving it from its initiator and also to query the initiator’s reputation from the RSUs to compute the event’s credibility, which will eventually be transmitted back to the RSUs to update the initiator’s reputation. In these systems, the evaluation of the reputation is conducted after the nodes share messages. Unlike the above systems, Li et al. [25] proposed an active detection method based on the probe to find the possible misbehavior nodes before the sharing, and the system divided the VANET into multiple fixed partitions and set some fixed powerful servers to provide stable blockchain services. However, although all the above works allow the vehicles to self-assess the message’s credibility or vehicle’s trustworthiness for specific interaction, they still rely on the RSUs to provide and update the vehicles’ reputation.The most existing DLT-based reputation/trust management systems adopted the blockchain platform as their infrastructure framework. They implemented the RSUs as the miner (running the backbone network of the blockchain) because they have better computing resources and more stable network links than the vehicles in VANET. However, it is easy to cause the delay of reputation update due to the limitation of the RSU bandwidth and block size [6] when the inflow traffic increases. Diallo et al. [26] and Zhang et al. [27] have tried to reduce the update delay by using other consensus technologies, such as Practical Byzantine Fault Tolerance (PBFT). However, PBFT has a high communication complexity, and the consensus cluster should not be too large. Therefore, there are no suitable flexible frameworks that can simultaneously cope with the dynamic network topology, fragility network connection, and the lower update delay requirements in VAENT.


### 2.2. The DAG-Based Distributed Ledger

DAG ledgers potentially offer many advantages over traditional blockchain architectures for DLTs, including scalability and faster transaction speeds (Ferraro). Many DAG-based DLT projects, such as NANO [28], Byteball [29], and Tangle [10], have been in operation for many years and have been tested in practical applications. DAG ledgers organize transactions according to the DAG structure instead of packing them into the block. The consensus is conducted in parallel and runs over the transaction level with stochastic attachment mechanisms instead of constructing a chain of blocks. All transactions must be strictly ordered by their timestamp, which forces the above methods to adopt an additional puissant and centralized component, such as the coordinator in the Tangle, to check and determine the order of all transactions. Bartolomeu et al. [14] deploy the Tangle in VANET, and their experiment result shows that the transaction confirmation delay has been significantly reduced than the blockchain solution, and the performance is comparable with Tangle’s main network. However, they only validated the feasibility of DAG-based consensus deployment on VANET and there is no further research on specific VANET applications. In terms of reputation management in VANET, Zhang et al. [27] and Kang et al. [24] both try to apply the DAG structure in subregions that a miner covered to improve transaction processing speed in subregions, but their ledger is still based on the blockchain platform.Therefore, this paper designs a DAG-based vehicular distributed ledger and implements it with the Tangle architecture to optimize reputation management in VANET.


## 2.1. DLT-Enabled Reputation/Trust Management in VANET

In a DLT-enabled reputation/trust management system in VANET, the distributed ledger helps the vehicles build the consensus of the data, trust, or opinion related to the participant’s reputation. The state-of-the-art systems can be classified into two categories: access-to-trust system and evaluate-to-trust system. We introduce them in detail as follows:(1)
Access-to-trust systemAccess-to-trust systems require that any nodes get permission first before they are considered trustworthy and build trusted communication [15, 16]. In general, the systems maintain a white list or black list to control this communication permission. Lu et al. [17] utilize two blockchains to record the workflow of the Certificate Authority (CA) and management history of all vehicles separately, and the former monitors the credibility of the CA, and the latter maintains the reputation of the system nodes and assists the CA in the issuance of certificates. With the development of smart contract [18], Javaid et al. [4] and Liu et al. [19] all adopted the smart contract to control the registering and access of the honest vehicles, and only the vehicles with permission can communicate with each other freely. Furthermore, Wang et al. [20] use smart contracts to manage the access of vehicles, and vehicles can obtain the evaluation results of the other vehicle’s reputation by submitting the request to the specific smart contract. To overcome the dynamic network size of the VANET, Javaid et al. [4] modified the Proof of Work (PoW) mechanism to adapt to the incoming traffic generated by the vehicles. Kudva et al. [22], Khalid et al. [23], and Liu et al. [19] build their systems based on the consortium blockchain platform, which operates only with a fixed number of preauthorized nodes so it can assign to some powerful nodes to keep the performance of their ledger system. All of the above works focus on communication efficiency but lack investigation into the incentives of the nodes in a decentralized system.
(2)
Evaluate-to-trust systemEvaluate-to-trust systems directly assess the credibility of the transmitted data, including based on the voting of different data sources about the same event, the reputation of the source sender, or even the empirical probability of the event occurrence. Kang et al. [24]use the interaction frequency, event timelines, and trajectory similarity of the source vehicles to evaluate their message’s credibility; Road Side Units (RSUs) collect the reputation opinions or other shared data and ensure the consensus of these records by PoW. To solve similar problems, Yang et al. [6] use the location of the sending vehicles to evaluate the message’s credibility, and RSUs collect multiple messages that report the same event from different vehicles, calculate the sending vehicles’ offsets, and add them to the blockchain through a consensus mechanism combining PoW and Proof of Stake (PoS). Based on the above work, Lu et al. [1] required the vehicles, in addition, to continue to collect the opinions on the event after receiving it from its initiator and also to query the initiator’s reputation from the RSUs to compute the event’s credibility, which will eventually be transmitted back to the RSUs to update the initiator’s reputation. In these systems, the evaluation of the reputation is conducted after the nodes share messages. Unlike the above systems, Li et al. [25] proposed an active detection method based on the probe to find the possible misbehavior nodes before the sharing, and the system divided the VANET into multiple fixed partitions and set some fixed powerful servers to provide stable blockchain services. However, although all the above works allow the vehicles to self-assess the message’s credibility or vehicle’s trustworthiness for specific interaction, they still rely on the RSUs to provide and update the vehicles’ reputation.The most existing DLT-based reputation/trust management systems adopted the blockchain platform as their infrastructure framework. They implemented the RSUs as the miner (running the backbone network of the blockchain) because they have better computing resources and more stable network links than the vehicles in VANET. However, it is easy to cause the delay of reputation update due to the limitation of the RSU bandwidth and block size [6] when the inflow traffic increases. Diallo et al. [26] and Zhang et al. [27] have tried to reduce the update delay by using other consensus technologies, such as Practical Byzantine Fault Tolerance (PBFT). However, PBFT has a high communication complexity, and the consensus cluster should not be too large. Therefore, there are no suitable flexible frameworks that can simultaneously cope with the dynamic network topology, fragility network connection, and the lower update delay requirements in VAENT.


## 2.2. The DAG-Based Distributed Ledger

DAG ledgers potentially offer many advantages over traditional blockchain architectures for DLTs, including scalability and faster transaction speeds (Ferraro). Many DAG-based DLT projects, such as NANO [28], Byteball [29], and Tangle [10], have been in operation for many years and have been tested in practical applications. DAG ledgers organize transactions according to the DAG structure instead of packing them into the block. The consensus is conducted in parallel and runs over the transaction level with stochastic attachment mechanisms instead of constructing a chain of blocks. All transactions must be strictly ordered by their timestamp, which forces the above methods to adopt an additional puissant and centralized component, such as the coordinator in the Tangle, to check and determine the order of all transactions. Bartolomeu et al. [14] deploy the Tangle in VANET, and their experiment result shows that the transaction confirmation delay has been significantly reduced than the blockchain solution, and the performance is comparable with Tangle’s main network. However, they only validated the feasibility of DAG-based consensus deployment on VANET and there is no further research on specific VANET applications. In terms of reputation management in VANET, Zhang et al. [27] and Kang et al. [24] both try to apply the DAG structure in subregions that a miner covered to improve transaction processing speed in subregions, but their ledger is still based on the blockchain platform.Therefore, this paper designs a DAG-based vehicular distributed ledger and implements it with the Tangle architecture to optimize reputation management in VANET.


## 3. Application Overview

In this section, we first present the application scenarios of sharing in VANET and the interactive model and then introduce fundamental concepts of the Tangle project as backdrop. For the clarity of the following discussion, the key notations are summarized in Table1.Table 1
Notions.
SymbolDefinitionSymbolDefinitionpiA node that can interact with others and issue transactionμThe reputationpj⟶iThe node answered the request ofpiσThe metric of interactive qualityyj⟶iThe received originally rating ofpj⟶iηThe metric of consensus contributionψiThe transactionR+,R−,R∗The calculated ratings of positive interaction, negative interaction, and consensus contributionψj⟶iThe transaction directly approved byψjwiThe weight ofψiψj⟶m⟶iThe transaction indirectly approved byψjNcThe set of all the active nodes in a period,Nc is the number of these nodesψiThe set of transactions that contains the historical interactions ofpiAiThe cumulative weight ofψiLtThe set of tips at timetΘThe threshold of local consistency


### 3.1. Application Model

Figure1 shows the overview of our reputation maintenance framework where the VANET entity, including vehicles and RSUs, arises sharing interaction and the vehicular reputation, maintained by a DDL. The framework contains two layers: the sharing and vehicular reputation management layers. We require a node’s reputation to be calculated by auditing the node’s history interactive behavior that accumulates in the sharing layer, and the node’s historical interaction is packaged into the transaction. A node will generate a transaction based on its last interaction and attach it to the DDL in the reputation management layer. To ensure all the nodes can run the DDL equally, we assume that every node has an essential computational resource and can hold a full copy of the ledger.Figure 1
Overview of trust maintenance with a DAG-based distributed ledger.Another important assumption is that the peer-to-peer interactive application in VANET scenario, such as environmental awareness, is mostly geographically independent. Take the traffic density perception at an intersection as an example; Figure1 shows that the nodes around the intersection S1 can be seen as a subpartition of VANET, and S1 consists of at least n≥5 vehicles and m≥2 RSUs. It is acceptable that all the traffic data contained in the message perceived by the p1 can only be verified by the nodes in the same partition (that is, S1). So, we can have S=S1,S2,⋯,SK, where S is the entire VANET and consists of K partitions. These partitions are connected by the RSUs, and any node belongs to at least one partition. Obviously, some applications need the nodes in different partitions to cooperate, such as route plans, and we will discuss these more complicated scenarios in future work.


### 3.2. Interactive Model

In terms of most applications in VANET, we consider two typical interactive models, sharing and cooperating.


#### 3.2.1. Sharing Model

To inform some warnings or share some knowledge, some vehicles may positively broadcast unencrypted information. Figure2 shows that there are nnodes (n≥2, Figure 2 givesV1 and V2 as an example) that broadcast the knowledge of a specific eventEat the same time. If a node has interests in E, it can collect a message set Msg=msg1,msg2,⋯,msgn. Then, the nodes need to assess the credibility of each of the received messages and evaluate a possible result of event E (because they do not know the truth about it). Based on the calculated result of event E, the node can judge whether the received messages are the same or contrary to the calculated result of E and evaluate a rating about interactive behavior of the information source node.Figure 2
Two vehicles sharing data with others.


#### 3.2.2. Cooperating Model

To get advice and assistance, some vehicles may ask for help from others. Figure3 shows a general process, a node (p1) in need broadcasts its request to the surrounding nodes first, and then, others may answer the request at their will. If there are n answered nodes, p1 can receive some responses; for easy understanding, we also use an answering message set Msg=msg1,msg2,⋯,msgn for the unified presentation with the same as sharing mode. The difference is only the p1 can judge whether the answered node provided an effective result and evaluate the rating of interactive behavior for each answered node. To simplify the discussion, we assume that all requested nodes are honest.Figure 3
A vehicle asks and establishes cooperation to others.


### 3.3. DAG-Based Distributed Ledger Model

All the transactions are stored in a DAG architecture and are represented by vertexes (dark grey rectangles shown in Figure4). A new transaction needs to approve several old (especially issued recently) transactions, and the approval relationships are represented by edges. A new edge (from the new vertex to the old vertices that stand for the selected previous transactions) is added while a new transaction is issued simultaneously. This adding process is also called transaction attachment. Some key concepts of the DDL are introduced as follows.Figure 4
Representation of approval between the transactions.Transaction Approval: as shown in Figure 4, there are two types of approval relationship, direct and indirect approval. Direct approval is represented by a directed edge and indirect approval is represented by a path that consists of several transactions and direct edges connecting them. For example, E1 indicates that ψc approved ψa, E2 indicates ψb approved ψc, and E4 and E5 indicate ψd and ψe approved ψa indirectly.Tip: transaction that has received no approval is called tip. A tip may be a newly issued transaction (e.g., ψe or ψf) or an old transaction but has not been approved even once (e.g., ψc). Define Lt to be the set of tips at time t. In general, an issuing node is suggested to select tips from Lt to approve, so the size of Lt determines the growth and health of the DDL. Once a transaction is approved, it is no longer a tip, but it also needs to accumulate enough direct and indirect approval to be regarded as secure and final confirmation.Cumulative weight: cumulative weight (CW) is a metric for measuring how trustworthy a transaction is for security consideration. Suppose Ai presents the CW of ψi and is calculated by the weights of all the transactions, including directly and indirectly, that approved ψi. In general, when a transaction’s CW reaches (only monotonically increasing) a threshold, we say that it is confirmed, which also means it is correct and immutable. We will introduce the details of how the weights increase and threshold setting in Section 5.


## 3.1. Application Model

Figure1 shows the overview of our reputation maintenance framework where the VANET entity, including vehicles and RSUs, arises sharing interaction and the vehicular reputation, maintained by a DDL. The framework contains two layers: the sharing and vehicular reputation management layers. We require a node’s reputation to be calculated by auditing the node’s history interactive behavior that accumulates in the sharing layer, and the node’s historical interaction is packaged into the transaction. A node will generate a transaction based on its last interaction and attach it to the DDL in the reputation management layer. To ensure all the nodes can run the DDL equally, we assume that every node has an essential computational resource and can hold a full copy of the ledger.Figure 1
Overview of trust maintenance with a DAG-based distributed ledger.Another important assumption is that the peer-to-peer interactive application in VANET scenario, such as environmental awareness, is mostly geographically independent. Take the traffic density perception at an intersection as an example; Figure1 shows that the nodes around the intersection S1 can be seen as a subpartition of VANET, and S1 consists of at least n≥5 vehicles and m≥2 RSUs. It is acceptable that all the traffic data contained in the message perceived by the p1 can only be verified by the nodes in the same partition (that is, S1). So, we can have S=S1,S2,⋯,SK, where S is the entire VANET and consists of K partitions. These partitions are connected by the RSUs, and any node belongs to at least one partition. Obviously, some applications need the nodes in different partitions to cooperate, such as route plans, and we will discuss these more complicated scenarios in future work.


## 3.2. Interactive Model

In terms of most applications in VANET, we consider two typical interactive models, sharing and cooperating.


### 3.2.1. Sharing Model

To inform some warnings or share some knowledge, some vehicles may positively broadcast unencrypted information. Figure2 shows that there are nnodes (n≥2, Figure 2 givesV1 and V2 as an example) that broadcast the knowledge of a specific eventEat the same time. If a node has interests in E, it can collect a message set Msg=msg1,msg2,⋯,msgn. Then, the nodes need to assess the credibility of each of the received messages and evaluate a possible result of event E (because they do not know the truth about it). Based on the calculated result of event E, the node can judge whether the received messages are the same or contrary to the calculated result of E and evaluate a rating about interactive behavior of the information source node.Figure 2
Two vehicles sharing data with others.


### 3.2.2. Cooperating Model

To get advice and assistance, some vehicles may ask for help from others. Figure3 shows a general process, a node (p1) in need broadcasts its request to the surrounding nodes first, and then, others may answer the request at their will. If there are n answered nodes, p1 can receive some responses; for easy understanding, we also use an answering message set Msg=msg1,msg2,⋯,msgn for the unified presentation with the same as sharing mode. The difference is only the p1 can judge whether the answered node provided an effective result and evaluate the rating of interactive behavior for each answered node. To simplify the discussion, we assume that all requested nodes are honest.Figure 3
A vehicle asks and establishes cooperation to others.


## 3.2.1. Sharing Model

To inform some warnings or share some knowledge, some vehicles may positively broadcast unencrypted information. Figure2 shows that there are nnodes (n≥2, Figure 2 givesV1 and V2 as an example) that broadcast the knowledge of a specific eventEat the same time. If a node has interests in E, it can collect a message set Msg=msg1,msg2,⋯,msgn. Then, the nodes need to assess the credibility of each of the received messages and evaluate a possible result of event E (because they do not know the truth about it). Based on the calculated result of event E, the node can judge whether the received messages are the same or contrary to the calculated result of E and evaluate a rating about interactive behavior of the information source node.Figure 2
Two vehicles sharing data with others.


## 3.2.2. Cooperating Model

To get advice and assistance, some vehicles may ask for help from others. Figure3 shows a general process, a node (p1) in need broadcasts its request to the surrounding nodes first, and then, others may answer the request at their will. If there are n answered nodes, p1 can receive some responses; for easy understanding, we also use an answering message set Msg=msg1,msg2,⋯,msgn for the unified presentation with the same as sharing mode. The difference is only the p1 can judge whether the answered node provided an effective result and evaluate the rating of interactive behavior for each answered node. To simplify the discussion, we assume that all requested nodes are honest.Figure 3
A vehicle asks and establishes cooperation to others.


## 3.3. DAG-Based Distributed Ledger Model

All the transactions are stored in a DAG architecture and are represented by vertexes (dark grey rectangles shown in Figure4). A new transaction needs to approve several old (especially issued recently) transactions, and the approval relationships are represented by edges. A new edge (from the new vertex to the old vertices that stand for the selected previous transactions) is added while a new transaction is issued simultaneously. This adding process is also called transaction attachment. Some key concepts of the DDL are introduced as follows.Figure 4
Representation of approval between the transactions.Transaction Approval: as shown in Figure 4, there are two types of approval relationship, direct and indirect approval. Direct approval is represented by a directed edge and indirect approval is represented by a path that consists of several transactions and direct edges connecting them. For example, E1 indicates that ψc approved ψa, E2 indicates ψb approved ψc, and E4 and E5 indicate ψd and ψe approved ψa indirectly.Tip: transaction that has received no approval is called tip. A tip may be a newly issued transaction (e.g., ψe or ψf) or an old transaction but has not been approved even once (e.g., ψc). Define Lt to be the set of tips at time t. In general, an issuing node is suggested to select tips from Lt to approve, so the size of Lt determines the growth and health of the DDL. Once a transaction is approved, it is no longer a tip, but it also needs to accumulate enough direct and indirect approval to be regarded as secure and final confirmation.Cumulative weight: cumulative weight (CW) is a metric for measuring how trustworthy a transaction is for security consideration. Suppose Ai presents the CW of ψi and is calculated by the weights of all the transactions, including directly and indirectly, that approved ψi. In general, when a transaction’s CW reaches (only monotonically increasing) a threshold, we say that it is confirmed, which also means it is correct and immutable. We will introduce the details of how the weights increase and threshold setting in Section 5.


## 4. Partitioned DAG-Based Distributed Ledger in VANET

This section first introduces how to record the details of the interaction into a transaction and how to verify. Then, we present the definition of the CW considered under the partitioned DDL. To deal with the fragility of connection and topology in VANET, we introduce a local consistency threshold and an extended tip selection algorithm to improve the throughput of transactional consensus while ensuring the ledger’s security.


### 4.1. Historic Interaction

We need a way for the node to obtain others’ reputations when establishing the trust. The existing works usually update the “balance” or “bias” of reputation. However, these solutions do not allow nodes to adjust reputations according to different situations. We consider the “auditing” method, which records the interaction details into transactions, and nodes calculate the reputation for anyone in their desired ways when needed.Two interactive models have the different roles of the node to record each interactive detail. For a sharing model, RSUs can generate the transaction to record an interactive event in the partition it is deployed. If there are many RSUs, a rotation method can balance the workload of transaction generation. For a cooperating model, the requested node is responsible for generating the transaction when finishing a round of interaction. Take the cooperating model as the example, and we define the transaction as shown in Figure5.
(1)Ψ≔d,γ,s,t,where d is the interaction data, γ is the transaction approval data, and s and t represent the encrypted script and timestamp, respectively. The detail of d is
(2)d≔pi,pj⟶i,yj⟶i,where pi denotes the issuing node that is also a requested node; pj⟶i and yj⟶i refers to all the nodes that answered the pi and the corresponding ratings, respectively. We use a Bayesian method [6] to inference the yj⟶i. γ represents the transaction approval relationship and composed of the following:
(3)γ≔ψi⟶m,PoWNonce,PoWtarget,where ψi⟶m denotes the selected and approved transaction set. PoW Nonce and PoW target are parameters for a PoW mechanism that used to prevent malicious nodes from issuing large-scale false transactions to attack the ledger network. In general, the target is set to a small value and does not bring heavy PoW workload for a vehicle.Figure 5
Data structure of the transaction.


### 4.2. Transaction Verification

Each node needs to verify the newly received transaction to avoid malicious and fake transaction attacks. Moreover, the transaction weight is also calculated if it passes the verification.The verification includes three steps; takeψi as an example; they are as follows:
(1)
Ind, whether the pi and pj⟶i exist(2)
Inγ, whether all the selected transactions in ψi⟶m exist, and verify their PoWNONCE(3)
If step 1 and step 2 pass, calculate the transaction’s weightFor step 1, we assume that all the interactive messages can be recorded with some methods, such as the smart contract among the reference nodes.For step 2, the validation ofγ requires that the selected and approved transactions must have been transmitted to all other nodes (at least in several nearby partitions) before they can be approved. In fact, the most recent tips that the issuing node cab select at time t can only be issued at t−h, where h, called the waiting period [10], includes both the PoW time and the minimum transmission time for transaction transmission to most nearby nodes.For step 3, any node that received the transaction needs to calculate its weight. The weight is calculated only once and stored only at the local.In our framework, we define the issuing node’s interactive behaviors as the weight of its issuing transaction. Some nodes invest a lot, including frequently and actively responding or issuing transactions (verifying and approving the other transactions to assist the DDL). For a peer-to-peer data sharing system, it is obvious that the nodes working hard and getting higher interaction ratings should have more credibility. So, we define the weight of the transaction issued bypi as
(4)wi=ϵ1ei+ϵ2∑k∈ψiyk,where ei denotes the number of valid transactions issued by pi and ψiis a set of transactions that contain the historical interactions of pi. yk refers to the corresponding rating and ϵ1+ϵ2=1. Obviously, ei and the size of ψi are changed over time, so we only calculate the weight at once when it is issued.


### 4.3. Cumulative Weight

The CW of a transaction can be calculated by the sum of the weights from all its successor transactions. If we setw=1 for each transaction, the CW represents how much approval this transaction achieved. For ψi, its CW is
(5)Ai=∑j∈ψj⟶i,ψj⟶m⟶iwj,where ψj⟶i,ψj⟶m⟶i=ψj⟶i+ψj⟶m⟶i denotes a set of transactions that directly and indirectly approve ψi, wj is the weight of ψj, and any transaction counts once. Figure 6 demonstrates an example of how a transaction accumulates weight, where the rectangle represents transaction, and the number outside the parentheses in the rectangle represents transaction weight. The transaction c selects a and b which, respectively, are represented by the edges E2 and E3, so a and b both accumulate a direct approval, and their accumulative weight is added by the weight of c (it is 12 in Figure 6). b and c approve a directly; d and e approve a indirectly. If wb=1, wc=12, wd=2, and we=1, then Aa=5+1+12+2+1=21.Figure 6
A part of ledger.


### 4.4. Local Consistency Threshold

The existing DDLs own independent components to strictly sequence transactions, such as Tangle’s coordinator [11]. Strictly ordered transactions are very important for financial applications to defend against the double attack. However, managing reputation does not need to be strict. We argue that a transaction, approved by enough but not be strictly ordered globally, is secure for auditing reputation for the reference nodes. DDL defines that a transaction reaches consensus when it achieves enough approval, making the transaction difficult to tamper. Combining the above discussion of the CW, it is easy to realize that the transaction accumulated a high CW which can be seen as secure and cannot easily be falsified. We need to find how much CW can ensure the security of transactions for auditing reputation.The local consistency threshold is proposed to enable the ledger node to judge whether the transaction is secure by itself instead of relying on the third component. Before introducing the details of the local consistency threshold, let us clarify two essential and reasonable assumptions in this paper: (1) if two nodes do not meet within their trips (refer to the trip where they need the VANET applications), they do not need the reputation of each other. First, in terms of the collaboration, nodes only care about the nodes running in several nearby partitions; e.g., the traffic light data of a specific road section is only meaningful and can only be verified by the nearby nodes. Then, in terms of time, the node’s behavior that is too old is no longer suitable for evaluating reputation for some security issue consideration [30]. (2) We consider that if a node has always been well-behaved in issuing a transaction (verification and selecting tips) and participating in the interaction (sharing and cooperating), then the ledger will eventually accept the transaction issued by this node with a high probability.According to the above discussion, we set a periodh, limiting all transactions’ valid time. When a period ends, the ledger will be reset. We also define a set of transactions Nc, containing all the transactions for a node cared. However, the fewer nodes will lead to security risks for a distributed ledger, so we bring the workload of the nodes to increase the transaction’s weight. Now, we can focus on the transaction consensus in nn≥1 partitions and define Θ as the local consistency threshold to assist nodes to infer the transaction’s credibility, and it can be expressed by
(6)Θ=LNc∑j∈Ncmaxk∈ψkjwkj,where ψkj=ψ1,ψ2,⋯,ψkj denotes the set of all the transactions issued by node pj, wkj is the weight of the ψkj, so maxk∈ψkjwkj presents the largest weight of the transaction issued by pj. Nc represents a set of active nodes (issued transactions in a period) in n partitions cared about; Nc is the number of these nodes. L is a positive hyperparameter that controls the evolution speed of the ledger, and the nodes can adjust it to cope with the scale change of the interest partitions. Nodes could make their judgments on whether the transaction is confirmed. Algorithm 1 introduces the detail of the transaction consensus process.


### 4.5. Tip Selection Algorithm

We propose a modification to the attachment mechanism of the Tangle. This modification ensures the transaction is verified and secure in the partitioning VANET and preserves essential features of the Monte Carlo Markov Chain (MCMC) selection algorithm [10].Algorithm 1: Consensus algorithm for transactions on partitions.
input: A tipψi,local consistency thresholdΘ, current tip set Lt, sub-DAG consisted of the confirmed transactions Gtcand sub- DAG consisted of the unconfirmed transactions Gtuoutput: Updated ledgerGt+1,cGt+1,u and the updated tip set Lt+11 Extract all approval transactionsψi⟶mpackaged in ψi;2 for eachψi⟶mdo3 calculate and add weightωito ψi;4 addωito Cumulative Weight Ai⟶mofψii⟶m;5 ifψi⟶minLtto Gtu6  addψi to Ltto toGtu7  moveψi⟶mfromLtto Gtu8 else9  wait for a punish time;10  addψi to Lt;11. Extract the transactionψi⟶m⟶ηthat indirectly approved by12 for eachψi⟶m⟶η in ii⟶m⟶ηdo13 addwi to Ai⟶m⟶n of ψi⟶m⟶n;14ifψi⟶m⟶n>Θ then15  moveψi⟶m⟶n to Gtc16final;17returnGt+1c,Gt+1c,Lt+1;Firstly, the issuing nodes need to verify whether or not the transaction selected for approval is mutually consistent with each other. If detecting an inconsistency, the tip selection process must be rerun until a consistentLt is found. In addition, creating m independent random walks in a path of DAG contains the transactions issued by the nodes running in the interested partitions in the current period. The walk starts at the genesis site and moves along the edges. The probability of stepping along an edge from site ψj to site ψk is
(7)f−αAj−Ak,where f· is an exponential function and α is a positive constant. Aj and Ak are the CWs of ψj and ψk, respectively. For a new transaction, suppose the walk should reach QQ≥m tips, and the issuing node selects the tip satisfying
(8)minl<Q∑i=1mΘ−Ail,where Ail denotes the CW of transactions directly approved by ψl that is the end of a walk. Finally, we also need to walk to the m tips that their selected transactions are about to be or just recent security.


## 4.1. Historic Interaction

We need a way for the node to obtain others’ reputations when establishing the trust. The existing works usually update the “balance” or “bias” of reputation. However, these solutions do not allow nodes to adjust reputations according to different situations. We consider the “auditing” method, which records the interaction details into transactions, and nodes calculate the reputation for anyone in their desired ways when needed.Two interactive models have the different roles of the node to record each interactive detail. For a sharing model, RSUs can generate the transaction to record an interactive event in the partition it is deployed. If there are many RSUs, a rotation method can balance the workload of transaction generation. For a cooperating model, the requested node is responsible for generating the transaction when finishing a round of interaction. Take the cooperating model as the example, and we define the transaction as shown in Figure5.
(1)Ψ≔d,γ,s,t,where d is the interaction data, γ is the transaction approval data, and s and t represent the encrypted script and timestamp, respectively. The detail of d is
(2)d≔pi,pj⟶i,yj⟶i,where pi denotes the issuing node that is also a requested node; pj⟶i and yj⟶i refers to all the nodes that answered the pi and the corresponding ratings, respectively. We use a Bayesian method [6] to inference the yj⟶i. γ represents the transaction approval relationship and composed of the following:
(3)γ≔ψi⟶m,PoWNonce,PoWtarget,where ψi⟶m denotes the selected and approved transaction set. PoW Nonce and PoW target are parameters for a PoW mechanism that used to prevent malicious nodes from issuing large-scale false transactions to attack the ledger network. In general, the target is set to a small value and does not bring heavy PoW workload for a vehicle.Figure 5
Data structure of the transaction.


## 4.2. Transaction Verification

Each node needs to verify the newly received transaction to avoid malicious and fake transaction attacks. Moreover, the transaction weight is also calculated if it passes the verification.The verification includes three steps; takeψi as an example; they are as follows:
(1)
Ind, whether the pi and pj⟶i exist(2)
Inγ, whether all the selected transactions in ψi⟶m exist, and verify their PoWNONCE(3)
If step 1 and step 2 pass, calculate the transaction’s weightFor step 1, we assume that all the interactive messages can be recorded with some methods, such as the smart contract among the reference nodes.For step 2, the validation ofγ requires that the selected and approved transactions must have been transmitted to all other nodes (at least in several nearby partitions) before they can be approved. In fact, the most recent tips that the issuing node cab select at time t can only be issued at t−h, where h, called the waiting period [10], includes both the PoW time and the minimum transmission time for transaction transmission to most nearby nodes.For step 3, any node that received the transaction needs to calculate its weight. The weight is calculated only once and stored only at the local.In our framework, we define the issuing node’s interactive behaviors as the weight of its issuing transaction. Some nodes invest a lot, including frequently and actively responding or issuing transactions (verifying and approving the other transactions to assist the DDL). For a peer-to-peer data sharing system, it is obvious that the nodes working hard and getting higher interaction ratings should have more credibility. So, we define the weight of the transaction issued bypi as
(4)wi=ϵ1ei+ϵ2∑k∈ψiyk,where ei denotes the number of valid transactions issued by pi and ψiis a set of transactions that contain the historical interactions of pi. yk refers to the corresponding rating and ϵ1+ϵ2=1. Obviously, ei and the size of ψi are changed over time, so we only calculate the weight at once when it is issued.


## 4.3. Cumulative Weight

The CW of a transaction can be calculated by the sum of the weights from all its successor transactions. If we setw=1 for each transaction, the CW represents how much approval this transaction achieved. For ψi, its CW is
(5)Ai=∑j∈ψj⟶i,ψj⟶m⟶iwj,where ψj⟶i,ψj⟶m⟶i=ψj⟶i+ψj⟶m⟶i denotes a set of transactions that directly and indirectly approve ψi, wj is the weight of ψj, and any transaction counts once. Figure 6 demonstrates an example of how a transaction accumulates weight, where the rectangle represents transaction, and the number outside the parentheses in the rectangle represents transaction weight. The transaction c selects a and b which, respectively, are represented by the edges E2 and E3, so a and b both accumulate a direct approval, and their accumulative weight is added by the weight of c (it is 12 in Figure 6). b and c approve a directly; d and e approve a indirectly. If wb=1, wc=12, wd=2, and we=1, then Aa=5+1+12+2+1=21.Figure 6
A part of ledger.


## 4.4. Local Consistency Threshold

The existing DDLs own independent components to strictly sequence transactions, such as Tangle’s coordinator [11]. Strictly ordered transactions are very important for financial applications to defend against the double attack. However, managing reputation does not need to be strict. We argue that a transaction, approved by enough but not be strictly ordered globally, is secure for auditing reputation for the reference nodes. DDL defines that a transaction reaches consensus when it achieves enough approval, making the transaction difficult to tamper. Combining the above discussion of the CW, it is easy to realize that the transaction accumulated a high CW which can be seen as secure and cannot easily be falsified. We need to find how much CW can ensure the security of transactions for auditing reputation.The local consistency threshold is proposed to enable the ledger node to judge whether the transaction is secure by itself instead of relying on the third component. Before introducing the details of the local consistency threshold, let us clarify two essential and reasonable assumptions in this paper: (1) if two nodes do not meet within their trips (refer to the trip where they need the VANET applications), they do not need the reputation of each other. First, in terms of the collaboration, nodes only care about the nodes running in several nearby partitions; e.g., the traffic light data of a specific road section is only meaningful and can only be verified by the nearby nodes. Then, in terms of time, the node’s behavior that is too old is no longer suitable for evaluating reputation for some security issue consideration [30]. (2) We consider that if a node has always been well-behaved in issuing a transaction (verification and selecting tips) and participating in the interaction (sharing and cooperating), then the ledger will eventually accept the transaction issued by this node with a high probability.According to the above discussion, we set a periodh, limiting all transactions’ valid time. When a period ends, the ledger will be reset. We also define a set of transactions Nc, containing all the transactions for a node cared. However, the fewer nodes will lead to security risks for a distributed ledger, so we bring the workload of the nodes to increase the transaction’s weight. Now, we can focus on the transaction consensus in nn≥1 partitions and define Θ as the local consistency threshold to assist nodes to infer the transaction’s credibility, and it can be expressed by
(6)Θ=LNc∑j∈Ncmaxk∈ψkjwkj,where ψkj=ψ1,ψ2,⋯,ψkj denotes the set of all the transactions issued by node pj, wkj is the weight of the ψkj, so maxk∈ψkjwkj presents the largest weight of the transaction issued by pj. Nc represents a set of active nodes (issued transactions in a period) in n partitions cared about; Nc is the number of these nodes. L is a positive hyperparameter that controls the evolution speed of the ledger, and the nodes can adjust it to cope with the scale change of the interest partitions. Nodes could make their judgments on whether the transaction is confirmed. Algorithm 1 introduces the detail of the transaction consensus process.


## 4.5. Tip Selection Algorithm

We propose a modification to the attachment mechanism of the Tangle. This modification ensures the transaction is verified and secure in the partitioning VANET and preserves essential features of the Monte Carlo Markov Chain (MCMC) selection algorithm [10].Algorithm 1: Consensus algorithm for transactions on partitions.
input: A tipψi,local consistency thresholdΘ, current tip set Lt, sub-DAG consisted of the confirmed transactions Gtcand sub- DAG consisted of the unconfirmed transactions Gtuoutput: Updated ledgerGt+1,cGt+1,u and the updated tip set Lt+11 Extract all approval transactionsψi⟶mpackaged in ψi;2 for eachψi⟶mdo3 calculate and add weightωito ψi;4 addωito Cumulative Weight Ai⟶mofψii⟶m;5 ifψi⟶minLtto Gtu6  addψi to Ltto toGtu7  moveψi⟶mfromLtto Gtu8 else9  wait for a punish time;10  addψi to Lt;11. Extract the transactionψi⟶m⟶ηthat indirectly approved by12 for eachψi⟶m⟶η in ii⟶m⟶ηdo13 addwi to Ai⟶m⟶n of ψi⟶m⟶n;14ifψi⟶m⟶n>Θ then15  moveψi⟶m⟶n to Gtc16final;17returnGt+1c,Gt+1c,Lt+1;Firstly, the issuing nodes need to verify whether or not the transaction selected for approval is mutually consistent with each other. If detecting an inconsistency, the tip selection process must be rerun until a consistentLt is found. In addition, creating m independent random walks in a path of DAG contains the transactions issued by the nodes running in the interested partitions in the current period. The walk starts at the genesis site and moves along the edges. The probability of stepping along an edge from site ψj to site ψk is
(7)f−αAj−Ak,where f· is an exponential function and α is a positive constant. Aj and Ak are the CWs of ψj and ψk, respectively. For a new transaction, suppose the walk should reach QQ≥m tips, and the issuing node selects the tip satisfying
(8)minl<Q∑i=1mΘ−Ail,where Ail denotes the CW of transactions directly approved by ψl that is the end of a walk. Finally, we also need to walk to the m tips that their selected transactions are about to be or just recent security.


## 5. Reputation Update with Transaction Local Consistency

In this section, we first present the definition of each part of the vehicular reputation. Then, we will describe the reputation update method based on the partitioning and valid period.


### 5.1. Vehicular Reputation

Our DDL requires the vehicle to be a node and contributes to the ledger maintenance. Therefore, we argue that the expression of reputation needs to contain the node’s behaviors in ledger maintenance and VANET interaction. Interactive behavior refers to the quality of data that the node shares when interacting, and it is stored in the relevant transactions issued after each interaction occurs. The maintenance behavior of the ledger, we also call consensus contribution, refers to the node’s performance in ledger maintenance and is calculated by other nodes when they verify a new transaction issued by the node.In summary, when omitting the symbol of interest partitions and valid period, the reputation is(9)μ=τ1σ+τ2η,where σ and η represent the interactive quality and consensus behavior, respectively; we will discuss them in the following subsection. τ1+τ2=1; they are used to adjust the ratio of the two measures in different scenarios. For example, in the initial phase of each valid period, the ledger needs as many as possible nodes to join to maintain the transaction consensus, at this case, τ2>τ1.


#### 5.1.1. Interactive Quality

To simply the discussion, we only consider the cooperating model because it can easily extend to the sharing model. Assume that a node hasM1-positive ratings and M2-negative ratings, so that all the received ratings M=M1+M2. Let Rmb+ be the positive rating that pb received at mth response at time t and Rmb− represent the negative rating. So we have
(10)Rtu+=∑t=t0tu∑m=1M1Rmb+,(11)Rtu−=∑t=t0tu∑m=1M2Rmb−,where t0 is the initial time of current valid period and tu represents the current time. The interactive quality is calculated as follows:
(12)σtu=θ1·Rtu+−θ2·Rtu−Rtu++Rtu−,where θ1 and θ2 are sensitivity weight; let R+=Rtu+,R−=Rtu−, then
(13)θ1=FR+FR++FR−,θ2=FR−FR++FR−.F· represents the sensitivity function such as Fx=x, Fx=x2, and Fx=x3; the sensitivity of the positive or negative rating in the metric of interactive quality can be controlled by θ. θ could adjust the weight of contribution rating based on the different requirements. For example, when the shared data may threaten the safety of humans, the weight of negative evaluation should be increased.


#### 5.1.2. Consensus Contribution

When the node selects tips, its behavior determines its contribution to the consensus of DDL. The selections are represented by the edges and are public to all nodes, and they are important on ledger evolution. When receiving a new transactionψi issued by pb, a node needs to check the CWs of all the transaction in ψi⟶m and calculate a consensus rating Rb∗t of pb, and the calculation can be expressed by
(14)Rb∗tu=Rb∗tu−1+∑m=1m=MΘ−Ai⟶mtu,where Ai⟶mtu presents the CW of the ψi⟶m approved by ψi at time tu. If Θ−Ai⟶mtu≤0, it denotes that the issuing node selected a confirmed transaction, which represents a bad behavior, of course; otherwise, it denotes a tip is selected or there is other issued unconfirmed transaction recently, which means a good behavior. Therefore, if the node performs positively, then 0≤Rb∗tu≤1; otherwise, −1≤Rb∗tu≤0. The iterative method is used because the CW of a transaction always increases along with time. Define the metric of consensus contribution as
(15)η=f−βRb∗,where β is an attenuation factor; it can be adjusted with the ledger network change even if node pb does nothing in a time interval. Thus, the metric of consensus contribution of a node’s reputation can be calculated by auditing the local transactions at any given time.


### 5.2. Reputation Update

Since the dimension of the DDL grows with time, it would be nonfeasible to search and audit the related transactions for reputation calculation even in one partition. A possible solution is to maintain additional data structures to store intermediate reputation calculations to save the computing power and time required for transaction search. We called this additional data structure as Node Status List (NSL). Each node should initialize an NSL when first connecting the ledger or a new valid period starting. Table2 presents the data field contained in each row of the list. The first column is node ID. The second is a set of tuples, and the elements recorded the calculating timestamp and consensus metric. The third is a tuple containing the interactive metric and the update timestamp.Table 2
Data field in NSL.
FieldSymbolNode IDpiIterative consensus metrict,R∗Cumulative interactive metrict,R+,R−Now, we consider the reputation update method based on the intermediate data structure. The node can calculate the transaction weight and the vehicular reputation by searching the NSL. If a new transaction passes the verification or exceeds the threshold, each receiving node will update the specific field at local. Algorithm2 describes the transaction consensus with node status data update.Algorithm 2: Reputation update algorithm.
input: NSL, a confirmed transaction ψi, issued node pi and the node that waited to interact with pjoutput: The updated reputation μ of pj1/∗∗∗ Update NSL ∗∗∗/ Extract response nodes pj⟶i and corresponding interactive ratings yj⟶i;2for each pj⟶i in pj⟶ido3 updateNSLpj⟶it,R+,R− based on the corresponding interactive rating yj⟶i;4 ExtractR∗ in ψi and update t,R∗ to NSLpi;5/∗∗∗ Calculate Reputation ∗∗∗/ Obtain the current time tu;6 Calculate qualityσ based on NSLpjt,R+,R−;7 Select an exponential function to calculateη=f−βR∗;8 Obtain the reputationμ;9final;10returnμ;


## 5.1. Vehicular Reputation

Our DDL requires the vehicle to be a node and contributes to the ledger maintenance. Therefore, we argue that the expression of reputation needs to contain the node’s behaviors in ledger maintenance and VANET interaction. Interactive behavior refers to the quality of data that the node shares when interacting, and it is stored in the relevant transactions issued after each interaction occurs. The maintenance behavior of the ledger, we also call consensus contribution, refers to the node’s performance in ledger maintenance and is calculated by other nodes when they verify a new transaction issued by the node.In summary, when omitting the symbol of interest partitions and valid period, the reputation is(9)μ=τ1σ+τ2η,where σ and η represent the interactive quality and consensus behavior, respectively; we will discuss them in the following subsection. τ1+τ2=1; they are used to adjust the ratio of the two measures in different scenarios. For example, in the initial phase of each valid period, the ledger needs as many as possible nodes to join to maintain the transaction consensus, at this case, τ2>τ1.


### 5.1.1. Interactive Quality

To simply the discussion, we only consider the cooperating model because it can easily extend to the sharing model. Assume that a node hasM1-positive ratings and M2-negative ratings, so that all the received ratings M=M1+M2. Let Rmb+ be the positive rating that pb received at mth response at time t and Rmb− represent the negative rating. So we have
(10)Rtu+=∑t=t0tu∑m=1M1Rmb+,(11)Rtu−=∑t=t0tu∑m=1M2Rmb−,where t0 is the initial time of current valid period and tu represents the current time. The interactive quality is calculated as follows:
(12)σtu=θ1·Rtu+−θ2·Rtu−Rtu++Rtu−,where θ1 and θ2 are sensitivity weight; let R+=Rtu+,R−=Rtu−, then
(13)θ1=FR+FR++FR−,θ2=FR−FR++FR−.F· represents the sensitivity function such as Fx=x, Fx=x2, and Fx=x3; the sensitivity of the positive or negative rating in the metric of interactive quality can be controlled by θ. θ could adjust the weight of contribution rating based on the different requirements. For example, when the shared data may threaten the safety of humans, the weight of negative evaluation should be increased.


### 5.1.2. Consensus Contribution

When the node selects tips, its behavior determines its contribution to the consensus of DDL. The selections are represented by the edges and are public to all nodes, and they are important on ledger evolution. When receiving a new transactionψi issued by pb, a node needs to check the CWs of all the transaction in ψi⟶m and calculate a consensus rating Rb∗t of pb, and the calculation can be expressed by
(14)Rb∗tu=Rb∗tu−1+∑m=1m=MΘ−Ai⟶mtu,where Ai⟶mtu presents the CW of the ψi⟶m approved by ψi at time tu. If Θ−Ai⟶mtu≤0, it denotes that the issuing node selected a confirmed transaction, which represents a bad behavior, of course; otherwise, it denotes a tip is selected or there is other issued unconfirmed transaction recently, which means a good behavior. Therefore, if the node performs positively, then 0≤Rb∗tu≤1; otherwise, −1≤Rb∗tu≤0. The iterative method is used because the CW of a transaction always increases along with time. Define the metric of consensus contribution as
(15)η=f−βRb∗,where β is an attenuation factor; it can be adjusted with the ledger network change even if node pb does nothing in a time interval. Thus, the metric of consensus contribution of a node’s reputation can be calculated by auditing the local transactions at any given time.


## 5.1.1. Interactive Quality

To simply the discussion, we only consider the cooperating model because it can easily extend to the sharing model. Assume that a node hasM1-positive ratings and M2-negative ratings, so that all the received ratings M=M1+M2. Let Rmb+ be the positive rating that pb received at mth response at time t and Rmb− represent the negative rating. So we have
(10)Rtu+=∑t=t0tu∑m=1M1Rmb+,(11)Rtu−=∑t=t0tu∑m=1M2Rmb−,where t0 is the initial time of current valid period and tu represents the current time. The interactive quality is calculated as follows:
(12)σtu=θ1·Rtu+−θ2·Rtu−Rtu++Rtu−,where θ1 and θ2 are sensitivity weight; let R+=Rtu+,R−=Rtu−, then
(13)θ1=FR+FR++FR−,θ2=FR−FR++FR−.F· represents the sensitivity function such as Fx=x, Fx=x2, and Fx=x3; the sensitivity of the positive or negative rating in the metric of interactive quality can be controlled by θ. θ could adjust the weight of contribution rating based on the different requirements. For example, when the shared data may threaten the safety of humans, the weight of negative evaluation should be increased.


## 5.1.2. Consensus Contribution

When the node selects tips, its behavior determines its contribution to the consensus of DDL. The selections are represented by the edges and are public to all nodes, and they are important on ledger evolution. When receiving a new transactionψi issued by pb, a node needs to check the CWs of all the transaction in ψi⟶m and calculate a consensus rating Rb∗t of pb, and the calculation can be expressed by
(14)Rb∗tu=Rb∗tu−1+∑m=1m=MΘ−Ai⟶mtu,where Ai⟶mtu presents the CW of the ψi⟶m approved by ψi at time tu. If Θ−Ai⟶mtu≤0, it denotes that the issuing node selected a confirmed transaction, which represents a bad behavior, of course; otherwise, it denotes a tip is selected or there is other issued unconfirmed transaction recently, which means a good behavior. Therefore, if the node performs positively, then 0≤Rb∗tu≤1; otherwise, −1≤Rb∗tu≤0. The iterative method is used because the CW of a transaction always increases along with time. Define the metric of consensus contribution as
(15)η=f−βRb∗,where β is an attenuation factor; it can be adjusted with the ledger network change even if node pb does nothing in a time interval. Thus, the metric of consensus contribution of a node’s reputation can be calculated by auditing the local transactions at any given time.


## 5.2. Reputation Update

Since the dimension of the DDL grows with time, it would be nonfeasible to search and audit the related transactions for reputation calculation even in one partition. A possible solution is to maintain additional data structures to store intermediate reputation calculations to save the computing power and time required for transaction search. We called this additional data structure as Node Status List (NSL). Each node should initialize an NSL when first connecting the ledger or a new valid period starting. Table2 presents the data field contained in each row of the list. The first column is node ID. The second is a set of tuples, and the elements recorded the calculating timestamp and consensus metric. The third is a tuple containing the interactive metric and the update timestamp.Table 2
Data field in NSL.
FieldSymbolNode IDpiIterative consensus metrict,R∗Cumulative interactive metrict,R+,R−Now, we consider the reputation update method based on the intermediate data structure. The node can calculate the transaction weight and the vehicular reputation by searching the NSL. If a new transaction passes the verification or exceeds the threshold, each receiving node will update the specific field at local. Algorithm2 describes the transaction consensus with node status data update.Algorithm 2: Reputation update algorithm.
input: NSL, a confirmed transaction ψi, issued node pi and the node that waited to interact with pjoutput: The updated reputation μ of pj1/∗∗∗ Update NSL ∗∗∗/ Extract response nodes pj⟶i and corresponding interactive ratings yj⟶i;2for each pj⟶i in pj⟶ido3 updateNSLpj⟶it,R+,R− based on the corresponding interactive rating yj⟶i;4 ExtractR∗ in ψi and update t,R∗ to NSLpi;5/∗∗∗ Calculate Reputation ∗∗∗/ Obtain the current time tu;6 Calculate qualityσ based on NSLpjt,R+,R−;7 Select an exponential function to calculateη=f−βR∗;8 Obtain the reputationμ;9final;10returnμ;


## 6. Experimental Result and Analysis

We build a trip set based on the New York yellow cab [31] and extract the trajectories at daytime of several days in December 2020. The vehicle number in the evaluation scenario is a uniform distribution between 5800 and 7900 and distributed in 55 partitions. All the partitions are fixed according to predivided partitions in [31], and we filter partitions with less than 20 vehicles and merge these vehicles into nearby partitions. Figure 7 shows the distribution of the partitions and vehicles’ heat at different times of one day. We can find that vehicle numbers in different partitions at the same period are very different, and so do the number of vehicles in the same partition at different periods.Figure 7
Distribution of the partitions and the vehicle heat in different hours in Manhattan.In addition, the entry of vehicles into VANET follows the Poisson process with an average ofλ [32], so does the arrival of transactions. Assume that vehicles issuing the transactions follow the power-law distribution [33, 34] and the number of the reference vehicles for the interaction is a uniform distribution between 3 and 10. Considering the simulation is conducted in daytime, we set the system’s throughput per second (TPS) in a partition to be large and positively correlated with the number of nodes. Suppose the global arrival rate λall≤1000, and for each partition, its arrival rate λk is also allocated according to the proportion of vehicles owned by it. Thus, for any partitions in our evaluations, suppose 3<λk<86.The simulation is implemented using Python 3.8.3 in Windows 10 system with a Lenovo laptop, which has four cores and 32 GB memory. Cryptography is the Python cryptography library (v2.8) [35] and the Hashlib standard library (3.7.7) [36].


### 6.1. Convergence of the Proposed Ledger

We first investigated the convergence performance of our proposed DAG-based distributed ledger. Figure8(a) shows that the size of Lt increases quickly in the first few epochs and reaches a stable state after around 20 epochs. The main reason for the rapid accumulation of tips in the early stage is the waiting period u. After a tip is released, it will take a while to be “seen” and verified by the nodes. Meanwhile, when a new validity period begins, the node’s reputation and each metric are reset to 0.5, so the tips’ weights and the parent’s selection are very close. The transaction selection can be thought of as random in all transactions, which will cause some tips to be unable to be verified in time. However, as the number of epochs increases, the size of Lt becomes stable, which verifies the convergence performance of our proposed DAG ledger in the case of the partitioning method. In Figure 8(b), we observe the change of the size of Lt around 120th epoch though adjusting the TPS in partitions. It can be seen that the convergence performance will not be affected because of the definition of the tip and the verifying-before-issuing mechanism of the transaction; that is, when a new transaction is added, several tips need to be verified. Therefore, the increase of TPS will also improve tip verification. So, the convergence performance of our proposed DAG ledger in the case of the partitioning method was verified.Figure 8
(a) The number of tips in partitions of different sizes. (b) The number of tips vs. TPS in partitions of different sizes,epoch=120.
(a)(b)


### 6.2. Local Consistency in Multipartitions

Next, we investigated the performance of the local consistency threshold. Figure9 shows the results of the threshold changing with the number of the followed partitions. We also set the node’s participation following the power-law distribution, and only the top 20% active nodes are considered when calculating the threshold starting from the middle of a period (randomly from 40 to 60 epochs in each evaluation). The results show that the threshold increase is slow in the initial few epochs. This is because the threshold is positively correlated with the reputation of the active nodes, and it will be reset to 0.5 in the initial stage of a new validity period. Furthermore, reputation always rises slowly at the beginning of the validity period. Even the most active nodes also need to spend multiple epochs to conduct one good behavior (answering the request from others or computing the PoW for approving transactions) and reach consistency with other related nodes.Figure 9
Local consistency threshold vs. epoch,L=1.Note that in the later epochs, the threshold grows slowly at the scenario of followed fewer partitions, and this is because many nodes have left the followed partitions before their reputation accumulated high enough. However, the reputation grows faster in the scenario of following more partitions, and this is because we can observe the nodes in a more extensive range (involved more partitions), so the nodes have enough time to accumulate a sufficiently high reputation. Moreover, we summarize that some nodes (a taxi will operate for a long time and drive within some fixed partitions) can accumulate much and soon based on the power-law distribution. Therefore, the local consistency threshold is effective; short-travel nodes only need to pay attention to fewer partitions and the recent behavior of the nodes, while long-travel nodes need to pay attention to more partitions and the long-term behavior of the nodes.


### 6.3. Performance of Reputation Update

Then, we test the resiliency of our reputation representation against misbehavior of vehicles in Figure10. The misbehavior includes bad collaboration performance (obtained a lower shared rating) or selecting an old and approved transaction to attach. In Figure 10, we can see that all the schemes with different tip selection algorithms can reduce the node’s reputation below 0.5 when the node’s misbehavior ratio exceeds 50%. Besides, when the reputation is lower than 0.5, the decline is very fast, mainly caused by the bad consensus behavior. Typically, if a node becomes lazy, it would select a fixed transaction set to save its computational power. Meanwhile, the CW of any approved transaction inevitably increases (raised by the indirect approval) with epoch, and the exponential function in Formula (5) also speeds up the decline. This also provides incentives to the node to select the tip.Figure 10
Reputation vs. misbehavior ratio for one vehicle,f·=x3.Last, Figure11 shows the impact of different metrics on reputation when bad behavior accumulates. We can conclude that when there is bad sharing behavior, the reputation begins to decline rapidly, while the consensus become bad, and the downward trend is slow. This is mainly controlled by the setting of hyperparameter. We can strengthen the weight of consensus metric by adjusting the proportion of τ For example, if the sensitivity function f·=x, then the sharing metric will decrease linearly. f·=x3 can reduce some misbehavior caused by inevitable communication delay; sharing metric will begin to decline rapidly after the misbehavior exceeds the tolerance limit. In addition, when there are few numbers of the activated vehicles, the reputation system can increase the weight of the consensus metric by recommending a large τ2, so as to attract more vehicles to help verify new transactions, which is also to accumulate its own reputation (consensus metric).Figure 11
Reputation accumulation process,τ1=τ2=0.5, f·=x3.
(a)
Honest node. The node reputation is reset to 0.5 at the beginning of each validity period. When the node starts to contribute, the evaluated reputation accumulate from 0(b)
Corrupted node (fromepoch=10), the bad behavior only involves sharing part; the consensus part is normal(c)
Corrupted node (fromepoch=10), the bad behavior only involves consensus part; the sharing part is normal(d)
Corrupted node (fromepoch=10), the bad behavior involves both sharing and consensus parts


## 6.1. Convergence of the Proposed Ledger

We first investigated the convergence performance of our proposed DAG-based distributed ledger. Figure8(a) shows that the size of Lt increases quickly in the first few epochs and reaches a stable state after around 20 epochs. The main reason for the rapid accumulation of tips in the early stage is the waiting period u. After a tip is released, it will take a while to be “seen” and verified by the nodes. Meanwhile, when a new validity period begins, the node’s reputation and each metric are reset to 0.5, so the tips’ weights and the parent’s selection are very close. The transaction selection can be thought of as random in all transactions, which will cause some tips to be unable to be verified in time. However, as the number of epochs increases, the size of Lt becomes stable, which verifies the convergence performance of our proposed DAG ledger in the case of the partitioning method. In Figure 8(b), we observe the change of the size of Lt around 120th epoch though adjusting the TPS in partitions. It can be seen that the convergence performance will not be affected because of the definition of the tip and the verifying-before-issuing mechanism of the transaction; that is, when a new transaction is added, several tips need to be verified. Therefore, the increase of TPS will also improve tip verification. So, the convergence performance of our proposed DAG ledger in the case of the partitioning method was verified.Figure 8
(a) The number of tips in partitions of different sizes. (b) The number of tips vs. TPS in partitions of different sizes,epoch=120.
(a)(b)


## 6.2. Local Consistency in Multipartitions

Next, we investigated the performance of the local consistency threshold. Figure9 shows the results of the threshold changing with the number of the followed partitions. We also set the node’s participation following the power-law distribution, and only the top 20% active nodes are considered when calculating the threshold starting from the middle of a period (randomly from 40 to 60 epochs in each evaluation). The results show that the threshold increase is slow in the initial few epochs. This is because the threshold is positively correlated with the reputation of the active nodes, and it will be reset to 0.5 in the initial stage of a new validity period. Furthermore, reputation always rises slowly at the beginning of the validity period. Even the most active nodes also need to spend multiple epochs to conduct one good behavior (answering the request from others or computing the PoW for approving transactions) and reach consistency with other related nodes.Figure 9
Local consistency threshold vs. epoch,L=1.Note that in the later epochs, the threshold grows slowly at the scenario of followed fewer partitions, and this is because many nodes have left the followed partitions before their reputation accumulated high enough. However, the reputation grows faster in the scenario of following more partitions, and this is because we can observe the nodes in a more extensive range (involved more partitions), so the nodes have enough time to accumulate a sufficiently high reputation. Moreover, we summarize that some nodes (a taxi will operate for a long time and drive within some fixed partitions) can accumulate much and soon based on the power-law distribution. Therefore, the local consistency threshold is effective; short-travel nodes only need to pay attention to fewer partitions and the recent behavior of the nodes, while long-travel nodes need to pay attention to more partitions and the long-term behavior of the nodes.


## 6.3. Performance of Reputation Update

Then, we test the resiliency of our reputation representation against misbehavior of vehicles in Figure10. The misbehavior includes bad collaboration performance (obtained a lower shared rating) or selecting an old and approved transaction to attach. In Figure 10, we can see that all the schemes with different tip selection algorithms can reduce the node’s reputation below 0.5 when the node’s misbehavior ratio exceeds 50%. Besides, when the reputation is lower than 0.5, the decline is very fast, mainly caused by the bad consensus behavior. Typically, if a node becomes lazy, it would select a fixed transaction set to save its computational power. Meanwhile, the CW of any approved transaction inevitably increases (raised by the indirect approval) with epoch, and the exponential function in Formula (5) also speeds up the decline. This also provides incentives to the node to select the tip.Figure 10
Reputation vs. misbehavior ratio for one vehicle,f·=x3.Last, Figure11 shows the impact of different metrics on reputation when bad behavior accumulates. We can conclude that when there is bad sharing behavior, the reputation begins to decline rapidly, while the consensus become bad, and the downward trend is slow. This is mainly controlled by the setting of hyperparameter. We can strengthen the weight of consensus metric by adjusting the proportion of τ For example, if the sensitivity function f·=x, then the sharing metric will decrease linearly. f·=x3 can reduce some misbehavior caused by inevitable communication delay; sharing metric will begin to decline rapidly after the misbehavior exceeds the tolerance limit. In addition, when there are few numbers of the activated vehicles, the reputation system can increase the weight of the consensus metric by recommending a large τ2, so as to attract more vehicles to help verify new transactions, which is also to accumulate its own reputation (consensus metric).Figure 11
Reputation accumulation process,τ1=τ2=0.5, f·=x3.
(a)
Honest node. The node reputation is reset to 0.5 at the beginning of each validity period. When the node starts to contribute, the evaluated reputation accumulate from 0(b)
Corrupted node (fromepoch=10), the bad behavior only involves sharing part; the consensus part is normal(c)
Corrupted node (fromepoch=10), the bad behavior only involves consensus part; the sharing part is normal(d)
Corrupted node (fromepoch=10), the bad behavior involves both sharing and consensus parts


## 7. Conclusion

This paper proposes a partitioned DDL for maintaining the vehicular reputation to support the trust establishment in VANET. We design the transaction for the vehicular reputation auditing using the details of interactions among vehicles. To encourage the vehicle to maintain the ledger, we design a vehicular reputation evaluation method by aggregating the contribution in vehicular interaction and ledger consensus maintenance. Besides, a reputation update method based on the consistency of transactions in one or several partitions is presented to allow any vehicle to evaluate other’s reputations anywhere and anytime. Simulation results demonstrate that our partitioned DDL is practical in real-world scenarios and achieves a better detection rate of bad behavior than the baselines with various tip selection algorithms. Future work is in progress to consider how to partition the VANET better to improve the vehicle’s safety during its trip.



---

*Source: 6833535-2022-03-23.xml*