Tor: Hidden Service Protocol
A hidden service needs to advertise its existence in the Tor network before clients will be able to contact it. Therefore, the service randomly picks some relays, builds circuits to them, and asks them to act as introduction points telling them its public key. Note that in the following figures the green links are circuits rather than direct connections. This makes it impossible for anyone to associate the introduction points with the hidden server's IP address. This is important, because although the introduction points and others are told the hidden service's identity (public key), they must not learn about the hidden server's location (IP address).
In a second step, the hidden service assembles a hidden service descriptor containing the introduction points' addresses and its public key and signs it with its private key. It stores that descriptor on a set of directory servers, again using a circuit that hides the link between the directory server storing the descriptor with the hidden server's IP address. The descriptor will be found by clients requesting XYZ.onion where XYZ is a 16 characters long name that can be uniquely derived from the service's public key. Although it might seem impractical to use an automatically-generated service name, it serves an important goal: Everyone – including the introduction points, the directory servers, and of course the clients – can verify that they are talking to the hidden service. After this step, the hidden service is set up.
A client that wants to contact a hidden service needs to learn about its onion address first. After that, the client can initiate connection establishment by downloading the descriptor from the directory servers. If there is a descriptor for XYZ.onion (the hidden service could also be offline or have left long ago, or there could be a typo in the onion address), the client creates a circuit to another randomly picked relay and asks it to act as rendezvous point, telling it a one-time secret.
Upon setting up the rendezvous point, the client assembles an introduce message (encrypted to the hidden service's public key) including the address of the rendezvous point and the one-time secret. The client sends this message to one of the introduction points, requesting it to deliver it to the hidden service. Again, communication takes place via a circuit, so that nobody can relate sending the introduce message to the client's IP address, ensuring the client's anonymity.
The hidden service decrypts the client's introduce message and finds the address of the rendezvous point and the one-time secret in it. The service creates a circuit to the rendezvous point and sends the one-time secret to it in a rendezvous message.
At this point it is of special importance that the hidden service sticks to the same set of guard nodes for creating new circuits. Otherwise an attacker could run an own relay and force a hidden service to create an arbitrary number of circuits in the hope of the corrupt relay to be picked as entry node and learn the hidden server's IP address via timing analysis. This attack was described by Øverlier and Syverson in their paper titled Locating Hidden Servers.
In the last step, the rendezvous point notifies the client about successful connection establishment. After that, both, client and hidden service can use their circuits to the rendezvous point for communicating with each other. The rendezvous point simply relays (end-to-end encrypted) messages from client to service and vice versa.
One of the reasons for not using the earlier created connection via the introduction point for actual communication is that no single relay should appear to be responsible for a given hidden service. This is why the rendezvous point never learns about the hidden service's identity.
In general, the complete connection between client and hidden service consists of 6 relays: 3 of them were picked by the client with the third being the rendezvous point and the other 3 were picked by the hidden service.
There are more detailed descriptions about the hidden service protocol than this one. See the Tor design paper for an in-depth design description and the rendezvous specification for the message formats.