# Block-STM

## Prior Works

- [block-stm paper](https://arxiv.org/abs/2203.06871)
- [sei-chain implementation](https://forum.sei.io/t/optimistic-concurrency-control/28)

## Our Contribution

https://github.com/crypto-org-chain/go-block-stm

- A new implementation as a standalone golang package
- Can be hooked into cosmos-sdk with [minimal changes](https://github.com/crypto-org-chain/cosmos-sdk/pull/205)
- Multiple optimisations on cosmos-sdk for better parallel execution performance

## Benchmark Results

> Each op executes a block with `5000` erc20 transfer transactions, with `100` unique sender accounts distributed randomly.

| Workers | ns/op | |
| --------------------- | ----------- | ---- |
| Sequential | 637,690,938 | 1x |
| Block-STM, 8 workers | 137,451,953 | 4.6x |
| Block-STM, 16 workers | 122,207,241 | 5.2x |

[code](https://github.com/crypto-org-chain/cronos/blob/90ac130f7c99e0e62eefafbee9b799b1ba3f8606/app/bench_test.go#L237)

## Overview

1. Transactions are executed in parallel optimistically
2. The execution results are validated to detect conflicts
3. If validation fails, transactions are re-executed
4. The end results are identical to a sequential execution

## Overview (cont)

- Transparent to users
- Application logic should try to avoid shared state

## Accidentical State Sharings

- Fee Collection
- [Our refactoring](https://github.com/crypto-org-chain/cosmos-sdk/pull/237) to make it work with parallel execution
- A few other cases in ethermint

## Cache

- Contend for a `Mutex` in read operations
- we removed the read cache from the cachekv stores, only buffer writes.

## Implementation

### Top-Level Scheduling

- [Executor loop](https://github.com/crypto-org-chain/go-block-stm/blob/main/executor.go#L44)

### Multi-Version Data Structure

[code](https://github.com/crypto-org-chain/go-block-stm/blob/main/mvdata.go)

* Concept: `map[Key]map[TxnIndex]Value`

// Read returns the value and the version of the value that's less than the given txn.
// If the key is not found, returns `(nil, InvalidTxnVersion, false)`.
// If the key is found but value is an estimate, returns `(nil, BlockingTxn, true)`.
// If the key is found, returns `(value, version, false)`, `value` can be `nil` which means deleted.
func (d *GMVData[V]) Read(key Key, txn TxnIndex) (V, TxnVersion, bool) {

### Estimate Mark

- Transaction that's aborted for failed validation will mark the keys that's touched with a "ESTIMATE" mark.
- A transaction that reads a "ESTIMATE" mark will block and wait for the depending transaction to finish.

### Transaction State Machine

stateDiagram-v2

	[*] --> ReadyToExecute
	ReadyToExecute --> Executing: TrySetExecuting()
	Executing --> Executed: SetExecuted()
	Executing --> Suspended: Suspend(cond)\nset cond
	Executed --> Aborting: TryValidationAbort(incarnation)
	Aborting --> ReadyToExecute: SetReadyStatus()\nincarnation++
	Suspended --> Executing: Resume()