Allegory Internal Structures and Implementation
An efficient data structure for implementing the Allegory / AllPay protocol.
First, an allegory - A Tale of Two Trees. We essentially have two trees, the first is called the “Tree of Truth” which stores all the state transitions representing the UTXO hand-offs within the allegory protocol. This tree can potentially grow pretty large and is at least over two times the number of names.
The second, called the “Tree of Life” which provides the ‘current’ state of the name-UTXOs. This tree is more compact, and the number of nodes roughly equal the number of names. It can be thought of as a radix name-prefix tree (with a caveat).
Neither tree is balanced, and they grow arbitrarily per demand. The two trees are intertwined and the inter-tree bonds occur at the leaf nodes of the former. For every state transition new leaf nodes are formed in the former, and the bonds are appropriately updated.
◦ Revisions Tree
◦ State Tree
Formally the Tree of Truth is called the ‘Revisions tree’ (state transition via Outputs) and the Tree of Life as the ‘State tree’. The primary purpose of the Revisions tree is to be able to efficiently store & retrieve the chain of Tx-Outputs (directed graph from leaf to genesis) so the light clients can SPV validate the name.
Also, the State tree is needed to provide a direct access entry point to the leaf node for a name lookup. It also serves to efficiently validate that name extensions are unique in both the tree representations, essential for new inserts in the Revisions tree to reflect state transitions.
Each tree has its corresponding root node, the Revisions tree root node represents the name-genesis Utxo. The nodes of both trees are considered immutable i.e. they can be extended but they don’t allow property or intra-tree relationship changes. However, the vertices (inter-tree relationships) from the State tree to the Revisions tree are very much mutable.
Lastly, it is forbidden to pluck fruits from these two trees, i.e. deleting terminal nodes will result in undefined behaviour.