Errors in the Levine 2017 paper on attacks against Freenet

This is the equation Levine et al. use in their 2017 text.

This is a probability calculation that models how likely it is that the originating node is one hop apart (H1) when receiving a number of requests (r).

By using a binomial distribution (B), they model the pobability of receiving a specific number of requests from a node with a given number of peers.

Let’s take it apart:

• H1 means "one hop apart": a downloader.
• H2 means "two hops apart": a relayer.
• r is the number of requests received.
• T is the total number of requests for the file sent by a downloader.
• g is the number of peers of the observed node.
• g+1 is the number of possible downloaders: the connected node and each of its peers.
• 1/g is the definition of even share.
• 1/gh is the definition of taking even share twice (h is the guessed number of peers of a node two steps away).

Pr(H1|r) means the probability that the node is a downloader if r requests were observed (H1: one hop apart).

B(r; T, 1/g) means: the probability of receiving r requests from a downloader. B(r; T, 1/gh) means: the probability of receiving r requests from a relayer.

Using 1/g and 1/gh in there is why they must assume that Freenet uses even share. Since Freenet does no use even share, their math is wrong and their whole calculation breaks apart. More on that later.

They now weight the probability of the downloader by 1/g+1, because it is only one node. Then they weight the probability of the relayer-case by g/g+1, because there are then g possible actual sources.

This all looks good, except for the definition of g and h (the most influencial variables in the formula).

A correct formula would not use the number of peers for g and h.

For the downloader it would replace (1/g) with the fraction of FOAFs.

For the relayer it would use replace (1/h: with the fraction of FOAFs and (1/g) with a weighted fraction of FOAFs with higher weight to FOAFs close to the location of the request, because here requests are already likely to be specialized by location. If the connected node is close to the locations of the received requests, up to 70% of its FOAFs will have to get higher weight.

This latter part is only required since the fix in response to the 2014 paper. Before 2014 this could be ignored, because the link length distribution was broken.

It would still possible to scale g for the downloader and h for the relayer to account for the likely number of FOAFs assuming a known distribution of peer-counts. This part of the formula they could salvage (it is currently wrong).

But g for the relayer is plain wrong, because it does not take weighting of closeness to the request into account. In other words: for a relayer they can no longer assume a flat distribution of requests in location space.

Since g and h are wrong the whole calculation is wrong. You cannot just fudge binomial coefficients and then assume that the result is still correct, because binomials are extremely sensitive to these coefficients.

The factor (1/g)^r is exponential in 1/g.

To check how sensitive their code really is to the factors I wrote a small tool that does their calculation — you need Guile Scheme to run it.

;; base n!/(n! * (n-k)!) implementation
(define (factorial n)
  (let lp ((m n)
           (res 1))
    (if (zero? m) res
        (lp (1- m)
            (* m res)))))


(define (nük n k)
  (if (> k n) 0
      (/ (factorial n)
         (factorial k)
         (factorial (- n k)))))

(define (binom p n k)
    (* (nük n k)
       (expt p k)
       (expt (- 1 p) (- n k))))

(define (B k n p) (binom p n k))

(define (pr_levine r T g h)
  (exact->inexact
    (/ (* (/ 1 (+ g 1)) (B r T (/ 1 g)))
       (+ (* (/ 1 (+ g 1)) (B r T (/ 1 g)))
          (* (/ g (+ g 1)) (B r T (/ 1 (* g h))))))))

(h is set by Levine et al. to 8 (peers) for the real downloader, a conservative setting)

But since this math uses even share, it is wrong.

The minimal adjustment to have the formula not fully wrong before 2014¹ would be to approximate FOAF routing by taking into account that their node does not have the average peer count of 30 but 60 (similar to the observed node).

This can be done very roughly² by changing 1/g to 2/g and changes connected to that, because their probability to receive any given packet is twice as high as for an average node.

(define (pr_fast_observer r T g h)
  (exact->inexact
    (/ (* (/ 2 (+ g 2)) (B r T (/ 2 g)))
       (+ (* (/ 2 (+ g 2)) (B r T (/ 2 g)))
          (* (/ g (+ g 2)) (B r T (/ 2 (* g h))))))))

I ran this against a scenario where their original formula yielded almost 100% probability that this is the downloader and the result was less than 0.0000001%: less than one in a billion.

Translated: compared to the scenario where the real downloader has 8 peers, by the semi-fixed math there’s no chance that an observed node with these results was the downloader.

Now they could argue that 8 peers is too little for the real dowloader. That would then drive the probabilities up again. But then they are in the game of fudging statistics to yield the result they want.

And this fix still misses the adjustments for more targeted routing since the fixes in response to the 2014 paper by Roos et al which would drive the probabilities lower again.

Note also that this is so heavily dependent on the factors of the binomials, that anything it says will fake a much too high precision: it misses the messy real world with changing backoff, different routing, malicious patched nodes that claim more bandwidth than they should get, and so forth.

It hides the probability that any result they get can have been a random fluctuation in routing.

The math is broken without even share, but there is the claim that Freenet uses random peer selection and therefore even share request distribution. They claim that Roos et al. 2014 shows that.

The Roos paper never stated that there is even share routing. It said that there was over 70% random routing. Random routing does not mean even share.

Random routing means that while selection is actually biased towards larger nodes (via FOAF), it does not move towards the general goal.

This is as if you walked around a city and at crossings you selected the direction by following a car chosen at random.

You’d think at every crossing:

• “Where should I go? That car looks nice, I’ll follow it!”

If you do that, you will most times choose large roads, not small sideroads, because there are more cars driving along the large roads. By selecting a car to follow at random, you are most likely to walk on large roads, because there are more cars driving on those large roads than on small roads.

You do not move towards your goal, though.

This problem (not moving towards your goal because most time you select a car at random) is what Roos 2014 described: over 70% of our routing decisions were effectively like that and less than 30% were actually directed.³

The preferred selection of the larger road is what Levine et al. ignore. It has been true before 2014 and it is still true today.

What changed after 2014 is the layout of the roads: now at least 70% of the roads are connected such that you can actually navigate by following cars with a license plate close to your goal.

Why does it so often come down to cars when searching an explanation that all can understand?

That’s a nice analogy, but how can one check whether Freenet operates this way? There is the claim that Freenet developers intended to have FOAF routing, but that this is not what is actually happening.

Regardless of who asks, I would ask them to look into the sourcecode: the absolute law of software. That says clearly in PeerManager.java:

for(int i = 0; i < peers.length; i++) { // this checks every peer
    PeerNode p = peers[i]; // the peer being checked
    // ...
    double l = p.getClosestPeerLocation(target, excludeLocations);
    // ^ this asks for the FOAF that is closest to the target.
    // ...
    if(!backedOff && (diff < closestNotBackedOffDistance // ...
        closestNotBackedOffDistance = diff;
        closestNotBackedOff = p; // here the peer is remembered if its FOAF is best
    // ...
PeerNode best = closestNotBackedOff;
// ^ here the best peer is chosen based on having the best FOAF location 

and p.getClosestPeerLocation() that is run for every single peer says:

locs = currentPeersLocation; // these are the FOAFs: all the peers of that peer
// ...
closest = findClosestLocation(locs, l); // binary search in the list of FOAFs
// ...
return locs[closest]; // this is the peer of that peer closest to the target — the FOAF

That is how Freenet determines which node to choose: Check for every single peer every FOAF it reported to see whether it is closer than the best FOAF of any other peer. Send the packet to the peer (that’s not backed off) with the closest FOAF.

These are the laws of Freenet routing. The nodes cannot disobey them, except if someone changes these laws for their node (by patching it).

This is not even share.

And there is no "they intended to". What Freenet actually does is right there in the source-code: the absolute law how a program operates. It cannot disobey that, it cannot bend that. Laws for programs are absolute and unbending. They can contain bugs, but that’s why they get reviewed.

The core of the routing are just these 10 lines of code (not counting comments, the parts of lines starting at //). There are contests for writing obfuscated code that does something else than what it seems to do, but there’s no obfuscation here: the code is plain and simple and the program must obey it.

This is software, and the laws of software do not bend.

OK, but did you actually measure that? Maybe there is a bug you did not see!

Freenet is used by people with very different internet connection speeds. It can utilize speeds from 10kiB/s (roughly a phone line) to 1000kiB/s (this can stream HD video).⁴

But the peer count only increases with the square root of the bandwidth, so a node with 10kiB/s gets 5 peers, a node with 100kiB gets 17 peers and a node with 1000kiB/s gets 55 peers.

If it did even share, nodes with 5 peers would constantly be overloaded, because they would receive on average 25 kiB/s of messages (5kiB/s in data per connection), more than 2x as much as their total bandwidth.

But nodes with 5 peers work and are not constantly overloaded.

So Freenet uses FOAF routing — and this is measured constantly, because otherwise the Freenet network would break down.

But what exactly would you measure (test)?

You would measure backoff. Since slower nodes would be overloaded by faster nodes, you’d expect a backoff well above 30%. It’s convenient that Levine et al. 2020 measured backoff and found only about 11% backoff. They just did not note that by measuring this they proved that Freenet does not use even share routing.

Also (observable locally) since the average node in Freenet has 30 peers, if Freenet used even share you would expect a node with 15 peers to be constantly in backoff / overload. I run such a slower node (because my internet speed is limited) and this is not the case.

The Levine group tested their formula in their 2020 text for false positives, and it detected their own nodes twice.

They claim that this is a low false positives rate, because they did not point out their own nodes much more often, but in fact it means that if they had waited a bit longer, they would have reported themselves as downloaders (they wait for three marked runs), even though it is certain that their nodes did not download any of the files.

Their own nodes were pointed out by their method not just once but twice. Since they monitor thousands of other nodes, over time they will find more and more innocents.

And most of their nodes had much fewer peers than the over 60 which some people had whom they targeted (their text implies that most Levine nodes had around 30 peers).

If actually guilty people use darknet-mode or just block the Levine nodes (there are some patches floating around that would have that effect), then the Levine method will only find relayers, because they cannot connect to the actual downloaders directly, so their method cannot ever point to the actual dowloader.

They will only be able to target the clueless and the innocent.

And since they do this knowingly (they know about the debunking here), that’s actually despicable.

Freenet does not use even share routing and the Levine method is wrong.