Two ways to frame it:

Provenance is a DAG, so you get a partial order for free by topological sort. That can be extended to a compatible total order. Then provenance for a node is just its ordering. This kind of mapping from objects to the first N consecutive naturals is also a minimal perfect hash function, which have n log n overhead. We can't navigate the tree to track ancestry, but equality implies identical ancestry.

Alternatively, we could track the whole history in somewhat more bits with a succinct encoding, 2N if it's a binary tree.

In practice, deterministic IDs usually accept a 2^-N collision risk to get log n.