SerializationObject Tree

Object Tree mature

Through the hash list, an object may span a tree:

3a229f... ba6eb4... 6f0146... a83e31... 409688... 3a229f... ba6eb4... 6f0146... a83e31...   2 2 0 1 0 82b79d... ...

Each node in that tree is an object, spanning its own subtree. The hash of a tree is simply the hash of its root object. Two trees with the same hash are most likely equal.

An object can obviously be referenced from more than one object. This is particularly useful for versioned data, as common subtrees can be shared:

Current version Previous version

The data tree implementation takes advantage of this.

Graph properties

Objects can only form acyclic graphs. Constructing a loop (cycle) would require constructing a hash collision.

To understand that, assume an object A that references an object B. Hence, A contains the SHA-256 sum of B. To create a back-reference from B to A, we would need to construct a new object B' containing the hash of A, and yielding the same hash as B, which is computationally infeasible.

For the same reason, an object cannot reference itself.

Objects can be referenced by more than one other object, however. In that case, the resulting structure is still a directed acyclic graph, but not a tree:

a5195c... a5195c... a5195c... Directed acyclic graph Corresponding tree

Since objects are immutable, we can (conceptually) duplicate such objects, and draw a corresponding tree. Every use of the object is then regarded as a separate instance, that just happens to have the same content.


The special case where objects form a chain is known as blockchain:

The hash of the head object of the blockchain uniquely identifies the blockchain. New blocks can easily be prepended to the head, but no block can be modified or inserted anywhere else in the chain.