Applied Science, Faculty of
Engineering, School of (Okanagan)
DSpace
UBCO
Leng, Junyuan
Master of Applied Science - MASc
University of British Columbia
The architecture of integrating blockchain with Industry 4.0 IoT network has emerged in recent years. Industry 4.0 refers to the new concept of intelligent manufacturing paradigm, including Internet of Things (IoT), Cloud computing and Cyber-Physical System (CPS). Blockchain is a decentralized, distributed ledger system used to record transactions across multiple participants. Blockchain offers a way of recording data that is designed to be secure, reliable and auditable, which makes it a preferred solution for securing IoT network. However, traditional blockchain suffers from storage scalability issue because each blockchain node stores the entire blockchain. The storage scalability problem can be even worse when blockchain is used in IoT network due to the high volume of data generated by massive number of IoT sensors. In this thesis, we propose a distributed storage architecture for blockchain based on erasure coding. The property of erasure coding makes it possible to greatly reduce storage overhead for each node without affecting the overall data integrity. Furthermore, to minimize the latency of rebuilding data in this distributed storage architecture, we formulate a latency-cost trade-off optimization problem and propose an efficient and scalable algorithm. Simulation results show that our architecture can achieve up to 80% latency reduction compared with other widely used distributed storage architectures. In addition, our architecture can save up to 90% storage space for each node, which removes the largest obstacle for integrating blockchain into IoT network.
Latency-Optimized DistributedStorage for Blockchain in IoT NetworkbyJunyuan LengB.Eng., Xi’an Jiaotong University, 2013M.Eng., Xi’an Jiaotong University, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Electrical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)March 2019© Junyuan Leng, 2019The following individuals certify that they have read, and recommend to the Faculty of Graduateand Postdoctoral Studies for acceptance, the thesis entitled:Latency-Optimized Distributed Storage for Blockchain in IoT Networksubmitted by Junyuan Leng in partial fulfillment of the requirements forthe degree of Master of Applied Science in Electrical EngineeringDr. Chen Feng, School of EngineeringSupervisorDr. Julian Cheng, School of EngineeringCo-supervisorDr. Zheng Liu, School of EngineeringSupervisory Committee MemberDr. Yang Cao, School of EngineeringSupervisory Committee MemberDr. Warren Hare, School of Arts and SciencesUniversity ExamineriiAbstractThe architecture of integrating blockchain with Industry 4.0 IoT network has emerged in recentyears. Industry 4.0 refers to the new concept of intelligent manufacturing paradigm, includingInternet of Things (IoT), Cloud computing and Cyber-Physical System (CPS). Blockchain is adecentralized, distributed ledger system used to record transactions across multiple participants.Blockchain offers a way of recording data that is designed to be secure, reliable and auditable,which makes it a preferred solution for securing IoT network. However, traditional blockchainsuffers from storage scalability issue because each blockchain node stores the entire blockchain.The storage scalability problem can be even worse when blockchain is used in IoT network due tothe high volume of data generated by massive number of IoT sensors.In this thesis, we propose a distributed storage architecture for blockchain based on erasurecoding. The property of erasure coding makes it possible to greatly reduce storage overhead foreach node without affecting the overall data integrity. Furthermore, to minimize the latency ofrebuilding data in this distributed storage architecture, we formulate a latency-cost trade-off opti-mization problem and propose an efficient and scalable algorithm. Simulation results show that ourarchitecture can achieve up to 80% latency reduction compared with other widely used distributedstorage architectures. In addition, our architecture can save up to 90% storage space for each node,which removes the largest obstacle for integrating blockchain into IoT network.iiiLay SummaryA new intelligent manufacturing paradigm, which is often referred to as Industry 4.0, is emergingin recent years. To meet with the data security and data integrity requirements of Industry 4.0, wepropose an architecture integrating Industry 4.0 with a reliable, immutable and secure data record-ing technology called blockchain. Blockchain is a decentralized, distributed ledger system used torecord transactions across multiple participants. Built on the basis of public key encryption, con-sensus mechanism and full decentralization, blockchain offers strong data privacy protection anddata security assurance in a distributed manner. However, simply integrating Industry 4.0 withblockchain is not practical because traditional blockchain suffers from storage scalability issue. Tosolve the blockchain storage scalability issue, we propose a distributed storage architecture forblockchain which greatly reduces storage space requirement (up to 90% less storage) without af-fecting the overall data integrity. Furthermore, to minimize the data access latency of our proposedstorage architecture, we formulate a latency-cost trade-off optimization problem and propose anefficient and scalable algorithm to solve this optimization problem. Simulation results show thatour architecture can achieve up to 80% latency reduction.ivPrefaceThis thesis is based on the research work conducted under the supervision of Dr. Chen Feng andDr. Julian Cheng in the School of Engineering at The University of British Columbia, OkanaganCampus.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Chapter 3: Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.1 Blockchain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 Blockchain Security Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2.1 Immutability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2.2 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2.3 Auditable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3 Blockchain IoT Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Chapter 4: System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114.1 Fog Layer Blockchain Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11viTABLE OF CONTENTS4.2 IoT Layer Blockchain Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Chapter 5: System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165.1 Placement Subproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.2 RS Coding Parameter Subproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185.2.1 Delay Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205.2.2 Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Chapter 6: Optimization Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236.1 Convex Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236.2 Single File Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256.3 Two-File Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.3.1 Time Complexity Analysis of Two-File Case . . . . . . . . . . . . . . . . . . . 326.4 Multiple-File Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326.4.1 Time Complexity Analysis of Multiple-File Case . . . . . . . . . . . . . . . . 32Chapter 7: Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.1 Simulation Parameter Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.1.1 Selection of µ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347.1.2 Selection of γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357.1.3 Selection of cost coefficient c . . . . . . . . . . . . . . . . . . . . . . . . . . . 357.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Chapter 8: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44viiList of FiguresFigure 3.1 Blockchain data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Figure 4.1 Integration architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Figure 4.2 Fog layer blockchain architecture . . . . . . . . . . . . . . . . . . . . . . . . . 12Figure 4.3 IoT layer blockchain verification mechanism . . . . . . . . . . . . . . . . . . 14Figure 5.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Figure 5.2 Water-filling algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Figure 6.1 Upper and lower bounds tightness . . . . . . . . . . . . . . . . . . . . . . . . 24Figure 6.2 Plot of f ′(x) when k = 90, l = 10, γ = µ = 1 . . . . . . . . . . . . . . . . . . 26Figure 6.3 Plot of f ′(x) when c = 0, k = 100,m = 400, γ = µ = 1 . . . . . . . . . . . . . 27Figure 6.4 Plot of f ′(x) when c = 0.004, k = 100,m = 400, γ = µ = 1 . . . . . . . . . . . 27Figure 6.5 Plot of f ′(x) when c = 0.2, k = 100,m = 400, γ = µ = 1 . . . . . . . . . . . . 28Figure 6.6 Plot of x∗1 = k1 + l1, x∗2 = m− x∗1 . . . . . . . . . . . . . . . . . . . . . . . . . 29Figure 6.7 Plot of x∗2 = k2 + l2, x∗1 = m− x∗2 . . . . . . . . . . . . . . . . . . . . . . . . . 30Figure 6.8 Plot of critical condition when x∗1 + x∗2 = m . . . . . . . . . . . . . . . . . . . 30Figure 7.1 System trade-off when s+ t = 0.1 . . . . . . . . . . . . . . . . . . . . . . . . 36Figure 7.2 System trade-off when s+ t = 0.5 . . . . . . . . . . . . . . . . . . . . . . . . 37Figure 7.3 System trade-off when s+ t = 1.0 . . . . . . . . . . . . . . . . . . . . . . . . 38Figure 7.4 System trade-off when s+ t = 0.1, s+ t = 0.5, s+ t = 1.0 . . . . . . . . . . . 39Figure 7.5 Simulated delay advantage vs. cost function when λ = 0.1, λ = 0.2 . . . . . . 40Figure 7.6 Simulated storage consumption comparison . . . . . . . . . . . . . . . . . . . 41Figure 7.7 Storage redundancy comparison . . . . . . . . . . . . . . . . . . . . . . . . . 42viiiList of AcronymsAcronyms DefinitionsIoT Internet of ThingsAI Artificial IntelligenceSDN Software-Defined NetworkMTTF Mean-Time-To-FailureQBD Quasi-Birth-DeathPoW Proof-of-WorkPoS Proof-of-StakePBFT Practical Byzantine Fault ToleranceRS Reed SolomonixList of SymbolsSymbols DefinitionsFi Raw blockchain data file chunkski Number of splitted original file chunksni Number of encoded file chunksN Total number of encoded chunks in the system` Storage capacity of single nodem Number of nodes in the systemTi Trunk request processing time of node iµ Parameter of the exponential distribution of TiD Delay of file retrieve requestE[D] Expectation of file retrieve request DSD[D] Standard deviation of file retrieve request Dg(n; k) Delay functionγ Expectation guarantee level of file retrieve requests Unit storage costt Unit bandwidth costλ Tradeoff parameter between delay and costc Cost coefficient, c = λ(s+ t)li Fault tolerance level of file ixList of Symbolsf(n; k) Upper bound of gn; kh(n; k) Lower bound of g(n; k)cu Upper bound of binary searchcl Lower bound of binary searchx˜ Candidate optimal solution of unconstrained optimization problemx∗ Final optimal solutionc′ Critical costxˆ Candidate optimal solution of critical costxiAcknowledgementsAfter two years of studying at UBC Okanagan, finally it comes to the day when I have finishedall my courses and my thesis. The feeling is complicated. It is a mixture of excitement and calmnessinstead of just feeling happy. On this special day, there are many of people that I must give thanksto.First of all, I give my greatest appreciation to my supervisor Dr. Chen Feng and co-supervisorDr. Julian Cheng. I was given the valuable chance to study at UBC Okanagan by the selflesswelcome of Dr. Chen Feng and Dr. Julian Cheng. Not only their caring of my life but alsotheir broad knowledge about academic research impressed and helped a lot. Without their patientinstruction, I could hardly imagine that I can successfully finish my degree in such a shot time.Second, I would like to thank my family. Thank my parents for providing financial and emotionalsupport for my studying abroad. In my mind, I have the best parents in the world. I would alsolike to thank my girlfriend Huizhe Chen for her encouragement and companionship when I feeldepressed. When I was struggling to get through hard times, her words and smiles always mademe feel full of energy and spirit.Third, I would like to thank all my friends who has helped me during my days spent at Kelowna:Chunpu Wang, Renming Qi, Junxiong He, Wanbing Xu, Dahai Wang, Weisheng Du, Yonghui Lv,Jianyu Niu, Yuwei Guo, Pengxia Wu, Xueting Yang and Fangyu Gai. My friends are always readyto offer help and getting together with them are the happiest time I’ve spent.Last but not least, thanks for the gorgeous view of Kelowna and Okanagan lake, both dayand night. Just sitting beside the lake shore or at the top of Knox mountain help me get out ofdepression, many times. Keep calm and fight back. That is what I think the mountain and waterhere try to teach me.xiiChapter 1IntroductionAs an awakening technology, Internet of Things [1] (IoT) is considered revolutionary not onlybecause it enables unlimited connectivity [2] for almost everything, but also because of the excitingprospects it indicates when combined with other emerging technologies including Big Data, Fogcomputing [3], Artificial Intelligence (AI), and Industry 4.0.The massive application of IoT in Industry 4.0 [4] brings enormous changes to what is believedto be the next industrial development stage. By providing network connectivity to smart sensors,micro controllers and other intelligent devices, IoT fills the gap between physical space and cyberspace [5]. The integration of IoT and Industry 4.0 greatly reshapes the way that Industry 4.0generates, collects and processes data. For example, real-time data from temperature sensors andhumidity sensors make it possible for Industry 4.0 monitoring system to instantly detect anoma-lies during the whole process of manufacturing; pipeline control data and product inspection databring convenience to quality assurance and quality control in Industry 4.0, which helps increasethe product quality; aggregation and analysis of historical manufacturing data build a solid foun-dation for business decision making and business model update, which helps to realize the smartmanufacturing in Industry 4.0 [6].Data, as we can conclude from the above scenarios, has become the main focus and core compe-tence of IoT and Industry 4.0. As almost all data from IoT and Industry 4.0 is highly confidentialand sensitive, data security has become an extremely important topic. When it comes to datasecurity, the massive scale and distributed nature of Industry 4.0 IoT become nightmares for re-searchers. A large number of solutions has been proposed to solve the seemingly impossible taskof keeping data secure in a distributed Industry 4.0 IoT network full of vulnerable devices andpotential security threats, of which the most recent one is integrating blockchain [7] technologyinto the current Industry 4.0 IoT architecture.Blockchain [8] is a decentralized, distributed ledger system used to record transactions acrossmultiple participants [9]. Built on the basis of public key encryption [10], consensus mechanism1Chapter 1. Introduction[11] and full decentralization, blockchain offers strong data privacy protection and data securityassurance in a distributed manner [12]. Blockchain brings a way of recording data that is designedto be secure, reliable and auditable, making it a perfect solution for securing IoT and Industry 4.0[13]. However, there is still a huge obstacle for integrating blockchain into IoT and Industry 4.0:storage scalability.Traditional blockchain architecture requires each participating node to store its own copy of theentire blockchain data. Over time, as transactions are appended to the tail of blockchain, the entireblockchain grows longer and consumes more storage space, causing the storage scalability issue[14]. The storage scalability issue may not be quite serious for traditional blockchain applicationslike Bitcoin [15] and Ethereum [16] because their participants have sufficient storage space (e.g.computer hard-drive). But for IoT and Industry 4.0, it is a totally different story.As intelligent devices like smart sensors and micro controllers in IoT and Industry 4.0 have ratherlimited storage capacity, the storage scalability issue of blockchain can be quite severe. Massivedata generated by IoT and Industry 4.0 can instantly occupy all storage space and paralyse thewhole network. The integration of blockchain with IoT and Industry 4.0 will not be possible untilwe fix the storage scalability issue.In this thesis, we propose a distributed storage architecture for blockchain based on erasurecoding [17]. The property of erasure coding makes it possible to greatly reduce storage consumptionfor each node without affecting the overall data integrity. Furthermore, to minimize the latencyof rebuilding data in this distributed storage architecture, we formulate a latency-cost trade-offoptimization problem and propose an efficient and scalable algorithm. Simulation results showthat the proposed architecture can achieve up to 80% latency reduction compared with otherwidely used distributed storage architectures. In addition, our architecture can save up to 90%storage space for each node, which removes the largest obstacle for integrating blockchain into IoTnetwork. In summary, we make the following contributions.− We propose a distributed storage architecture for blockchain and IoT integration based onerasure coding.− We formulate an optimization problem to find the optimal erasure coding parameters whenconsidering latency-cost trade-off.− We find an efficient and scalable algorithm for our optimization problem and examine theeffectiveness of our algorithm through simulation experiments.2Chapter 1. Introduction− We build a prototype testbed based on our architecture and algorithm.This thesis is organized in the following manner. Chapter 2 briefly discusses some related re-search work. Chapter 3 presents background information about blockchain and blockchain securitymechanism. Chapter 4 presents a detailed description of our proposed distributed storage architec-ture for blockchain and IoT integration. Chapter 5 gives a formal representation of our optimizationproblem. The proposed optimization solution algorithm is presented in Chapter 6. Based on thatalgorithm, a series of simulation experiments data and in-depth analysis are given in Chapter 7.Finally, Chapter 8 concludes the thesis.3Chapter 2Related WorkThere have been several previous publications focusing on similar research problems discussedin this thesis, including the integration architecture of blockchain and Industry 4.0 IoT, applicationof coding theory in distributed storage and optimal parameter selection of erasure coding.Integration of blockchain and Industry 4.0 IoT is attracting more and more attentions in recentyears. Comprehensive surveys were presented in [18], [19] and [20], covering different applicationscenarios, usage patterns and potential challenges in blockchain and IoT integration. A blockchain-based platform architecture for industrial IoT was proposed in [21]. This architecture first combinedprevious information sharing platform called Smart-M3 and blockchain, then it used smart contractsto provide trust between participants of IoT production network. Similarly, the application ofblockchain’s smart contracts in IoT network was also explored in [22]. This work discussed severalways in which blockchain and IoT can be used together to allow peer-to-peer communications anddata exchange in a non-trusting environment. Another novel blockchain-based distributed cloudarchitecture integrating SDN, Fog computing and IoT was proposed in [23], providing low-cost,secure and on-demand access to IoT network nodes.Additionally, considering the privacy and security properties of blockchain, using blockchainto provide security service for Industry 4.0 IoT has become the next hotspot. Survey paperslike [24], [25] and [26] discussed state-of-the-art IoT security issues and potential blockchain-basedsolutions. A blockchain-based decentralized security framework for IoT was proposed in [27], givingan overview of using blockchain technology for realization of security across distributed participantsin IoT network. More specifically, for IoT data security, [28] implemented blockchain-based protocoland prototype system to provide data integrity service data, eliminating the trust requirements onthird party auditors; [29] added a blockchain-based auditable access layer to the IoT storage layerto enable a secure and resilient access control management for IoT data. The topic of IoT deviceauthentication was covered in [30], where secure virtual zones can be built on the basis of blockchainto ensure a robust identification and authentication of IoT devices. By combinating blockchain and4Chapter 2. Related Workprivate-key encryption, a solution for IoT credibility verification was outlined in [31].However, all these above papers suffer a common problem: they are more like future visions fullof novel concepts and potential architectures, instead of practical systems with in-depth analysisand usable prototypes. On the contrary, our work consists of systematic problem modeling, in-depththeoretical analysis, and extensive simulation experiments.We are not the first to apply erasure coding in distributed storage system. As pointed out bycomprehensive survey papers like [32], [33] and [34], there has been several efforts on using erasurecoding to build a reliable and robust distributed storage system.By quantitatively compare building a distributed storage system using erasure coding and repli-cation, the authors in [35] showed that erasure coding had orders of magnitude higher mean-time-to-failure (MTTF) than replication, which means that erasure coding has far better system durability.Mean-field analysis between erasure coding and replication was also performed in [36], and theanalysis revealed that erasure coding strictly outperformed replication at all traffic loads whileimproving reliability.To meet different requirements in distributed storage system, a series of erasure codes have beenexplored. Conventional Reed-Solomon code [37] is the most widely used erasure code. Thoughit achieved optimal storage efficiency, it suffers from high repair bandwidth. For performanceconsiderations, LDPC code [38] was proposed to offer approximate erasure code properties whilehaving a much faster encoding-decoding speed. Regenerating code [39] was proposed to providereliability and efficient data repair in distributed storage systems with the help of cooperationamong participating nodes.More specifically, the latency metric was also explored from different perspectives in previousresearches. One perspective taken by [40], [41] and [42] was to model the request queue for multipledata chunks in a distributed storage system as a multi-dimensional Markov chain, and quasi-birth-death (QBD) process was used to bound the Markov chain. Finally, numerical bounds of latencycan be solved through matrix-analytic methods. Another perspective taken by [43] and [44] wasto use fork-join models in queuing theory to bound the Markov chain. The subordinate fork-joinsystem was then utilized to derive bounds on the mean latency.The most significant difference between our work and previous work is the research methodology.Since most previous researchers in this area are from the field of coding theory, they focus ontraditional coding theory topics such as deriving tight bounds of availability and achieving optimal5Chapter 2. Related Workrepair bandwidth. Correspondingly, they use traditional coding theory research methodologies suchas fork-join model in queuing theory, information flow graph analysis and Markov process. Instead,our solution models the latency-cost trade-off as a joint optimization problem, then uses convexoptimization method to solve the problem efficiently.A number of attempts have been made to deal with the blockchain storage scalability problem.ElasticChain [45] uses its own duplicate-ratio-regulation algorithm to control the portion of thecomplete blockchain stored on each node. By storing only part of the whole chain on each node,ElasticChain improves the blockchain storage scalability, but its storage efficiency is not as highas erasure coding. Another solution proposed in [46] uses a novel combination of Shamir’s secretsharing scheme, private key encryption and distributed storage codes to construct a coding schemethat distributed blockchain data among subsets of nodes. Though this coding scheme saves storagespace, it can lead to loss of data integrity compared with convention erasure code method. Authorsof [47] proposed a low storage room requirement framework for distributed ledger in blockchainby simply using erasure coding to store blockchain data. Similar frameworks were also given in[48] and [49]. However, those frameworks lack in-depth discussion about erasure coding parameterselection or performance optimization.6Chapter 3Background3.1 BlockchainAs the major supporting technology for record-keeping used by crypto-currencies like Bitcoinand Ethereum, blockchain is attracting more and more attentions in recent years. Before we startfinding more potential use-cases for this new technology, the nature of blockchain has to be explored.As you may tell from its name, blockchain is literally just a “chain” made up of several “blocks”.In this context, a block is a data structure containing digital information (e.g. transactions inBitcoin, or your order details for Amazon) while a chain can be seen as a database formed bylinking all these growing blocks to record the complete history of the whole blockchain system.Furthermore, blockchain can also be seen as a distributed and decentralized database ledger,that keeps public records in an append-only fashion. For use as a distributed ledger, blockchainis typically managed by a peer-to-peer network collectively adhering to a protocol for inter-nodecommunication, called the blockchain network. A blockchain network can be constructed on thebackbone of blockchain technology, in which there are multiple blockchain nodes packing digitalinformation to generate new blocks and appending the new blocks to the tail of the chain.Some people may ask that why we do not just use database instead of blockchain since fromthe above description blockchain does not seem to have much difference with traditional databasetechnologies. Actually, this is not true. Traditional database technologies can be divided into cen-tralized database and distributed database, blockchain has some advantages over both categories.Compared with centralized database, blockchain does not entirely rely on the normal operation of acentral node, thus avoiding the single point of failure in traditional centralized database systems. Adistributed blockchain can not be hacked, manipulated, or otherwise disrupted the way a databasebuild on one single operator can be. In addition, a traditional centralized database requires a systemdirectly operated by known and trustworthy individuals (e.g. a known administrator, a managingdepartment). Blockchain, on the other hand, can be operated by unknown nodes and participants73.2. Blockchain Security Mechanismall across the world. Compared with distributed database, blockchain does not require every nodein the network to be cooperative. In other words, blockchain is resistant to malicious nodes anddata modification. These great security properties are achieved by taking security mechanism intoconsideration from the first day blockchain is created. Further details about blockchain securitymechanism will be given in the following section.3.2 Blockchain Security Mechanism3.2.1 ImmutabilityThe most well-known security property of blockchain is data immutability, which means it isimpossible for a malicious user to arbitrarily alter historical data. Blockchain network utilizesblockchain data structure to guarantee immutability of all data recorded on blockchain. A typicaldata structure of blockchain is shown in Fig. 3.1.Figure 3.1: Blockchain data structureBlockchain data structure is a linked list indexed by hash values of each single block data. Eachblock contains some data, a cryptographic hash value of the data, and a cryptographic hash value ofits previous block. In Fig. 3.1 there are three different blocks in this blockchain, each storing its owndata hash value (marked in red) as well as the hash value of its previous block. If a malicious usertries to alter or tamper some historical data, the corresponding hash value would change, makingit inconsistent with hash values stored in its successor node. The immutability makes blockchain83.3. Blockchain IoT Integrationdifficult to tamper with.3.2.2 ConsensusHowever, data immutability only guarantees the recorded data on blockchain can not be arbi-trarily altered, which is far from making the blockchain security mechanism flawless. Because anynode or participant in blockchain network can submit information to the blockchain, it is necessaryfor the blockchain network to verify and agree on all addenda before they are permanently recordedon the blockchain. This process of verifying data and achieving agreement is called “consensus”.Blockchain needs consensus mechanism to guarantee every participating node in the networkagrees on state of the system. State can have a variety of different meanings, including real-timesensor data values, financial account balances, and access control and authentication records.There have been three major categories of consensus algorithms for blockchain: the proof-of-work [50] algorithm (PoW), the proof-of-stake [51] algorithm (PoS), and the practical byzantinefault tolerance [52] algorithm (PBFT). Since consensus algorithm is not the focus of this thesis, wewill not cover in-depth details of how these consensus algorithms work.3.2.3 AuditableLast but not least, blockchain provides the security property of auditable. In order to performdata verification or maintain data immutability, each record on the blockchain must be accessibleby any node or participant of the blockchain network, allowing for any node or participant toindividually verify the authenticity of each transaction recorded for any single record in the theblockchain. This transparency means that blockchains are auditable.3.3 Blockchain IoT IntegrationThanks to all these security enhancement brought by blockchain, blockchain technology has beenintegrated into massive research and application areas such as crypto-currency [53], digital paymentsystem [54], and asset registration [55]. Of all the above applications, the integration of blockchainand IoT is attracting intense interest based on the following reasons: blockchain technology canbe used in tracking billions of connected IoT devices [56], enable a secure processing and storageof IoT data [57]; blockchain’s decentralized design helps eliminate single points of failure, creatinga more resilient and reliable infrastructure for IoT devices to operate [58]. Blockchain has been93.3. Blockchain IoT Integrationmentioned as the the missing piece to solve security, privacy, and reliability issues in the IoT area.An integrated architecture of blockchain and IoT proposed in this thesis will be discussed in thefollowing chapters.10Chapter 4System ArchitectureThe integration of IoT and blockchain can happen in multiple layers and dimensions. A genericIoT architecture can be separated into three different layers: Cloud layer, Fog layer and IoT devicelayer. As shown in Fig. 4.1, our proposed architecture integrates blockchain with Fog layer and IoTdevice layer respectively, providing data security enhancement and distributed data storage servicein a hierarchical manner, while maintaining function transparency between different layers. In theremaining part of this chapter, we provide an in-depth description of how the integration of IoTand blockchain is achieved at each layer.Figure 4.1: Integration architecture4.1 Fog Layer Blockchain IntegrationThe integration of blockchain with Fog layer is shown in Fig. 4.2.In Fig. 4.2, several Fog nodes each controlling a certain stage of the whole production processare connected to form the Fog layer of the complete IoT architecture. Additionally, these Fog114.1. Fog Layer Blockchain IntegrationFigure 4.2: Fog layer blockchain architecturenodes run blockchain protocols to work as distributed nodes of the Fog level blockchain network.Blockchain serves as a core module of Fog layer, providing security enhancement services includingproduction process audit, sensitive data access control and manufacturing control authentication.These security enhancement services ensure the data generated and collected from supply chain,manufacturing process and real-time monitoring are securely transmitted to and processed by thebusiness intelligence part, achieving the ultimate intelligent manufacturing ecosystem of Industry4.0.For production process audit, blockchain can be utilized to store every auditable record in theblockchain data structure by treating these records as “transactions”. Hash algorithm providesimmutability property for blockchain, preventing any third-party participant or malicious userfrom tampering the raw records. Blockchain makes it possible to perform comprehensive audit forhistorical production process data anytime in the future.Also, blockchain can be applied in access control and operation authentication when businessintelligence department needs some data from other departments. Request information includingrequest source ID, request target ID, request time can be packed into a blockchain transaction and124.2. IoT Layer Blockchain Architecturerecorded in the blockchain data structure. Especially, if a certain request requires authorizationfrom higher level administrators, blockchain can also record the authorization operation for futurerevision. By integrating blockchain technology, access control and operation authentication becomemore transparent and traceable.4.2 IoT Layer Blockchain ArchitectureApart from the Fog layer blockchain network composed of Fog nodes, our architecture hasanother underlying blockchain network formed by all IoT devices at the IoT layer. The purpose ofthis IoT layer blockchain is to securely store real-time data generated by various IoT devices in adistributed and autonomous manner.To implement an autonomous blockchain network across massive number of nodes, the mostimportant problem to solve is how to achieve consensus in a closed-form distributed system. Thisproblem is even more important for our IoT layer blockchain because this blockchain network musthave the ability to quickly and independently verify massive real-time data generated by largeamount of IoT devices and reach agreement on data correctness among different nodes.Previous research on blockchain data verification has been proposed in [59], in which theblockchain serves as a ledger of hash values of external data stored in an originating system.In other words, the original data and its corresponding hash values are separated. These hashvalues are anchored into the blockchain, with the blockchain being used as a means of validatingthe integrity of the original data. A major disadvantage of this solution is that once the externaldata storage is corrupted or compromised, the original data can not be recovered, which can bringcatastrophic consequences.To solve that, we design a distributed-hash-based verification mechanism for IoT layer blockchain.In our mechanism, not only the hash values but also the original data are distributed stored acrossall blockchain network nodes. The distributed storage of original data eliminated the weak point ofexternal storage failure, providing a more reliable solution for data verification. A sample diagramof this verification mechanism is shown in Fig. 4.3.In Fig. 4.3 we use circles numbered 1-6 to stand for different IoT nodes, the blue squaresattached to each circle stand for chunks of distributed blockchain data stored on that node, andthe red squares attached to each circle stand for hash values of every blockchain block data. Astime goes by, the blockchain network packs new transactions into a new block and calculates hash134.2. IoT Layer Blockchain ArchitectureFigure 4.3: IoT layer blockchain verification mechanism144.2. IoT Layer Blockchain Architecturevalue of the newly generated block. Then blockchain network uses the hash values as indexes toform a linked-list, or a chain structure of blocks, which is called the blockchain data structure.As opposed to blockchain generation, verification is a reverse process. In our system, verificationis divided into two steps. The first step is to collect all chunks stored at other IoT nodes and rebuildthe original block data. The second step is to calculate the hash value of the rebuilt block dataand compare it with the hash value in the node’s local storage. If the two values are consistent,then we can verify the correctness of all associated transactions packed in that block. Combiningthis verification mechanism with existing consensus algorithms like PBFT can achieve the finalconsensus for the whole IoT layer blockchain network.By integrating blockchain technology with both Fog layer and IoT layer, our proposed architec-ture provides a data security enhancement and distributed data storage while maintaining functiontransparency between different layers.15Chapter 5System ModelIn this chapter, we focus on the layer of distributed storage, aiming to improve its reliabilityand reduce its access delay. We consider an IoT cluster consisting of m nodes. For simplicity, thesystem holds the following assumptions:Assumption 1: All m nodes are homogeneous, each with an identical storage capacity.Assumption 2: Once an IoT node fails, all the data stored on that node will be lost.Assumption 3: The number of nodes m is sufficiently large to store all files.The purpose of this distributed storage is to store a series of files F1, F2, . . . , Fi, . . . across severalselected nodes in a distributed manner, while enabling a fast and reliable recovery of the originalfile when needed. In this context, the term “file” stands for raw blockchain data generated by theblockchain network. Each file may contain only a single blockchain data, or may contain severalblockchain data, which is decided by the system administrator.In order to distribute a series of files F1, F2, · · · , Fi to be stored on the IoT nodes, we spliteach file Fi into ki fixed-size chunks, then use an (ni, ki) Reed-Solomon code (RS code) to generateni encoded chunks, including ni − ki parity chunks. According to the property of Reed-Solomoncoding, the original data can be recovered by collecting any ki encoded chunks [60]. The systemmodel is shown in Fig. 5.1As shown in Fig. 5.1, the working process of our system can be described as the following steps:− Step 1: Our system reads a part of the whole blockchain data file Fi which is newly generated.This blockchain data is generated by the Fog node, using all data collected and sent to theFog node by subordinate IoT nodes.− Step 2: Our system splits the read data into ki fixed-size file chunks, then uses Reed-Solomoncoding algorithm to generate ni encoded chunks including ni − ki parity chunks.− Step 3: Our systems schedules the ni encoded chunks onto several IoT nodes to store.16Chapter 5. System ModelFigure 5.1: System model175.1. Placement Subproblem− Step 4: When receives blockchain reading request, our system retrieves any ki different chunksand recover the original blockchain data.From the working process, we can see there are two key points for our system: the placementof ni encoded chunks to selected ni nodes in IoT cluster leads to a placement subproblem, and thechoice of adequate Reed-Solomon coding parameter leads to a coding parameter subproblem. Wewill give in-depth analysis of these two subproblems in Section 5.1 and Section 5.2.5.1 Placement SubproblemIn this section, we solve the placement subproblem. For simplicity, we assume that each IoTnode can only store one encoded chunk. (We will relax this assumption later.) Then, the problemreduces to the following question: How shall we select ni nodes in the IoT cluster for each file Fi?Let N =∑i ni denote the total number of encoded chunks in the system. We randomly select Nnodes (out of m nodes) and then partition them into groups of size ni. We can check that thissolution is optimal since all m nodes are homogeneous according to Assumption 1.We then proceed to a general case in which each IoT node can store ` encoded chunks. We canthink of this cluster consisting of `×m “virtual” IoT nodes of unit storage capacity. Now, supposethat N ≤ ` × m and maxi ni ≤ m according to Assumption 3. We can apply a “water-filling”strategy so that− every IoT node stores at most one encoded chunk from each file;− the maximum number of encoded chunks stored by an IoT node is minimized.An example of the water-filling strategy is shown in Fig. 5.2.This strategy has two advantages. First, when an IoT node fails, it will affect at most oneencoded chunk for each file. Second, it minimizes the number of affected files under a node failure.Therefore, we will use this strategy to solve the placement subproblem.5.2 RS Coding Parameter SubproblemFor the RS coding parameter subproblem, our objective is to find the optimal parameter whichmaximizes the system “utility” and minimize the system “cost”. Here, both “utility” and “cost”stand for abstract concepts composed of several different system metrics.185.2. RS Coding Parameter SubproblemFigure 5.2: Water-filling algorithm195.2. RS Coding Parameter SubproblemIn this thesis, we choose to minimize a weighted sum of retrieval delay and storage/bandwidthcost, as we will explain shortly by formulating the delay and cost functions.5.2.1 Delay FunctionAccording to the property of RS coding, an (n, k) RS code can encode k original chunks of afile to generate n encoded chunks. The original file can be retrieved by collecting any k out of nencoded chunks. (Note that we have dropped the subscript i to simplify the notation.) The fileretrieve process is described as follows:− Step 1: The file retrieve request is divided into n individual chunk requests to be processedby n nodes.− Step 2: Once k out of n individual chunk requests are completed and returned, the file retrieveprocess is completed.If we denote the chunk request processing time by Ti for node i, then the delay of file retrieverequest is the kth smallest random variable in the set {T1, T2, · · · , Tn}, which is often called the kthorder statistic. For ease of presentation, we make the following assumption about the distributionof Ti.Assumption 4: The chunk request processing time Ti follows an exponential distribution withmean value 1/µ.If we denote the delay of file retrieve request (i.e., the kth order statistic) by D, then theexpectation and standard deviation of D are given byE[D] =1µk∑i=11n− k + i ,SD[D] =1µ√√√√ k∑i=11(n− k + i)2 .(5.1)These results follow from the properties of order statistics of exponential distributions. Weobserve from Eq. (5.1) that E[D] and SD[D] both decrease as n grows (for a fixed k). This suggeststhat we should use as many nodes as possible (up to the storage constraint) in order to achieve asmall delay.205.2. RS Coding Parameter SubproblemWe are now ready to define the delay function g(n; k):g(n; k) , E[D] + γSD[D]=1µk∑i=11n− k + i +γµ√√√√ k∑i=11(n− k + i)2 .Here, γ is a parameter inspired by Chebyshev’s inequality1Pr (D ≥ E[D] + γSD[D]) ≤ 1γ2.That is, the event that the delay D is no less than g(n; k) happens with probability at most 1γ2.Note that the above inequality applies to arbitrary distribution of D. Hence, it is conservative andoften serves as a “worst-case” bound. For instance, if D is a Gaussian random variable, then wehavePr (D ≥ E[D] + 3× SD[D]) ≤ 0.3%which is referred to as the three-sigma rule of thumb.5.2.2 Cost FunctionThe cost consists of two parts: storage cost and bandwidth cost.Storage Cost: We assume that storing a single chunk on node i requires a storage cost of si.According to Assumption 1, all nodes have an identical storage cost denoted by s. In particular, ifwe have n encoded chunks in total, the storage cost will be s · n.Bandwidth Cost: We assume that transmitting a single chunk on node i requires a bandwidthcost of ti. According to Assumption 1, all links have an identical bandwidth cost denoted by t. Inparticular, if we have n encoded chunks transmitted, the bandwidth cost will be t · n.5.2.3 Problem FormulationWe are now in a position to formulate the parameter selection subproblem. In particular, wewould like to minimize a weighted sum of the delay function g(ni; ki) and the cost function (s+ t)nifor each file i.1Note that one version of Chebyshev’s inequality states that Pr (|D − E[D]| ≥ γSD[D]) ≤ 1γ2.215.2. RS Coding Parameter Subproblemmin∑i(g(ni; ki) + cni)s.t. ∀i, ki + li ≤ ni ≤ m∑ini ≤ ` ·m(5.2)Here, c = λ(s + t) and λ is a parameter providing a tradeoff between the delay and cost. Theparameter li indicates the fault tolerance level of file i (i.e., the number of node failures file i cantolerate). Clearly, Problem (5.2) is an integer programming problem, since our control variablesni are integer numbers. We will apply convex relaxation to solve for Problem (5.2) in the nextchapter.22Chapter 6Optimization SolutionIn this chapter, we present a solution to the optimization problem (5.2) based on convex relax-ation.6.1 Convex RelaxationTo apply convex relaxation, we need to define two functionsf(n; k) =1µln(nn− k)+γµ√1n− k −1nh(n; k) =1µln(n+ 1n− k + 1)+γµ√1n− k + 1 −1n+ 1.The functions f(n; k) and h(n; k) have several properties. First, f(n; k) and h(n; k) are bothdecreasing functions of n (for any fixed k). Second, f(n+1; k) = h(n; k). Third, f(n; k) ≥ g(n; k) ≥h(n; k) due to the following inequalitiesln(n+ 1n− k + 1)≤k∑i=11n− k + i ≤ ln(nn− k)1n− k + 1 −1n+ 1≤k∑i=11(n− k + i)2 ≤1n− k −1n.That is, f(n; k) and h(n; k) serve as upper and lower bounds of g(n; k), respectively.Tightness of upper bound f(n; k) and lower bound h(n; k) is shown in Fig. 6.1. In this figure,we set k = 100, l = 20, µ = 100, γ = 3 which are typical values also used in the evaluation chapter.From Fig. 6.1, we can see the curve of f(n; k) and the curve of h(n; k) converge together as nincreases, which means the gap between these two bounds are sufficiently small. So the upperbound f(n; k) and lower bound h(n; k) are tight enough.236.1. Convex RelaxationFigure 6.1: Upper and lower bounds tightnessThis suggests the following optimization problem:min∑i(f(xi; ki) + cxi)s.t. ∀i, ki + li ≤ xi ≤ m∑ixi ≤ ` ·m(6.1)where xi are real numbers rather than integer numbers and the function f(x; k) is given byf(x; k) =1µln(xx− k)+γµ√1x− k −1x.Intuitively, Problem (6.1) can be viewed as an “approximation” of our original problem (5.2),especially for large ki (so that f(ni; ki)− h(ni; ki) is small).It turns out that Problem (6.1) is a convex optimization problem. To see this, it suffices toshow that the function f(x; k) is a convex function with respect to x. For notational convenience,246.2. Single File Casewe write f(x) as a short-hand notation of f(x; k). Then, the second derivative of f(x) isf ′′(x) =γ4· 8kx(x− k) + 3k3x3(x− k)3√kx(x−k)+k(2x− k)x2(x− k)2 . (6.2)Clearly, f ′′(x) ≥ 0 when k + l ≤ x ≤ m. This is a sufficient condition for f(x) to be convex.Although a convex problem can be solved by many existing tools and algorithms, we will developa fast algorithm by making a special use of the structure of Problem (6.1).6.2 Single File CaseTo explain our fast algorithm, we start from the simplest case: There is a single file in thesystem. In this case, Problem (6.1) reduces to the following convex problem:min f(x) + cxs.t. k + l ≤ x ≤ m(6.3)Let x˜ be the solution to the equation2f ′(x) + c = 0. (6.4)Then, x˜ is the optimal solution to the unconstrained optimization problemmin f(x) + cx (6.5)because f(x) is a convex function.If x˜ ∈ [k + l,m], then x˜ is also the optimal solution to Problem (6.3). Otherwise, the optimalsolution x∗ is either k + l or m, depending on whether x˜ < k + l or x˜ > m.To provide more intuition, we give an illustration of f ′(x). In this example, we let γ = µ = 1for simplicity, and let k = 100, l = 20, then k + l = 120.From Fig. 6.2, we can see f ′(x) is a monotonically increasing function. It has a vertical asymp-tote at x = k and a horizontal asymptote. Since c is a positive value, the plot of f ′(x)+c is the plotof f ′(x) shifted upward by c units. After the shifting, the plot of f ′(x) + c will have an intersection2The existence and uniqueness of x˜ can be easily proved.256.2. Single File CaseFigure 6.2: Plot of f ′(x) when k = 90, l = 10, γ = µ = 1point with x-axis. At this point, f ′(x) + c = 0 and the point’s x-coordinate is x˜.As c increases, the intersection point will move towards the negative direction of x-axis and x˜will decrease. The relative position of x˜ with the range [k+ l,m] depends on the value of c. Next wewill give a case-by-case discussion on how the value of c affects the optimal solution x∗ to Problem(6.3).Case 1: c < −f ′(m)The relation between x˜ and the feasible range [k + l,m] when c < −f ′(m) is shown in Fig. 6.3.When c < −f ′(m), the intersection point (x˜, 0) is to the right of point (m, 0). In this case, wecan not choose x∗ = x˜. Instead, we choose x∗ = m. Intuitively, if a system’s cost is sufficientlysmall to be neglected, our best strategy is to spread encoded chunks on all IoT nodes to achievethe lowest delay. We call this type of system Low-Cost-System.Case 2: −f ′(m) ≤ c ≤ −f ′(k + l)The relation between x˜ and the feasible range [k + l,m] is shown in Fig. 6.4.When −f ′(m) ≤ c ≤ −f ′(k + l), the intersection point (x˜, 0) lies between point (k + l, 0) andpoint (m, 0). As x˜ satisfies the constraint, the optimal solution is x˜, i.e. x∗ = x˜. Intuitively, in asystem with medium cost, our best strategy is to find a balance between delay and cost trade-off.We call this type of system Medium-Cost-System.Case 3: c > −f ′(k + l)266.2. Single File CaseFigure 6.3: Plot of f ′(x) when c = 0, k = 100,m = 400, γ = µ = 1Figure 6.4: Plot of f ′(x) when c = 0.004, k = 100,m = 400, γ = µ = 1276.3. Two-File CaseThe relation between x˜ and the feasible range [k + l,m] is shown in Fig. 6.5.Figure 6.5: Plot of f ′(x) when c = 0.2, k = 100,m = 400, γ = µ = 1In this case, we can not choose x∗ = x˜. Instead, we choose x∗ = k+ l. Intuitively, if the cost ofa system is too high to be affordable, our best strategy is to use the minimum required number ofnodes to store our file chunks. We call this type of system High-Cost-System.As shown in Fig. 6.2, the plot of f ′(x) has a vertical asymptote at x = k. The vertical asymptoteat x = k means f ′(k) = −∞, i.e. −f ′(k) = +∞. It is impossible for −f ′(k) to be smaller than c.6.3 Two-File CaseIn this section we will extend our discussion to the case of two files. Note that if the storagecapacity of each node is at least 2 (i.e., ` ≥ 2), then Problem (6.1) can be decoupled into twosubproblems of the single-file case. (This is because the constraint x1 +x2 ≤ `m is redundant when` ≥ 2.) Hence, we only need to discuss the case of ` = 1, which is given below.min f1(x1) + cx1 + f2(x2) + cx2s.t. x1 + x2 ≤ mk1 + l1 ≤ x1 ≤ mk2 + l2 ≤ x2 ≤ m(6.6)286.3. Two-File CaseHere, f1(x1) and f2(x2) are short-hand notations of f(x1; k1) and f(x2; k2).Let x˜i be the optimal solution to the following convex problem:min fi(xi) + cxis.t. ki + li ≤ xi ≤ m.(6.7)If x˜1 + x˜2 ≤ m, then (x˜1, x˜2) is the optimal solution to Problem (6.6). Otherwise, the optimalsolution (x∗1, x∗2) satisfies one of the following conditions:− x∗1 = k1 + l1, and x∗2 = m− x∗1;− x∗2 = k2 + l2, and x∗1 = m− x∗2;− x∗1 + x∗2 = m, and f ′1(x∗1) = f ′2(x∗2).The first two cases of x∗1 = k1 + l1, x∗2 = m − x∗1 and x∗2 = k2 + l2, x∗1 = m − x∗2 are shown inFig. 6.6 and Fig. 6.7 respectively.Figure 6.6: Plot of x∗1 = k1 + l1, x∗2 = m− x∗1The three different conditions motivate us to define a “critical cost” c′ as follows. There exists acost value c′, which makes the intersection points with x-axis of plot f ′1(x) and plot f ′2(x), denotedby xˆ1 and xˆ2 respectively, to have a sum exactly equal to m, i.e. xˆ1 + xˆ2 = m. An example ofcritical condition is given in Fig. 6.8.296.3. Two-File CaseFigure 6.7: Plot of x∗2 = k2 + l2, x∗1 = m− x∗2Figure 6.8: Plot of critical condition when x∗1 + x∗2 = m306.3. Two-File CaseThe critical cost c′, together with the values of xˆ1 and xˆ2, can be found through a standardbinary search.With c′ and (xˆ1, xˆ2), we can use a simple strategy to find the optimal solution (x∗1, x∗2), asexplained in Algorithm 1.Algorithm 1: Algorithm for the Two-File CaseInput:cost function: c;node number: m;RS coding parameters, k1, l1, k2, l2two functions: f ′1(x1), f ′2(x2);Output:optimal solution (x∗1, x∗2)1: Solve the convex problem of min f1(x1) + cx1 s.t. k1 + l1 ≤ x1 ≤ m, find the solution x˜12: Solve the convex problem of min f2(x2) + cx2 s.t. k2 + l2 ≤ x2 ≤ m, find the solution x˜23: if x˜1 + x˜2 ≤ m then4: x∗1 ← x˜15: x∗2 ← x˜26: return x∗1, x∗27: else8: Use a binary search algorithm to find xˆ1 and xˆ29: if k1 + l1 ≤ xˆ1 ≤ m and k2 + l2 ≤ xˆ2 ≤ m then10: x∗1 ← xˆ111: x∗2 ← xˆ212: return x∗1, x∗213: else14: if xˆ1 < k1 + l1 then15: x∗1 ← k1 + l116: x∗2 ← m− x∗117: return x∗1, x∗218: else19: if xˆ2 < k2 + l2 then20: x∗2 ← k2 + l221: x∗1 ← m− x∗222: return x∗1, x∗223: end if24: end if25: end if26: end if316.4. Multiple-File Case6.3.1 Time Complexity Analysis of Two-File CaseAlgorithm 1 consists of three parts: part one is to find the candidate optimal solution x˜, parttwo is to find xˆ using binary search, part three is to go through several conditional expressionsand output the final optimal solution. We only focus on part two (binary search) in the followingdiscussion since it “dominates” the time complexity.Using standard argument, one can show that the time complexity of the binary search in parttwo is given below:O(log2(cu − cl))(6.8)where cu = max{−f ′1(k1 + l1),−f ′2(k1 + l1)} and cl = c.The two parameters cu and cl are upper and lower bounds for our binary search range. Thereason is as follows. If we set cu as an upper bound, the corresponding xi < ki + li and we havex1 + x2 < m. On the other hand, if we set cl as a lower bound, the corresponding x1 + x2 > m(because otherwise the algorithm already stops). Hence, we can perform a standard binary searchto obtain xˆ1 and xˆ2 with xˆ1 + xˆ2 = m. For , we can set it to be 10−4 since the final output of x∗1and x∗2 will be rounded.6.4 Multiple-File CaseAs the single file case and two-file case have been covered in previous sections, we can extendour algorithm to the case of multiple files. The algorithm follows a recursive manner. First, wesolve for multiple individual convex problems and obtain {x˜i}. If∑i x˜i ≤ `m, we stop and output{x˜i}. Otherwise, we use a binary search to find {xˆi}. If all of them satisfy ki + li ≤ xˆi ≤ m, thenwe stop and output {xˆi}. Otherwise, we set x∗i = ki + li for those files with xˆi < ki + li. Thisreduces the scale of the problem and we repeat the above process until we only have one or twofiles remaining.6.4.1 Time Complexity Analysis of Multiple-File CaseTime complexity of multiple-file case can be given based on our discussion about the two-filecase. Assume we have m files in total, the time complexity has the following formation:O(m× log2(cu − cl))(6.9)326.4. Multiple-File Casewhere cu = max{−f ′1(k1 + l1),−f ′2(k1 + l1), · · · ,−f ′m(km + lm)} and cl = c.Since we have m files, under the worst case we must repeat the binary search for m times. So,the time complexity is multiplied by m. Another difference is the value of cu. For the multiple-filecase, cu is the largest among −f ′i(ki + li).33Chapter 7EvaluationIn this chapter we present evaluation results of our system.7.1 Simulation Parameter Selection7.1.1 Selection of µAccording to the previous assumptions, the chunk request processing time ti follows an expo-nential distribution with mean value 1µ , so the physical meaning of parameter µ is the averagechunk request processing rate.Chunk request processing rate is decided by chunk size and transmission bandwidth. For chunksize, the typical value in our system is 128KB. For transmission bandwidth, we investigate thenetwork bandwidth of some widely-used IoT devices and tried to find a reasonable value. A tableshowing the comparison of network bandwidth between different IoT devices is given below.Table 7.1: Mainstream IoT device bandwidthDevice RPi 3B RPi 3B+ Onion Omega2 DragonBoard-410c STM32L4 IoT ESP32-DevKitCWiFi 802.11n 802.11ac 802.11n 802.11n 802.11n 802.11nEthernet 100Mbps 1000Mbps N/A N/A N/A N/ATable 7.1 shows that almost all IoT devices have 802.11n WiFi connectivity, which has a band-width of up to 300Mbps. The smallest bandwidth is the 100Mbps Ethernet of RPi 3B. For fairness,here we choose 100Mbps as the typical value of network bandwidth. The average chunk requestprocessing rate µ can be calculated byµ =100Mbps128KB=100× 1024Kbps128× 8Kb = 100 request/second (7.1)So µ = 100 is a reasonable choice.347.2. Simulation Results7.1.2 Selection of γIn the empirical sciences the so-called three-sigma rule of thumb expresses a conventional heuris-tic that majority of the values are taken to lie within three standard deviations of the mean. Hence,we choose γ = 3.7.1.3 Selection of cost coefficient cFor cloud-based IoT storage and transmission cost, we take Amazon AWS as an example.Amazon AWS charges 0.023 USD/GB for data storage, and 0.09 USD/GB for data transmission.If IoT devices use local storage (e.g. SD card), a typical price for local storage is 0.16 USD/GB.7.2 Simulation ResultsWe first explore the delay-cost trade-off of different λ values. In our objective function, changingthe value of λ changes the system trade-off situation. In Fig. 7.1, Fig. 7.2 and Fig. 7.3 we plot 3trade-off curves with cost function s + t = 0.1, s + t = 0.5 and s + t = 1.0 respectively. For eachcurve, we continuously change λ from 0 to 1 and calculate the corresponding delay values and costvalues. The three curves provide valuable insight on system trade-off decision making process.Fig. 7.4 illustrates all three curves under the same coordinate, which makes the relationshipbetween different system trade-off more clear.We next compare the proposed algorithm with some well-known Reed-Solomon codes to explorehow much advantage the new algorithm achieves. In this simulation, we choose the RS(104, 100)code which is widely used in RAID systems [61] as the benchmark. For the advantage metric, wechoose the delay advantage. The calculation of delay advantage is defined in Eq. (7.2), where Dbstands for delay value of benchmark algorithm and Do stands of delay value of our algorithm.delay advantage =Db −DoDb∗ 100% (7.2)Fig. 7.5 shows the simulated delay advantage of our algorithm compared with traditional RScoding algorithm when choosing different cost function s+ t values. The blue plot corresponds toλ = 0.1 while the orange plot corresponds to λ = 0.2. We can see that our algorithm can achieveup to 80% delay decrease when cost function s + t < 1. Our algorithm has delay advantage overtraditional RS coding algorithm in the range of s+ t ∈ [0, 2].357.2. Simulation ResultsFigure 7.1: System trade-off when s+ t = 0.1367.2. Simulation ResultsFigure 7.2: System trade-off when s+ t = 0.5377.2. Simulation ResultsFigure 7.3: System trade-off when s+ t = 1.0387.2. Simulation ResultsFigure 7.4: System trade-off when s+ t = 0.1, s+ t = 0.5, s+ t = 1.0397.2. Simulation ResultsFigure 7.5: Simulated delay advantage vs. cost function when λ = 0.1, λ = 0.2407.2. Simulation ResultsAdditionally, since the purpose of our proposed RS coding based distributed storage archi-tecture is to minimize the space consumption on each blockchain network node, we compare thestorage space consumption of our algorithm with traditional blockchain paradigm. A storage spaceconsumption comparison based on simulation is shown in Fig. 7.6.Figure 7.6: Simulated storage consumption comparisonNotice that the y-axis of Fig. 7.6 has a logarithmic scale. That is because our RS coding basedstorage has huge advantages over traditional blockchain storage paradigm. As can be concludedfrom Fig. 7.6, our architecture can save up to 90% storage space for each node, which removes thelargest obstacle for integrating blockchain into IoT network.Furthermore, as a distributed storage system, we should not only focus on the storage con-sumption of each individual node, but also on the whole system storage redundancy. There is abalance between single node storage consumption and whole system storage redundancy. We canminimize the single node storage consumption by encoding original data to more chunks, but that417.2. Simulation Resultswould increase the total storage redundancy. A storage redundancy of the whole system is shownin Fig. 7.7.Figure 7.7: Storage redundancy comparisonWe can conclude from Fig. 7.7 that the total storage redundancy imported by our architectureis about 1.5 times, which is quite acceptable considering the huge storage space-saving of eachindividual node.42Chapter 8ConclusionIn this thesis, we proposed a distributed storage architecture for blockchain based on erasurecoding. The property of erasure coding makes it possible to greatly reduce storage overhead foreach node without affecting the overall data integrity. Furthermore, to minimize the latency ofrebuilding data in this distributed storage architecture, we formulated a latency-cost trade-offoptimization problem and proposed an efficient and scalable algorithm. Simulation results showthat the proposed architecture can achieve up to 80% latency reduction when compared with otherwidely used distributed storage architectures. In addition, our architecture can save up to 90%storage space for each node, which removes the largest obstacle for integrating blockchain into IoTnetwork.43Bibliography[1] Jayavardhana Gubbi, Rajkumar Buyya, Slaven Marusic, and Marimuthu Palaniswami. Inter-net of things (iot): A vision, architectural elements, and future directions. Future generationcomputer systems, 29(7):1645–1660, 2013.[2] In Lee and Kyoochun Lee. The internet of things (iot): Applications, investments, and chal-lenges for enterprises. Business Horizons, 58(4):431–440, 2015.[3] Mung Chiang and Tao Zhang. Fog and iot: An overview of research opportunities. IEEEInternet of Things Journal, 3(6):854–864, 2016.[4] Yang Lu. Industry 4.0: A survey on technologies, applications and open research issues.Journal of Industrial Information Integration, 6:1–10, 2017.[5] Jay Lee, Behrad Bagheri, and Hung-An Kao. A cyber-physical systems architecture for indus-try 4.0-based manufacturing systems. Manufacturing Letters, 3:18–23, 2015.[6] Michael Ru¨ßmann, Markus Lorenz, Philipp Gerbert, Manuela Waldner, Jan Justus, PascalEngel, and Michael Harnisch. Industry 4.0: The future of productivity and growth in manu-facturing industries. Boston Consulting Group, 9(1):54–89, 2015.[7] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder.Bitcoin and cryptocurrency technologies: A comprehensive introduction. Princeton UniversityPress, 2016.[8] Michael Crosby, Pradan Pattanayak, Sanjeev Verma, Vignesh Kalyanaraman, et al. Blockchaintechnology: Beyond bitcoin. Applied Innovation, 2(6-10):71, 2016.[9] Zibin Zheng, Shaoan Xie, Hongning Dai, Xiangping Chen, and Huaimin Wang. An overview ofblockchain technology: Architecture, consensus, and future trends. In 2017 IEEE InternationalCongress on Big Data (BigData congress), pages 557–564. IEEE, Jun. 2017.44Bibliography[10] Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public keyencryption with keyword search. In International Conference on Theory and Applications ofCryptographic Techniques, pages 506–522. Springer, May 2004.[11] Christian Cachin and Marko Vukolic´. Blockchain consensus protocols in the wild. arXive-prints, abs/1707.01873, Jul. 2017.[12] Guy Zyskind, Oz Nathan, et al. Decentralizing privacy: Using blockchain to protect personaldata. In 2015 IEEE Security and Privacy Workshops, pages 180–184. IEEE, May 2015.[13] Seyoung Huh, Sangrae Cho, and Soohyung Kim. Managing iot devices using blockchainplatform. In 2017 19th International Conference on Advanced Communication Technology(ICACT), pages 464–467. IEEE, Feb. 2017.[14] Ghassan Karame. On the security and scalability of bitcoin’s blockchain. In Proceedings of the2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1861–1862.ACM, Oct. 2016.[15] Satoshi Nakamoto et al. Bitcoin: A peer-to-peer electronic cash system. 2008.[16] Gavin Wood. Ethereum: A secure decentralised generalised transaction ledger. Ethereumproject yellow paper, 151:1–32, 2014.[17] James S Plank. T1: erasure codes for storage applications. In Proceedings of the 4th USENIXConference on File and Storage Technologies, pages 1–74, Dec. 2005.[18] Alfonso Panarello, Nachiket Tapas, Giovanni Merlino, Francesco Longo, and Antonio Puliafito.Blockchain and iot integration: A systematic survey. Sensors, 18(8):2575, Aug. 2018.[19] Marco Conoscenti, Antonio Vetro, and Juan Carlos De Martin. Blockchain for the internet ofthings: A systematic literature review. In 2016 IEEE/ACS 13th International Conference ofComputer Systems and Applications (AICCSA), pages 1–6. IEEE, Dec. 2016.[20] Ali Dorri, Salil S. Kanhere, and Raja Jurdak. Blockchain in internet of things: Challenges andsolutions. arXiv e-prints, abs/1608.05187, Aug. 2016.[21] Nikolay Teslya and Igor Ryabchikov. Blockchain-based platform architecture for industrial iot.In 2017 21st Conference of Open Innovations Association (FRUCT), pages 321–329. IEEE,Nov. 2017.45Bibliography[22] Konstantinos Christidis and Michael Devetsikiotis. Blockchains and smart contracts for theinternet of things. IEEE Access, 4:2292–2303, 2016.[23] Pradip Kumar Sharma, Mu-Yen Chen, and Jong Hyuk Park. A software defined fog nodebased distributed blockchain cloud architecture for iot. IEEE Access, 6:115–124, 2018.[24] Minhaj Ahmad Khan and Khaled Salah. Iot security: Review, blockchain solutions, and openchallenges. Future Generation Computer Systems, 82:395–411, 2018.[25] Charalampos S Kouzinopoulos, Georgios Spathoulas, Konstantinos M Giannoutakis, Kon-stantinos Votis, Pankaj Pandey, Dimitrios Tzovaras, Sokratis K Katsikas, Anastasija Collen,and Niels A Nijdam. Using blockchains to strengthen the security of internet of things. InInternational ISCIS Security Workshop, pages 90–100. Springer, Jul. 2018.[26] Mandrita Banerjee, Junghee Lee, and Kim-Kwang Raymond Choo. A blockchain future forinternet of things security: a position paper. Digital Communications and Networks, 4(3):149–160, 2018.[27] Deepak Puthal, Nisha Malik, Saraju P Mohanty, Elias Kougianos, and Chi Yang. Theblockchain as a decentralized security framework [future directions]. IEEE Consumer Elec-tronics Magazine, 7(2):18–21, 2018.[28] Bin Liu, Xiao Liang Yu, Shiping Chen, Xiwei Xu, and Liming Zhu. Blockchain based dataintegrity service framework for iot data. In 2017 IEEE International Conference on WebServices (ICWS), pages 468–475. IEEE, Jun. 2017.[29] Hossein Shafagh, Lukas Burkhalter, Anwar Hithnawi, and Simon Duquennoy. Towardsblockchain-based auditable storage and sharing of iot data. In Proceedings of the 2017 onCloud Computing Security Workshop, pages 45–50. ACM, Nov. 2017.[30] Chao Qu, Ming Tao, Jie Zhang, Xiaoyu Hong, and Ruifen Yuan. Blockchain based credibilityverification method for iot entities. Security and Communication Networks, 2018:1–11, 2018.[31] Mohamed Tahar Hammi, Badis Hammi, Patrick Bellot, and Ahmed Serhrouchni. Bubbles oftrust: A decentralized blockchain-based authentication system for iot. Computers and Security,78:126–142, 2018.46Bibliography[32] Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright, and Kan-nan Ramchandran. Network coding for distributed storage systems. IEEE Transactions onInformation Theory, 56(9):4539–4551, 2010.[33] Alexandros G. Dimakis, Kannan Ramchandran, Yunnan Wu, and Changho Suh. A survey onnetwork codes for distributed storage. Proceedings of the IEEE, 99(3):476–489, 2011.[34] Jun Li and Baochun Li. Erasure coding for cloud storage systems: A survey. Tsinghua Scienceand Technology, 18(3):259–272, 2013.[35] Hakim Weatherspoon and John Kubiatowicz. Erasure coding vs. replication: A quantita-tive comparison. In Revised Papers from the First International Workshop on Peer-to-PeerSystems, pages 328–338. Springer-Verlag, Mar. 2002.[36] Bin Li, Aditya Ramamoorthy, and R Srikant. Mean-field analysis of coding versus replicationin large data storage systems. ACM Transactions on Modeling and Performance Evaluationof Computing Systems, 3(1):1–28, 2018.[37] Alla Levina, Ilya Kuzmin, and Sergey Taranov. Reed solomon codes and its application forcloud storage system. In Third International Conference on Future Generation CommunicationTechnologies (FGCT 2014), pages 46–49. IEEE, Aug. 2014.[38] Benjamin Gaidioz, Birger Koblitz, and Nuno Santos. Exploring high performance distributedfile storage using ldpc codes. Parallel Computing, 33(4-5):264–274, 2007.[39] K. V. Rashmi, Nihar B. Shah, Kannan Ramchandran, and P. Vijay Kumar. Regeneratingcodes for errors and erasures in distributed storage. In 2012 IEEE International Symposiumon Information Theory Proceedings, pages 1202–1206. IEEE, Jul. 2012.[40] Nihar B. Shah, Kangwook Lee, and Kannan Ramchandran. When do redundant requestsreduce latency? IEEE Transactions on Communications, 64(2):715–722, 2016.[41] Kangwook Lee, Nihar B. Shah, Longbo Huang, and Kannan Ramchandran. The mds queue:Analysing the latency performance of erasure codes. IEEE Transactions on Information The-ory, 63(5):1–1, 2017.47Bibliography[42] Parimal Parag and Jean-Francois Chamberland. Novel latency bounds for distributed codedstorage. In 2018 Information Theory and Applications Workshop (ITA), pages 1–9. IEEE,Feb. 2018.[43] Gauri Joshi, Yanpei Liu, and Emina Soljanin. On the delay-storage trade-off in content down-load from coded distributed storage systems. IEEE Journal on Selected Areas in Communi-cations, 32(5):989–997, 2014.[44] Parimal Parag, Archana Bura, and Jean-Francois Chamberland. Latency analysis for dis-tributed storage. In IEEE INFOCOM 2017 - IEEE Conference on Computer Communications,pages 1–9. IEEE, May 2017.[45] Dayu Jia, Junchang Xin, Zhiqiong Wang, Wei Guo, and Guoren Wang. Elasticchain: Supportvery large blockchain by reducing data redundancy. In Web and Big Data, pages 440–454.Springer, Jul. 2018.[46] Ravi Kiran Raman and Lav R. Varshney. Dynamic distributed storage for blockchains. In2018 IEEE International Symposium on Information Theory (ISIT), pages 2619–2623. IEEE,Jun. 2018.[47] Mingjun Dai, Shengli Zhang, Hui Wang, and Shi Jin. A low storage room requirement frame-work for distributed ledger in blockchain. IEEE Access, 6(c):22970–22975, 2018.[48] Doriane Perard, Je´roˆme Lacan, Yann Bachy, and Jonathan Detchart. Erasure code-based lowstorage blockchain node. arXiv e-prints, abs/1805.00860, May 2018.[49] Yu Xiang, Tian Lan, Vaneet Aggarwal, and Yih-farn R Chen. Joint latency and cost op-timization for erasure-coded data center storage. IEEE/ACM Transactions on Networking,24(4):2443–2457, 2016.[50] Arthur Gervais, Ghassan O Karame, Karl Wu¨st, Vasileios Glykantzis, Hubert Ritzdorf, andSrdjan Capkun. On the security and performance of proof of work blockchains. In Proceedingsof the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages3–16. ACM, Oct. 2016.[51] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros:48BibliographyA provably secure proof-of-stake blockchain protocol. In Annual International CryptologyConference, pages 357–388. Springer, Jul. 2017.[52] Harish Sukhwani, Jose´ M Mart´ınez, Xiaolin Chang, Kishor S Trivedi, and Andy Rindos. Per-formance modeling of pbft consensus process for permissioned blockchain network (hyperledgerfabric). In 2017 IEEE 36th Symposium on Reliable Distributed Systems (SRDS), pages 253–255. IEEE, Sep. 2017.[53] Ittay Eyal. Blockchain technology: Transforming libertarian cryptocurrency dreams to financeand banking realities. Computer, 50(9):38–49, Sep. 2017.[54] Po-Wei Chen, Bo-Sian Jiang, and Chia-Hui Wang. Blockchain-based payment collection su-pervision system using pervasive bitcoin digital wallet. In 2017 IEEE 13th International Con-ference on Wireless and Mobile Computing, Networking and Communications (WiMob), pages139–146. IEEE, Oct. 2017.[55] Nguyen B Truong, Tai-Won Um, Bo Zhou, and Gyu Myoung Lee. Strengthening theblockchain-based internet of value with trust. In 2018 IEEE International Conference onCommunications (ICC), pages 1–7. IEEE, Jul. 2018.[56] Oscar Novo. Blockchain meets iot: An architecture for scalable access management in iot.IEEE Internet of Things Journal, 5(2):1184–1195, Mar. 2018.[57] Zhiqing Huang, Xiongye Su, Yanxin Zhang, Changxue Shi, Hanchen Zhang, and Luyang Xie.A decentralized solution for iot data trusted exchange based-on blockchain. In 2017 3rd IEEEInternational Conference on Computer and Communications (ICCC), pages 1180–1184. IEEE,Mar. 2017.[58] Xueping Liang, Juan Zhao, Sachin Shetty, and Danyi Li. Towards data assurance and resiliencein iot using blockchain. In MILCOM 2017-2017 IEEE Military Communications Conference(MILCOM), pages 261–266. IEEE, Oct. 2017.[59] Victoria L Lemieux. A typology of blockchain recordkeeping solutions and some reflectionson their implications for the future of archival preservation. In 2017 IEEE InternationalConference on Big Data (Big Data), pages 2271–2278. IEEE, Dec. 2017.49Bibliography[60] James S Plank. A tutorial on reed–solomon coding for fault-tolerance in raid-like systems.Software: Practice and Experience, 27(9):995–1012, Jan. 1997.[61] Dimitri Pertin, Alexandre Van Kempen, Benoˆıt Parrein, and Nicolas Normand. Comparison ofraid-6 erasure codes. In The third Sino-French Workshop on Information and CommunicationTechnologies, SIFWICT 2015, pages 42–50. HAL, Jun. 2015.50
Thesis/Dissertation
eng
Electrical Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Latency-optimized distributed storage for blockchain in IoT network
Text