If the goal is to prevent introduction points from guessing the number of instances because of multiple instances using the same introduction points, shouldn't this scheme work?
1. On deployment, all instances of a hidden service have a copy of a secret bitstring (maybe the private key for the hidden service, maybe an additional secret) and the number of instances N. Every instance also has a unique instance ID k in the range [0, N-1].
2. When selecting an introduction point, an instance only considers candidates for which
hash(introduction-point-address || shared-secret) = k mod N.
With this system no two instances will ever connect to the same introduction point, and it doesn't require any synchronisation between the instances other than the initial instance ID assignation. But it relies on there being enough potential introduction points for which the equality holds.
This will also mean that an introduction point knows that it is always being used by the same instance of a hidden service. If you want to avoid this you could add the current day or hour or random time period to the hashed value, but then you might get a collision when a new time period begins.
Apologies if this has already been discussed.
--ll