# Benchmarking tool for Typhon

## Purpose of this tool
Determine how good Typhon is with respect to other state-of-the-art protocols, starting with Tendermint.

## Sub-tasks

1. Study how recent indidivual projects have evaluated their algorithms. Also survey existing tools in more depth and find out what good practices are.
2. Determine what it is exactly that we *can* benchmark
3. Decide what it is exactly that we *want* to benchmark
4. Create a set of concrete research questions based on what we want
5. Determine concrete set of requirements and properties for our tool that will enable us to answer those research questions
7. Design the tool (perhaps using some external project as foundation )
8. Implement the tool
9. Verify the tool by implementing existing consensus algorithm and compare it to published results

---

## 1. Evaluation methods other papers

### 1.1) Narwhal and Tusk [1]

#### Physical infrasturcutre set-up
- Performed experiments via AWS
- across 5 different AWS regions
- 10 Gbps of bandwidth available
- 32 virtual CPUs (16 phyical core) on a 2.5 GHz
- 128 GB memory

#### Experiment parameters
- 4 validators running one worker
- batch size is 500KB
- block size is 1KB
- transaction size is 512B
- submitting transacations at fixed rate for 5 minutes

#### Metrics
- Latency:
- start time: client submits transcation;
- end time: transaction is commited by the leader that proposed it as part of a block
- Throughput: transactions per second that validator processes

#### Protocol implementation details
- Language: Rust
- Networking tool: Tokio
- Database tool: RocksDB
- P2P connections: TCP

#### Indication of cost
- ...

#### Pros
- (Rust) code available
- set-up already there (saves time)
- access to authors
- both local and global runs
-
#### Cons

- poor documentation
- low number of validators (scalability not tested)
- no distributed tracing

### 1.2) Tendermint [2,6]

#### Physical infrastructre set-up
- Performed experiments via AWS
- across 16 different AWS regions
- collocate all clients in a single AWS server to centralize all measurements in a single location
- spread validators evenly over AWS regions

#### Experiment parameters
- block size: 20MB
- mempool size: 1GB
- sending and receiving rates: 5000 KB/s
- intervals that govern gossip: 100ms
- validator nodes: 16,32,64,128
- clients: 1536
- clients are evenly distributed among validators
- hops (min, avg, max) for communication: (1,2,3)
- transaction injection rate: depends on the speed of transaction

#### Metrics
- latency:
- the difference of timestamps of two successive blocks (block latency)
- the time it takes for a client transaction to be ordered, from its submission to the delivery of the block that includes it (transaction latency)
- throughput: transactions per second that validator processes

#### Protocol implementation
- language: golang
- block latencies include 1s artificial timeout commit delay (to collect as many votes as possible endorsing the commited block)
- clients are delivered the sequence of blocks commited by Tendermint and they compute the latencies and throughput
- application takes snapshots periodically of its state and persists to disk
- all clients submit 1KB transactions to validators evently in a closed loop (clients submit a transaction to a given validator wait until transaction was included in a block commited by Tendermint, and then submit a new transaction to the same validator.)
- clients submit 1KB transactions until 30 blocks of transactions are commited.

#### Indication of cost
- ...
-

#### Pros
- results are well discussed (easy to verify our own implementation)
- set-up it pretty clear
- different types of fault assumptions tested (crash/byzantine)
- access to developers

#### Cons
- no code available (perhaps ask the authors?)
- no data on the tool itself (is it modular/extendible/?)
- all clients on one machine (central point of statistician -> not good for testing several sub-componetents)
- language is golang (ie not rust)
- nothing on message (sizes/format/anything?)

### 1.3) Hotstuff [3]

#### Physical infrastructre set-up
- uses amazon EC2
- 16 vCPUs (8000 processors, turbo CPU clock speed up to 3.4 GHZ)
- each replica on a single VM instance (16 cores per replica)

#### Experiment parameters
- batch sizes vary (100, 400, 800)
- injection rate varies
- 4 replicas of which 1 fails (f=1)
- varying request/response load sizes (128-1024 bytes) to test scalability
- a view change triggered every 1k decisions
-

#### Metrics
- client side: latency
- server side: latency + throughput

#### Protocol implementation
- use TCP
- use secp256k1 for digital signatures
- leader replacement (view change):
- written in C++

#### Indication of cost

#### Pros
- takes marshalling/unmarshalling (but to what degree?) into account
- code availability (https://github.com/hot-stuff/libhotstuff)

#### Cons
- not any indication of throughput
- not very elaborate explanation. A lot of unclarities (for example on latency measurements)
- failed to throttle the bandwidth
- written in c++

### 1.4) Mir-BFT [4]

#### Physical infrastructure set-up

#### Experiment parameters

#### Metrics

#### Protocol implementation

#### Indication of cost

#### Pros

#### Cons

### 1.5) PaxiBFT Framework [5]

#### Physical infrastructre set-up
- 2 vCPU
- how many AWS instances?
- LAN deployment
- WAN deployment (4 different regioas)

#### Experiment parameters
- validator sizes varies (between 4-20)
- client sizes varies (up to 90)

#### Metrics
- latency
- throughput

#### Protocol implementation
- language: Go
- config file is distribute among all validators (in JSON format)
- relies on [Paxi](https://github.com/ailidani/paxi) framework for a lot of things

#### Indication of cost

#### Pros
- code available
- available documentation on the framework
- has modularity
- is pretty elaborate (has components such as network communication, state machine of a key-value store, client API and multiple types of quorum systems.)
-

#### Cons
- Some important aspects are unclear (e.g., unclear whether benchmarker is on every replicate or on a single machine)
- no accces to authors (yet)
- not in rust

### Synthesis
Best to build on Facebook's Narwhal repository. The code is clean and easy to extend, the set-up is clear, it's in Rust, and it is flexible. We should however the testing more realistic and also allow distributed tracing for sub-processes.

### Notes
- Evaluating BFT protocols in the presence of Byzatine faults is still an open questions [1]. So we will have to think about what Byzantine behavior we will consider to confuse the protocols.

## Sub-task 2: What can we benchmark?
In theory, we can benchmark everything that triggers a (potential) state change by means of a message exchange. Therefore, we created a layered architecture that shows potential messaging in this hackMD on Anoma's [layered architecture]((https://hackmd.io/_LxxCSAmRwW28fNquMW81A)) and the typhon's [specs](https://specs.anoma.net/master/architecture/consensus/typhon.html).

## 3. What should we benchmark?
There are a lot of different consensus algorithms that use (a combination of) different mechanisms. The primary goal of the tool is therefore to create a sub-set of these consensus algorithms with their modular components and compare their messaging schemes. To limit the scope, we will assume that transactions are created and injected in the network by some nodes. To be more concrete, we are mainly interested in comparing Tendermint with Typhon from messaging perspective for different mempool, consensus and execution layer designs. For this we need different metrics.

#### Performance-based metrics
* throughput
* latency
* block distribution time
* bock verification time
* various block size
* discovery cost
* scalability (measure as the changes of performance metrics for increasing the number of nodes of the network)

#### Security-based metrics
<!-- * passive attack resistance
* active attack resistance -->
* Fault tolerance (ability to find consensus and complete transaction with sub-optimal network topology)
* DoS attack resistance
* Eclipse attack resistance
* Frontrunning attack resistance
* MEV?

#### Misc
* heterogeneity: meet requirements under heterogenous network conditions
* modularity: the ability test several sub-components of the protocol
* safety: identified with the Integrity, Validity and Finaly properties
* liveness: identified with the termination property

## 4. What are relevant research questions?

#### Main research question
The main goal of the tool will be to compare how good Typhon is compared to state-of-the-art algorithms. Therefore, the main research questions is as follows: *How does Typhon compare from a performance and security perspective with state-of-the-art consensus algorithms?*

#### *Some* relevant sub-questions
- What are some performance and security requirements for consensus algorithms?
- How costly is message exchange in Typhon in comparison with other consensus mechanisms? More precisely, how costly is:
- broadcasting of transactions
- retrieving transactions
- ordering transactions
- How scalabel is Typhon in comparison to other works when:
- number of clients increase
- number of transactions increase
- number of validators increase
- number of workers increase
- How secure is Typhon in comparison to other works when:
- validators behave maliciously
- crash failures
- honest validators are slow

## 5. Create concrete requirements for benchmarking tool

#### Functional requirements
- measure how fast we can distribute transactions
- measure how fast execution engines can retrieve transactions
- measure how fast we can order transactions
- measure how long it takes before we can do garbage collection
- measure how fast can we create certificate of availability
- use system logs to understand the behavior of the relevant actor by tracing:
- transactions
- erasure code packages
- primary nodes
- work nodes
- executors
- clients
- allow different types of (random) behavior, so make nodes byzantine if needed.
- run benchmarks both locally and globally
- write node behavior and protocols in rust

#### Non-functional requirements
- relevant: the benchmark workload should be representative of the typical operations performed in the problem domain
- portable: it should be easy to implement the benchmark both on and for different systems (so that we can expand it in the future)
- scalable: the benchmark should be applicable to different system sizes
- modular: the benchmark tool should enable benchmarking and improving several sub-components of a distributed algorithm
- simple: the benchmarker, workload and especially the results should be understandable

## Design the architecture of the tool

Created a reference architecture that can be run locally using the following design patterns:
- factory: to allow the creation of several sub-components
- adaptor: to allow sub-components of different algorithms to fit in
- strategy: to encapsulate different behavior that can be used (e.g., broadcasting behavior)
- observer: to see when events are triggered and to log results every x steps (note that this is not sufficient for correct tracing in a distributed manner).

---
## Sources
[1] Danezis, G., Kokoris-Kogias, L., Sonnino, A., & Spiegelman, A. (2022, March). Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. In Proceedings of the Seventeenth European Conference on Computer Systems (pp. 34-50).

[2] Buchman, E., Kwon, J., & Milosevic, Z. (2018). The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938.

[3] Yin, M., Malkhi, D., Reiter, M. K., Gueta, G. G., & Abraham, I. (2018). HotStuff: BFT consensus in the lens of blockchain. arXiv preprint arXiv:1803.05069.

[4] Stathakopoulou, C., David, T., & Vukolic, M. (2019). Mir-bft: High-throughput bft for blockchains. arXiv preprint arXiv:1906.05552.

[5] Alqahtani, S., & Demirbas, M. (2021, August). Bottlenecks in blockchain consensus protocols. In 2021 IEEE International Conference on Omni-Layer Intelligent Systems (COINS) (pp. 1-8). IEEE.

[6] Cason, D., Fynn, E., Milosevic, N., Milosevic, Z., Buchman, E., & Pedone, F. (2021, September). The design, architecture and performance of the Tendermint Blockchain Network. In 2021 40th International Symposium on Reliable Distributed Systems (SRDS) (pp. 23-33). IEEE.

[7] Ng, H. (2020). Distributed Consensus: Performance Comparison of Paxos and Raft.

[8] De Angelis, S. (2018). Assessing security and performances of consensus algorithms for permissioned blockchains. arXiv preprint arXiv:1805.03490.

[9] Bes, R. (2021). Benchmarking Distributed Database Performance and Dependability under Partial System Failures.

https://github.com/salemmohammed/PaxiBFT
https://github.com/ailidani/paxi
https://github.com/facebookresearch/narwhal
https://scholarspace.manoa.hawaii.edu/bitstream/10125/80070/0586.pdf