# Simulations

## Overview

### Approach

Unlike the Head protocol, it is cumbersome to come up with analytics baselines of the protocol since the traffic depends on the behaviour of many (impredictible) clients. We can however simulate a particular sequence of events and compare the time taken by a simulation of the protocol with the fastest possible execution of the same sequence on a typical unconstrained message broker. By doing so, we can compare the overhead of running the protocol and its effectiveness.

Instead of modelling behavioural patterns for clients, we use data from _the real world_ as it is more representative of potential use-cases (for it directly reflects existing behavioural patterns). Public blockchains provide a good source of such data, in particular Cardano for which it is also currently possible to track with some good level of confidence the transaction history of many kinds of wallets.

Current blockchains such as Cardano do not however generate important payment traffic on the layer one. Thus, we artificially compress the time and merge blocks at a given compression rate. This inflates the traffic while preserving the interactions between the clients. On the other hand, the number of wallets on such a blockchain is large (hundreds of thousands) and hard to simulate. We therefore also merge wallets by assigning them an identifier following a Round-Robin approach and cycling through a fixed list of identifiers.

Using such a dataset of real transactions, we have simulated the execution of the protocol using different parameters and analyzed the influence of each parameter on the actual throughput in comparison with the maximum possible throughput.

In addition, we also measure the time needed to settle each transaction of the simulation. The settlement time includes sending the transaction to the server, validating the transaction, notifying each recipients, and receiving an final acknowledgement of the server. If the transaction cannot be processed (because it will put either the sender or one of the recipients out of the payment window) then it is queued for later and no acknowledgement is sent. Instead, a snapshot is requested from the server to all relevant parties. The measured settlement time therefore include the time needed to perform snapshots when necessary.

### Simulated IO

// From Philipp

### Parameters

The simulation is run between multiple actors: one server and many clients. All clients are modelled in a uniform manner, though their behaviour is fully determined by an input dataset which reads as a schedule of events. The time is divided into slots and one or more events may occur at each slot. Clients may either:

- Go online and pull data from the server
- Submit a transaction

Clients always go online before submitting a transaction. From this schedule stems then many more interactions between clients and server according to the protocol. The simulation does not however model the rounds of transaction acceptance between clients and the server. That is, transactions are implicitely accepted when submitted provided that they do not exceed the payment window. If they do, they are queued by the server which also immediately request snapshots from all affected clients.

The server is asymmetric to clients in the sense where its resources (computational and network wise) are considered much larger than those of the clients. In particular we consider the server to:

- Have unlimited memory
- Be able to process up to 16 requests concurrently (through 16 distinct cores)
- Have up to 100MBits/s of read and write network bandwidth

As a matter of fact, early simulations have shown that the network usage between the server and all clients was rather low and far from being a limiting parameter. This is mainly due to the asymmetric nature of the setup. As a consequence, we have focused the simulations on different parameters which have proven to have a non negligeable influence on the results.

The following parameters are considered in this analysis:

- The **size of the payment window**, which is considered identical for each client.
- The **settlement delay**, which includes the total settlement time from the moment a snapshot is requested to the moment it is confirmed by the server.
- The **number of clients**, derived from the mainchain data using Round-Robin assignation of identifiers
- The **compression** of the chain, using different rates. At higher compression rates, the chain is more dense with more transactions at each slot.

## Dataset(s)

The dataset is comprised of data from the Cardano mainnet from [the block at slot 16992698 with id `e698128f`](https://explorer.cardano.org/en/block?id=e698128f8b4521266de8e31262c519f63f07e6e9f00637f927d0a49e12899228) to [the block at slot 28813234 with id `40462cb8`](https://explorer.cardano.org/en/block?id=40462cb8ddeb4c9035c55984ec847216de28ab1868ad7c3ea5c3f72870bc8581).

Every block is post-processed into a pipeline of several steps detailed in the next sections:

1. Identification: associating transactions inputs and outputs to clients.
2. Normalization: adjusting amounts to a stable currency.
3. Compression: merging slots and clients into smaller sets.

### Identification

For every block, we have extracted every transaction and mapped each input and output to a corresponding stake key, when possible. Note that this approach is only possible because:

1. On Cardano, addresses are made of two parts: a payment part (typically identified by a payment key) and a delegation part (optional, typically identified by a stake key).
2. All major Cardano wallets on the market (Daedalus, Yoroi, Adalite, Exodus...) currently use a single stake key per wallet for delegation.

We can therefore approximate wallets of the mainchain by looking at stake keys present in addresses. Besides, some addresses may be in an old format (carrying no stake key whatsoever) or simply, not contain any delegation part. Transactions containing such addresses are discarded.

> FOOTNOTE: On Cardano, old addresses (so-called 'Byron' addresses) are notoriously mainly used by exchanges and large parties who have either little interest in delegating or, haven't taken the time yet to migrate to the new address format. By discarding those old addresses, we are therefore able to discard most of the traffic generated by exchanges and mostly focus on traffic generated by end-users.

Cardano is a UTxO-based blockchain in which transactions inputs refer to a previous unspent transaction output. The reference is unique but does not contain addresses themselves. To resolve addresses corresponding to inputs, it is, therefore, necessary to maintain an index of all addresses seen in the past while processing blocks of the dataset (and therefore, to process blocks sequentially). This allows us to associate a stake key to both inputs and outputs.

As a result of this post-processing, we obtain a sequence of transactions where fields have been restricted to: an amount, a single stake key hash input, a list of stake key hashes outputs, a size in bytes and discrete timestamp (a.k.a. slot).

### Normalization

Crypto-currencies are still quite volatile and the market is in constant fluctuations. As a consequence, the intrinsic value of a particular crypto-currency is varying over time. In the case of Cardano, 1 ADA in July 2020 was worth up to 0.13 USD, whereas 1 ADA in February 2021 was worth up to 1.12 USD.

Our dataset spans over a long period and fiat currencies such as the US dollar are still the main reference when it comes to underlying value. We have therefore normalized amounts in the dataset using historical data of conversion rates from ADA to USD (with a daily precision).

That is, every amount in the dataset can be interpreted as if ADA was a currency fully pegged to the USD such that 1 ADA = 1 USD. Doing this makes the dataset agnostic to time and market fluctuations and allow to compare on the same level any payments of the dataset.

### Compression

As explained in the introduction, the current traffic observable on the Cardano mainchain is rather low. To keep payment interactions between wallets while still increasing the chain traffic, we compress the transaction history by merging multiple blocks as if they were processed at the same time. On Cardano, the time is divided into slots, and slots may or may not contain a block. When we say that the chain has been compressed by a factor of `N`, we say that we have only counted one slot for every `N` slots and considered all transactions between two compressed slots as if they all happened in that slot.

Note however that regardless of the compression rate, we always consider a dataset of the same duration: 591 slots -- which corresponds to the number of slots of the most compressed dataset. For a smaller compression rate, the dataset is truncated at 591 slots. This is necessary to compare simulations running over the same duration but with different traffic density.

### Vizualizations

At the highest compression rate, the final datasets contain `453858` transactions with the following distributions (amounts are given in normalized-ADA):

![][amounts-distribution]

Besides, in the context of the Tail protocol, we also assume that only transactions smaller than the payment window `W` are processed through the server. Although the theoretical maximum is `2*W`, it is only possible to receive or send a transaction of at most `W` after a snapshot; processing larger payments would require to first either send or receive other smaller payments to deviate from the snapshot synchronization point. Realistically, we expect the server to reject payments above `W` and have therefore discarded such payments.

Characteristics of the resulting datasets for various sizes of the payment window `W` are given in the table below:

| Payment Window | Average Transaction Amount | Median Transaction Amount | % of symmetric clients |
| --- | --- | --- | --- |
| 1000₳ | 140₳ | 45₳ | 95.8% |
| 2500₳ | 269₳ | 62₳ | 96.6% |
| 5000₳ | 420₳ | 69₳ | 96.9% |
| 7500₳ | 548₳ | 76₳ | 97.3% |
| 10000₳ | 644₳ | 80₳ | 97.6% |
| 12500₳ | 750₳ | 85₳ | 97.6% |
| 15000₳ | 834₳ | 85₳ | 97.9% |
| 20000₳ | 961₳ | 86₳ | 97.6% |
| 25000₳ | 1077₳ | 88₳ | 98.0% |
| 50000₳ | 1536₳ | 90₳ | 97.8% |
| ∞ | 25000₳ | 97₳ | 73.4% |

> FOOTNOTE: _symmetric_ means clients for which the received/sent (resp. sent/received) ratio is at most 3. Said differently, it corresponds to clients that are quite symmetric in their behaviour, they send as much as they receive.

## Variable: Compression

![][compression]

| Payment Window | Settlement Delay | Number Of Clients | Compression | Max TPS | Actual TPS | Avg. Conf. Time |
| --- | --- | --- | --- | --- | --- | --- |
| 10000 | 120 | 1000 | **1000** | 6.194 | 4.745 | 1.562 |
| 10000 | 120 | 1000 | **2500** | 22.22 | 14.36 | 2.097 |
| 10000 | 120 | 1000 | **5000** | 54.71 | 28.01 | 2.951 |
| 10000 | 120 | 1000 | **10000** | 197.4 | 49.97 | 3.327 |
| 10000 | 120 | 1000 | **11000** | 241.4 | 52.29 | 3.424 |
| 10000 | 120 | 1000 | **12000** | 273.9 | 55.65 | 3.454 |
| 10000 | 120 | 1000 | **13000** | 310.7 | 58.88 | 3.545 |
| 10000 | 120 | 1000 | **14000** | 375.3 | 62.78 | 3.480 |
| 10000 | 120 | 1000 | **15000** | 413.9 | 63.59 | 3.587 |
| 10000 | 120 | 1000 | **16000** | 480.5 | 65.29 | 3.561 |
| 10000 | 120 | 1000 | **17000** | 539.7 | 68.08 | 3.557 |
| 10000 | 120 | 1000 | **18000** | 602.5 | 71.84 | 3.440 |
| 10000 | 120 | 1000 | **19000** | 659.8 | 70.91 | 3.626 |
| 10000 | 120 | 1000 | **20000** | 717.8 | 73.47 | 3.524 |

#### Interpretation(s)

The larger the traffic, the larger the throughput as we would normally expect. What's interesting to notice here is the almost linear growth of the throughput in the case of the simulated Tail vs the quadratic growth of the maximum throughput.

How to interpret this? The tail does not scale well with the number of transactions? ¯\\_(ツ)\_/¯

## Variable: Payment Window

![][payment-window]

| Payment Window | Settlement Delay | Number Of Clients | Compression | Max TPS | Actual TPS | Avg. Conf. Time |
| --- | --- | --- | --- | --- | --- | --- |
| **1000** | 120 | 1000 | 20000 | 601.5 | 37.95 | 7.374 |
| **2500** | 120 | 1000 | 20000 | 661.7 | 49.11 | 5.512 |
| **5000** | 120 | 1000 | 20000 | 693.4 | 58.43 | 4.587 |
| **7500** | 120 | 1000 | 20000 | 709.3 | 68.32 | 3.805 |
| **10000** | 120 | 1000 | 20000 | 717.8 | 73.47 | 3.524 |
| **12500** | 120 | 1000 | 20000 | 725.0 | 77.87 | 3.366 |
| **15000** | 120 | 1000 | 20000 | 729.8 | 85.61 | 2.946 |
| **20000** | 120 | 1000 | 20000 | 735.4 | 97.53 | 2.492 |
| **25000** | 120 | 1000 | 20000 | 739.4 | 105.1 | 2.254 |
| **30000** | 120 | 1000 | 20000 | 742.4 | 118.7 | 1.985 |
| **40000** | 120 | 1000 | 20000 | 746.7 | 128.6 | 1.805 |
| **50000** | 120 | 1000 | 20000 | 749.5 | 144.1 | 1.546 |

#### Interpretation(s)

Intuitively, the higher the payment window the less frequent are snapshots, which has a positive impact on the transaction throughput. Note that the maximum throughput varies with the payment window here because changing the payment window also changes the dataset. Using lower values for the payment windows discards more transactions from the dataset resulting in less overall traffic.

It is interesting to compare the evolution of the ratio `actual tps / max tps` in this case:

| 1000 | 2500 | 5000 | 7500 | 10000 | 12500 | 15000 | 20000 | 25000 | 30000 | 40000 | 50000 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0.0631 | 0.0742 | 0.0843 | 0.0963 | 0.1024 | 0.1074 | 0.1173 | 0.1326 | 0.1421 | 0.1599 | 0.1722 | 0.1923 |

The ratio is indeed increasing showing that the actual throughput not only increases because more transactions are included but mainly because of bigger payment windows.

## Variable: Settlement Delay

![][settlement-delay]

| Payment Window | Settlement Delay | Number Of Clients | Compression | Max TPS | Actual TPS | Avg. Conf. Time |
| --- | --- | --- | --- | --- | --- | --- |
| 10000 | **30** | 1000 | 20000 | 717.8 | 172.9 | 1.194 |
| 10000 | **60** | 1000 | 20000 | 717.8 | 115.1 | 2.088 |
| 10000 | **90** | 1000 | 20000 | 717.8 | 87.60 | 2.938 |
| 10000 | **120** | 1000 | 20000 | 717.8 | 73.47 | 3.524 |
| 10000 | **150** | 1000 | 20000 | 717.8 | 63.66 | 4.361 |
| 10000 | **180** | 1000 | 20000 | 717.8 | 56.81 | 4.724 |
| 10000 | **210** | 1000 | 20000 | 717.8 | 51.40 | 5.171 |
| 10000 | **240** | 1000 | 20000 | 717.8 | 49.31 | 5.429 |
| 10000 | **270** | 1000 | 20000 | 717.8 | 47.52 | 5.740 |
| 10000 | **300** | 1000 | 20000 | 717.8 | 46.51 | 6.131 |
| 10000 | **450** | 1000 | 20000 | 717.8 | 37.13 | 7.384 |

#### Interpretation(s)

The settlement delay is one of the parameters with the biggest impact on the overall throughput. Long settlement delays mean that clients are unable to send payments for a long-time, but also to receive payments!

It is interesting to notice the exponential shape of the curve showing how rapidly the delays impact the throughput while having less and less impact as the value increases.

## Variable: Number Of Clients

![][number-of-clients]

| Payment Window | Settlement Delay | Number Of Clients | Compression | Max TPS | Actual TPS | Avg. Conf. Time |
| --- | --- | --- | --- | --- | --- | --- |
| 10000 | 120 | **1000** | 20000 | 717.8 | 73.47 | 3.524 |
| 10000 | 120 | **2000** | 20000 | 718.5 | 118.1 | 3.314 |
| 10000 | 120 | **3000** | 20000 | 718.6 | 169.8 | 3.213 |
| 10000 | 120 | **4000** | 20000 | 718.6 | 200.6 | 3.173 |
| 10000 | 120 | **5000** | 20000 | 718.7 | 223.5 | 3.131 |
| 10000 | 120 | **6000** | 20000 | 718.7 | 245.2 | 3.078 |
| 10000 | 120 | **7000** | 20000 | 718.7 | 261.2 | 2.977 |
| 10000 | 120 | **8000** | 20000 | 718.7 | 275.3 | 2.932 |
| 10000 | 120 | **9000** | 20000 | 718.8 | 292.0 | 2.794 |
| 10000 | 120 | **10000** | 20000 | 718.8 | 297.8 | 2.789 |
| 10000 | 120 | **11000** | 20000 | 718.8 | 306.8 | 2.730 |
| 10000 | 120 | **12000** | 20000 | 718.7 | 316.3 | 2.679 |
| 10000 | 120 | **13000** | 20000 | 718.8 | 325.5 | 2.574 |
| 10000 | 120 | **14000** | 20000 | 718.7 | 331.6 | 2.564 |
| 10000 | 120 | **15000** | 20000 | 718.7 | 334.1 | 2.482 |

#### Interpretation(s)

Perhaps surprising at first, but increasing the number of clients (while keeping the same overall traffic) has a very positive effect on the throughput. The increasingly larger amount of clients reduces the interactions between and dependencies onto other clients.

That is, if for a given number of clients, a client is on average interacting with `n` other clients then it has a chance to impact these `n` clients when performing a snapshot. With a larger number of clients `n` gets also bigger and therefore, the chances of a client to impact another gets smaller.

In a context where a server has an unlimited amount of resources and can handle an unlimited amount of clients, it would be possible to asymptotically approach the max throughput for a very large number of clients.

This suggests that Tails are a better fit when the number of participants becomes larger (which so far is in adequation with its design goal). For smaller groups, the Hydra Head protocol is likely a better fit.

[payment-window]: https://i.imgur.com/FHBBqGs.png

[settlement-delay]: https://i.imgur.com/8jpA7na.png

[number-of-clients]: https://i.imgur.com/ggeKX7v.png

[compression]: https://i.imgur.com/qrvzek1.png

[amounts-distribution]: https://i.imgur.com/rLAOzoI.png