| description | image | slug | keywords | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
This section introduces *access Mana* and *consensus Mana* and explains which modules use which Mana. |
5.3Mana |
|
This section introduces access Mana and consensus Mana and determines which modules use each of these two types of Mana.
Any permissionless system needs a Sybil protection mechanism. In Coordicide, this is done by forcing every node to create a node identity (see also Section 3.3 - Peer Discovery). Since the creation of an arbitrarily large number of identities is not an expensive operation, two Difficult-to-obtain resources are linked to each node identity; we call them access Mana(aMana) and consensus Mana (cMana). Both kinds of Mana can be described as essential resources to multiple parts of the network. They are related to the IOTA token, but are not tokens by themselves and do not interfere with the token balance in any direct way. When a transaction is processed, a certain amount of aMana and cMana—dependent on the amount of IOTAs moved by the transaction—will be pledged to nodes specified in the transaction (their node IDs must be specified as defined in Section 2.2 - Standard Payloads Layout). The access and consensus Mana pledged to each node ID must be stored as an extension of the ledger state. The only way a node can obtain aMana or cMana is to convince some ken holders to pledge to it. Both kinds of Mana provides adequate Sybil protection because they are difficult and costly to be acquired in arbitrarily large amounts.
Access and consensus Mana are used as Sybil protection in different modules, which have different natures and requirements. For this reason, it is natural to use different formulas to calculate the appropriate Mana to each module. Consensus Mana should be seen as the Mana that is responsible for the security of the system, on the other hand, access Mana is used to distribute access to the network during congestion periods.
We give a short overview on how each module uses its associated kind of Mana:
- Section 3.4 - Neighbor Selection: Nodes only establish a connection with nodes of similar consensus Mana.
- Section 4.6 - Congestion Control: The throughput (in bytes per second) of each node is dependent on the access Mana held.
- Section 6.3 - Fast Probabilistic Consensus: The selection probability for a node during a voting query is proportional to the consensus Mana held.
- Section 6.4 - Finalization: Finalization occurs when (among other criteria) a message is approved by nodes holding a certain fraction of the consensus Mana in the network.
The Mana specification depends on the following specification:
Each transaction must have an accessManaNodeID and a consensusManaNodeID field to determine which node to pledge these two types of Mana. Both of these fields consist of a node ID of the node that will receive each kind of Mana. Access Mana and consensus Mana do not have to be pledged to the same node.
Both kinds of Mana are exponential moving averages (EMA) of the base Manas (specifically, cMana is the EMA of base cMana, and aMana is the EMA of base aMana). An EMA is a type of moving average that places a greater weight and significance on the most recent data points. More precisely, the weighting for older data decreases exponentially in time, however, never reaching zero.
Even though the definition of an EMA should be unique (no matter to which function that you apply it), the general algorithm for the calculation of the EMAs—with the flexibility needed in our case—is not easily implementable. Thus, two different algorithms already customized for each type of Mana are provided in the present document.
We define the following parameters:
-
$\gamma$ - decay factor for base aMana. -
$\alpha$ - moving average factor for the cMana. -
$\beta$ - moving average factor for the aMana.
Additionally, we define four vectors that assign a real value to each node Id: the aMana vector, base aMana vector, cMana vector and base cMana vector. The base aMana vector and the base cMana vector are auxiliary vectors (meaning that they are needed to compute the aMana vector and the cMana vector, even though their values are not directly used in any of the modules). Due to the time dependance of the EMA (and also the base aMana function), the four vectors have a reference time to which they are associated.
The Mana vectors are updated in different occasions. Access Mana pledging happens when a transaction is booked on the ledger state. At the same time, entries of the nodes whose aMana is not being modified during the pledging are updated only with respect to the (possibly) newer time reference. In general, updates only due to time (without aMana pledging) happen whenever a node's aMana is being accessed by an external module (as the congestion control, for instance).
On the other hand, cMana is updated only relatively to the end of each epoch (see Section 4.2 - Timestamps). The reason behind this is that epochs are objective, i.e. all nodes agree on which epoch a certain message (or transaction) belongs to. Thus, since nodes agree (with high probability) about transactions with timestamps older than the end of the epoch plus TIMESTAMP_CUTOFF (see Section 4.2 - Timestamps), they will consequently agree—again, with high probability–about the cMana vector relative to these transactions.
Therefore, one can assume that the nodes in sync will (with high probability) agree on values of cMana relative to the set of transactions that have timestamp older than a fixed epoch in the past. On the other hand, aMana will capture recent fluctuations, but nodes are expected to have slightly different perceptions of this quantity.
The base cMana of a node nodeID at time time is defined as the sum over all unspent outputs at time time of transactions with consensusManaNodeID = nodeID. This means that, when an output is consumed, its cMana pledge is revoked and pledged to a (possibly) different node. See the example below:
Example 1:
Suppose transaction
Image 5.3.1: Illustration of outputs being consumed.
The update of the base cMana proceeds as follows:
- Add 300 to the base cMana state of the node
$N_z$ . - Subtract 100 from the base cMana state of the node
$N_x$ . - Subtract 200 from the base cMana state of the node
$N_y$ .
If a transaction
The total cMana of a node
- pledging of the cMana relative to a transaction with timestamp smaller than
$t_0$ . - pledging of the cMana relative to a transaction with timestamp larger than
$t_0$ . - updating the cMana to a time
$t_1>t_0$ without any new cMana pledging.
In the first case, the reference time of the cMana must not be changed, whereas in the second case, the reference time of the cMana must be changed to the timestamp of the transaction. This means that a node must never update the cMana to a point in the past (relatively to the last cMana calculated). The exact update procedure for each of the cases defined above are defined next.
Suppose that the last reference time is
-
a) Base cMana update. Just before updating the base cMana vector we must store it, since the last base cMana state (that we call
$\text{Old_Base_cMana}$ ) and the time relative to the last update are used later for the cMana calculations. This temporary vector can be deleted right after the cMana vector is updated.The update of the base cMana state goes as follows: if a new transaction with
$n$ inputs of values$x_1, x_2, \ldots, x_n$ pledges cMana to a node$N$ , then- we add
$\sum_{j=1}^{n}x_j$ to the base cMana of the node$N$ . - Each input
$I_j$ corresponds to some UTXO (and, consequently, to some transaction) stored in the ledger state. Then, we locate the node Id (let us say,$\text{Node}_j$ ) to whom the cMana relative to this output was pledged to in the past. Then, we subtract$x_j$ from the base cMana state of the node$\text{Node}_j$ , for each$I_j$ ,$j=1,\dots,n$ .
- we add
-
b) Pledging and revoking cMana. If the base cMana balance of node
$i$ (before we added this transaction) was$\text{Old_Base_cMana}(\text{Node}_i)$ and the new base cMana balance (after the addition of this transaction) is$\text{Base_cMana}(\text{Node}_i)$ , then we update the cMana vector adding to all nodes' entry the term:$$ (1-e^{-\alpha s})[\text{Base_cMana}(\text{Node}_i)-\text{Old_Base_cMana}(\text{Node}_i)] $$
The term above can be negative—since some nodes have their base cMana revoked—but the resulting cMana must not be. Notice that for most nodes (specifically, for all nodes that did not have their base cMana value changed) the value above is zero.
Suppose that the last reference time is
-
a) Base cMana update. Just before updating the base cMana vector we must store it, since the last base cMana state (that we call
$\text{Old_Base_cMana}$ ) and the time relative to the last update are used later for the cMana calculations. This temporary vector can be deleted right after the cMana vector is updated.The update of the base cMana state goes as follows: if a new transaction with
$n$ inputs of respective values$x_1, x_2, \ldots, x_n$ pledges cMana to a node$N$ , then- we add
$\sum_{j=1}^{n}x_j$ to the base cMana of the node$N$ . - Each input
$I_j$ corresponds to some UTXO (and, consequently, to some transaction) stored in the ledger state. Then, we locate the node Id (let us say,$\text{Node}_j$ ) to whom the cMana relative to this output was pledged to in the past. Then, we subtract$x_j$ from the base cMana state of the node$\text{Node}_j$ , for each$I_j$ ,$j=1,\dots,n$ .
- we add
-
b) Updating the cMana with respect to time. Suppose that the outdated cMana is
$\text{Old_cMana}$ . We update all cMana entries as follows:$$ \text{cMana}(\text{Node}_i)=e^{-\alpha s} \text{Old_cMana}(\text{Node}_i)+(1-e^{-\alpha s})\text{Old_Base_cMana}(\text{Node}_i) $$ where
$\alpha$ is the moving average parameter for the cMana.
Suppose that the last reference time is
$$
\text{cMana}(\text{Node}_i)=e^{-\alpha s} \text{Old_cMana}(\text{Node}_i)+(1-e^{-\alpha s})\text{Old_Base_cMana}(\text{Node}_i)
$$
where
The consensus Mana of a node is only calculated and stored relatively to the end of each epoch (see Section 4.2 - Timestamps). Only the values of the last MAX_STORED_EPOCHS epochs are stored. Thus, if
-
Update the cMana with respect to time, as described in section 4.3.3.1.3, from time
$t_{E-1}$ to$t_{E}$ -
For each transaction with timestamp in the interval
$[t_{E-1},t_{E})$ , perform (as described in section 4.3.3.1.1) the base cMana update and the pledge and revoking of cMana, while the reference time$t_{E}$ remains constant.
Additionally, we define the active consensus Mana of a node A in epoch E (i.e., relatively to time
Therefore, even if node node has consensus Mana greater than zero at a certain epoch ACMS(E).
Both calculations defined above (cMana and active cMana on an epoch TIMESTAMP_CUTOFF (see Section 4.2 - Timestamps) units of time after
The following data structures and functions must be defined:
-
UpdatecMana(epoch): updates the base cMana and cMana vectors from the end ofepoch-1toepoch, pledging and revoking the base cMana and cMana relative to all the relevant transactions. -
GetActiveConsensusMana(time): returns a mapping between all known nodes and their active cMana, calculated at the end of the epoch that containstime. -
ManaRank(lowerMana, upperMana, epoch): returns the node ID of the nodes with active cMana in the interval[lowerMana, upperMana], relative toepoch. Notice thatepochmust be, at least, the current epoch minusMAX_STORED_EPOCHSand, at most, the last epoch.
When an output is consumed and funds are consequently transferred, a certain amount of base aMana—dependent on the amount of funds and the age of the output—will be pledged to a node. This pledge is never revoked, as opposed to base cMana. Nevertheless, the base aMana of all nodes will decay over time, which means that all the calculations for aMana will be slightly different than for cMana. The base aMana at time
If this same output pledges aMana to a node
The base aMana of a node nodeID at time time is defined as the sum of the individual base aMana generated by all already consumed outputs accessManaNodeID = nodeID and timestamp smaller or equal than time. Nevertheless, as in the cMana case, computing the aMana using this equation can be excessively demanding. For that reason, the aMana shall computed recursively, updating it based on its last value. This update is customized for three different situations (here,
- pledging of the aMana relative to a transaction with timestamp smaller than
$t_0$ ; - pledging of the aMana relative to a transaction with timestamp larger than
$t_0$ ; - updating the aMana to a time
$t_1>t_0$ without any new aMana pledging.
In the first case, the reference time of the aMana must not be changed, whereas in the second case, the reference time of the cMana must be changed to the timestamp of the transaction. This means that a node must never update the aMana to a point in the past (relatively to the last aMana calculated). The exact update procedure for each of the cases defined above are defined next.
Suppose that the last reference time is
-
Base aMana pledging. Suppose that the new transaction consists of
$m$ inputs$I_1, I_2, \ldots, I_m$ of value$x_1, x_2, \ldots, x_m$ —respectively—and pledges aMana to a node$N$ . We update the base aMana of node$N$ by adding to its base aMana the value$$ d=e^{-\gamma s} \sum_{j=1}^{m}x_j(1-e^{-\gamma \delta_{j}}) $$ where
$\delta_{j}>0$ is the difference between$t$ and the timestamps of the transaction that generated$I_j$ and$\gamma$ is the decay factor. This value$d$ has to be temporarily stored, since it will be used in the aMana update. -
Pledging aMana. We update the aMana vector adding to node
$N$ 's entry the term:$$ \begin{cases}
\frac{e^{-\gamma s}-e^{-\beta s}}{(\beta-\gamma)e^{-\gamma s}}\beta d,\text{ if }\beta\neq\gamma;\ s \beta d,\text{ if }\beta=\gamma,\ \end{cases} $$ where the term$d$ is the same it was added when updating the base aMana vector.
Suppose that the last reference time is
-
Base aMana update with respect to time. Suppose that the last base aMana is
$\text{Old_Base_aMana}$ . We update all base aMana entries as follows:$$ \text{Base_aMana}(\text{Node}_i) = e^{-\gamma s}\text{Old_Base_aMana}(\text{Node}_i) $$
-
Base aMana pledging. Suppose that the new transaction consists of
$m$ inputs$I_1, I_2, \ldots, I_m$ of value$x_1, x_2, \ldots, x_m$ , respectively, and pledges aMana to a node$N$ . We update the base aMana of node$N$ by adding to its base aMana the value$$ d=\sum_{j=1}^{m}x_j(1-e^{-\gamma \delta_{j}}) $$ where
$\delta_{j}>0$ is the difference between$t$ and the timestamps of the transaction that generated$I_j$ and$\gamma$ is the decay factor. This value$d$ has to be temporarily stored, since it will be used in the aMana update. -
Updating the aMana with respect to time. We update all aMana entries as follows:
$$ \text{ aMana}(\text{Node}_i)=\begin{cases}
e^{-\beta s} \text{Old_aMana}(\text{Node}_i)+\frac{e^{-\gamma s}-e^{-\beta s}}{(\beta-\gamma)e^{-\gamma s}} \beta\text{Base_aMana}(\text{Node}_i),\text{ if }\beta\neq\gamma;\ e^{-\beta s} \text{Old_aMana}(\text{Node}_i)+s\beta\text{Base_aMana}(\text{Node}_i),\text{ if }\beta=\gamma,\ \end{cases} $$where
$\beta$ is the moving average parameter for the aMana and$\gamma$ is the base aMana decay factor. Notice that, here, the value of$\text{Base_aMana(Node}_i)$ used is the one already updated.
Suppose that the last reference time is
-
Base aMana update with respect to time. Suppose that the outdated base aMana is
$\text{Old_Base_aMana}$ . We update the base aMana entries as follows:$$ \text{Base_aMana}(\text{Node}_i) = e^{-\gamma s}\text{Old_Base_aMana}(\text{Node}_i) $$
-
Updating the aMana with respect to time. We update all the aMana entries as follows:
$$ \text{aMana}(\text{Node}_i)=\begin{cases}
e^{-\beta s} \text{Old_aMana}(\text{Node}_i)+\frac{e^{-\gamma s}-e^{-\beta s}}{(\beta-\gamma)e^{-\gamma s}} \beta\text{Base_aMana}(\text{Node}_i),\text{ if }\beta\neq\gamma;\ e^{-\beta s} \text{Old_aMana}(\text{Node}_i)+s\beta\text{Base_aMana}(\text{Node}_i),\text{ if }\beta=\gamma,\ \end{cases} $$where
$\beta$ is the moving average parameter for the aMana and$\gamma$ is the base aMana decay factor. Notice that, here, the value of$\text{Base_aMana(Node}_i)$ used is the one already updated.
The following data structures and functions must be defined:
-
GetAccessMana(): returns a mapping between all known nodes and their access Mana, calculated atcurrentTime(which means that the aMana is updated tocurrentTimewhen this function is called). -
UpdateaMana(transaction): whenever a transactiontransactionis added to the ledger state, it updates the aMana vector in order to add the aMana relative totransactionand to the (possibly) new reference time.
The Mana is an extension of the ledger state, hence its calculation depends on the ledger state perception of the node. Snapshotting is the mechanism that stores older ledger states and prunes unnecessary messages. Together with the ledger state, aMana and cMana vectors (and the reference time relative to them) are also saved, since a certain ledger state reflects a certain aMana and cMana distribution in the network. Thus, when a node joins the network, it will query other nodes to get their snapshot file, containing a aMana Snapshot Vector, a cMana Snapshot Vector, and two ACMS (one for each of the last two snapshotted epochs) that will be used as initialization data.
The following parameters will be used by default, and all nodes must know them. We do not have explicit rules to punish nodes that clearly do not use these parameters, but we expect that they would be eventually ignored, due to other implicit mechanisms. For instance, even if the Mana vectors of a certain node are significantly different from the other nodes' view (causing a divergence from the majority's opinion in the voting protocol), with a very high probability its opinion will not affect the final outcome of the voting. For other modules (like congestion control), a node with a significantly different perception of Mana will be blacklisted and will not harm the network. Thus, the nodes have plenty of incentives to follow the rules.
| Name | Type | Description | Observation |
|---|---|---|---|
DECAY |
float | decay factor for base aMana | Called |
C_MANA_EMA_COEFF |
float | moving average factor for the cMana | Called |
A_MANA_EMA_COEFF |
float | moving average factor for the aMana | Called |
Table 5.3.2: List of Parameters.
| Name | Type | Description |
|---|---|---|
object.cManaNode |
nodeID | Id of the node to which object's cMana was pledged |
object.amount |
double | Amount moved by object |
object.aManaNode |
nodeID | Id of the node to which object's aMana was pledged |
transaction.inputs |
list of inputs IDs | List of inputs consumed by transaction |
transaction.time |
time | Timestamp of transaction |
nodes |
list of nodeIDs | List of known nodes. |
epoch.finalTime |
time | Final time of epoch |
epoch.initialTime |
time | Initial time of epoch |
epoch.transactions |
list of TxIds | Set of transactions with timestamps in the interval [epoch.initialTime,epoch.finalTime) |
input.time |
time | Timestamp of the transaction that generated the output relative to input |
Table 5.3.3: Local Variables and Built-in Functions.
In this section, for the sake of clarity, we introduce an example of code of the functions defined above.
The function UpdateBasecManaTr(transaction) updates the vector basecMana, pledging and revoking the base cMana relative to a transaction transaction.
FUNCTION UpdateBasecManaTr(transaction)
basecMana[transaction.cManaNode] = basecMana[transaction.cManaNode]+transaction.amount
FOR input in transaction.inputs
basecMana[input.cManaNode] = basecMana[input.cManaNode]-input.amountThe function UpdatecManaTime(epoch) updates the vector cMana, changing its reference time from the end of epoch-1 to the end of epoch.
FUNCTION UpdatecManaTime(epoch)
n = epoch.finalTime-epoch.initialTime
FOR node in nodes
cMana[node] = exp(-C_MANA_EMA_COEFF*n)*cMana[node]
+(1-exp(-C_MANA_EMA_COEFF*n))*basecMana[node]The function UpdatecManaTr(epoch,transaction) updates the vector cMana, pledging and revoking the cMana relative to a transaction transaction.
FUNCTION UpdatecManaTr(epoch,transaction)
n = epoch.finalTime - transaction.time
FOR node in nodes
IF basecMana[node] != basecManaOld[node]
cMana[node] = cMana[node]+(1-(1-C_MANA_EMA_COEFF)**n)*(basecMana[node]-basecManaOld[node])The function UpdatecMana(epoch) updates the vectors cMana and basecMana, from the end of epoch-1 to epoch, pledging and revoking the base cMana and cMana relative to all the relevant transactions.
FUNCTION UpdatecMana(epoch):
UpdatecManaTime(epoch)
IF epoch.transactions != NULL:
FOR transaction in epoch.transactions:
basecManaOld = basecMana
UpdateBasecManaTr(transaction)
UpdatecManaTr(epoch,transaction)In this section, for the sake of clarity, we introduce an example of code of the functions defined above.
The function UpdateBaseaManaTime(t) updates the vector baseaMana, changing its reference time from lastUpdateTime to t.
FUNCTION UpdateBaseaManaTime(t)
n = t-lastUpdateTime
FOR each node i
baseaMana[i] = baseaMana[i]*exp(-DECAY*n) The function UpdateaManaTime(t) updates the vector aMana, changing its reference time from lastUpdateTime to t.
FUNCTION UpdateaManaTime(t)
n = t-lastUpdateTime
IF DECAY != A_MANA_EMA_COEFF
FOR each node i
aMana[i] = exp(-A_MANA_EMA_COEFF*n)*aMana[i]+(1-exp((DECAY-A_MANA_EMA_COEFF)*n))/(A_MANA_EMA_COEFF-DECAY))*A_MANA_EMA_COEFF*baseaMana[i]
ELSE
FOR each node i
aMana[i] = exp(-A_MANA_EMA_COEFF*n)*aMana[i]+ n*A_MANA_EMA_COEFF*baseaMana[i] The function UpdateBaseaManaTr(t,transaction) updates the vector baseaMana, pledging the base aMana relative to a transaction transaction.
FUNCTION UpdateBaseaManaTr(transaction)
FOR input in transaction.inputs
baseaMana[transaction.aManaNode] = baseaMana[transaction.aManaNode]+exp(-DECAY*(MAX(transaction.time,lastUpdateTime)-transaction.time))*input.amount*(1-exp(-DECAY*(transaction.time-input.time))) The function UpdateaManaTr(transaction) updates the vector aMana, pledging the aMana relative to a transaction transaction.
FUNCTION UpdateaManaTr(transaction):
n = lastUpdateTime-transaction.time
IF DECAY != A_MANA_EMA_COEFF
aMana[transaction.aManaNode] = aMana[transaction.aManaNode]+(exp(-DECAY*n)-exp(-A_MANA_EMA_COEFF*n))/(A_MANA_EMA_COEFF-DECAY))*A_MANA_EMA_COEFF*(baseaMana[transaction.aManaNode]-baseaManaOld[transaction.aManaNode])
ELSE
aMana[aManaNode(transaction)] = aMana[transaction.aManaNode]+exp(-DECAY*n)*DECAY*A_MANA_EMA_COEFF*(baseaMana[transaction.aManaNode]-baseaManaOld[transaction.aManaNode])
The function UpdateaMana(transaction) updates the vectors aMana and baseaMana, from lastUpdateTime to MAX(lastUpdateTime, transaction.time), pledging the base aMana and aMana relative to transaction.
FUNCTION UpdateaMana(transaction):
# if the tx is not old, add it and update the vector to t
IF transaction.time > lastUpdateTime:
UpdateBaseaManaTime(transaction.time)
UpdateaManaTime(transaction.time)
UpdateBaseaManaTr(transaction)
lastUpdateTime = transaction.time
# add a transaction in the past
IF transaction.time < lastUpdateTime:
baseaManaOld = baseaMana
UpdateBaseaManaTr(transaction)
UpdateaManaTr(transaction)