CONIKS Prefix Merkle Tree - is it necessary to change tree-wide constant for each update folks!

I'm digging through CONIKS papers and it seems that it is an absolute must to select new tree-wide constant for each update (and to rebuild the whole tree respectively) to prevent parallel attacks through past versions of the same tree structure (like parallel birthday attack for instance).

Can't understand why does it matter and what is the attack scenario?

How practical is this attack?

For instance, Google Trillian developers don't select new Tree Id for each update (for Map using CONIKS hasher).

Papers Im looking at:

1) https://eprint.iacr.org/2014/1004.pdf

2) https://eprint.iacr.org/2016/683.pdf

Many thanks!
As Gary Belvin from Trillian replied:


  In Trillian we use a tree wide constant for computing hashes (See
  MapHasher) in order to achieve as close to l bit security as possibe
  and prevent attacks between trees and between different locations
  inside of a tree.
  
  As you've noted, the map does not update the tree nonce for each
  revision of the map. Recomputing the entire map tree for each update
  would be prohibitively expensive and would prevent the Trillian Map
  from being a system that supports near-realtime updates. This tradeoff
  is described in the CONIKS paper, section 3.1
  
  To attack multiple revisions of the same tree, an attacker searches
  for a collision, and then hopes that a future version of the tree
  contains a node that matches the collision. If every leaf node changed
  at every revision, this would be a lot of new nodes to hope for a
  match against. However, in the map, the number of new nodes is &lt; tree
  depth * updates, which grows linearly, not exponentially.
  
  Even if every node of the map changed at each revision, we should
  still be safe. If I'm reading Katz correctly, in order to maintain l
  bit security in a multi-instance setting we need l + log(N) bits in
  the hash function, where N is the total number of map revisions. 256
  bits of hash output should be sufficient to maintain 128 bits of
  security for 2^128 revisions.