Name Resolution & Public Key Fetching

When the client reads an email or sends an email to possibly multiple recipients, it needs to resolve an address name@host1 to a public key. There are two parts to this.

Name Resolution

The first part is resolving the address to a public key hash. Since no server can be trusted alone, we mitigate the trust issue by asking a collection of Scramble servers (aka notaries) for a notarized (signed) response that claims that each notary knows name@host1 is associated with some particular public key hash. This is much like Convergence.io (see http://www.youtube.com/watch?v=Z7Wl2FW2TcA).

Also like Convergence.io, the client doesn't query all the notaries directly, but rather asks its Scramble server (aka primary notary) to dispatch the notary query to the other notaries. This protects the client's privacy.

If the notary is unaware of a name (i.e. a lookup miss), it immediately responds with a negative result & later tries to fetch the public key hash for storage. New Scramble accounts should be seeded into the notary network.

The client may choose to save this resolution result in its contacts list.

Public Key Fetching

The second part is fetching the public key (armor text) given a public hash. Again, the client asks its Scramble server to dispatch the query to the correct secondary Scramble servers.

Why two separate steps?

Public keys are one or two orders of magnitude larger than its hash. Since hash mappings are much cheaper to store, all Scramble servers could potentially know the public key hashes for ALL addresses. The client could also easily store all of its contacts' public key hashes.

Combining both into a single request

The client's Scramble server doesn't need to perform the two steps synchronously. They can be dispatched as a single request per secondary Scramble host thus reducing overall latency.

The request to /publickeys/query has the format:

{
  nameAddresses: "name1@host,name2@host,"                 // Client doesn't know the pubHashes,
                                                          // resolve name via notaries & fetch public keys
  hashAddresses: "name3#hash3@host,name4#hash4@host,...", // Client already knows hashes, just fetch public keys
  notaries:      "notary@mxhost1,notary@mxhost2,...",     // Present if name resolution is necessary
}

The client's MX host then dispatches the request to all the notaries & hosts in one go. Then it returns a simple aggregate response which looks like the following:

{
    nameResolution: {
        "notary@mxhost1": {
            // on success
            result: {
                "name1@host": {
                    pubhash:   "1234567890123456",
                    timestamp: 1380383422,
                    signature: <armor>,
               }
            },
            // on error
            error: <message>
        },
        "notary@mxhost2": ... // same as above
    },
    publicKeys: {
        "name1@host": {publicKey:<armor>,                       // on success
                       error:<"Failed to reach/resolve host">}, // on error
        "name2@host": {publicKey:<armor>,
                       error:<"Failed to reach/resolve host">},
        "name3@host": {publicKey:<armor>,
                       error:<"Wrong hash" or "Failed to reach/resolve host">},
        "name4@host": {publicKey:<armor>,
                       error:<"Wrong hash" or "Failed to reach/resolve host">},
        ...
    }
}

Issues & Considerations

• The Scramble server may have been compromised & provided the client with a bad list of notaries, i.e. no list of notaries, or an older version of the user's notary list.
• This scheme doesn't work unless there are many notaries (e.g. many Scramble servers).
• It's worth noting that Scramble servers are somewhat incentivized to provide notary services -- even for other scramble server addresses -- because it adds value to the network. Yet it isn't clear how notaries will deal with varying levels of abuse. For example, a primary notary may be targeted with a flood of spurious dispatch calls. What then?
• What levels of cache misses are acceptable for a user? If users desire a consensus with no cache misses, then all notaries are required to know ALL addr mappings. If each mapping requires 30 bytes to store (a guesstimate, including indices) then a billion addresses require 30 gigabytes of storage.