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 < 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.