# Light Repository Blockchain System with Multisecret Sharing for Industrial Big Data

Authors: Hefeng Chen; Hsiao-Ling Wu; Chin-Chen Chang; Long-Sheng Chen
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Blockchain is an emerging technology that promises many exciting applications in various fields, including financial, medical, energy, and logistics management. However, there are still some limitations in the existing blockchain framework that prevents its widespread adoption in the commercial world. One important limitation is the storage requirement, wherein each blockchain node has to store a copy of the distributed ledger. Thus, as the number of transactions increases, this storage requirement grows quadratically, eventually limiting the scalability of a blockchain system. Moreover, the public ledger in a blockchain framework allows anyone in the network to audit the transaction, which may not be favourable in some privacy-sensitive applications. In this paper, a secret-sharing scheme is proposed to reduce the size of the blockchain transactions. Each transaction block is divided intot parts, and the size of each part is 1/t size of transaction block. We use the secret-sharing mechanism to share t parts into n shares. Hence, each node stores not one transaction but one share in the blockchain system. The proposed scheme can eventually reduce the storage cost of a blockchain transaction by 1/t without introducing an additional recovery communication cost; however, robustness is reduced in node failure as a tradeoff. Meanwhile, the proposed scheme was more efficient and secure compared to other state-of-the-art schemes that aim to reduce blockchain storage for industrial big data.


---

## Body

## 1. Introduction

Internet commerce has become relatively entirely dependent on financial institutions that are trusted third parties to handle electronic payments. Although the system is suitable for most transactions, it still has the inherent weaknesses in trust-based models. Blockchain is a paradigm-shifting technology that has emerged over the past decade, which is based on peer-to-peer communication technology, network theory, and cryptography [1]. In a traditional centralized database model, the central server stores every transaction record, which can be disastrous if the central server is being attacked. In contrast, blockchain technology is a distributed solution without any third-party trust problem. Since every node in the blockchain network keeps a copy of the public ledger, it is possible to audit the transactions locally without referring to a centralized authority. Therefore, blockchain can also be viewed as a distributed ledger system, which eliminates the disadvantage of a traditional centralized database model. However, the storage cost in blockchain is huge [2], which is one of the factors currently limiting the widespread adoption of blockchain technology. Since each node needs to store the public ledger locally, the storage cost of an entire blockchain network grows quadratically.To resolve the storage issue in blockchain, Dai et al. [3] proposed a low-storage blockchain system that employs network coding theory to divide the transaction data into multiple blocks and then stores the blocks at different nodes. This can realize distributed storage (DS) by recovering the transaction data through network coding (NC). They proposed two kinds of NC-based DS, one is deterministic rate (NC-DRDS) and the other is rateless (NC-RLDS), to deal with a fixed and variable number of blockchain nodes, respectively. In another approach, Dorri et al. [4] proposed a memory-optimized and flexible blockchain (MOF-BC) that allows the user to summarize or remove part of the “aged” blockchain transactions. This eventually reduces the ability to perform a public audit, as some of the information is eventually erased. The idea of distributed storage blockchain (DSB) is first introduced by Raman and Varshney in 2018 [5]. The blockchain transaction block is first encrypted and then stored at different nodes (together with the encryption key) using a secret-sharing scheme. In this way, the storage of a blockchain is reduced significantly. Later, Kim et al. [6] improved DSB by proposing a local secret-sharing (LSS) scheme, which can tolerate single peer failure.Secret sharing is used as a basic cryptographic primitive in computer science, including for electronic voting [7], key-aggregate authentication [8], distributed cloud computing [9], secret image sharing [10, 11], and data hiding [12]. In 1979, the secret sharing was first introduced by Shamir [13] based on the Lagrange interpolating polynomial, while Blakley [14] independently took another approach based on the hyperplane geometry. In 1983, Mignotte’s scheme [15] and Asmuth-Bloom’s scheme [16] were proposed based on the Chinese remainder theorem. A perfect t,n secret-sharing scheme [13] has two properties: (1) any t or more shares can recover the secret; (2) any t−1 or fewer shares reveal no information about the secret. To share another secret, the dealer must redistribute every participant’s secret share. Later, several schemes have been presented for multiple secret sharing. In a multisecret sharing scheme, every user only needs to keep one share and many secrets can be shared independently without updating the share.Most multisecret sharing schemes require the disclosure of large amounts of public information. Chien et al. [17] proposed a multisecret scheme based on systematic block codes, while Yang et al. [18] improved the amount of public information required by Chien et al. Further, Yang’s scheme is based on Shamir’s secret-sharing scheme such that fewer than the threshold number of pieces do not leak any information. Dehkordi and Mashhadi’s scheme [19] focused on improving the efficiency of computations involved in share creation and secret reconstruction rather than space efficiency. Our multisecret sharing is based on recursion, in which a secret is first divided into t pieces and then the pieces are encoded one by one in such a manner that the shares of the already encoded pieces are reused to create new shares for the next piece.In this paper, we improve existing work [3, 5, 6] by proposing a low-storage scheme with multisecret sharing based on polynomial interpolation. Our idea is different from Raman and Varshney [5] and Kim et al. [6] as we do not encrypt the blockchain transaction block. Instead, our proposed scheme divides the blockchain transaction block directly into multiple shares and stores it in different nodes. The advantages of our work can be summarized as follows.(1)
Efficiency: the size of share is on the order of |S|/t; that is, the storage room and communication cost are reduced effectively.(2)
Robustness: no side information needs to be stored with the shares, and no public information needs to be disclosed.


## 2. Blockchain and Storage Issues

Blockchain is a distributed ledger system that requires each participating node to store a copy of ledger for the transaction records. Every time a transaction block is created, it is first verified by the neighbouring nodes and then goes through the consensus (mining) process by solving a difficult cryptographic puzzle. One of the nodes that successfully solve this puzzle is rewarded with some incentives. This transaction block is then added to the ledger, wherein each block is related to the previous block through a chain of hash values. This data structure suffers from scalability issue, as the storage room required to keep the entire ledger is growing quadratically when the number of blockchain nodes increases.


## 3. Overview of Shamir’s Secret-Sharing Scheme

### 3.1. Shamir’sr,n-Threshold Secret Sharing

In 1979, Shamir developed ar,n-threshold secret-sharing scheme [13] based on polynomial interpolation, wherein a univariate polynomial y=fx of degree r−1 is uniquely defined by r points xj,yj with distinct xj, for j=1,2,…,r. The scheme can decompose one secret into n shares, with r shares required to recover the original secret, where r≤n. However, the secret cannot be recovered with less than r shadows. It consists of the following two phases.


### 3.2. Shadow Distribution Phase

The trusted dealer starts with a secret integer,S≥0, that is, to be distributed among n users. Thus, the dealer runs the following:(1)
Choose a primep>maxn,S.(2)
Randomly selectr−1 independent coefficients a1,a2,…,ar−1∈ℤp, to constitute a random polynomial with r−1 degree over ℤp:(1)fx=S+∑j=1r−1ajxjmodp.(3)
Choosen distinct nonzero elements of ℤp, denoted as xi, for 1≤i≤n.(4)
Computesi=fximodp,1≤i≤n and securely transfer the share si to user Ui, along with the public index xi.


### 3.3. Secret Reconstruction Phase

Assume thatr users, Ui1,Ui2,…,Uir, pool their shares to compute the secret S. Their shadows provide r distinct points xij,sij′s, 1≤j≤r, which allow the computation of the coefficients of fx by Lagrange interpolation. The secret, S, can be expressed as(2)S=f0=∑j=1rsijcijmodp,where cij=∏1≤k≤r,k≠jxij/xik−xijmodp, for 1≤j≤r.Figure1 shows an example of Shamir’s (3, 6) secret sharing, which can be adopted by blockchain. Assume that the transaction block α is divided into three equal length packets, which are expressed as integers α1, α2, and α3. We use them as the coefficients to construct a 2-degree polynomial, which is expressed as fx=α1+α2x+α3x2. The shadows are then generated and distributed to the blockchain nodes with ID=1,2,3,4,5,6.Figure 1
Optional (3, 6) Shamir secret sharing.


## 3.1. Shamir’sr,n-Threshold Secret Sharing

In 1979, Shamir developed ar,n-threshold secret-sharing scheme [13] based on polynomial interpolation, wherein a univariate polynomial y=fx of degree r−1 is uniquely defined by r points xj,yj with distinct xj, for j=1,2,…,r. The scheme can decompose one secret into n shares, with r shares required to recover the original secret, where r≤n. However, the secret cannot be recovered with less than r shadows. It consists of the following two phases.


## 3.2. Shadow Distribution Phase

The trusted dealer starts with a secret integer,S≥0, that is, to be distributed among n users. Thus, the dealer runs the following:(1)
Choose a primep>maxn,S.(2)
Randomly selectr−1 independent coefficients a1,a2,…,ar−1∈ℤp, to constitute a random polynomial with r−1 degree over ℤp:(1)fx=S+∑j=1r−1ajxjmodp.(3)
Choosen distinct nonzero elements of ℤp, denoted as xi, for 1≤i≤n.(4)
Computesi=fximodp,1≤i≤n and securely transfer the share si to user Ui, along with the public index xi.


## 3.3. Secret Reconstruction Phase

Assume thatr users, Ui1,Ui2,…,Uir, pool their shares to compute the secret S. Their shadows provide r distinct points xij,sij′s, 1≤j≤r, which allow the computation of the coefficients of fx by Lagrange interpolation. The secret, S, can be expressed as(2)S=f0=∑j=1rsijcijmodp,where cij=∏1≤k≤r,k≠jxij/xik−xijmodp, for 1≤j≤r.Figure1 shows an example of Shamir’s (3, 6) secret sharing, which can be adopted by blockchain. Assume that the transaction block α is divided into three equal length packets, which are expressed as integers α1, α2, and α3. We use them as the coefficients to construct a 2-degree polynomial, which is expressed as fx=α1+α2x+α3x2. The shadows are then generated and distributed to the blockchain nodes with ID=1,2,3,4,5,6.Figure 1
Optional (3, 6) Shamir secret sharing.


## 4. Blockchain Transactions with Secret-Sharing Scheme

In this section, we describe our proposal of using secret-sharing scheme to reduce the storage cost of blockchain. In our sharing scheme, each block is stored in a distributed manner among all nodes. Consider the transaction blockα, our idea inspired by Parakh and Kak [20]. The flowchart of sharing process and reconstruction process is shown in Figure 2.Figure 2
Flowchart of sharing process and reconstruction process.Firstly, we divide the blockα into t pieces of size α/t, denoted as α1,α2,…,αt, such that their concatenation α1‖α2‖…‖αt=α. All the arithmetic performed is finite field arithmetic on ℤp, where p is larger than αi1≤i≤t and n. Then, we share them recursively as follows. The first step is to run Shamir’s (2, 2) secret sharing for the piece α1. That is, generate randomly a 1-degree polynomial g1x whose constant term is α1, and compute g1,1=g11 and g1,2=g12 to obtain two shares for α1. Next, generate a 2-degree polynomial g2x=α2+g1,1x+g1,2x2modp whose constant term is the next piece α2, and the coefficients are the previous two shares. By induction, assume that we have obtained i shares of the piece αi−12≤i≤t−1, denoted as gi−1,1,gi−1,2,…,gi−1,i, we can generate a i-degree sharing polynomial for the next piece αi by using gi−1,j as the j-th coefficient term for j=1,2,…,i. At the last step, we generate a t-degree sharing polynomial:(3)gtx=αt+gt−1,1x+gt−1,2x2+⋯+gt−1,kxtmodp,and the final n shares are(4)gtx1,gtx2,…,gtxn,where x1,x2,…,xn are n public indexes of nodes. The sharing scheme is shown in Algorithm 1.Algorithm 1:Sharing process.
Given the blockα and n public indexes x1,x2,…,xn
Divideα into t equal length pieces α1,α2,…,αt
Select a large primep>maxα1,α2,…,αt,n
Select a random numberr∈ℤp, and construct a 1-degree polynomial g1x=α1+rxmodp
Computeg1,1=g11 and g1,2=g12
fori=2 to t−1do
Constructi-degree polynomial gix=αi+gi−1,1x+gi−1,2x2+⋯+gi−1,iximodp
forj=1 to i+1do
Computegi,j=gij
end for
end for
Constructt-degree polynomial gtx=αt+gt−1,1x+gt−1,2x2+⋯+gt−1,kxtmodp
fori=1 to ndo
Computeβi=gtxi
end for
Distribute the shareβi to the corresponding node with public index xi, for i=1,…,nThe reconstruction is an inverse process that is carried out in a backward and first-out manner. Anyt+1 of the shares can interpolate a t-degree polynomial gt⋅ with the constant term αt. Then, interpolate a t−1-degree polynomial gt−1⋅ with the constant term αt−1, by taking the j-th coefficient of gt⋅ as the point at x=j, for j=1,2,…,t. The recursion repeats until α1 is obtained. Then, the whole block is given by the concatenation α1‖α2‖…‖αt=α. Algorithm 2 shows how to reconstruct the shared transaction block.Algorithm 2: Reconstruction process.
Given anyt+1 shares βx1,βx2,…,βxt+1
Interpolatet+1 points, x1,βx1,x2,βx2,…,xt+1,βxt+1, to generate t-degree polynomial  gtx=αt+gt−1,1x+gt−1,2x2+⋯+gt−1,kxtmodp
Compute the constant termαt=gt0 and the coefficients
for i=k−1 to 1 do
Interpolatei+1 points 1,gi,1,2,gi,2,…,i+1,gi,i+1 to generate i-degree polynomial  gix=αi+gi−1,1x+gi−1,2x2+⋯+gi−1,iximodp
Computeαi=gi0modp
end for
returnα=α1‖α2‖…‖αtIn Figure3, a block α is divided into 4 pieces α1=19, α2=27, α3=4, and α4=15. Assumed that α is to be shared between 7 parties such that any 5 of them can reconstruct all the 4 secrets. We can now use a prime p=31 and random number r=11.Figure 3
Example of proposed (5, 7) secret sharing where the blockα=19270415, the prime modules p=31, and the random number r=11.Theorem 1.
Our proposed scheme divides the original fileα into n pieces in such a way that (i) any t+1 packets can recover the original file α, but (ii) no group of t pieces can do so.Proof.
Based on the Lagrange interpolation, givent points ui1,yi1, ui2,yi2, …, uit+1,yit+1 with distinct uij’s, there is a unique polynomial of degree t such that yij=guij, for 1≤j≤t+1, i.e.,(5)gx=∑j=1t+1yijlijxmodp,where lijx=∏1≤k≤t+1,ik≠ijx−uik/uij−uikmodp.
Therefore,αt=g0 can be reconstructed correctly. To reconstruct the next piece αt−1, a t−1-degree polynomial is generated by taking the k-th coefficient of gx as the point at x=k, for k=1,2,…,t. Correctness is still guaranteed by Lagrange interpolation. Then, based on recursion, αt−2, …, α2, α1 can be correctly reconstructed one by one.
On the contrary, if onlyt of these n packets are available, it is not suffice to compute αi’s. For each candidate value αt∈0,1,…,p−1, we can construct a unique polynomial gx of degree t such that g0=αtmodp and gxij=yijmodp for 1≤j≤t+1. These p possible polynomials have equal probability; therefore, the real value of packets cannot be determined.
Moreover, we can improve the above proposed scheme to achieve the verifiable property. In general, each transaction block in the blockchain system (e.g., Bitcoin) consists of a block header and a data block. All transactions are included in the data block as leaf nodes of a Merkle tree [21], and the hash root of the Merkle tree is computed in the block header (see Figure 4). Denote the block header and data block of a transaction block, α, as β and δ, respectively. Now, we perform the above sharing scheme for β and δ, independently. After reconstructing β and δ, the correctness of δ can be verified by the root hash value in block header β.Figure 4
Transactions hashed in a Merkle tree.


## 5. Practical Implementation Issues

### 5.1. Storage Cost

Assuming that the block header is stored inFη and the data block is stored in Fq, then the blockchain’s storage cost per transaction per peer is(6)log2η+log2q.The storage cost of the DSB proposed by Raman and Varshney [5] is(7)log2ηt+1+2log2q.This is effectively smaller compared to the traditional blockchain. Kim et al. [6] proposed the LSS scheme to further reduce the storage cost to(8)log2ηt+log2q.The comparison of storage cost for different schemes is detailed in Table1.Table 1
Comparison of storage/communication costs and robustness.
Traditional blockchain
Original DSB [5]
DSB with LSS [6]
Proposed scheme
Storage cost
log
2
η
+
log
2
q
log
2
η
/
t
+
1
+
2
log
2
q
log
2
η
/
t
+
log
2
q
log
2
η
+
log
2
q
/
t
Communication cost
log
2
η
+
log
2
q
log
2
η
+
2
t
+
1
log
2
q
+
ρ
log
2
η
+
t
log
2
q
log
2
η
+
log
2
q
Robustness
n
−
1
n
/
t
+
1
−
1
2
n
/
t
+
1
−
1
n
−
t
−
1Compared to the traditional blockchain, our proposed scheme can effectively reduce the storage cost by1/t, so the storage cost becomes log2η+log2q/t. From Table 1, it is clear that our proposed scheme is more efficient than other prior work including Kim et al.’s [6]. This can effectively reduce the deployment and maintenance cost in blockchain.


### 5.2. Recovery Communication Cost

Our proposed scheme can effectively reduce the storage cost in blockchain communication, but it also introduces some additional communication cost. In traditional blockchain, each node keeps a public ledger locally. If any node failure happens, the failed node can recover the ledger by getting it from other peers, so the communication cost is proportional to the storage cost. The minimum communication cost is essentially(9)log2η+log2q.When there is a node failure, our proposed scheme requirest+1 secret shares to recover the transaction block, so the recovery communication cost is dependent on the number of shares t+1 and proportional to the storage cost:(10)t+1log2η+log2qt+1=log2η+log2q.Figure5 shows the tradeoff between storage and recovery communication cost for a specific case. It is clearly shown that our proposed scheme can achieve lower storage cost but does not increase the recovery communication cost. This is a huge advantage compared to original blockchain and the state-of-the-art work by Kim et al.Figure 5
Tradeoff between storage cost and recovery communication cost (η=2350, q=230, and ρ=200).


### 5.3. Robustness to Peer Failures

In regard to the robustness to peer failures, traditional blockchain can toleraten−1 node failure, in the expense of large ledger stored in every node. The scheme proposed by Raman and Varshney [5] and Kim et al. [6] can only tolerate n/t+1−1 and 2n/t+1−1 failures, respectively, which is significantly smaller than the traditional blockchain. Our proposed scheme can tolerate n−t−1 node failure, which is better compared to these two state-of-the-art schemes [5, 6]. Figure 6 shows the comparison of robustness where n=900.Figure 6
Comparison of robustness (n = 900).Another interesting work was presented by Dai et al. [3] recently based on network coding theory. Compared to them, our proposed scheme shares the same storage cost, communication cost, and robustness. However, their scheme can guarantee the recovery of transaction block if the collected packets is no less than t. It may leak information to malicious node if the collected packets is less than t. On the contrary, our proposed scheme utilizes Shamir’s secret-sharing scheme, which can assure that if the collected packets is less than r, no additional information is being leaked. Hence, it is more advantageous compared to the scheme proposed by Dai et al.


## 5.1. Storage Cost

Assuming that the block header is stored inFη and the data block is stored in Fq, then the blockchain’s storage cost per transaction per peer is(6)log2η+log2q.The storage cost of the DSB proposed by Raman and Varshney [5] is(7)log2ηt+1+2log2q.This is effectively smaller compared to the traditional blockchain. Kim et al. [6] proposed the LSS scheme to further reduce the storage cost to(8)log2ηt+log2q.The comparison of storage cost for different schemes is detailed in Table1.Table 1
Comparison of storage/communication costs and robustness.
Traditional blockchain
Original DSB [5]
DSB with LSS [6]
Proposed scheme
Storage cost
log
2
η
+
log
2
q
log
2
η
/
t
+
1
+
2
log
2
q
log
2
η
/
t
+
log
2
q
log
2
η
+
log
2
q
/
t
Communication cost
log
2
η
+
log
2
q
log
2
η
+
2
t
+
1
log
2
q
+
ρ
log
2
η
+
t
log
2
q
log
2
η
+
log
2
q
Robustness
n
−
1
n
/
t
+
1
−
1
2
n
/
t
+
1
−
1
n
−
t
−
1Compared to the traditional blockchain, our proposed scheme can effectively reduce the storage cost by1/t, so the storage cost becomes log2η+log2q/t. From Table 1, it is clear that our proposed scheme is more efficient than other prior work including Kim et al.’s [6]. This can effectively reduce the deployment and maintenance cost in blockchain.


## 5.2. Recovery Communication Cost

Our proposed scheme can effectively reduce the storage cost in blockchain communication, but it also introduces some additional communication cost. In traditional blockchain, each node keeps a public ledger locally. If any node failure happens, the failed node can recover the ledger by getting it from other peers, so the communication cost is proportional to the storage cost. The minimum communication cost is essentially(9)log2η+log2q.When there is a node failure, our proposed scheme requirest+1 secret shares to recover the transaction block, so the recovery communication cost is dependent on the number of shares t+1 and proportional to the storage cost:(10)t+1log2η+log2qt+1=log2η+log2q.Figure5 shows the tradeoff between storage and recovery communication cost for a specific case. It is clearly shown that our proposed scheme can achieve lower storage cost but does not increase the recovery communication cost. This is a huge advantage compared to original blockchain and the state-of-the-art work by Kim et al.Figure 5
Tradeoff between storage cost and recovery communication cost (η=2350, q=230, and ρ=200).


## 5.3. Robustness to Peer Failures

In regard to the robustness to peer failures, traditional blockchain can toleraten−1 node failure, in the expense of large ledger stored in every node. The scheme proposed by Raman and Varshney [5] and Kim et al. [6] can only tolerate n/t+1−1 and 2n/t+1−1 failures, respectively, which is significantly smaller than the traditional blockchain. Our proposed scheme can tolerate n−t−1 node failure, which is better compared to these two state-of-the-art schemes [5, 6]. Figure 6 shows the comparison of robustness where n=900.Figure 6
Comparison of robustness (n = 900).Another interesting work was presented by Dai et al. [3] recently based on network coding theory. Compared to them, our proposed scheme shares the same storage cost, communication cost, and robustness. However, their scheme can guarantee the recovery of transaction block if the collected packets is no less than t. It may leak information to malicious node if the collected packets is less than t. On the contrary, our proposed scheme utilizes Shamir’s secret-sharing scheme, which can assure that if the collected packets is less than r, no additional information is being leaked. Hence, it is more advantageous compared to the scheme proposed by Dai et al.


## 6. Conclusions

Traditional blockchain requires huge storage room when the number of nodes increases, which limits the scalability of this emerging technology. In this article, we proposed a low-storage scheme based on secret sharing to reduce the storage cost of blockchain. The proposed scheme is able to reduce the storage cost of traditional blockchain by1/t without introducing additional communication cost. It is also more efficient compared to the other recent studies [5, 6] that attempted to solve the same problem. Although the scheme proposed by Dai et al. [3] is as efficient as our proposed scheme, it leaks partial information and is considered less secure. The proposed scheme requires both r and n to be fixed, so it is more suitable for private and consortium blockchain systems where the number of nodes is predetermined. This can be a limitation as the number of nodes in public blockchain is changing dynamically. In future, we plan to extend this to support public blockchain.



---

*Source: 9060756-2019-10-16.xml*