guiltygyoza Blog Readings Now

Conceptualizing on-chain trial protocols for knowledge

Special thanks to Yonatan Ben Shimon, Henry Caron, and derked.eth for inspirations.

1- Art patrons outbid others at auctions to earn their proof of patronage. They contribute capital amounts that meet the requirements of the auction conditions.

2- What would an “auction” for proof of inventorship look like? While patronage is capital contribution by nature and is characterized by its capital amount and terms (e.g. one-time payment or periodic payment; payment continuation conditional to art output or unconditional), inventorship is knowledge contribution by nature and is characterized by its soundness and merits. The process of verifiying soundness and merits has nothing to do with auction. A much better name for it is “trial”.

3- In terms of computational complexity, evaluating capital amount and terms of patronage is much simpler than evaluating the soundness and merits of knowledge. On L1, an entire paradigm of auction protocols have been invented for non-fungible tokens linked to off-chain/on-chain artworks. On L2, can we create robust trial protocols for knowledge?

4- For concreteness’s sake, at Topology we have conceptualized a solve2mint system. The system contract presents puzzles to be solved, unique solutions to which yield non-fungible tokens as reward or recognition. Note that the scarcity of mintable tokens in a solve2mint system is determined by the number of solutions to the puzzles, which is much more interesting than the artificial scarcity e.g. 10k NFTs adopted by many projects now. Specific instances of the system can be further categorized into 3 classes:

  • Class C: The puzzle constitutes mathematical equations that can be solved analytically. To mint the reward, one simply eyeballs the smart contract, extracts the equations, solves the equations using some off the shelf solver such as Wolfram Alpha, submits all the solutions and grabs all the rewards. The apparent weakness of a Class C solve2mint system is that analytic solutions can be easily found with off the shelf solvers, which makes the system first-come first-served and prone to sniping.

  • Class B: The puzzle constitutes equations that can only be solved numerically. To mint the reward optimally, one would extract the equations from the contract, build off-chain numerical simulators and search for solutions within the solution space. Class B solve2mint system is much more challenging than Class A, but it straddles across the off-chain/on-chain boundary. The core issue here lies in the fact that minters can leverage infinite compute resource off the blockchain to find solutions to some on-chain problems. To address this problem, some additional form of scarcity has to be introduced. One way is to time-constrain a Class B system. For example, a system may present N random numerical puzzles, all under the same specific family of puzzles, and require a minter to solve all N puzzles within M L2 blocks (or some L2-native units of time), where M >= N.

  • Class A: A trial consists of N randomly constructed Class B puzzles, and minters are required to submit an L2 smart contract that passes the trial. The trial can be broken down to 5 steps: (1) During a trial, the solve2mint contract is provided with the address of a particular solver contract. (2) the solve2mint contract makes N contract calls to the solver contract, each time passing a randomly constructed puzzle, and accepting a solution as return. (3) the solve2mint contract verifies the correctness of the solution. (4) the solve2mint contract repeats step 2-3 for N-1 times and confirms that the solver provides a correct solution each time. (5) the solve2mint contract ranks the solution under some metrics and inserts the solver address into a solution ledger.

5- Class A is particularly interesting because it inherently supports “composable” solution. A solver contract may make use of another library contract for particular data structure or function support. Imagine the puzzles being mazes to be traversed, and a solver contract implements an A* algorithm, using a graph traversal library implemented by someone else.

6- In the context of running solve2mint systems on StarkNet, it helps onboard developers to learn Cairo.

7- While attractive, Class A has at least 2 known issues:

(1) In order to rank solutions (solver contracts), the solve2mint system needs access to some resource meter, such as the hypothetical “step meter” on StarkNet. We have gasleft() in Solidity; there is no counterpart in Cairo at the time of writing.

(2) Without access the solver’s contract content, the solve2mint system cannot prevent “reentrancy attack” - the same solver contract can be resubmitted for scoring. Note that merely having a hash value to solver’s compiled contract is insufficient - a malicious actor can mutate an existing solver contract trivially and qualify for a unique submission with essentially the exact same underlying solver. This issue can be “absorbed” into issue (1) if the solve2mint system accepts a new solver as solution iff its performance is superior to all existing solutions - this invalidates trivial code mutations.

8- One way to bypass issue (1) is to build another layer of abstraction on top of Cairo, where metrics can be measured at arbitrary granularity. For example, one can build a solve2mint system with Christopher, the RTL simulator written in Cairo, where a solution is a Cairo contract encapsulating a digital circuit design that meets some functional and performance requirements. The simulator can quantify the gate usage, latency, and eventually power consumption of the submitted circuit. This does not require having a gasleft() equivalent in Cairo.

9- As a proof of concept, 0xstrat v1 is a Class B solve2mint system based on simple 2d rigid body physics. It has been deployed on StarkNet testnet here. Description of how it works is available in the repo. Below is a screenshot of a local pygame visualization of a simulation run. Note the concept of family: in the case of 0xstrat v1, family is defined as a number that encodes uniquely the sequence of collision events in a simulation run, where collision can occur between two particular circles or between a particular circle and a particular side of the walls. Every family yields only one qualifed solution, which incentivizes minters to search for new solution families.