(brainstorming) Anonymous validators: using the onion protocol without using Tor/I2P

[nkeywal]

Tldr: Looking at what it could mean to implement ourselves the onion protocol and to be on our own isolated but anonymous network. It’s a close call but it seems that joining an anonymous network (Tor, I2P, whatever) is the reasonable option.

Here is the onion protocol from wikipedia (https://en.wikipedia.org/wiki/Onion_routing):

• The source does not contact the destination directly but go through a set of nodes (routers in the diagram above).
• Everything is encrypted, so the routers do not know what is the message nor the final destination.
• Especially,the first router does not know if the node sending the message is the actual source or another router. So in our case it doesn't even know if the sender is a validator or not.

Tor actually defines circuits, i.e. long lived connections from a source to a destination, always using the same routers. One of the advantages is that they minimize the cost of establishing connections between the routers: establishing a TCP+TLS connection is expensive. Second advantage: the destination can send a response to the source, without knowing the source. A service can also be made available as a circuit: as such it’s possible to offer a service while remaining anonymous.

The overhead is clear: if you have 3 routers, the message will be sent 4 times instead of one. The bandwidth and the latency will be multiplied by 4. As well, there are 4 times more computers to contact, with a low probability that the connection is already established. So the connection cost increases dramatically. However, these points may not to be an issue for us:

• The attestations are small, so the bandwidth will not be an issue
• QUIC may help to minimize the connection cost (the 0 RTT feature).
• Tor circuit could help, if we accept to use multiple times the same routers for multiple attestations for example.

This allows to create a lot of noise that would make the system difficult to attack. Routers do not have to be on the same shard, so the p2p Sybil attack par shard does not apply.

It’s still possible for multiple participants to cooperate to identify a validator: if all the routers of a single message are byzantine then they can cooperate and identify the validator. The protection against this is to have a variable number of routers and more routers. Still statistical analysis could be possible: a validator will send more messages than a simple router. There is a solution for this as well (asking non validator nodes to send random data). The main point is that there are many possible attacks, so using an existing solution or at least design is safer.

As well, if some routers are byzantine and drop the messages, the more routers we use to send a message the less chance we have to successfully send this message. Here is a graph when the sender sends its message 50 times:

In other words, with a 3 routers and 50% of byzantine nodes on the p2p network, 10% of the messages won’t be received by any honest node.

This can be work-arounded if the attesters wait for an answer from the destination (i.e. establish a circuit): this way the sender can detect if the message was dropped by one of the routers. But the security is still inferior, because the byzantine nodes can adapt themselves. Their strategy will be:

• Forward the message only if the next hop is a byzantine node
• Byzantine final nodes confirm the reception (but actually discard the message).

If we add this curve to the previous graph we see it helps but it’s not a game changer:

However, even with this strategy it’s still difficult for the attacker to censor only some specific attesters: it’s all-or-nothing strategy.

Conclusion:

• The routers can be on all shards, so attacking a single shard is not possible at the onion-routing level.
• We can hide not only the link public key <-> ip address but as well the fact that a given node is a validator.
• Adding an onion based protocol makes DoS easier but censorship remains difficult.
• Even if the DoS are easier they’re still expensive: it requires a few thousand of nodes, and it should still be possible to add reputation mechanisms to make them complicated.
• In all cases there are a lot of options available for the attacker.
• In the scenario above, attacks are easier because the network is isolated (ethv2) and there is a single type of message (attestation). Adding multiple message types (transactions, …) and being merged with another network (i.e. I2P or something similar) would make things safer.

octave code used for the graph:
callCt = 50
function retval = ee (ot)
  t = 1 - ot;
  honestConf = t .^4;
  byzConf = t.^3 .* ot + t.^2 .* ot.^2 + t .* ot.^3;
  noConf = 1 - (honestConf + byzConf);
  retval = honestConf ./ (1 - noConf);
endfunction;
t = linspace(0,1,100);
plot (t, 1 - ( 1- ee(t)).^callCt, t,  1 - ( 1- (1-t).^4).^callCt, t, 1 - ( 1- (1-t).^3).^callCt, t,   1 - ( 1- (1-t).^1).^callCt  )
h = legend ({"onion - 3 routers with confirmations", "onion - 3 routers", "onion - 2 routers", "no onion"});
legend (h, "location", "southwest");
xlabel("ratio of byzantine nodes");
ylabel(strcat("probability (when contacting ",num2str(callCt)," nodes)"));
title(strcat("probability that the message is received by at least one honest node (",num2str(callCt)," calls)"));