The current method of choosing a starting point is "start with a random tip, and backtrack until reaching a transaction with enough cumulative weight.” We introduced a change in #75 : instead of choosing the first transaction which crosses the threshold, we choose the last one which doesn’t. The intention was to get rid of the frequent “sub-tangle is too big” errors that kept occurring during tip selection.
This change caused the Tangle to split into a bunch of split snakes, as the picture shows. While we’re not sure exactly how it came to be, it is clear why it’s stable: we choose a random tip to backtrack from (at the end of one of these snakes), and we don’t backtrack deep enough to get a starting point which allows merging. At some point this forking transaction is so deep that it’s impossible to start the walk there anyway ("sub-tangle is too big" error).
We might try to “fix” this situation by merging branches, but we would ideally like to find a tip selection method that heals itself in such a situation. As an interim solution, we reverted #75 .
Potential Solutions
Choose 2 independent entry points
This is tempting, but probably a bad idea, since it will be a complicated coding effort once we re-introduce the ledger state post z-net.
Selection the single “best” tip. This will prevent splitting by deterministically starting from the same tip. We suggested two potential criteria:
Always start from the most distant tip (from genesis).
Select the largest connected component:
Take the graph of transactions from the last X minutes
Find connected components and count their size.
Choose a random tip from the biggest component.
Optimized or heuristic tip selection when sub-tangle is too big. The idea is to find a way to never throw “sub-tangle is too big” errors. We suggested several methods to achieve this:
Unweighted steps: during the random walk take mostly alpha=0 steps (which are cheap), and only compute CW for a small fraction of the steps, while hoping to stay on the main tangle.
Keep old weights semi-updated (by storing the last computed CW for each transaction). This a heuristic approach that assumes weight differences don’t change too much for transactions in the deep Tangle.
Propagate CW to approvees when a new transaction becomes solid, rather than computing CW from scratch upon tip selection. This can be combined with caching (only propagate backwards once a “bin” has filled, which is a heuristic to optimize the propagation), and a cap on how far in the past you propagate (beyond which weights are no longer updated, or very infrequently.
Description
The current method of choosing a starting point is "start with a random tip, and backtrack until reaching a transaction with enough cumulative weight.” We introduced a change in #75 : instead of choosing the first transaction which crosses the threshold, we choose the last one which doesn’t. The intention was to get rid of the frequent “sub-tangle is too big” errors that kept occurring during tip selection.
This change caused the Tangle to split into a bunch of split snakes, as the picture shows. While we’re not sure exactly how it came to be, it is clear why it’s stable: we choose a random tip to backtrack from (at the end of one of these snakes), and we don’t backtrack deep enough to get a starting point which allows merging. At some point this forking transaction is so deep that it’s impossible to start the walk there anyway ("sub-tangle is too big" error).
We might try to “fix” this situation by merging branches, but we would ideally like to find a tip selection method that heals itself in such a situation. As an interim solution, we reverted #75 .
Potential Solutions
Choose 2 independent entry points This is tempting, but probably a bad idea, since it will be a complicated coding effort once we re-introduce the ledger state post z-net.
Selection the single “best” tip. This will prevent splitting by deterministically starting from the same tip. We suggested two potential criteria:
Optimized or heuristic tip selection when sub-tangle is too big. The idea is to find a way to never throw “sub-tangle is too big” errors. We suggested several methods to achieve this: