# Polar Coded Merkle Tree: Improved Detection of Data Availability Attacks in
Blockchain Systems

Debarnab Mitra, Lev Tauz, and Lara Dolecek  Department of Electrical and
Computer Engineering, University of California, Los Angeles, USA
email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Light nodes in blockchain systems are known to be vulnerable to data
availability (DA) attacks where they accept an invalid block with unavailable
portions. Previous works have used LDPC and 2-D Reed Solomon (2D-RS) codes
with Merkle Trees to mitigate DA attacks. While these codes have demonstrated
improved performance across a variety of metrics such as DA detection
probability, they are difficult to apply to blockchains with large blocks due
to generally intractable code guarantees for large codelengths (LDPC), large
decoding complexity (2D-RS), or large coding fraud proof sizes (2D-RS). We
address these issues by proposing the novel _Polar Coded Merkle Tree_ (PCMT)
which is a Merkle Tree built from the encoding graphs of polar codes and a
specialized polar code construction called _Sampling-Efficient Freezing_
(SEF). We demonstrate that the PCMT with SEF polar codes performs well in
detecting DA attacks for large block sizes.

##  I Introduction

Decentralization and security properties of blockchains have led to their
applications in a wide variety of fields [1, 2, 3, 4, 5, 6, 7]. A blockchain
is an immutable ledger of transaction blocks. Full nodes in a blockchain
system store the entire ledger and validate transactions. However, for better
scalability, blockchains also run _light nodes_ who store the header of each
block and cannot validate transactions. Light nodes rely on honest full nodes
for _fraud proofs_ [8] in order to reject invalid blocks.

Blockchains where light nodes are connected to a majority of malicious full
nodes are vulnerable to _data availability (DA) attacks_ [8, 9]. In this
attack, a malicious full node (i.e., an adversary) generates a block with
invalid transactions and hides the invalid portion of the block from other
nodes. This action prevents honest nodes from sending fraud proofs to the
light nodes. Light nodes, in this scenario, randomly request/sample chunks of
the block from the block generator and detect a DA attack if any request is
rejected. To improve the detection of a DA attack by light nodes, erasure
coding has been proposed to encode the block [8] which forces the adversary to
hide a larger fraction of the encoded block. However, erasure coding allows
the adversary to carry out an _incorrect-coding (IC) attack_ by incorrectly
generating the coded block, in which case honest full nodes can send an _IC
proof_ to the light nodes to reject the block [8], [9]. Recently, [10]
proposed a technique to mitigate DA attacks without requiring IC-proofs,
however [10] employs complex cryptographic computations. We remark that
channel coding has been considered to mitigate a variety of issues in
blockchains [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25].

The first paper to address DA attacks via coding used 2D Reed-Solomon (RS)
codes to encode each block [8]. Their method was recently optimized in [26].
While offering a high probability of detecting DA attacks, 2D-RS codes result
in large IC proof sizes and decoding complexity. Large IC-proof sizes can be
exploited by the adversary to congest the network and cause issues such as
denial of service attacks, reduced transaction throughput, etc.. To improve
upon 2D-RS codes, authors in [9] proposed the _Coded Merkle Tree (CMT)_ : a
Merkle tree [1] where each layer is encoded using a Low-Density Parity-Check
(LDPC) code. LDPC codes reduce the IC proof size compared to 2D-RS codes due
to their sparse parity check equations. LDPC codes also allow the use of a low
complexity peeling decoder [27] for decoding the CMT where the probability of
failure to detect DA attacks depends on the minimum stopping set size of the
LDPC code [9].

Application of coding has to be carefully considered depending on the size of
the transaction blocks in blockchains which can range from a few MBs (small
block size), e.g., Bitcoin [28], Bitcoin Cash[29], to hundreds of MBs (large
block size), e.g., Bitcoin SV[30]. For large block sizes, large code lengths
are required since large code lengths allow for smaller partitioning of the
block, thereby reducing the network bandwidth requirement. In regard to the
CMT, previous work in [9] has considered random LDPC codes for large code
lengths. However, due to the random construction, the approach has a non-
negligible probability of generating bad codes [9] which undermines the
security of the system. At the same time, works in [11, 12] have provided
deterministic LDPC codes with short code lengths based on the PEG algorithm
[31] that result in a low probability of failure. However, the NP-hardness of
determining the minimum stopping set size of LDPC codes [32] makes it
difficult to provide an efficiently computable guarantee on the probability of
failure for large code lengths. As such, designing a CMT with LDPC codes at
large code lengths/block sizes is difficult. To mitigate these issues, we
propose _Polar Coded Merkle Tree (PCMT)_ : a CMT built using the encoding
graph of polar codes [33] (we refer to a CMT built using LDPC codes as an
LCMT). Although polar codes have dense parity check matrices [34], they have
sparse encoding graphs, which result in a small IC proof size in the PCMT. We
provide a specialized polar code construction called _Sampling-Efficient
Freezing (SEF) Algorithm_ that i) provides a low probability of failure to
detect DA attacks; ii) allows flexibility in designing polar codes of any
lengths. We demonstrate that SEF Polar codes have an efficiently computable
guarantee on the probability of failure which simplifies system design at
large block sizes. We then demonstrate that for large block sizes, a PCMT
built using SEF Polar codes result in a lower probability of failure compared
to LDPC codes designed by the PEG algorithm.

The rest of this paper is organized as follows. In Section II, we provide the
preliminaries and the system model. In Section III, we provide our
construction method for the PCMT. We present the SEF algorithm in Section IV.
Finally, we provide simulation results and performance comparisons in Section
V.

##  II Preliminaries and System Model

Notation: Let $\mathbf{F}_{2}=\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ and
$\mathbf{T}_{2}=\begin{bmatrix}1\\\ 2\end{bmatrix}$. For a vector
$\mathbf{a}$, let $\mathbf{a}(i)$ and $\min(\mathbf{a};k)$ denote the $i$th
element and $k$th smallest value of $\mathbf{a}$, respectively. Let $\otimes
n$ denote the $n$th Kronecker power. Let $|S|$ be the cardinality of set $S$.
All logarithms are with base 2. For integers $a$ and $b$ define
$[a,b]=\\{i\;|\;a\leq i\leq b\\}$, $(a,b]=\\{i\;|\;a<i\leq b\\}$, and
$[a]=\\{i\;|\;1\leq i\leq a\\}$, where elements in the three sets are
integers.

####  II-1 Coded Merke Tree preliminaries

A CMT, like a regular Merkle Tree [1], is a cryptographic commitment generator
that is used to check the integrity of transactions in the block [9].
Additionally, erasure coding allows to check for data availability via random
sampling. In this section, we provide a general framework for the CMT
construction that captures its key properties. Later in Section III, we
present the PCMT within the general CMT framework.

A CMT parametrized by $\mathcal{T}=(k,R,q,l)$ is a coded version of a Merkle
tree [1]. It has $(l+1)$ layers $L_{0},L_{1},\ldots,L_{l}$ where $L_{l}$ is
the base layer and $L_{0}$ is the CMT root. $L_{j}$ has
$N_{j}=\frac{N_{l}}{(qR)^{l-j}}$ coded symbols, where $N_{l}=\frac{k}{R}$. Let
$\text{{CodeSym}}[j]=\\{C_{j}[i]\;|\;i\in[N_{j}]\\}$ be the coded symbols of
$L_{j}$, where $\text{{data}}[j]=\\{C_{j}[i]\;|\;i\in[RN_{j}]\\}$ and
$\text{{parity}}[j]=\\{C_{j}[i]\;|\;i\in(RN_{j},N_{j}]\\}$ are the set of data
and parity symbols of $L_{j}$, respectively. The coded symbols in the CMT are
formed as follows: Set the data symbols of the base layer $\text{{data}}[l]$
to the chunks of the transaction block. For $j=l,l-1,\ldots,1$: _a)_ form the
parity symbols $\text{{parity}}[j]$ from the data symbols $\text{{data}}[j]$
using a rate $R$ systematic linear code via a procedure
$\text{{parity}}[j]=\text{{encodeParity}}(\text{{data}}[j])$; _b)_ form the
data symbols $\text{{data}}[j-1]$ from the coded symbols $\text{{CodeSym}}[j]$
by a procedure $\text{{data}}[j-1]=\text{{formParent}}(\text{{CodeSym}}[j])$.

The formParent$()$ procedure has the property that each data symbol
$C_{j-1}[i]$ in $\text{{data}}[j-1]$ contains the hashes of $q$ coded symbols
of $\text{{CodeSym}}[j]$. Finally, $\text{{data}}[0]$ forms the root Root of
the CMT and is the commitment to the block.

Each coded symbol $\tau$ in the CMT has a Merkle proof Proof($\tau$) which can
be used to check the integrity of the symbol given the Root using Verify-
Inclusion($\tau$, Proof($\tau$), Root). The CMT is decoded using a hash-aware
decoder which decodes the tree from the root to the base layer. Each layer is
decoded using a procedure $\text{{decodeLayer}}(L_{j})$ and the hash of the
decoded symbols are matched with their hash provided in the parent layer of
the CMT. Assume that the decoded CMT symbols
$\tau_{1},\tau_{2},\ldots,\tau_{d}$ satisfy a degree $d$ parity check equation
(of the erasure code used for encoding). Of these symbols, if there exists a
symbol $\tau_{e}$ whose hash does not match with the hash provided by the
parent of $\tau_{e}$ in the CMT, an IC attack is detected. In this case, an IC
proof consists of the following: the symbols
$\\{\tau_{1},\tau_{2},\ldots,\tau_{d}\\}\setminus\tau_{e}$ and their Merkle
proofs, and the Merkle proof of $\tau_{e}$. The IC proof is verified by first
verifying that each symbol $\tau_{i}$, $1\leq i\leq d,i\neq e$, satisfies
Verify-Inclusion($\tau_{i}$, Proof($\tau_{i}$), Root), then decoding
${\tau}_{e}$ from the remaining symbols (as they form a parity check equation)
and then checking that ${\tau}_{e}$ does not satisfy Verify-
Inclusion(${\tau}_{e}$, Proof(${\tau}_{e}$), Root).

We consider a blockchain system similar to [9, 12] with full nodes and light
nodes where full nodes produce new blocks. Light nodes only store the CMT root
of each block and use it to verify the Merkle proof of CMT symbols and IC
proofs. Similar to [8, 9, 11, 12], we assume that light nodes are honest, are
connected to at least one honest full node, but can be connected to a majority
of malicious full nodes. For the purposes of a DA attack, consider one layer
of the CMT having $N$ coded symbols. A malicious full node causes a DA attack
by _a)_ generating an invalid block and producing its CMT; _b)_ hiding coded
symbols (of the $N$ coded symbols) such that no honest full node is able to
decode back all the coded symbols. Light nodes detect this DA attack by
anonymously and randomly requesting (sampling) a small number of coded symbols
from the block producer and accepting the block if all the requested samples
are returned. A malicious node only returns coded symbols that it has not
hidden [8, 9, 11, 12]. Let $\alpha_{\min}$, which we call the _undecodable
threshold_ , be the minimum number of coded symbols that a malicious node must
hide to prevent honest full nodes from decoding all the coded symbols. Then,
the probability of failure for a light node to detect a DA attack using $s$
random i.i.d. samples is $P_{f}(s)=(1-\frac{\alpha_{\min}}{N})^{s}$. Note that
we focus on the security of the system on a per client basis similar to
[8],[9]. The following metrics are of importance for a CMT: i) IC proof size
(must be small in comparison to the original block size since this proof is
communicated to all light nodes and can be used to congest the network), ii)
undecodable threshold, iii) complexity of computing the undecodable threshold
(which is important at large CMT code length $N$), and iv) decoding
complexity. In this paper, we will demonstrate a construction of CMT using
polar codes called the PCMT that performs well on all these metrics when the
size of the block $b$ is large.

Figure 1: Left panel: FG $\mathcal{G}_{8}$ where circles represent VNs and
squares represent CNs. The black (red) VNs and CNs represent a stopping set
(stopping tree); Right panel: $\mathcal{G}_{5}$ obtained by removing the VNs
from the last 3 rows of $\mathcal{G}_{8}$. (removed VNs are shown in low
opacity).

####  II-2 Polar Codes preliminaries

An ($\widehat{N},\widehat{K}$) polar code of codelength $\widehat{N}=2^{n}$
for some integer $n$ and information length $\widehat{K}$ is defined by a
transformation matrix $\mathbf{F}_{2^{n}}=\mathbf{F}^{\otimes n}_{2}$. The
generator matrix of the polar code is a submatrix of $\mathbf{F}_{2^{n}}$
having $\widehat{K}$ of its rows corresponding to the data (information)
symbols, while the rest of the rows correspond to frozen symbols (zero chunks
in this paper). The factor graph (FG) representation [37] of
$\mathbf{F}_{2^{3}}$ is shown in Fig. 1 left panel. In general, the FG of
$\mathbf{F}_{2^{n}}$ (denoted by $\mathcal{G}_{2^{n}}$) has $n+1$ variable
node (VN) and $n$ check node (CN) columns. Let $v_{ki}$ ($c_{ki}$) denote the
VN (CN) in the $k$th column and $i$th row as shown in Fig. 1. Note that the
CNs have a degree of either 2 or 3.

Figure 2:  PCMT $\mathcal{T}$ $=(k=4,R=0.5,q=4,l=2)$. In the PCMT, the coded
symbols corresponding to all the columns of the polar FG are hashed into the
parent layer. The dropped symbols are shown in dotted. The symbols in $L_{2}$
are colored according to the column they belong to in FG $\mathcal{G}_{8}$.
The circled symbols in $L_{1}$ are the Merkle proof of the red symbols in
$L_{2}$. The data (parity) symbols in the Merkle proofs are shown in solid
(dashed) circles.

Systematic encoding of $(\widehat{N},\widehat{K})$ polar codes [35, 36]
(required for CMT construction), can be performed using the method described
in [36]. Given information and frozen index sets
$\widehat{\mathcal{A}}\subset[\widehat{N}]$ and
$\widehat{\mathcal{F}}=[\widehat{N}]\setminus\widehat{\mathcal{A}}$, such that
$|\widehat{\mathcal{A}}|=\widehat{K}$, the systematic encoder of [36]
determines the value of all the VNs in the FG $\mathcal{G}_{\widehat{N}}$ such
that i) $\\{v_{1i}\;|i\;\in\widehat{\mathcal{F}}\\}$ are set to zero (frozen)
symbols; ii) VNs in $\\{v_{(n+1)i}\;|\;i\in\widehat{\mathcal{A}}\\}$ and
$\\{v_{(n+1)i}\;|\;i\in\widehat{\mathcal{F}}\\}$ are the provided data symbols
and resultant parity symbols in the systematic encoding. Details regarding
systematic encoding can be found in Appendix D.

A polar code can be decoded using a peeling decoder on the code FG. Similar to
LDPC codes, the peeling decoder on the FG of a polar code fails if all VNs
corresponding to a stopping set (of the FG) are erased. A stopping set is a
set of VNs such that every CN connected to this set is connected to at least
two VNs in the set. Similar to [37], we call the VNs of a stopping set $\psi$
that are in the rightmost column of the FG as its _leaf set_ denoted by Leaf-
Set($\psi$). An important category of stopping sets in the FG of polar codes
is called _stopping trees_ [37]. A stopping tree is a stopping set that
contains only one VN from the leftmost column of the FG (called its root).
Fig. 1 left panel shows a general stopping set and a stopping tree in the FG
$\mathcal{G}_{8}$. As demonstrated in [37], each VN $v_{1i}$,
$i\in[\widehat{N}]$, is root of an unique stopping tree. Let $ST^{2^{n}}_{i}$
be the unique stopping tree with root VN $v_{1i}$ in the FG
$\mathcal{G}_{2^{n}}$ and let $f^{2^{n}}_{i}=|\text{{Leaf-
Set}}(ST^{2^{n}}_{i})|$. It is easy to see (and also proved in [37]) that
$f^{2^{n}}_{i}=\mathbf{T}_{2^{n}}(i)$, $\forall i\in[\widehat{N}]$, where
$\mathbf{T}_{2^{n}}=\mathbf{T}^{\otimes n}_{2}$.

##  III Polar Coded Merkle Tree (PCMT)

In this section, we describe the construction of a PCMT under the general CMT
framework of Section II. Assume all $N_{j}$’s are powers of 2. In Section IV,
we remove this assumption. Let $\mathcal{A}_{j}$ ($\mathcal{F}_{j}$) be the
information (frozen) index sets of the polar code used in layer $j$ of the
PCMT. We have $|\mathcal{A}_{j}|=RN_{j}$ and $|\mathcal{F}_{j}|=(1-R)N_{j}$.
For convenience, we re-index the row indices in FG $\mathcal{G}_{j}$ such that
$\mathcal{A}_{j}$ and $\mathcal{F}_{j}$ are the indices $[1,RN_{j}]$ and
$(RN_{j},N_{j}]$, respectively.

For the PCMT, define intermediate coded symbols (which are used to form the
PCMT) $\overline{C}_{j}[k][i]$, $j\in[l]$ where $k\in[\log N_{j}+1]$,
$i\in[N_{j}]$. Index $k$ ($i$) is the column (row) number of the VN that the
symbol $\overline{C}_{j}[k][i]$ corresponds to, in the FG
$\mathcal{G}_{N_{j}}$. In the general CMT framework, for $j\in[l]$, we have
$\text{{data}}[j]=\\{\overline{C}_{j}[\log N_{j}+1][i]\;|\;i\in[RN_{j}]\\}$,
$\text{{parity}}[j]=\\{\overline{C}_{j}[\log
N_{j}+1][i]\;|\;i\in(RN_{j},N_{j}]\\}$ and
$\text{{CodeSym}}[j]=\text{{data}}[j]\cup\text{{parity}}[j]$.

####  III-1 Formation of PCMT symbols

The $\text{{encodeParity}}()$ procedure for a PCMT is as follows: for the data
symbols $\text{{data}}[j]$, use a systematic polar encoder as described in
Section II to find the parity symbols $\text{{parity}}[j]$, where VNs
corresponding to
$\text{{frozen}}{[j]}=\\{\overline{C}_{j}[1][i]\;|\;i\in(RN_{j},N_{j}]\\}$ in
$\mathcal{G}_{N_{j}}$ are set as zero chunks. The systematic encoder also
provides the set of symbols
$\text{{dropped}}[j]=\\{\overline{C}_{j}[k][i]\;|\;k\in[\log
N_{j}],\;i\in[N_{j}]\\}$ which are dropped from the PCMT and are not included
in $\text{{CodeSym}}[j]$. However, before dropping, we use them to form the
parent layer in the PCMT. The $\text{{formParent}}()$ procedure for a PCMT is
as follows. Let $x\bmod{p}:=(x)_{p}$ and let Hash and concat represent the
hash and string concatenation functions, respectively. We have

$\displaystyle\overline{C}_{j-1}$ $\displaystyle[\log N_{j-1}+1][i]$ (1)
$\displaystyle={\text{concat}}(\\{{\text{Hash}}(\overline{C}_{j}[k][x])\;|\;k\in[\log
N_{j}+1],$ $\displaystyle\;x\in[N_{j}],\;i=1+(x-1)_{RN_{j-1}}\\}),\;\forall
i\in[RN_{j-1}],$

where $\text{{data}}[j-1]=\\{\overline{C}_{j-1}[\log
N_{j-1}+1][i]\;|\;i\in[RN_{j-1}]\\}$. For a PCMT, the root
($\text{{data}}[0]$) has a size $t=N_{1}(\log N_{1}+1)$ hashes. In Fig. 2, the
formation of $\overline{C}_{1}[3][2]$ is shown.

In the above $\text{{formParent}}()$ procedure, data symbols in
$\text{{data}}[j-1]$ are formed by taking the hashes of all the $N_{j}(\log
N_{j}+1)$ intermediate coded symbols of layer $j$ (i.e.,
$\text{{dropped}}[j]\cup\text{{CodeSym}}[j]$) and concatenating $q(\log
N_{j}+1)$ hashes together according to Eqn. (1). The intuition behind taking
the hashes of all the intermediate coded symbols is so that the symbols in
$\text{{dropped}}[j]$ also get committed to the root (i.e., these symbols also
have a Merkle proof). Although dropped, the symbols in $\text{{dropped}}[j]$
can be decoded back by a peeling decoder using the available (non-erased)
symbols of $\text{{CodeSym}}[j]$. Once decoded, they can be used to build
small IC proofs using the degree 2 and 3 CNs in the polar FG
$\mathcal{G}_{N_{j}}$.

####  III-2 Merkle proof of PCMT symbols

For the above PCMT construction, symbols in $\text{{CodeSym}}[j]$ and
$\text{{dropped}}[j]$ have Merkle proofs. The Merkle proof of the symbols
$\overline{C}_{j}[k][i]$, $k\in[\log N_{j}+1],\;i\in[N_{j}]$ consists of a
data symbol and parity symbol from each layer of the PCMT above $L_{j}$
similar to LCMT in [24, 12]. Precisely, it is given by the following:

$\displaystyle\text{{Proof}}(\overline{C}_{j}[k][i])=\\{\overline{C}_{j^{\prime}}[\log
N_{j^{\prime}}+1][1+(i-1)_{RN_{j^{\prime}}}],$ (2)
$\displaystyle\overline{C}_{j^{\prime}}[\log
N_{j^{\prime}}+1][1+RN_{j^{\prime}}+(i-1)_{(1-R)N_{j^{\prime}}}]\;|\;j^{\prime}\in[j-1]\\}.$

The Merkle proof for $\overline{C}_{2}[4][4]$ is shown in Fig. 2. The data
symbols from each layer in $\text{{Proof}}(\overline{C}_{j}[k][i])$ lie on the
path of $\overline{C}_{j}[k][i]$ to the PCMT root; this path is used to check
the integrity of $\overline{C}_{j}[k][i]$ in a manner similar to an LCMT [9,
24].

####  III-3 Hash-aware peeling decoder and IC proofs

The PCMT is decoded using a hash-aware peeling decoder similar to LCMT in [9].
The $\text{{decodeLayer}}(L_{j})$ procedure for the decoder is as follows. Its
acts on the FG $\mathcal{G}_{N_{j}}$. It takes as inputs the frozen symbols
$\text{{frozen}}[j]$ and the non hidden symbols of $\text{{CodeSym}}[j]$.
Using a peeling decoder, it finds all symbols in
$\text{{dropped}}[j]\cup\text{{CodeSym}}[j]$. The hash of every decoded
(peeled) symbol is matched with its hash provided by the parent layer
$L_{j-1}$. If hashes do not match, an IC attack is detected. In this case, IC
proof is generated using the degree 2 or 3 CN of the FG $\mathcal{G}_{N_{j}}$
as per the general CMT framework.

###  III-A DA attacks on PCMT

Consider layer $L_{j}$, $j\in[l]$, of the PCMT. For a given information index
set $\mathcal{A}_{j}$, let $\Psi^{\mathcal{A}_{j}}$ denote the set of all
stopping sets in the FG $\mathcal{G}_{N_{j}}$ that do not have any VNs
corresponding to $\text{{frozen}}[j]$. The hash-aware peeling decoder fails to
decode $L_{j}$ if coded symbols corresponding to a stopping set in
$\Psi^{\mathcal{A}_{j}}$ are erased. Since all the coded symbols except the
rightmost column of $\mathcal{G}_{N_{j}}$ are dropped, the peeling decoder
will fail if the adversary hides the leaf set of a stopping set in
$\Psi^{\mathcal{A}_{j}}$.

To prevent a DA attack, light nodes randomly sample symbols from the PCMT base
layer, i.e., $\text{{CodeSym}}[l]$. Randomly sampling the base layer ensures
that the non-dropped symbols of intermediate layer $L_{j}$, $j\in[l-1]$, i.e.,
$\text{{CodeSym}}[j]$, are also randomly sampled via the Merkle proofs of the
base layer samples similar to an LCMT in [9]. For subsequent analysis, we
assume (WLOG) that the adversary conducts a DA attack on the base layer of the
PCMT. To find the adversary strategy that leads to the largest probability of
failure when the light nodes use random sampling, we use the following
important property of stopping sets in polar FGs that was proved in [37]:

$\min_{\psi\in\Psi^{\mathcal{A}_{l}}}|\text{{Leaf-
Set}}(\psi)|=\min_{i\in\mathcal{A}_{l}}f^{N_{l}}_{i}.$ (3)

Eqn. (3) implies that, when light nodes use random sampling, the best strategy
for the adversary (to maximize the probability of failure) is to hide the
smallest leaf set amongst all stopping trees with non frozen root. Thus,
$\alpha_{\min}=\underset{i\in\mathcal{A}_{l}}{\min}f^{N_{l}}_{i}$.

##  IV Sampling-Efficient Freezing Algorithm

For the best adversary strategy,
$\alpha_{\min}=\min_{i\in\mathcal{A}_{l}}f^{N_{l}}_{i}$. Based on this result,
a naïve frozen set selection method would be to select the indices of $RN_{l}$
VNs from the leftmost column of the FG $\mathcal{G}_{l}$ with the smallest
stopping tree leaf set sizes $f^{N_{l}}_{i}$. Note that for this naïve frozen
set selection, the polar code becomes equivalent to a Reed-Muller (RM) Code
[38]. We call the naïve frozen set selection as _Naïve-RM (NRM)_ algorithm for
which it can be easily shown that
$\alpha_{\min}^{NRM}=\min\left(\mathbf{T}_{N_{l}};(1-R)N_{l}\right)$ (which is
the $(1-R)N_{l}$-th smallest value of $\mathbf{T}_{N_{l}}$).

Next, we describe the Sampling-Efficient Freezing (SEF) algorithm and show
that it results in a higher effective undecodable threshold compared to the
NRM algorithm. Additionally, our algorithm allows for polar codes of any
length and are not limited to powers of two. Assume that in this section, for
all FG $\mathcal{G}_{\widehat{N}}$, the rows in $\mathcal{G}_{\widehat{N}}$
are indexed $1$ to $\widehat{N}$ from top to bottom. The SEF algorithm is
based on the following lemma.

######  Lemma 1.

Consider FG $\mathcal{G}_{\widehat{N}}$ where $\widehat{N}$ is a power of two.
Let $\widehat{\mathcal{F}}$ and $\widehat{\mathcal{A}}$ be the frozen and
information index sets. For a parameter $\mu$, define the set of VNs
$\mathcal{V}^{\mu}_{\widehat{N}}[k]=\\{v_{ki}\;|\;i\in[\widehat{N}-\mu+1,\widehat{N}]\\}$.
If $[\widehat{N}-\mu+1,\widehat{N}]\subset\widehat{\mathcal{F}}$, then i)
$\forall$ $\psi\in\Psi^{\widehat{\mathcal{A}}}$, $\psi$ does not have any VNs
in $\mathcal{V}^{\mu}_{\widehat{N}}[\log\widehat{N}+1]$; ii) all VNs in
$\\{\mathcal{V}^{\mu}_{\widehat{N}}[k]\;|\;k\in[\log\widehat{N}+1]\\}$ are
zero chunks.

###### Proof Idea.

Assuming that a stopping set $\psi\in\Psi^{\widehat{\mathcal{A}}}$ has a VN
from $\mathcal{V}^{\mu}_{\widehat{N}}[\log\widehat{N}+1]$, we prove, by
incorporating the definition of stopping sets, that $\exists$ ${i}$,
$i\in[\widehat{N}-\mu+1,\widehat{N}]$ such that $v_{1i}\in\psi$. This is a
contradiction since $\psi\in\Psi^{\widehat{\mathcal{A}}}$ and hence does not
have VNs in $\mathcal{V}^{\mu}_{\widehat{N}}[1]$. Full proof can be found in
Appendix A. ∎

Block size $b$ (MB)IC proof size / block size

Block size $b$ (MB)$P_{f}(s)$

Block size $b$ (MB)$P_{f}(s)$

Figure 3: All figures use $b=cRN_{l}$. Left panel: Comparison of IC proof size
normalized by block size $b$ for different data symbol size $c=\frac{b}{k}$.
We use $(R,q,l)=(0.5,4,4)$ in the figure. For IC proof size of LCMT, we use
the maximum CN degree $d_{c}$. For PCMT, the maximum CN degree $d_{p}=3$;
Middle and Right panel: $P_{f}(s)$ vs. blocksize $b$ for LCMT and PCMT. The
two panels use $(R,q,l)=(0.4,5,4)$, $(0.5,4,4)$, and $(0.75,4,3)$ and a
constant data symbol size $c$. Sample size $s$ for PCMT and LCMT are selected
such that total sample download size is $\frac{b}{3}$ and $\frac{b}{5}$ for
the middle and right panels, respectively.

Lemma 1 states that, if the last $\mu$ rows (from the bottom) in the leftmost
column of $\mathcal{G}_{\widehat{N}}$ are all frozen, then no stopping set in
$\Psi^{\widehat{\mathcal{A}}}$ can have a VN from the last $\mu$ rows in the
rightmost column of $\mathcal{G}_{\widehat{N}}$. Thus, for a frozen index set
$\widehat{\mathcal{F}}$ such that
$[\widehat{N}-\mu+1,\widehat{N}]\subset\widehat{\mathcal{F}}$, the light nodes
do not need to sample the VNs in
$\mathcal{V}^{\mu}_{\widehat{N}}[\log\widehat{N}+1]$. We leverage the above
property to improve the effective undecodable threshold of polar codes.
Additionally, since all the VNs in
$\\{\mathcal{V}^{\mu}_{\widehat{N}}[k]\;|\;k\in[\log\widehat{N}+1]\\}$, which
are all the VNs in the last $\mu$ rows of $\mathcal{G}_{\widehat{N}}$, are
zero chunks, these VNs and their associated edges can be removed from the FG.
After this removal, we get the FG $\mathcal{G}_{\widehat{N}-\mu}$ of a polar
code of length $\widehat{N}-\mu$. We use this property to design polar codes
of lengths that are not powers of two. An example of FG $\mathcal{G}_{5}$ is
shown in Fig. 1 right panel. Algorithm 1 provides the SEF algorithm to design
the frozen index set $\mathcal{F}$ of an $(N,K)$ polar code; $N$ is not
necessarily a power of two.

Algorithm 1 SEF Algorithm

1:Inputs: $N$, $K$ Output: $\mathcal{G}_{N}$, $\mathcal{F}$, $\mathbf{T}_{N}$

2:Initialize: $\widehat{N}=2^{\lceil\log N\rceil}$, FG
$\mathcal{G}_{\widehat{N}}$, $\mu_{1}=\widehat{N}-N$, $i=N$.

3:$\mathcal{G}_{N}$ = FG obtained by removing all VNs in
$\\{\mathcal{V}^{\mu_{1}}_{\widehat{N}}[k]\;|\;k\in[\log\widehat{N}+1]\\}$ and
their connected edges from $\mathcal{G}_{\widehat{N}}$ (also remove any CNs
that have no connected edges)

4:$\mathbf{T}_{N}$ = $\mathbf{T}_{\widehat{N}}$ with last $\mu_{1}$ entries
removed

5:$\mathcal{F}=\\{e\;|\;e\in[N],\;\mathbf{T}_{N}(e)<\min(\mathbf{T}_{N};N-K)\\}$

6:while $|\mathcal{F}|<N-K$ do

7: if $i\not\in\mathcal{F}$ then $\mathcal{F}=\mathcal{F}\cup i$ end if;
$i=i-1$

In the SEF algorithm, we first remove the VNs from the last
$\mu_{1}=\widehat{N}-N$ rows in FG $\mathcal{G}_{\widehat{N}}$ (step 3). This
gives us the FG $\mathcal{G}_{N}$ which has $N$ coded symbols and is used for
the construction of the PCMT. Then, in steps 4-7, we select the frozen index
set $\mathcal{F}$ of size $N-K$ for the $(N,K)$ polar code. Note that
$\mathbf{T}_{N}$ (step 4) stores the stopping tree sizes of the VNs $v_{1i}$,
$i\in[N]$. For the selection of $\mathcal{F}$, we first select all the indices
$e$ in $[N]$ whose corresponding VNs $v_{1e}$ have their stopping tree sizes
less than $\min(\mathbf{T}_{N};N-K)$ (step 5). Then, the remaining indices in
$\mathcal{F}$ are selected as the VN indices from the bottom row of FG
$\mathcal{G}_{N}$ that are not already present in $\mathcal{F}$ (steps 6-7).
We have the following lemma.

######  Lemma 2.

Let $\mu_{2}$ be the largest $\mu$ such that $[N-\mu+1,N]\subset\mathcal{F}$
and let $\mathcal{A}=[N]\setminus\mathcal{F}$. For an $(N,K)$ polar code
produced by the SEF algorithm, let the light nodes randomly sample among the
top $N-\mu_{2}$ VNs from the rightmost column of FG $\mathcal{G}_{N}$. For
this sampling strategy, the effective undecodable threshold is
$\alpha_{\min}^{SEF}=\frac{\min_{i\in\mathcal{A}}\mathbf{T}_{N}(i)*N}{N-\mu_{2}}$.
As such, $P_{f}(s)=\left(1-\frac{\alpha_{\min}^{SEF}}{N}\right)^{s}$.

###### Proof Idea.

We prove the lemma by using Lemma 1 and Eqn. 3. The full proof can be found in
Appendix B. ∎

Note that due to step 5 of the SEF algorithm,
$\min_{i\in\mathcal{A}}\mathbf{T}_{N}(i)\geq\min(\mathbf{T}_{N};N-K)$. Thus,
the undecodable ratio of the SEF algorithm is always as big as the NRM
algorithm.  The FG $\mathcal{G}_{N}$ output by the SEF algorithm is used for
constructing different layers of the PCMT. $\mathcal{G}_{N}$ has $\lceil\log
N\rceil+1$ VN and $\lceil\log N\rceil$ CN columns each with $N$ VNs or CNs.
Thus, for the PCMT construction described in Section III, we replace all
instances of $\log N_{j}$ with $\lceil\log N_{j}\rceil$ (where $N_{j}$’s need
not be powers of two). Rest of the construction remains the same.

| 2D-RS | LCMT | PCMT
---|---|---|---
| $\mathcal{T}_{1}$ | $\mathcal{T}_{2}$ | $\mathcal{T}_{1}$ | $\mathcal{T}_{2}$ | $\mathcal{T}_{1}$ | $\mathcal{T}_{2}$
Root size (KB) | 2.05 | 5.82 | 0.26 | 0.51 | 1.02 | 2.56
IC proof size (MB) | 5.80 | 16.40 | 1.54 | 1.54 | 0.53 | 0.54
Total sample download size (MB) | 10.76 | 12.30 | 43.01 | - | 33.80 | 80.10
Decoding complexity | $O(N_{l}^{1.5})$ | $O(N_{l})$ | $O(N_{l}\lceil\log N_{l}\rceil)$

TABLE I: Comparison of various performance metrics for 2D-RS, LCMT and PCMT.
The table uses $\mathcal{T}_{1}=(k,R,q,l)=(512,0.5,4,8)$,
$\mathcal{T}_{2}=(4096,0.5,4,10)$, $c=256$KB, and $b=cRN_{l}$. Sample download
size is calculated such that $P_{f}(s)$ is $0.01$. Due to complexity of
finding $\alpha_{\min}$ for LCMT, we do have a corresponding total sample
download size value for $\mathcal{T}_{2}$.

##  V Simulations and Performance Comparison

In this section, we demonstrate the benefits of a PCMT with respect to the CMT
metrics i)-iv) described in Section II when the size of the block $b$ is
large. We also compare the performance of a PCMT with an LCMT and 2D-RS codes.
We denote the output size of the Hash function as $y$ and the size of the data
chunk (symbol) in the base layer as $c$ where block size $b=ck=cRN_{l}$. We
use $y=256$ bits. All PCMTs are built using SEF Polar codes. All LCMTs are
built using LDPC codes constructed using the PEG algorithm [31] where the
degree of all VNs is set to 3. For the PEG LDPC codes, the undecodable
threshold $\alpha_{\min}$ is evaluated by solving an Integer Linear Program
(ILP) as described in [39] and is computationally infeasible for larger code
lengths. In contrast, SEF Polar codes have an easily computable
$\alpha_{\min}$ using Lemma 2. Due to complexity issues, we compute
$\alpha_{\min}$ for LDPC codes up to a feasible code length (and, thus, up to
a feasible block size). From the description of the PCMT provided in Section
III, derivation of its root size, IC proof size, and single sample download
size (base layer sample and associated Merkle proof) is straight forward and
is provided in Appendix C (which we use to generate the plots in Fig. 3).

In Fig. 3 left panel, we plot the IC proof size vs. block size $b$ for an LCMT
and a PCMT and different data symbol sizes $c$. We see that for $c=256$ and
$16$KB (large block sizes), the IC proof size is smaller for a PCMT compared
to an LCMT and gets bigger than an LCMT for $c=1$KB (small block sizes).

######  Remark 1.

We note that for a PCMT and an LCMT with the same CMT $\mathcal{T}$
parameters, the PCMT incurs an asymptotic penalty of $O(\log b)$ in the IC-
proof size over the LCMT due to collecting the hashes of VNs in all the
columns of the FG (can be seen from the expressions in Appendix C). However
for practical block sizes of interest, the IC-proof size of a PCMT can be
significantly lower compared to an LCMT, as shown in Fig. 3, due to the low CN
degree in the FG of polar codes.

In Fig. 3 middle and right panels, we compare the probability of failure
$P_{f}(s)$ to detect a DA attack conducted on the base layer. We compare
$P_{f}(s)$ for large and short block sizes in the middle and right panels,
respectively. From Fig. 3, we see that PCMT has a worse probability of failure
compared to an LCMT for small block sizes. However for large block sizes, PCMT
always has a lower probability of failure compared to an LCMT across all rates
$R$ and block sizes $b$ thanks to a higher undecodable ratio for the SEF Polar
codes and a negligible penalty in the single sample download size.

In Table I, we provide additional comparison of various performance metrics
for 2D-RS, LCMT, and PCMT. We can see that PCMT outperforms LCMT w.r.t. IC-
proof size and total sample download size with small increase in root size and
decoding complexity. While PCMT has a $O(\lceil\log N_{l}\rceil)$ factor
greater decoding complexity than an LCMT, the decoding complexity is smaller
than for 2D-RS codes which is $O(N_{l}^{1.5})$ [9]. At the same time, PCMT
also has a lower IC proof size and root size compared to 2D-RS codes while
having a higher sample download size. Going from $\mathcal{T}_{1}$ to
$\mathcal{T}_{2}$, the IC-proof size for 2D-RS codes increases 3 fold while
the IC-proof size remains almost constant for LCMT and PCMT. Note that for
2D-RS codes, the IC proof size, decoding complexity, and header size do not
scale well as the block size increases [9].

Overall, when the size of the transaction block $b$ is large, a PCMT built
using SEF Polar codes has good performance w.r.t metrics i)-iv) described in
Section II and offers a new trade-off in these metrics compared to LCMT and
2D-RS codes.

## References

  * [1] S. Nakamato, “Bitcoin: A peer to peer electronic cash system," 2008. [Online] Available: https://bitcoin.org/bitcoin.pdf.
  * [2] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger," _Ethereum project yellow paper_ , Apr. 2014.
  * [3] K. Salah, M. H. U. Rehman, N. Nizamuddin and A. Al-Fuqaha, “Blockchain for AI: Review and open research challenges," _IEEE Access_ , vol. 7, pp. 10127-10149, 2019.
  * [4] K. Huang, X. Zhang, Y. Mu, F. Rezaeibagha, X. Du and N. Guizani, “Achieving intelligent trust-layer for internet-of-things via self-redactable blockchain," _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 4, pp. 2677-2686, Apr. 2020.
  * [5] M. J. Casey and P. Wong, “Global supply chains are about to get better, thanks to blockchain,” _Harvard Business Review_ , Mar. 2017. [Online] Available: https://hbr.org/2017/03/global-supply-chains-are-about-to-get-better-thanks-to-blockchain.
  * [6] N. Teslya and I. Ryabchikov, “Blockchain-based platform architecture for industrial IoT," _21-st Conference of Open Innovations Association (FRUCT)_ , pp. 321-329, Nov. 2017.
  * [7] M. Mettler, “Blockchain technology in healthcare: The revolution starts here,” _IEEE 18th International Conference on e-Health Networking, Applications, and Services (Healthcom)_ , pp. 1-3, Sept. 2016.
  * [8] M. Al-Bassam, A. Sonnino, V. Buterin, “Fraud and data availability proofs: Detecting invalid blocks in light clients," _International Conference on Financial Cryptography and Data Security_ Springer, Mar. 2021.
  * [9] M. Yu, S. Sahraei, S. Li, S. Avestimehr, S. Kannan, and P. Viswanath, “Coded merkle tree: Solving data availability attacks in blockchains," _International Conference on Financial Cryptography and Data Security, Springer, Cham_ , pp. 114-134, Feb. 2020.
  * [10] K. Nazirkhanova, J. Neu, and D. Tse, “Information dispersal with provable retrievability for rollups," _arXiv preprint arXiv:2111.12323_ Nov. 2021.
  * [11] D. Mitra, L. Tauz, and L. Dolecek, “Concentrated stopping set design for coded merkle tree: Improving security against data availability attacks in blockchain systems," _2020 IEEE Information Theory Workshop (ITW)_ , pp. 1-5, Apr. 2021.
  * [12] D. Mitra, L. Tauz, and L. Dolecek, “Overcoming data availability attacks in blockchain systems: LDPC code design for coded merkle tree," _arXiv preprint arXiv:2108.13332_ , Aug. 2021.
  * [13] S. Cao, S. Kadhe, and K. Ramchandran, “CoVer: Collaborative light-node-only verification and data availability for blockchains," _IEEE International Conference on Blockchain (Blockchain)_ , pp. 45-52, Nov. 2020.
  * [14] D. Perard, J. Lacan, Y. Bachy, and J. Detchart, “Erasure code-based low storage blockchain node," _IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)_ , pp. 1622-1627, Jul. 2018.
  * [15] M. Dai, S. Zhang, H. Wang, and S. Jin, “A low storage room requirement framework for distributed ledger in blockchain," _IEEE Access_ , vol. 6, pp. 22970-22975, Mar. 2018.
  * [16] Q. Huang, L. Quan, and S. Zhang, “Downsampling and transparent coding for blockchain" _arXiv preprint arXiv:1911.01778_ , Nov. 2019.
  * [17] D. Mitra and L. Dolecek, “Patterned erasure correcting codes for low storage-overhead blockchain systems,” _IEEE Asilomar Conference on Signals, Systems, and Computers_ , pp. 1734-1738, Nov. 2019.
  * [18] S. Kadhe, J. Chung, and K. Ramchandran, “SeF: A secure fountain architecture for slashing storage costs in blockchains," _arXiv preprint arXiv:1906.12140_ , Jun. 2019.
  * [19] A. Tiwari, and V. Lalitha, “Secure raptor encoder and decoder for low storage blockchain," _International Conference on COMmunication Systems & NETworkS (COMSNETS)_, pp. 161-165, Jan. 2021.
  * [20] D. S. Gadiraju, V. Lalitha, and V. Aggarwal, “Secure regenerating codes for reducing storage and bootstrap costs in sharded blockchains," _IEEE International Conference on Blockchain (Blockchain)_ , pp. 229-236, Nov. 2020.
  * [21] B. Choi, J. Sohn, D. Han, and J. Moon, “Scalable network-coded PBFT consensus algorithm," _IEEE International Symposium on Information Theory (ISIT)_ , pp. 857-861, Jul. 2019.
  * [22] S. Li, M. Yu, C. Yang, A. S. Avestimehr, S. Kannan, and P. Viswanath, “PolyShard: Coded sharding achieves linearly scaling efficiency and security simultaneously," _IEEE Transactions on Information Forensics and Security_ , vol. 16, Jul. 2020.
  * [23] C. Wang, and N. Raviv, “Low latency cross-shard transactions in coded blockchain," _arXiv preprint arXiv:2011.00087_ , Oct. 2020.
  * [24] P. Sheng, B. Xue, S. Kannan, and P. Viswanath, “ACeD: Scalable data availability oracle," _arXiv preprint arXiv:2011.00102_ , Oct. 2020.
  * [25] D. Mitra, L. Tauz, and L. Dolecek, “Communication-efficient LDPC code design for data availability oracle in side blockchains," _IEEE Information Theory Workshop (ITW)_ , pp. 1-6, May 2021.
  * [26] P. Santini,G. Rafaiani, M. Battaglioni, F. Chiaraluce, M. Baldi, _et al._ , “Optimization of a Reed-Solomon code-based protocol against blockchain data availability attacks", _arXiv preprint arXiv:2201.08261v1_ , Jan. 2022.
  * [27] T. Richardson, and R. Urbanke, “Modern coding theory," _Cambridge: Cambridge University Press_ , 2008.
  * [28] Online: https://www.blockchain.com/charts/avg-block-size, accessed 11th Jan. 2022.
  * [29] Online: https://bitinfocharts.com/comparison/bitcoin%20cash-size.html#3y, accessed 11th Jan. 2022.
  * [30] Online: https://bitinfocharts.com/comparison/bitcoin%20sv-size.html#3y, accessed 11th Jan. 2022.
  * [31] X.Y. Hu, E. Eleftheriou and D.M. Arnold, “Regular and irregular progressive edge-growth tanner graphs," _IEEE Transactions on Information Theory_ , vol. 51, no. 1, pp. 386-398, Jan. 2005.
  * [32] K. M. Krishnan, and P. Shankar, “Computing the stopping distance of a Tanner graph is NP-hard," _IEEE Transactions on Information Theory_ , vol. 53, no. 6, pp. 2278-2280, Jun. 2007.
  * [33] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3051-3073, Jul. 2009.
  * [34] N. Goela, S. B. Korada, and M. Gastpar, “On LP decoding of polar codes," _IEEE Information Theory Workshop_ , pp. 1-5, Aug. 2010.
  * [35] E. Arikan, “Systematic polar coding," _IEEE Communications Letters_ vol. 15, no. 8, pp. 860-862, Aug. 2011.
  * [36] L. Li and W. Zhang, “On the encoding complexity of systematic polar codes," _IEEE International System-on-Chip Conference (SOCC)_ , pp. 415-420, Sept. 2015.
  * [37] A. Eslami, H. Pishro-Nik, “On finite-length performance of polar codes: stopping sets, error floor, and concatenated design," _IEEE Transactions on Communications_ , vol. 61, no. 3, pp. 919-929, Feb. 2013.
  * [38] D. E. Muller, “Application of boolean algebra to switching circuit design and to error correction,” _Transactions of the I.R.E. Professional Group on Electronic Computers_ , vol. EC-3, no. 3, pp. 6–12, Sept. 1954.
  * [39] A. Sarıduman, A. E. Pusane, Z. C. Taşkın, “An integer programming-based search technique for error-prone structures of LDPC codes," _AEU-Int. Journal of Electronics and Communications_ , vol. 8, no. 11, pp. 1097-1105, Nov. 2014.

##  Appendix A Proof of Lemma 1

First of all, it is easy to see that when all the VNs in
$\mathcal{V}^{\mu}_{\widehat{N}}[1]$ (i.e., the VNs in the last $\mu$ rows
from the leftmost column of FG $\mathcal{G}_{\widehat{N}}$) are frozen or set
to zero chunks, all the VNs in the last $\mu$ rows from all the columns will
be zero chunks. This is because every CN in row $i$ of the FG is either
connected to VNs in the same row $i$ or to VNs from a row below $i$ (i.e.,
having a row index greater than $i$) in the FG. This proves the second claim
of the lemma.

For the first claim, let $\psi\in\Psi^{\widehat{\mathcal{A}}}$ and let
$\mathcal{G}^{\psi}_{\widehat{N}}$ be the induced subgraph of
$\mathcal{G}_{\widehat{N}}$ corresponding to the set of VNs $\psi$. From the
definition of $\Psi^{\widehat{\mathcal{A}}}$, $\psi$ does not have any frozen
VNs from the leftmost column of the FG $\mathcal{G}_{\widehat{N}}$, i.e.,
$\psi$ does not have any VNs in the set
$\\{v_{1i}\;|\;i\in\widehat{\mathcal{F}}\\}$. Since
$[\widehat{N}-\mu+1,\widehat{N}]\subset\widehat{\mathcal{F}}$, $\psi$ does not
have any VNs in $\mathcal{V}^{\mu}_{\widehat{N}}[1]$.

We prove the first claim of the lemma by contradiction. Assume that $\psi$ has
a VN from $\mathcal{V}^{\mu}_{\widehat{N}}[\log\widehat{N}+1]$. In particular,
assume that $v_{(n+1)i_{1}}\in\psi$, where $n=\log\widehat{N}$ and
$i_{1}\in[\widehat{N}-\mu+1,\widehat{N}]$. Now, by the property of stopping
sets, $c_{ni_{1}}\in\mathcal{G}^{\psi}_{\widehat{N}}$. Now, to satisfy the
stopping set property, either $v_{ni_{1}}\in\psi$ or $v_{ni_{2}}\in\psi$ where
$i_{1}<i_{2}\leq\widehat{N}$ and $v_{ni_{2}}$ and $c_{ni_{1}}$ are connected
in $\mathcal{G}_{\widehat{N}}$. Thus, for the column number $n$, we have at
least one index ${i}$, $i\in[\widehat{N}-\mu+1,\widehat{N}]$ such that
$v_{ni}\in\psi$. Proceeding in a similar manner as above, for the column
number $(n-1)$, we have at least one index ${i}$,
$i\in[\widehat{N}-\mu+1,\widehat{N}]$ such that $v_{(n-1)i}\in\psi$. Repeating
the same process until we reach the leftmost column, we can find at least one
index ${i}$, $i\in[\widehat{N}-\mu+1,\widehat{N}]$ such that $v_{1i}\in\psi$.
However, this is a contradiction of the fact that $\psi$ does not have any VNs
in set
$\mathcal{V}^{\mu}_{\widehat{N}}[1]=\\{v_{1i}\;|\;i\in[\widehat{N}-\mu+1,\widehat{N}]\\}$.

##  Appendix B Proof of Lemma 2

The SEF algorithm produces a $(N,K)$ polar code with a FG $\mathcal{G}_{N}$
where the bottom $\mu_{2}$ VNs from the leftmost column of $\mathcal{G}_{N}$
are frozen. Moreover, $\mathcal{G}_{N}$ is obtained from freezing (and hence
removing) the last $\widehat{N}-N$ rows of $\mathcal{G}_{\widehat{N}}$, where
$\widehat{N}=2^{\lceil\log N\rceil}$. Note that $\mathcal{F}$ is the output of
the SEF algorithm and $\mathcal{A}=[N]\setminus\mathcal{F}$. Define
$\widehat{\mathcal{F}}=\mathcal{F}\cup[N+1,\widehat{N}]$,
$\widehat{\mathcal{A}}=[\widehat{N}]\setminus\widehat{\mathcal{F}}$. Clearly,
$\widehat{\mathcal{A}}$ and $\mathcal{A}$ are the same sets. Thus, the $(N,K)$
polar code can be seen as a code defined on the FG $\mathcal{G}_{\widehat{N}}$
with frozen index set $\widehat{\mathcal{F}}$, and information index set
$\mathcal{A}$, where only the top $N$ VNs from the rightmost column of
$\mathcal{G}_{\widehat{N}}$ are the coded symbols.

Due to Lemma 1, VNs in the last $\mu_{2}+\widehat{N}-N$ rows in the rightmost
column of $\mathcal{G}_{\widehat{N}}$ are not part of any stopping set in
$\Psi^{\mathcal{A}}$. This implies that VNs in the last $\mu_{2}$ rows in the
rightmost column of $\mathcal{G}_{N}$ are not part of any stopping set in
$\Psi^{\mathcal{A}}$. Thus in the FG $\mathcal{G}_{N}$, the light nodes do not
need to sample the VNs in the last $\mu_{2}$ rows in the rightmost column of
$\mathcal{G}_{N}$ and only randomly sample the top $N-\mu_{2}$ VNs. Moreover,
from Eqn. (3) (applied on FG $\mathcal{G}_{\widehat{N}}$), the smallest leaf
set size of all stopping sets in $\Psi^{\mathcal{A}}$ is given by

$\displaystyle\min_{\psi\in\Psi^{\mathcal{A}}}|\text{{Leaf-
Set}}(\psi)|=\min_{i\in\mathcal{A}}f^{\widehat{N}}_{i}=\min_{i\in\mathcal{A}}\mathbf{T}_{\widehat{N}}(i)=\min_{i\in\mathcal{A}}\mathbf{T}_{N}(i).$

Hence, the probability of failure
$P_{f}(s)=(1-\frac{\min_{i\in\mathcal{A}}\mathbf{T}_{N}(i)}{N-\mu_{2}})^{s}$
resulting in an effective undecodable threshold of
$\alpha_{\min}^{SEF}=\frac{\min_{i\in\mathcal{A}}\mathbf{T}_{N}(i)*N}{N-\mu_{2}}$.

|  2D-RS |  LCMT |  PCMT
---|---|---|---
Root size |  $2y\lceil\sqrt{N_{l}}\rceil$ |  $yN_{1}$ |  $yN_{1}(\lceil\log N_{1}\rceil+1)$
Single sample download size |  $\frac{b}{k}+y\lceil\log\sqrt{N_{l}}\rceil$ |  $\frac{b}{k}+y(2q-1)(l-1)$ |  $\frac{b}{k}+y(2q-1)(l-1)+2qy\sum_{j=1}^{l-1}\lceil\log N_{j}\rceil$
IC proof size |  $(\frac{b}{k}+y\lceil\log\sqrt{N_{l}}\rceil)\lceil\sqrt{k}\rceil$ |  $\frac{(d_{c}-1)b}{k}+d_{c}y(q-1)(l-1)$ |  $\frac{(d_{p}-1)b}{k}+d_{p}y(q-1)(l-1)+d_{p}qy\sum_{j=1}^{l-1}\lceil\log N_{j}\rceil$
Decoding complexity |  $O(N_{l}^{1.5})$ |  $O(N_{l})$ |  $O(N_{l}\lceil\log N_{l}\rceil)$
$\alpha_{\min}$ |  Analytical expression in [8] |  NP-hard to compute |  Lemma 2

TABLE II: Comparison of various performance metrics of 2D-RS codes, an LCMT,
and a PCMT. The LCMT and PCMT have the same $(k,R,q,l)$ parameters. The
maximum degree of CNs in the LDPC codes and polar FG are $d_{c}$ and
$d_{p}=3$, respectively. The size of the block is $b$. 2D-RS has $k$ data
symbols and $\lceil\log\sqrt{N_{l}}\rceil$ layers in the Merkle tree where
$N_{l}=\frac{k}{R}$. For an LCMT, the number of layers $l$ can be calculated
such that the root size is some fixed constant $t$. The same $l$ is used for
the PCMT.

##  Appendix C Performance Analysis and Comparison

Comparison of various performance metrics of an LCMT, a PCMT and 2D-RS codes
is provided in Table I. The metrics for 2D-RS codes are calculated as
described in [8]. Detailed derivation of the root size, single sample download
size, and IC proof size for an LCMT and PCMT in Table I is as follows.

####  C-1 Root size

For an LCMT, the root consists of the hashes of all the coded symbols in
$L_{1}$. Hence, the root consists of $N_{1}$ hashes and, thus, has a size of
$yN_{1}$. For a PCMT, the root consists of hashes of all the coded and dropped
symbols in $L_{1}$, i.e., the hashes of all the VNs in FG of the polar code
used in $L_{1}$. Hence, the root consists of $N_{1}(\lceil\log N_{1}\rceil+1)$
hashes and, thus, has a size of $yN_{1}(\lceil\log N_{1}\rceil+1)$.

####  C-2 Single sample download size

For an LCMT, as described in [9, 24, 12], each sample request consists of a
base layer symbol of the CMT and the Merkle proof of the base layer symbol.
Moreover, the Merkle proof of the base layer symbol consists of a data symbol
and a parity symbol from each layer above the base layer (i.e., layers
$L_{j}$, $j\in[l-1]$ ). The Merkle proof satisfies the property that the data
symbol in proof from layer $L_{j}$ consists of the hash of the data symbol in
proof from layer $L_{j+1}$, $j\in[l-1]$. Thus, of the $q$ hashes present in
the data symbol of the Merkle proof from layer $L_{j}$, $j\in[l-1]$, the hash
corresponding to the data symbol of the Merkle proof from layer $L_{j+1}$ is
not communicated in the Merkle proof (and it can be calculated by taking a
hash of the data symbol of the Merkle proof from layer $L_{j+1}$). Thus, there
are only $(q-1)$ hashes from each layer $L_{j}$, $j\in[l-1]$ for the data part
in the Merkle proofs. Thus, the size of the Merkle proof of a base layer
symbol is $y(2q-1)(l-1)$ (since the size of each parity symbol is $yq$).
Finally, the overall download size for a single sample request is
$\frac{b}{k}+y(2q-1)(l-1)$, where $\frac{b}{k}$ is the size of the base layer
symbol.

For a PCMT, similar to an LCMT above, a sample request consists of a base
layer symbol of the PCMT and the Merkle proof of the base layer symbol. The
Merkle proof of the base layer symbol in this case again consists of a data
symbol and a parity symbol from each layer above the base layer. Note that,
here, the data and the parity symbols in layer $L_{j}$ are the non-dropped
symbols of the polar FG $\mathcal{G}_{N_{j}}$ corresponding to the information
$\mathcal{A}_{j}$ and frozen set $\mathcal{F}_{j}$ indices, respectively. In
contrast to an LCMT, in a PCMT, each data symbol of layer $L_{j}$, $j\in[l-1]$
consists of $q_{j}=q(\lceil\log N_{j}\rceil+1)$ hashes.

The Merkle proof in a PCMT also satisfies the property that the data symbol in
proof from layer $L_{j}$ consists of the hash of the data symbol in proof from
layer $L_{j+1}$, $j\in[l-1]$. Thus, only $(q_{j}-1)$ hashes from layers
$L_{j}$, $j\in[l-1]$ are present in the data part of the Merkle proofs. Thus,
for a PCMT, the size of the Merkle proof of a base layer symbol is

$\displaystyle\sum_{j=1}^{l-1}y(2q_{j}-1)$
$\displaystyle=\sum_{j=1}^{l-1}y(2(q(\lceil\log N_{j}\rceil+1))-1)$
$\displaystyle=y(2q-1)(l-1)+2qy\sum_{j=1}^{l-1}\lceil\log N_{j}\rceil$

Finally, the overall download size for a single sample request is
$\frac{b}{k}+y(2q-1)(l-1)+2qy\sum_{j=1}^{l-1}\lceil\log N_{j}\rceil$, where
$\frac{b}{k}$ is the size of the base layer symbol in a PCMT. Note the
additional penalty factor of $2qy\sum_{j=1}^{l-1}\lceil\log N_{j}\rceil$ in
the single sample download size for a PCMT compared to an LCMT. However, for
large block sizes when $\frac{b}{k}$ is large compared to $y$, the penalty is
small.

####  C-3 IC proof size

As described in Section II, the IC proof for a failed parity check equation
with $d$ symbols consists of $d-1$ symbols and the Merkle proofs of the $d$
symbols. Note that the proof size is largest for a failed parity check
equation in the base layer. Thus, we provide the IC proof size when the $d$
symbols are base layer symbols. Also note that, in IC proofs, the Merkle proof
of a symbol only consists on the data symbols from each layer above the base
layer (the parity symbols included in the Merkle proofs of the light node
samples are only to get additional samples of the intermediate layers) [9,
24]. Thus, in an LCMT, for a failed parity check equation with $d$ symbols,
the size of the IC proof is $\frac{(d-1)b}{k}+dy(q-1)(l-1)$, where the $(q-1)$
term arises due to the same reason as explained in the single sample download
size calculation. Hence, when the maximum CN degree of the LDPC code is
$d_{c}$, the IC proof size becomes $\frac{(d_{c}-1)b}{k}+d_{c}y(q-1)(l-1)$.

For a PCMT, the IC proof for a failed parity check equation with $d$ symbols
again consists of $d-1$ symbols and the Merkle proofs of the $d$ symbols. Note
that the symbols here can be both the dropped or non-dropped symbols of the
polar FG. Also, each data symbol of layer $L_{j}$, $j\in[l-1]$ in a PCMT
consists of $q_{j}=q(\lceil\log N_{j}\rceil+1)$ hashes. Thus, for a failed
parity check equation with $d$ symbols, the size of the IC proof in a PCMT is

$\displaystyle\frac{(d-1)b}{k}$ $\displaystyle+\sum_{j=1}^{l-1}dy(q_{j}-1)$
$\displaystyle=\frac{(d-1)b}{k}+\sum_{j=1}^{l-1}dy((q(\lceil\log
N_{j}\rceil+1))-1)$
$\displaystyle=\frac{(d-1)b}{k}+dy(q-1)(l-1)+dyq\sum_{j=1}^{l-1}\lceil\log
N_{j}\rceil.$

For a PCMT, the maximum CN degree for a CN in the FG of the polar code is
$d_{p}=3$. In this case, the IC proof size becomes
$\frac{(d_{p}-1)b}{k}+d_{p}y(q-1)(l-1)+d_{p}yq\sum_{j=1}^{l-1}\lceil\log
N_{j}\rceil$.

###  C-A Undecodable Threshold

The undecodable threshold $\alpha_{\min}$ for an LCMT with the LDPC codes
described in Section V and a PCMT with SEF Polar codes is shown in Fig. 4.
From the figure, we see that a PCMT has a higher $\alpha_{\min}$ compared to
an LCMT for different values of rates $R$ and code lengths $N$. Hence for
large block size $b$, when the penalty in the single sample download size for
a PCMT is small, they have a lower probability of failure compared to an LCMT
for the same total sample download size. This result is shown in Fig. 3 right
panel.

$N$$\alpha_{\min}$

Figure 4: Left Panel: Undecodable threshold $\alpha_{\min}$ vs $N$ for PEG
LDPC codes (with VN degree 3) and SEF Polar codes. For PEG LDPC codes, we only
list $\alpha_{\min}$ that we were able to find by solving the ILP in [39].

##  Appendix D Systematic encoding of Polar codes

Systematic encoding of an $(\widehat{N},\widehat{K})$ polar codes can be
performed using the method described in [36]. It operates on the FG
$\mathcal{G}_{\widehat{N}}$ of the code. Let
$\widehat{\mathcal{A}}\subset[\widehat{N}]$ and
$\widehat{\mathcal{F}}=[\widehat{N}]\setminus\widehat{\mathcal{A}}$ be the
index sets corresponding to the data and frozen symbols of the
$(\widehat{N},\widehat{K})$ polar code, respectively, where
$|\widehat{\mathcal{A}}|=\widehat{K}$. Also, let $\widehat{N}=2^{n}$. The
systematic encoding is performed on the FG $\mathcal{G}_{\widehat{N}}$ by i)
placing the $\widehat{K}$ data symbols at the VNs
$\\{v_{(n+1)i}|i\in\widehat{\mathcal{A}}\\}$ (in the rightmost column) and
setting the VNs at $\\{v_{1i}|i\in\widehat{\mathcal{F}}\\}$ (in leftmost
column) to zero symbols; ii) determining the rest of the VNs using the check
constraints of the FG $\mathcal{G}_{\widehat{N}}$ in a two stage reverse and
forward encoding on the FG [36]. The coded symbols are the VNs
$v_{(n+1)i},i\in[\widehat{N}],$ and are by design systematic. Systematic
encoding can also be performed using a peeling decoder as the encoder as
described next.

In [35], author proposed to perform systematic encoding of polar codes by
using a successive cancellation decoder on the code FG as the encoder.
Inspired by this idea, we show that systematic encoding of the polar codes can
also be performed using a peeling decoder as the encoder. The encoder, which
we call a peeling encoder for polar codes (PEPC), works as follows. Consider
the data and frozen index sets $\widehat{\mathcal{A}}\subset[\widehat{N}]$ and
$\widehat{\mathcal{F}}=[\widehat{N}]\setminus\widehat{\mathcal{A}}$ of the
polar code with FG $\mathcal{G}_{\widehat{N}}$. Place the data symbols at the
VNs $\\{v_{(n+1)i}|i\in\widehat{\mathcal{A}}\\}$ (in the rightmost column) and
set the VNs at $\\{v_{1i}|i\in\widehat{\mathcal{F}}\\}$ (in leftmost column)
to zero symbols. Use a peeling decoder to find the remaining VNs of the FG.
The coded symbols $c_{i}=v_{(n+1)i},i\in[\widehat{N}],$ are by design
systematic. We have the following lemma corresponding to a PEPC.

######  Lemma 3.

Systematic encoding of polar codes using a PEPC always results in a valid
codeword. In other words, the peeling decoder never encounters a decoding
failure when used for encoding.

We prove Lemma 3 by proving the following important property of stopping sets
in the FG of polar codes produced by the SEF algorithm. Note that the property
holds true for regular polar FG $\mathcal{G}_{\widehat{N}}$ where
$\widehat{N}$ is a power of 2. Additionally, the property also holds true for
the FG $\mathcal{G}_{N}$ obtained by removing VNs from the last few rows of FG
of the form $\mathcal{G}_{\widehat{N}}$, where $\widehat{N}$ is a power of 2.
Thus, let $n=\lceil\log N\rceil$. The proof provides insights on important
properties of stopping sets in the FG of polar codes. To our best knowledge,
we have not seen the following result before in literature and, hence, it may
be of independent interest.

######  Lemma 4.

Consider a polar FG $\mathcal{G}_{N}$ produced by the SEF algorithm (this
encompasses polar factor graphs $\mathcal{G}_{\widehat{N}}$, where
$\widehat{N}$ is a power of 2). Every stopping set of $\mathcal{G}_{N}$ has a
full row of VNs i.e., it has all VNs in the set
$\\{v_{ki}\;|\;k\in[\;\lceil\log N\rceil+1\;]\\}$ for some $i\in[N]$.

###### Proof.

Let $\psi$ be a stopping set of $\mathcal{G}_{N}$. Let
$\mathcal{G}^{\psi}_{N}$ be the induced subgraph of $\mathcal{G}_{N}$
corresponding to the set of VNs $\psi$. Observe that the FG $\mathcal{G}_{N}$
has two types of edges (see Fig. 1 for an example): horizontal edges and
slanted edges (which involves a connection between a degree 3 VN and a degree
3 CN). We consider two cases: i) $\mathcal{G}^{\psi}_{N}$ does not have any
slanted edges; ii) $\mathcal{G}^{\psi}_{N}$ has at least one slanted edge.

For case i), it is easy to see that the stopping set $\psi$ must include a
full row of VNs. For case ii), note that it implies $\mathcal{G}^{\psi}_{N}$
has at least one slanted edge. This implies that $\psi$ has at least one VN of
degree 3. In this situation, define the set
$\Delta_{\psi}=\\{(i,k)\;|\;i\in[N],\;k\in[n],v_{ki}\in\psi,\text{degree of
}v_{ki}=3\\}$. Let $i_{\max}=\max(\\{i|(i,k)\in\Delta_{\psi}\text{ for some
}k,k\in[n]\\})$. $\Delta_{\psi}$ contains the indices of all the degree 3 VNs
of $\psi$ and $i_{\max}$ denotes the largest row index such that $\psi$ has a
degree 3 VN from that row. Note that $\Delta_{\psi}$ is non empty because we
are considering case ii). Now, we claim that $\psi$ has all the VNs in the row
$i_{\max}$, i.e., $\psi$ contains all the VNs in
$\\{v_{ki_{\max}}\;|\;k\in[n+1]\\}$. To see why this is true, let
$\accentset{\rule{2.10002pt}{0.6pt}}{k}$,
$\accentset{\rule{2.10002pt}{0.6pt}}{k}\in[n]$, be such that
$(i_{\max},\accentset{\rule{2.10002pt}{0.6pt}}{k})\in\Delta_{\psi}$. This
means that $v_{\accentset{\rule{2.10002pt}{0.6pt}}{k}i_{\max}}\in\psi$. Now by
the definition of a stopping set, the CNs to the right and left of
$v_{\accentset{\rule{2.10002pt}{0.6pt}}{k}i_{\max}}$ must belong to the
induced subgraph graph of the stopping set. In other words,
$c_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}-1)i_{\max}}\in\mathcal{G}^{\psi}_{N}$
and
$c_{\accentset{\rule{2.10002pt}{0.6pt}}{k}i_{\max}}\in\mathcal{G}^{\psi}_{N}$
(unless $v_{\accentset{\rule{2.10002pt}{0.6pt}}{k}i_{\max}}$ is the rightmost
or the left most VN in which case we will have only one CN neighbour). Now, to
satisfy the stopping set property, for both these CNs, their corresponding VNs
to their left and right in the same row $i_{\max}$ must belong to the stopping
set $\psi$ (i.e.,
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}-1)i_{\max}}\in\psi$,
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}+1)i_{\max}}\in\psi$). If not, then
to satisfy the stopping set property, the CN must be connected to a VN
$v_{ki}\in\psi$ by a slanted edge. Note that a slanted edge connects a CN to a
degree 3 VN in lower row. In other words, a slanted edge connects a CN from
row $i_{\max}$ to a degree 3 VN in a row with index greater than $i_{\max}$.
This condition violates the definition of $i_{\max}$. Thus,
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}-1)i_{\max}}\in\psi$ and
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}+1)i_{\max}}\in\psi$. Now,
considering $v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}-1)i_{\max}}$ and
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}+1)i_{\max}}$ as the starting VN
(similar to $v_{\accentset{\rule{2.10002pt}{0.6pt}}{k}i_{\max}}$), we can
apply the above logic to show that
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}-2)i_{\max}}\in\psi$ and
$v_{(\accentset{\rule{2.10002pt}{0.6pt}}{k}+2)i_{\max}}\in\psi$. Repeatedly
applying the same argument, we can show that all the VNs in
$\\{v_{ki_{\max}}\;|\;k\in[n+1]\\}$ belong to $\psi$, where $n=\lceil\log
N\rceil$.

∎

According to the above lemma, every stopping set has at least one full row of
VNs, i.e., it has VNs from all columns along a single row. We use this
property to prove Lemma 3.

_Proof of Lemma 3_:
Let $\mathcal{V}$ be the set of all VNs in the polar FG $\mathcal{G}_{N}$.
Also, let
$\mathcal{\overline{V}}_{e}=\\{v_{(n+1)i}\;|\;i\in\mathcal{A}\\}\cup\\{v_{1i}\;|\;i\in\mathcal{F}\\}$
and $\mathcal{V}_{e}=\mathcal{V}\setminus\mathcal{\overline{V}}_{e}$. VNs in
$\mathcal{V}_{e}$ are uninitialized or initially erased by the PEPC and are
determined using a peeling decoder (for the purposes of encoding). Thus, the
PEPC can fail if $\mathcal{V}_{e}$ contains a stopping set of
$\mathcal{G}_{N}$. However, since $\mathcal{A}\cup\mathcal{F}=[N]$ (i.e., they
form a partition of all the row indices), for all $i\in[N]$ either
$v_{(n+1)i}\in\mathcal{\overline{V}}_{e}$ or
$v_{1i}\in\mathcal{\overline{V}}_{e}$. Thus, for all $i\in[N]$, $v_{(n+1)i}$
and $v_{1i}$ both cannot simultaneously belong to $\mathcal{V}_{e}$. Hence,
$\mathcal{V}_{e}$ cannot contain a full row of VNs. Using Lemma 4, we conclude
that $\mathcal{V}_{e}$ cannot contain a stopping set. Thus, the PEPC will
always be successful and will result in a valid codeword.