LeapChain: Efficient Blockchain Verification for Embedded IoT

Publication
Proceedings of the 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
Date

One of the challenges of Blockchain is its linear growing size. Even light clients need to download and hash up to 40 MB of block headers for Bitcoin and up to 3 GB for Ethereum – too much for an embedded IoT device. As a remedy, we have created LeapChain, a Blockchain extension that allows to verify the inclusion and integrity of any block using only a logarithmic amount of block headers. By inserting just one additional back-linking hash into each block header, the maximum processed header data is reduced to 7.3 kB in the worst case. The logarithmic scaling is achieved by a special repeating pattern of several backlink distances that are calculated as multiples of a common base value. If you want to understand how it works, read on.

LeapChain Idea: we add a leap-hash allowing us to traverse the blockchain with a reduced amount of steps.

Motivation: Blockchain for embedded IoT

While cryptocurrencies focus on transactions of assets, there exist ideas to transfer Blockchain to the embedded domain, such as for secure peer-to-peer firmware updating and validating. For this scenario, a manufacturer would publish a signed hash of the latest firmware on a blockchain, where the signature is verified by all full powered network participants and – if valid – included in the blockchain. An IoT end node could then receive a new firmware from any peer and verify its validity and integrity by simply comparing its hash to the hash in the blockchain. This solution is more robust as it avoids a single point of failure, more efficient because the end nodes do not need to perform public key cryptography, and more transparent as any new update is publicly verified on the blockchain. However, due to the constant growth of the blockchain, downloading and processing the entire chain will quickly exceed the resource capabilities of cheap IoT devices. We therefore developed an efficient block verification approach for constrained IoT devices.

LeapChain Pattern

We extend the conventional block structure, such that each block header stores one additional back-linking leap-hash that “points” further back than just the direct predecessor – leaping over several blocks in between.

In order to achieve a logarithmic scaling, we use several leap-widths $w(i)$ based on different exponents to a constant base $b$. These leap-widths are calculated from the block height $i$ according to

$$ w(i) = b^{(i \mod b)} \quad \in \ W = \big\{ b^1, b^2, \ldots, b^b \big\} $$

which ensures that all leap-widths have a single common divisor $b$ and each leap-width is $b$ times the previous leap-width. Beginning with $i = 1$, we assign each block of height $i$ a leap-hash that belongs to the $w(i)$-th previous block. If $w(i)$ points to a block index $i < 0$, we set the leap-hash to the hash of the genesis block ($i = 0$).

LeapChain Pattern for $b = 4$

Example

Consider the case where base $b = 4$, which would result in four leap-widths $\{4^1, 4^2, 4^3, 4^4\} = \{4, 16, 64, 256\}$. All blocks with index $i \mod 4 = 1$, which are colored in green, form a single leapline with leap-width $w = 4$. The next leap-width is $w = 16$ (orange) and between two connected orange blocks, we have $4-1$ other orange blocks, each belonging to one of the $\frac{16}{4}=4$ separate leaplines of width $w = 16$. The common base $b = 4$ ensures that all leaplines jump multiple of 4 and thus a block of one leapline will never hit a block of another leapline. As a result, block 2 can be reached from block 69 in 4 steps (68, 67, 3, 2) by using either the prev-hash or the leap-hash.

Verification via Suffix Proofs

The LeapChain pattern allows us to verify that a certain block $X$ and its data, which could be a firmware hash, are included in the blockchain and were confirmed by consensus. We use the additional backlinks to construct a LeapChain that proves the integrity of the blockchain between two blocks $X$ and $Y$ by traversing the blockchain from $Y$ to $X$ using only a subset of blocks $\mathcal L \subseteq X,...,Y$.

LeapChain suffix proof for $X = 6$: We traverse from the latest block $Y=49$ to $X = 6$ proving integrity and PoW consensus.

Basically, $\mathcal L$ connects the latest block $Y$ to our target block $X$ providing evidence of a certain amount of cumulative PoW on top of $X$, which confirms the consensus. The proof $\mathcal L$ is constructed based on the distance $\delta$ between $Y$ and $X$. We iteratively calculate the largest leapline that fits into the remaining distance. Leaplines can be switched by using the prev-hash instead of the leap-hash. So in general, a proof consists of three parts:

  1. an initial walk part (using prev-hash) to reach the first leapline
  2. a jump part using several leaplines (using leap-hash to jump or prev-hash to switch lines)
  3. a final walk part to reach the target block.

As shown above, it is also possible to construct several LeapChains between two blocks. So if we do not trust a specific LeapChain, we can challenge our peers by requesting an alternative LeapChain, which is infeasible to construct in such a short time for an attacker attempting to provide false blocks.

The PoW consensus requires that each block hash needs to be below the target value, which is determined by a certain difficulty. This difficulty is usually calculated from previous blocks using timestamps but since we will leap blocks, a verifying device cannot determine the difficulty for the blocks of a LeapChain because it does not know the difficulty of the intermediate blocks. However, this problem can be solved by including the current difficulty in the block data or by requesting more blocks of a lower difficulty.

a) Logarithmic Scaling of LeapChain and b) upper bounds of processed block headers.

Conclusion

The LeapChain proof size scales logarithmically with $b \log_b(\delta)$ to the block distance $\delta$ while maintaining the same integrity guarantees as the full chain. Setting $b = 8$, we can verify the inclusion of any block out of 134 million blocks using at most 76 block headers. LeapChain guarantees deterministic and tight upper bounds for hardware requirements regarding memory and computation below a few kilobytes. This simple and efficient method would enable Simplified Payment Verification (SPV) and other blockchain applications on constraint embedded devices.

For more technical details about the construction of the verification proofs and the security analysis, see the full paper.