Context

By leveraging zero-knowledge proofs, it is possible to verify large computations within Leo programs, very large computations. Whereas traditional blockchains are often used to reward people based on small data points (you made the right DeFi trade, you are a unique human, you signed up for an airdrop), there is an amazing opportunity ahead to reward people for larger work that they perform. What if we could instantly reward people for solving large math problems or physics simulations which are objectively verifiable?

There have been initiatives running for decades where people can contribute to solving computational problems, perhaps most famous are folding@home and the BOINC initiative. However, these systems do not offer financial rewards to participants.

In the cryptography literature, making proofs of large computations is known under the header of Proofs of (Useful) Work, and they are usually used for rate limiting or consensus. There have been several attempts at using Proofs of Useful Work in consensus, for example PrimeCoin. However, for our purposes, all we would want to do is reward people for the useful work which they do.

In fact, the Aleo network has this partially baked in, by rewarding people for creating zero-knowledge proofs. It would be great if we can expand this to also reward people for solving other computational problems.

Problem

There are many computational problems which might be encodable within a Leo program. However, it is not always straightforward how such problems can be programmed into the program without blowing up the prover time. Depending on the problem, we don’t want to encode the entire problem statement into the Leo program, only the verification that someone found a good solution.

If the verification is anyhow succinct, a bounty program could also easily be created on, say, Ethereum. However, two problems on Ethereum are that:

• the submitted solution would be public and at risk of front-running.
• there may still be significant costs incurred to run the verification

Here are two concrete examples of computational problems, for which a Leo program could put up a bounty:

• Alice wants to find large mersenne primes, but this takes a lot of work. She would like to reward anyone who finds a new large mersenne prime.
• Alice wants to find an improved solution to a large travelling salesman problem, or to a number of other stochastic local search problems (as proposed by IOHK). She would like to put up a bounty for anyone who has a better solution than the status quo.

Have a look around at the BOINC website, there are many other computational problems awaiting…

• Improving our understanding of stellar objects and physics
• Deep learning
• Climate modelling
• Medicine and biology modelling, e.g. for protein folding

Requirements and Design Considerations

Impact

By making use of zero-knowledge proofs, we can incentivize the world to solve real computational problems and be fairly rewarded for this. And all of this in a trustless way. The resulting solutions, from the travelling salesman problem to prime search, could help make numerous systems in the world more secure, efficient and smart.

Design Specifications

For this RFP we would like to see a Leo program which allows any user to add Aleo credits as a bounty. In principle, each deployed program rewards solutions to one specific problem. The bounty will only be paid out if a particular computational problem is solved; see the examples above for inspiration. Different computational problems will need different Leo programs.