Randomness Findings

[ryleung-magicblock]

Key findings:

• Initially investigated native randomness in the validator itself, but this was found to be impractical, as no way could be found to protect against the client and validator colluding.
• So, we decided to implement a randomness oracle
• Initial proof of concept using Starknet's VRF at https://github.com/magicblock-labs/VRF-experiments https://github.com/magicblock-labs/stark-vrf and https://github.com/magicblock-labs/vrf-server but VRF proof verification on-chain was found to consume too great a CU cost.
• Did some investigation into implementing a builtin program to do the verification, but this was too complicated, and would make for too complicated of an interface (need 1 tx to commit to a seed and a client move, 2nd tx to call into an instruction to supply a VRF proof, which CPIs into the builtin program, which then CPIs into a third instruction to use the verified random number, or at least 1 CPI from the builtin into an instruction to use the verified random number).
• So, we therefore had to find a way to verify VRF proofs within CU cost using the new Solana syscalls for bignum bn128 operations or the secp256k1_recover syscall
• Based on this, we finally concluded that the two practical approaches are:

1. Wrapping a VRF proof in an e.g. Groth16 proof, which can be verified efficiently on-chain with bn128 syscalls using libraries such as SP1 or Light
   • Verified on-chain verification of groth16 proofs could be done within compute budget (using Light - SP1 should be similar though SP1 currently is not compatible with Anchor due to using too new of a pre-release Solana version) at https://github.com/magicblock-labs/VRF-experiments/tree/light-groth16
   • However, generating VRF proofs wrapped in Groth16 proofs has proven to be too expensive computationally. Generating an uncompressed proof using SP1 took about 21 minutes, resulting in a proof >40mb, and consuming about 16gb of memory. I was not able to generate a Groth16 proof on my system, running out of memory (on a 64gb system). Running the VRF in the SP1 zkvm environment without generating a proof took about 1 second and ~29 million zkvm (RISCV) instructions (though there may be scope for some optimization, it's unlikely to result in a several times or order of magnitude improvement) and Uma from SP1 reports that the absolute minimum for generating a ZK proof for any computation in SP1 is currently about 3 seconds and about 16gb of memory (exceeding our latency requirements at the moment). Test for generating an SP1 proof wrapping a Stark VRF at https://github.com/magicblock-labs/SP1-Verification-Test
2. Directly using ECVRF, which is possible to verify on-chain using secp256k1_recover syscalls. However, the problem here is that there are no compatible implementations of generating the VRF proof and on-chain verification and overall pretty poor support for ECVRF for Solana. So we would need to implement those ourselves, which is difficult due to lacking cryptographic domain knowledge. In particular, https://github.com/deanmlittle/solana-secp256k1/tree/master provides support for various EC operations, which should be possible to be leveraged to do on-chain verification, given domain knowledge.

Conclusion
For now, it does not seem feasible to continue developing the randomness service, because the 2 above options both have blocking issues (respectively, that generating Groth16 proofs is too expensive, and that we don't have the cryptographic expertise to implement ECVRF in-house at the moment). If/when that changes, we can restart along one of the above 2 approaches depending on what "makes sense" or is available at that time.

[GabrielePicco]

Implemented here: https://github.com/magicblock-labs/ephemeral-vrf