Problem
One of the main goals of coordicide is to have a dynamically available, partition tolerant core protocol. However, as recent conversations has shown, the current notion of confirmation is not partition tolerant. Indeed, if we have two forks of the tangle, the order the forks are downloaded affects the notion of confirmation.
Suppose we have forks A and B. Suppose that before the fork that nodes N_1,\dots, N_n have all the mana. The consider that in fork A, the mana is transferred to nodes M_1,\dots,M_m. Now consider the hypothetically extreme case where the N_i and M_j are distinct, and assume that nodes M_i operate only in the fork A, and very few, if any, N_i operate in A. Currently, mana is booked on confirmation, in a “current mana vector”. In fork A, the mana transfers will be confirmed (because the protocol is dynamically available, and confirmation will not halt), and the messages in A will be confirmed by the nodes M_j. Meanwhile, in fork B, the mana will be held by the N_i which will confirm the messages in B.
Now, when the forks merge, the nodes in B will not confirm the mana transfers to the M_j, and thus none of the messages in fork A will appear to be confirmed. Similarly, the nodes in A, will not see the messages in B confirmed. Therefore the fork will not be resolved, since no one can agree on which one is correct.
Recall, that partition tolerant means that the protocol can always choose between forks, not that these forks will be merged.
Proposed Solution
I propose that we return to mana based epochs. Specifically, the confirmation for each message in a certain epoch would be judged by the mana as computed with respect to a predefined epoch. Let me explain more precisely.
Fix a message M. Recall the following the vectors (recall that each indexed by the space of node IDs)
- \overrightarrow{\rm{supp}}(M) is the supporters of M
- \overrightarrow{\rm{mana}} is the mana vector
- \overrightarrow{\rm{act}} is the list of active nodes computed using Sebastian’s activity window
- \overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}} active mana vector: is the pointwise product of these vectors. A value is 0 if the node is non active, and for all active nodes, the value indicates the amount of mana the node has.
Then, we have
\rm{AW}(M)=\rm{comp}_{\overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}}}(\overrightarrow{\rm{supp}}(M))=\frac{\overrightarrow{\rm{supp}}(M)\cdot (\overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}})}{||\overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}}||}
where the dot is the normal dot product. We mark a message as confirmed when this percentage exceeds a certain threshold
I propose that we modify the formula as follows:
\rm{AW}(M)=\rm{comp}_{\overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}}(M)}(\overrightarrow{\rm{supp}}(M))=\frac{\overrightarrow{\rm{supp}}(M)\cdot (\overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}})}{||\overrightarrow{\rm{act}}\times\overrightarrow{\rm{mana}}(M)||}
where \overrightarrow{\rm{mana}}(M) is the mana vector of the computed at the end of epoch i-N where i is the epoch of M, and N is some parameter.
I claim that this notion of confirmation should be t invariant under the order that messages were received. This seems a bit complicated to prove, and so I omit the proof and hope that my claim is true, leaving this as an open problem 
Problem 1
The first central problem (besides that the above claim needs verified) is the computability. We used something similar to last spring, but it was computationally impractical because of the exponential moving average.
However, I think this can be fixed by simply removing the exponential moving average. Specifically I propose the following general algorithm:
- When we initialize the mana vector for Epoch n+1, we copy the mana vector from Epoch n
- When a message in epoch i becomes confirmed, we iterate through all mana vectors j\ge i and apply the mana changes
So is this practical from an implementation point of view?
Problem 2
One of the strength’s of this solution is that it allows us to “unconfirm” confirmed transactions. This can happen when the mana vector changes during an epoch. This presents some complications to the protocol.
First, how do we do the unconfirmation? Everytime a transaction is confirmed, do we have to iterate through all the messages to see where the confirmation flag changes?
Second, if we unconfirm a message what do we do? I suppose
- Un-mutate the changes in the ledger state
- Revert the changes in the mana vectors
- Change the eligibility status of messages in future conte.
The second is potentially expensive: for every mana change, we have to search for confirmation status’s to change, and which causes new changes in mana, which causes new changes in confirmation…
Number 3 presents a challenge to TSA and the scheduler: how does the fluctuating eligibility affect these modules.
These issues however might be endemic to any solution with reversible confirmations.