As I've suggested before, I really really think you should also analyze an I2P-like scheme where HSs try really hard to maintain path persistence to their RPs for some fixed time period on the order of an hour (but which can be parameterized and analyzed to give the expected time for guard discovery).
...
In other words: instead of making many fresh RP circuits that can be destroyed, you pick a few RP paths, and maintain them for all circuits for a while, regardless of the activity that your HS sees, and also keep retrying these paths regardless of any circuit failure/teardown you experience. These RP paths would still have guards that last on the order of several months (or whatever duration matches the expected Guard discovery time from the analysis above), but the adversary would lose the ability to move up the chain by causing your circuits to fail from the client end or by driving a ton of activity at you.
I agree that it would be an improvement to remove the ability of an adversary to force the selection of new paths to the RP. For security purposes, it seems the same as adding additional layers of “guards” that have shorter expiration times. And that does suggest one benefit of *shorter* lifetimes for secondary or tertiary guards: you may make expiration faster than an adversary can begin surveillance. The trick is to make the expiration time just under the speed of surveillance. If expiration is too fast, the adversary can just as well wait for you to choose one of his relays.
Suppose the third hop from the HS was changed every hour, and the adversary controlled 1% of all consensus weight. Then it would take a little over 4 days in expectation to choose an adversarial relay and thereby expose the second hop. Assuming the second and first hops rotate slower than surveillance speed, the adversary can at that point move up the chain via surveillance to identify the HS. If the HS can hold onto that third hop for as long as a day, then it would take a little over 14 weeks in expectation for an adversarial relay to be selected.
These number don’t seem great to me, but they do seem like an improvement.
Aaron