Updating append only for oZKS

[Jasleen1]

Recall that an algorithm for generating the append-only proof must take two epochs t_init and t_final, and returns

• unchanged_nodes: an array containing roots of sub-trees of the ozks data structure whose last modification happened at some epoch less than or equal to t_init.
• inserted: an array containing all the leaves inserted between t_init and t_final i.e. the leaves were inserted in epochs [t_init+1, ..., t_final].

Append-only proofs for the oZKS construction can no longer rely on the stored copies of all states. This results in a few problems.

• First of all, if we no longer have a way to store the various root hashes, we have to rely on the auditors to keep all root states ever. To avoid this, we propose that the root hashes for each epoch should be stored in the database that stores the entire tree.
• Secondly, if we only store the last time a node was updated, as we do in the last_epoch field of the HistoryTreeNode struct, we run into an efficiency issue as follows. We can recover the unchanged array by traversing the tree to look for nodes with last_epoch<=t_init. However, in order to recover leaves that were changed between t_init and t_final, we need to traverse through to all leaves.

To address these two problems, propose the following:

• In storage, keep the root's hash for each epoch. Perhaps for this we can create a new Storable.
• In each HistoryTreeNode, node we have two fields: last_epoch (already exists in the current code) and oldest_decendent_ep. The last_epoch denotes the most recent epoch node's hash was updated and oldest_descendent_ep denotes the epoch of descendent of this node with the oldest epoch. In particular, oldest_descendent_ep is defined as follows:

• oldest_descendent_ep = last_epoch if the node is a leaf,
• oldest_descendent_ep = min(left_child.oldest_descendent_ep, right_child.oldest_descendent_ep) otherwise.

• When implementing append_only_proof, to compute unchanged_nodes, the algorithm should do the following:

• Initialize a queue, and start at the root.
• If the current node last_epoch <= t_init, add the node to unchanged_nodes.
• Else, if oldest_descendent_epoch <= t_init if this is not a leaf node add this node's left and right child to the queue, if it is a leaf node, then add this node to unchanged_nodes.
• In any other case, just pop the queue and repeat, unless it's empty.
• If the queue is empty, unchanged_nodes has been computed.

• To compute inserted, do the same thing as when computing unchanged nodes but replacing t_init with t_final. The changes are: only add leaves to inserted and do not do anything for a given node if last_epoch<=t_init.
  The main parts of the proof returned will be (unchanged_nodes, inserted).

[Jasleen1]

Addressed by #206