Portable Data Challenge

A keepstore server supplies a permission signature to a client that can demonstrate that it has some other means of reading the data. The most obvious demonstration is for the client to send the data to the server. However, this is not optimal: it involves transmitting the entire data block over the network, even if the server already has a copy of the same data.

The mechanism proposed here allows clients and servers to demonstrate that they have read the data recently, without transmitting the data over the network.

Client implementation: "PUT"

1. Obtain an "Etag Salt" value from the server.
  • Perform a PUT request.
  • Store the value of the X-Keep-Etag-Salt response header.
  • Cache the salt value for 1h or until the timestamp embedded in the salt.
  • Salt obtained from one keepstore server can be used on other servers at the same site.
2. Before performing a PUT request, compute the expected Etag using the Etag Salt.
  • Etag = Etag Salt + HMAC_SHA256(Etag Salt, Data)
3. With the PUT request, provide the computed Etag in an If-None-Match header, and set an Expect header.
  • If-None-Match: "Etag"
  • Expect: 100-continue

4. If the server responds "100 Continue", send the data in the request body.

5. If the server responds "200 OK" without "100 Continue", do not send a request body.

6. If the server response has an X-Keep-Etag-Salt header, cache it and use it for subsequent requests.

If there is insufficient support for "100 continue" behavior, send an empty request body. The response will be 200 (with a signed locator in the response body), or 422 (hash mismatch in request) depending on whether the block is already present.

Client implementation: "copy"

A client intending to perform a copy operation between two keepstore servers (whether or not they are on the same cluster) can first try getting a signed locator from the destination server by using a challenge:

1. Get a current Etag Salt value from the destination server (if one is not already known) by doing a PUT operation.

2. Send a HEAD request to the source server, providing the destination server's Etag Salt value in an X-Keep-Etag-Salt header.

3. If the HEAD response has an Etag header, send a PUT request to the destination server with an empty request body and an If-None-Match header containing the Etag value from the source server's HEAD response.

4. If the PUT response is not successful, fall back to a normal copy operation: GET the data from the source server, and send it to the destination server in a PUT request. Include the same If-None-Match header again in the non-empty PUT request, just in case the data appeared on the destination server in between the two PUT requests.

Server implementation: "PUT"

1. Generate a new "Etag Salt" value periodically.
  • The first 8 characters of the salt must be an expiry time, as a hexadecimal-encoded UNIX timestamp, at least 1h in the future.
  • The salt must be accepted by all keepstore servers at the present cluster between now and the expiry time.
  • Example:
    • Let time T = current UNIX timestamp (seconds since 1970)
    • Let period P = seconds before a new salt will be computed
    • Let TTL = minimum duration salt is expected to be valid after being received by client (e.g., 3600)
    • Let expiry time E = T - (T mod P) + P + TTL
    • Let H(x) = big-endian hexadecimal encoding of uint32(x)
    • EtagSalt = H(E) + H(HMAC_SHA256(blob signing key, E))
  • Note: E = T + P + TTL would work too, but subtracting (T mod P) results in a smaller server-side cache of valid EtagSalt values.
2. Set an X-Keep-Etag-Salt header in every response to a PUT request.
  • X-Keep-Etag-Salt: EtagSalt
3. If a PUT request has an If-None-Match header with value SaltedEtag:
  • Ensure SaltedEtag begins with a valid Etag Salt, i.e., the timestamp is betweeen T and T-(T mod P)+P+TTL
  • If so, read the data from disk, and ensure the remainder of SaltedEtag is equal to H(HMAC_SHA256(Etag Salt, Data))
  • If so, respond 200 OK with a signed locator in the response body, without reading the request body.
  • Otherwise, send 100 Continue, read the request body, and proceed as if no If-None-Match header had been provided.

Server implementation: "GET", "HEAD"

1. If the request has an X-Keep-Etag-Salt header with value ForeignEtagSalt:
  • Verify the requested locator's permission signature ("+A[...]") as usual.
  • Do not check whether ForeignEtagSalt is valid.
  • Compute SaltedEtag = H(HMAC_SHA256(ForeignEtagSalt, Data))
  • Set a response header Etag: "SaltedEtag"

Proxy considerations

1. keepproxy must forward If-None-Match request headers and X-Keep-Etag-Salt response headers.

2. keepproxy must not send a 100 Continue response to a client until it receives a 100 Continue response from an upstream server.