freenet/fred-staging — pull request #94 by Thynix (2012-06-06 20:13:27+00:00)
Title: Metropolis-Hastings corrected probes, FCP support, and simulator

These probes route with Metropolis-Hastings correction, and use the number of reported peer locations (enabled by node.publishOurPeersLocation) to determine peers' degrees. If this information is not available it falls back to random walk. It uses Metropolis-Hastings correction along with relatively high hops-to-live values to attempt to make the probe endpoint be as close to a random selection from the entire network as practical. This is in contrast to the current probes which are biased towards well-connected endpoints, and which provide less-useful information in a less-privacy-conscious fashion.

An originating node makes a probe request which contains:

* UID: to match response to request and route it back to the requesting node.
* hopsToLive: number of hops remaining until possibly returning a result. When this value is 1 the node has a 20% chance of responding. This is to protect the the endpoint's plausible deniability.
* type: The type of response requested of the endpoint.

Possible types are:

* Bandwidth: outgoing bandwidth limit in 64-bit integer KiB/s.
* Build: Freenet build number - such as 1407.
* Identifier: identifier and very low-precision 7-day uptime percentage.
* Link lengths: link lengths (difference in location) with peers.
* Store size: size of the datastore in 64-bit integer GiB.
* Uptime: 48-hour or 7-day uptime percentage.

Responses apply Gaussian noise to bandwidth, link lengths, store size, and uptime to further protect anonymity. There are options on the Core settings page to enable or disable responses to each type of probe request, as well as change the identifier.

Possible outcomes - of which all but "Error: Unknown" can occur remotely and are propagated:

* Refusal: the endpoint opted not to respond to the requested type.
* Response: the requested information.
* Error:
* Disconnected: a node being waited on to provide a response disconnected.
* Overload: a node cannot accept the request because its probe DoS protection has tripped.
* Timeout: timed out while waiting for a response.
* Unknown: the local node did not recognize the error used.
* Unrecognized type: a node did not recognize the requested probe type. This can occur anywhere along the chain, not just at the endpoint, because intermediate nodes must recognize the type in order to recognize and return a response.

DoS protection takes the form of rate-limited probe acceptance. Each accepted probe increments a counter which is decremented 60 seconds later. If the counter is at 5, no more probe requests will be accepted. This poses some danger of making a probe unlikely to return a result from bouncing around inside some small cluster of nodes.

Timeout is based on the current HTL and has a constant to account for the probabilistic decrement at HTL = 1 taking longer.

This contains FCP support for the probes and a simulator.