search

barryWhiteHat / roll_up

scale ethereum with snarks
360 stars 50 forks source link

General dapps wtih roll_up #14

Open barryWhiteHat opened 6 years ago

barryWhiteHat commented 6 years ago

So far we have talked about how to build a NFT with roll_up. Which boils down to basic read and writes.

Here i describe how to do efficiently do general dapps inside roll_up.

So far we have maintained a single merkle tree, which hold the user specific data. But we can add another tree that holds the app specific data. Which can only be updated by the snark according to rules defined in the snark.

So this should work and allow us to build basic applications. However they would be quite expensive to prove. This is because snarks are not good for general dapps with the following limitations

  1. We cannot make loops
  2. If we want to do an IF else we need to check the code inside the if and else loop in both execution paths. So it gets to be quite expensive. Tho there may be some nice ideas https://www.cs.virginia.edu/~sza4uq/index/geppetto.pdf for the if else case.

If we compare this to the EVM we notice that loops are used very rarely as they can be a problem if its impossible to complete loop execution inside the gasBlockLimit. Also in the EVM its rare to have a single master function that uses if loops to define the execution path. Most developers prefer to have a single function per task.

We can do the same with snarks where we have multiple functions defined by different snarks which should cut down the the repeated if code inside the snark. Where either the IF is true or the code fails. We need to think about consensus meacahisms that order which snarks get proved and in which order because there is a possibility of DOS attacks that disallow certain kinds of function calls. More discussion on that https://github.com/barryWhiteHat/roll_up/issues/7

It would be nice to mock up some simple examples inside this new paradigm and see if these ideas hold, if there is anything we have not considered.

PhABC commented 6 years ago

If we have multiple possible snarks that the contract can accept, how does this work with multiple transactions and how does it affect verification cost?

barryWhiteHat commented 6 years ago

So we have 2 merkle trees

  1. Global state that the snark can only edit.
  2. User specific state that each user is able to edit.

In snark each function call is a seperate snark with a uniqe transaction format. You batch transactions per "transaction types"

Verification cost will scale with the size of the gloabal state and the depth of the "user specific state" merkle tree. Proving cost scales the same way.