Simulation of a proof-of-work blockchain system. It provides a MAP/PH/1 queue, and an M/M/1 queue.
It is meant to be a computation model for the mathematical model developed by Quan-Lin Li, Jing-Yu Ma, Yan-Xia Chang, Fan-Qi Ma & Hai-Bo Yu in "Markov processes in blockchain systems". Find it at https://doi.org/10.1186/s40649-019-0066-1.
Furthermore, I have elaborated that this model would be more realistic if it took transactions fees into account. Miners prioritize transactions that offer larger fees. Thus, this script enables to select transactions in random order, or in fees order.
For more information about this work, please read the accompanying thesis.
usage: main.py [-h] [--seed SEED] [--mm1] [--mapph1] [--fees] [parameters_dir]
Simulate a proof-of-work blockchain system with a M/M/1 or MAP/PH/1 queue,
with fees or not.
positional arguments:
parameters_dir path to directory containing the parameters (README for
details)
optional arguments:
-h, --help show this help message and exit
--seed SEED seed to initialize the pseudo random generator
--mm1 run the simulation with M/M/1 queue
--mapph1 run the simulation with MAP/PH/1 queue
--fees Prioritize transactions according to offered fees
(otherwise, random order)
The queue is a two steps batch process :
- Infinite size waiting room. Service in random order.
- First step is called "transactions selection" or "block selection", the server randomly selects as many transactions as it can from the waiting room, with a maximum number of b transactions. The set of selected transactions is then called a "block".
- Second step is called "block broadcast". The server takes the block formed in the previous step and "mines" it. Once this step is done, the transactions definitely leaves the queue.
- The first and second steps are mutually exclusive and follow each other without interruption.
The queue comes in two version : M/M/1 (CLI option --mm1) or MAP/PH/1 (CLI option --mapph1). The "transactions
selection" step can be changed to prioritize transactions with higher fees (CLI option --fees). If the fees are
enabled, transactions are assigned a fee following a truncated normal distribution.
All parameters must be provided in a folder :
- Either named "parameters" in the directory where you run the script.
- Or the folder path is given as the first command line argument.
All parameters are defined in their own csv file with the name of the parameter as the filename plus the
extension .csv. For examples, see the parameters folder this repository contains.
Both versions of the queue requires the following parameters :
- b : The max number of transactions a block can contain.
- sigma : The time at which the software starts recording data. If less than one, it's considered to be a fraction of tau.
- tau : The time at which the simulation stops recording the arrival of new transactions.
- upsilon : The extra time after tau after which the queue shutdowns. If less than one, it's considered to be a fraction of tau. During that time, recorded transactions can still finish.
The ratio of fees / weight of the transaction is simulated by randomly selecting them from a sample :
- ratios : A column vector containing a sample of fees/weight ratios.
The M/M/1 queue requires the following parameters :
- lambda : The expected interarrival time.
- mu1 : The expected "transactions selection" duration.
- mu2 : The expected "block broadcast" duration.
The MAP/PH/1 queue requires the following parameters :
- C : Square matrix to generate the MAP process (non-absorbing transitions).
- D : Square matrix, same size as C, to generate the MAP process (absorbing transitions).
- omega : Vector of the stationary probabilities of the initial state of the MAP process.
- S : Square matrix to generate the PH process for the block selection.
- beta : Vector of the absorbing transitions probabilities for block selection (length equal to one side of S).
- T : Square matrix to generate the PH process for the block broadcast.
- alpha : Vector of the absorbing transitions probabilities for the block broadcast (length equal to one side of T).
Transaction arrivals, blocks selection and waiting room size are recorded from sigma to tau. Blocks broadcast are recorded from sigma to tau + upsilon.
All records are then aggregated into the following measures :
- The confirmation time : Which is also the sojourn time, is the time between the arrival of a transaction, and the time it leaves. From a blockchain point of view, it corresponds to the time between the broadcast of the transaction and the embedding of a block containing this transaction in the blockchain.
- The waiting time : The time between the arrival and the selection of a transaction.
- The service time : The time a transaction spends into the server.
- The block time : The time between successive blocks broadcast time.
- The block size : The number of transactions per block
- The waiting room size : The number of transactions in the waiting room.
- Unconfirmed transactions : The number of transactions unconfirmed per fee.
With the default parameters, simulating the queues takes from seven seconds to about two minutes.
| queue/selection | random | fees |
|---|---|---|
| M/M/1 | 7s | 120s |
| MAP/PH/1 | 40s | 140s |
From that it's very clear that sorting the transactions according to their fees has a high cost to the execution time. Investing time in optimizing the sorting method would be greatly beneficial. One could take advantage of the particular behaviour of the waiting room to do so :
- Top b transactions are removed with each block
- Order within top b transactions, or within the rest in not important
- Transactions are added much more frequently than they are removed.
- Transactions are added one by one
- Transactions are removed
bbyb
Furthermore, by creating a C addon, and handling the memory himself, one would be able to use a single array for the waiting room, and a single array for the server room. That would greatly reduce the memory management overhead.