Sharding the IOTA Tangle Effectively
The full article was originally published by Eukaryote on Medium. Read the full article here.
The IOTA tangle is an incredibly innovative data structure which eliminates the need for expensive and/or centralizing PoW/PoS-based synchronization. However, there’s one pertaining problem with it: The IOTA Tangle is currently stored on every single node, in full, which requires the database to be pruned (i.e snapshotted) regularly, which is an inelegant solution to the problem as we want data stored in the Tangle to, ideally, last forever (or at least a reasonably long time), in much the same way as in a blockchain.
When we shard the Tangle, we want to create many smaller subsections of the larger Tangle in a way such that each node needs to make as few calls to other nodes as possible, and without compromising the collective strength of a large Tangle. We can accomplish this through clever definition of shards, ensuring as little ambiguity as to the location of any transaction as possible.
We may first consider sharding the Tangle by transaction hash, such that every shard keeps transactions whose hashes fall in a certain range. If there are t total shards and a total transactions, this allows nodes to only keep a/t transactions, which reduced the storage space needed. Additionally, each node only needs to know about transactions in its shard, so nodes only need to broadcast transactions to neighbors of the corresponding shard. However, this poses a major problem: how to check double spends. As the number of shards increases, so does the number of neighbors contacted in order to verify a transaction, as we need to contact neighbors of every shard to find transactions by address. As the number of shards scales, this may become simply too expensive.
We can also shard the Tangle by address hash, an arguably more logical way to subdivide the Tangle. This solves the problem of double spend checking, at the expense of transaction retrieval, as the node has to ask every single shard for transactions.
So, what if we shard by multiple features? If each node stores all the transactions with hashes in a certain range or transactions with address hashes in a certain range, then each shard can lookup by address hash and transaction hash, without needing to contact every neighbor. In addition, as there will be overlaps between the address range and the transaction range, the amount of transactions that need to be stores is less than or equal to (a/t)*w (there is a method for a calculation of the mean expected transactions per node), where w is the number of different features (i.e Transaction Hash, Address Hash, Approvee Hashes, Bundle Hash).
Several optimizations could be made to the IOTA Implementation to accommodate this better. A must is automatic peering (such as provided by Nelson), and the ability to only send and receive transactions with peers on the same shard, and only communicate with peers on different shards to verify transactions, obtaining other shards’ tips to confirm, and looking up transactions not in the current shard. This means that there could be dozens of shards and a node could have hundreds of neighbors while only maintaining an active connection with a few of them, allowing for the network to scale much better, as well as making running a full node much more practical, and with uptime limits lifted by automatic peering, making every wallet a full node could become practical again. This is by no means a perfect approach, but it brings to light the possibility of sharding in IOTA.
The biggest limit of blockchain is the requirement of every node to store, transmit, and validate every transaction, leading to centralization and scaling problems. The biggest advantage of Tangle is its relative partition tolerance and flexibility. By leveraging that, we can make every node only store a portion of the Tangle, and only receive some transactions while not compromising the innate efficiency of the Tangle. Let’s improve what we do best.