Decentralized Data Archival: New Definitions and Constructions

To the best of our knowledge, we are the first to initiate a formal treatment of the $\mathrm{𝗂𝖣𝖣𝖠}$ problem. We provide formal definitions that mathematically capture the aforementioned intuitive requirements of approximate best-possible recoverability and replication security. Importantly, as mentioned, our definitions implicitly require that security hold even when the adversary controls all participating pseudonyms. In particular, we stress that “honest majority” style assumptions are not a great fit in a decentralized/permissionless setting when an adversary can generate arbitrarily many pseudonyms.

We construct an efficient $\mathrm{𝗂𝖣𝖣𝖠}$ scheme in the random oracle model that supports append-only updates. Our scheme achieves low barrier to entry: the minimal space provisioning required to contribute is only polylogarithmic. Furthermore, the amortized update cost is logarithmic (or slightly more than logarithmic) for each node as well as the publisher. Importantly, we prove the security of our construction even when all the pseudonyms in the system are controlled by the same adversary.

Below, let $\lambda$ be the security parameter, let $B$ be the number of bits per block, let $S$ be the space provisioning per storage node, let $N$ be the maximum database size, and let $n_0$ be the initial database size. Note that $S$, $N$, and $n_0$ are measured in the number of blocks.

We stress that under our security requirements, it is inevitable that each node must incur at least constant cost per update. Since otherwise, if 1% of the nodes are not aware of the new update, the adversary can erase the other 99% of nodes and cause this new block to be lost, even if the remaining 1% nodes actually have enough space to store the entire dataset. In this sense, our per-update costs are (nearly) optimal.

Our scheme can also be easily extended to a setting where nodes have heterogeneous space provisioning, provided that the minimum space per node $S$ is at least polylogarithmic. In this non-uniform space setting, a node with $k\cdot S$ need not incur $k$ times the update and audit costs – it still enjoys the same update and audit costs as stated above. See Section 7.1 of the full version for more details.

We first show how to combine techniques from PoR and PoRep in a non-blackbox fashion to get a decentralized data archival scheme for a static database (see Section 3.1 here and Section 5 of the full version). The most naïve way to get a dynamic scheme is to rerun the static scheme upon every update, but the cost per update would be linear in the data size. The key question is how to make the scheme dynamic without this prohibitive cost.

At first sight, it might be tempting to think that directly applying the standard hierarchical data structure of Bentley and Saxe [9] can turn any static scheme into a dynamic one. Recall that the hierarchical data structure divides the dataset into logarithmically many levels, of size $1,2,4,\mathrm{\dots },n$, respectively, where the smaller levels contain the fresher data blocks. It then runs a separate instance of the static scheme per level. Each level $\mathrm{\ell }$ of size $2^{\mathrm{\ell }}$ needs updating only every $2^{\mathrm{\ell }}$ steps, and thus the amortized update cost is logarithmic.

Unfortunately, we observe this approach does not generically work for any cryptographic scheme. In our case, there are two reasons why a straightforward application of the hierarchical data structure fails:

1. 1.

   Our security definition lacks compositional guarantees. Our notion of $ϵ$-best-recoverability includes an implicit accounting requirement: data recovery is only possible if the total storage provisioned by all nodes that pass the audit slightly exceeds the size of the dataset. However, when we have multiple instances of the static scheme – each corresponding to one of the logarithmically many levels – this condition is not necessarily met in a synchronized fashion across all levels. As a result, even if each instance individually satisfies $ϵ$-best-recoverability, their combined system may fail to satisfy the same notion globally.

2. 2.

   The underlying cryptography lacks compositional guarantees. We make use of a PoRep scheme to compute a replication encoding for each level in the hierarchical data structure. To formally prove security, we need the underlying PoRep scheme to satisfy a certain form of adaptive sequential composability, that is, we want the PoRep’s security to hold even the adversary may choose some instance’s data in a way that depends on another instance’s replication encoding. Unfortunately, known PoRep constructions [23, 22, 34] do not provide the desired compositional guarantees.

To solve the first challenge, we devise a new space allocation scheme to allocate a node’s space among the multiple levels – see Section 3.2 for details. For the second challenge, we are not aware of any approach to extend the proofs in earlier works [23, 22, 34] to satisfy the desired adaptive sequential composition. Specifically, existing techniques for proving space-time tradeoffs through direct incompressibility arguments are highly involved and apply to extremely limited settings [19, 20]. While some other proof techniques [39, 18, 1, 25, 2] have been shown to prove space-time tradeoffs, they do not produce meaningful results in our setting. Instead, we devise a method to side-step the lack of composition of the underlying PoRep. Specifically, we modify our construction and force a storage node to locally recompute the replication encodings of all levels upon every update, using the new digest of the entire database to seed the underlying random oracle used in the PoRep scheme. We show that with this modification, we can prove security even when the underlying PoRep scheme does not provide the desired compositional guarantees.

Unfortunately, this modification also incurs significant extra costs. Specifically, each storage node would now have to pay at least $B\cdot S$ cost per update to recompute the replication codes of all levels, where $B$ is the block size and $S$ is the blocks of space allocated by a node. In Section 3.4, we devise some additional algorithmic tricks to avoid this extra cost blowup, and bring the amortized update cost back down, to $\tilde{O}(1)\cdot B$.

In our definitions, we adopt the same philosophy suggested in a line of prior works [38, 7]. Specifically, we do not aim to support efficient read (by index) in the $\mathrm{𝗂𝖣𝖣𝖠}$ abstraction itself. This is a deliberate choice, as efficient (authenticated) read can easily be handled with a separate (possibly distributed) retrieval service provider who may simply store a cleartext copy of the dataset along with the Merkle openings [7, 38], allowing users request any specific block. A separate reward system can be used to incentivize the retrieval provider. Moreover, the retrieval service can be designed to optimize efficiency without worrying about redundancy and robustness. Philosophically, by decoupling the problem of providing retrieval from that of data archival, this definitional approach expands the design space and allows for more efficient constructions. For example, our construction can leverage the more efficient erasure codes rather than locally decodable codes.

Our work raises several natural open questions. First, although we manage to side-step the underlying PoRep’s lack of composition, our work nonetheless leaves open the following interesting question: How can we design a PoRep scheme with the desired adaptive sequential composition property? Likely the reason why the prior works [23, 22, 34] never considered this natural compositional notion is exactly because they (implicitly) considered a setting with a static database, where every node has ample space to store the entire database. A related open question is whether we can design an $\mathrm{𝗂𝖣𝖣𝖠}$ scheme that is itself composable. Another theoretically interesting question is whether the random oracle needed for the shard selection can be avoided. On the practical front, it would be interesting to devise a practical variant of our construction. Specifically, for the blockchain context, instantiating the publisher without trust using efficient Incrementally Verifiable Computation (IVC) would be highly relevant – see Section 7.2 of the full version for details. Our paper focuses on append-only updates, so a natural direction is to extend the scheme to support other types of updates.

In the following subsection, we will describe related work in more detail. In Section 2, we will define the iDDA problem and corresponding security definitions more formally. In the last section of this article, we will present an informal technical roadmap describing our constructions.

While the prior works on Data Availability Sampling (DAS) [27, 28, 14, 3, 26] and and Verifiable Information Dispersal (VID) [24, 33, 7, 41, 12, 29] may bear superficial resemblance to our problem at first sight, these works are of fundamentally different nature, partly because they (implicitly) assume that a separate instance of the scheme will be applied on a per-block basis.

We argue that the “separate instance per block” approach cannot satisfy our requirements. Under this approach, either almost all nodes must store some (encoded) fragments of every block, or only a subset of the nodes are responsible for a block. The former case necessitates per-node storage that is linear in the dataset size, thus violating the “low barrier to entry” requirement; whereas the latter case is prone to a selective censorship attack if all nodes responsible for a block become corrupted. Another way to see this is that even if $\mu$ nodes can pass the audit and their purported total space exceeds the data size, we still may not be able to recover the dataset, since the identities of these nodes can be adversarially chosen such that none of them is responsible for storing a particular block.

Next, we review the prior works on PoR, DAS, PoRep, and VID one by one, and give more reasons why all of them are of fundamentally different nature from our $\mathrm{𝗂𝖣𝖣𝖠}$ abstraction, despite bearing some superficial resemblance at first sight.

In proofs of retrievability (PoR) [30, 32, 35, 21, 11, 4, 38, 13, 36], an untrusted node can prove that it is indeed correctly storing the data it is asked to store, and that no data loss has occurred. The security definition requires that if a node can successfully pass the audit, then we can extract the entire dataset by rewinding the node and feeding it with many different challenges. A couple works have explored how to extend PoR schemes to support a dynamically evolving database [38, 13].

Data availability sampling [27, 28, 14, 10, 17] can be viewed as a strengthening of PoR. Specifically, in PoR, we assume that the committer of the data is trusted, whereas in DAS, the committer can be adversarial. In comparison with PoR, DAS additionally requires that even when the commitment to the data is adversarially chosen, if a node can pass the audit, we must be able to extract some dataset consistent with the commitment by rewinding the node and feeding it with many different challenges.

Due to historical reasons, PoR was studied typically with the cloud setting in mind, where a client outsources a dataset to a powerful but untrusted cloud server capable of storing the entire dataset. By contrast, the DAS abstraction was proposed in a blockchain context, where blocks are proposed by untrusted block producers in the underlying the consensus protocol. Lightweight consensus clients want to ensure that the data block is available, without necessarily downloading the entire block. It is implicitly assumed that a separate DAS instance will be applied to each block being produced. Because block producers are untrusted, it is crucial that security hold even when the committer is malicious.

Clearly, neither PoR nor DAS solve our $\mathrm{𝗂𝖣𝖣𝖠}$ problem for two main reasons. First, the approach of spawning a separate instance of the scheme per block inherently requires each storage node to maintain space that is linear in the size of the database. This directly violates our “low barrier to entry” requirement. Second, neither PoR nor DAS provide replications security. Specifically, a node with ample space can store just one copy of the data, and yet pretend to be arbitrarily many pseudonyms and earn unbounded rewards.

In verifiable information dispersal (VID) [24, 33, 7], a potentially malicious party encodes some data string and distributes the encoded fragments among a set of nodes. At the end, the nodes can interact to determine whether the original block is available. VID’s security relies on a threshold number of honest nodes, making it unsuitable for a permissionless setting in which the adversary can control arbitrarily many pseudonyms. Like DAS, the VID abstraction was also proposed in a blockchain consensus context, where the committer is a possibly malicious block producer. Consequently, it is typically assumed that a separate VID instance is applied to disperse each block, thus leading to a linear space requirement per node.

Proofs of replication (PoRep) [23, 22, 34] guarantee that if a node can pass the audit purporting to have allocated $\alpha \cdot n$ amount of space where $n$ is the data size, then the following are guaranteed: 1) the node must indeed be consuming $(\alpha -ϵ)\cdot n$ amount of space; and 2) the space is indeed used to store useful data. Existing works on PoRep [23, 22, 34] typically consider a static database and assume that the storage node can store the entire database. PoRep (over unencoded data) also does not guarantee extraction of the entire data when the storage provider can pass the audit.

In our paper, we commit to some data string by computing an erasure code and a vector commitment over the erasure code. We use a constant redundancy for the erasure code (dependent on $ϵ$). This way, the publisher can simply cache all the opening proofs cheaply. This way, when an update occurs or upon first joining, the storage node only needs to download some data from the publisher, and the publisher need not perform any online computation.

Alternatively, we can use a polynomial commitment scheme with arbitrarily large redundancy (e.g., as large as the underlying field size) [31, 40, 8]. Unfortunately, this approach has the drawback that the publisher must compute the opening proofs on the fly, and in a non-batched setting, the computation cost is at least linear in the database size using known approaches [31, 40, 8]. In comparison, our approach has only $B\cdot \tilde{O}(1)$ amortized publisher cost per update.

We now define the correctness property of an $\mathrm{𝗂𝖣𝖣𝖠}$ scheme. At a high level, correctness means that even if there are corrupt nodes in the system, honest nodes can always pass the audit with probability 1. More formally, for any $\lambda$, $S$, any initial $\mathrm{𝖣𝖡}$, any adversary $𝒜$, the following experiment outputs $1$ with probability $1$:

• $\mathrm{■}$

  Initialize. Call $\mathrm{𝖼𝗋𝗌}\leftarrow \mathrm{𝐒𝐞𝐭𝐮𝐩}(1^{\lambda })$, and $\varphi ,{\mathrm{𝗌𝗍}}^0\leftarrow \mathrm{𝐈𝐧𝐢𝐭}(\mathrm{𝖼𝗋𝗌},S,\mathrm{𝖣𝖡})$.

• $\mathrm{■}$

  Queries. The adversary can adaptively issue the following queries, where each query is one of the following:

  • –

    Corrupt. $𝒜$ declares some identity $\mathrm{𝑖𝑑}$ as corrupt. If $\mathrm{𝑖𝑑}$ has already joined earlier, give its private state ${\mathrm{𝗌𝗍}}^{\mathrm{𝑖𝑑}}$ to $𝒜$.

  • –

    Join. $𝒜$ specifies an identity $\mathrm{𝑖𝑑}$. If the identity $\mathrm{𝑖𝑑}$ has previously been corrupted, the publisher performs the $\mathrm{𝐉𝐨𝐢𝐧}$ protocol with $𝒜$ who acts on behalf of $\mathrm{𝑖𝑑}$. Otherwise, spawn an honest identity $\mathrm{𝑖𝑑}$, and have the publisher perform the $\mathrm{𝐉𝐨𝐢𝐧}$ protocol with $\mathrm{𝑖𝑑}$. If $\mathrm{𝑖𝑑}$ has previously been spawned, simply ignore the existing state and respawn the node.

  • –

    Update. $𝒜$ specifies an updated block $\mathrm{𝗎𝗉𝖽}$, a set of identities $\mathrm{𝖨𝖣𝖲𝖾𝗍}$. It is required that $\mathrm{𝖨𝖣𝖲𝖾𝗍}$ is chosen among the identities that have joined, and moreover, all honest identities that have been joined must belong to $\mathrm{𝖨𝖣𝖲𝖾𝗍}$. Now, the $\mathrm{𝐔𝐩𝐝𝐚𝐭𝐞}$ protocol is invoked with $\mathrm{𝗎𝗉𝖽}$, involving the publisher and $\mathrm{𝖨𝖣𝖲𝖾𝗍}$. Note that $𝒜$ will act on behalf of any corrupt identity in $\mathrm{𝖨𝖣𝖲𝖾𝗍}$.

• $\mathrm{■}$

  Challenge. $𝒜$ specifies an identity $\mathrm{𝑖𝑑}$ that has joined and remains honest. Now, the honest $\mathrm{𝑖𝑑}$ engages in an $\mathrm{𝐀𝐮𝐝𝐢𝐭}$ protocol with the auditor who receives the up-to-date $\varphi$. The experiment outputs 1 if the auditor accepts; else it outputs 0.

We now proceed to the security definitions. Our security definition has two components: approximate best-possible recoverability and replication security. We describe both components in detail below.

Intuitively, replication security says that if an adversary wants to get $\alpha$ times the fair reward in expectation, it must be consuming roughly $\alpha$ times the space, and this must hold even when the original data itself is compressible. We now elaborate on how to understand the definition. Suppose the adversary dedicates $\alpha \mu S$ blocks of space where $S$ is the space of an honest node. We expect that in every period, the adversary should get roughly $\alpha \mu$ times the fair reward. However, the adversary can allocate $\alpha \mu S$ blocks of space among its $\mu$ nodes in various ways: it can allocate $S$ space for $\alpha \cdot \mu$ nodes and 0 space for the remaining nodes, but it can also equally allocate $\alpha \cdot S$ space to each of the $\mu$ nodes. Regardless, the adversary should not get noticeably more than $\alpha \cdot \mu$ times the fair reward. Our replication security definition captures this intuition by randomly sampling a challenge node among the $\mu$ specified nodes, which is effectively an “averaging argument” to capture the idea that “no matter how the adversary allocates its space, it should get no more than $\alpha \cdot \mu$ times the fair reward in expectation”. Another reason why we randomly sample a challenge node in the definition rather than challenging all of them is because in practice, it may make sense to randomly sample the time at which each node is challenged. If the challenge times are known ahead of time, then the adversary can reconstruct the storage right before the challenge and delete the space afterwards.

Our replication security notion implies an $ϵ$-Nash-equilibrium, that is, a node with a fixed amount of space cannot get $ϵ$ fraction more rewards than behaving honestly and contributing all of its space towards archiving the dataset. Because honest behavior is an equilibrium, it implies that that in the equilibrium state, any node claiming rewards commensurate with contributing $\alpha n$ blocks of space is actually storing $\alpha$ copies of the database.

First, if the database were static, we can employ the following idea.

• $\mathrm{■}$

  Preprocess and publish. The trusted data publisher computes an erasure code over the original database $\mathrm{𝖣𝖡}$, resulting in $\overline{\mathrm{𝖣𝖡}}$. It then computes and publishes the Merkle digest denoted ${\varphi }^{\mathrm{DB}}$ of $\overline{\mathrm{𝖣𝖡}}$.

• $\mathrm{■}$

  Store. Every storage node with roughly $S$ blocks of space uses a random oracle $G(\mathrm{𝑖𝑑},\cdot )$ to sample $S$ indices. It then downloads $\overline{\mathrm{𝖣𝖡}}[S]$ along with the relevant Merkle opening proofs, and computes a replication encoding of $\overline{\mathrm{𝖣𝖡}}[S]$ henceforth called the node’s shard. Specifically, we will use the PoRep scheme of Pietrzak [34]. The resulting replication encoding has $S$ blocks, and it provides the guarantee that the encoding is incompressible if the node later wants to pass the audit within bounded time.

  The node additionally computes a corresponding Merkle digest ${\varphi }^{\mathrm{shard}}$ of its replication-encoded shard, and a succinct correct proof $\pi$ attesting to the fact that ${\varphi }^{\mathrm{shard}}$ is computed correctly w.r.t. $G(\mathrm{𝑖𝑑},\cdot )$ and ${\varphi }^{\mathrm{DB}}$. Finally, the node stores the following information:

  1. 1.

     its shard, the shard’s Merkle digest ${\varphi }^{\mathrm{shard}}$, as well as a proof of correctness $\pi$ of the digest ${\varphi }^{\mathrm{shard}}$, and

  2. 2.

     the Merkle openings of all (replication-encoded) blocks in the shard.

• $\mathrm{■}$

  Audit. An auditor samples $\kappa =\omega (\log \lambda )$ random challenge indices among $[S]$ and asks the storage node to open the replication-encoded blocks at these positions. The node responds with the challenged positions, along with ${\varphi }^{\mathrm{shard}}$, $\pi$, and the Merkle opening proofs of the opened positions w.r.t. ${\varphi }^{\mathrm{shard}}$. The auditor accepts if $\pi$ verifies and all Merkle opening proofs verify.

Throughout the paper, we assume that the block size $B$ is at least polylogarithmically large, such that the space required for storing metadata (e.g., digests and opening proofs) is absorbed by the block storage.

Now, if the database is evolving over time, the most naïve approach is to rerun the static scheme from scratch with every update. The resulting scheme indeed satisfies $ϵ$-best-possible recoverability as well as $ϵ$-replication-security for an arbitrarily small $ϵ\in (0,1)$. Unfortunately, for each update, the scheme would incur $\tilde{O}(B\cdot N)$ cost for the publisher and $O(B\cdot S)$ cost for each storage node, where $N$ is the maximum data size.

We ask the natural question: can we reduce the cost per update to $\tilde{O}(1)\cdot B$ ?

With Bentley and Saxe’s techniques [9], the publisher can maintain a hierarchy of levels numbered $0,1,\mathrm{\dots },L=O(\log N)$, respectively, where each level $\mathrm{\ell }\in \{0,1,\mathrm{\dots },L\}$ is either an erasure code of $2^{\mathrm{\ell }}$ blocks, or empty.

Every time a new data block arrives, we find the smallest empty level denoted ${\mathrm{\ell }}^{\ast }$, and merge all smaller levels as well as the newly arriving block into level ${\mathrm{\ell }}^{\ast }$, by recomputing an erasure code of these blocks. The levels smaller than ${\mathrm{\ell }}^{\ast }$ now become empty. Further, suppose that the data publisher publishes a Merkle digest of each level. Assuming that the block size $B$ is larger than the size of a Merkle opening proof, and the erasure code has constant rate, then the amortized publisher cost for maintaining this hierarchical data structure can be as small as $O(B\log N)$ if we use a special updatable erasure code proposed in prior work [38].

The idea is for each storage node with approximately $S$ blocks of space to choose $s_{\mathrm{\ell }}$ random erasure-coded blocks per non-empty level for its shard, such that ${\sum }_{\mathrm{\ell }}{s}_{\mathrm{\ell }}=S$. As before, this selection can be made with the help of a random oracle $G(\mathrm{𝑖𝑑},\cdot )$. During the audit, the auditor will challenge $\mu =\omega (\log \lambda )$ random indices per level.

The challenging question is: how do we allocate the local space $S$ among the levels? To understand the subtleties here, it helps to look at a couple naïve approaches:

• $\mathrm{■}$

  (Idea 1) Uniform sampling rate: prone to selective censorship. The first idea is to use a uniform sampling rate. Specifically, let $p=S/n$ where $S$ is the local space provisioning and $n$ is the current database size – for a growing database, we can recompute the sampling rate $p$ whenever the database size has reached $(1+o(1))\cdot n_{\mathrm{prev}}$ where $n_{\mathrm{prev}}$ denotes the database size when $p$ was last calculated. Now, a node would sample every block in any level with uniform probability $p$, so that in expectation, it will get $S$ blocks for its shard.

  Unfortunately, this natural approach is fundamentally flawed. Under this approach, a node would end up sampling $\mathrm{\Theta }(S)$ blocks in expectation for the largest level. However, for any constant-sized level (say, level 0), the fraction of nodes required to store some block of that level is only $\mathrm{\Theta }(S/n)$. This means that if the adversary selectively deletes the small fraction of identities assigned to store some block of level $0$, it can completely wipe out the data belonging to level $0$! Another way to think of the same attack is the following. As mentioned, it could be that the adversary controls all the pseudonyms that are contributing and requesting rewards. In this case, if the adversary chooses only identities that are not assigned any block of level $0$ (e.g., through rejection sampling), it can successfully wipe out level $0$ altogether while still being able to pass the audits.

• $\mathrm{■}$

  (Idea 2) Same number of blocks per level: causes space waste. To fix the problem with idea 1, we can increase the sampling rate of the smaller levels. A natural idea is to sample the same number of blocks per level regardless of the level’s size. In other words, a node samples $s_{\mathrm{\ell }}=S/\widehat{L}(n)$ blocks for every non-empty level, where $\widehat{L}(n)$ denotes the number of non-empty levels under a size-$n$ database. Unfortunately, this approach suffers from a different problem partly because the smaller levels effectively replicate their data much more abundantly than the larger levels, leading to a waste problem. In particular, $ϵ$-best-possible recoverability requires that when $\mu$ nodes pass the audit and the total space provisioned satisfies $\mu \cdot S\approx (1+ϵ)n$, we should be able to extract the entire dataset. However, when $\mu$ is chosen to ensure recoverability of the largest level $L$, i.e., $\mu \cdot s_{\mathrm{\ell }}\approx (1+ϵ)\cdot 2^L$, the total space provisioned $\mu \cdot S$ could exceed the data size by a logarithmic factor, that is, $S\cdot \mu =\mathrm{\Omega }(n\log n)$. In other words, this approach would require a total space provisioning of $\mathrm{\Theta }(n\log n)$ rather than $(1+ϵ)n$ to recover a database of size $n$.

More fundamentally, Idea 2 fails partly because our security definition itself lacks compositional guarantees. Specifically, Idea 2 can in fact be shown to satisfy $ϵ$-best-possible recoverability for each individual level, as long as we select the parameter $S$ and the rate of the erasure code satisfy some mild assumptions. Unfortunately, it is not the case that if each individual level satisfies $ϵ$-best-possible recoverability, the union of all levels would also satisfy the same notion. Partly, this is because the number of nodes $\mu$ needed for the space provisioning per level to roughly match the level’s size can vary across the levels!

We resolve the aforementioned challenges by using a hybrid of the aforementioned ideas. Specifically, we divide the levels into two categories: the biggest $2\log \log n$ levels numbered $L-2\log \log n+1$ to $L$ are called the large levels, and all remaining levels are called the small levels. In our formal description later, we generalize the parameter $2\log \log n$ to more general forms, but for clarity, we simply use $2\log \log n$ in the informal roadmap. By renaming, we may assume that each node has $(1+o(1))S$ blocks of space rather than $S$ for some suitable sub-constant function $o(1)$. We will allocate the $(1+o(1))S$ blocks of space among the levels as follows:

• $\mathrm{■}$

  Large levels. We dedicate $S$ blocks of space in aggregate to the large levels. Among the large levels, we adopt a uniform sampling rate. In other words, a large level $i+1$ occupies twice as much space as level $i$.

• $\mathrm{■}$

  Small levels. We dedicate $S\cdot o(1)$ blocks of space in aggregate to the small levels. Further, this space is divided evenly across the small levels.

This hybrid approach achieves the best of both worlds. First, by having a higher sampling rate in the smaller levels, we prevent the aforementioned selective censorship attack. Second, since nearly all the space is allocated to the large levels, the space waste caused by the smaller levels is restricted to $S\cdot o(1)$. Moreover, the $o(1)$ factor loss can be absorbed into the $ϵ$-slack already permitted in our security definition.

One remaining technicality is how to formally argue resilience against the selective censorship attack mentioned earlier. In particular, if for some level $s_{\mathrm{\ell }}$, each storage node samples only $s_{\mathrm{\ell }}=1$ block to store, then an adversary can carefully select a set of identities that cause $2/3$ of the (erasure-coded) blocks to be lost. Specifically, the adversary can use rejection sampling to select only identities that are assigned a block from the first $1/3$. Intuitively, when $s_{\mathrm{\ell }}$ is larger, erasing $2/3$ of the blocks appears much harder, since only a negligible fraction of $\mathrm{𝑖𝑑}$s avoid hitting any specific $1/3$ of the blocks.

To formalize this intuition, we consider an adversary that can make at most polynomially many queries to $G(\mathrm{𝑖𝑑},\cdot )$. After these queries, it selects a subset of $\mu$ queried identities denoted ${\mathrm{𝑖𝑑}}_1,\mathrm{\dots },{\mathrm{𝑖𝑑}}_{\mu }$ to minimize the union $G({\mathrm{𝑖𝑑}}_1,\cdot )\cup \mathrm{\dots }\cup G({\mathrm{𝑖𝑑}}_{\mu },\cdot )$. We prove that with all but negligible probability, $|G({\mathrm{𝑖𝑑}}_1,\cdot )\cup \mathrm{\dots }\cup G({\mathrm{𝑖𝑑}}_{\mu },\cdot )|\ge \min (2^{\mathrm{\ell }},(1-ϵ)\cdot s_{\mathrm{\ell }}\cdot \mu )$, as long as i) the number of blocks sampled $s_{\mathrm{\ell }}$ is at least polylogarithmically large, and ii) the redundancy (i.e., inverse rate) of the erasure code is a suitably large constant. In particular, this implies that as long as $(1-ϵ)\cdot s_{\mathrm{\ell }}\cdot \mu \ge 2^{\mathrm{\ell }}$, then the union of any $\mu$ nodes’ shards are sufficient for reconstructing level $\mathrm{\ell }$ which contains $2^{\mathrm{\ell }}$ blocks – even when the identities are adversarially chosen.

Of course, our actual proof is more complicated than the above. In the actual proof, the above combinatorial reasoning is embedded in some extraction argument that takes into account the fact that even when a node passes the audit, it may not be storing all blocks belonging to its shard. We defer the details to Section 9 of the full version.

The careful reader may also observe that a straightforward instantiation of our hybrid space allocation idea would incur roughly $\tilde{O}(S)\cdot B$ amortized cost per update for a storage node. However, later in Section 3.4, we will discuss some additional tricks that bring this cost down to $\tilde{O}(1)\cdot B$.

Although the new hybrid space allocation appears to address the aforementioned issues, we are not aware of any method to formally prove its security. Specifically, one important challenge we face is that the underlying replication encoding scheme [34] lacks compositional guarantees.

Pietrzak [34] only proved the incompressibility (subject to answering challenges quickly) of his replication encoding scheme in a standalone setting. More specifically, imagine that there is a single database, and we use the digest of the database to seed the hash function used to compute the replication code. Then, the resulting replication code is incompressible subject to answering challenges quickly.

In our application, there is a separate instance of the replication encoding per level. The most straightforward approach is for each level to use the level’s own digest (along with the storage node’s $\mathrm{𝑖𝑑}$) to seed its own hash function. With this approach, however, the adversary in our security experiment would be able to choose the data contents of the smaller levels to depend on the replication codes of the larger levels. This is because in our security experiment, the adversary chooses the updates adaptively over time. So when it chooses the blocks that go into the smaller levels, the replication codes of the larger levels are already available.

Unfortunately, Pietrzak’s proofs [34] fall apart in such a setting when multiple instances are composed and some instances’ data can depend on other instances’ replication code. Upon a closer examination, Pietrzak’s proof has the following blueprint – henceforth let $𝒜=({𝒜}_1,{𝒜}_2)$ where ${𝒜}_1$ is the adversary that outputs some database $\mathrm{𝖣𝖡}$ and an adversarial replication encoding denoted ${\mathrm{𝗌𝗍}}^{𝒜}$ of $\mathrm{𝖣𝖡}$, and ${𝒜}_2({\mathrm{𝗌𝗍}}^{𝒜})$ is the adversary interacting with the auditor.

• $\mathrm{■}$

  First, he shows that if ${𝒜}_2({\mathrm{𝗌𝗍}}^{𝒜})$ can answer challenges quickly, then there is a winning strategy to an underlying pebbling game. Specifically, by placing some initial labels on the depth-robust graph, the adversary can pebble almost all vertices in a small number of steps.

• $\mathrm{■}$

  Second, he analyzes the underlying pebbling game and argues that for any winning strategy, the number of initial pebbles must be large.

• $\mathrm{■}$

  Finally, he shows that if ${\mathrm{𝗌𝗍}}^{𝒜}$ is short, and the number of initial pebbles is large, then one can construct an encoding scheme to compress the random oracle $H({\varphi }^{\mathrm{DB}},\cdot )$ where ${\varphi }^{\mathrm{DB}}$ is the digest of the challenge database, thus contradicting Shannon’s theorem that random strings are incompressible. Intuitively, every initial pebble corresponds to a location ${𝒜}_2({\mathrm{𝗌𝗍}}^{𝒜})$ can predict in $H({\varphi }^{\mathrm{DB}},\cdot )$. As a result, we need not record these predicted positions in the encoded string, thus achieving compression. The encoded string consists of the short ${\mathrm{𝗌𝗍}}^{𝒜}$, $H({\varphi }^{\mathrm{DB}},\cdot )$ at all non-predicted locations, and a small amount of metadata needed for extracting from ${𝒜}_2({\mathrm{𝗌𝗍}}^{𝒜})$ the predicted locations.

The subtlety in the proof lies with the decoder. For technical reasons, the decoder needs to know the database to successfully extract $H({\varphi }^{\mathrm{DB}},\cdot )$ at the predicted locations. In a standalone setting, before running ${𝒜}_2$ to perform decoding, the decoder first runs ${𝒜}_1$ till the point it first submits ${\varphi }^{\mathrm{DB}}$ to extract the database – henceforth this is called the preparation stage. If the digest ${\varphi }^{\mathrm{DB}}$ is also computed from a random oracle, then except with negligible probability, ${𝒜}_1$ cannot have queried $H({\varphi }^{\mathrm{DB}},\cdot )$ yet before revealing the database. In our composed setting, the same proof strategy fails, since ${𝒜}_1$ will submit the different level’s data incrementally. This means that before submitting the data in level $1$, ${𝒜}_1$ may already start querying $H({\varphi }_0^{\mathrm{DB}},\cdot )$ yet where ${\varphi }_0^{\mathrm{DB}}$ is the digest of the $0$-th level. Unfortunately, the decoder has no way of answering queries to $H({\varphi }_0^{\mathrm{DB}},\cdot )$ yet in the preparation stage, without having run ${𝒜}_2$ to perform the decoding.

Although the literature also comes with some other replication encoding candidates [23, 22], to the best of our knowledge, no known scheme provides the compositional guarantees we desire.

One way to solve the problem is to devise a replication coding scheme with the desired compositional guarantees, where the data of some instances may depend on the replication code of other instances. Unfortunately, we are not aware of any existing tools that can be used to achieve this: existing techniques for proving space-time tradeoffs through direct incompressibility arguments are highly involved and apply to extremely limited settings [19, 20]. While some other proof techniques [39, 18, 1, 25, 2] have been shown to prove space-time tradeoffs, they do not produce meaningful results in our setting.

Fortunately, we devise a method that side-steps this problem. Whenever a new erasure-coded level is rebuilt in the hierarchical data structure, we ask a storage node to recompute its replication codes for all levels, using the union of all levels’ digests $({\varphi }_0,\mathrm{\dots },{\varphi }_L)$ along with the node’s $\mathrm{𝑖𝑑}$ as the seed to the random oracle.

At first sight, this approach comes with additional computational overhead on the storage node. Specifically, the computational cost per update is at least $S\cdot B$. However, in Section 3.4, we discuss additional tricks to asymptotically reduce the computational overhead, and achieve $\tilde{O}(1)\cdot B$ amortized cost per update.

So far, we have a candidate scheme but each storage node must pay at least $S\cdot B$ download bandwidth and computational cost per update. We propose a couple additional tricks to bring this cost down to $\tilde{O}(1)\cdot B$. For example, when $S$ is roughly $\sqrt{n}$ (see also Section 7.1 of the full version), these tricks bring significant cost savings. We stress that it is inherently unavoidable that each node must pay at least constant cost per update subject to our definitions – in this sense, our update costs are nearly optimal. Specifically, if 1% of the nodes do nothing upon an update, it means that they have no information about the new block. Now, if the adversary selectively corrupts the 99% remaining nodes, it can selectively erase this new block from the universe even if the 1% nodes’ combined storage is already large enough to store the entire dataset.

1. 1.

   Small $⟹$ $\{\text{tiny, mini, small}\}$: We further divide the small levels into tiny, mini, and small levels. For the tiny levels each containing at most $\kappa =\omega (\log \lambda )$ blocks, the node simply stores the original data blocks (without any encoding), and all of the blocks are challenged during the audit. For the mini levels each containing between $\kappa$ and $\mathrm{\Theta }(S/{\log }^{2}n)$ blocks, the node stores all encoded blocks belonging to the level (without using the random oracle $G$ to subsample), and $\kappa =\omega (\log \lambda )$ of them will be challenged during the audit. The small levels are treated in the same way as before.

2. 2.

   Seed with an aggregate digest only for the large levels: Instead of making all levels’ replication codes use the aggregate digest $({\varphi }_0,\mathrm{\dots },{\varphi }_L)$ as the seed, we have only the large levels use the aggregate digest ${\{{\varphi }_{\mathrm{\ell }}\}}_{\mathrm{\ell }\in \text{large}}$, and the small levels use the level’s own digest as the seed. Recall that the large levels occupy $1-o(1)$ fraction of the local space, this modification does not affect our $ϵ$-replication security since the $o(1)$ loss can be absorbed into the arbitrarily small constant slack $ϵ\in (0,1)$.

A more detailed description and analysis of these optimizations are provided in Section 6.2 of the full version.

Recall that so far, in our underlying static construction, we rely on a SNARK proof to attest to the correctness of the shard’s digest ${\varphi }^{\mathrm{shard}}$ w.r.t. the database’s digest ${\varphi }^{\mathrm{DB}}$ and the indices selected by the shard $G(\mathrm{𝑖𝑑},\cdot )$. Using a SNARK, however, comes with a couple drawbacks. First, it incurs additional costs of cryptographic computation. Second, since the replication encoding is computed using a random oracle (RO), we would end up computing a SNARK over computations that involve RO queries – this is undesirable due to impossibilities of relativized succinct arguments in the RO model.

In our final construction, we avoid this SNARK proof by checking correctness at a few challenged locations, resulting in a proof of approximate correctness (rather than strict correctness). Further, we make our approach non-interactive by having the node sample the challenges itself through a random oracle (commonly known as the Fiat-Shamir paradigm). The fact that we only have approximate correctness introduces additional technicalities in our proof. Note that in comparison, Pietrzak’s proof works only if the encoder is honest. Nonetheless, we show that approximate correctness is sufficient for proving our security notions. We defer the details to the subsequent formal technical sections.

In Section 7 of the full version, we discuss a couple of extensions. Specifically, we show how to support non-uniform space provisioning among nodes, ensuring that a node with $k$ times the space need not incur $k$ times the update and audit costs. We also show when provided with a trusted hash digest of the original dataset ${\varphi }_{\mathrm{orig}}$ (e.g., from the blockchain’s consensus layer), how to instantiate the publisher without any trust, by relying on an Incremental Verifiable Computation (IVC) scheme to incrementally compute succinct proofs that vouch for the correctness for the digests of the erasure-coded hierarchical data structure.