COTI’s Algorithm Simulation Explained
Many of our COTI community members have wrote in asking us how we created the DAG simulation. Our CTO, Dr. Nir Haloani, explains the full details of the simulation and how it came about below.
Introduction
The goal of this simulation is to present how the Trustchain algorithm works. It demonstrates the functioning of the algorithm in many ways, but excludes network propagation, storage and cryptography features. The DAG in the simulation consists of precomputed transactions, and we can see its growth in line with various parameters and Trust Score distributions.
What is the COTI Web Simulation?
Our simulations are presented in 2D and 3D format. The simulation itself is based on a 3D force-directed graph, which is an open source module used to plot the DAG. Data is synced to the module through real data that is generated offline and resynced randomly to the plugin. The idea is to simulate how the consensus and attachment algorithms work.
In the 2D simulation, all transactions in the Cluster are presented as circles connecting to each other to form a lattice. The transactions are plotted on an axis of Trust Score vs time. New transactions are added at a rate of . Changing this parameter therefore changes the rate at which transactions occur in the simulation. An example of the 2D simulation is shown in the figure below. In this case =10.
As shown in the above figure, transactions change color depending on their confirmation status. When transactions are first added to the Cluster they are orange. When a transaction is verified it changes to blue. Finally, when a transaction reaches the confirmation trust threshold it turns black. As the simulation continues, there will be a wave of color changes corresponding to verification and confirmation events taking place in various parts of the network. Since transactions from low trust users take longer to reach a trust threshold, we expect confirmation color transitions to have a slant, with fewer low trust transaction confirmations and higher trust transaction confirmations. As shown in the figure below, zooming in on transactions reveals their Trust Score (TS). Hovering over outgoing transactions highlights the Trustchain in red (for confirmed transactions).
Unlike the 2D simulation, transactions in the 3D simulation are not tied to a fixed 2D grid but are free to propagate freely. When one transaction validates another, it forms a link holding the transactions together; otherwise, transactions that are not linked repel one other and move around until they become evenly spaced out.
As in the 2D simulation, transactions change colors depending on their confirmation status, following the same color scheme as the 2D simulation. In addition to transactions being color labeled according to their confirmation status, transactions are also highlighted according to their Trust Score. As shown in the figure below, clicking on a transaction will highlight the Trustchain that confirmed it in red.
How Did We Make It?
Notation
Source: A source is a transaction that has attached to the Cluster and validated another transaction, but has not yet been validated itself. Validation involves verifying that a transaction is valid (i.e. properly signed).
Attachment: When a user links their transaction to other transactions in the Cluster.
Validated transaction: A transaction with at least one other transaction attached to it.
Confirmed transaction: A transaction that has acquired enough cumulative trust to earn network merit.
DAG: Transactions are connected to previous transactions in a unidirectional feed forward manner, which creates a directed acyclic graph (DAG).
The crux of the simulation
The crux of the simulation consists of the Source Selection Algorithm, which defines how a new transaction in the network selects a source to validate. Important considerations are new transaction Trust Scores and how long they have been waiting to be validated.
What happens first is that the new transaction receives a list of all the sources in the Cluster with a Trust Score within its neighborhood. The size of the neighborhood is defined by the parameter , which expresses the permitted difference in Trust Score (as a fraction of 100) between the new transaction and the sources it can connect to in the validation process. From this neighborhood of permitted sources, the new transaction chooses two sources to validate. They are weighted by the amount of time the sources have been waiting, so that the sources which have been waiting longer have a higher probability of being validated.
Once the new transaction has validated two sources, it attaches to the Cluster and becomes a source itself. The amount of time it takes for a new transaction to validate the sources and perform the required proof of work is controlled by the parameter Δt.
These are the inner workings of the DAG simulation for any single, new transaction that joins the Cluster. In reality, there are many new transactions per second that follow the exact procedure that was previously discussed. In the simulation, the number of new transactions per second is controlled by the parameter .
Naturally, there are some edge cases that must be considered, as the network must begin at some point in time. The initial transactions (i.e. the genesis transactions) represent the first stages of the network when the first COTIs are exchanged for other currencies. The DAG must grow from these genesis transactions, so if there are more new transactions than sources, a new transaction can join the Cluster by validating one transaction rather than two. This allows the Cluster to grow without compromising on security. In order to simplify the mathematical analysis, the simulation assumes that Trust Scores are randomly distributed and that the network is not under attack by malicious parties.
Mathematics underlying the attachment algorithm
Transaction attachment flow chart
The following is a flowchart illustrating the attachment algorithm for new transactions that need to attach to the Cluster.
Conclusion
“The mathematical framework which COTI has utilised is not only theoretically sound but was rigorously tested via simulation. The assumptions made about the proof of work and transaction arrival rate process were reasonable given the Cluster (directed acyclic graph) and the change in time. The simulation performed showed in log-scale that transaction confirmation delay is reduced over time given an increase in the Trust Score. This remarkable breakthrough strengthens the hypothesis that a trust-based algorithm can increase the transaction rate throughput with significantly lower risk.”
–Obakeng Moepya, PhD, Machine Learning Fraud Detection specialist
“The series of empirical investigations that make use of the presented simulation reassure our assumptions for algorithm choices and optimization of real world Cluster performance. The mathematical framework of the simulation clearly shows the impact of internal and external parameters on the performance and throughput characteristics of COTI’s Cluster. This provides, without loss of generality, conclusive evidence that the Cluster is scalable.”
–Nir Haloani, PhD in Applied Mathematics
