Try   HackMD

Hackathon Idea - Provable Optimization Bounties

A system by which parties can prove they have found some inputs which result in some output for an arbitrary problem and claim a bounty.

The problem is defined as a program which compiles to MIPS and reads/writes to particular memory locations for the input and solution. The program can be very large. Only the cost of a challenge increases with problem size (and even then it only increases logarithmically)

Applications

Bounties could be posted on-chain for the following types of problems

  • Challenging non-convex optimization problems

  • Speed running / superplay

    • Find a sequence of inputs (button+CPU cycle pairs) that reach some game state while minimizing time or maximising score (or some other objective function)

  • Hacking a binary or contract

    • Given a harness around a piece of software a participant could try to find some inputs which manipulate the program in a particular way (e.g change the balance locked in a contract) and therefore provably claim a bug bounty.

  • Verifying SNARKs

    • If the off-chain computaion is verifying a ZK-SNARK proof then the protocol inherits the zero knowledge property while being far cheaper to execute on-chain. This also allows exploring of different trade-offs (e.g. code size and execution against proof size) where usually minimizing on-chain proving cost is the primary goal for SNARKs

  • Producing SNARK proofs

    • Allow for posting bounties for expensive SNARK proof generation. The fraud proof is proof that a given SNARK proof is correct for some given inputs (no longer ZK although I think it can be with some tricky homomorphic shit)

  • Other chain state transtions

    • It would be possible to prove execution of a chain state transition function from genesis to particular valid block hash. If the objective function is the chain selection metric it would be possible to have submitters competing to post the best chain at a given height, solving one of the main problems of trustless bridging. (e.g. for Eth2 "the accumulated sum of validator votes, weighted by validator staked-ether balances")

This solves the trust problem usually present in these types of optimization/bug bounties. With the payout encoded in a smart contract there is no need to trust that the funder will actually pay out once they receive the information. This may make submitters more likely to engage.

Willem: My supervisor actually had a student who developed a new CDMA code string and submitted it to Ericsson but they didn't pay out the full amount even though the code met the requirements.

Properties

Very gas efficient to submit a new bounty. Basically just requires posting a hash on-chain and making the code available off-chain.

Optimistic Case:

  • All computation off-chain
  • Only inputs (calldata) and claim info (final state, claimer address) submitted stored on-chain

Challenged Case:

  • One MIPS opcode on-chain per challenge
  • Memory accessed by opcode and merkle trie nodes stored on-chain along with proof paths

Overview

The system makes use of fraud proofs and Optimism-Cannon on-chain MIPS execution.

The code and static memory allocated for the program is put into a single byte array and merklized to produce a root hash. This root hash is submitted on-chain by a bounty poster.

The code is written with a special API that reads the input bytes from a particular known memory location (via the pre-image oracle) and writes the output to another special location (as well as a special magic termination value to particular address).

Participants can execute this code off-chain within a special emulated MIPS environment in order to see the value for given inputs. Their task is to optimize the output according to the bounty that was posted.

If a participant wants to claim a bounty they post their input and output pair to the claim function along with a bond. This starts a challenge period where if any other person can prove their computation was incorrect they will receive the bond. If no-one challenges then the participant can receive the bounty (if their output meets the conditions) and their bond back.

A participant cannot simply post their submission in cleartext as then any miner who sees the claim first can front-run it. Instead two txns must be submitted:

  1. The first is a commitment where the participant submits a signature on the hash of the input. This is the proving they have possession of the input data. The bounty contract saves this signature. Participant waits for finality…
  2. The second reveals the input data itself. The contract hashes it and ensures the signature is a valid signature over the hash (this places further limits on the size of the solution, it must be hashable on-chain within a block gas limit.

To challenge a claim a challenger must also submit a bond of equal value. If a challenge is lodged this starts the bisection search for the single opcode in the execution trace where the challenger and challengee agree on the root hash of the program memory before, but disagree on it after. Once this has been established this opcode can be executed on-chain by the MIPS execution contract to provably resolve the dispute. If the instruction reads from memory or a register this must be provided to the chain along with a proof path of its inclusion in the execution state. It is the responsibility of the challenger/ee to make sure these are available.

Existing work and work for hackathon

Optimism has already done a lot if the difficult work in creating:

  • A Solidity MIPS execution contract
  • A Solidity MIPS processor memory contract
  • A bisection challenge game implementation (would need to be modified)
  • Code for compiling Go s.t. it can be executed in this context
  • An environment for running the code off-chain and testing framework for running it on-chain

What would be required to implement during the hackathon:

  • Contracts for posting bounties that use the challenge and bisection game fraud proofs
  • Golang API for writing program harnesses that reads input and writes output in a standardized way
  • An example application
    • idea - wrap a Nintendo emulator and let people try and beat super mario level 1 in the shortest time. This is a very complex piece of code but has a quite simple interface that shows off the capabilities.

Limitations

  • Submitting a solution requires publishing it in the chain calldata. This is required so that anyone can recreate your solution and make fraud proofs if required. This could be a downside though as it leaks information to competitors. Framing the problem in particular ways could prevent this being an issue (e.g. "the first participant with a result > X wins", rather than "the highest value after T time wins")
  • Input must be submitted as calldata which comes with size restrictions
  • Publishing the solution in the mempool makes it public so could be front-run
    • We could solve this with a

Design

Contract API

!It should allow any arbitrary action to be triggered on the bounty claim, not just releasing funds! Bounty poster can submit a contract that implements the required interface (trigger function ()) which can release funds, mint an NFT, whatever.

setBounty - payable

Accepts:
- The bounty amount to be held by the contract
- Merkle root of the prover code (bytes32)
- Claim threshold (uint256) (one slot)
- Bond requirement

stakeClaim

Accepts:
- Signature on hash of solution bytes
- Hash of prover code this is a solution for

This stores the signature mapped by the prover code and the submitter
codeHash -> submitter -> signature

This allows one submitter to stake a claim for one problem at a time

claim - payable

Accepts:
- Bond for claim
- Solution bytes

Checks that a stakeClaim call was made by hashing the solution bytes and checking the signature matches for the submitter.

Solution bytes are not stored and only includes so they are forced to appear in calldata and be public so anyone can verify the proof.

This starts the countdown for the challenge period after which the claim can be finalized

finalizeClaim

Accepts:
- codeHash
- payoutAccount

Allows the winner of a bounty to claim their share of the funds

Challenge Protocol

Following the example from Cannon this will require

  • initiateChallenge
  • proposeState (challenger)
  • respondState (defender)
  • confirm (anyone)
  • deny (anyont)

The last two are callable only once a single opcode to execute has been isolated by the bisection protocol and the data and merkle path has been provided for its execution.

Prover API

I guess this will be written in Go and is essentially a harness for the actual optimization code. It takes care of reading the input from the correct memory location, writing the output and magic bytes to the correct location, and any other things I can't think of right now.

ReadInput() []byte

Reads input from the redefined location. As this will need to deal with arbitrary sized inputs (unlike Cannon which only takes hashes as inputs and reads the rest from chain) we might need to do something tricky. That or have all inputs the same max size and then allow the code further down to read what it needs..

Minigeth currently reads 32 bytes starting at 0x30000000 for the input. We are going to need way more than that.. more like 1000 bytes. This is possibly the main challenge to be overcome in the hackathon.

There are 2048 bytes of memory until the next special value so I propose we use all of this as the place to write the input blob (up to that max value).

Recall this doesn't actually require writing any of this data to the ethereum state. Only computing a merkle root for a trie over the memory where this has been written.

ISSUE: It is soooo gas expensive to update the Merkle trie! Adding 512 memory locations (2048 bytes) costs like 230M gas! No fucking way.

This can be solved by placing only the hash of the input into the memory trie at the start (this is cheap) and then using a similar approach to the pre-image oracle where the data just appears in memory and the prover code itself verifies the validity of the data against the hash.

Or we could continue following the existing pre-image oracle approach and just put the block hash as the input and then use this to do inclusing proof of the calldata. This is kinda finicky though.

Suggest we use the existing location for pre-image oracle data

0x31000000 onward with the first 4 bytes the length as uint32.

WriteOutput(output [32]byte)

Write the output value to memory location and the magic termination bytes to their location. Also all the exit syscall for non-prover termination.

Currently writes one ethereum slot (32 bytes) to 0x30000804. This is perfect.

Demo

My ideal demo for the project is a mainnet deployment of a NES Mario prover (input: keypresses, output: first level time-to-complete). There can be a deadline bounty for the fastest time to complete the first level for the duration of the conference with the winner receiving some special NFT.

We can deploy on whatever network will rope the best bounties (or multiple)

This is a sweet demo as it can interest gaming peeps (this solves the anti-cheat problem for certain types of games), NFT peeps, and shows we make something that can run in the wild. It is also visual and easy to comprehend. I think it will capture peoples imagination.

Hackathon Bounties

Optimism

This is an excellent candidate to collect an Optimism bounty since we are hacking directly with their stuff.

It would probably only be eligible for the second one with the games focus.

🎮🌠 Optimism Games & NFT Infrastructure: 2 teams win $ 2,500 per team

From NFT card games to open-world explorations, we want it all! If your project is a game or makes the NFT world better (i.e no code NFT deployers) then you qualify for this prize!

Polygon

Kinda lame but if we deploy there we are eligible. Might be fun if we take the mario route to post a public bounty for the duration of the conference that anyone can claim.

🏊‍♀️ $4,000 prize pool - Deploy at least one smart contract on Polygon’s testnet or mainnet for a share of our prize pool. To be eligible for the prize pool, your contract’s Polygonscan must be linked in the README and have at least 2 successful transactions within the hackathon timeframe. In the README please link to a tweet from a teammate explaining why you built #onPolygon at EthBogota.

Klaytn

Pretty sure these guys are flogs but an easy one to be eligible for and if we take the game option I think their devs could see the appeal of provable exection to produce Metaverse shit..

Building an implementation (any core protocol toolings, ecosystem toolings, NFT & Metaverse use cases, DAO use cases, DeFi use cases, DApps use cases) on Klaytn ecosystem, with Klaytn’s token standard and any ecosystem tools listed in https://github.com/klaytn/awesome-klaytn on any type of Klaytn blockchain infrastructure. (E.g. mainnet, testnet, local Klaytn nodes, service chain, etc.)

🏆 Top 3 Prizes - $10k in total:

​​​​🥇 Champion: $5,000
​​​​🥈 First runner-up: $3,000
​​​​🥉 Second runner-up: $2,000

Ethereum Foundation

We could maybe swing this one… It is definitely a scaling solution and an alternave to ZK stuff (much more flexible)

Privacy & Scaling Exploration

The PSE team explores new use cases for zero-knowledge proofs and other cryptographic primitives through research and proof-of-concepts.

Cartesi

These folk might be interested in what we are working on and it might be worth applying. I think their system is basically the same thing but with RISC-V (https://github.com/cartesi/machine-solidity-step/tree/master/contracts)

The Blockchain OS is building Cartesi Rollups, a modular execution layer that elevates simple smart contracts to decentralized Linux servers. It allows developers to launch highly scalable rollup chains, and code decentralized logic with their favorite languages and software components.

ENS

Use ENS. Get free money.

🤝 Integration Bounty - $5,000

​​​​distributed equally amongst all projects that resolve ENS names and avatars
Last changed by 
 
Willem Olding
0
193

Read more

ChainSafe Cannon R&D Proposed Scope

Deliverable: Cannon Memory Merklization R&D

Nov 15, 2024
CGP Application - RollApp Shielded Pool (RSP)

As shown by CarteZcash, the successor to this project, Cartesi serves as an excellent vehicle to bring privacy features to Ethereum. While CarteZcash focused on a single application that provided shielding Eth transactions, CSP will support any asset including NFTs and to allow different Cartesi application to integrate with the pool to gain privacy features.

Aug 28, 2024
Open Grant Proposal: Delorean Protocol

Project Name:

Aug 9, 2024
Aztec Grant Application - PLUME Library

Verifying data contained within an Ethereum blob requires verifying a KZG proof that the polynomial committed to by the blob opens to a given value(s) at a given point(s).

Jul 12, 2024
Read more from Willem Olding
Published on HackMD