Design a on-chain random number

doubiliu commented 4 years ago

Introduction

Currently, Neo does not provide a on-chain random number. The project can only use Oracle to obtain external random number. Such random number is not reliable. If Neo can provide a on-chain random number, it will have a relatively large application scenario ,such as gambling and games.

Detail

Truly/Pseudo-random number

We divide random number into 2 categories: truly-random number and pseudo-random number

Truly-random number: All unpredictable random transactions in real life, such as the probability of rocket launch failure.
Pseudo-random number: Through a certain algorithm to simulate the generation of truly-random number, you need to provide random seeds.

On-chain random number

We only discuss pseudo-random numbers. Its generation process:

Input--->	Transfer Function--->	Output
Parameter Factor	S():Seed Generation Function ----> T():Conversion Function	Random Number

For general software, the parameter factor can be provided by the machine, but there are two important problems to be solved for the distributed system:

Consistency: Different nodes need to generate the same random number
Decentralization: Avoid the generation of random numbers controlled by a single node

Commit-Reveal mechanism

Due to the characteristics of the blockchain, the rules for generating random number seeds are known in advance. Therefore, attacker can calculate the random number in advance according to the generation rule and manipulate the random number generation, which has centralized risk distribution.

Process

Node submit text hash.
Node submit text.
Calculate the random number

Risk

Leader Attack: In reveal stage, the speaker or the last submitter can control the range of random numbers by whether to adopt the text or submit the text.

Solution

We investigate two options:

Solution1：BLS

Random number seed is the BLS signature of multiple nodes

Base Concept

Curve hash： Reflect msg hash to a point on the curve
Curves pairing：2 points on the curve conform to the multiplication commutation law

Process

Suppose there is node 1 A, node 2 B, node 3 C

Prepare Stage

Each node generates a set of private keys Then we can get: Node A private key group Node B private key group Node C private key group

Each node generates a set of public key Then we can get: It is also known as shared private key. Each node generates a set of shared private keys. Take node A as an example: Each node secretly sends the shared private key to the corresponding other node When a node receives the shared private key of other nodes, it can be verified by the following equation: Currently, the private key, shared private key, public key, and verification information held by each node are summarized as follows:

There is a theoretical global private key $(a_0+b_0+c_0)$ and global public key $(a_0+b_0+c_0)G$ ,but no one knows.

Usage Stage

Calculate the curve hash $H(s)$ of a certain message S.

Each node uses its shared private key to generate a public signature

Problem

In the initial stage, private connections are required between nodes

Summary

The essence of the solution is to use the Commit-Reveal mechanism, but by means of aggregate signatures, the leader cannot calculate the overall signature without collecting enough signatures.

Solution2：RANADO+VDF

This solution has been used in Ethereum 2.0

Process

Node submit hash.
Node submission text.
Generate a random number seed and calculate the corresponding random number through the VDF algorithm.

Problem

Time-consuming: The time it takes to calculate the random number must be greater than the length of the disclosure period.
Power Attack: ASIC hardware can reduce calculation time

Summary

It is essentially a variation of the Commit-Reveal mechanism. The VDF algorithm prevents the leader from knowing the random number calculation result in advance, making it inoperable. But in the long run, there is still risk .

shargon commented 4 years ago

The same block could have different signatures in different nodes.

doubiliu commented 4 years ago

Why? @shargon The public signature of each node may be different, but when a sufficient count of public signatures are aggregated, the global signature is the same.

shargon commented 4 years ago

But you can receive 5 signatures (ABCDE) and i receive (ABCDF) and both blocks are valid, but our agregation are different.

doubiliu commented 4 years ago

This will not happen, because the signature of each node will be written into the smart contract through the transaction, which means that the set of signatures recorded in the block is a gradually increasing set.In addition, even for different collections, such as <ABCDE> <ABCDF>, we don’t need them to be exactly the same, only the majority of them are the same, because

shargon commented 4 years ago

because the signature of each node will be written into the smart contract through the transaction,

OK, I thought that this will happening during consensus

doubiliu commented 4 years ago

Haha, this has nothing to do with consensus. We only need to select a few nodes to periodically submit a few signatures to the chain, so that users can use the random number in the interval.

doubiliu commented 4 years ago

If we use BLS as the signature method for Oracle transactions, this implementation will be simpler. @shargon @belane

shargon commented 4 years ago

If we use BLS as the signature method for Oracle transactions, this implementation will be simpler.

https://github.com/neo-project/neo/issues/1085#issuecomment-611550968

doubiliu commented 4 years ago

Do you have any new ideas? @erikzhang @shargon @vncoelho

erikzhang commented 4 years ago

My idea is that this is not part of neo3. If I were you, I would not spend time on it, at least not at present.

igormcoelho commented 3 years ago

I would also love to have some pretty random number on chain, and just to check, we still have some block nonce on Neo 3, correct? Besides that, if some communities are committed to sending one or few tx every few seconds for the lifetime, including real hardware entropy, I cannot see something better than that, for users to have access to real entropy on their codes (besides CN block nonces and the rest). As long as censorship does not apply to random transactions, it is impractical for any authority in Neo ecosystem to control the numbers (as user contracts are free to choose the mixing hash strategy, that may include block hash, previous block hashes, and transactions in prefixed positions).

So, in my opinion, a better thing that Neo could offer is the implementation of Mersenne Twister and other nice lightweight deterministic pseudo-random generators, with cheap gas costs, being initialized by these "entropy-based" hash seeds. This simplifies implementations a lot, and removes barriers from users having to redesign random strategies to untested ones that may certainly be unsafe on practice.

roman-khimov commented 3 years ago

we still have some block nonce on Neo 3, correct?

We have it in consensus data ("footer" part of the block), but it's not available to contracts.

neo-project / neo