Simplified on Tangle voting with dynamic sharding
A bivouac is a structure formed by migratory army ant colonies. A nest is constructed out of living ant workers’ own bodies to protect the colony and is later deconstructed as ants move on.
Introduction
This blogpost series is based on the previous post “Indirect voting using two DAG layers” that tried to simplify the Tangle Multiverse consensus model for analysis. That laid a foundation to this next series, which is my first attempt to merge on Tangle voting with dynamic sharding.
I’d like to start by listing some concepts that are left out from this model for now (in addition to actual algorithms and proofs, i.e. the real work of course).
1.Local mana as a source of trust: In this model we don’t give much detail to the underlying source of trust. I don’t see local mana as a very important concept in the long run and I wrote more about it here. Local mana is a nice addition or temporary solution before a more scalable source of trust is applied, at best. Long term solutions might be DID based, or companies and instances running their identified voter nodes on the network. It might be possible to make this model work also with local mana as a source of trust, but it’s designed to function mainly with participants whose identity is known. There is a short description of the source of trust later on, but it’s far from complete and should be considered as an example. Focus on this post is the actual voting mechanisms.
2. Spam protection and congestion control: This is a huge field and it’ s pretty much left unaddressed here. The network should be capable of protecting honest participants from spam attacks. This should be distinguished from situations where network adoption grows and network matures. In the latter case the amount of sharding can increase without compromising safety. We most likely still need also congestion control mechanisms even though we have sharded ledger state. There are many different ways to approach these problems, but we don’t discuss them here.
General structure of the model
We begin with Iota Foundations dynamic sharding model where a wide Tangle is divided by practically unlimited shard markers. Tangle is also bend into a ring in a way that by increasing the shard marker one eventually goes around the circle back to the smallest shard marker. If you are not familiar with their sharding approach, there is a blogpost series about it by Hans Moog. Series is not fully completed, but you can find it here. There is also a Youtube presentation that gives a brief explanation of those parts that are still missing from the blog post series. You can watch it here, dynamic sharding starts at 59:20
One problem we face when combining dynamic sharding with on Tangle voting is, that if all voters don’t see similarly sized areas of the Tangle, voters might not see all votes given for a certain transaction. If this might occur, it is really hard to make a reliable voting model.
We aim to solve that problem by introducing a term “slice” to the model. In addition to dividing Tangle by shard markers, we divide the Tangle with (x) lines in a way that between each line (in the beginning) there are similar amounts of shard markers. In this example we could start with (x) being 100. Areas between lines are called a slice. A slice is basically a shard, but we don’t call it a shard because it might get confused with dynamic sharding terminology.
If we have a distributed system without any sybil protection mechanism, an adversary node can create almost as many sybil nodes as he wants. We aim to use that idea to our advantage and base our dynamic sharding approach to it. Every voter can place as many voting locations (VL) to the Tangle as they want. VL can be considered as a virtual node and all transactions are issued through some VL. Each VL has its own shard marker. Voters can vote in those slices they have a VL. VL can only be issued or removed, but not moved from one place to another. The general idea is that the network could start with every voter having VL at every shard. When the network evolves, voters can adjust the area of the Tangle they are interested in by removing or issuing new VL. The network consists only of VL and their interactions. Every transaction is tied to a certain VL. Votes travel with transactions like in the Indirect voting using two DAG layers model. Votes effect is limited to the slice where issuing VL belongs to. If a voter has multiple VL at a certain slice, it can issue transactions with any of those, but every VL functions separately and creates its own voting structures. Only after voters have determined how each VL votes, the final step is to check if some voters have multiple VL at a slice. Even if a voter issues multiple VL to a certain slice, his voting power remains the same.
Every voter that has a VL at a certain slice, follow transactions of that slice and transactions from adjacent slices. This allows voters to reference tips from adjacent slices (in priority layer 2) if the transaction issued is at the border of two slices. In this scenario the voter confirms the transactions from his own slice point of view, but voters at the adjacent slice consider the referenced transaction still as a tip because it doesn’t have any direct or indirect reference that ties it to the voting consensus (at priority layer 2) at its own slice. In other words transactions referenced from another slice don’t gain any votes from those references.
We can’t begin with too many slices. The more slices we have, the less transactions are issued per slice and this correlates to the confirmation time of a transaction. For that reason slices can merge with other slices or split into multiple slices depending on the network load. This is explained in detail at the fourth part of this series. It’s important to note hat the dynamic sharding is made possible by the VL system and every voter can decide how large an area of the network to follow. By changing the size of a slice network just aims to serve users in the best possible way, so it is kind of a maintenance operation.
Area of a slice is determined in the following way: Slice A has area from shard markers equal or larger than a and smaller than b. Slice B has area from shard markers equal or larger than b and smaller than c.
When doing on Tangle voting with slices, it might introduce some new problems. Even though every voter has the same voting power, whether or not there is a VL in between, the “effective voting power” decreases as the number of slices increases. The voter has a certain interest to send transactions at a certain slice, but the attacker might concentrate all it’s conflict spamming to a certain slice. If the voter’s voting area is divided into too many independent slices, he simply might not be interested in sending enough transactions to solve all conflicts in every area. We could solve this by forcing every user to send transactions through nodes owned by a voter, but that brings quite a heavy load on voter nodes.
A more sophisticated solution might be to allow two types of nodes. Voter nodes (whose identity is known) and permissionless nodes. Permissionless nodes could do all the heavy lifting (PoW for example) and then consult a voter node to send a transaction together. Transactions would always have to carry a voter node’s voting information. With permissionless nodes, local mana might provide a spam protection mechanism (so called access mana), but not give any voting influence (i.e. we don’t have a consensus mana). Also voter nodes ability to join into transaction sending could be restricted, so an attacker spamming conflicts would need to consult different voters in turns to keep up with spamming. This would help voters to solve conflicts even in high conflict load situations. One thing to note is that the underlying trust model needs to be accessible enough that it doesn’t create a situation where “miners” and users are separated. The fact that we don’t have groups with different interests is one of the biggest advantages of Iota compared to other projects. It should look more like a light node and full node kind of situation. But like said before, this depends on the trust model underneath, which we don’t discuss much more here.
Transaction structure
We use a simplified UTXO model where each transaction can only spend one UTXO either fully or partially and send tokens to another UTXO. This destination UTXO can either be newly created, or it can be combined with some other UTXO (in the latter case the destination UTXO will be spent and a new combination UTXO will be created). We don’t allow combinations of more than two UTXO with a single transaction for now.
Each time tokens are transferred, it’s realized using two transactions. Transaction 1 spends the UTXO selected and has the same shard marker as the spent UTXO. If tokens from that UTXO are only partially spent it creates a new UTXO with remaining tokens to that specific location. First transaction also specifies the destination of the second transaction.
When transaction 1 is confirmed by the network, the issuer can create a transaction 2 to the destination location using the transaction 1 as a proof. This transaction either creates a new UTXO, or merges tokens to already existing UTXO as described previously. The destination transaction has the same shard marker as the UTXO created. We use this rather complex system in order to tie all double spending attempts always to a single shard marker. This makes the model a lot simpler.
Continue to Part 2 here.
