1

Dynamic Distributed Storage for Scaling
Blockchains
Ravi Kiran Raman and Lav R. Varshney

arXiv:1711.07617v2 [] 7 Jan 2018

Abstract
Blockchain uses the idea of storing transaction data in the form of a distributed ledger wherein each node in
the network stores a current copy of the sequence of transactions in the form of a hash chain. This requirement of
storing the entire ledger incurs a high storage cost that grows undesirably large for high transaction rates and large
networks. In this work we use the ideas of secret key sharing, private key encryption, and distributed storage to
design a coding scheme such that each node stores only a part of the entire transaction thereby reducing the storage
cost to a fraction of its original cost. When further using dynamic zone allocation, we show the coding scheme
can also improve the integrity of the transaction data in the network over current schemes. Further, block validation
(bitcoin mining) consumes a significant amount of energy as it is necessary to determine a hash value satisfying a
specific set of constraints; we show that using dynamic distributed storage reduces these energy costs.
Index Terms
Blockchains, scaling, distributed storage, secret sharing

I. I NTRODUCTION
Blockchains are distributed, shared ledgers of transactions that reduce the friction in financial networks due to
different intermediaries using different technology infrastructures, and even reduce the need for intermediaries to
validate financial transactions. This has in turn led to the emergence of a new environment of business transactions
and self-regulated cryptocurrencies such as bitcoin [1], [2]. Owing to such favorable properties, blockchains are
being adopted extensively outside cryptocurrencies in a variety of novel application domains [3], [4]. In particular,
blockchains have inspired novel innovations in medicine [5], supply chain management and global trade [6], and
government services [7]. Blockchains are expected to revolutionize the way financial/business transactions are done
[8], for instance in the form of smart contracts [9]. In fact, streamlining infrastructure and removing redundant
intermediaries creates the opportunity for significant efficiency gains.
The blockchain architecture however comes with an inherent weakness. The blockchain works on the premise
that the entire ledger of transactions is stored in the form of a hash chain at every node, even though the transactions
themselves are meaningless to the peers that are not party to the underlying transaction. Consequently, the individual
nodes incur a significant, ever-increasing storage cost [10]. Note that secure storage may be much more costly than
just raw hard drives, e.g. due to infrastructure and staffing costs.
In current practice, the most common technique to reduce the storage overload is to prune old transactions in
the chain. However, this mechanism is not sustainable for blockchains that have to support a high arrival rate of
transaction data. Hence the blockchain architecture is not scalable owing to the heavy storage requirements.
For instance, consider the bitcoin network. Bitcoin currently serves an average of just under 3.5 transactions per
second [11]. This low number is owing to a variety of reasons including the economics involved in maintaining a
high value for the bitcoin. However, even at this rate, this accounts for an average of 160MB of storage per day
[10], i.e., about 60GB per year. The growth in storage and the number of transactions in the bitcoin network over
time [10] are shown in Figs. 1a and 1b. The exponential growth in the size of the blockchain and the number of
transactions to be served highlights the need for better storage techniques that can meet the surging demand.
SETL, an institutional payment and settlement infrastructure based on blockchain, claims to support 1 billion
transactions per day. This is dwarfed by the Federal Reserve, which processes 14 trillion financial transactions
per day. If cryptocurrencies are to become financial mainstays, they would need to be scaled by several orders.
Specifically, they will eventually need to support to the order of about 2000 transactions per second on average
The authors are with the University of Illinois at Urbana-Champaign.

2

(a) Blockchain Size

(b) Average Number of Transactions per day

(c) Hash-rate

Fig. 1: Increase in transactions, storage, and hash-rate in bitcoin. Data obtained from [10].

[11]. Note that this translates to an average storage cost of over 90GB per day. This is to say nothing about uses for
blockchain in global trade and commerce, healthcare, food and agriculture, and a wide variety of other industries.
With storage cost expected to saturate soon due to the ending of Moore’s Law, storage is emerging as a pressing
concern with the large-scale adoption of blockchain.
This impending end to Moore’s law not only implies saturated storage costs, but also a saturation of computational
speeds. Block validation (mining) in bitcoin-like networks requires computing an appropriate hash value that caters
to specified constraints and adding the data block to the blockchain. Notwithstanding new efforts such as [12],
this process has been found to be computationally expensive and demands the use of high-end hardware and large
volumes of energy. The hash rate, which is the number of hashes computed per second on the bitcoin network,
is indicative of the total energy consumption by the network. The hash rate has been found to be increasing
exponentially over time, as indicated in Fig. 1c, as a result of both an increase in the rate of transactions, and an
increase in the number of miners with powerful computing machines.
This staggering growth in hash computation results in a corresponding growth in energy consumption by the
blockchain network. Recent independent studies have estimated that the global energy consumption of the bitcoin
network is of the order of 700MW [13], [14]. This amount of power is sufficient to power over 325,000 homes and
well over 5000 times the power consumed per transaction by a credit card. Increasing demand for bitcoin in the
absence of any updates to the mechanism of mining is thus projected to increase the consumption to the order of
14GW by the year 2020. The reducing energy efficiency improvement of mining hardware at a time when bitcoin
value is rising rapidly, with a projected rapid increase the transaction rate further compounds the energy problem.
In addition to the unsustainable growth in energy consumption, this requirement of mining on availability of
efficient computing resources and cheap electricity also establishes an imbalance in the decentralized mining
requirement of bitcoin-like cryptocurrencies. In particular, miners tend to concentrate in geographic regions of the
world where both the mentioned resources are available for cheap. This is again undesirable for cryptocurrencies
such as bitcoin that rely fundamentally on the distributed nature of the mining operation to establish reliability.
Thus, it is of interest to keep the mining process relatively cheap without compromising on data integrity.
The current mechanism of bitcoin mining is referred to at large as a Proof of Work (PoW) method where the
creation of a hash that adheres to the constraint set is identified as a proof of validation. This is typically done
in a competitive environment with the first peer to mine earning a reward in terms of new bitcoins. The reason
for using such a mechanism is two-fold. Firstly, it automates and controls the generation of new bitcoins in the
system while also incentivizing miners to validate data blocks. Secondly, the creation of the hash constraints also
enhances data integrity as a corruption to the block in turn requires the computationally expensive recomputation
of the constrained hash values.
In this paper we do not consider the economics related to cryptocurencies through the mining process. Blockchain
systems, cryptocurrencies in particular, however have explored the feasibility of reducing the energy demands by
moving away from a competition-based mining process. Efforts to move to a Proof of Stake (PoS) model wherein

3

peers are assigned the mining task in a deterministic fashion depending on the fraction of cryptocurrency (stake)
they own. While the method is not yet foolproof, the removal of the competitive framework is expected to reduce
the energy demands. In this work, we focus on energy reduction through an alternate scheme that guarantees a
enhanced data integrity through information-theoretic immutability rather than a computational one in Sec. VII.
A. Our Contributions
In this paper we show that the storage costs in large-scale blockchain networks can be reduced through secure
distributed storage codes. Specifically, when each peer stores a piece of the entire transaction instead of the entire
block, the storage cost can be diminished to a fraction of the original. In Sec. IV, we use a novel combination of
Shamir’s secret sharing scheme [15], private key encryption, and distributed storage codes [16], inspired by [17],
to construct a coding scheme that distributes transaction data among subsets of peers. The scheme is shown to be
optimal in storage up to small additive terms. We also show, using a combination of statistical and cryptographic
security of the code, that the distributed storage loses an arbitrarily small amount of data integrity as compared to
the conventional method.
Further, in Sec. V, using a dynamic zone allocation strategy among peers, we show that the integrity of the data
can further be enhanced in the blockchain. We formulate the zone allocation problem as an interesting combinatorial
problem of decomposing complete hypergraphs into 1-factors. We design an allocation strategy that is order optimal
in the time taken to ensure highest data integrity. We show that given enough transaction blocks to follow, such a
system is secure from active adversaries.
Distributed storage schemes have been considered in the past in the form of information dispersal algorithms
(IDA) [18], [19] and in the form of distributed storage codes [16], [20]. In particular [19] considers an information
dispersal scheme that is secure from adaptive adversaries. We note that the coding scheme we define here is stronger
than such methods as it handles active adversaries. Secure distributed storage codes with repair capabilities to protect
against colluding eavesdroppers [21] and active adversaries [22] have also been considered. The difference in the
nature of attacks by adversaries calls for a new coding scheme in this paper.
In addition to the reduction in storage costs without compromising the integrity, in Sec. VII, we study the energy
demands of our scheme in comparison to conventional bitcoin-like blockchains by comparing the computational
complexity involved in establishing the blockchain. We show that our scheme creates a framework to reduce energy
consumption through the use of simpler, easy to compute hash functions.
The enhanced integrity, reduced storage and energy costs do come at the expense of increased recovery and
repair costs. In particular, as the data is stored as a secure distributed code, the recovery process is highly sensitive
to denial of service attacks and the codes are not locally repairable, as elaborated in Sec. VI.
Before getting into the construction and analysis of the codes, we first introduce a mathematical abstraction of
the blockchain in Sec. II, and give a brief introduction to the coding schemes that are used in this work in Sec. III.
II. S YSTEM M ODEL
We now introduce a mathematical model of conventional blockchain systems. We first describe the method in
which the distributed ledger is maintained in the peer network, emphasizing the roles of various nodes in the process
of incorporating a new transaction in the ledger. Then, we introduce data corruption in blockchain systems and the
nature of the active adversary considered in this work.
A. Ledger Construction
The blockchain comprises a connected peer-to-peer network of nodes, where nodes are placed into three primary
categories based on functionality:
1) Clients: nodes that invoke or are involved in a transaction, have the blocks validated by endorsers, and
communicate them to the orderers.
2) Peers: nodes that commit transactions and maintain a current version of the ledger. Peers may also adopt
endorser roles.
3) Orderer: nodes that communicate the transactions to the peers in chronological order to ensure consistency
of the hash chain.

4

Fig. 2: Architecture of the Blockchain Network. Here the network is categorized by functional role into clients Ci ,
peers Pi , and orderers O. As mentioned earlier, the clients initialize transactions. Upon validation, the transactions
are communicated to peers by orderers. The peers maintain an ordered copy of the ledger of transactions.

Note that the classification highlighted here is only based on function, and individual nodes in the network can
serve multiple roles.
The distributed ledger of the blockchain maintains a current copy of the sequence of transactions. A transaction is
initiated by the participating clients and is verified by endorsers (select peers). Subsequently, the verified transaction
is communicated to the orderer. The orderer then broadcasts the transaction blocks to the peers to store in the ledger.
The nodes in the blockchain are as depicted in Fig. 2. Here nodes Ci are clients, Pi are peers, and O is the set of
orderers in the system, categorized by function.
The ledger at each node is stored in the form of a (cryptographic) hash chain.
Definition 1: Let M be a message space consisting of messages of arbitrary length. A cryptographic hash function
is a deterministic function h : M → H, where H is a set of fixed-length sequences called hash values.
Cryptographic hash functions additionally incorporate the following properties:
1) Computational ease: To establish efficiency, the hash function should be easy to compute.
2) Pre-image resistance: Given H ∈ H, it is computationally infeasible to find M ∈ M such that h(M) = H .
3) Collision resistance: It is computationally infeasible to find M1 , M2 ∈ M such that h(M2 ) = h(M1 ).
4) Sensitivity: Minor changes in the input change the corresponding hash values significantly.
Other application-specific properties are incorporated depending on need.
Let Bt be the tth transaction block and let Ht be the hash value stored with the (t + 1)th transaction, computed
as Ht = h(Wt ), where h(·) is the hash function, and Wt = (Ht−1 , Bt ) is the concatenation of Ht−1 and Bt . Thus,
the hash chain is stored as
(H0 , B1 ) − (H1 , B2 ) − · · · − (Ht−1 , Bt ).
Let us assume that for all t, Bt ∼ Unif(Fq ) and Ht ∈ Fp , where q, p ∈ N and Fq , Fp are finite fields of order
q and p respectively. Thus, in the conventional implementation of the blockchain, the cost of storage per peer per
transaction is
R̃s = log2 q + log2 p bits.
(1)
Transactions stored in the ledger may at a later point be recovered in order to validate claims or verify details
of the past transaction by nodes that have read access to the data. Different implementations of the blockchain
invoke different recovery mechanisms depending on the application. One such method is to use an authentication
mechanism wherein select peers return the data stored in the ledger and the other peers validate (sign) the content.
Depending on the application, one can envision varying the number of authorization checks necessary to validate
the content.
For convenience, we restrict this work to one form of retrieval which broadly encompasses a wide class of
recovery schemes. Specifically, we assume that in order to recover the tth transaction, each peer returns its copy
of the transaction and the majority rule is applied to recover the block.

5

B. Blockchain Security
There are two main forms of data security that we focus on.
1) Integrity: transaction data stored by clients cannot be corrupted unless a majority of the peers are corrupted.
2) Confidentiality: local information from individual peers does not reveal sensitive transaction information.
Corruption of data in the blockchain requires corrupting a majority of the peers in the network to alter the
data stored in the distributed, duplicated copy of the transaction ledger. Thus, the blockchain system automatically
ensures a level of integrity in the transaction data.
Conventional blockchain systems such as bitcoin enforce additional constraints on the hash values to enhance data
integrity. For instance, in the bitcoin network, each transaction block is appended with a nonce which is typically a
string of zeros, such that the corresponding hash value satisfies a difficulty target i.e., is in a specified constraint set.
The establishment of such difficulty targets in turn implies that computing a nonce to satisfy the hash constraints
is computationally expensive. Thus data integrity can be tested by ensuring the hash values are consistent as it is
computationally infeasible to alter the data.
The hash chain, even without the difficulty targets, offers a mechanism to ensure data integrity in the blockchain.
Specifically, note that the sensitivity and pre-image resistance of the cryptographic hash function ensures that any
change to Ht−1 or Bt would require recomputing Ht . Further, it is not computationally feasible to determine Wt
such that h(Wt ) = Ht .
Thus storing the ledger in the form of a hashchain ensures that corrupting a past transaction not only requires
the client to corrupt at least half the set of peers to change the majority value, but also maintain a consistent hash
chain following the corrupted transaction. That is, say a participating client wishes to alter transaction B1 to B10 .
Let there be T transactions in the ledger. Then, corrupting B1 implies that the client would also have to replace
H1 with H10 = h(W10 ) at the corrupted nodes. This creates a domino effect, in that all subsequent hashes must in
turn be altered as well, to maintain integrity of the chain. This strengthens the integrity of the transaction data in
blockchain systems.
Confidentiality of information is typically guaranteed in these systems through the use of private key encryption
methods, where the key is shared with a select set of peers are authorized to view the contents of the transactions.
Note however that in such implementations, a leak at a single node could lead to a complete disambiguation of the
information.
C. Active Adversary Model
In this work, we explore the construction of a distributed storage coding scheme that ensures a heightened sense
of confidentiality and integrity of the data, even when the hash functions are computationally inexpensive.
Let us assume that each transaction Bt also has a corresponding access list, which is the set of nodes that have
permission to read and edit the content in Bt . Note that this is equivalent to holding a private key to decrypt the
encrypted transaction data stored in the ledger.
In this work, we primarily focus on active adversaries who alter a transaction content Bt to a desired value Bt0 .
Let us explicitly define the semantic rules of a valid corruption for such an adversary. If a client corrupts a peer,
then the client can
1) learn the contents stored in the peer;
2) alter block content only if it is in the access list of the corresponding block; and
3) alter hash values as long as chain integrity is preserved, i.e., an attacker cannot invalidate the transaction of
another node in the process.
The active adversary in our work is assumed to be aware of the contents of the hash chain and the block that it
wishes to corrupt. We elaborate on the integrity of our coding scheme against such active adversaries. We also
briefly elaborate on the data confidentiality guaranteed by our system against local information leaks.
Another typical attack of interest in such blockchain systems is the denial of service attack where an adversary
corrupts a peer in the network to deny the requested service, which in this case is the data stored in the ledger. We
also briefly describe the vulnerability of the system to denial of service attacks owing to the distributed storage.
Before we describe the code construction, we first give a preliminary introduction to coding and encryption
schemes that we use as the basis to build our coding scheme.

6

III. P RELIMINARIES
This work uses a private key encryption scheme with a novel combination of secret key sharing and distributed
storage codes to store the transaction data and hash values. We now provide a brief introduction to these elements.
A. Shamir’s Secret Sharing
Consider a secret S ∈ Fq that is to be shared with n < q nodes such that any subset of size less than k get
no information regarding the secret upon collusion, while any subset of size at least k get complete information.
Shamir’s (k, n) secret sharing scheme [15] describes a method to explicitly construct such a code. All the arithmetic
performed here is finite field arithmetic on Fq .
i.i.d
Draw ai ∼ Unif(Fq ), for i ∈ [k − 1] and set a0 = S . Then, compute
yi = a0 + a1 xi + a2 x2i + · · · + ak−1 xk−1
, for all i ∈ [n],
i

where xi = i. Node i ∈ [n] receives the share yi .
Since the values are computed according to a polynomial of order k −1, the coefficients of the polynomial can be
uniquely determined only when we have access to at least k points. Recovering the secret key involves polynomial
interpolation of the k shares to obtain the secret key (intercept). Thus, the secret can be recovered if and only if at
least k nodes collude.
In this work, we presume that each secret share is given by (xi , yi ), and that the unique abscissa values are chosen
uniformly at random from Fq \{0}. That is, {xi : i ∈ [n]} are drawn uniformly at random without replacement
from Fq \{0}. Then, given any k − 1 shares and the secret, the final share uniformly likely in a set of size q − k .
It is worth noting that Shamir’s scheme is minimal in storage as the size of each share is the same as the size of
the secret key. Shamir’s scheme however is not secure to active adversaries. In particular, by corrupting n − k + 1
nodes, the secret can be completely altered.
Secret key sharing codes have been widely studied in the past [23]–[25]. In particular, it is known that ReedSolomon codes can be adopted to define secret shares. Linear codes for minimal secret sharing have also been
considered [26]. In this work however, we restrict to Shamir’s secret sharing scheme for simplicity.
B. Data Encryption
Shannon considered the question of perfect secrecy in cryptosystems from the standpoint of statistical security of
encrypted data [27]. There, he concluded that perfect secrecy required the use of keys drawn from a space as large
as the message space. This is practically unusable as it is difficult to use and securely store such large key values.
Thus practical cryptographic systems leverage computational limitations of an adversary to guarantee security over
perfect statistical secrecy.
We define a notion of encryption that is slightly different from that used typically in cryptography. Consider a
message M = (M1 , . . . , Mm ) ∈ M, drawn uniformly at random. Let K ∈ K be a private key drawn uniformly at
random.
Definition 2: Given message, key, and code spaces M, K, C respectively, a private key encryption scheme is a
pair of functions Φ : M × K → C, Ψ : C × K → M, such that for any M ∈ M,
Φ(M; K) = C, such that, Ψ(C, K) = M,

and it is -secure if it is statistically impossible to decrypt the codeword in the absence of the private key K beyond
a confidence of  in the posterior probability. That is, if
max

M∈M,C∈C

P [Ψ(C, K) = M ] ≤ .

(2)

The definition indicates that the encryption scheme is an invertible process and that it is statistically infeasible to
decrypt the plaintext message beyond a degree of certainty. We know that given the codeword C, decrypting the
code is equivalent to identifying the chosen
 private key. In addition, from (2), we observe that the uncertainty in
1
the message estimation is at least log2  . Thus,

log2 1 bits ≤ H(M|C) ≤ log2 |K| bits.

7

Algorithm 1 Coding scheme for data block
n
for z = 1 to m
do
(z)
Generate private key Kt ∼ Unif(K)
(z)
(z)
(z)
Encrypt block with key Kt as Ct = Φ(Bt ; Kt )
(i)
Use a distributed storage code to store Ct among peers in {i : pt = z}
(z)
(z)
(z)
Use Shamir’s (m, m) secret sharing scheme on Kt and distribute the shares (K1 , . . . , Km ) among peers
in the zone
end for

For convenience, we assume without loss of generality that the encrypted codewords are vectors of the same
length as the message from an appropriate alphabet, i.e., C = (C1 , . . . , Cm ).
Since we want to secure the system from corruption by adversaries who are aware of the plaintext message,
we define a stronger notion of secure encryption. In particular, we assume that an attacker who is aware of the
message M, and partially aware of the codeword, C−j = (C1 , . . . , Cj−1 , Cj+1 , . . . , Cm ), is statistically incapable
of guessing Cj in the absence of knowledge of the key K . That is, for any M, C−j ,
1
(3)
P [Φ(M; K) = C|M, C−j ] ≤ , for any Cj .
2
Note that this criterion indicates that the adversary is unaware of at least 1 bit of information in the unknown code
fragment, despite being aware of the message, i.e.,
H(C|M, C−j ) ≥ 1 bit.

C. Distributed Storage Codes
This work aims to reduce the storage cost for blockchains by using distributed storage codes. Distributed storage
codes have been widely studied [16], [28] in different contexts. In particular, aspects of repair and security, including
explicit code constructions have been explored widely [20]–[22], [29], [30]. In addition, information dispersal
algorithms [18], [19] have also considered the question of distributed storage of data. This is a non-exhaustive
listing of the existing body of work on distributed storage and most algorithms naturally adapt to the coding
scheme defined here. However, we consider the simple form of distributed storage that just divides the data evenly
among nodes.
IV. C ODING S CHEME
For this section, assume that at any point of time t, there exists a partition Pt of the set of peers [n] into sets
of size m each. In this work we presume that n is divisible by m. Let each set of the partition be referred to as
n
a zone. Without loss of generality, the zones are referred to by indices 1, . . . , m
. At each time t, for each peer
(i)
n
i ∈ [n], let pt ∈ [ m ] be the index that represents the zone that includes peer i. We describe the zone allocation
scheme in detail in Sec. V.
A. Coding Data Block
In our coding scheme, a single copy of each data block is stored in a distributed fashion across each zone.
Consider the data block Bt corresponding to time t. We use a technique inspired by [17]. First a private key K is
generated at each zone and the data block is encrypted using the key. The private key is then stored by the peers in
the zone using Shamir’s secret key sharing scheme. Finally, the encrypted data block is distributed amongst peers
in the zone using a distributed storage scheme. The process involved in storage and recovery of a block, given a
zone division is shown in Fig. 3.
The coding scheme is given by Alg. 1. In this discussion we will assume that the distributed storage scheme
just distributes the components of the code vector Ct among the peers in the zone. The theory extends naturally
to other distributed storage schemes.

8

Fig. 3: Encryption and decryption process for a given zone allocation. The shaded regions represent individual
zones in the peer network. The data is distributed among peers in each zone and the data from all peers in a zone
are required to recover the transaction data.
In order to preserve the integrity of the data, we use secure storage for the hash values as well. In particular,
at time t, each zone Z ∈ Pt stores a secret share of the hash value Ht−1 generated using Shamir’s (m, m) secret
sharing scheme.
The storage per transaction per peer is thus given by
1
Rs =
(4)
log2 |C| + 2 log2 |K| + 2 log2 p bits,
m
where |C| ≥ q depending on the encryption scheme. In particular, when the code space of encryption matches the
message space, i.e., |C| = q , the gain in storage cost per transaction per peer is given by
m−1
Gain in storage cost = R̃s − Rs =
log2 q − 2 log2 |K| − log2 p bits.
(5)
m
Thus, in the typical setting where the size of the private key space is much smaller than the size of the blocks, we
have a reduction in the storage cost.
B. Recovery Scheme
We now describe the algorithm to retrieve a data block Bt in a blockchain system comprising a total of T
transactions. The algorithm to recover block Bt is described in Alg. 2.
The recovery algorithm exploits information-theoretic security in the form of the coding scheme, and also invokes
the hash-based computational integrity check established in the chain. First, the data blocks are recovered from
the distributed, encrypted storage from each zone. In case of a data mismatch, the system inspects the chain for
consistency in the hash chain. The system scans the chain for hash values and eliminates peers that have inconsistent
hash values. A hash value is said to be inconsistent if the hash value corresponding to the data stored by a node
in the previous instance does not match the current hash value.
Through the inconsistency check, the system eliminates some, if not all corrupted peers. Finally, the majority
consistent data is returned. In practice, the consistency check along the hash chain can be limited to a finite number
of blocks to reduce computational complexity of recovery.
In the implementation, we presume that all computation necessary for the recovery algorithm is done privately
by a black box. In particular, we presume that the peers and clients are not made aware of the code stored at other
peers or values stored in other blocks. Specifics of practical implementation of such a black box scheme is beyond
the scope of this paper.
C. Feasible Encryption Scheme
The security of the coding scheme from corruption by active adversaries depends on the encryption scheme used.
We first describe the necessary condition on the size of the key space.
Lemma 1: A valid encryption scheme satisfying (2) and (3), has
|K| ≥ 2m .

9

Algorithm 2 Recovery scheme for data block
N ← [n]
(z)
n
Using polynomial interpolation
on theshares, compute Kt , for all z ∈ [ m
]

(z)
(z)
(z)
n
Decode blocks Bt ← Ψ Ct ; Kt , for all z ∈ [ m ]
(z)

n
if |{Bt : z ∈ [ m
]}| > 1 then
for τ = t to T do
(z)
n
Using polynomial interpolation from the hash shares, compute Hτ , for all z ∈ [ m
]

(z)
n
z
z
Determine Wτ = Bτ , Hτ −1 , for all
n z ∈ [m] 

o
(z)
(z 0 )
(i)
(i)
Determine hash inconsistencies I ← i ∈ [n] : h Wτ
6= Hτ , z = pτ , z 0 = pτ +1
N ←
\I
n N (i)
o
(pt )
if Bt
: i ∈ N = 1 then
break
end if
end for
end if
nn (i)
oo
(p )
return Majority in
Bt t : i ∈ N

Proof: First, by chain rule of entropy,
H(K, C|M) = H(K) + H(C|M, K) = H(K),

(6)

where (6) follows from the fact that the codeword is known given the private key and the message.
Again using the chain rule and (6), we have
H(K) = H(C|M) + H(K|C, M)
m
X
≥
H(Cj |C−j , M)

(7)

j=1

≥ m,

(8)

where (7) follows from non-negativity of entropy and the fact that conditioning only reduces entropy. Finally, (8)
follows from the condition (3). Since keys are chosen uniformly at random, the result follows.
We now describe an encryption scheme that is order optimal in the size of the private key space upto log factors.
Let T be the set of all rooted, connected trees defined on m nodes. Then, by Cayley’s formula [31],
|T | = m(m−1) .

Let us define the key space by the entropy-coded form of uniform draws of a tree from T . Hence in the description
of the encryption scheme, we presume that given the private key K , we are aware of all edges in the tree. Let
V = [m] be the nodes of the tree and v0 be the root. Let the parent of a node i in the tree be µi .
Consider the encryption function given in Alg. 3. The encryption algorithm proceeds by first selecting a rooted,
connected tree uniformly at random on m nodes. Then, each peer is assigned to a particular node of the tree. For
each node other than the root, the codeword is created as the modulo 2 sum of the corresponding data block and
that corresponding to the parent. Finally, the root is encrypted as the modulo 2 sum of all codewords at other nodes
and the corresponding data block. The bits stored at the root node are flipped with probability half. The encryption
scheme for a sample data block is shown in Fig. 4. We refer to Alg. 3 as Φ from here on.
The decryption of the stored code is as given in Alg. 4. That is, we first determine the private key, i.e., the rooted
tree structure, the bit, and peer assignments. Then we decrypt the root node by using the codewords at other peers.
Then we sequentially recover the other blocks by using the plain text message at the parent node.
Lemma 2: The encryption scheme Φ satisfies (2) and (3).
Proof: Validity of (2) follows directly from the definition of the encryption scheme as the message is not
recoverable from just the encryption.

10

Algorithm 3 Encryption scheme
T ← Unif(T ), K ← Key(T ); b ← Binom(n, 1/2)
Assign peers to vertices, i.e., peer i is assigned to node θi
For all 
i 6= v0 , C̃i← Bi ⊕ Bµi ; flip bits if bi = 1.
C̃v0 ← ⊕j6=v0 C̃j ⊕ Bv0
if bv0 = 1 then
Flip the bits of C̃v0
end if
Store Ci ← C̃θi at each node i in the zone
Store (K, θ) using Shamir’s secret sharing at the peers
Store the peer assignment θi locally at each peer i

Fig. 4: Encryption examples for a zone with six peers. The data block, parameters, tree structure, and corresponding
codes are shown. The two cases consider the same rooted tree with varying peer assignments. The corresponding
change in the code is shown.

To check the validity of (3), note that given the data at all peers other than one node, the adversary is unaware
of the parent of the missing node. Since this is uniformly likely, the probability that the adversary can guess the
encrypted data is at most 1/2, with the maximum being if the root is not recovered.
Lemma 3: The storage cost per peer per transaction under (Φ, Ψ) is
1
log2 q + 2m log2 m + 2 log2 p + 1 bits
(9)
m
Proof: First note that C = Fq . Next, the number of rooted, connected trees on m nodes is given by Cayley’s
formula as m(m−1) . The peer assignments can be stored locally and so cost only log2 m bits per node per transaction.
Thus, the result follows.
From Lemma 3, we can see that the encryption scheme guarantees order-optimal storage cost per peer per transaction
up to log factor in the size of the key space. The security of the encrypted data can be enhanced by increasing the
inter-data dependency by using directed acyclic graphs (DAGs) with bounded in-degree in place of the rooted tree.
Then, the size of storage for the private key increases by a constant multiple.
Rs (Φ, Ψ) =

D. Individual Block Corruption
We now establish the security guarantees of individual blocks in each zone from active adversaries. First, consider
an adversary who is aware of the hash value Ht and wishes to alter it to Ht0 .

11

Algorithm 4 Decryption scheme
Use polynomial interpolation to recover (K, b, θ)
Define θ̃i ← j if θj = i
Flip the bits of Cθ̃v , if bv0 = 1
0
Bv0 ← Cθ̃v ⊕j6=θ̃v Cj
0
0
For all i ∈ [n]\{v0 }, flip bits of Ci if bi = 1
Iteratively compute Bi ← Cθ̃i ⊕ Bµi for all i 6= v0
return B
Lemma 4: Say an adversary, aware of the hash value Ht and the peers in a zone z , wishes to alter the value
stored in the zone to Ht0 . Then, the probability of successful corruption of such a system when at least one peer is
honest, is O(1/q).
Proof: Assume the adversary knows the secret shares of k − 1 peers in the zone. Since the adversary is also
aware of Ht = a0 , the adversary is aware of the coding scheme through polynomial interpolation. However, since
the final peer is honest, the adversary is unaware of the secret share stored here. Hence the result follows.
This indicates that in order to corrupt a hash value, the adversary practically needs to corrupt all nodes in the zone.
To understand corruption of data blocks, we first consider the probability of successful corruption of a zone
without corrupting all peers of the zone.
Lemma 5: Consider an adversary, aware of the plain text B and the peers in a zone. If the adversary corrupts
c2
c < m peers of the zone, then the probability that the adversary can alter the data to B0 is at most m
2 , i.e.,


c
n
P B → B0 in zone z ≤ , for all B 6= B0 , z ∈ [ m
].
(10)
m
Proof: For ease, let us assume that θi = i for all i ∈ [m]. From the construction of the encryption scheme,
we note that if Bi → Bi0 is to be performed, then all blocks in the subtree rooted at i are to be altered as well.
Further, for any change in the block contents, the root is also to be altered.
Thus, a successful corruption is possible only if all nodes in the subtree and the root have been corrupted.
However, the adversary can only corrupt the peers at random and has no information regarding the structure of the
tree. Thus, the simplest corruption is one that alters only a leaf and the root. Thus, the probability of corruption
can be bounded by the probability of corrupting those two particular nodes as follows:


P B → B0 in zone z ≤ P [Selecting a leaf and root in c draws without replacement from [m]]

  
m−2
m
=
/
c−2
c
c(c − 1)
c2
=
≤ 2.
(11)
m(m − 1)
m
n
A consistent corruption of a transaction by an active adversary however requires corruption of at least 2m
zones.
Theorem 1: Consider an active adversary who corrupts c1 , . . . , cn/2m peers respectively in n/2m zones. Then,
the probability of successful corruption across the set of all peers is
Pn/2m !!


2
n
i=1 ci
P Successful corruption B → B0 ≤ exp
log
, for all B 6= B0 .
(12)
m
n

Proof: From Lemma 5 and independence of the encryption across zones, we have
n/2m 2
Y c


0
i
P Successful consistent corruption B → B ≤
m2
i=1




n/2m

n
log m
2m
i=1
n
 Pn/2m 
ci
≤ exp
log 2 i=1
,
n
m
= exp 2

X

log ci − 2

(13)

12

where (13) follows from the arithmetic-geometric mean inequality.
Note that
n/2m
X
n
ci ≤ ,
2
i=1

and thus the upper bound on successful corruption decays with the size of the peer network if less than half the
network is corrupted. From Thm. 1, we immediately get the following corollary.
Corollary 1: If an adversary wishes to corrupt a data block with probability at least 1 − , for some  > 0, then
the total number of nodes to be corrupted satisfies
n/2m

X
i=1

ci ≥

m
n
(1 − ) n .
2

(14)

Cor. 1 indicates that when the network size is large, the adversary practically needs to corrupt at least half the
network to have the necessary probability of successful corruption. Thus we observe that for a fixed zone division,
the distributed storage system loses an arbitrarily small amount of data integrity as compared to the conventional
scheme.
In Sec. V, we introduce a dynamic zone allocation scheme to divide the peer network into zones for different time
slots. We show that varying the zone allocation patterns over time appropriately yields even better data integrity.
With regard to denial of service attacks, since it is infeasible to recover the data block without the share of any
peer in the zone, the system is capable of handling upto 1 denial of service attack per zone. That is, the system
can tolerate a total of n/m denial of service attacks.
E. Data Confidentiality
We earlier stated that the two aspects of security needed in blockchain systems are data integrity and confidentiality. We addressed the question of data integrity in the previous subsection. We now consider confidentiality of
transaction data.
Consider the situation where a peer i in a zone is compromised. That is, an external adversary receives the data
stored by the peer for one particular slot. This includes the secret share of the private key Ki , the encrypted block
data Ci , and secret share corresponding to the hash of the previous block.
From Shamir’s secret sharing scheme, we know that knowledge of Ki gives no information regarding the actual
private key K . Thus, the adversary has no information on the rooted tree used for encryption.
We know that the transaction data are chosen uniformly at random. Since the adversary is unaware of the relation
of the nodes to one another, from the encryption scheme defined, we know that given the entire encrypted data C,
the probability of recovering the block B is uniformly distributed on the set of all possible combinations obtained
for all possible tree configurations. That is, each possibly rooted tree yields a potential candidate for the transaction
data.
This observation implies that
H(B|C) ≤ H(K, B|C) = H(K) + H(B|K, C) = m log2 m.

(15)

We know that the entropy of the transaction block is actually H(B) = log2 q > m log2 m. That is, the adversary
does learn the transaction data partially and has a smaller set of candidates in comparison to the set of all possible
values, given the entire codeword.
However, in the presence of just Ci , the adversary has no way to determine any of the other stored data, nor
does it have any information on the position of this part of the code in the underlying transaction block. Thus,
local leaks reveal very little information regarding the transaction block.
Thus, we observe that the coding scheme also ensures a high degree of confidentiality in case of data leaks from
up to m − 1 peers in a zone.

13

Fig. 5: Dynamic Zone Allocation over Time: Iterate the zone allocation patterns among the peers so that increasing
number of peers need to be corrupted to maintain a consistent chain structure.

V. DYNAMIC Z ONE A LLOCATION
In the definition of the coding and recovery schemes, we presumed the existence of a zone allocation strategy
over time. Here we make it explicit.
Cor. 1 and Lemma 4 highlighted the fact that the distributed secure encoding process ensures that corrupting a
transaction block or a hash requires an adversary to corrupt all peers in the zone. This fact can be exploited to
ensure that with each transaction following the transaction to be corrupted, the client would need to corrupt an
increasing set of peers to maintain a consistent version of the corrupted chain.
In particular, let us assume a blockchain in the following state
(H0 , B1 ) − (H1 , B2 ) − · · · − (Ht−1 , Bt ).

Let us assume without loss of generality that an adversary wishes to corrupt the transaction entry B1 to B01 . The
validated, consistent version of such a corrupted chain would look like
0
(H0 , B01 ) − (H10 , B2 ) − · · · − (Ht−1
, Bt ).

If the zone segmentation used for the encoding process is static, then the adversary can easily maintain such a
corrupted chain at half the peers to validate its claim. If each peer is paired with varying sets of peers across blocks,
then, for sufficiently large t, each corrupted peer eventually pairs with an uncorrupted peer.
Let us assume that this occurs for a set of corrupted peers at slot τ . Then, in order to successfully corrupt the
hash Hτ −1 to Hτ0 −1 , the adversary would need to corrupt the rest of the uncorrupted peers in the new zone. On
the other hand, if the client does not corrupt these nodes, then the hash value remains unaltered indicating the
inconsistencies of the corrupted peers.
Thus, it is evident that if the zones are sufficiently well distributed, corrupting a single transaction would eventually
require corruption of the entire network, and not just a majority. A sample allocation scheme is shown in Fig. 5.
However, the total number of feasible zone allocations is given by
√
n!
2πn  n n
No. of zone allocations =
(16)
n ≈ √
n m ,
(m!) m
2πm m
which increases exponentially with the number of peers and is monotonically decreasing in the zone size m. This
indicates that naive deterministic cycling through this set of all possible zone allocations is practically infeasible.
To ensure that every uncorrupted peer is eventually grouped with a corrupted peer, we essentially need to ensure
that every peer is eventually grouped with every other peer. Further, the blockchain system needs to ensure uniform
security for every transaction and to this end, the allocation process should also be fair.
In order to better understand the zone allocation strategy, we first study a combinatorial problem.

14

Algorithm 5 Dynamic Zone Allocation Strategy
Let ν2 . . . , ν2n0 be the vertices of a 2n0 − 1 regular polygon, and ν1 its center
for i = 2 to 2n0 do
Let L be the line passing through ν1 and νi
M ← {(νj , νk ) : line through νj , νk is perpendicular to L}
M ← M ∪ {(ν1 , νi )}
Construct zones as {νj ∪ νk : (νj , νk ) ∈ M }
end for
restart for loop

Fig. 6: Dynamic Zone Allocation strategy when n = 4m. The zone allocation scheme cycles through matchings of
the complete graph by viewing them in the form of the regular polygon.
A. K -way Handshake Problem
Consider a group of n people. At each slot of time, the people are to be grouped into sets of size m. A peer
gets acquainted with all other peers in the group whom they have not met before. The problem can thus be viewed
as an m-way handshake between people.
n−1
Lemma 6: The minimum number of slots required for every peer to shake hands with every other peer is m−1
.
Proof: At any slot, a peer meets at most m − 1 new peers. Thus the lower bound follows.
Remark 1: Note that each such grouping of nodes constitutes a matching (1-factor) of an m-uniform complete
n . Baranyai’s theorem [32] states that if n is divisible by m, then, there exists a
hypergraph on n nodes, Km

n−1
n
1-factors. However, we do not require every hyperedge to be covered by the
decomposition of Km into m−1
allocation scheme, but only for every node to be grouped with every other node eventually.
Note that for m = 2, it shows that we can decompose a graph into n − 1 different matchings. In this case, the
handshake problem is the same as the decomposition of the graph into matchings. Thus Baranyai’s theorem in this
case gives us the exact number of slots to solve the problem.
We use the tightness observed for the 2-way handshake problem to design a strategy to assign the peers in zones.
n
Let n0 = m
. Partition the peers into 2n0 sets, each containing m/2 peers. Let these sets be given by ν1 , . . . , ν2n0 .
Then, we can use matchings of K2n0 to perform the zone allocation.
Consider Alg. 5. The algorithm provides a constructive method to create zones such that all peers are grouped
with each other over time. The functioning of the algorithm is as in Fig. 6.
Lemma 7: The number of slots required for every peer to be grouped with every other peer is 2n0 − 1.
Proof: The result follows directly from the cyclic decomposition and Baranyai’s theorem for m = 2.
We see that the scheme matches the lower bound on the number of slots for coverage in the order sense. Thus we
consider this allocation strategy in the following discussion. In addition to the order optimality, the method is also
fair in its implementation to all transactions over time.
B. Security Enhancement
From Alg. 2, we know that inconsistent peers are removed from consideration for data recovery. While Lemma 7
n
guarantees coverage in 2 m
slots, we are in fact interested in the number of slots for all uncorrupted peers to be

15

paired with corrupt peers. We now give insight into the rate at which this happens.
We know that an adversary who wishes to corrupt a block corrupts at least n/2 nodes originally.
Lemma 8: Under the cyclic zone allocation strategy, the adversary needs to corrupt at least m new nodes with
each new transaction to establish a consistent corruption.
Proof: From the cyclic zone allocation strategy and the pigeonhole principle, we note that with each slot, at
least two honest nodes in the graph are paired with corrupt nodes. Thus the result follows.
n
Naturally this implies that in the worst case, with 2m
transactions, the data becomes completely secure in the
network. That is, only a corruption of all peers (not just a majority) leads to a consistent corruption of the
transaction.
VI. DATA R ECOVERY AND R EPAIR
A. Recovery Cost
As highlighted in the scheme, the recovery process of a transaction block or hash value requires the participation
of all peers in the zones. However, practical systems often have peers that are temporarily inactive or undergo data
failure. In such contexts the recovery of the data from the corresponding zone becomes infeasible.
Thus it is of interest to know the probability that it may not be feasible to recover an old transaction at any time
slot. Consider a simple model wherein the probability that a peer is inactive in a slot is ρ, and peer activity across
slots and peers is independent and identically distributed.
Theorem 2: For any δ > 0, probability of successful recovery of a data block at any time slot is at least 1 − δ
if and only if m = Θ(log n)
Proof: First, the probability that the data stored can be recovered at any time slot is bounded according to the
union bound as follows:
P [Recovery] = P [there exists a zone with all active peers]
n
≤ (1 − ρ)m .
m
Thus, to guarantee a recovery probability of at least 1 − δ , we need
n
(1 − ρ)m ≥ 1 − δ
m
1
 (log n − log(1 − δ)) .

=⇒ m ≤
1
log 1−ρ

(17)
(18)

Next, to obtain sufficient conditions on the size of the zones, note that
P [Failure] = P [at least one peer in each zone is inactive]

n
n
= (1 − (1 − ρ)m ) m ≤ exp −(1 − ρ)m
,
m
where the last inequality follows from the fact that 1 − x ≤ exp(−x). Hence a sufficient condition for guaranteeing
an error probability of less than δ is


m n
≤δ
exp −(1 − ρ)
m
1

 (log n − log log(1/δ)) .
=⇒ m ≤
(19)
1
log 1−ρ
Thus the result follows.
Thm. 2 indicates that the zone sizes have to be of the order of log n to guarantee a required probability of
recovery in one slot when node failures are possible.

16

Algorithm 6 Bitcoin Mining Algorithm
input: previous block data Wt , acceptable hash value set Ht
output: nonce-appended data W̃t , hash value Ht
for all Nt ∈ N do
W̃t ← (Nt , Wt )
Ht ← h(W̃t )
if Ht ∈ Ht then
break
end if
end for
return W̃t , Ht

B. Data Repair
The distributed secure storage ensures that individual entries stored at each peer can not be recovered from the
knowledge of other entries in the zone. Thus it is not feasible to repair nodes locally within a zone. However, it
suffices to substitute a set of bits such that the code structure is retained.
A node failure indicates that the private key is lost. Thus repairing a node involves recoding the entire zone using
data from a neighboring zone. Thus owing to the encryption, it is difficult to repair nodes upon failure.
Thus, the transaction data is completely lost if one peer from every zone undergoes failure. That is, the system
can handle up to n/m node failures. This again emphasizes the need to ensure that m is small in comparison to n.
VII. C OMPUTATION AND E NERGY
As stated in Sec. II-B, conventional blockchain systems incorporate constraints on the hash values of transactions over time to enhance the security of data blocks. Enforcing such constraints however translates to higher
computational load on the block validation (mining) process.
Let us elaborate with the example of the bitcoin. The bitcoin network employs the SHA-256 algorithm for
generating the hash values [33]. At each time slot, the network chooses a difficulty level at random from the set
of hash values, Fp . The role of the miner in the network is to append an appropriate nonce to the block such that
the corresponding hash value satisfies the difficulty level for the slot. The nonce-appended block and the generated
hash value are then added to the blockchain. To be precise, the hash is applied twice in bitcoin. First, the block is
hashed and then the nonce is appended to this version and rehashed. However, for simplicity, we just presume that
the nonce is added directly to the hash.
At any slot t, let the transaction block be Bt and previous hash Ht−1 . Let the set of all possible nonce values
be N = {0, 1}b , where b is the number of bits appended to the transaction block, and is chosen sufficiently large
such that the hash criterion will be satisfied for at least one value. Let the nonce added by the miner be Nt . Then,
the miner searches for Nt ∈ N such that
h(Ht−1 , Nt , Bt ) ∈ Ht ,

where Ht ⊆ Fp is the set of permissible hash values at time t as determined by the difficulty level.
However, due to the pre-image resistance of the cryptographic hash function, the miner is not capable of directly
estimating the nonce, given the data block and difficulty level. This in conjunction with collision resistance of
the hash function implies that the best way for the miner to find a nonce that corresponds to a hash value in the
desired range is to perform brute-force search. Thus, the typical miner in the bitcoin network adopts Alg. 6 to add
a transaction to the blockchain. The brute-force search for nonce value results in a large computational cost which
in turn results in an increase in the consumption of electricity as reflected in the hash rate as was shown in Fig. 1c.
The imposition of the constraints on the hash values for each block enhances the integrity of data blocks. Consider
an adversary who corrupts a data block. Establishing consistency in the chain following such a corruption requires
not only recomputing a hash value, but doing so such that the hash values adhere to the constraints. Each such
computation of a hash value is computationally expensive. Thus, the security established through the use of such

17

constraints is essentially equivalent to preventing the addition of incorrect transactions to the chain, as is to be
prevented by expensive mining.
We now use the notion of an ideal cryptographic hash function to quantify the expected computational cost. Let
us again presume that the message space is bounded and given by M. If M ∼ Unif(M) and h(·) is an ideal
cryptographic hash function, then H = h(M) is also distributed uniformly in the space of hash values H. Thus,
extending from this notion, for any Ht ⊂ H, the set of values Mt ⊂ M such that h(M) ∈ Ht for any M ∈ Mt
has a volume proportional to the size of the hash subset, i.e., |Mt | ∝ |Ht |.
We know that the mining algorithm exhaustively searches for a nonce value that matches the required hash
constraints. Now, if the hash value is chosen at random, and the transaction block is given to be uniformly random,
then searching for the nonce by brute-force is equivalent, in average to the experiment of drawing balls from an
urn without replacement.
Theorem 3: Let q = |N |, |Ht | = p0 be given, and let Ht be chosen at uniformly at random from the set of
all subsets of H with size p0 . Let M (Wt , Ht ) be the number of steps taken by Alg. 6 to find a valid hash. If
1  p0  p, and b ≥ p0 is sufficiently large, then
h  0 
 i


0
E M (Wt , Ht )|Wt , |Ht | = p0 = E M 0 pp q, 1 − pp q ,
(20)
where M 0 (a, b) is the number of turns it takes, drawing without replacement from an urn containing a1 blue and
a2 red balls, to get the first blue ball.
Proof: First, we know that the volume of permissible nonce values is proportional to the size of the hash subset,
i.e., is cp0 , for some constant c. Any message from this set is uniformly likely as the corresponding constraint set
is drawn uniformly. Further, we know that for p0 = p, any nonce is permissible and so cp = q .
Thus, we essentially are drawing without replacement as the brute-force search does not resample candidates,
0
and we are drawing till we get an element from the set of size pp q in a set of size q . This is essentially the same
as would be the case for sampling without replacement from the urn. Since the uniformity in trials holds only on
average, the result follows.
Corollary 2: The expected computational cost of the mining algorithm is given by
 


p
0
E M (Wt , Ht )|Wt , |Ht | = p = O
,
p0
for any 1  p0  p, and b ≥ p0 sufficiently large.
Proof: The result follows directly from Thm. 3 and the expected number of draws for the sampling without
replacement experiment.
In practical systems, a moderate range of values of p0 are used as a very small subset might not be satisfied with
a bounded nonce set and a large subset leads to loss of data integrity, as almost any value works. Thus practical
systems choose values in a range wherein it is sufficiently difficult to generate viable candidates satisfying the hash
constraint.
Thus we note that the average computational cost can be very high in bitcoin-like systems. In particular, the
bitcoin uses 256 bit hash values. That is, log2 p = 256, while log2 q = 32. This in turn implies that the potential
candidate space to search is very large thereby leading to increased energy consumption.
On the other hand, in our proposed dynamic distributed storage scheme, the hash values computed are not
restricted by these constraints. Instead we enhance data integrity in the blockchain using information-theoretic
secrecy instead of a computational one. This way, computing hash values and the corresponding secret shares
is computationally inexpensive. Further, we have shown that the integrity is guaranteed through the consistency
checks. Thus, the scheme defined here guarantees a reduction in the computational cost without compromising on
security.
VIII. C ONCLUSION
In this work, we considered fundamental questions that hinder the scaling of conventional blockchain systems.
We addressed the issue of increasing storage costs associated with large-scale blockchain systems. Using a novel
combination of secret key sharing, encryption, and distributed storage, we developed coding schemes that were
information-theoretically secure and reduced the storage to a fraction of the original load. We also showed that the
resulting storage cost was optimal up to log factors in the size of the private key.

18

We showed that the distributed storage code ensures both data integrity and confidentiality, with very little loss in
comparison to the conventional schemes. We then used a dynamic segmentation scheme to enhance data integrity.
We described a zone allocation strategies using decomposition of a complete graph into matchings that was order
optimal in the time for complete coverage.
We also investigated the energy requirements of conventional bitcoin-like blockchain systems by studying the
computational complexity associated with establishing the hashchain. We highlighted the need for simple hashing
schemes and showed that our coding scheme guarantees a significant reduction in energy consumption.
Notwithstanding these benefits, the coding scheme hinges centrally on distributing the transaction data securely
among a set of peers. Thus, the recovery and repair costs associated with the scheme are higher than conventional
systems. In particular, through probabilistic recovery arguments, we established order optimal necessary and sufficient conditions on the size of the zones in our construction. Further, we also highlighted the fact that local repair
is infeasible in this scheme and requires explicit recomputation of the codes corresponding to the zone.
Additionally, the encoding and recovery schemes presumed the feasibility of performing them using black box
methods, such that the peers do not learn the codes pertaining to other peers. We did not attempt to define explicit
methods of constructing such black box schemes in this work, and this would be the focus of future research.
Another aspect to be addressed here is the computational protocols and the related costs to be used to distributed
the codewords in the peer-to-peer network. Since the data stored by individual nodes varies, owing to the dynamic
distributed storage scheme, it is essential to communicate the individual blocks in a point-to-point manner, rather
than as a broadcast, as is done in conventional blockchain systems. This process naturally implies an increased
communication cost in the network. Since this is closely related to the code construction methodology, this aspect
is also to be considered in detail in future research.
This work establishes the feasibility of enhancing blockchain performance and reducing associated costs through
novel use of coding-theoretic techniques. We believe such methods enhance the ability of blockchain systems to
scale to address practical applications in a variety of industries.
ACKNOWLEDGMENT
The authors would like to thank Prof. Andrew Miller for references and useful discussions on blockchain systems.
R EFERENCES
[1] J. Bonneau, A. Miller, J. Clark, A. Narayanan, J. A. Kroll, and E. W. Felten, “SoK: Research perspectives and challenges for bitcoin
and cryptocurrencies,” in Proc. 2015 IEEE Symp. Security Privacy, May 2015, pp. 104–121.
[2] A. Narayanan, J. Bonneau, E. Felten, A. Miller, and S. Goldfeder, Bitcoin and Cryptocurrency Technologies: A Comprehensive
Introduction. Princeton: Princeton University Press, 2016.
[3] D. Tapscott and A. Tapscott, Blockchain Revolution: How the Technology behind Bitcoin is Changing Money, Business, and the World.
New York: Penguin, 2016.
[4] S. Underwood, “Blockchain beyond bitcoin,” Commun. ACM, vol. 59, no. 11, pp. 15–17, Oct. 2016.
[5] A. Azaria, A. Ekblaw, T. Vieira, and A. Lippman, “Medrec: Using blockchain for medical data access and permission management,”
in 2nd Int. Conf. Open Big Data (OBD 2016), Aug. 2016, pp. 25–30.
[6] M. J. Casey and P. Wong, “Global supply chains are about to get better, thanks to blockchain,” Harvard Bus. Rev., Mar. 2017.
[Online]. Available: https://hbr.org/2017/03/global-supply-chains-are-about-to-get-better-thanks-to-blockchain
[7] M. Swan, Blockchain: Blueprint for a New Economy. Sebastopol, CA: O’Reilly Media, Inc., 2015.
[8] M. Iansiti and K. R. Lakhani, “The truth about blockchain,” Harvard Bus. Rev., vol. 95, no. 1, pp. 118–127, Jan. 2017.
[9] A. Kosba, A. Miller, E. Shi, Z. Wen, and C. Papamanthou, “Hawk: The blockchain model of cryptography and privacy-preserving
smart contracts,” in Proc. 2016 IEEE Symp. Security Privacy, May 2016, pp. 839–858.
[10] Blockchain info. [Online]. Available: https://blockchain.info/home
[11] K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, E. G. Sirer, D. Song, and R. Wattenhofer,
“On scaling decentralized blockchains,” in Financial Cryptography and Data Security, ser. Lecture Notes in Computer Science, J. Clark,
S. Meiklejohn, P. Y. A. Ryan, D. Wallach, M. Brenner, and K. Rohloff, Eds. Berlin: Springer, 2016, vol. 9604, pp. 106–125.
[12] M. Vilim, H. Duwe, and R. Kumar, “Approximate bitcoin mining,” in Proc. 53rd Des. Autom. Conf. (DAC ’16), Jun. 2016, pp. 97:1–97:6.
[13] C. Malmo, “Bitcoin is unsustainable,” Jun. 2015. [Online]. Available: https://motherboard.vice.com/en us/article/ae3p7e/
bitcoin-is-unsustainable
[14] P. Fairley, “Blockchain world - feeding the blockchain beast if bitcoin ever does go mainstream, the electricity needed to sustain it will
be enormous,” IEEE Spectr., vol. 54, no. 10, pp. 36–59, Oct. 2017.
[15] A. Shamir, “How to share a secret,” Commun. ACM, vol. 22, no. 11, pp. 612–613, Nov. 1979.
[16] A. G. Dimakis and K. Ramchandran, “Network coding for distributed storage in wireless networks,” in Networked Sensing Information
and Control, V. Saligrama, Ed. New York: Springer, 2008, pp. 115–136.

19

[17] H. Krawczyk, “Secret sharing made short,” in Advances in Cryptology — CRYPTO ’93, ser. Lecture Notes in Computer Science, D. R.
Stinson, Ed. Berlin: Springer, 1994, vol. 773, pp. 136–146.
[18] M. O. Rabin, “The information dispersal algorithm and its applications,” in Sequences, R. M. Capocelli, Ed. New York: Springer-Verlag,
1990, pp. 406–419.
[19] C. Cachin and S. Tessaro, “Asynchronous verifiable information dispersal,” in 24th IEEE Symp. Rel. Distrib. Sys. (SRDS’05), Oct.
2005, pp. 191–201.
[20] K. V. Rashmi, N. B. Shah, P. V. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed
storage,” in Proc. 47th Annu. Allerton Conf. Commun. Control Comput., Sep. 2009, pp. 1243–1249.
[21] A. S. Rawat, O. O. Koyluoglu, N. Silberstein, and S. Vishwanath, “Optimal locally repairable and secure codes for distributed storage
systems,” IEEE Trans. Inf. Theory, vol. 60, no. 1, pp. 212–236, Jan. 2014.
[22] S. Pawar, S. El Rouayheb, and K. Ramchandran, “Securing dynamic distributed storage systems against eavesdropping and adversarial
attacks,” IEEE Trans. Inf. Theory, vol. 57, no. 10, pp. 6734–6753, Oct. 2011.
[23] R. J. McEliece and D. V. Sarwate, “On sharing secrets and Reed-Solomon codes,” Commun. ACM, vol. 24, no. 9, pp. 583–584, Sep.
1981.
[24] E. Karnin, J. Greene, and M. Hellman, “On secret sharing systems,” IEEE Trans. Inf. Theory, vol. IT-29, no. 1, pp. 35–41, Jan. 1983.
[25] W. Huang, M. Langberg, J. Kliewer, and J. Bruck, “Communication efficient secret sharing,” IEEE Trans. Inf. Theory, vol. 62, no. 12,
pp. 7195–7206, Dec. 2016.
[26] J. L. Massey, “Minimal codewords and secret sharing,” in Proc. 6th Joint Swedish-Russian Int. Workshop Inf. Theory, Aug. 1993, pp.
276–279.
[27] C. E. Shannon, “Communication theory of secrecy systems,” Bell Syst. Tech. J., vol. 28, pp. 656–715, Oct. 1949.
[28] A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, “A survey on network codes for distributed storage,” Proc. IEEE, vol. 99, no. 3,
pp. 476–489, Mar. 2011.
[29] Y. Wu, A. G. Dimakis, and K. Ramchandran, “Deterministic regenerating codes for distributed storage,” in Proc. 45th Annu. Allerton
Conf. Commun. Control Comput., Sep. 2007, pp. 242–249.
[30] N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Distributed storage codes with repair-by-transfer and nonachievability
of interior points on the storage-bandwidth tradeoff,” IEEE Trans. Inf. Theory, vol. 58, no. 3, pp. 1837–1852, Mar. 2012.
[31] R. Durrett, Random Graph Dynamics. Cambridge: Cambridge University Press, 2007.
[32] Z. Baranyai, “The edge-coloring of complete hypergraphs I,” J. Comb. Theory, Ser. B, vol. 26, no. 3, pp. 276–294, 1979.
[33] H. Gilbert and H. Handschuh, “Security analysis of SHA-256 and sisters,” in Selected Areas in Cryptography, ser. Lecture Notes in
Computer Science, M. Matsui and R. J. Zuccherato, Eds. Berlin: Springer, 2004, vol. 3006, pp. 175–193.

