Blockchain (BC) is increasingly applied to the Internet of Things (IoT) domains to realize decentralized IoT environments where reliable and anonymous activities can be carried out. BCs exploit a distributed ledger, which requires to be continuously synchronized and to maintain a high level of consistency. To allow BCs applied to the IoT of maintaining high levels of reliability in the network and resilience against malicious or fraudulent nodes, in the recent past has been proposed a Trust-based Optimum Neighbor Selection (TONS) algorithm able to find the Minimum Spanning Tree of the agent network with the purpose of selecting those agents which optimize communication and trustworthiness. In this paper, a new version of TONS, named TONS2, has been conceived for agent-based IoT environments to improve the overall eficiency of the TONS algorithm. The results ot the test we performed have confirmed that in terms of consumed resources TONS2 is appreciably more eficient than TONS.
The great interest generated by the Internet of Things (IoT) comes from its ability to interconnect
heterogeneous devices providing attractive functionality across a wide horizon of domains. [
Recently, several IoT applications have exploited the blockchain [
In various types of blockchains the concept of "neighbors" is relevant, particularly in decentralized and distributed ones. Nodes connect with each other as neighbors to share information, validate transactions, and maintain the security and integrity of the network. The specific terminology and role of nodes and neighbors (i.e., miners, endorsers, validators, voters, notaries, etc.) may vary depending on the type of technology and network structure.
For example, the Bitcoin mining network is designed as a peer-to-peer overlay, in which
nodes, called miners, are randomly connected. Blocks are transmitted over this network using a
multi-hop transmission scheme. In other words, a block creator broadcasts its newly mined
block to all its neighbors [
In such a scenario, it is known from the literature that a high level of consistency of a BC DL
will require a small number of neighbors per nodes and a low rate of delivery time between
neighbors [
Given this premise, the contribution of this paper consists of proposing TONS2, an improved
version of the algorithm TONS described in [
The rest of the paper is organized as follows. Section 2 presents some related work, the Section 3 introduces the native algorithm TONS, while its evolution TONS2 is described in Section 4. The experiments we have performed to evaluate the efectiveness and the eficiency of TONS2 are presented and discussed in Section 4.1. Finally, some conclusions are drown in Section 5.
Our study rely on three main elements, namely: • A BC implements a DL, on a peer-to-peer (P2P) architecture, structured in a chain of data blocks [20], where a distributed consensus protocol enables the BC without trusted third parties and in presence of unreliable actors. BCs properties are transparency, immutability, capabilities of ensuring privacy and maintaining a complete and public transaction history [21] However, BCs are considered resilient to attacks and threats, although BCs have been tampered in the past [22]. • IoT devices have generally limited computational, storage and power capabilities, conversely IoT applications need of high level of connectivity and power to manage the large volumes of data they could generate [23, 24]. • Trust and reputation systems enable qualified parties to interact and cooperate on the basis of the history about their past behaviors [25, 26].
Synergistically, BCs can support trust (i.e., reputation) systems in managing IoT networks [27] to provide them with resilience against a large variety of attacks made easier by device characteristics. For example, TrustChain [28] provides resistance against sibyl-attacks in an online IoT community by adopting a consensus mechanism that can determine the validity and integrity of transactions instead of the more usual Proof-of-Work.
In dynamic federated social IoT environments, where IoT devices can migrate into diferent environments populated by potential untrusted actors, the consequences of a bad partner choice can result to be particularly risky. To mitigate this problem, in [29] multi-agent and BC technologies exploit reputation scores (witnessed by a BC) to form groups of trusted agent-based IoT devices in each federated environment. The authors of [30] designed a BC-based trust model for IoT that dynamically aggregates information sources to compute certified reputation scores for each entity in a decentralized manner by using a multilevel approach. In [31] a distributed trust model for IoT, supported by a BC, based on connected trust domains to form end-to-end trust relationships between devices is described.
With respect to the computation of the Minimum Spanning Tree (MST) search1, a number of 1A MST is a minimum-weight tree that in a graph, connected, and with undirected arcs, has only the subset of arcs required to connect all vertices with each other by one and only one path. centralized, semi-distributed or distributed MST algorithm have been proposed [32, 33, 34, 35], also in scenarios including the presence of IoT devices and BCs. For instance, DONS [30] (Dynamic and Optimized Neighboring Search) implements a hybrid architecture where the network topology is managed by an elected peer (i.e., leader) exploiting the neighbor lists to select the best neighbors for each peer by solving a MST based on the message propagation delays. Delays of the broadcast messages can make critical the synchronization of miners to add transaction blocks. In [36] an adaptive broadcasting approach is designed for BC’s accounting services, authorization, and authentication combining transmission and data-check times. In [37] the time gap between the propagation of a winning block and the next mining competition is minimized; in particular a message propagation mechanism exploiting the closest neighbors by using the message latency.
Finally, in IoT scenarios, in [38] edge computing is used to mitigate system latency and bandwidth limitation, while edge computing security is provided by a BC that adopts a threetier network model, named BMEC, exploiting a solution utilizing neural networks. In this case, the MST search is carried out on a weighted indirect graph consisting of edge-based blocks to enhance the BC transaction speed, built based on predetermined priority rules, application type, and past behaviors of edge devices.
In this Section the original TONS algorithm will be summarized; however, a complete description of this algorithm can be found in [29].
Let = ⟨, , ⟩ be a BC network (an undirected, weighted and connected graph), where: (i) is a set of agent nodes in ; (ii) is a set of arcs , , with , ∈ representing bidirectional communication between the agents, and associated with a weight , ; (iii) is a set of weights, where , = ⟨, , , ⟩ ∈ is a tupla consisting of , > 0, named time-weight, that is the transmission time required to transmit 1 byte of data from the agents and , and , , named trust-weight, that is the mutual trustworthiness between the agents and .
Besides, let the positive value , = , · , (i.e., the product of the pair of weights above described) be the overall weight of the arc , and, similarly, let be the global overall weight (i.e., the sum of the weights of the arcs of the whole network ).
Furthermore, it is supposed that each agent ∈ knows its neighbors = ( ,1, .., ,) and their associated weights. Therefore, in the adjacency matrix of size | × | each its element will be set to , if the arc , ∈ , while a sub-network of is an undirect graph * ( * , * , * ), such that * ⊆ , * ⊆ , and * (where * will inherit the weights of for the graph ).
Finally, let a Spanning Tree of be a connected acyclic sub-graph of , with * = and | * |=| | − 1, and let a Minimum Spanning Tree of be the unique Spanning Tree having the minimum of among all the Spanning Trees of .
TONS has been developed to realize the Optimum Neighbor Selection ( ) finding the subset
ℎ = (ℎ1, ..ℎ) ∈ , ∀ ∈ underlying the BC network, such that ,ℎ ∈ , ∀ℎ ∈ ℎ.
It is executed periodically to maintain updated the list of the agents in by exploiting the
MST computations by one of agents (i.e., the leader, which is chosen by adopting approaches
like [
To implement our approach, we assume that each interaction occurring between agents (i.e., nodes) can be described from a short report, called proof. Moreover, in the BC construction we assume also that in the agent can require to the agent data for this purpose. In such a scenario, can either ask to a third node for a “recommendation” about (based on the proofs about the past interactions of with ) or it can directly require from itself a statement about its competence (both are expressed in the real domain [0, .., 1]).
Let be the “Assurance”, a real value ranging in [0, .., 1], evaluating the proofs that can show to for assuring the reliability level of the provided. To represent the trust measure of sent by to the requester about , the real value [0, .., 1] − is computed. The maximum level of assurance (i.e., 1) will be reached when all the proofs produced by to generate its recommendations about are traced through authentic and non-repudiable messages recorded on the BC itself. Conversely, the minimum value of will be obtained when all transactions will be without proof.
Finally, a “feedback” will by assigned from to if if will require data to .
Let , , , and be four mappings associated with each agent ∈ in the BC network = ⟨, , ⟩. Each mapping has an agent as input and a diferent trust measure ranging in [0, .., 1] (with 0/1 the minimum/maximum trust value), as output assigned by to .
In detail: • () is the overall trust assigned by to its interactions with . • () is the measure of the reputation assigned by to on basis of recommendations coming from the BC agents. • () is the trust weight, i.e. the weight assigned by to the reliability of the reputation communicated from to . In other words, computes the overall trust score of by considering both the trust () and the reputation (). The percentage of relevance assigned to trust versus reputation is given by (), autonomously computed by based on the level of assurance and the recommendations provided by the contacted agents. • () is the overall “score” (preference) assigned to by based on its perceived reliability and reputation of .
Moreover, a further mapping has been defined to represent the recommendations received by the agent . Specifically, a recommendation is assumed to be a pair = ⟨, ⟩, with (called recommendation value) and (called recommendation level of assurance) ranging in the real domain [0, .., 1] (where 0/1 is the minimum/maximum value). Formally, (, ) is a mapping that in input receives two agents and and in output returns the recommendation (, ) that provides to about , together with a measure of the level of assurance associated with this recommendation.
Each node will update its mappings by means of the steps:
• Step 1: Reception of the Recommendations. The agent receives recommendations
(encoded in the mapping) from the other agents in response to previous
recommendation requests. Each recommendation provided by about the agent is stored in a
recommendation message consisting of a tuple ⟨, ⟩, whose elements are stored by in
its mapping (, ). and (, )., respectively.
• Step 2: Computing the T mapping. updates the mapping T for any agent with
which has interacted and, as a result, has issued one or more feedback for contributions
provided by . These feedback, stored in the mapping (), represent the quality
of the collaboration that provided to during the -th by real values ranging in [
() = 1 ∑︁ ()
=1 At each step, is updated by averaging the value of at the previous step − 1 and that computed at the new step , denoted by , as:
() = · (− 1)() + (1 − ) · ()
where is a real value ranging in [
|| − 1 • Step 4: Computation of S. The agent computes the overall score () in the agent by considering both the trust () and the reputation (), while the value of the mapping () weights the relevance of the service reliability with respect to reputation: () = () · () + (1 − ()) · () • Step 5: Sending the mapping S to the leader. Each agent sends its mapping to the leader of . • Step 6: Computation of ONS. The leader L exploits Prim’s approach [40] to find the by computing both the time-weight , and the trust-weight , of the arc , ∈ , as the arithmetic mean between the () and (). Finally, from the MST then computes its and sends it to the agents belonging to the ONS that, in turn, will forward it to their neighbors.
At each step, the agent exploits the mapping to select the most suitable candidates to require for collaboration. We highlight that the usage of TONS introduces the time cost required from the computation of the trust measures, that is generated realized during the transactions performed in the network.
The TONS algorithm has been designed to compute the ONS from the MST, but it is an expensive procedure in terms of computational, storage and power resources, which is an aspect relevant in presence of IoT devices and, particularly, when they are light, and poorly equipped.
From the experiments carried out to test TONS, we observed that the set of best neighbor agents was not subject to sudden changes in its composition. Consequently, an updated version of this algorithm, called TONS2, was developed to reduce the computational, storage and power costs required by TONS to the IoT devices, but without significantly impacting on the quality of the neighbor selection process. To this purpose, in TONS2 an heuristic strategy has been introduced to compute a new ONS only: (i) after each consecutive blocks validated in the DL, with > 1, (we call “batch” this sequence of blocks to validate); (4) (5) (ii) when the overall score of each agent belonging to the agent set decreases more than a ifxed percentage; (iii) when the communication time occurring between two agents increases more than a fixed percentage; (iv) when a time threshold, meaning the maximum time allowed to complete a batch, is elapsed.
Therefore, let ∆ and ∆ be the thresholds defining the percentages of maximum loss of score and communication quality respectively, and let be the maximum time imposed to complete a batch.
It is evident as TONS2 could save IoT resources by confirming the agent set without modifying the trust-based ONS search algorithm of TONS. In detail, for each batch the leader will execute the algorithm of TONS with the first block to validate. Then for each subsequent block in the batch to be validated, the leader will preemptively check whether the overall score and the weight-time parameter (both referred to the previous process of block validation) will respect the constraints imposed by ∆ and ∆ , and the time is not elapsed. If the constraints are met then the leader will initiate a new block validation process, otherwise it will proceed to update all mappings (see below) and will perform the selection of a new set of agents.
Unfortunately, this procedure may cause a side efect on agent trust values due to the fact that the same set of agents will validate multiple consecutive blocks in the DL. In fact, by choosing the same set of agents several times, they will gain an important advantage over the rest of the agent community, having more opportunities to increase their trustworthiness. This implies more chances to be chosen for new block validation processes than the other agents.
Summarizing, the TONS2 strategy will be the following: • Let be the loop counter of the batch ranging in [1, .., ]. For = 1 the mappings , , , , and are copied in * , * , * , * , * and * . • After each other validation block process in the batch only * , * , * , * , * and * will be updated as described in Section 3.1.2 and for each pair of agents and , belonging to the exploited agent set, then: – If ()* >= (1 − ∆ ) · () && is not elapsed && < , then a new interaction in the batch will be performed and will be set to + 1; – If ()* < (1 − ∆ ) · () | | is elapsed | | = , then the batch will end (i.e., will be completed) and a new ONS computation will be executed by the leader; • When in the batch there are not new blocks to validate then the mapping , and will be updated as follows: = + ( − * )/; = + ( − * )/; = * .
In terms of computational complexity, the batch procedure of TONS2 and TONS, for each new iteration in the batch after the first block, have complexities of (| |2) and (| |3), respectively. Therefore, each time that in a batch the ONS computation is not performed because the agent set is confirmed, a significant amount of resources is saved.
The batch procedure above describes is formally presented as a pseudo-algorithm in Algorithm 1.
This Section describes the experiments we performed to evaluate the advantages given by
TONS2 with respect to TONS. The interested reader can found a more detailed analysis of the
efectiveness and eficiency of TONS in [
To carry out these experiments we adopted the same computational configuration, i.e. an
ASUS PC equipped with an Intel i7 CPU (8-Cores, 7GHz), 32 GB DDR4-SDRAM, 1 TB of SSD
and Windows-11 OS. Several experiments by using random network models belonging to
the Barabási–Albert (BA) and Erdős–Rényi (ER) network models [
The results obtained bv the performed comparison between the TONS and TONS 2 algorithms are presented in the Tables 1 and 2 and graphically depicted in Figures 1 and 2 for the BA and RE network models and diferent batch dimensions. To permit a proper evaluation of the results, the average times (in seconds) have been reported for only those simulations that completed all the blocks assigned to them. Such results show that the advantage in time introduced by number of nodes average neighbors TONS (3 blocks) TONS2 (k=3) TONS (4 blocks) TONS2 (k=4) TONS (5 blocks) TONS2 (k=5)
TONS2 with respect to TONS increases with both the network size and the batch dimensions. This confirmed our expectations.
The consistency of a DL is a fundamental aspect of BC systems where the propagation of shared data in the shortest way and the optimization for the neighbor selection for each agent play a relevant role, particularly in IoT scenarios.
In our previous work [
To improve the computational complexity of TONS, we added in TONS an heuristic strategy to avoid of computing a new set of agents for each new block to validate. To test the benefits provided from this new version of TONS, called TONS2, we compared these two algorithms by executing some simulations on BA and ER network models for diferent dimensions of the batch of validating blocks. The obtained results have shown that TONS2 is capable to save important amount of computational, storage and power resources (a desired feature in an IoT context) with a minimal performance detriment, particularly important in presence of IoT devices poorly equipped. physics 74 (2002) 47. [18] S. Chatterjee, P. Diaconis, Estimating and understanding exponential random graph models, The Annals of Statistics 41 (2013) 2428–2461. [19] J. F. Mikalsen, Firechain: An eficient blockchain protocol using secure gossip, Master’s thesis, UiT Norges arktiske universitet, 2018. [20] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, Decentralized Business
Review (2008) 21260. [21] Q. Zhou, H. Huang, Z. Zheng, J. Bian, Solutions to scalability of blockchain: A survey,
Ieee Access 8 (2020) 16440–16455. [22] X. Li, P. Jiang, T. Chen, X. Luo, Q. Wen, A survey on the security of blockchain systems,
Future Generation Computer Systems 107 (2020) 841–853. [23] A. Reyna, C. Martín, J. Chen, E. Soler, M. Díaz, On blockchain and its integration with iot.
challenges and opportunities, Future generation computer systems 88 (2018) 173–190. [24] X. Zhou, W. Liang, I. Kevin, K. Wang, L. T. Yang, Deep correlation mining based on hierarchical hybrid networks for heterogeneous big data recommendations, IEEE Transactions on Computational Social Systems 8 (2020) 171–178. [25] Z. Yan, P. Zhang, A. V. Vasilakos, A survey on trust management for internet of things,
Journal of network and computer applications 42 (2014) 120–134. [26] G. Fortino, L. Fotia, F. Messina, D. Rosaci, G. M. L. Sarné, Trust and reputation in the internet of things: State-of-the-art and research challenges, IEEE Access 8 (2020) 60117–60125. [27] R. Kumar, R. Sharma, Leveraging blockchain for ensuring trust in iot: A survey, Journal of
King Saud University-Computer and Information Sciences (2021). [28] Z. Huang, X. Su, Y. Zhang, C. Shi, H. Zhang, L. Xie, A decentralized solution for iot data trusted exchange based-on blockchain, in: 2017 3rd IEEE International Conference on Computer and Communications (ICCC), IEEE, 2017, pp. 1180–1184. [29] G. Fortino, F. Messina, D. Rosaci, G. M. L. Sarné, Using blockchain in a reputation-based model for grouping agents in the internet of things, IEEE Transactions on Engineering Management 67 (2019) 1231–1243. [30] B. Shala, U. Trick, A. Lehmann, B. Ghita, S. Shiaeles, Blockchain and trust for secure, enduser-based and decentralized iot service provision, IEEE Access 8 (2020) 119961–119979. [31] R. Di Pietro, X. Salleras, M. Signorini, E. Waisbard, A blockchain-based trust system for the internet of things, in: Proceedings of the 23nd ACM on symposium on access control models and technologies, 2018, pp. 77–83. [32] C. F. Bazlamaçcı, K. S. Hindi, Minimum-weight spanning tree algorithms a survey and empirical study, Computers & Operations Research 28 (2001) 767–785. [33] S. Ruzika, H. W. Hamacher, A survey on multiple objective minimum spanning tree problems, in: Algorithmics of Large and Complex Networks, Springer, 2009, pp. 104–116. [34] G. Pandurangan, P. Robinson, M. Scquizzato, et al., The distributed minimum spanning tree problem, Bulletin of EATCS 2 (2018). [35] P. C. Pop, The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances, European Journal of Operational Research 283 (2020) 1–15. [36] F. Y.-S. Lin, C.-H. Hsiao, Y.-F. Wen, Y.-C. Su, Adaptive broadcast routing assignment algorithm for blockchain synchronization services, in: 2018 Tenth International Conference on Ubiquitous and Future Networks (ICUFN), IEEE, 2018, pp. 487–492. [37] W. Bi, H. Yang, M. Zheng, An accelerated method for message propagation in blockchain networks, arXiv preprint arXiv:1809.00455 (2018). [38] G. Li, X. Ren, J. Wu, W. Ji, H. Yu, J. Cao, R. Wang, Blockchain-based mobile edge computing system, Information Sciences 561 (2021) 70–80. [39] R. Antwi, J. D. Gadze, E. T. Tchao, A. Sikora, H. Nunoo-Mensah, A. S. Agbemenu, K. O.-B.
Obour Agyekum, J. O. Agyemang, D. Welte, E. Keelson, A survey on network optimization techniques for blockchain systems, Algorithms 15 (2022) 193. [40] R. C. Prim, Shortest connection networks and some generalizations, The Bell System Technical Journal 36 (1957) 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x.