Transactions draft

Adding a hash to a box is an atomic operation, which either fails or succeeds. Along with a forward-moving data structure, every modification is a transaction.

Recall that modifications are carried out in three steps:

  1. The client constructs a modified tree, and submits it to the store.
  2. The client adds the new tree to the box.
  3. The client removes the old tree from the box.

The private box thereby goes through tree states:

private box A private box A B private box A B A A ⊗ B = B B

The transaction is complete after the (atomic) addition.

Removal does not change the state of the data any more, but can be thought of as a cleanup step. If removal fails, the next read operation will incur some overhead, since both versions need to be read and merged. The result will be the same, however.

Note that no locking is involved at any point in the transaction.