...by Daniel Szego
"On a long enough timeline we will all become Satoshi Nakamoto.."
Daniel Szego

Sunday, September 23, 2018

Fair ordering of transactions in Hashgraph

The Hashgraph virtual voting algorithm provides a fair ordering of the events in the following sense:
- Fair access: means that no individual can stop a transaction from entering the system,
or even delay it very much.
- Fair timestamps: A consensus timestamp that reflects when the majority of the network
members received that event. This consensus timestamp is “fair”, because it is not possible for a
malicious node to corrupt it and make it differ by very much from that time.
- Fair transaction order: A common order of the events that is to be seen exactly the same way after virtual voting by each node and that can not be influenced by individual nodes, or the minority of the nodes. 

There is one problem however, the mathematical side of the algorithms and the proofs guarantee a fair ordering of the events and not the transactions them self. Certainly, if each event contains at most one transaction, than fair ordering of the events equals with the fair ordering of the transactions. If however on event can contain multiply transactions, the situation is not so simple. A node creating multiply transaction for an event can game the order of the transactions in a certain event and even between multiply events. 

To avoid unfair ordering of transactions in an event an improvement might be to define an order and a timestamp of the transactions inside a node. On such an order might be to consider the hashes of the transactions in an event in a increasing order, like:

sha256(Tr_1), sha256(Tr_2), ... sha256(Tr_k) in an increasing order, where {Tr_1, Tr_2, ... Tr_k} is the set of transactions associated to an event. 

It does not really matter how an individual node orders the transactions in an event physically, the events are always regarded as the ordering of the transaction hashes. As a consequence it can not be gamed by the individual nodes unless transactions or signatures for transactions are forged that is usually pretty difficult because of the cryptographical algorithms.

Similarly a global order of the transactions can be defined as well:
- the global order of the events is provided by the Hashgraph algorithms.
- the order of the transactions in an event is provides by the ordering of the hashes. 

Based on the global order and the Hashgraph algorithm for attaching a timestamp for each event, the transactions can be associated by a timestamp as well:
- if an event contains only one transaction, the transaction timestamp equals with the timestamp of event. 
- if an event contains several transactions, the transactions must be timestamped in the event. A possible algorithm might be the following:
Consider an Ei event that contains the {Tr_1,Tr_2, .... Tr_j} transactions that are ordered as {sha256(Tr_1), sha256(Tr_2) ... sha256(Tr_j)}. The time period between Ei and Ei-1 can be evenly distributed among the transactions in a way that if a transaction gets a higher ordering, it gets a newer timestamp. 

Last but not least, a fair access can be only be reached if transaction are communicated to several nodes, like one 33% +1 of the exiting nodes.