# 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 - Finding new CDMA/error correction codes or [large primes](https://www.eff.org/awards/coop) - Finding [elliptic curve pairings with certain properties](https://github.com/zcash/pasta) - Some initial conditions / params for training a ML algorithm - Scheduling / load balancing 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
112

Read more

Getting a ethereum-consensus build in embeded Rust

This guide was incredibly valuable while figureing this out http://blog.timhutt.co.uk/std-embedded-rust/index.html The goal was to get a version of ethereum-spec.rs to build for an embeded target with no existing standard library or OS syscalls. This must be able to deserialize SSZ encoded Ethereum containers (e.g. state, blocks), do BLS signature verification and compute state transitions. Issues This was a huge pain with lots of little puzzles to solve. I'll try and document them as best as I can Adding #![no_std] to a crate only prevents the crate itself from using std. It doesn't enforce anything about the dependencies so unless every dependency (and their dependencies etc) also doesn't use std it is going to leak in somewhere so we are going to have to build it When building for a non-whitelisted target (e.g not Wasm, windows, mac, linux) then using the std crate requires the #![feature(restricted_std)] crate attribute. This adds a few annoyances:We now need to use nightly rust This needs to be set for every crate that is still using std, not just the root crate. This is a real killer since it means we need to patch any remaing crate that uses std (not just alloc, or core) features.

2/27/2023
On the feasibility of a fault-proof based blockchain bridge

For the hackathon at EthBogota the ChainSafe team developed a new bridge prototype we called Zipline. Like all great hackathon entries it is a bit of a Frankenstein. Inspired by the work on ZK bridges by Succinct Labs^1, it uses the fault proof code from Optimism Cannon^2 and the Eth2 light client code from Snowbridge^3 to build a trustless block header relay for Gasper based chains (e.g. Ethereum and Gnosis Chain) to EVM chains. The logic is fairly straightforward. The Altair hard-fork adds a light-client protocol to the beacon chain that allows resource contrained devices to trustlessly follow along with minimal communication and computational effort. Even this lightweight protocol is too expensive to execute within an EVM runtime and so we use fault proofs to allow off-chain execution of the light client protocol with on-chain settlement. In the final Zipline protocol anyone can submit sync updates along with a sizeable bond. These updates have a challenge period during which anyone can dispute their validity and trigger the dispute resolution game (by also submitting a bond). This game uses bisection of the execution trace to resolve the instruction where fraud may have taken place. The isolated intruction is executed by the chain as the final judgement for if there was fraud or not. It works exactly like fault-proof based rollups (e.g. Optimism, Arbitrum) but instead of executing transactions it is validating the light-client protocol of another chain.

11/3/2022
Zipline - A Trustless Eth2 Bridge Protocol

Background Ethereum Light Client Protocol Since the Altair upgrade Ethereum has a light client protocol that allows a node to follow the network by receiving a single signed update message every ~27 hours. Each sync period (~27 hours) a sync committee of 512 validators is selected. They attest all finalized blocks for their duration and at the end of the sync period a new committee is deterministically selected. A light client node receives SyncUpdate messages which contain: Aggregte BLS signature and participation bitfield Header of the attested block List of pubkeys of next committee Proof committee rotation

10/9/2022
Elrond dev cheat sheet

Smart contracts in Rust All contracts need to begin with the following imports #![no_std] #![no_main] #![allow(unused_attributes)] imports!(); The imports!() macro comes from the elrond-wasm crate and automatically imports everything you need. It includes the following

7/30/2020
Read more from Willem Olding
Published on HackMD