Pseudo-Random Number Generator (PRNG) for Cartesi's Convenience Layer

[fscosta]

New Proposal

Cartesi PRNG

A set of tools to generate random numbers on Cartesi’s convenience layer.

Project Description

The goal of this project is to create a framework for Cartesi that will make it easy for web3 developers to create DApps using Cartesi. The framework will:

• use React and TypeScript to create a modular and reusable component library that will provide a common PRNG (Pseudo-Random Number Generator) algorithm to Cartesi technology;
• use Web3.js and Cartesi’s SDK to connect to the blockchain and the Cartesi Machine;
• be documented with Docusaurus;
• be published on npm and GitHub and maintained with semantic versioning.

Our project will offer three different ways to generate random numbers, each with its own advantages and disadvantages:

1. The first type uses block number, clock, and end user ethereum address to make a seed. This is a simple way to generate a seed that depends on some external factors that are hard to predict or manipulate. However, this type of PRNG may not be very secure or random, as it may be vulnerable to attacks or biases.
2. The second type uses VDF - Verifiable Delay Function, which will produce an unpredictable result in the future while the blockchain network is making another block. That way, the resulting seed cannot be predicted or biased. Also, the VDF result can be provided by anyone to avoid tampering.
3. The third type uses a hash function to commit to a number that will be revealed in the future and generate the seed. This is a more secure and random way to generate a seed, as hash functions are designed to produce outputs that are unpredictable and uniformly distributed. However, this type of PRNG may require more transaction steps and may not be very efficient.

Value proposition

We believe that creating these tools for developers we remove a important entry barrier for them. Random numbers are an essential part of many apps and DApps, specialy games. So, as we add this feature to the convenience layer, we expect to see an increase in Cartesi’s adoption and in our community growth.

Here are some types of games that could benefit from this framework:

• A decentralized soccer game that uses Cartesi’s random algorithm to generate fair and unpredictable moves for both players;
• A decentralized card game that uses Cartesi’s off-chain computation to handle encryption algorithms and game logic to randomize the deck;
• RPG games that use PRNGs to determine loot drops, enemy spawns, critical hits, etc.

How you will use Cartesi, specifically?

This project aims to add tooling to build DApps on Cartesi, and this is why it makes sense to have community’s support. The following sections describe how each of the algorithms will interact with the Cartesi environment.

Simple PRNG

The Simple PRNG scheme is unpredictable and verifiable, but it is biasable because the block proposer for a given slot can directly manipulate the block’s hash by manipulating the block’s body.

VDF PRNG

For this type of PRNG, we will use a VDF - Verifiable Delay Function for cryptography. A VDF is a function that takes a certain amount of time to compute, and cannot be accelerated through parallelization or additional processors. Once computed, the output can be quickly verified by anyone.

1. Define a VDF that takes twice as long as the block production time.
2. Send an input to initiate the process and obtain the block hash of the transaction block: BlockHash[0].
3. Compute VDF(BlockHash(N)) and send the result to the contract.
4. Meanwhile, the network will produce the next block hash: BlockHash(N+1).
5. The contract will combine the VDF results with the block hash and generate a random number.
6. Send the number to the target contract.

This algorithm can be exploited by the leader only, if the leader has a sequential processing power more than twice as high as the network’s. To illustrate, let’s imagine a hypothetical scenario: The leader generates the blockhash, calculates the result of the VDF and if it is not favorable, he generates another blockhash.

Hashed Turn Based Seed for PRNG

Based on the commit-reveal but applied to PvP games where the result can be WO.

The commit-reveal is a cryptographic scheme that allows players to hide their choices until they are revealed later. It is used to prevent front-running attacks, where someone can see the transactions in the pool and act before them. The commit-reveal has two phases: a commit phase, where the players send their hashed choices to a smart contract, and a reveal phase, where the players reveal their choices and the contract verifies them. The contract then uses the choices to generate a random outcome for the game.

PvP games are player versus player games, where two players compete against each other. Examples of PvP games are rock-paper-scissors, even or odd, or poker.

The result can be WO means that the result can be a walkover, which is when one player wins by default because the other player does not show up, forfeits, or fails to reveal their choice.

Milestones

Milestone 1: Simple PRNG

• Duration: 4 weeks

• Deliverables:

  1. An automated build and test process of the npm library artifact using Github Actions;
  2. An automated packaging and release process for the npm library;
  3. The entire codebase under a permissive MIT open-source license;
  4. A readme file that explains the project;
  5. A smart contract with a new attribute in input_metadata to receive blockhash;
  6. A library for the Cartesi Machine that obtains all the seeds and produces a random number sequence

A simple method to generate random numbers

• Funds request (USD) for milestone 1: $8,000 USD

Milestone 2: VDF PRNG

• Duration: 6 weeks

• Deliverables:

  1. An automated build and test process of the library artifact using Github Actions;
  2. An automated packaging and release process for the npm library;
  3. The entire codebase under a permissive MIT open-source license;
  4. A readme file that provides an overview of the project;
  5. A smart contract with:
     1. a new method to verify the VDF result;
     2. a new method to register the configuration;
     3. a new attribute in input_metadata to receive the seed;
  6. A library for the Cartesi Machine that obtains the generated seed and produces a random number sequence

• Funds request (USD) for milestone 2: $12,000 USD

Milestone 3: Hashed Turn Based Seed for PRNG

• Duration: 8 weeks

• Deliverables:

  1. An automated build and test process of the library artifact using Github Actions;
  2. An automated packaging and release process for the npm library;
  3. The entire codebase under a permissive MIT open-source license;
  4. A readme file that provides an overview of the project;
  5. A smart contract with:
     1. a new method to register the commit hash;
     2. a new method to check the revealed result;
     3. a new attribute in input_metadata to receive the seed;
  6. A library for the Cartesi Machine that obtains the generated seed and produces a random number sequence

• Funds request (USD) for milestone 3: $16,000 USD

Total funds requested

$36,000 USD

About your Team

Bruno Ochotorena

Web3 Developer
LinkedIn: /in/sandhilt

Fabio Oshiro

Web3 Specialist
LinkedIn: /in/fabiooshiro

Contributions to the Cartesi community:

• We ran a Solana DApp on Ethereum using Cartesi
• Open-Source: Cartesi’s Solana adapters

Links and resources

Website: calindra.tech

LinkedIn: /company/calindra

Github: /Calindra

ERC-20 Payee address

0x7cE0AA3DFbB8abdCD0Ea426769ffD21302DAA8B8

[felipeargento]

Your proposal is very interesting and well written! I believe that making random numbers easily accessible for DApp developers will be incredibly beneficial, and I like the idea of providing different pathways with varying levels of strength for developers to choose from.

As a reusable infrastructure project, it seems like a perfect fit for the grant program. I’ll refrain from commenting on the budget, I think it’s best left to the community to assess

About the project itself:
Regarding the Simple PRNG, have you considered incorporating something less predictable than just the block.number? While this wouldn’t necessarily prevent miners from manipulating the result, it would make it more difficult for users (who own the sender address) to predict it.

One possible solution could be to include information such as block.timestamp to it. “Clock” (contained in the Cartesi Machine), “Sender address” (defined by the sender), “Block number” (somewhat predictable, but not defined by the sender), and “Block timestamp” (decided by the proposer, but more volatile) might be a good combo. This could even function as a weak VDF of sorts, cause it may take some time to collect all the necessary information haha.

This is the list of constants available to the smart contract which could be used as a seed:
https://docs.soliditylang.org/en/v0.8.17/units-and-global-variables.html#block-and-transaction-properties

Have you considered how this seed would be included in the InputBox? One approach could be to create a different “addInputWithRandomSeed” endpoint and require the DApp to only accept inputs with it, so that each time the DApp advances its state, a new random number would be available. Or, maybe you can use the Input Metadata, so you don’t even need a different endpoint, and all the inputs contain it.

Lastly, I wasn’t entirely clear on whether you were creating both the input creation outside the Cartesi Machine and the generation of the actual random number inside a TypeScript package that can be imported inside the Cartesi Machine. The first piece would be great because it could be used by other contributors to create libraries in different languages, so we’d extend this convenience to even more developers

About the proposal:

I’d like to see a bigger list of deliverables for each milestone, so that they can be treated as self-contained. Take a look at this RFP, for instance, it might serve as inspiration for deliverables:

[RFP #004] Distribution channels for the Cartesi Machine Emulator binaries

Distribution channels for the Cartesi Machine Emulator binaries Introduction The Cartesi Machine Emulator is at the core of the Cartesi technology stack. It is used in the Cartesi Rollups framework, while running a validator node for a DApp, but it’s also used as tooling during the development of a Cartesi DApp. The emulator binary is currently officially distributed as a docker image, available at Docker only for linux/amd64. While that may be sufficient for node execution it’s not the most …

For instance, in the first milestone: will you deliver a npm package that can be used in Cartesi DApp to generate the random numbers? Will you create an example DApp that uses that funcionality so we can see it running/working? Will you deliver unit tests and a README? etc.
You mention some of that in the goals of the project, but I’d also add that specifically in the deliverables for the milestones.

The budget request is a bit hard to judge without understanding the exact deliverables

Thank you for submitting this proposal. The diagrams were a nice touch!

[fabio.oshiro]

Hello Felipe, we are thinking of putting an array of blockhash in the metadata, do you think it would be feasible?

Regarding the deliverables, we will include these details in the proposal: npm, docs and tests for sure!

Thank you very much for your comments

[felipeargento]

No problem, It was a pleasure to review this!

About the array of blockhashes on metadata:
I see two things that can be an issue with this approach. The blockhash is available for the current block (only the past ~255 ones) and the cost of adding a growing array to metadata (worst case scenario is that it doesnt even fit the blockchain). I guess the second problem can be solved if you use a running hash, so you don’t need to include the full array.

[fabio.oshiro]

Ok, the current blockhash is the only thing we need for that implementation. We will revise the proposal based on your feedback.

[fscosta]

Just submitted an update of the proposal. We listed the expected deliverables for each milestone.

[felipeargento]

Nice! The deliverables are looking much better now

Regarding the first milestone, the deliverable number 5 is a bit confusing to me. The blockhash would not be available for a call in a smart contract (because the current blockhash is influenced by that call). So you could only get the past blockhash (up to 255 in the past), which I don’t think helps you very much.
You could consider getting a future blockhash, but then I think it gets complicated…because you’d maybe need two inputs? not sure if there is a clever way to do this.
Anyway, my recommendation would be to do away with the blockhash and use the input metadata information as the seed coming from the blockchain. But I’m sure you’re more suitable to make that call !

Other than that, I’m still missing a deliverable so that we can see it working in practice. I’d love if you could consider adding a small example-application using the library you’re building as a deliverable to each milestone. It doesn’t even need to be useful, just showing the basic functionality would suffice imo.

Just to reiterate: I think this project would be a great addition to the cartesi ecosystem, it will help a lot of different developers and I’m quite excited about it!

[fabio.oshiro]

You are right, I made a mistake. However, the L2 only gets the input after the block is finalized, so we still have the blockhash, don’t we?

[felipeargento]

Unfortunately not! It’s true that in the common setup the L2 only receives the inputs that after the block is finalized in L1. However, when the block is created (not even finalized) the input is already ossified. For the dapp to have access to the blockhash of a block with a certain input, you’d either have to send another input on a future block informing it or you’d need the dehashing device - which doesnt exist yet

[fabio.oshiro]

What you are saying to me is that all the input, including the metadata, is made on-chain, right?

[felipeargento]

Exactly!
Here is how, in version 0.8, the input metadata is stored onchain:

cartesi/rollups/blob/main/onchain/rollups/contracts/libraries/LibInput.sol#L134

The input itself is not exactly “made on-chain”. One decides what input they want to send to a certain Cartesi DApp, calls the onchain smart contract function addInput(bytes input). That “input” was defined offchain and is only interpreted by the DApp running inside the Cartesi Machine. The addInput function adds the metadata, which is made onchain for real.

[carsten.munk]

Without dismissing anybody’s approach to things, there’s also an approach like just using a https://drand.love/ random beacon that for example Filecoin relies on; it’s just a BLS12-381 signature check

[Divesh]

RNG is definitely super important, but does the project really need 36k to build this ?

I believe, it would be better if cartesi made the PRNG available though the language compilers. ( Like , the random function - instead of using the general methods , would use data which makes sense on the block chain to generate the random number )

[fabio.oshiro]

Nice contribution! This is a good option for generating a random number. We are working on that proposal.

[fabio.oshiro]

Given all the information, we came up with this proposal, using Drand → Tooling: Drand for Cartesi

[joe-cartesi]

Thanks, Fabio. I will lock this thread. Can you do me a favor and link to it from your new proposal?