Secure random number generator at runtime for N3

[Jim8y]

• update June 24 2021, remove VRF, currently allow the primary to generate the nonce directly with Random system call, will update it with BLS based on issue #1657 .
• update May 17 2021, remove VDF, use VRF directly. #2470

It has remained a big challenge for all Blockchain projects to generate secure random numbers at runtime. Existing solutions to get random numbers are basically using the data from the Blockchain, which has limited random space and sometimes predictable. The random number should be hidden from users until transactions are executed and grouped into blocks to design a secure random number generator. It is hard to achieve a secure random number generator for other Blockchain projects, but rather easy to do so in neo because of dBFT.

Do you have any solution you want to propose?

The primary generates a random number denoted as nonce_0 and keeps it in the header. After the new Block is confirmed, each consensus node generates a local random number marked as nonce, then calculates the random number with VDF.

VDF is a type of function with a minimal execution time, making sure that everyone has to wait for a specific time to get the result.

In the figure above:

• nonce_0 is the random number from the latest Block. This value prevents other consensus nodes from preparing random numbers in advance.
• nonce is the random number that each consensus node generates locally. This value prevents the last primary from calculating the random number in advance.
• block denotes the hash value of the latest Block. This value makes sure that dishonest nodes could prepare the random number in advance jointly.

To prevent nodes from generating random number in large scall to pick one that benefit themselves the best, the delay of the VDF should be over half of the value MillisecondsPerBlock.

Considering each consensus period might have multiple views, every consensus node has to prepare its own verifiable random number in case of view change.

To prevent consensus nodes from creating multiple nonce values locally and run multiple VDF in parallel, we can use Verifiable Random Function (VRF) to make sure that each consensus node can only generate one verifiable random number with given input.

Neo Version

• Neo 2
• Neo 3

Where in the software does this update applies to?

• Compiler : Add new runtime interface System.Runtime.GetRandomNumber
• P2P: Has to add extra field Nonce to the Header.
• Consensus: Add one extra random number field to consensus messages.

[erikzhang]

Block[i - 1].Nonce ^ Block[i].Hash?

[Jim8y]

Block[i - 1].Nonce ^ Block[i].Hash?

No, we can not use any value from the existing Block to generate secure random number. More like Rand[i] = Block[i].Nonce ^ Block[i].Hash

[Jim8y]

Rand[i] should be generated along with Block[i - 1].Nonce, but keeps hidden from the public until generating Block[i]

[Jim8y]

2296

Nonce in the previous version is not reliable because it relies on the primary node to generate it and is published to the public before it is used for the next Block.

In the new design, consensus nodes do not publish the nonce until it is used. And even the nonce generated by the primary node is not directly used to prevent misbehavior of the primary node on the random number.

[erikzhang]

I don't think you can assume that the primary is honest.

[Jim8y]

I don't think you can assume that the primary is honest.

I agree, that is why the number generated by the last primary is not directly used.

[Jim8y]

The principle here is, other consensus node should not able to know the random number until they start the consensus. The primary node is the first to know the random number but it can not decide or change it.

If you stil think it is not secure for primary node to join the process of generating random number, maybe we can also use Oracle nodes to create random number cooperatively by sending a random number transaction for each Block.

[Jim8y]

Please allow me to put it more clear by renaming those terms:

The random number generated by the last primary node is denoted as raw_random_number. The random number used for contract execution is called random_number.

raw_random_number is synchronized to all consensus nodes but kept private to the public.

random_number is calculated from raw_random_number by the current primary with built-in rules, xor or hash with transactions from persisting Block for example, such that no node could determine or know random_number beforehand.

[erikzhang]

raw_random_number is synchronized to all consensus nodes but kept private to the public.

It is impossible. Because the consensus messages are relaying on the p2p network.

[Jim8y]

raw_random_number is synchronized to all consensus nodes but kept private to the public.

It is impossible. Because the consensus messages are relaying on the p2p network.

My mistake. But encryption algorithms could achieve this.

[erikzhang]

My old solution is to use Shamir's Secret Sharing Scheme.

[Jim8y]

My old solution is to use Shamir's Secret Sharing Scheme.

Now I unserstand where the biggest problem is. Will try to redesign it with threshold signature.（might also try VDF）

[doubiliu]

My old solution is to use Shamir's Secret Sharing Scheme.

Now I unserstand where the biggest problem is. Will try to redesign it with threshold signature.（might also try VDF）

I think BLS will be a better solution.

[Jim8y]

My old solution is to use Shamir's Secret Sharing Scheme.

Now I unserstand where the biggest problem is. Will try to redesign it with threshold signature.（might also try VDF）

I think BLS will be a better solution. BLS is a decent way to generate random numbers, but i think it introduces too much modification to the existing consensus algorithm. And expecially for dBFT, which has selected primary, i think it would be more reasonable to generate verifiable random numbers locally.

[doubiliu]

My old solution is to use Shamir's Secret Sharing Scheme.

Now I unserstand where the biggest problem is. Will try to redesign it with threshold signature.（might also try VDF）

I think BLS will be a better solution. BLS is a decent way to generate random numbers, but i think it introduces too much modification to the existing consensus algorithm. And expecially for dBFT, which has selected primary, i think it would be more reasonable to generate verifiable random numbers locally.

Why should we modificy the consensus? In my understanding, this can be completely separated from the consensus node and completed by Oracle. And in the actual process, we only need a key-distribution step and confirmation step in the initialization stage.

[doubiliu]

When committee selects new Oracle nodes, all Oracle nodes enter the initialization stage, and then use ECC to encrypt the shared private key and send it to the chain, so that it can only be decrypted by the corresponding Oracle node. When most Oracle nodes receive the shared key, it can be considered that the initialization process is over, and then the process of generating random numbers can be considered as just a multi-sign process, which is not complicated.

https://github.com/neo-project/neo/issues/1657#issue-621474006

[Jim8y]

When committee selects new Oracle nodes, all Oracle nodes enter the initialization stage, and then use ECC to encrypt the shared private key and send it to the chain, so that it can only be decrypted by the corresponding Oracle node. When most Oracle nodes receive the shared key, it can be considered that the initialization process is over, and then the process of generating random numbers can be considered as just a multi-sign process, which is not complicated.

#1657 (comment)

Oracle in N3 uses callback trancation to process oracle request, which is an asynchronous function, I dont think it is a reliable way to generate random number for Block since the primary will not know when it can get the random number transaction.

[doubiliu]

I probably understand now, what you imagine is to generate a random number in each block. It sounds like VDF is also a good idea. But I want to know what is the application scenario of this random number, because if it is only a user's request (such as gambling, etc.), it seems that the real-time requirements of the block are not too high.

[Jim8y]

I probably understand now, what you imagine is to generate a random number in each block. It sounds like VDF is also a good idea. But I want to know what is the application scenario of this random number, because if it is only a user's request (such as gambling, etc.), it seems that the real-time requirements of the block are not too high.

can you please share your concern onVRF with me?

[Jim8y]

2470

[ediopia]

This will be very useful for my project

[roman-khimov]

Implementation-wise my concerns are:

• modifying block header in #2477 We're at RC3, changing block headers is very invasive.
• modifying consensus protocol in neo-project/neo-modules#596 We're at RC3, we want consensus to work in final release.

But there also is a protocol-level problem, the code we have in neo-project/neo-modules#596 implements (primary_private_key, prevhash) -> nonce scheme, so while Primary can't cheat on it and can't choose a random number it wants to it still knows this number well in advance of other nodes and it still can benefit from it. This nonce is not dependent on current block in any way, Primary can then change transaction list/generate transaction of its own to benefit from this known nonce. And it wouldn't require any computational power actually, because the nonce is known, the "lottery" contract (in general) is known and transactions that are to be included are controlled by the Primary.

2481 is different in that it allows Primary to choose some particular generated nonce which theoretically makes it weaker than neo-project/neo-modules#596, but practically malicious Primary needs to benefit from this in some way and that actually can be harder than with neo-project/neo-modules#596. Because it can only benefit from it by altering transaction list (moving/removing transactions of others and adding transactions of its own), but that directly affects block hash and thus random number generated. So there is a conflict between choosing a number and benefiting from it with this scheme and I think it's a good property.

Both solutions have some problems, but #2481 is much much simpler and can be implemented with minimal modifications to the core parts, so it'd be nice to consider it again.

[Jim8y]

@roman-khimov, thank you for your discussion and suggestions. I do agree with all the things you mentioned.

But please allow me to make some clarifications.

First of all, the threat that you described above is called the MEV attack. We should discuss this topic in another issue cause it exists everywhere in all Blockchain projects.

Secondly, nonce here is a tool, and we never said the user should use it in the current block. Users could send the transaction first then call the random in a callback transaction, it's up to the contract developer.

Thirdly, we have principles to follow while designing a random number algorithm: uniqueness, unbiased, unpredictable, unknown before users sending transactions. That is why we shall never never and never use the existing onchain data directly and that is also why crypto scientists design VRF, please refer to large-scale attacks against random number on EOS in 2019.

Then, random number is essential for NEO on Game, DIFI, and NFT, if we don't add it now while N3 is still under development, it would be too late and make NEO fail behind the public chain competition. Since it requires hard fork, if we don't do it now, the next chance would be neo N4 of who knows when.

Lastly, as you can see in the discussion above, I tried to add 'nonce' in the transaction instead of in the header, but I failed to do so cause of various challenges. Trust me, i feel the same as you when I had to add the nonce to the header. It is a hard choice, but it's the only one.

[roman-khimov]

Users could send the transaction first then call the random in a callback transaction, it's up to the contract developer.

If used in a commit-reveal fashion where all transactions are settled first and only then some subsequent block announces the winner based on current random number then yes, it is secure with #2477/neo-project/neo-modules#596 if PrevHash comes from different Primary (and #2481 allows for Primary to cheat with some computational effort if it has made some bet already). Do we have cases where we need to have some random number in the same block with transaction using this number? I'm not sure, but looks like the only way to do that really is some BLS scheme mentioned above (but it's even more invasive in terms of dBFT modifications and it also is very slow, might be noticeable).

Since it requires hard fork, if we don't do it now, the next chance would be neo N4 of who knows when.

Well, it comes down to release management then and here my top priority for now would be rolling out N3. For this to happen we must not change it. There are lots of things that could be improved, but we can roll them out in incremental updates (and it'd give these features more time to mature).

[Jim8y]

@roman-khimov i don't think it worth any effort to worry about an issue no other Blockchain projects can currently solve. MEV attack, I think you know that better than me, is a fundamental design issue of Blockchain. But the random number is a thing we could address right now, think about that, it requires a hard fork to add it, but we are just right here, even Ethereum is also working actively on adding the random number in eth2.0, you should know how important it is for a public chain project. We can work on other improvements later, but not this one since it needs a hard fork. Once you release N3 officially without the random number, there is no chance for neo to have it anymore, whatever the method you prefer. Random number is important for Games and NFTs, i don't know what N3 is gonna do when tons of Game and NFT contracts need the random number to work.

[nicolegys]

@Liaojinghui Since your current implementation changes a lot from the discussion here, could you give a brief overview of it? It seems that there are still some concerns and suggestions. N3 is coming soon and random number is important, let's have a final review on this issue.