The PCG Random Number Generator for the AVM | xGov
The PCG Random Number Generator for the AVM
This pilot proposal is for lib-pcg-avm, a random number generator (RNG) library implemented for Algorand Python, Algorand TypeScript, TEALScript, and PyTeal.
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.
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 of 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.
Proposal Funded!
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.
The entirety of this work was done outside of the tasks and responsibilities of my former job at the Algorand Foundation.
Additional Info 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.
Adoption Metrics
- The project has been feature complete for a while now, and it has already been adopted by experimental and 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.
- ClickPy reports 15K+ total downloads ClickPy Dashboard
- npm-stat reports old metrics of adoption; it's not possible to get a global view npm-stat
Created By QB3E...J34A//5 months ago