Random Number Generation on the Algorand Virtual Machine
This pilot proposal is for lib-pcg-avm, a random number generator (RNG) library implemented for Algorand Python, Algorand TypeScript, TEALScript, and PyTeal. [GitHub Link]
Description
Motivation
This library brings to the AVM language ecosystem the capability of generating random numbers, starting from a high-entropy seed.
Random numbers are ubiquitous in cryptography, consensus protocols, randomized algorithms, and particularly smart contract applications (lotteries, winner selection, fair reward distribution, assets with randomized features, zero-knowledge proofs, and much more).
We rely on randomness to create interesting and fair smart contract code, so using battle-tested RNGs is crucial. Getting this wrong can result in devastating exploits and using a known generator prevents developers from having to implement custom solutions that can fail in unexpected and unpredictable ways.
Technical Implementation & Quality Assurance
PCG is highly regarded in academia for its great statistical properties, simplicity, performance, and versatility. These are some of the reasons why I chose it as particularly suited for the AVM. This implementation faithfully replicates at its most fundamental level the reference implementation in C. The AVM implementation that I wrote is subject to test cases produced using the reference implementation, to ensure its behavior doesn’t deviate.
It’s also implemented in four of the popular languages used for writing smart contracts in the AVM: Algorand Python, Algorand TypeScript, TEALScript, and PyTeal. All the implementations are subject to the same test suite, ensuring there’s no internal inconsistency. It can generate random numbers in various bit sizes to ensure developers can use as few resources as needed.
The packaging, distribution, CI/CD pipelines, and test suites are also production-grade. The repository is thoroughly maintained with the help of automated pipelines and GitHub Dependabot, ensuring low maintenance costs and a stable future for this code.
On top the current source code, a great deal of effort went into research, refactors, ideas that were ultimately rejected, and adapting the generator to the specific features of the AVM.
About the Team
My name is Giorgio Ciotti, I have been an Algorand developer since 2020. My most recent job was at the Algorand Foundation, where I worked as a Senior DevRel Engineer and later as a Senior Software Engineer for close to two years. I worked on the AlgoKit suite of tools, wrote smart contracts for both education and production, and I also taught bootcamps on the AVM. Previous to that I was writing tooling and DeFi contracts. I am now, as the time of writing this, an independent dev.
License
MIT License.
Focus
This library serves as an important piece in the randomness supply chain.
It all starts with a seed from a high-entropy source such as the Randomness Beacon and Verifiable Random Functions.
The generator “expands” this seed into a statistically sound sequence of random numbers.
The smart contract consumes this sequence of random numbers to produce its desired result.
We only focus on the generator with lib-pcg-avm, but we note that a separate but equally important piece of the supply chain is a utilities library for classic randomized algorithms such as permutations, combinations, shuffle algorithms, etc.
Funding Type
Retroactive.
Adoption Metrics
The project has been feature complete for a while now, and it has already been adopted by experimental project as well as production-grade projects (Tardly No Loss Lottery). It has been used to develop lotteries, rewards distribution systems, staking systems, and auction protocols.
The TVL in the No Loss Lottery is, at the time of writing, ~674.000,00 ALGO.
Dashboard for lib-pcg-algopy [Link]
Dashboard for lib-pcg-algots [Link]
Dashboards for the TEALScript and PyTeal implementations are not available (the library is not distributed through a packaging system for these legacy languages).
Amount requested
The amount of 32.000,00 ALGO covers the research, development, and past maintenance of the project. This work took place over a span of more than 2 years.
xGov Link
Not applicable yet. Pending discussion on this pilot proposal.
