A Blockchain Based Truthful Incentive Mechanism for Distributed P2P Applications

In distributed peer-to-peer (P2P) applications, peers self-organize and cooperate to effectively complete certain tasks such as forwarding files, delivering messages, or uploading data. Nevertheless, users are selfish in nature and they may refuse to cooperate due to their concerns on energy and bandwidth consumption. Thus each user should receive a satisfying reward to compensate its resource consumption for cooperation. However, suitable incentive mechanisms that can meet the diverse requirements of users in dynamic and distributed P2P environments are still missing. On the other hand, we observe that Blockchain is a decentralized secure digital ledger of economic transactions that can be programmed to record not just financial transactions and Blockchain-based cryptocurrencies get more and more market capitalization. Therefore in this paper, we propose a Blockchain based truthful incentive mechanism for distributed P2P applications that applies a cryptocurrency such as Bitcoin to incentivize users for cooperation. In this mechanism, users who help with a successful delivery get rewarded. As users and miners in the Blockchain P2P system may exhibit selfish actions or collude with each other, we propose a secure validation method and a pricing strategy, and integrate them into our incentive mechanism. Through a game theoretical analysis and evaluation study, we demonstrate the effectiveness and security strength of our proposed incentive mechanism.

SECTION I. Introduction

Peer-to-Peer (P2P) applications are featured by distributed architectures that partition tasks or work loads between peers without a trusted authority. Peers self-organize and collaborate in certain tasks such as forwarding files, delivering messages, or uploading data. Example P2P applications include mobile data offloading that allows mobile users to cooperatively deliver cellular network data by exploiting complementary network technologies (e.g., WiFi and femtocell) [1], Delay Tolerant Social Network (DTSN) [2] where users opportunistically forward messages for others that share common interests by following a store-carry-forward mechanism, and mobile crowdsensing in which smartphone users collaboratively upload data for the purpose of reducing energy consumption and mobile data cost [3].

The effectiveness of data transfer, packet forwarding, or data collection in the P2P applications mentioned above relies on the cooperation of mobile users. As data transmissions in such P2P applications often happen in an opportunistic manner, uncooperative behaviors would lead to low delivery success ratio and long delivery latency. On the other hand, autonomous mobile users may exhibit selfish behaviors, refusing to cooperate in data transmissions for the concerns on energy and bandwidth consumption. Therefore the participating users should be provided with enough rewards for cooperation. However, the properties of P2P applications bring challenges into the design of an incentive mechanism [4], [5]. First, most P2P applications exploit opportunistic connections among mobile users without knowing who will be the next hop and how many users will get involved; thus it is hard to know who will get rewarded and how many rewards shall be paid. Second, in a distributed environment, users may not believe that they can get their rewards as there is no pre-established trust between each other. Moreover, the uncontrolled environment may lead to some disorders in an incentive system. Finally, users may have different valuations on consumed resources and different requirements on the returns.

Many incentive mechanisms have been proposed and implemented, including the reputation systems, the Tit-for-Tat schemes, and the credit based approaches. A reputation system [6], [7] can help a user identify uncooperative peers by monitoring the behaviors of its neighbors during data transmissions and propagating the uncooperative reputation throughout the network. Such systems generally lack the considerations on a formal specification and analysis of the incentive types and on how to define the reputation of a new user. Tit-for-Tat schemes [8], [9] stimulate mobile users to cooperate by exchanging equal services among them based on what contributions they have done for others. Each user receives as much service as it has done for its neighbors based on its history behavior. These schemes are restricted to applications with long session durations that can provide many opportunities for reciprocation between pairs of users. Another challenge of Tit-for-Tat is its hardness of meeting the different service requirements of the users. Credit based approaches [10], [11] provide incentives by paying the cooperative users certain amount of credit or virtual money. Such approaches could be the most promising due to their explicit and flexible incentive methods; nevertheless, most credit based incentive schemes either rely on a central trusted authority or do not give an explicit digital currency system that is provably secure, leading to possible system collapses.

Blockchain is a decentralized digital ledger of economic transactions that can be programmed to record not just financial transactions, and it has the advantages of transparency, security and speed [12]–​[14]. Blockchain-based cryptocurrencies have recently gained a noticeable popularity, and their current market capitalization is over $566 billion. The security of Blockchain depends on a majority of the computing power instead of a central authority, thus eliminating the risks of one taking control over the system, generating inflation, or completely shutting down the system. In this paper, we exploit Blockchain transactions to incentivize users to cooperate in P2P applications.

The basic idea of our incentive scheme is to employ Blockchain transactions to reward those intermediate nodes that contribute to a successful delivery from the sender to the receiver. If an intermediate node helps transmit the data, the next-hop node sends it a signed acknowledgement which is used as a proof of getting the rewards. The miners in the Blockchain P2P system are in charge of verifying whether there is a successful delivery from the sender to the receiver, and examining the validity of the signed acknowledgements provided by the cooperative intermediate nodes in a successful delivery. The Blockchain P2P system is an independent system from P2P applications, the transactions generated in P2P applications will send to the miners in the Blockchain P2P system for the verification. This brings another concern: if a miner can see the content of a signed acknowledgement, she can disguise as a cooperative intermediate node to get the payment. To overcome this problem, we extend the Blockchain transaction syntax to support a secure validation of the acknowledgement by using commutative encryptions. We also propose a pricing strategy to defend the possible attacks resulted from selfish users and to prevent their collusion.

The major contributions of the paper are summarized as follows:

• We design a Blockchain-based truthful incentive mechanism that can meet the diverse requirements of users in dynamic and distributed P2P environments.

• We introduce a secure validation method to keep the to-be-verified content secret from the miners in the Blockchian P2P system.

• We propose a pricing strategy to prevent selfish users from exhibiting selfish actions and to defend the collusion attacks resulted from them.

• We further employ a game theoretical analysis and simulation study to demonstrate the security and efficiency of our incentive mechanism.

The remainder of the paper is structured as follows. Section II outlines the related work. In Section III, we introduce the Blockchain P2P system and the basic cryptographic primitives employed in this paper. Our incentive scheme is detailed in Section IV, followed by a comprehensive security analysis and evaluation in Section V. The paper is concluded in Section VI.

SECTION II. Related Work

The incentive schemes for P2P applications fall into three categories: Reputation, Barter (Tit-for-Tat), and Credit (virtual money).

A. Reputation-Based Approaches

In a reputation system [6], [7], [15], [16], each user is given a score that can be interpreted as the probability of an entity behaving honestly. Such a system provides us with information regarding the honesty of the peers, therefore can be utilized to identify misbehaving users. For example, a watchdog is used by a user in [16] to monitor the behavior of each neighbor to make sure that the neighbor forwards others’ data. If misbehaviors are detected, the user broadcasts the uncooperative reputation of the neighbor to other users in the network. Burak et al. [15] combined centralized reputation-based evaluation with collaborative reputation values based on votes. Reputation systems generally suffer from the following drawbacks: i) no formal specification and analysis of the types of the incentives is provided [10]; ii) the possibility of selfish users colluding with each other to maximize their welfare is generally ignored; and iii) the reputation-based approaches are known to be vulnerable to Sybil attacks [17] and whitewashing attacks [18].

B. Tit-for-Tat Schemes

Barter (Tit-for-Tat) based schemes [8], [9], [19] stimulate mobile users to cooperate by exchanging equal services based on what contributions they have done for others. In [8], Buttyan et al. proposed the use of pair-wise Tit-for-Tat (TFT) as an incentive mechanism for DTNs, in which each user estimates the contribution levels of its neighbors based on their behaviors in history, and then forwards as much traffic to its neighbors in accordance with their contribution levels. Parisa et al. [9] used the T-Chain incentive mechanism to discourage free-riding in video streaming applications. Tit-for-Tat schemes are restricted to applications with long session durations that can provide many opportunities for reciprocation between pairs of users [20]. Another challenge of Tit-for-Tat is its hardness to meet the different service requirements of the users.

C. Credit-Based Schemes

In Credit based systems [10], [11], [21]–​[24], a central authority assigns certain virtual money to each user. When a user needs others’ help (for example, to forward a message), it should pay the helper certain amount of virtual money. As the amounts of payments rely on the reports of the users, a selfish user may attempt to cheat the system to maximize its expected welfare. For example, a selfish node may withhold its acknowledgement, or collude with other nodes to forge acknowledgements, if such actions can maximize its welfare. Some effort has been made to counter such cheating behaviors. Zhong et al. [10] proposed a cheat-proof, credit-based system for stimulating cooperation among selfish nodes in mobile ad hoc networks. Felegyhazi et al. [25] and Zhang et al. [11] developed game theory frameworks based on the use of pricing strategies. These schemes assume that a routing path between the sender and the receiver is determined before data transmission occurs. Without knowing who will be the next hop and how many users will get involved, it is hard to know who will get rewarded and how many rewards shall be paid.

Other related credit-based schemes include [22] and [21]. Zhu et al. [22] proposed a layered incentive scheme for dynamic routing in DTNs. In this scheme, the sender first generates a base-layer message containing the payment policy. Then each of the intermediate nodes who agrees with the payment policy generates a new layer based on the previous layer by appending a non-forged digital signature. After receiving all the collected layered messages, the last intermediate node sends them to a trusted center, i.e., a bank, for validation and payment assignment according to the payment policy. Obviously, this mechanism emphasizes the generation and verification of the secure layered messages but does not involve a detailed pricing strategy. Chen and Chan [21] presented a pricing strategy running on top of a given DTN routing module, which works by setting the sender’s payment and the intermediate nodes’ rewards to ensure that selfish actions do not result in larger rewards. Bogliolo et al. [26] investigated the combined use of credit and reputation-based schemes to establish ad-hoc connections. We notice that all the credit based incentive schemes rely on central trusted authorities that do not exist in P2P applications. Furthermore, no explicit virtual digital currency system that is provably secure was proposed by any credit based system. Nevertheless, lacking a secure currency system could result in a collapsed incentive mechanism, just like the economy could break down if the banking system is not secure or is out of control.

Our incentive scheme is inspired by the existing research, but is very different. It is based on the Bitcoin system whose security is directly dependent on the majority of the computing power. We propose a secure validation approach carried out by the miners in the Bitcoin system instead of a trusted third authority, and a pricing strategy for the secure Bitcoin system to defend against selfish actions and prevent collusion attacks resulted from selfish users. Compared with the existing ones, our scheme does not rely on a trusted third authority but it can incentivize each node in P2P applications to honestly follow the designed protocol.

SECTION III. Preliminaries and the Threat Model

A. Blockchain P2P System

Since Bitcoin [27] came out in 2008, its underlying technique, blockchain has attracted lots of attentions from academia and industry. Many versions of Blockchain were released as open-source softwares [12], [27], [28]. Compared with other payment systems, Blockchain is peer-to-peer, i.e. users can transact directly without a trusted authority. Each transaction in Blockchain involves a sender $A$ and a recipient $B$ who are respectively identified by their public keys $PK_{A}$ and $PK_{B}$ , and miners who verify the correctness of the transaction.

A typical transaction works for the money transfer as follows: (1) $A$ first creates a transaction $T_{x}=(T_{y},PK_{B},v,Sig_{SK_{A}}(T_{y},PK_{B},v))$ and broadcasts it to other nodes in the network, where $T_{y}$ is a previous transaction, $v$ is the amount of coins, $SK_{A}$ is $A$ ’s private key, and $Sig_{SK_{A}}(T_{y},PK_{B},v)$ is a signature on $T_{x}$ signed by $A$ ; (2) miners who maintain a chain of blocks verify if the money from transaction $T_{x}$ has not been spent by $A$ and solve a hard mining problem; (3) a miner that completes the validation and the mining problem adds the transaction to a block and broadcasts it to other nodes. Blockchain also supports a more generalized transaction [29], [30], which considers the functionality money transfer, i.e., a sender conditionally transfers its money to a receiver. The workflow of the generalized transaction is similar to the typical one, but the context of the transaction is different. The context of a generalized transaction $T_{x}=(T_{y},\pi _{x},v,\sigma)$ is shown in Fig. 1, where the in-script $\sigma$ refers to some information for validation provided by the sender of the transaction, and the output-script $\pi _{x}$ with a Boolean output refers to the recipient of the transaction. A receiver redeeming $T_{x}$ is valid only if $\pi _{x}$ evaluates to true.

FIGURE 1.

A Bitcoin transaction.

Deposit protocols [31]–​[33] have been implemented by exploiting the Blockchain P2P system, in which each user is required to initially put aside a certain amount of money, which will be paid back to the user once he/she honestly follows the protocol; otherwise the deposit is given to the other parties and compensates them for the fact that the protocol terminates prematurely. The design philosophy and features of Blockchain make it an attractive way to address the incentive challenges in peer-to-peer networks that lack trusted third parties.

B. Commutative Encryption

In this work, we employ commutative encryption as one of the basic cryptographic primitives. A commutative encryption function [34] is a family of bijections $f:M\times K \to M$ such that for a given $m\in M$ we have

$$\begin{equation*} f_{a}(f_{b}(m))=f_{b}(f_{a}(m)) \end{equation*}$$ for any $a,b\in K$ . A commutative encryption enables a plaintext to be encrypted more than once using different users’ public keys (say $a$ and $b$ ). One cannot decrypt the ciphertext $f_{b}(f_{a}(m))$ without the help of the other user. The order of the keys used in encryption and decryption do not affect the computational result. Example commutative cryptosystems include Pohligand Hellman [35] and Massey and Omura [36].

C. Threat Model and Assumptions

Fig. 2 illustrates a typical architecture of P2P applications. The system consists of senders, intermediate nodes, and receivers. Senders transmit certain files, messages, or the sensed data to the receivers with the help of the intermediate nodes. The numbers of senders and receivers are different in different P2P applications. For example, there are 1 sender and $n$ receivers in mobile data offloading, while in the context of DTN there are only 1 sender and 1 receiver. In this paper, we consider a simple case with 1 sender and 1 receiver. Our incentive scheme can be easily extended to the cases with 1 sender and multiple receivers, and then the more complex cases with multiple senders and receivers.

FIGURE 2.

P2P application system.

Data transmissions in P2P applications rely on the cooperation between intermediate nodes. To incentivize the cooperations, senders give certain rewards to the nodes that help transmit the data. In this work, we assume that nodes are selfish but would take a rational decision to maximize their profit. Specially, each node may launch the following attacks:

• Refusing to Pay: A sender can refuse to pay back the intermediate nodes when the data are successfully delivered to the receiver.

• Denying Attack: The intermediate nodes or the receiver can deny that they have received the data from other nodes, which could prevent others from getting rewarded.

• Extending/Shortenning the Path: The intermediate node can extend or shorten the path to get more reward from the sender.

• Collusion Attack: Nodes can collude with each other to maximize their profit. In this work, we only consider the collusion among intermediate nodes or between an intermediate node and the receiver. We shall address the case where the sender colludes with the receiver in our future work by considering reputation based inventive systems.

SECTION IV. Blockchain Based Truthful Incentive Mechanism

In our model, we employ the idea of credit based incentives to motivate intermediate nodes to cooperate. In a credit based scheme, incentive can be considered as a transaction. When discussing a transaction, we should figure out the following questions: (1) who pays who; (2) how to pay the bill; (2) how much the payer should pay; and (4) how to guarantee that the transaction is secure.

A. Who Pays Who?

When a sender wants to transmit a certain message to a receiver, there exist three different options to pay back the intermediate nodes. The first option is to let the receiver give rewards to all the intermediate nodes; but this approach allows malicious nodes to get high rewards by sending many fake messages. The second option is to give the rewards by both the sender and the receiver, which could suffer the same problem as the first option since the sender can collude with the intermediate nodes. The third option is for the sender to pay back the intermediate nodes when it figures out that the message is successfully delivered to the receiver, which is adopted by this work.

Another relevant question we need to answer is who should get the rewards. In this study, we choose to award only those nodes that contribute to a successful delivery, which means that an intermediate node cannot get a reward if the receiver does not receive the message correctly. To identify the intermediate nodes who help forward the message, the node in the next hop is required to send a signed acknowledgement back. Because a node is considered cooperative if and only if the node has a signed acknowledgement from its successor, it is important for an intermediate node to stimulate its successor by paying certain money to its successor for sending the signed acknowledgement.

B. How to Pay the Bill?

As mentioned before, intermediate nodes should be motivated to cooperate in a dynamic and distributed environment. In particular, a sender knows the receiver, but it does not know the route to the receiver. The sender should give rewards to the intermediate nodes who help transmit the message. Cooperative nodes can be divided into two types: negative cooperative nodes who help transmit the data but the receiver fails to receive the data, and positive cooperative nodes who help transmit the data and the receiver does successfully receive the data. In our consideration, the sender only pays back the positive cooperative nodes.

In our model, the sender employs the Blockchain P2P system to pay back the positive cooperative nodes. The workflow of the payment consists of three steps. In the first step, the sender publicizes a transmission task and makes a certain deposit that is used to pay back the positive cooperative nodes. In the second step, the sender transmits data to the receiver by opportunistic connections. In the last step, the positive cooperative nodes get their payments. For simplicity, we first discuss the case with only one positive cooperative node; then extend our scheme to the multiple positive cooperative node case.

1) One Positive Cooperative Node

Suppose that a sender $A$ sends a message $m$ to a receiver $E$ . There is only one relay node $B$ between the sender $A$ and the receiver $E$ . Let $(PK_{i}, SK_{i})$ be the public/private key pair of node $i$ , $H()$ be a hash function, $E()$ be an encryption function, and $Sig()$ be a signature function. The workflow of the payment is elaborated as follows.

• Publishing a Transmission Task: When $A$ wants to transmit data to $E$ , it first generates two random numbers $R_{1}$ and $R_{2}$ , where $R_{1}$ is used to prove that the node in the next hop receives the data correctly, and $R_{2}$ is used to prove that the receiver gets the data successfully. $A$ keeps $R_{1}$ and $R_{2}$ secret, and publishes ${h_{1}} = {E_{P{K_{A}}}}({R_{1}})$ , ${h_{2}} = H({R_{2}})$ . Then $A$ makes a deposit to commit that it will give rewards to $B$ if $B$ successfully transmits the data to the receiver $E$ . $A$ constructs a transaction $Deposi{t_{A}}$ as shown in Fig. 3.

• Data Transmission: As illustrated in Fig. 4, $A$ first sends the message $m||{E_{P{K_{E}}}}({R_{2}})||\sigma ||Si{g_{S{K_{A}}}}({R_{1}})$ to node $B$ , where ${\sigma }$ is a signature on $H(m)||{E_{P{K_{E}}}}({R_{2}})$ . At the same time, $A$ constructs a transaction $Paymen{t_{A \to B}}$ and broadcasts it to other nodes in the Blockchain P2P network for validation. Then, $B$ sends the message $m||{E_{P{K_{E}}}}({R_{2}})||{\sigma }$ to the receiver $E$ , constructs a transaction $Paymen{t_{B \to E}}$ and broadcasts it to the Blockchain P2P network. Finally, $E$ receives the message, verifies the signature ${\sigma }$ , and sends $B$ a signed acknowledgement ${E_{P{K_{E}}}}(Si{g_{S{K_{E}}}}(AC{K_{E}}))$ , which is encrypted by $B$ ’s public key $PK_{B}$ . Note that the transactions $Paymen{t_{A \to B}}$ and $Paymen{t_{B \to E}}$ represent a commitment that coins will be transferred only after the miners have verified them. The transactions in the data transmission are illustrated in Fig. 5.

• Obtaining the Payments: To redeem the rewards, $B$ and $E$ provide miners with $\{{E_{P{K_{B}}}}({ACK_{E}}),{E_{P{K_{B}}}}({R_{1}})\}$ and $\{R_{2},{E_{P{K_{E}}}}({ACK_{E}})\}$ , respectively. Then, the miners validate the transactions. $B$ and $E$ can get the rewards if and only if the following conditions are satisfied: (a)

  1. $E$ can provide the random number $R_{2}$ , which is verified by

     $$\begin{equation*} H(R_{2})=h_{2}; \end{equation*}$$

  2. $B$ can provide the random number $R_{1}$ , which is verified by

     $$\begin{equation*} {E_{P{K_{B}}}}({h_{1}}) = {E_{P{K_{A}}}}({E_{P{K_{B}}}}(R_{1})); \end{equation*}$$

  3. $B$ can provide the correct signed acknowledgement, which is verified by

     $$\begin{equation*} {E_{P{K_{B}}}}({E_{P{K_{E}}}}(AC{K_{E}})) = {E_{P{K_{E}}}}({E_{P{K_{B}}}}(AC{K_{E}})). \end{equation*}$$

FIGURE 3.

$A$ makes a deposit.

FIGURE 4.

$A$ transmits data to $E$ .

FIGURE 5.

Transactions in message transmission.

2) Multiple Positive Cooperative Nodes

In this section, we extend our scheme to a more complex case where there are multiple positive cooperative nodes. Suppose that a sender $A$ sends a message $m$ to a receiver $E$ , and $B,C,D$ are the positive cooperative nodes who help $A$ transmit the data to $E$ . The workflow of the payment is elaborated as follows.

• Publishing a Transmission Task: $A$ announces a task $A\! \to \! E:m$ and generates two random numbers $R_{1}$ and $R_{2}$ that should be kept secret. Then $A$ makes a deposit to commit that it will give the rewards to the positive cooperative nodes if the message is successfully delivered to the receiver $E$ ; otherwise $A$ would get the deposit back. The transcript of the transaction is shown in Fig. 6.

• Data Transmission: The process of the data transmission from $A$ to $E$ is illustrated in Fig. 7. $A$ first sends the message $m||{E_{P{K_{E}}}}({R_{2}})||\sigma ||Si{g_{S{K_{A}}}}({R_{1}})$ to $B$ , and constructs a transaction $Paymen{t_{A \to B}}$ . Then, $B$ , $C$ , and $D$ help $A$ transmit the message $m||{E_{P{K_{E}}}}({R_{2}})||{\sigma }$ to the receiver $E$ , and construct transactions $Paymen{t_{B \to C}}$ , $Paymen{t_{C \to D}}$ , and $Paymen{t_{D \to E}}$ , respectively. $C$ , $D$ , and $E$ send the signed encrypted acknowledgement back to $B$ , $C$ , and $D$ , respectively. Note that the transactions $Paymen{t_{A \to B}}$ , $Paymen{t_{B \to C}}$ , $Paymen{t_{C \to D}}$ , and $Paymen{t_{D \to E}}$ represent a commitment that coins will be transferred only after the miners have verified them. The Blockchain transactions in the data transmission are illustrated in Fig. 8.

• Obtaining the Payments: After the data is successfully delivered to the receiver, all the positive cooperative nodes should get the rewards by providing the miners with the proofs that they did help transmit the data. To be more specific, $B$ provides $\{{E_{P{K_{B}}}}({R_{1}}),{E_{P{K_{B}}}}({ACK_{C}}),PK_{A},PK_{C}\}$ ; $C$ provides $\{{E_{P{K_{C}}}}({ACK_{C}}),{E_{P{K_{C}}}}({ACK_{D}}),PK_{D}\}$ ; $D$ provides $\{{E_{P{K_{D}}}}({ACK_{D}}),{E_{P{K_{D}}}}({ACK_{E}}),PK_{E}\}$ ; and $E$ provides $\{R_{2},{E_{P{K_{E}}}}({ACK_{E}})\}$ . The transactions are considered to be valid if and only if the following conditions are satisfied: (a)

  1. $E$ can provide the random number $R_{2}$ , which is verified by

     $$\begin{equation*} H(R_{2})=h_{2}; \end{equation*}$$

  2. There is a route from $A$ to $E$ , and the route can be determined by the transaction chain from $A$ to $E$ , as shown in Fig. 9.

  3. $B$ can provide the random number $R_{1}$ , which can be verified by

     $$\begin{equation*} {E_{P{K_{B}}}}({h_{1}}) = {E_{P{K_{A}}}}({E_{P{K_{B}}}}(R_{1})); \end{equation*}$$

  4. $B,C,D$ can provide the correct signed acknowledgements, which are verified by

     $$\begin{align*} {E_{P{K_{B}}}}({E_{P{K_{C}}}}(AC{K_{C}}))=&{E_{P{K_{C}}}}({E_{P{K_{B}}}}(AC{K_{C}})),\\ {E_{P{K_{C}}}}({E_{P{K_{D}}}}(AC{K_{D}}))=&{E_{P{K_{D}}}}({E_{P{K_{C}}}}(AC{K_{D}})),\\ {E_{P{K_{D}}}}({E_{P{K_{E}}}}(AC{K_{E}}))=&{E_{P{K_{E}}}}({E_{P{K_{D}}}}(AC{K_{E}})). \end{align*}$$

FIGURE 6.

$A$ publishes a task and makes a deposit.

FIGURE 7.

$A$ transmits the data to $E$ .

FIGURE 8.

Transactions in a multihop message transmission.

FIGURE 9.

The transaction chain from $A$ to $E$ .

C. How Much Should the Payers Pay?

A sender should determine the payment to the positive cooperative nodes for their help to transmit its data, and each positive cooperative node needs to determine the payment to its successor for sending the signed acknowledgement. Instead of considering the two components separately, we consider the final payment to the positive cooperative nodes and the receiver. Without loss of generality, we assume that $A$ sends $m$ to $E$ via $P = (P_{1}, P_{2}, \ldots, P_{n})$ , the list of positive cooperative nodes who help the transmission. Then, the final payment to node $i$ is computed by

$$\begin{equation*} {p_{i}}=\!\begin{cases} \alpha /{2^{n - 1}}, & {\mbox {if }} i\in P, \\ \beta, & {\mbox {if }} i=E,\\ 0,& {\mbox {otherwise. }} \end{cases} \end{equation*}$$

Note that in our implementation, $A$ first makes a deposit; after determining the number of positive cooperative nodes, $A$ determines the actual amount of coins given to them, and the residual deposit will return to $A$ . For example, in the case of multiple positive cooperative nodes shown in Fig. 6, $A$ first makes a deposit of $\alpha {\mathrm{ + }}\beta$ coins. After all the positive cooperative nodes have been identified (Fig. 8), $A$ sets $\alpha '{\mathrm{ = }}\alpha /{2^{3 - 1}} = \alpha /4$ .

D. Is it Secure?

1) Cheating Behaviors of the Participants

Since selfish mobile nodes always try to maximize their utilities, they may cheat. For example, they can act as a miner to get more information from the Blockchain transactions and then launch sophisticated attacks. In particular, a receiver may have one of the three selfish actions: i) it does not send back a signed acknowledgement to its previous node or just simply sends the acknowledge to others; ii) it does not provide the validation information or provides a bogus validation information; and iii.a) it does not receive the data but falsely claims that it has received the data. An intermediate node can have another cheating behavior except the first two selfish actions mentioned above: iii.b) it does not help with transmitting the data but falsely claims that it has transmitted the data.

Note that any of the selfish actions mentioned above can be further complicated by the collusion of two or more nodes. We assume that collusion only occurs between neighbors. This is a reasonable assumption in opportunistic transmissions because a node hardly gets in contact with a non-neighbor node. Moreover, we can add a lock-time into each payment transaction, which makes it more difficult for a node to contact its non-neighbors. We consider two kinds of collusion attacks:

• A receiver colludes with its neighbors. The receiver and its neighbors can forge a bogus path from the sender to the receiver. For example, suppose that the true path is $A \to B \to C \to D \to E$ . After receiving the data from $D$ , $E$ does not send the signed acknowledgement to $D$ , or it does not provide the validation information. Instead, $E$ chooses some nodes from its neighbors to create a bogus path, i.e., $A \to E_{1} \to E_{2} \to E_{3} \to E$ .

• An intermediate node colludes with its neighbors. The intermediate node collude with its neighbors to extend or shorten the path. As shown in Fig. 10, $B$ can choose some nodes from its neighbors to create a bogus path $A \to B \to B_{1} \to B_{2} \to B_{3} \to C \to D \to E$ , or $B$ colludes with $C$ to shorten the path to obtain a new path $A \to B \to D \to E$ .

FIGURE 10.

An intermediate node colludes with its neighbors.

FIGURE 11.

Utility of a positive cooperative node.

2) Data-Transmission Game

To study the security of our incentive mechanism, we employ a static game to analyze the cooperative behaviors of the intermediate nodes. Through the Nash equilibrium results of the game, we can obtain the best strategies of the players under different pricing strategies. By setting a suitable pricing strategy, we can guarantee the security of our incentive mechanism against the selfish behaviors of the users and the collusion attacks. The model of the data-transmission game is described as follows.

a: Players

This game has $n + 1$ players, the positive cooperative nodes $P = (P_{1}, P_{2}, \ldots, P_{n})$ and the receiver $E$ .

b: Strategies

Each player $i$ has two possible actions: play honestly or play selfishly. If player $i$ plays honestly, it follows the protocol; otherwise, it plays selfishly, either behaves selfishly itself or colludes with its neighbors. We denote the strategy of node $i$ by $s_{i}$ . Then $s_{i}$ is either $Honest$ or $Selfish$ .

c: Utilities

Player $i$ can get its utility by deducting its cost from its received payment. Without colluding with its neighbors, the utility of $u_{i}$ is computed by

$$\begin{equation*} {u_{i}} = {\begin{cases} \alpha /{2^{n - 1}} - {c_{i}}, & i \in P ~{\mbox {and }} {s_{i}} = Honest,\\ \beta - {c_{E}}, & i = E ~{\mbox {and }}{s_{i}} = Honest,\\ 0, & i \in P ~{\mbox {and }} {s_{i}} = Selfish,\\ 0, & i = E ~{\mbox {and }}{s_{i}} = Selfish. \end{cases}} \end{equation*}$$ where $c_{i}$ is the cost of $i$ for transmitting the data, sending a signed acknowledgement, and providing the validation information, $c_{E}$ is the cost of the receiver $E$ for sending a signed acknowledgement and providing the validation information.

When player $i$ colludes with others, it is more complicated because the utility should consider the success probability of the collusion attack. We discuss the details in Section V. Here we present some definitions for the security analysis of our incentive scheme.

Definition 1:

The best response strategy for a player is a strategy that brings the maximum expected utility to itself, regardless of the strategies of all other players.

To meet the security requirement, we need to design an incentive mechanism to discourage playing selfishly. In other words, we should make sure that $s_{i}=Honest$ is the best response strategy for each player in the game. We detail the following two cases: without and with collusion. More definitions about collusion resistance are given as follows.

Definition 2:

An incentive mechanism is receiver-collusion-resistant if the receiver and any group of its colluding neighbors cannot increase the expected sum of their utilities by using any strategy profile other than the one in which everybody plays honestly.

Definition 3:

An incentive mechanism is intermediate-node-collusion-resistant, if any group of colluding intermediate nodes cannot increase the expected sum of their utilities by using any strategy profile other than the one in which everybody plays honestly.

Definition 4:

An incentive mechanism is secure if $s_{i}=Honest$ is the best response strategy for each player and the game is receiver-collusion-resistant and intermediate-node-collusion-resistant.

SECTION V. Security Analysis and Utility Evaluation

A. Security Analysis Without Collusion Attacks

Theorem 1:

In the data-transmission game, $s_{i}=Honest$ is the best response strategy for every player $i$ if $\alpha > {2^{n - 1}}{c_{i}}$ and $\beta > {c_{E}}$ .

Proof:

When player $i$ plays honestly, we have

$$\begin{equation*} {u_{i}} = {\begin{cases} \alpha /{2^{n - 1}} - {c_{i}}, & i \in P,\\ \beta - {c_{E}}, & i = E. \end{cases}} \end{equation*}$$

$E$ does not respond honestly (or an intermediate node $P_{i}$ does not play honestly):

• $E$ (or $P_{i}$ ) does not send the acknowledgement to its previous node $P_{n}$ ($P_{i-1}$ ) or simply sends it to another node. If $E$ ($P_{i}$ ) does not send ${E_{P{K_{n}}}}(Si{g_{S{K_{E}}}}(AC{K_{E}}))$ (${E_{P{K_{i-1}}}}(Si{g_{S{K_{i}}}}(AC{K_{i}}))$ ) to $P_{n}$ ($P_{i-1}$ ), $P_{n}$ ($P_{i-1}$ ) will not provide the validation information; thus $E$ ($P_{i}$ ) can not get the payment from the transaction $Paymen{t_{P_{n} \to E}}$ ($Paymen{t_{{P_{i-1}} \to P_{i}}}$ ). If $E$ ($P_{i}$ ) sends the acknowledgement to another node, the node can not provide the validation information of $P_{n}$ ($P_{i-1}$ ) because $P_{n}$ ($P_{i-1}$ ) keeps its acknowledgement secret by encryption, i.e., ${E_{P{K_{n}}}}(AC{K_{n}})$ (${E_{P{K_{i-1}}}}(AC{K_{i-1}})$ ). Thus, $E$ ($P_{i}$ ) can not get the payment.

• $E$ (or $P_{i}$ ) does not provide validation information or provides a bogus validation information. If $E$ ($P_{i}$ ) does not provide the validation information, $E$ ($P_{i}$ ) can not get the payment from $Paymen{t_{P_{n} \to E}}$ ($Paymen{t_{{P_{i-1}} \to P_{i}}}$ ). If $E$ ($P_{i}$ ) provides a bogus validation information, the transactions $Paymen{t_{A \to {P_{1}}}}$ ($Paymen{t_{{P_{i - 2}} \to {P_{i-1}}}}$ ) and $Paymen{t_{{P_{n - 1}} \to {P_{n}}}}$ ($Paymen{t_{{P_{i - 1}} \to {P_{i}}}}$ ) can not be verified. Thus, $E$ ($P_{i}$ ) can not get the payment.

• $E$ (or $P_{i}$ ) does not receive the data but falsely claims that it has received the data. If $E$ ($P_{i}$ ) does not receive the data, $E$ can not provide $R_{1}$ , then the transaction $Paymen{t_{A \to {P_{1}}}}$ can not be verified. Thus $E$ ($P_{i}$ ) can not get the payment. In addition, if the data is important to $E$ , cheating will damage its benefit.

As $\alpha > {2^{n - 1}}{c_{i}}$ , we have ${u'_{E}} = 0 < \beta - {c_{E}} = {u_{E}}$ and ${u'_{i}} =0 < \alpha /{2^{n - 1}} - {c_{i}} = {u_{i}}$ . Therefore, $E$ ’s ($P_{i}$ ’s) utility is reduced by playing selfishly. Therefore, if $\alpha > {2^{n - 1}}{c_{i}}$ and $\beta > {c_{E}}$ , $s_{i}=Honest$ is the best response strategy for the payer $i$ .

B. Security Analysis With Collusion Attacks

We first consider the case when $E$ colludes with its neighbors; then we analyze the case when an intermediate node colludes with its neighbors.

Theorem 2:

Our incentive mechanism is receiver-collusion-resistant if $\alpha < \beta /{q^{2}}$ , where $q$ is the probability that two arbitrary nodes encounter each other.

Proof:

We first consider the case with one conspired node; then we extend to the case of multiple conspired nodes.

• Case 1:

  Suppose $G=\{E,E_{1}\}$ is a collusion group. $G$ forges a bogus path with one positive cooperative node, i.e., $A \to E_{1} \to E$ . Let $E(u_{G})$ denote the expected sum of the utility of $G$ . Our goal is to show that

  $$\begin{equation*} E(u_{G})\le u_{E}. \end{equation*}$$

  If $E_{1}$ gets $R_{1}$ , $E$ and $E_{1}$ can get the payment from $A$ , which means that $E_{1}$ has encountered both $E$ and $A$ (with a probability of $q^{2}$ ). The expected sum of the payment of $G$ is $p_{G} = {q^{2}}(\alpha + \beta) + (1 - {q^{2}})\beta ={q^{2}}\alpha +\beta$ . Considering the cost of $E_{1}$ to provide the validation information and to communicate with $E$ , we have the expected sum of the utility of $G$ to be $u_{G}={q^{2}}\alpha +\beta -\beta -c_{E}= {q^{2}}\alpha -c_{E}$ . Thus we obtain ${u_{G}}={q^{2}}\alpha -c_{E}<\beta -c_{E}=u_{E}$ .

• Case 2:

  Suppose $G=\{E,E_{1}, \ldots,E_{n}\}$ is a collusion group. $G$ forges a bogus path with multiple positive cooperative nodes, i.e., $A \to E_{1} \to \cdots \to E_{n} \to E$ . Let $E(u_{G})$ denote the expected sum of the utility of $G$ . Our goal is to show that

  $$\begin{equation*} E(u_{G})\le u_{E}. \end{equation*}$$

  When $(A,E_{1}),(E_{1},E2),\ldots,(E_{n},E)$ encounter each other, $G$ gets the payment. The expected sum of the payment of $G$ is

  $$\begin{align*} p_{G}=&{q^{n + 1}}(n\alpha /{2^{n - 1}} + \beta) + (1 - {q^{n + 1}})\beta \\=&{q^{n + 1}}n\alpha /{2^{n - 1}} + \beta. \end{align*}$$ Deducting the cost of $G$ , we have the expected sum of the utility of $G$ : $$\begin{equation*} u_{G} = {q^{n + 1}}n\alpha /{2^{n - 1}} + \beta - n\beta -c_{E}. \end{equation*}$$ As $\alpha < \beta /{q^{2}}$ , we have $$\begin{align*} {u_{G}}=&{q^{n + 1}}n\alpha /{2^{n - 1}} + \beta - n\beta -c_{E} \\<&\frac {{{q^{n + 1}}n\beta }}{{{2^{n - 1}}{q^{2}}}} - n\beta + \beta -c_{E} \\=&({q^{n - 1}}/{2^{n - 1}} - 1)n\beta + \beta -c_{E} \\<&\beta -c_{E}=u_{E}. \end{align*}$$

Therefore, if $\alpha < \beta /{q^{2}}$ , our incentive mechanism is receiver-collusion-resistant.

Theorem 3:

Our incentive mechanism is intermediate-node-collusion-resistant.

Proof:

An intermediate node can collude with its neighbors to extend or shorten the path.

• Case 1:

  An intermediate node colludes with its neighbors to extend the path. We first Consider the case with one positive cooperative node $A \to B \to E$ . Let $G=\{B,B_{1},\ldots,B_{n}\}$ be the collusion group. $G$ extends the path to $A \to B \to B_{1} \to \cdots \to B_{n} \to E$ . Let $E(u_{G})$ denote the expected sum of utility of $G$ . Our goal is to show that

  $$\begin{equation*} E(u_{G}) \le u_{B}, \end{equation*}$$ where $u_{B}$ is the utility of $B$ to play honestly. As $B$ indeed helped $A$ transmit data to $E$ , it can get all the needed validation information from $A$ and $E$ , which means that $B$ can always launch a successful collusion attack. According to our pricing scheme, we have $$\begin{align*} E(u_{G})=&(n + 1)\alpha /{2^{n}} - {c_{B}}; \\ {u_{B}}=&\alpha - {c_{B}}. \end{align*}$$ Let $f(x) = (x + 1)/{2^{x}},\;x \ge 1$ . We have $f'(x) = {2^{ - x}}(1 - (1 + x)x) < 0$ . Thus, $f(x)$ is a monotonically decreasing function. Accordingly we have $f(n) < f(n - 1) < \ldots < f(1)$ . It is easy to see that $$\begin{equation*} E(u_{G}) = (n + 1)\alpha /{2^{n}} - {c_{B}} <\alpha - {c_{B}}=u_{B}. \end{equation*}$$ Now we consider the case with multiple positive cooperative nodes. Let $u_{B}=\alpha ' - {c_{B}}$ . We can deduce that $$\begin{equation*} E(u_{G}) = (n + 1)\alpha ' /{2^{n}} - {c_{B}} <\alpha ' - {c_{B}}=u_{B}. \end{equation*}$$

• Case 2

  An intermediate node colludes with its neighbors to shorten the path $A \to P_{1} \to \cdots \to P_{i} \to P_{i+1} \to \cdots \to P_{n} \to E$ . Let $G=\{P_{i},P_{i+1}\}$ be a collusion group. Then $G$ shortens the path to $A \to P_{1} \to \cdots \to P_{i} \to P_{i+2} \to \cdots \to P_{n} \to E$ . Let $E(u_{G})$ denote the expected sum of the utility of $G$ . Our goal is to show that

  $$\begin{equation*} E(u_{G}) \le u_{P_{i}}+u_{P_{i+1}}, \end{equation*}$$ where $u_{P_{i}}$ and $u_{P_{i+1}}$ are respectively the utilities of $P_{i}$ and $P_{i+1}$ to play honestly. As $P_{i}$ and $P_{i+1}$ indeed helped transmit the data, they can get all the needed validation information. Thus they can launch a successful collusion attack. According to our pricing scheme, we have $$\begin{align*} E({u_{G}})=&\alpha /{2^{n - 2}} - {c_{P_{i}}} - {c_{{P_{i + 1}}}}; \\ {u_{P_{i}}}=&\alpha /{2^{n - 1}} - {c_{P_{i}}}; \\ {u_{{P_{i + 1}}}}=&\alpha /{2^{n - 1}} - {c_{{P_{i + 1}}}}. \end{align*}$$ It is easy to see that $$\begin{equation*} E(u_{G}) = u_{P_{i}}+u_{P_{i+1}}. \end{equation*}$$

Therefore, our incentive mechanism is intermediate-node-collusion-resistant.

The three theorems together prove the following theorem.

Theorem 4:

Our incentive mechanism is secure if $\alpha > {2^{n - 1}}{c_{\max }}$ , $\beta > {c_{E}}$ , and $\alpha < \beta /{q^{2}}$ .

C. Evaluation

1) Overhead

We employ a laptop computer with an Intel Core i7-2640M Processor (4MB Cache, up to 2.8GHz) to implement a prototype of our system using the Crypto++5.62 library and consider a path of 5 hops, to evaluate the overhead of our incentive mechanism. The OS of the laptop is Windows 10 Pro 64. The length of a message payload is 1024 bytes, and the message digest function is MD-5. We consider three commutative encryption schemes: ElGamal with a modulus of 1024 bits, RSA with a modulus of 1024 bits, and RSA with a modulus of 3072 bits.

We first evaluate the CPU processing time. In our incentive system, the major processing overhead is the R2 encryption operation, the message and R1 signing operations, and the transaction generating operation by the sender, the ACK signing and encryption operation (or the R1 decryption operation) and the transaction generating operation by each intermediate node, the message verification operation, the R2 decryption operation, and the ACK signing and encryption operation by the receiver, and the verification operation by the miners. The columns of Table 1 report the CPU processing time of the sender, an intermediate node (average), the receiver, and a miner. We observe that RSA has a much smaller overhead. Therefore if reducing overhead is the major objective, RSA is a better implementation choice. Compared with the scheme proposed by Zhu et al. [22], the CPU processing time of the sender in our approach is slightly larger, the average CPU processing time of the intermediate node is slightly smaller, and the CPU processing time of the receiver is smaller.

TABLE 1 The CPU Processing Time

We next evaluate the bandwidth and storage requirements. Compared with the opportunistic routing protocols introduced in [37] and [38] but without any incentive mechanism, the major increased message overhead includes the encrypted R2, the signed R1, and the signed and encrypted ACK. For ElGamal and RSA with a modulus of 1024 bits, the encrypted R2 takes about 128 bytes, the signed R1 takes about 128 bytes, the signed and encrypted ACK takes about 128 bytes; for RSA 3074 bits, the encrypted R2 takes about 384 bytes, the signed R1 takes about 384 bytes, and the signed and encrypted ACK takes about 384 bytes. The storage requirement for the Blockchain transactions is analyzed as follows. For RSA 1024 and ElGamal 1024, each transaction requires at least 1 byte for the previous transaction reference, 128 bytes for the in-script, 1 byte for the Bitcoin value, and 128 bytes for out-script; adding up together we get 258 bytes for a minimum-sized Bitcoin transaction. For RSA 3074, each transaction requires 384 bytes for the in-script and 384 byes for the out-script, resulting in a 770-byte minimum-sized Bicoin transaction. Note that the process of miners verifying the transactions does not affect the cost of the routing protocols, and the throughput of processing the transaction is determined by Blockchain consensus algorithm [12].

2) Utility Evaluation

In this section we evaluate the utilities of the players under different strategies. We set $\alpha = 16 \times {10^{ - 3}}$ coins, $\beta = 0.5 \times {10^{ - 3}}$ coins, ${c_{E}} = 0.1 \times {10^{ - 3}}$ coins, and ${c_{P_{i}}} = 1 \times {10^{ - 3}}$ coins. The number of positive cooperative nodes is varied from 1 to 10 with a step size of 1, and the encounter probability is increased from 0 to 0.5 with a step size of 0.05.

a: Utility of a Positive Cooperative Node

Fig. 12 shows the impact of the number of positive cooperative nodes and the playing strategies on the utility of a positive cooperative node. We observe that the node’s utility indeed demonstrates diminishing returns when the number of positive cooperative nodes increases. Extending the length of the path ($k=3,k=5$ ) leads to the drop of $P_{i}$ ’s utility. When $\alpha > {2^{n - 1}}{c_{P_{i}}}$ , i.e., $n<5$ , playing honestly is the best response strategy for $P_{i}$ because the utility by playing honestly is larger than that by playing selfishly. When $n>=5$ , the $P_{i}$ ’s utility is below zero, which is hard to happen as rational participants want to gain benefits.

FIGURE 12.

Utility of the receiver.

b: Utility of the receiver

Fig. 12 shows the impact of the encounter probability and the playing strategies on the utility of $E$ . We observe that the success rate of collusions is higher when the encounter probability is higher. The utility obtained when $E$ colluding with $k=1$ intermediate node is larger than that with multiply intermediate nodes, i.e., $k=3$ . When $\alpha < \beta /{q^{2}}$ , i.e., $q<0.177$ , the utility by playing honestly is larger than that by playing selfishly, which is in accordance with our theoretical analysis results.

SECTION VI. Conclusion and Future Research

In this paper, we propose a Blockchain based incentive mechanism that can meet the diverse requirements in a dynamic and distributed P2P environment. In our incentive mechanism, intermediate nodes who contribute to a successful delivery can obtain rewards from Blockchain transactions. The transactions are verified by the miners in a secure way by using commutative encryptions. A pricing strategy is proposed to guarantee the security of our incentive mechanism. We also employ a static game model to demonstrate the security strength of our incentive mechanism.

In our future research, we will consider the issue of a sender colluding with its receiver. One possible solution is to introduce reputation into our incentive scheme. In this reputation based incentive scheme, the collusion group of the sender and the receiver will be put into a blacklist by the accusation of the intermediate nodes. We also will consider the contradiction of incentive and privacy in our scheme. We will bring certain cryptographic extensions such as zero-knowledge proof and blind signature to Blockchain for achieving fully anonymous currency transactions.