SeF Notes.md

• Epoch is $k$ blocks (e.g. $k = 10,000$)
• $s$ are the droplets encoded per epoch
• Storage reduction factor is $\frac{1}{(k/s)}$ and needs approximately $k/s$ honest nodes

LT coding (clear droplets)

• Sample a degree $d$ from ${1,..,k}$
• Sample $d$ blocks from $k$ uniformly at random
• Bitwise XOR the $d$ blocks
• Encode a droplet $C_{j} = B_{1} \oplus .. \oplus B{j}$

Adversarial behavior

• Merky droplet: Peer reports $C_{a} \neq v_{a}B$
• Opaque droplet: Arbitrarily choose degree $d$, and arbitrarily choose $d$ blocks to encode into $C_{j}$. This attack attempts to increase probability of decoding failure

Decoding Failure

• If the node cannot decode the epoch in $ns$ droplets, it may contact additional droplets. When receiving additional droplets, it may undo the effects of the $B_{i}$ already decoded. Either a singleton is revealed, or additional nodes must be contacted. Decoding fails when all possible nodes have been contacted.

Degree Distribution

• A degree distribution, $\mu()$, is a probability mass function on integers ${1,..,k}$

Define $\rho(d)$ as: $$\rho(d) = \begin{cases} \frac{1}{k} & d=1 \ \frac{1}{d(d-1)} & d = 2,..,k \end{cases}$$

For $0 < \delta < 1$ and $c > 0$, define $R$: $$R = c\sqrt k \ln \frac{k}{\delta}$$

Define $\theta(d)$ as: $$\theta(d) = \begin{cases} \frac{R}{dk} & d = 1,..,k/R-1 \ \frac{R}{k}\ln(\frac{R}{\delta}) & d = \frac{k}{R} \ 0 & d = k/R+1,..,k \end{cases}$$ Let $\beta$ be: $$\beta = \sum_{d=1}^{k}\rho(d) + \theta(d)$$

Then the degree distribution $\mu$ is: $$\mu(d) = \frac{\rho(d) + \theta(d)}{\beta}$$ For $d = {1,..,k}$

Performance

• Bootstrapping cost: in a scheme with storage savings $\gamma$ and parameter $0 < \delta < 1$. The bootstrap cost measured by number of honest droplet nodes $K(\gamma, \delta)$ that a bucket node must contact such that the probability of recovering the blockchain is at least $1 - \delta$. The number of nodes $K(\gamma,\delta)$ may be considered the minimum number of honest droplet nodes for the system to guarantee at least $1 - \delta$ chance of recovery. For any savings $\gamma$, $K(\gamma,\delta) \geq \gamma$, i.e. $\gamma$ is the lower bound for the number of droplet nodes.
• Computation cost: expected number the arithmetic operations to construct and decode droplets
• Bandwidth cost: if there exists $σ$ malicious droplet nodes, the bandwidth cost is $\beta(\gamma,\delta,σ)$.

Storage savings: $$\gamma = \frac{k}{s}$$ Bootstrap cost: $$K(\gamma,\delta) = \frac{k + O(\sqrt k \ln^{2}(k/\delta))}{s}$$ Bandwidth overhead: $$\beta(\gamma, 2\delta, \sigma) = O\frac{ln^{2}(k/\delta)}{(1 - \sigma)\sqrt k}$$