Before the guided tour puzzle can start, N tour guides has to be set up in the system, where N \ge 2. Meanwhile, the server establishes a
shared secret k_{js} with each tour guide G_{j} using a
secure channel, where 0\leq j. The server keeps a short-lived secret K_{s} for computing the first hash value that is returned to the client as part of a puzzle message. A puzzle message also contains the length of the tour L, which is used to control the difficulty of a guided tour puzzle. The figure shows an example of a guided tour when N=2 and L=5. The details of the each protocol step of the guided tour puzzle protocol is explained in the following. •
Service request: A client x sends a service request to the server. If the server load is normal, the client's request is serviced as usual; if the server is overloaded, then it proceeds to the
initial puzzle generation step. •
Initial puzzle generation: the server replies to the client x with a puzzle message that informs the client to complete a guided tour. The puzzle message contains the length of the tour L and a hash value h_0. The server computes h_0 using the following formula: ::h_{0} = hash(A_{x}\; ||\; L\; ||\; ts\; ||\; K_{s}) :where, || means concatenation, A_{x} is the address (or any unique value) of the client x, ts is a coarse timestamp, and hash is a
cryptographic hash function such as
SHA-1. •
Puzzle solving: A client computes the index of the tour guide at the l-th stop of its tour using the following formula: ::S_{l}=(h_{l-1}\; mod\; N) :where, 0 . When contacted by a client x, a tour guide G_j computes a hash value h_{l} (0 ) using the formula: ::h_{l} = hash(h_{l-1}\; ||\; l\; ||\; L\; ||\; A_{x}\; ||\; ts\; ||\; k_{js}) :where, l means the l-th stop of the client's tour, k_{js} is the shared key between the tour guide G_{j} and the server. After client x receives the server's reply message, it starts a guided tour by computing the index S_{1} of the first tour guide using formula for S_l. The client then sends a set of values (h_0, 1, L) to the tour guide G_{S_1}, where the second value denotes which stop of a tour the client is currently at. As a response, the client receives a hash value h_1 from the tour guide G_{S_1}, where h_1 is computed using the formula for h_l. The client x repeats this process L-1 more times and contacts the tour guides G_{S_2}, G_{S_3}, ..., G_{S_L}. The reply message from the last-stop tour guide G_{S_L} contains the last hash value h_L, and the client x sends (h_0,\; h_L) to the server as the puzzle answer. •
Puzzle verification: when the server receives a request from client x with a puzzle answer (h'_{0}, h'_{L}) attached, it first checks to see if h'_{0} is equal to the h_{0} it computed using the formula for h_0. If so, the server computes h_L by repeatedly using the formula for h_l, and verifies that h'_{L} is equal to h_{L}. If both hash values are valid, the server allocates resources to process the client's request. Since the server knows the shared keys k_{1s}, k_{2s}, \dots, k_{Ns}, it can compute the chain of hashes h_1, h_2, ..., h_L without contacting any tour guide. A loose time synchronization between the server and tour guides is required in order to compute the same hash value at the server and tour guides. == Comparison to other puzzle protocols ==