1. 02 May, 2019 1 commit
  2. 01 May, 2019 3 commits
  3. 29 Apr, 2019 2 commits
  4. 27 Apr, 2019 2 commits
    • Jakob Botsch Nielsen's avatar
      Move ChainStep and ChainTrace to Type · 5221931a
      Jakob Botsch Nielsen authored
      This moves ChainStep and ChainTrace to type. The reason being that our
      proofs will depend on prefixes of traces and it will be very useful (if
      not required) to be able to match on the trace and the steps.
      ChainBuilderType is changed appropriately: now, an implementation just
      needs to prove that ChainTrace empty_env [] cur_env [] is inhabited.
      Thus, ChainTrace can basically be seen as one particular way to order
      the execution so that we reach a state. When it is inhabited, it thus
      means that there exists a proper way to order actions so that we reach
      the state we are in.
      5221931a
    • Jakob Botsch Nielsen's avatar
      62aff812
  5. 26 Apr, 2019 4 commits
  6. 25 Apr, 2019 6 commits
  7. 24 Apr, 2019 1 commit
  8. 23 Apr, 2019 2 commits
    • Jakob Botsch Nielsen's avatar
      Some further cleanups · 7a5e908d
      Jakob Botsch Nielsen authored
      Refactor proof of add_new_block_header and simplify add_block proof.
      7a5e908d
    • Jakob Botsch Nielsen's avatar
      Various refactorings and cleanups · f8adfa8c
      Jakob Botsch Nielsen authored
      * Remove BlockTrace and bake everything into ChainTrace
      * Simplify ChainTrace. Its signature is now
      ChainTrace : Environment -> list Action -> Prop.
      
      These changes will make it easier to reason over traces when proving
      properties about contracts. For one, we can now talk about prefixes of
      the entire chain without the weird distinction between block traces and
      chain traces.
      f8adfa8c
  9. 22 Apr, 2019 7 commits
  10. 19 Apr, 2019 4 commits
    • Jakob Botsch Nielsen's avatar
      Remove some unused leftover code · 70965e72
      Jakob Botsch Nielsen authored
      70965e72
    • Jakob Botsch Nielsen's avatar
      Update for dev Coq · 478221dd
      Jakob Botsch Nielsen authored
      478221dd
    • Jakob Botsch Nielsen's avatar
      ad6bc95a
    • Jakob Botsch Nielsen's avatar
      Specify and prove an initial blockchain semantics · 71ea5d00
      Jakob Botsch Nielsen authored
      This specifies an initial version of blockchain semantics. The semantics
      are specified as several relations:
      
      ChainStep :
        Environment -> Action -> Tx ->
        Environment -> list Action ->
        Prop.
      
      This relation captures the semantics of a single step/action in the
      chain. Such an action can either be a transfer, contract deployment or
      contract call. It specifies that when an action is executed in some
      starting environment, then the blockchain records a transaction (Tx) on
      the chain and performs certain updates to the environment. Finally, the
      step also results in possible new actions to be executed due to contract
      execution.
      
      An environment is for now simply a Chain (which contracts can interact
      with) and a collection of contracts that have been deployed to some
      addresses. The Chain contains various useful operations for contracts
      such as the current block number or ability to query transactions and
      user balances.
      
      For example, for a simple transfer action we may have ChainStep pre act
      tx post []. Then the ChainStep relation will capture that the only thing
      that has changed in the post environment is that tx has been added to
      the chain (so that the appropriate account balances have been updated),
      but for instance also that no new contracts have appeared. Since this is
      just a transfer, there also cannot be any new actions to execute.
      
      The semantics of the environment updates are captured in an abstract
      manner to allow for different implementations of blockchains.
      Specifically, we use an equivalence relation
      EnvironmentEquiv : Environment -> Environment -> Prop and just require
      that the environment is equivalent (under this relation) to an obvious
      implementation of an environment. We implement an obvious blockchain,
      LocalBlockchain, which uses finite maps with log n access times rather
      than the linear maps used in the default semantics.
      
      A single block, when added to a blockchain, consists of a list of these
      actions to execute. In each block this list of actions must then be
      executed (in a correct manner) until no more actions are left. This is
      captured in
      BlockTrace :
        Environment -> list Action ->
        Environment -> list Action -> Prop.
      For all intents and purposes this can be seen as just a transitive
      reflexive closure of the ChainStep relation above. Right now it only
      allows blocks to reduce steps in a depth-first order, but this relation
      should be simple to update to other or more general orders of reduction.
      Note that ChainStep and BlockTrace say nothing about new blocks, but
      only about execution within blocks. The semantics of how blocks are
      added to the chain is captured in
      ChainTrace : Environment -> Environment -> Prop.
      
      This is a collection of block traces and representing additions of
      blocks. At each block added, ChainTrace also captures that the
      environment must be updated accordingly so that contracts can access
      information about block numbers correctly.
      
      Finally, a blockchain must always be able to prove that there is a
      ChainTrace from its initial environment (the genesis blockchain) to its
      current environment.
      
      There are several TODOs left in the semantics:
      1. We need to account for gas and allow execution failures
      2. We need to put restrictions on when contracts can appear as the
      source of actions
      3. We need to capture soundness of the add_block function in blockchain
      implementations
      
      We also provide to sanity checks for these semantics:
      1. We prove them for a simple block chain (LocalBlockchain.v).
      2. We prove a "circulation" theorem for any blockchain satisfying the
      semantics. That is, we show the following theorem:
      
      Theorem chain_trace_circulation
            {env_start env_end : Environment}
            (trace : ChainTrace env_start env_end)
        : circulation env_end =
          (circulation env_start +
           coins_created
             (block_height (block_header env_start))
             (block_height (block_header env_end)))%Z.
      71ea5d00
  11. 09 Apr, 2019 2 commits
  12. 19 Mar, 2019 2 commits
  13. 16 Mar, 2019 1 commit
  14. 14 Mar, 2019 3 commits