In a blockchain Data Availability Attack (DAA), a malicious node publishes a block header but withholds part of the block, which contains invalid transactions. Honest full nodes, which can download and store the full ledger, are aware that some data are not available but they have no formal way to prove it to light nodes, i.e., nodes that have limited resources and are not able to access the whole blockchain data. A common solution to counter these attacks exploits linear error correcting codes to encode the block content. A recent protocol, called SPAR, employs coded Merkle trees and low-density parity-check codes to counter DAAs. In this paper, we show that the protocol is less secure than claimed, owing to a redefinition of the adversarial success probability. As a consequence we show that, for some realistic choices of the parameters, the total amount of data downloaded by light nodes is larger than that obtainable with competing solutions.
A blockchain can be seen as an ordered list of blocks, each containing a set of transactions
occurred among the participants of a peer-to-peer network. The recent discovery of Data
Availability Attacks (DAAs) represents a new threat against blockchain security. Since the
DAA introduction in [
In fact, scalability, which is related to the ability of supporting large transaction rates,
represents one of the main issues in most existing blockchains [
Light nodes aim at downloading as less data as possible. For instance, they may store only
the block headers, which unambiguously identify the content of the blocks. However, in a
setting with relatively few full nodes, collusion among them is more probable; this makes light
nodes more susceptible to DAAs. In fact, the aim of a DAA is to make at least one light node
accept a block which has not been fully disclosed to the network. This can happen if and only if
honest full nodes are prevented from preparing fraud proofs, i.e., demonstrations that the block
is invalid [
One of the most promising countermeasures to DAAs consists in encoding the blocks through
some error correcting code. Encoding introduces redundancy and distributes the information
of each transaction across all the codeword symbols, so that recovering a small portion of
an encoded block may be enough to retrieve the entirety of its contents through decoding.
This strategy, combined with a sampling process in which light nodes ask for fragments of
an encoded block and then gossip them to the connected full nodes, ensures that malicious
block producers are forced to reveal enough pieces of the invalid block [
In a recent paper [
Our contribution In this paper we study the security of the SPAR protocol. Namely, we
recompute the adversarial success probability with the consideration that deceiving at least a
single light node is a success for the attacker, which is the same scenario considered in [
Paper organization The paper is organized as follows. In Section 2 we describe the notation and some background. In Section 3 we introduce a general framework to study DAAs. In Section 4 we provide some numerical results. Finally, in Section 5 we draw some conclusions.
In this section we establish the notation used throughout the paper, and recall some background notions.
Given two integers a and b, we use [a, b] to indicate the set of integers x such that a ≤ x ≤ b. For a set A, we use |A| to denote its cardinality. We denote with Fq the finite field with q elements. Given a vector v, we use supp(v) to denote its support, i.e., the set containing the positions of its non-zero entries and wH(v) to denote its Hamming weight, that is, the size of its support. Given an integer l and a set A, Al is the set of vectors of length l taking entries in A. Given a matrix M, mi,j denotes its entry at row i and column j, Mi,: denotes the i-th row, and M:,j denotes the j-th column. Given a set A, M:,A (respectively, MA,:) represents the matrix formed by the columns (respectively, rows) of M indexed by A.
We denote by Concat the string concatenation function and by Hb(·) the binary entropy function. Moreover, we denote by Hash a cryptographic hash function, with codomain D. Given some vector a, we use T (a) to denote a generic hash tree structure constructed from a and using Hash as underlying function. The root of the tree is denoted as T .Root(a); it generically takes values in Dt and is a one-way function. With analogous notation, by T .Proof(a, i) we refer to the proof that the i-th entry of a is a leaf in the base layer of the tree. Notice that, when Hash is properly chosen, then for any pair of strings a 6= a′ we have T .Root(a) 6= T .Root(a′) and, for any index i, T .Proof(a, i) 6= T .Proof(a′, i) with overwhelming probability (say, not lower than 1 − 2−256 for modern hash functions); therefore, for the sake of simplicity, in the following we assume the absence of root and proof collisions.
LDPC codes are a family of linear codes characterized by parity-check matrices having a relatively small number of non-zero entries compared to the number of zeros. Namely, if an LDPC H ∈ Fr×n has full rank r < n and row and column weight in the order of log(n) and q log(r), respectively, then it defines an LDPC code with length n and dimension k = n − r, with code rate R = nk . If all the rows (columns, respectively) of H have the same Hamming weight, we denote it as w (v, respectively). The associated code is C = c ∈ Fqn cH⊤ = 0 , where ⊤ denotes transposition. The rows of the parity-check matrix define the code parity-check equations, that is, n X cj hi,j = 0, ∀i ∈ [1, r], ∀c ∈ C. j=1 (1) Equivalently, any code can be represented in terms of a generator matrix G ∈ Fk×n, which q forms a basis for C.
In an Erasure Channel (EC), some of the codeword symbols are replaced with the erasure
symbol ǫ. To this end, we express the action of an EC as c + e′, where c is the input sequence
and e′ ∈ {0, ǫ}n, with ǫ such that, conventionally, ǫ + a = ǫ, ∀a ∈ Fq. A decoding algorithm
for the EC aims to obtain a codeword by substituting each erasure with an element from Fq. In
the case of LDPC codes, the most common decoder used over the EC is the peeling decoder [
SPAR is based on a novel hash tree called Coded Merkle Tree (CMT), combined with an ad-hoc hash-aware peeling decoder.
Coded Merkle Tree A CMT is a hash tree which is constructed from ℓ linear codes {C(1), · · · , C(ℓ)} over Fq; the i-th code has length ni and dimension ki. Each code C(i) is defined by the systematic generator matrix G(i) = [Iki | Ai], with Ai ∈ Fqki×(ni−ki) and Iki being the identity matrix of size ki. The CMT uses an integer b which must be a divisor of all codelength values n1, · · · , nℓ. Furthermore, one needs to have partitions for the sets [1, ni], for i ∈ [1, ℓ − 1]. Namely, we have Si = nS1(i), · · · , Sk(ii)+1 o which is a partition of [1, ni], such that the S(i) are all disjoint and each one contains b elements, since ki+1 = ni/b. Starting from j c ∈ C(1), we build the associated CMT T ′(c) as follows: 1. set i = 1; 2. for j ∈ {1, · · · , ki+1}, set with {z1, · · · , zb} = Sj(i); uj = Concat Hash c(zi1) , · · · , Hash c(zib) 3. encode u = [u1, · · · , uki+1 ] as1 c = uG(i+1); 4. if i < ℓ − 1, increase i and restart from step 2), otherwise set T ′.Root(c) = u. 1Notice that, when LDPC codes are considered, encoding is conveniently performed using the parity-check matrix rather than the generator matrix. This implementation detail does not affect the conclusions of our analysis but, considering encoding with the parity-check matrix, we would unnecessarily burden the notation. Therefore, we stick to encoding with the generator matrix. Hash-aware peeling decoder A hash-aware peeling decoder, described in [13, Section 4.3], is an algorithm that decodes a set of ℓ words which are expected to constitute a CMT. Namely, let {x(1), · · · , x(ℓ)}, where x(i) ∈ {Fq ∪ {ǫ}}ni, be the words to be decoded. The hash-aware peeling decoder works in a top-down fashion and, at every iteration, uses the peeling decoder strategy (i.e., recover erasures that participate in univariate parity-check equations) for any layer of the CMT. Additionally, the hash-aware peeling decoder verifies the consistency between symbols of connected layers of the tree via hash functions, whilst the symbols are recovered. Decoding fails whenever a stopping set or a failed parity-check equation is met, just like the conventional peeling decoder. Furthermore, the hash-aware peeling decoder fails in case check consistency fails for some layer. Finally, an undetected error is met (but not recognized by the decoder) if the decoded sequence is a codeword, but not the original one.
In this section we present a general framework to study DAAs, and then apply it to the SPAR
protocol. For brevity, we only give the fundamentals of the model; for further details concerning
DAAs, we refer the interested reader to [
We consider a game in which an adversary A exchanges messages with m players P 1, · · · , P m, who cannot communicate among themselves. Each player has access to an oracle O , who can only perform polynomial time operations. Every list of transactions is seen as a vector u ∈ Fqk. We assume that the following information is publicly available: - a validity function f : Fqk 7→ {False, True}, which depends on the blockchain rules and on its current status; - a k-dimensional code C ⊆ Fqn with generator matrix G; - two hash trees T , T ′ (the former is constructed upon the uncoded data u, while the latter is constructed upon the codeword c = uG).
The game proceeds as follows: 1. A chooses u ∈ Fqk such that f (u) = False and a vector c˜ ∈ Fn; q 2. A challenges the players with (hu, hc), where hu = T .Root(u), hc = T ′.Root(c˜); 3. each player Pi selects Ji ⊆ [1, n] with size s; 4. A receives U = Sim=1 Ji; 5. to reply to a query containing the index i, A must send {˜ci, T .Proof(c˜, i)}; A is free to choose which queries to reply and which ones to ignore; 6. if a player does not receive a valid reply for any of his queries, then he discards (hu, hc); 7. the players gossip all the valid answers to O , that aims to produce a proof for one of the following facts: a) ∃c˜ 6∈ C, such that T ′.Root(c˜) = hc; b) ∃c˜ ∈ C such that T ′.Root(c˜) = hc, c˜ = u˜G and T .Root(u˜) 6= hu; c) ∃c˜ ∈ C such that T ′.Root(c˜) = hc, c˜ = u˜G, T .Root(u˜) = hu and f (u˜) = False.
Let us also define two properties.
Property 1. Soundness: if a player accepts (hu, hc), then O will be able to recover c˜ (and u˜) within a finite maximum delay.
Property 2. Agreement: if a player accepts (hu, hc), then all the other players will accept (hu, hc) within a finite maximum delay.
Clearly, if A wins the game, which happens with probability γ, soundness and agreement are caused to fail. We denote by γ the Adversarial Success Probability (ASP), i.e., the probability that A wins a random execution of the game.
It can be easily seen that, in our model, the players P 1, · · · , P m correspond to the light nodes
connected to a malicious node modeled by A . The oracle O instead represents the fact that we
assume any light node must be connected to at least one honest full node wishing to broadcast
fraud proofs. We remark that the hypotheses and properties that underlie our model are the
same under which DAAs have been studied in the literature [
In SPAR, the CMT is instantiated using the code design procedure considered in [
Let u ∈ Fqk denote the list of transactions of a new block. Then, a correctly constructed header contains hu = T .Root(u) and hc = T ′.Root(c), with c = uG(1). However, in case of a DAA, the word c˜ = c + e upon which hc is constructed may be any vector picked from Fn. q The authors of SPAR study the protection of the protocol against DAAs; namely, they initially consider the following two cases: a) if c˜(i) 6∈ C(i), then the proof consists in sending the value of all the symbols that participate in a failed parity-check equation, except for one of them, together with their CMT proofs; we refer to such a proof as parity-check equation incorrect-coding proof ; b) if c˜ = c but f (u) = False, the adversary succeeds only if the samples received by the oracle are not enough to allow the recovery of u from c˜ through decoding.
The scenario where the oracle finds a hash inconsistency is also considered, in which case O can broadcast a fraud proof to the light nodes, called here hash inconsistency incorrect-coding proof.
The following bound for the ASP is derived [13, Theorem 1]:
γ ≤ max n(1 − αmin)s , 2maxi{Hb(αi)ni+ms log2(1−αi)}o
(2)
where αi is the undecodable ratio of C(i), that is, the minimum fraction of coded symbols
the adversary needs to make unavailable in order to prevent the oracle from full decoding,
αmin = mini(αi), and s is the number of queries performed by each light node. Therefore, if
the oracle is not able to decode due to the presence of a stopping set, the adversarial success
probability computed in [
We argue here, instead, that a sufficient condition to break the soundness and agreement
as defined in [
Proposition 1. In SPAR, an adversary cannot cause the soundness and agreement to fail with probability γ ≤ min{1, max{1 − [1 − (1 − αmin)s]m , t2}}, (3) where t2 = 2maxi{b(αi)ni+ms log(1−αi)}.
Proof. According to Property 1, the soundness fails if at least one player accepts the block header, but the oracle will not be able to dispatch a fraud proof. The probability that exactly one player accepts the challenge is lower than or equal to (1 − αmin)s and, therefore, the probability that exactly one player discards the challenge is larger than or equal to 1 − (1 − αmin)s. Considering that there are m players, the probability that all of them discard the block is larger than or equal to [1 − (1 − αmin)s]m. So, finally, the probability that at least a player accepts the block is lower than or equal to
1 − [1 − (1 − αmin)s]m .
The rest of the proof is as in [13, Theorem 1].
Let us consider the code parameters proposed in [
In Table 1 we report the upper bound (2) and the newly assessed upper bound (3) on the ASP, for some values of s, considering n = 4096 and m = 1024; notice that the new value is never smaller than the previously computed upper bound. Clearly, this may have severe security consequences.
As obvious and expected, the upper bound on ASP is a decreasing function of the number of samples s. So, once a target adversarial success probability is chosen, it is possible to compute a lower bound for the value of s each player needs to ask in order to stay below it, simply by inverting (2) and (3). Considering the same parameters as above (n = 4096 and m = 1024) we obtain the results in Table 2. where B is the block size, y is the hash size and b, introduced in Section 2.3, is the number of batched hashes in each layer. Finally, t is the number of hashes in the root and determines the header size H = tℓH, where ℓH = 256 is the binary length of the digests.
In Table 3, we assess the sampling cost S, normalized with respect to the block size B,
assuming m = 1024, R = 1/4, k = 1024 symbols, B = 1 MB, b = 8, t = 256 hashes and
some different values of the ASP γ. A comparison with the optimized ASBK protocol [
However, it should be noticed that SPAR has the advantage of relying on a fixed header size whereas in ASBK the header size increases as the square root of the block size. Therefore, considering the same setting, in Tables 4, 5 and 6 we have compared the total amount of downloaded data D (sampling cost plus header size) using SPAR, to that obtained using the optimized ASBK protocol, The tables also report the header size H for the optimized ASBK protocol, when B = 1 MB, B = 10 MB and B = 100 MB, respectively. The header size for SPAR does not depend on the block size and its value is tℓH = 8.192 kB. Notice that this amount of data must be downloaded by any light node during the regular course of the protocol, independently of the malicious behaviour of some full nodes, possibly resulting in the additional download of fraud proofs.
We observe that, for relatively small and moderate values of the block size, despite the larger header size, the use of the ASBK protocol is preferable even if a weak adversary is taken into account. Instead, when the block size is large, SPAR is very convenient in the presence of a weak adversary, but still more costly than ASBK if the adversary is strong.
By carefully analyzing the SPAR protocol we have shown that the actual sampling cost required by the scheme, in order to achieve target security guarantees, is much larger than that initially expected. Moreover, it is shown that, in many practical scenarios, the amount of data that light nodes have to download is larger than that of other well-known schemes.