1 of 16

​

Beyond Gas Limit

Computational results on the blockchain

2 of 16

200

60,000

If we ask the program to save them.

Maximum number a simple solidity program managed to count before reaching gas limit.

3 of 16

Verify on the blockchain

Compute the solutions locally.

Blockchain acts as a verifier.

4 of 16

Example: Path length

Is there path of length 10 or less?

  • Computation:
  • Verification:

​

​

5 of 16

Arthur Merlin games

  • Merlin (User)
    • Unlimited computational power.
  • Arthur (Blockchain)
    • Limited (polynomial) computational power.
    • Can throw public dices.
  • Protocols such that Merlin can prove results to Arthur.

6 of 16

Theory

  • On chain computation: A.
  • On chain verification: MA.
  • Problem in NP → YES-answers can be verified in polynomial time.
  • In practice
    • Users also have computational limitations.
    • Even polynomial time tends to be too high for the gas limit.

7 of 16

Computational Court

Parties give computational evidence.

Blockchain acts as a judge.

Adversarial procedure.

8 of 16

Example: Knapasack

  • Computation:
  • Recording result:

​

R1: $8

R2: $15

9 of 16

Example: Matrix multiplication

  • Computation:
  • Recording result:
  • Disproof:

​

= ?

R1:

R2:

10 of 16

General computation

​

  • Anyone can submit a result with a deposit.
  • Save intermediary states of the program to compute the result.
  • Disprove wrong results with interactive verification.
    • Binary search.
    • Use Merkle Tree root hash.

​

11 of 16

General computation

12 of 16

General computation

  • Number of interactions logarithmic to the number of computational steps.
  • Only need of verification if someone tries to cheat.
  • Right result as long as at least one honest party.
  • Must deal with time-outs.
  • Use interactive verification on the verification.
    • Can have any result in NP in logarithmic number of interactions.

​

13 of 16

What for?

  • Complex reputation systems.
    • Decentralised Court.
  • Complex voting systems.
    • Schulze method.
  • Machine Learning.
  • AI living on the blockchain.

​

14 of 16

Thanks!

I am Clément Lesaege

Working on a decentralized court project :

Kleros.io.

​

You can find me at:

clement@lesaege.com

​

15 of 16

Bibliography

​

  • From Smart Contracts to Courts with not so Smart Judges, by C. Reitwiessner.
  • Practical Delegation of Computation using Multiple Servers by R. Canetti, B. Riva and G. Rothblum.

​

16 of 16

Images (CC BY-SA)

  • Knapsack image: Work based on Drake and Keenan Pepper work.
  • Binary search image: Work based on AlwaysAngry work.