Versions are not used for anything and the comment is outdated.

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
  traces
* Require implementations to give a proof-relevant trace, and rework
  proofs to use these, as necessary

This holds for reachable states without this, as proven in
undeployed_contract_no_in_txs.

A state being reachable means there is an execution starting from the
empty state, that ends up in the state.

- Remove 'prove' tactic
- Remove some duplicated tactics and make some proofs more efficient

Match on smaller expressions, making everything much faster. Also
optimize solve_single.

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"
messages.
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
queue.

This split between cases only makes things harder.

These abstract the list structure of the trace away from the events, so
that a trace is now a CursorList of ChainEvent values. The ChainState is
a new type for the environment and queue.

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.

Since we will need to reason over specific inhabitants of traces, this
is required to prove many interesting properties by induction, as
explained to me by Danil Annenkov.

Get rid of the proofs showing that ChainStep and ChainTrace respect
EnvironmentEquiv. ChainTrace no longer respects this in the base case
(this was necessary to define trace_app).

Instead of traces always starting from the empty environment and an
empty queue, they can now start from any environment and queue. This
should hopefully make it simpler for us to define what it means to be a
prefix of a trace.

* 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.

This requires that implementations have a way to determine whether an
address belongs to a contract simply from its value (i.e. from the
format of the address). This is a reasonable expectation and will also
allow contracts to be able to determine whether code will be executed
from actions. Finally, it will also simplify some checks.

Also implement breadth-first variant of local block chain.

Now we can just rewrite with environment equivalences instead of
extracting the chain equivalence from it.

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.

This contains _all_ information that happened in a transaction (for
instance, including the exact contracts that were deployed). The
ChainBuilder exposes the trace of transactions (as FullTx values) that
have happened in the chain.

* Unindent comments after newlines
* Generalize typeclasses with backtick

The ChainBuilder represents the full implementation of a blockchain
containing all operations (such as adding blocks) and state (such as
full contracts with their receive functions). Such a value is
convertible to a Chain (but not vice versa). This is where we will state
general properties about how the block chain behaves temporally.