plus/minus epsilon

SEAD, the Secure Efficient Ad hoc Distance vector routing protocol, is a recent secure ad-hoc routing protocol designed to use symmetric cryptographic primitives almost exclusively. Relying on symmetric cryptography, rather than asymmetric often requires 3 to 4 orders of magnitude less computation with a negligible increase in storage or network overhead.

However, while there has been a lot of work to make SEAD as efficient as possible, the application of distributed hash tables presents several problems that SEAD in its current form isn't equipped to handle. Mainly, that SEAD has no way to purge old entries from routing tables. However, it also must be decided if the protocol should be optimized to reduce time complexity or to reduce space complexity, because (as would be expected) the two goals sharply conflict.

It's best to have read the original paper on SEAD, along with the author's followup, first.

Reducing Time Complexity

Reducing the time complexity of the protocol has been the goal of most previous optimizations proposed for SEAD because nodes in the network are often assumed to have extremely limited processing capabilities.

The primary way to bound verification overhead is to, instead of having one long hash chain, have a hash chain for each sequence number up to some upper bound and then commit to all of them at the same time through the use of a Merkle tree. The root of the Merkle tree along with a tag noting the sequence numbers this tree is valid for can then be signed with a more expensive primitive, like a digital signature.

A MW-Chain can also be added as the last value committed to by the tree. When a tree has expired, a new one can be generated and then authenticated with a signature produced by the MW-Chain. If published along with a proof that the root value of the MW-Chain was committed to by the previous Merkle tree, a node who has already verified an asymmetric signature on the previous tree can prove the new tree is valid by checking that the MW-Chain was committed to by the previous tree and that it correctly signs the new root.

MW-Chains have the advantage that, because each tree only authenticates its own successor, the sequence numbers that each are valid for don't need to be authenticated in any way. However, if a node misses an entire tree-worth of sequence numbers (due to rapid updates, attempted attacks, or even if the node has just joined a long-standing network), the node will have to resort to verifying the asymmetric signature.

Computation, then, is only reduced in the absence of an attacker and a node can still be overwhelmed by being forced to verify an arbitrarily large number of invalid asymmetric signatures. It should be noted, however, that the required computation is still much less than the original method.

It should be reiterated that it's important the sequence numbers a Merkle tree is valid for be signed along with the root of the tree to prevent an attacker from providing old/expired trees as authentication for higher sequence numbers. In a similar spirit, when proving commitment to a value, most implementations of Merkle trees specify whether each value along the way to the root should be put on the left or the right. These markers can be used to verifiably id each committed value, such that the first committed value is the anchor of the hash (tree) chain that authenticates sequence number 0, the second committed value is the only anchor that authenticated sequence number 1, and so on. For example, if each given value in the proof is marked to go on the right, then the anchor is on the far left--id number 0--therefore, it is the anchor for the hash (tree) chain of sequence number 0.

Given all of this, each entry in a node's routing table, will contain something along the lines of:

1. metric - An unsigned integer. Metric. Measures the distance from the source.
2. sq - An unsigned integer. Sequence number.
3. next - A neighbor's node ID. Next node on the shortest path to this destination.
4. element - A SHA1 auth. Either from a hash chain or a hash tree chain.
5. proof - A set of hashes that proves the anchor of the current hash (tree) chain is committed to by the root.
6. verification - A MW-Chain signature and a proof that the public key was committed to by the previous root. Cheap verification.
7. signature - An asymmetric signature of the current root and the sequence numbers this tree is valid for. Expensive verification.

In the entry, anchor and root are referenced but never specified. This is because they can be omitted to save space and only negligibly increase the amount of required computation.

The algorithm to verify such an entry--disregarding issues of type and whether or not the offered entry is actually better than the current entry--is:

# max is the maximum length of a hash (tree) chain
# num is he number of sequence numbers each tree authenticates
# id(proof) derives the id of a value from its proof
# applyMT(val, proof) applies a proof to a value.  Derives the root of the tree.
# applyMWC(msg, sig) applies a MW-Chain signature to a value.  Derives the public key.

if metric > max then return false
if id(proof) isnt (sq % num) then retrun false

anchor = H(max - metric, element) # H(n, ...) means chain H(...) n times.
root = apply(anchor, proof)

newTreeId = floor(sq / num)
oldTreeId = floor(table[id].sq / num)

# If there's previous and recent record of this peer.
# Any entry with a lower sequence number should have been thrown away already.
if table[id]? and newTreeId is (oldTreeId + 1)
    # verification[0] is the MW-Chain signature.
    # verification[1] is the proof of commitment.

    # MW-Chains are always the last value.
    if num isnt id(verification[1]) then return false

    cand = applyMWC(newTreeId + root, verification[0])
    cand = applyMT(cand, verification[1])

    # Accept if verification correctly computes the old root.  The old root
    # should be cached, but not sent.
    ok = cand is table[id].root
else if table[id]? and newTreeId is oldTreeId
    ok = root is table[id].root
else # There's no previous/recent record.
    ok = ... # Verify the asymmetric signature on the root.

return ok

Reducing Space Complexity

The optimizations above, while they greatly reduce the amount of computation required, can take anywhere from half a kilobyte to several kilobytes of memory per routing entry depending on the configuration of the network and the efficiency of the language's implementation. Granted, nodes in the network might not have an excess of processing capability, but in the event of a network with several million connected nodes, such large entries aren't practical either. Hence, it may be worthwhile to establish a lower bound on the size of an individual routing entry.

The above schema does a fairly good job of omitting unneeded data, so by stripping the performance optimizations, we get a schema along the lines of:

1. metric - Rarely exceeds 255, yielding uint8.
2. sq - Can be arbitrarily large, capped at uint32.
3. next - A neighbor's node ID. A convenient trick is to use the node's ID as its public key. A 112-bit elliptic curve yields a 14 byte public key.*
4. element - A SHA1 hash. Yields 20 bytes.
5. signature - An asymmetric signature of the anchor and the sequence numbers this chain is valid for. Yields 56 bytes.

• While a 112-bit elliptic curve isn't typically considered secure, the last known published attack on a 112-bit curve used an excess of computer resources and took approximately four months. While this would be a threat to long-lived keys, nodes in an ad-hoc network are so ephemeral they rarely use the same key for more than a few hours.

Summing up the sizes of each field shows that an entry is 95 bytes in its most space-efficient form. In 2GB of memory, we can store approximately 22 million unique peer records. This is disregarding space required by any caches, other control structures, and the memory of the application itself (which may grow in parallel with the routing table)--not to mention that periodically dumping 2GB of records to N peers is completely impractical as well.

However, through more interactive protocols, it is possible to reduce the bandwidth used in periodic updates. The first that comes to mind is only publishing a node's id, metric, and sequence number (perhaps some other data as well). The receiving node can then, with very little effort, determine if an entry should be requested for full verification.

An alternative method that could be implemented would be something similar to Dynamo's Replica Synchronization, where each node's entire routing table is committed to by a Merkle tree. For two nodes to determine if their tables are synchronized, they simply need to verify that the root nodes of the Merkle trees equal. If not, they can (in logarithmic time and space) identify which entries differ by following any discrepancies down to the foot of the tree. Granted, this approach might be difficult to implement in a way that's resistant to protocol breaches.

Adding Disconnects to SEAD

At the moment, SEAD accumulates old records of disconnected peers in the event that the peer has simply changed position in the network, and that new routing entries containing information on the peer's location will arrive. However, in the vast majority of P2P protocols, it's essential that nodes have a way to purge old data to preserve resources.

The answer turns out to be fairly succinct: on the creation of each routing entry, a timestamp should be added and signed by any authentication mechanisms (the verification and signature keys in the above schemas). If the newest record a node has of a peer (or a record the node has been sent by an adjacent peer) is reported older than its TTL, then the node can freely discard the entry. This method enforces the strictest practical definition of "being connected": some node in the network has the private key belonging to this public key and is performing the minimum required work of keeping its routing entry updated. Of course, loose time synchronization is required for disconnects to reliably work, meaning there needs to be a cluster-wide trusted time server for nodes to synchronize with at startup.

For a node to prevent itself from being discarded by the network, it must periodically push up its sequence number at minimum once per X seconds (as defined by the cluster). Calculating the TTL then, is as follows:

In the simple, space-efficient schema in section two, a new signature is calculated for each sequence number, so the TTL is simply:

TTL = max(interval, (m * period)) + grace

Where interval is the interval on which nodes should increase their sequence number, m is the maximum network diameter, period is the interval on which nodes dump their routing tables to each other, and grace is a (usually small) extra delay to account for other possible delays in the network. This TTL should slightly over-approximate the maximum amount of time it can take a node to completely distribute an updated routing entry.

In the time-efficient schema, however, a timestamp can't be verified on each increase in sequence number--only each time one tree is exchanged for another, leading to systematically greater TTLs (albeit, not by enough to nullify all the advantages the ability to purge entries offers). The TTL is then defined as:

TTL = max((n * interval), (m * period)) + grace

Where n is the number of sequence numbers each tree commits to.