MIME-Version: 1.0
From: Gleb Naumenko <naumenko.gs@gmail.com>
Date: Wed, 23 May 2018 14:03:58 -0700
Message-ID: <CAG0mztWq7RKExwnERQ=-b2Lpq7QYW-4r97RYwnmoLdeNvaVngQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000bab6c4056ce5df68"
Subject: [bitcoin-dev] Peer rotation
Precedence: list

--000000000000bab6c4056ce5df68
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi all,
I'm bringing this up again because since the last time (2014) new papers on
network attacks have been published, and in general I think this is
something that has to be done in one or another form.

### Motivation
It has been shown that revealing the topology of the network may increase
the risk of network-related attacks including partitioning/eclipse (and
consequentially double-spending attacks and attacks on mining) and
deanonymization of transactions.

The current join/leave algorithm makes the network fairly static, which
makes it possible to reconstruct the topology by observing events in the
network (for example, see Dandelion threat model [1] or Exploiting
Transaction Accumulation and Double Spends for Topology Inference in
Bitcoin [2]).
Rotation of the peers is an obvious solution, but there are several
questions to answer.
[The idea has also been discussed here: [3] and in the mailing list: [4],
but ended up not well-researched.]

### Issues with rotation
In P2P network, rotation of peers may cause an additional threat, because
it is safer to stick to the existing connections, due to the fact that
having connections to more different peers increases the chances of
connecting to an attacker. Considering the fact that an attacker can
influence your future behavior including what connections you make, this
may worsen the situation.

One important detail to keep in mind here is that a node may act
legitimately, but just to wait when all of the connections are under the
control of an attacker. So a good idea here is to avoid disconnecting the
most reliable peers.

### Reliable peers
There are several metrics that might be used to consider peers to be
reliable:
Which fraction of recent blocks have a particular node relayed to us?
=E2=80=A6 of recent transactions ... ?
For how long the connection has been maintained?

### Implementation details
Rotation of the outgoing connections only seems to be sufficient yet not
very hard to implement and analyze. In addition, it will cause rotation of
the incoming connections of nodes in the network due to the fact that each
of the outgoing connections is also an incoming connection on the second
side; and due to the scoring mechanism for replacing existing incoming
connections when getting a new one.

Current 8 peers for outgoing connections is an arbitrary number, however,
there is a reason behind keeping a number of outgoing connections low.
Anyway, considering the threat highlighted before it is a good idea to
rotate only a fraction of peers.

Thus, there are 3 values to discuss (N, M, T):
N =E2=80=94 Number of persistent peers which are considered to be trustwort=
hy based
on the metrics as per Section 3
M =E2=80=94 Number of peers to be rotated every T seconds

The trade-off here is how to add enough entropy while not ending up being
connected to dishonest peers only. It is tunable by modifying {N, M}.

Lower bound for T is a value that won=E2=80=99t significantly delay transac=
tion
propagation because of establishing handshakes (and it will not result in
connecting to dishonest peers only), while the upper bound is a value at
which it would be still infeasible to execute an attack.

Figuring out an optimal set {N, M, T} may be done analytically or by
simulation.
I'd be happy to discuss the way of figuring it out.

### Protocol extensions
It may also be useful to keep track of the previous connections (which were
evicted due to the rotation) and get back to those after a while under
certain conditions.

For example, to decrease a chance of connecting to dishonest peers, a peer
may alternate connecting to the brand new peer with connecting to the old
and fairly reliable peer.

### Transactions de-anonymized
Rotation of the peers itself may increase the chance that particular
Bitcoin address or set of transactions would be linked to a node.
In this case either Dandelion [1] or sending own transactions to a static
set of peers (say first 8 peers) may help.

[1] https://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki
[2] https://fc18.ifca.ai/bitcoin/papers/bitcoin18-final10.pdf
[3] https://github.com/bitcoin/bitcoin/pull/4723
[4]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-August/006502.=
html

--000000000000bab6c4056ce5df68
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div>Hi all,</div><div>I&#39;m bringing this up again=
 because since the last time (2014) new papers on network attacks have been=
 published, and in general I think this is something that has to be done in=
 one or another form.</div><div><br></div><div>### Motivation</div><div>It =
has been shown that revealing the topology of the network may increase the =
risk of network-related attacks including partitioning/eclipse (and consequ=
entially double-spending attacks and attacks on mining) and deanonymization=
 of transactions.</div><div><br></div><div>The current join/leave algorithm=
 makes the network fairly static, which makes it possible to reconstruct th=
e topology by observing events in the network (for example, see Dandelion t=
hreat model [1] or Exploiting Transaction Accumulation and Double Spends fo=
r Topology Inference in Bitcoin [2]).</div><div>Rotation of the peers is an=
 obvious solution, but there are several questions to answer.</div><div>[Th=
e idea has also been discussed here: [3] and in the mailing list: [4], but =
ended up not well-researched.]</div><div><br></div><div>### Issues with rot=
ation</div><div>In P2P network, rotation of peers may cause an additional t=
hreat, because it is safer to stick to the existing connections, due to the=
 fact that having connections to more different peers increases the chances=
 of connecting to an attacker. Considering the fact that an attacker can in=
fluence your future behavior including what connections you make, this may =
worsen the situation.</div><div><br></div><div>One important detail to keep=
 in mind here is that a node may act legitimately, but just to wait when al=
l of the connections are under the control of an attacker. So a good idea h=
ere is to avoid disconnecting the most reliable peers.</div><div><br></div>=
<div>### Reliable peers</div><div>There are several metrics that might be u=
sed to consider peers to be reliable:</div><div>Which fraction of recent bl=
ocks have a particular node relayed to us?</div><div>=E2=80=A6 of recent tr=
ansactions ... ?</div><div>For how long the connection has been maintained?=
</div><div><br></div><div>### Implementation details</div><div>Rotation of =
the outgoing connections only seems to be sufficient yet not very hard to i=
mplement and analyze. In addition, it will cause rotation of the incoming c=
onnections of nodes in the network due to the fact that each of the outgoin=
g connections is also an incoming connection on the second side; and due to=
 the scoring mechanism for replacing existing incoming connections when get=
ting a new one.</div><div><br></div><div>Current 8 peers for outgoing conne=
ctions is an arbitrary number, however, there is a reason behind keeping a =
number of outgoing connections low.</div><div>Anyway, considering the threa=
t highlighted before it is a good idea to rotate only a fraction of peers.<=
/div><div><br></div><div>Thus, there are 3 values to discuss (N, M, T):</di=
v><div>N =E2=80=94 Number of persistent peers which are considered to be tr=
ustworthy based on the metrics as per Section 3</div><div>M =E2=80=94 Numbe=
r of peers to be rotated every T seconds</div><div><br></div><div>The trade=
-off here is how to add enough entropy while not ending up being connected =
to dishonest peers only. It is tunable by modifying {N, M}.</div><div><br><=
/div><div>Lower bound for T is a value that won=E2=80=99t significantly del=
ay transaction propagation because of establishing handshakes (and it will =
not result in connecting to dishonest peers only), while the upper bound is=
 a value at which it would be still infeasible to execute an attack.</div><=
div><br></div><div>Figuring out an optimal set {N, M, T} may be done analyt=
ically or by simulation.=C2=A0</div><div>I&#39;d be happy to discuss the wa=
y of figuring it out.<br></div><div><br></div><div>### Protocol extensions<=
/div><div>It may also be useful to keep track of the previous connections (=
which were evicted due to the rotation) and get back to those after a while=
 under certain conditions.</div><div><br></div><div>For example, to decreas=
e a chance of connecting to dishonest peers, a peer may alternate connectin=
g to the brand new peer with connecting to the old and fairly reliable peer=
.</div><div><br></div><div>### Transactions de-anonymized</div><div>Rotatio=
n of the peers itself may increase the chance that particular Bitcoin addre=
ss or set of transactions would be linked to a node.</div><div>In this case=
 either Dandelion [1] or sending own transactions to a static set of peers =
(say first 8 peers) may help.</div><div><br></div><div>[1] <a href=3D"https=
://github.com/mablem8/bips/blob/master/bip-dandelion.mediawiki">https://git=
hub.com/mablem8/bips/blob/master/bip-dandelion.mediawiki</a></div><div>[2] =
<a href=3D"https://fc18.ifca.ai/bitcoin/papers/bitcoin18-final10.pdf">https=
://fc18.ifca.ai/bitcoin/papers/bitcoin18-final10.pdf</a></div><div>[3] <a h=
ref=3D"https://github.com/bitcoin/bitcoin/pull/4723">https://github.com/bit=
coin/bitcoin/pull/4723</a></div><div>[4] <a href=3D"https://lists.linuxfoun=
dation.org/pipermail/bitcoin-dev/2014-August/006502.html">https://lists.lin=
uxfoundation.org/pipermail/bitcoin-dev/2014-August/006502.html</a></div></d=
iv><div><br></div></div>

--000000000000bab6c4056ce5df68--