search

AlacrisIO / meta

Internal management of Legicash/Legilogic/Alacris
0 stars 0 forks source link

Allow Alacrity to deal with large state #128

Open fare opened 5 years ago

fare commented 5 years ago

Use Merkle commitments to large data structure so that a contract can verify a computation with a large state. Verification of a step happens in two steps:

  1. decoding some part of the Merklized DAG
  2. evaluating the regular code, and failing the verification if it tries to look outside the DAG.

Sending a step for verification requires:

  1. being able to run the evaluation step without verification, when unchallenged, and/or when looking for a step that requires challenging the other.
  2. being able to run the one step being challenged in a mode that keeps a trace of DAG nodes visited, to build the structure sent to the contract.

Of course, large states are useless without a way to deal with large times, but that's next issue #129.

fare commented 5 years ago

NB: If your code manages 4GB of data, just walking the data structure 4 bytes at a time will take 1 billion operations, which if operation takes 30 minutes to get confirmed will last for 57 millenia. Therefore, to usefully deal with large data structures in finite time, we need a technique to accelerate time just like we can use merklization of balanced trees to compress space. That's #129.