1. 30 Oct, 2019 1 commit
  2. 29 Oct, 2019 1 commit
  3. 28 Oct, 2019 1 commit
  4. 25 Jun, 2019 1 commit
  5. 24 Jun, 2019 3 commits
  6. 21 Jun, 2019 1 commit
    • Jakob Botsch Nielsen's avatar
      Refactor to remove compute_block_reward · e7245511
      Jakob Botsch Nielsen authored
      - No longer require that block reward can be computed from height.
      - Remove Chain's dependence on BlockHeader. Instead inline appropriate
        fields in Chain structure.
      - Change step_block to use a BlockHeader now instead of manually
        specifying all the fields. The new BlockHeader now additionally
        contains the creator and reward of that block, so step_block in effect
        contains the reward.
      - These refactorings means that the circulation proof changes. Introduce
        created_blocks to get list of blocks created by user, and prove
        instead that the circulation equals the sum of rewards in blocks.
      - Rename "baker" to a more general "creator" globally
  7. 17 Jun, 2019 1 commit
  8. 14 Jun, 2019 1 commit
  9. 13 Jun, 2019 1 commit
  10. 11 Jun, 2019 1 commit
  11. 10 Jun, 2019 1 commit
  12. 07 Jun, 2019 2 commits
  13. 06 Jun, 2019 1 commit
    • Jakob Botsch Nielsen's avatar
      Remove incoming_txs and outgoing_txs from contract view of chains · 90f0d1e4
      Jakob Botsch Nielsen authored
      This is much more realistic, as allowing contracts to efficiently access
      transaction histories for all addresses is extremely expensive. To do
      this, we
      * Add an account_balance operation in Chain instead
      * Change incoming_txs and outgoing_txs to compute transactions from
      * Require implementations to give a proof-relevant trace, and rework
        proofs to use these, as necessary
  14. 31 May, 2019 1 commit
  15. 27 May, 2019 1 commit
  16. 24 May, 2019 1 commit
  17. 14 May, 2019 1 commit
  18. 09 May, 2019 2 commits
  19. 05 May, 2019 1 commit
  20. 03 May, 2019 2 commits
  21. 02 May, 2019 2 commits
    • Jakob Botsch Nielsen's avatar
      Add a comment for permutation case · 197cbb99
      Jakob Botsch Nielsen authored
    • Jakob Botsch Nielsen's avatar
      Prove a property for the Congress contract · 1b1c9908
      Jakob Botsch Nielsen authored
      This proves a concrete property about any Congress contract deployed to
      a blockchain. More specifically, we show that the count of transactions
      sent out by any Congress contract will always be less than or equal to
      the total number of actions it has receive in "create proposal"
      Thus, this property is stated only over the transactions going in and
      out to the Congress contract.
      To prove this, we reason over incoming and outgoing transactions, the
      internal state of the congress and also the actions in the blockchain
  22. 19 Apr, 2019 1 commit
    • 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 ->
      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
      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
      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 +
             (block_height (block_header env_start))
             (block_height (block_header env_end)))%Z.
  23. 14 Mar, 2019 1 commit
  24. 12 Mar, 2019 2 commits
  25. 10 Mar, 2019 1 commit
    • Jakob Botsch Nielsen's avatar
      Refactor finite map/finite sets and prove map-list/set-list equality · 5e814944
      Jakob Botsch Nielsen authored
      * Pull the functionality we need into a Containers.v file that takes
        care of including the proper implementations of fmaps and fsets.
        Additionally, this file defines notation/new names.
      * Stop using map/set notation for operations. This conflicts with
        lists/record-set and is generally a head-ache.
      * Switch to lists instead of AVL trees for the sets and maps. This
        allows us to prove (assuming proof irrelevance) what we need:
        FSet.of_list (FSet.elements x) = x. Prove this and the equivalent for
        fin maps.
      * Do not use program instances in Oak.v. We can do with instances which
        generate a lot less bloat.
  26. 08 Mar, 2019 1 commit
    • Jakob Botsch Nielsen's avatar
      Implement execution in LocalBlockChain · 357cd8df
      Jakob Botsch Nielsen authored
      This implements a depth first execution of chain actions with support
      for deploying contracts from contracts and calling into other contracts
      recursively. To support these things, contracts need to exhibit a
      bijection of their types from and to OakValue. This machinery is modeled
      with type classes. Then, use this to avoid having to store strongly
      typed contracts anywhere; instead, a contract can be converted to a
      WeakContract instance (using a coercion). The WeakContract verifies that
      messages and states serialize/deserialize correctly and then passes
      everything along to the strongly typed contract under the hood.
  27. 05 Mar, 2019 1 commit
  28. 04 Mar, 2019 2 commits
  29. 22 Feb, 2019 1 commit
  30. 21 Feb, 2019 3 commits