transaction subset contribution

[SurfingNerd]

problem: currently each node sends each transaction to each node.
A transaction has only to be contributed by one node to get included.
first proposal would be to randomly pick transactions.
we have to work with transaction buckets for this achievement:

Propability of transactions inclusion for a full set:
x-Axis: propabillity value for a node
y-Axis: total chance for transaction inclusion
green graph: All 25 contribute - best case
Blue graph: Only 19 nodes contribute.
https://www.desmos.com/calculator/utqdkgtxc5

Propability of transaction inclusion:
x-Axis: number of Nodes
y-Axis: transaction inclusion: probability (1 = 100%)
p - slider: Chance of transaction proposal
https://www.desmos.com/calculator/tyal2zptps

With a transaction proposal chance of 17% we hit 99% transaction inclusion chance. and 97% if only 19 out of 25 nodes contribute.

Transaction Fee buckets

example:

A1 = Account 1
A2 = Account 2
A3 = Account 3

F1= Fee if 1 Gwei
F2= Fee of 2 Gwei
F3= Fee of 3 Gwei
FS= Service Transactions - Fee of 0 Gwei.

N1 = Nonce 1
N2 = Nonce 2
N3 = Nonce 3.

Transactions:
A1F3N1
A1F1N2
A1F1N3
A2F3N2
A2F2N1
A2F1N3
A3FSN1

Would result in the order:

FS

For Service Transactions (allowed transaction with gas fee of zero)
highest prioritized bucket.

• A3FSN1 - OK - high priority Service transaction.

F3:

• A1F3N1 - OK
• A2F3N2 - OK only after F2 (A2F2N2) was be proposed, or A2F2N2 gets replaced with higher Gas Fee, so it goes up to a higher value bucket.

F2:

• A2F2N1 - OK

F1:

• A1F1N2 - OK
• A1F1N3 - OK
• A2F1N3 - OK

Each RNG should pick from the highest gas fee bucket and contribute from those - until the bucket is empty.

Draft for the Data storage behind:

• Array of GasFeeBuckets, one for each different gas fee.
• each GasFeeBucket knows it's gas fee and associated accounts with transactions AccountBucket
• each AccountBucket knows it's gas fee, it's account and a sorted list of executable transactions (no Nonce Gap) and non executable transactions (because of Nonce Gap).

Q: Does the existing architecture already filter out hard Nonce Gaps (Pool vs Queue) "hard nonce gap": Not even a lower payed Transaction does exist. That would help performance wise.

Considerations:

• the sorting seems to be something very special - does it help to offload it to a sorter thread - can HBBFT do something meaning full in the meantime ? maybe signaling: https://doc.rust-lang.org/book/ch16-02-message-passing.html

This would automatically solve : #112

[SurfingNerd]

implemented a simpler algorithm, and merged in #118 to hbbft-performance

[dforsten]

Transaction subset contribution currently works like this:
Randomly take the number of the transaction queue length, and divide it by half of the active hbbft validators.

Empirically taking this amount of transaction has shown to be a good compromise between the size of the contribution and producing sufficient overlaps between contributions to produce blocks containing almost all of the transactions on each validator's transaction queue. Note that active validators are all connected with each other and will contain very similar transaction queues.

Transactions are selected by sender, all transactions for that sender with valid nonces are included in the contribution.
This may seem unfair, since the lucky sender will have all transactions included, but the order of senders is random.

When the block is ready to be assembled the contributions of all validator nodes are collected, flattened into a single list and duplicates eliminated.
Note that the order of nodes and their contributions is fixed, which means it is known ahead of time which validator's contribution will be included first. This may create opportunities for very sophisticated front-running schemes if the first validator is selectively including transactions.
A validator lucky enough to be chosen as first validator for an epoch can front-run transactions of his choosing.

[dforsten]

How the individual contributions are assembled is less critical, can be changed at any time.
The way the contributions are then assembled into a block however is critical, and is difficult to change after the fact.

All validator nodes are expected to produce a block with exactly the same transactions in exactly the same order.

To assure this each validator chosen for a hbbft epoch is given a fixed index which does not change for the duration of the epoch.

This means that a validator lucky enough be chosen as first validator (index 0) knows that his transactions will be included first in the block.

I recommend mitigating this vulnerability by randomly shuffling the transactions, using the random number generated for that block by hbbft to make the final order of transactions absolutely unpredictable.
Care has to be taken to not produce illegal transaction nonce ordering per sender.

[dforsten]

Since random reshuffling is part of the protocol we have to take care the solution is both deterministic and portable.
The Rust „rand“ module makes these guarantees for a subset of its functions:
https://rust-random.github.io/book/portability.html

We have to carefully select the function we use and seed it with the random number uniquely generated at block generation, also in a portable manner.

The downside of using Rust rand is that it is a language-specific implementation, when porting to other languages the exact same random number generator would have to be re-implemented in the target language.

Should we worry about that? Probably not, the alternative would be to come up with a reliable portable solution ourselves.

It is worth investigating how the Ethereum implementation is using random number generators and use the same method, ensuring that our use of deterministic random numbers is no less robust than the Ethereum client itself.

[dforsten]

Since the random number generated by the hbbft engine is unpredictable our requirements for the deterministic random generator are low. Rust „rand“ offers a good selection of algorithms with varying complexity:
https://rust-random.github.io/book/guide-rngs.html

Recommendation:
Choose the simplest algorithm with sufficient randomization quality and document well which algorithm was chosen. Evaluate if re-implementation is necessary or if we can trust the Rust implementation to produce identical results in future versions of the „rand“ crate.

[dforsten]

An interesting option is to use Keccak256 on the hbbft block’s random value as source of deterministic random numbers.