...by Daniel Szego
quote
"Simplicity is the ultimate sophistication."
Leonardo da Vinci

Sunday, September 23, 2018

How to create real decentralized random oracle with Hashgraph



Real random oracle is one of unsolved Holy Grail of decentralized networks. Hashgraph technology promises perhaps a real possibility to solve it. A pseudo algorithm should be the following:

Let we assume that we have a smart contract function that assigns to a state a new value, like

function() {
 state = new_state
}

we basically do not call this function but create a transaction, like

TR: call function() signed by private_key of some account owner.

This transaction is propagated on the network by the gossip of gossip protocol, probably checked by every node, goes through a virtual voting and ordered with other transactions into a common order. Only after that, it is applied to the state (independently if it is an account based system or an UTXO based).

so let assume a function that calls a real native decentralized random oracle, like the following function:

function() {
 state = rand()
}

and a transaction that calls this function.

As soon as a node "sees" the transaction of function that contains a random oracle call, the node call its internal native random function and creates a ri random value, which is further propagated on the network similarly as the transactions. As a consequence there will be a set of {r1, r2, .... rN} random values propagated on the network, one for each node.

As a next step, we wait until there is a consensus and an order of these random values, so every node will see exactly the same order of these individual random values, like r4, r3, r1, r2 ... rN. And at this point we give a value to the random function as rand() = merkle_root(r4, r3, r1, r2 ... rN). As merkle_root is a deterministic function and and each node sees exactly the same order of individual random numbers, even if rand() is calculated independently at each node it will produce the same result.  

Certainly, the real quality depends on the individual random numbers as well. However as Hashgraph is Byzantine fault tolerant, if more than two third of the nodes provide a relative good random number meaning either cryptographically secure or pseudorandom, the result will have probably the same attribute, meaning cryptographically secure or  pseudorandom.

Experimental implementation can be found in the following github repo.