Randomness inside the Cartesi Machine

Technical Vision Forum
1

Introduction

Randomness has many uses in science, art, statistics, cryptography, gaming, and other fields. The Cartesi Machine, however, is deterministic and, therefore, can only generate pseudo-random numbers from an initial value, called “seed”. Since the initial machine state is known, it cannot contain the seed, otherwise the entire sequence of random numbers would also be known. The seed must, therefore, be derived from inputs.

RANDAO

A random seed can be generated by a group of participants using a commit-reveal scheme. Ethereum proof-of-stake (PoS) employs a slightly different scheme for randomly selecting block proposers, known as RANDAO. In this scheme, the random number generated by a block proposer is their signature of the current epoch number n with their own private key. This value is then mixed in (through XOR) with the previous RANDAO value. At the end of the epoch, this value is then used to select the block proposers of epoch n+2.

Post-merge, EIP-4339 introduced the PREVRANDAO opcode, which returns the previous RANDAO value. This EIP also outlined several considerations for application developers that would like to use RANDAO values as a source of randomness for their applications. The main takeaway is that RANDAO values only get more random over time, as random events have more time to interfere: block proposers accidentally missing slots, effective balance fluctuations, validators turning active/inactive, etc. The EIP suggests applications to wait at least 4 epochs, and an additional 2–4 slots for the next RANDAO value.

Solidity 0.8.18 introduced the block.prevrandao keyword for retrieving the previous RANDAO value.

Proposal

Add block.prevrandao to the input metadata schema.

Security considerations

We argue that numbers generated by the RANDAO are a “good enough” source of randomness for most DApps. There are several considerations related to the safe usage of PREVRANDAO by application developers, which can be found in the resources linked at the end of this text.

Usability considerations

High-level frameworks (HLFs) can help developers decode input metadata (to extract the prevrandao field) and manage delayed “dice rolls” (for the suggested amount of epochs and slots, in terms of blocks).

External resources

2

I agree with the idea of inserting prevrandao at every input. Then we let some library inside the machine decide when enough time has elapsed. I guess that different applications will require different tradeoffs between quality-latency of RNG.

However, I would argue that the library inside the CM has to be very well designed.

For example, what if a DApp has very infrequent inputs and an attacker is able to wait until the moment when prevrandao is “convenient”? We have to take these situations into account as well.

The dehashing device would completely solve this issue, though.

1 Like
3

The dehashing device would completely solve this issue, though.

You’re right! With the dehashing device, you’d be able to access the prevRandao field from block headers. This would even allow you to add an input any time you want after the recommended “waiting period”. The problem with the current PREVRANDAO instruction is that you can only inspect this field from the previous block, so the user has to really time his input-adding, or the DApp back-end may be permissive to allow inputs a few blocks later, which may hinder security.

1 Like
4

The post (ref: Solidity Deep Dive: New Opcode 'Prevrandao' Section “How to use current Prevrandao”) discussed 2 ways of implementation. Way 1 is to retrieve prevrandao anytime after the recommended wait period, and this way has the drawback as Augusto and Gui mentioned. Way 2 can mitigate this situation a little, by enforcing to use the prevrandao only from one specific block. However, if that block was missed, then the prevrandao can’t be used.
Way 1 is very relaxed while way 2 is quite strict. So maybe the middle ground is worth considering: allow the use of prevrandao only from a specified range of blocks after the recommened wait period.
This way the condition won’t be too strict, while not giving attackers unlimited advantages.

5

quick question: How that is different from the random number generation created by Calindra?

6

This is a nice idea, but it has to be clear for the developer that users that know how to hack this get to “re-throw” the dice if they want to.

So, for example, a cassino running a standard roulette could become attackable.

7

Another alternative is to use block-hashes. This allows for an interval of 256 blocks for the user without harming security.

For example, when you request a seed the DApp registers the current bn = block.number. Then, if within 256 blocks some user sends some input, then we could retrieve the block-hash of bn + 1. But: this cannot be done automatically with every input that arrives to the input-box.

Here is yet another alternative:

For every input that arrives to the input-contract, it includes within the blob the following weird looking thing:

block.hash( ((block.number - 1) % 100) * 100 )

Then, suppose that your input arrives at the block 123456 and requires a seed. Then if any input arrives between blocks 123500 and 123599, your request can be fulfilled. It is possible to make this interval a bit larger (like 200).

What do you think?

8

I would have to read it more in order to understand it. Can you send some documentation?

9

Another alternative is to use block-hashes. This allows for an interval of 256 blocks for the user without harming security.

But then wouldn’t the block proposer be able to craft a block such that its hash produces a favorable outcome in some dApp?

10

I think application developers should have a “framework” about how to decide if PREVRANDAO is good enough for their application, which would be very easy to use, or if a much more sophisticated solution is necessary, like one based on DRAND (Calindra’s work).

As an example: I’m developing a card game, the game lasts for 2 hours, the maximum pot is $10000. Is PREVRANDAO good enough? How much an attack would cost? If it’s good enough, is it still good if max pot is 1M? Or if game lasts for a day?

I think coming out of the theoretical field and tapping the real world is important.

1 Like
11

Great point! I believe this estimation would have to consider the block reward, which, according to the article from Markus Waas linked in the main text, is roughly 0.044 ETH (depending on ETH inflation rates). Another source of income for the block proposer we have to consider is through MEV, which is somehow dependent on luck.

12

Hi @Augusto
Docs:

Attack vectors:

13

Indeed, it would be great to have a clear process to help developers decide what RNG is good enough for their applications. But in fact, I think that all of the proposed ideas (DRAND, PREVRANDAO, BLOCK NUMBER, CHAINLINK) are good enough to get things started.

It is not a requirement that the first solution is also very safe. Any implementation that is not broken and is convenient to use (in terms of API) will kickstart the usage of RNG in Cartesi DApps. This can be reviewed and improved later on.

1 Like
14

During PoW, miners were not able to craft a block hash. Instead, all they could do was withhold a block that was not convenient for them. As it turns out, this is not a big weakness, except for very large bets.

One has to research if this has changed significantly since PoS.