I made this post private since I wasnt sure if the chrysalis specs were public yet.
In chrysalis, we need to compute YTSRI and OTSRI efficiently. For definitions, read this first.
A primer on Boolean algebra representations
Let X be a set of size n and A be a subset. Let V be the vectors of 1s and 0s of length n. Fix a canonical ordering of X=\{x_1,x_2,\dots,x_n\}. We can represent A as a vector v^A\in V : let v^A_i=1 if and only if x_i\in A. Similarly, every vector v\in V defines a set A^v\subset X: v_i\in A if and only if v_i=1. Thus V is a representation of all the subsets of X. (Fun fact: this representation endows the subsets of X with an \mathbb{F}_2 algebra structure!)
Intuitively, this representation is defined by vectors containing the Boolean values answering the questions “Is x_i in A?”.
Set theoretic operations on subsets of X turn into pointwise logical operations on V.
- A\cup B corresponds to pointwise OR operations
- A\cap B corresponds to pointwise AND operations
-
A\setminus B (set deletion) corresponds to pointwise AND \neg operations (e.g. true AND \neg true=true)
So we can abuse notation slightly and apply the operations \cup, \cap, and \setminus directly to vectors in V.
Furthermore, consider a bit mask representation of a set. A bit mask effectively represents a set as a vector of 1s and 0s in the same way described above. Thus, we can apply the operations \cup, \cap, and \setminus to the bit masks using the logical operators discussed above.
Preliminaries
To perform the algorithms, a node will need to store the following information. In this document, unconfirmed means not approved by a milestone.
- Every transaction must be stored with with their YTSRI and OTSRI
- The recent cone of a transaction is the unconfirmed transactions in its past cone. Every transaction must be stored with a bitmask representing the recent cone. For a transaction
tx, we denote the bitmask bytx.recentCone. - A bud is a transaction whose recent cone is simply itself. We maintain a list of buds called
budList. This list can also be represented as a bit mask.
Incoming transaction
First, we indicate how to update all the above information for an incoming transaction tx which directly references transactions x an y
- The YTSRI and OTSRI of
txare respectively the maximum and minimum the YTSRIs and OTSRIs ofxandy. -
tx.recentCone=x.recentCone+recentCone+ hash (tx) where hash (tx) is the bitmask of the singleton transaction 1. - If
xandyare both referenced by milestones, then addtxto the bud list.
One can easily check that these actions are correct. Moreover, they are computationally cheap.
Incoming milestones
When a new milestone arrives, updating all these fields becomes more tricky. Moreover, we want to limit the number of times we need to traverse the tangle.
We can actually update this information with two traversals of the unconfirmed transactions. Let newlyConfirmed be the bit mask of the transactions whose milestone index is the last milestone. These are precisely transactions that were confirmed by the last milestone. This vector can be easily computed while the node is calculated the new ledger state under white flag.
First, we rest budList to the 0 vector (i.e. the empty set). In the first traversal of the unconfirmed transactions, we do the following to each tx
Set NewRecentCone=tx.recentCone\newlyConfirmed
If NewRecentCone does not equal tx.recentCone, then set tx.YTSRI=current Milestone
Set tx.recentCone=NewRecentCone
If size(tx.recentCone)=1, then
add tx to budList
Set tx.OTSRI=min{tx.trunk.milestoneNumber,tx.branch.milestoneNumber}
This logic updates
- YTSRI
- The recent cone bitmasks
- The bud list
- The OTSRI of each bud
Next, we retraverse the unconfirmed transactions using the bud list to update the OTSRI. Specially for each unconfirmed tx
Set tx.OTSRI=min{x.OTSRI | x in tx.recentCone INTERSECT budList}
This algorithm produces the correct OTSRI because we can prove that every unconfirmed transaction contains a bud with the same OTSRI.
Alternatives
The second traversal might not be strictly necessary. First, a node could just store the milestone number that each OTSRI is computed by. If the OTSRI is out of date when some application needs to use it, it can be updated on the fly.
Alternatively, both traversals can be done at once if the unconfirmed transactions are traversed from past to present: specifically we only process a transaction if we have passed through its entire past first. This way, all the buds in a transactions past cone would have already been identified. However, I cannot think of an efficient way of finding such a traversal.
Resource consumption
First, let us discuss memory. Let N be the number of unconfirmed transactions. We will need bit masks of size O(N) to prevent collisions. Note that even though the total number transactions that get stored in bit masks through out time is unbounded, only N transaction at a time.
Since each unconfirmed transaction will need its own bit mask, the memory consumption is O(N^2).
Since the order of each traversal doesnt matter, we dont actually need to walk the tangle. Thus these algorithms involve O(N) look up operations. Similarly, we will perform O(N) pointwise logical bitmask operations, yielding O(N^2) logical operations.
Overall, these algorithms wont scale indefinitely. However, it should handle a TPS in the 100s.
Open Questions
- What happens if there is a collision in the the bit mask? Will it cause a small aberration in the tip selection algorithm, or will it cause a network split?
- What is a good upper bound for N? What happens when this upper bound is violated? Can the node always just allow N unconfirmed transactions?
- How big do the bit masks need to be? This is dependent on the previous question. If occasional collisions can be tolerated, then the bit masks can be much smaller. If not, we need large bit masks.