SerializationObject Tree

Object Tree

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 almost certainly equal.

An object can obviously be referenced from more than one object, and trees may share subtrees. This is particularly useful for versioned data:

Currentversion Previousversion

Directed acyclic graphs

When objects are referenced multiple times, the resulting structure is a directed acyclic graph (DAG). However, since objects are immutable, we can (conceptually) duplicate them, and draw a corresponding tree:

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

In the context of Condensation, we stick to the tree terminology.


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.


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

block 0 block 1 block 2 block 3 head block 4 tail

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.