Rendezvous points should return signed proof of the established rend point
Right now our protocol has a vulnerability where you can send an introduce attempt without actually establishing the rendezvous point that you send the onion service toward.
If the establish_rendezvous attempt sent back a signed acknowledgment from the relay, then you could include that signed acknowledgment in your introduce attempt, and the onion service could use it to decide whether to answer.
In the short term, when most people aren't including it, onion services would want to answer even when it's missing. But under load, or in the future where most people should be sending them, onion services could opt to discard introduction attempts that are missing a proof-of-rendezvous-point (or that provide a proof from a relay that the onion service doesn't know about).
This idea needs some crypto design where we want to choose a compact efficient-to-compute thing that the relay can return. And also we want to figure out which key should be signing it. And we probably want some sort of timestamp in the blob so onion services can discard really old ones.
Note that there's some flexibility for how we accomplish this goal, for example, if it helps we could change things so the relay tells the client what rendezvous cookie it can use.
(When I say efficient, I'll note that my relay right now is receiving about 160 establish-rendezvous attempts per second, sustained -- and that's after discarding the ones from tor2web clients.)
I am also open to other smart ideas on how best to resolve the protocol flaw. :)