[Bitcoin-development] Outbound connections rotation

[Bitcoin-development] Outbound connections rotation

[Ivan Pustogarov]

Hi there,

I'd like to start a discussion on periodic rotation of outbound connections.
E.g. every 2-10 minutes an outbound connections is dropped and replaced
by a new one.

Motivation:
Each bitcoin non-UPnP client behind NAT has 8 outbound connections
which change only rarely (due to occasional remote side disconnections).
A subset of these 8 entry nodes uniquely identifies a user.
An attacker can listen for transactions in Bitcoin network and for each
transaction record the first 8 peers which forwarded the transaction.
If two distinct transactions (with unrelated bitcoin addresses)
come from the same set of 8 peers, the attacker can conclude that they
originated from the same user. This gives another method (in addition
to transaction graph analysis) for an attacker to link different BC
addresses of the same user.
Also note that by default bitcoin clients advertise their public IP
addresses. The attacker can link the advertised IP's to corresponding
8 entry nodes and use it to deanonymise Bitcoin clients.

If a bitcoin client periodically rotates his set of outbound
connections, his 8-peers fingerprint is blurred over time.

Corresponding pull request is #4723.

Some details are here: https://www.cryptolux.org/index.php/Bitcoin

-- 
Ivan

Re: [Bitcoin-development] Outbound connections rotation

[Jeff Garzik]

Simply by observing timing from sufficiently geo-graphically and
network-ly dispersed nodes, you may deduce the original broadcaster of
a transaction.  Rotating peers doesn't help.

That said, periodic rotation can be helpful.  Every 2-10 minutes is excessive.


On Mon, Aug 18, 2014 at 12:46 PM, Ivan Pustogarov
<ivan.pustogarov@uni.lu> wrote:
> Hi there,
>
> I'd like to start a discussion on periodic rotation of outbound connections.
> E.g. every 2-10 minutes an outbound connections is dropped and replaced
> by a new one.
>
> Motivation:
> Each bitcoin non-UPnP client behind NAT has 8 outbound connections
> which change only rarely (due to occasional remote side disconnections).
> A subset of these 8 entry nodes uniquely identifies a user.
> An attacker can listen for transactions in Bitcoin network and for each
> transaction record the first 8 peers which forwarded the transaction.
> If two distinct transactions (with unrelated bitcoin addresses)
> come from the same set of 8 peers, the attacker can conclude that they
> originated from the same user. This gives another method (in addition
> to transaction graph analysis) for an attacker to link different BC
> addresses of the same user.
> Also note that by default bitcoin clients advertise their public IP
> addresses. The attacker can link the advertised IP's to corresponding
> 8 entry nodes and use it to deanonymise Bitcoin clients.
>
> If a bitcoin client periodically rotates his set of outbound
> connections, his 8-peers fingerprint is blurred over time.
>
> Corresponding pull request is #4723.
>
> Some details are here: https://www.cryptolux.org/index.php/Bitcoin
>
> --
> Ivan
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development



-- 
Jeff Garzik
Bitcoin core developer and open source evangelist
BitPay, Inc.      https://bitpay.com/

Re: [Bitcoin-development] Outbound connections rotation

[Gregory Maxwell]

On Mon, Aug 18, 2014 at 9:46 AM, Ivan Pustogarov <ivan.pustogarov@uni.lu> wrote:
> Hi there,
> I'd like to start a discussion on periodic rotation of outbound connections.
> E.g. every 2-10 minutes an outbound connections is dropped and replaced
> by a new one.

Connection rotation would be fine for improving a node's knoweldge
about available peers and making the network stronger against
partitioning.

I haven't implemented this because I think your motivation is
_precisely_ opposite the behavior. If you keep a constant set of
outbound peers only those peers learn the origin of your transactions,
and so it is unlikely that any particular attacker will gain strong
evidence. If you rotate where you send out your transactions then with
very high probability a sybil pretending to be many nodes will observe
you transmitting directly.

Ultimately, since the traffic is clear text, if you expect to have any
privacy at all in your broadcasts you should be broadcasting over tor
or i2p.

Re: [Bitcoin-development] Outbound connections rotation

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 809 bytes --]

>
> Connection rotation would be fine for improving a node's knoweldge
> about available peers and making the network stronger against
> partitioning.
>

It's also the first/next step towards decentralising the DNS seeds (for SPV
clients), as it'd allow each node to explore the network and return better
quality results in getaddr.


> If you rotate where you send out your transactions then with
> very high probability a sybil pretending to be many nodes will observe
> you transmitting directly.
>

This is sort of what Tor is going through with their guard nodes and how
often to rotate them.

I think the attack Ivan is talking about does not require sybil attacks to
work though, just listening to lots of peers. Raising the bar to require
the attacker to receive lots of connections seems like a win.

[-- Attachment #2: Type: text/html, Size: 1233 bytes --]

Re: [Bitcoin-development] Outbound connections rotation

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 1948 bytes --]

Yes, I believe peer rotation is useful, but not for privacy - just for
improving the network's internal knowledge.

I haven't looked at the implementation yet, but how I imagined it would be
every X minutes you attempt a new outgoing connection, even if you're
already at the outbound limit. Then, if a connection attempt succeeds,
another connection (according to some scoring system) is replaced by it.
Given such a mechanism, plus reasonable assurances that better connections
survive for a longer time, I have no problem with rotating every few
minutes.
On Aug 18, 2014 7:23 PM, "Gregory Maxwell" <gmaxwell@gmail.com> wrote:

> On Mon, Aug 18, 2014 at 9:46 AM, Ivan Pustogarov <ivan.pustogarov@uni.lu>
> wrote:
> > Hi there,
> > I'd like to start a discussion on periodic rotation of outbound
> connections.
> > E.g. every 2-10 minutes an outbound connections is dropped and replaced
> > by a new one.
>
> Connection rotation would be fine for improving a node's knoweldge
> about available peers and making the network stronger against
> partitioning.
>
> I haven't implemented this because I think your motivation is
> _precisely_ opposite the behavior. If you keep a constant set of
> outbound peers only those peers learn the origin of your transactions,
> and so it is unlikely that any particular attacker will gain strong
> evidence. If you rotate where you send out your transactions then with
> very high probability a sybil pretending to be many nodes will observe
> you transmitting directly.
>
> Ultimately, since the traffic is clear text, if you expect to have any
> privacy at all in your broadcasts you should be broadcasting over tor
> or i2p.
>
>
> ------------------------------------------------------------------------------
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

[-- Attachment #2: Type: text/html, Size: 2537 bytes --]

[Bitcoin-development] Fwd: Outbound connections rotation

[Gregory Maxwell]

On Mon, Aug 18, 2014 at 10:30 AM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> Yes, I believe peer rotation is useful, but not for privacy - just for
> improving the network's internal knowledge.
>
> I haven't looked at the implementation yet, but how I imagined it would be
> every X minutes you attempt a new outgoing connection, even if you're
> already at the outbound limit. Then, if a connection attempt succeeds,
> another connection (according to some scoring system) is replaced by it.
> Given such a mechanism, plus reasonable assurances that better connections
> survive for a longer time, I have no problem with rotating every few
> minutes.

Previously when you and I had discussed this I'd proposed that some
number (say) four of the most long lived connections which had proven
themselves useful (e.g. by relaying blocks) be pinned up and not be
eligible for dropping. By protecting some subset of peers you
guarantee that an attacker which simply introduces a lot of nodes
cannot partition the network which existed prior to when the attack
started.

On Mon, Aug 18, 2014 at 10:27 AM, Mike Hearn <mike@plan99.net> wrote:
> I think the attack Ivan is talking about does not require sybil attacks to work though, just listening to lots of peers

I may not be understanding you. Might be a definitions thing, I'm
using the definition: A sybil attack is when a party takes on many
identities (nodes) in the network.

What ivan highlights is a bit of a tradeoff between concealing
identities and linkages.  Relaying transactions through only a single
peer ever (until that one is no longer on the network) is the best
strategy for concealing your identity (ignoring tor and what not), as
only that peer learns anything about your identity.  But it may reveal
a lot about how different transactions are linked, since people
observing that peer will observe that your transactions are
correlated.

The optimal strategy for avoiding linkages (ignoring tor, again), is
to randomly pick a different peer for each transaction and relay the
transaction only to that peer.  This can (and probably should) be
distinct from your normal network connectivity.

Probably for anti-linkage I'd suggest that a facility for that kind of
announcement should be done. If used over tor it would also protect
your identity.   Then the regular topology of the network can be
optimized for learning and partition resistance.

Re: [Bitcoin-development] Fwd: Outbound connections rotation

[Wladimir]

> The optimal strategy for avoiding linkages (ignoring tor, again), is
> to randomly pick a different peer for each transaction and relay the
> transaction only to that peer.  This can (and probably should) be
> distinct from your normal network connectivity.

It already happens with 8 peers that if you have lousy peers, the
transaction doesn't reach the network on the first broadcasting. When
sending to only one random peer it will likely be even worse.

I guess the wallet could send out the transaction 'staggered' over
time. It could pick a random new node, broadcast the transaction, wait
a bit, pick a new node, broadcast the transaction until it is comes
back through one of the other peers.

Separating the transaction broadcasting (of the wallet) from, for
example, the nodes used to request blocks from could make sense. Maybe
doubly so if bloom filters are involved.

Wladimir

Re: [Bitcoin-development] Outbound connections rotation

[Ivan Pustogarov]

Yes, I agree that if a client rotates its outbound connections then
sooner or later he will connect to a malicious peer. This case considers
an attacker which has some peers in the network. E.g. renting 500 IP addresses
for 0.01 USD per IP per hour will cost 3600 USD per month: doable but
still not for free.
I think that revealing the origin (or rather public IP) of a distinct
transaction is tolerable. The learned public IP can be shared by several
users. So a big ISP can server as a anonymyzer which prevents from linking
tx of the same user.

Rotation will help against low-resource attackers with no peers at all.
The reason for rotation is that if client's 8 outbound connections stay
the same for a long time, an attacker which does not have any peers at all
but just listens the Bitcoin network can link together differed BC addresses
and learn the IP of the client. The 8 entry peers are unique per client so if two
users share the same IP, they can be distinguished.
In order to protect himself from this specific attack, a client can also
set only 3-4 outbound connections, so the proposed modification is just
another potential defence. If it is useful for other things, it' great.


> If you rotate where you send out your transactions then with
> very high probability a sybil pretending to be many nodes will observe
> you transmitting directly.

Outbound connections are still rotated from time to time due to remote side
disconnections. Plus outbound connections do not survive BC client restarts
(unlike Tor Guard nodes).


On Mon, Aug 18, 2014 at 10:21:07AM -0700, Gregory Maxwell wrote:
> On Mon, Aug 18, 2014 at 9:46 AM, Ivan Pustogarov <ivan.pustogarov@uni.lu> wrote:
> > Hi there,
> > I'd like to start a discussion on periodic rotation of outbound connections.
> > E.g. every 2-10 minutes an outbound connections is dropped and replaced
> > by a new one.
> 
> Connection rotation would be fine for improving a node's knoweldge
> about available peers and making the network stronger against
> partitioning.
> 
> I haven't implemented this because I think your motivation is
> _precisely_ opposite the behavior. If you keep a constant set of
> outbound peers only those peers learn the origin of your transactions,
> and so it is unlikely that any particular attacker will gain strong
> evidence. If you rotate where you send out your transactions then with
> very high probability a sybil pretending to be many nodes will observe
> you transmitting directly.
> 
> Ultimately, since the traffic is clear text, if you expect to have any
> privacy at all in your broadcasts you should be broadcasting over tor
> or i2p.

-- 
Ivan

Re: [Bitcoin-development] Outbound connections rotation

[Gregory Maxwell]

On Mon, Aug 18, 2014 at 11:37 AM, Ivan Pustogarov
<ivan.pustogarov@uni.lu> wrote:
> the same for a long time, an attacker which does not have any peers at all
> but just listens the Bitcoin network can link together differed BC addresses
> and learn the IP of the client.

I don't understand what you're talking about here; if you have no peer
at all you will learn nothing about the Bitcoin network.

Can you clarify?


> The 8 entry peers are unique per client so if two
> users share the same IP, they can be distinguished.

What mechanism are you referring to specifically?

> Outbound connections are still rotated from time to time due to remote side
> disconnections. Plus outbound connections do not survive BC client restarts
> (unlike Tor Guard nodes).

On our initial connections we do have a preference for nodes we knew
were up recently. This could be made further. That the current
behavior isn't great isn't an argument for making it worse on that
dimension.

Re: [Bitcoin-development] Outbound connections rotation

[Ivan Pustogarov]

The attack I'm trying to address is described here: https://www.cryptolux.org/index.php/Bitcoin
It was discussed here: https://bitcointalk.org/index.php?topic=632124.0

It uses the following observation. Each NATed client connects to the Bitcoin network
through 8 entry peers; he also advertises his public IP address to these peers which
allows an attacker to make the mapping <8-entry-peers, client-IP-address>.
The probability for two different clients to choose
the same entry peers is negligible. When a client generates a transaction,
the entry peers of the client are likely to be the first to retransmit it.

The attacker establishes many connections to each reachable Bitcoin peer and listens
for transactions. For each transaction she records 8-10 peers which were the first to forward this tx.
As a result, if two transactions are forwarded by the same set of entry peers,
they are likely to belong to the same client. 
Also each 8-tuples has a mapping to the client's advertised IP address.


On Mon, Aug 18, 2014 at 12:37:49PM -0700, Gregory Maxwell wrote:
> On Mon, Aug 18, 2014 at 11:37 AM, Ivan Pustogarov
> <ivan.pustogarov@uni.lu> wrote:
> > the same for a long time, an attacker which does not have any peers at all
> > but just listens the Bitcoin network can link together differed BC addresses
> > and learn the IP of the client.
> 
> I don't understand what you're talking about here; if you have no peer
> at all you will learn nothing about the Bitcoin network.
> 
> Can you clarify?
> 
> 
> > The 8 entry peers are unique per client so if two
> > users share the same IP, they can be distinguished.
> 
> What mechanism are you referring to specifically?
> 
> > Outbound connections are still rotated from time to time due to remote side
> > disconnections. Plus outbound connections do not survive BC client restarts
> > (unlike Tor Guard nodes).
> 
> On our initial connections we do have a preference for nodes we knew
> were up recently. This could be made further. That the current
> behavior isn't great isn't an argument for making it worse on that
> dimension.

-- 
Ivan

Re: [Bitcoin-development] Outbound connections rotation

[Gregory Maxwell]

On Mon, Aug 18, 2014 at 1:33 PM, Ivan Pustogarov <ivan.pustogarov@uni.lu> wrote:
> The attack I'm trying to address is described here: https://www.cryptolux.org/index.php/Bitcoin
> It was discussed here: https://bitcointalk.org/index.php?topic=632124.0
>
> It uses the following observation. Each NATed client connects to the Bitcoin network
> through 8 entry peers; he also advertises his public IP address to these peers which
> allows an attacker to make the mapping <8-entry-peers, client-IP-address>.

I'm afraid I'm losing you here.  The node advertises himself to
everyone he is connected to and in/or out, those nodes pass along
those advertisements.  When I receive an advertisement from a node I
do not know how far away the advertised peers is, presumably I can
accurately exclude it from being 0-hops— itself—) 1 or more should be
indistinguishable. Is there a reason that they're distinguishable that
I'm missing?

Can you explain to me how you propose to produce this mapping?

Re: [Bitcoin-development] Outbound connections rotation

[Ivan Pustogarov]

For each neighbour, a Bitcoin peer keeps the history of addresses that
it forwarded to the neighbour. If an address was already forwarded
to a neighbour it is not retransmitted again.

An attacker can make a list of potential IP addresses of clients (say
an IP range of an ISP, or listen for addresses in the Bitcoin network
before the attack). Then she periodically "spams" the network with this list and
updates the address-forward history at each Bitcoin peer.
After each "spam" round, the attacker reconnects her connections to Bitcoin peers
and thus clears the retransmission history for her connections only.

As the result, when a NAT client connects to the network and advertises its
address, the addresses will propagate to the attacker's connections only.


On Mon, Aug 18, 2014 at 01:43:44PM -0700, Gregory Maxwell wrote:
> On Mon, Aug 18, 2014 at 1:33 PM, Ivan Pustogarov <ivan.pustogarov@uni.lu> wrote:
> > The attack I'm trying to address is described here: https://www.cryptolux.org/index.php/Bitcoin
> > It was discussed here: https://bitcointalk.org/index.php?topic=632124.0
> >
> > It uses the following observation. Each NATed client connects to the Bitcoin network
> > through 8 entry peers; he also advertises his public IP address to these peers which
> > allows an attacker to make the mapping <8-entry-peers, client-IP-address>.
> 
> I'm afraid I'm losing you here.  The node advertises himself to
> everyone he is connected to and in/or out, those nodes pass along
> those advertisements.  When I receive an advertisement from a node I
> do not know how far away the advertised peers is, presumably I can
> accurately exclude it from being 0-hops— itself—) 1 or more should be
> indistinguishable. Is there a reason that they're distinguishable that
> I'm missing?
> 
> Can you explain to me how you propose to produce this mapping?

-- 
Ivan

Re: [Bitcoin-development] Outbound connections rotation

[Gregory Maxwell]

On Mon, Aug 18, 2014 at 2:02 PM, Ivan Pustogarov <ivan.pustogarov@uni.lu> wrote:
> For each neighbour, a Bitcoin peer keeps the history of addresses that
> it forwarded to the neighbour. If an address was already forwarded
> to a neighbour it is not retransmitted again.

Okay, sorry, I thought you were saying something else. I understand.

[Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Isidor Zeuner]

Hi there,

quote:
[...]
> If two distinct transactions (with unrelated bitcoin addresses)
> come from the same set of 8 peers, the attacker can conclude that they
> originated from the same user. This gives another method (in addition
> to transaction graph analysis) for an attacker to link different BC
> addresses of the same user.

Using the same set of nodes for posting transactions using unrelated
inputs kind of limits the privacy improvement that can be gained from
using unrelated inputs in the first place.

Similar to how Tor uses different circuits for different hosts to
connect to, it may make more sense to only use the same set of nodes
for posting a subsequent transaction when the input addresses are also
the same.

[...]
> Some details are here: https://www.cryptolux.org/index.php/Bitcoin
>

I also find the topic of banning Tor exit nodes interesting.

I wonder if it makes more sense not to ban IP addresses completely,
but instead to throttle them using a PoW-based access control
scheme. Misbehaving addresses can have their connecting difficulty
scaled up, which should make it uneconomic to try to DoS the usage of
Tor exit nodes for connecting to Bitcoin.

It may also help nodes behind a NAT router if they share their global
IP with misconfigured nodes.

Best regards,

Isidor

Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 831 bytes --]

>
> Misbehaving addresses can have their connecting difficulty
> scaled up, which should make it uneconomic to try to DoS the usage of
> Tor exit nodes for connecting to Bitcoin.
>

You can't solve DoS by requiring all clients to do complicated work, all
that means is that weak clients (like users mobile phones and tablets) are
successfully DoSd whereas the attackers botnet of stolen computers sit
there solving PoWs.

The correct way to solve DoS is by having work prioritisation and queueing
mechanisms, then finding ways to distinguish "good" clients from "bad"
clients. Doing this whilst preserving privacy is hard. Long term the only
way to solve it may be to require clients to present some kind of cookie
during resource exhaustion events that prove they've been around for a
while, thus allowing them to jump the queue.

[-- Attachment #2: Type: text/html, Size: 1116 bytes --]

Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Isidor Zeuner]

Hi Mike,

thanks for your assessment.

Please find my replies in-line:
> >
> > Misbehaving addresses can have their connecting difficulty
> > scaled up, which should make it uneconomic to try to DoS the usage of
> > Tor exit nodes for connecting to Bitcoin.
> >
>
> You can't solve DoS by requiring all clients to do complicated work,

Since when? This has been a recognized approach since people called it
"hashcash" ([1] - before cryptocurrencies were even invented).

I hear your concerns, but even then, I would see the PoW-based
approach as an improvement to today's situations.

To be clear, I do not propose to have _all_ clients do complicated
work. Just those using an address which has been misbehaving. Right
now, they cannot connect at all, no matter how much resources they
dedicate towards doing so.

> all
> that means is that weak clients (like users mobile phones and tablets) are
> successfully DoSd whereas the attackers botnet of stolen computers sit
> there solving PoWs.
>

The way I had it in mind, well-behaved clients on an address used by
attackers would have more effort to connect because of the PoW, but
after that, they can stay connected. The attacker also has to put more
effort into connecting, and after sending malformed messages, gets
disconnected. So, the attacker would have to perform much more PoW
computations in order to keep up his attack.

> The correct way to solve DoS is by having work prioritisation and queueing
> mechanisms, then finding ways to distinguish "good" clients from "bad"
> clients. Doing this whilst preserving privacy is hard. Long term the only
> way to solve it may be to require clients to present some kind of cookie
> during resource exhaustion events that prove they've been around for a
> while, thus allowing them to jump the queue.
>

Exactly. Not every user may like to have a cookie by which an observer
might get the chance to even link his connection to his previous
connections, thereby allowing the discussed deanonymization technique
to get even more effective.

Maybe having both options would be even better: In case of an attack,
those able to solve the anti-DoS PoW can still connect (just maybe
slower). Those who wish to run a weak client can choose to sacrifice
privacy for connectivity and keep a cookie for connecting.

Best regards,

Isidor

[1] http://www.hashcash.org/papers/hashcash.pdf

Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 3460 bytes --]

>
> Since when? This has been a recognized approach since people called it
> "hashcash" ([1] - before cryptocurrencies were even invented).
>

I only know of one site that worked the way you propose: TicketMaster, a
long time ago. They used it as a less harsh form of blocking for IPs that
they strongly suspected were bots, which is what you suggest indeed. But
99% of the hard work of that system was in scoring the connections. The
actual PoW part didn't work that great because bots have much more patience
than humans do.

Other sites also use proofs of work, but they're CAPTCHAs i.e. human PoWs.
And unfortunately those don't work very well these days either :(


> To be clear, I do not propose to have _all_ clients do complicated
> work. Just those using an address which has been misbehaving.


Yes, I understand, but then you're back to scoring clients - the hard part
- and the only question is do you slow down that client by sticking them at
the bottom of a work queue or by requiring them to solve a difficult PoW.
The best approach is the first one because that scales naturally .... you
don't have to define some notion of misbehaviour, you just prioritise
amongst clients.

The current notion of "misbehaviour" is only somewhat useful. It's easy to
classify reasonable behaviour as harmful and shoot yourself in the foot. We
managed this at least once back in 2010 when we actually released a version
of Bitcoin that interpreted a normal request to serve the block chain as a
DoS attack! It couldn't serve the chain at all! Additionally many things
that can be interpreted as an attack like sending a message with a bad
signature can also be caused just by mistakes, or version skew during
software upgrades. So it's very tricky to get this right.

That's important because one quite common way big sites suffer DoS attacks
is by accidentally having real users create a DoS "attack" by e.g. pushing
a bad software update, or by having sudden and unexpected press-driven
growth, etc. You really don't want to force users to sit around waiting and
wasting battery. It's better to serve as many requests as you can up to
your absolute limit and try to ensure as many of them as possible are good.


> Exactly. Not every user may like to have a cookie by which an observer
>>
> might get the chance to even link his connection to his previous
> connections, thereby allowing the discussed deanonymization technique
> to get even more effective.
>

I doubt it matters. Any DoS attack that's powerful enough to use up most of
the networks resources is probably being driven by a botnet of some kind,
and *all* legitimate users will lose in an even fight against a botnet.

Cookies can be somewhat anonymized. For example a cookie that is merely a
signature over a timestamp of some kind (doesn't have to be an secp256k1
signature) can be normalised to the day or week. So you can prove you've
been using Bitcoin for say 3 years but it doesn't pin you down precisely.

This isn't perfect:  attackers can and do "age" accounts before preparing
for abuse. Proof of UTXO is another way to rank users. If you're richer
you're presumably more important for the network to process than poor
people. However you end up back at a CPU imbalance. PoW can possibly play a
role here to even it out: the cost of submitting a UTXO proof should be at
least equal to the cost of verifying the signature, but that is a PoW small
enough that users would not notice.

[-- Attachment #2: Type: text/html, Size: 4383 bytes --]

Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Isidor Zeuner]

Hi Mike, hi Ivan, hi all,

>
> >
> > Since when? This has been a recognized approach since people called it
> > "hashcash" ([1] - before cryptocurrencies were even invented).
> >
>
> I only know of one site that worked the way you propose: TicketMaster, a
> long time ago. They used it as a less harsh form of blocking for IPs that
> they strongly suspected were bots, which is what you suggest indeed. But
> 99% of the hard work of that system was in scoring the connections. The
> actual PoW part didn't work that great because bots have much more patience
> than humans do.
>

I think the proposal back then was targeted at e-mail
delivery. Interestingly, one of today's most common approaches
against unsolicited e-mails, DKIM, can also be considered as being a
relative to PoW if we consider that bulk mailer operators don't
like it because of the CPU burden it creates. But with e-mail, people
tend to see it even as an advantage to also have identification of the
participants, so it's no surprise that pure PoW approaches did not
achieve importance.

With cryptocurrencies, it's different. Combating DoS without
creating additional ways to identify users is something where many
interested users can be found.

Humans may have less patience than an attacker who just wants to
achieve his DoS objective in a batch processing manner. But humans
also don't care if their patience is put to the test by having to
wait until one Tor exit node is finally unbanned, or by waiting for
the connection PoW to finish because it temporarily got harder due to
an attack.

No doubt that a dedicated attacker can have an (even big) advantage
resource-wise. But this is no different between the case where both
computing power and the number of Tor exit nodes are the resource to
compete on, and the case where it's just the resource of Tor exit
nodes that gets exhausted. But by giving users the choice of proving
their dedication through a connecting PoW challenge, I would expect
users having more possibilities of finding their way through a
DoS-imposed partial outage. After all, the possibly powerful attacker
has to invest his resources into making all access routes to the
network unusable, while for well-behaved users, every single access
route that still works is useful. Therefore, I think it makes sense to
add more degrees of freedom.

> Other sites also use proofs of work, but they're CAPTCHAs i.e. human PoWs.
> And unfortunately those don't work very well these days either :(
>

None of these measures are perfect. But I think we can achieve a
solution that is good enough. Hopefully without integrating a
centralized captcha provider ;)

>
> > To be clear, I do not propose to have _all_ clients do complicated
> > work. Just those using an address which has been misbehaving.
>
>
> Yes, I understand, but then you're back to scoring clients - the hard part
> - and the only question is do you slow down that client by sticking them at
> the bottom of a work queue or by requiring them to solve a difficult PoW.
> The best approach is the first one because that scales naturally .... you
> don't have to define some notion of misbehaviour, you just prioritise
> amongst clients.
>

On the one hand, I think that to some extent, the work queue based
throttling just moves the problem from making it hard to connect
towards making it hard to do something useful with your connection.

But as I touched above, I see the merit that comes from the PoW-based
approach in allowing well-behaving users to explore multiple axes of
putting effort into connecting. Expanding on this approach, I think
that the work queue based approach and PoW could be combined, leading
to three measures the nodes can use for throttling misbehaving
clients:

* scaling up connection PoW
* throttling the connection on the work queue
* throttling the IP on the work queue

The challenging part would be to properly tune the extent of the three
measures in order to throttle attackers' messages with minimum
impact to well-behaving users.

> The current notion of "misbehaviour" is only somewhat useful. It's easy to
> classify reasonable behaviour as harmful and shoot yourself in the foot. We
> managed this at least once back in 2010 when we actually released a version
> of Bitcoin that interpreted a normal request to serve the block chain as a
> DoS attack! It couldn't serve the chain at all! Additionally many things
> that can be interpreted as an attack like sending a message with a bad
> signature can also be caused just by mistakes, or version skew during
> software upgrades. So it's very tricky to get this right.
>

Sure, but that's a different topic. It may not be even realistic
to have a model which can be reduced to deciding between purposeful
misbehaviour and regular usage. But an attacker who wants to cut off
IPs from the network will always use whatever misbehaviour that leads
to maximum penalty, meaning that it is a decision between not
penalizing at all, or doing so.

> That's important because one quite common way big sites suffer DoS attacks
> is by accidentally having real users create a DoS "attack" by e.g. pushing
> a bad software update, or by having sudden and unexpected press-driven
> growth, etc. You really don't want to force users to sit around waiting and
> wasting battery. It's better to serve as many requests as you can up to
> your absolute limit and try to ensure as many of them as possible are good.
>

I'd say, better have a few Tor-based users realize that they
should look for a fixed update because their client has to do PoW for
connecting, rather than having all Tor-based users locked out.

Still, users should be notified that something is unusual.

>
> > Exactly. Not every user may like to have a cookie by which an observer
> >>
> > might get the chance to even link his connection to his previous
> > connections, thereby allowing the discussed deanonymization technique
> > to get even more effective.
> >
>
> I doubt it matters. Any DoS attack that's powerful enough to use up most of
> the networks resources is probably being driven by a botnet of some kind,
> and *all* legitimate users will lose in an even fight against a botnet.
>
> Cookies can be somewhat anonymized. For example a cookie that is merely a
> signature over a timestamp of some kind (doesn't have to be an secp256k1
> signature) can be normalised to the day or week. So you can prove you've
> been using Bitcoin for say 3 years but it doesn't pin you down precisely.
>
> This isn't perfect:  attackers can and do "age" accounts before preparing
> for abuse. Proof of UTXO is another way to rank users. If you're richer
> you're presumably more important for the network to process than poor
> people. However you end up back at a CPU imbalance. PoW can possibly play a
> role here to even it out: the cost of submitting a UTXO proof should be at
> least equal to the cost of verifying the signature, but that is a PoW small
> enough that users would not notice.
>

Both cookies and Proof of UTXO sound like interesting approaches, but
I still see additional possibilities to deduce information about the
user identity here. They could be a nice addition for a better
approach to handle DoS attacks, but I would disagree when it comes to
only providing possibly privacy-weakening approaches.

I'm looking forward to your comments.

Best regards,

Isidor

Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 3621 bytes --]

DKIM is hardly a PoW; signing is cheap and gets cheaper all the time. I
used to work in the email business and big bulk mailers all spent far more
CPU time on other aspects of their business, the overhead of DKIM is
irrelevant.

PoW didn't work in the anti spam world because it (amongst other problems)
mixes up bulk mail and spam, which are not the same thing. Very common
conceptual error though.


> humans also don't care if their patience is put to the test by having to
> wait until one Tor exit node is finally unbanned, or by waiting for
> the connection PoW to finish because it temporarily got harder due to
> an attack.
>

They don't? This is news to me. Humans always care. One of the surest ways
to hurt your online business is to have a slow website because lots of
users will give up rather than tolerate a few seconds of latency. At Google
we actually had formulas that could relate a change in web search latency
to revenue impact.

So humans very much care! I actually doubt that any reasonable mobile
wallet will use the new Tor support bitcoinj by default, for example,
because it imposes quite some startup cost when the downloaded consensus
isn't fresh, and slow startup is painful. It could be optimised but nobody
has done that. For long running desktop wallets where startup time can be
amortised over hours or days, I guess it makes more sense.

I agree that PoW tokens might make sense as a last resort if nodes can't
even put a connection at the bottom of a priority queue and you're right
that it may be a useful tool in a shared toolbox. However if we reach the
point where users are all being PoWd then we're already pretty hosed and
it's probably close to game over :(

I'd say, better have a few Tor-based users realize that they
> should look for a fixed update because their client has to do PoW for
> connecting, rather than having all Tor-based users locked out.
>

I think Tor is a separate issue. If an attacker wants to either force all
users off Tor, or force them via a handful of exits, then this attack is
quite detectable already and wallets could already decide to simply give up
on Tor at that point automatically. No PoW needed. Well, ideally, nodes
would disconnect a banned IP with some kind of notice saying why it was
banned, but that's a small improvement.

Still, users should be notified that something is unusual.
>

If we're talking mainstream success then users by and large do not care
about technical mumbo jumbo like peer to peer networks or Tor ("that's the
thing drug dealers and pedos use???"). They just want the damn thing to
work reliably. So notifying them is unhelpful - it's not actionable. They
would just see a message like

   "The wizzle sprocket is kaput - keep working? YES NO"

and then everyone presses yes.

Stuff like Tor plays well in the crypto community but it's very hard to
actually switch on by default, because it needs to have absolutely no cost
at all, otherwise you'll just annoy the vast majority who don't want to pay
for very abstract and hard to quantify privacy benefits.

So I think it's worth considering the DoS problem and Tor somewhat
separately, even though they're related. The solution to a crafty
privacy-attacking DoS that tries to make exits useless is don't use Tor at
all. The solution to "the entire Bitcoin network is under attack" is much
harder. It's unclear to me we can ever solve it convincingly - banks don't
connect together using private networks in which anonymity is forbidden
because they're stupid. They do it because it solves DoS attacks in one
solid move and they feel it's worth the high cost.

[-- Attachment #2: Type: text/html, Size: 5600 bytes --]

Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation)

[Isidor Zeuner]

Hi Mike,

thanks for your assessment.

Please find my replies in-line:
> DKIM is hardly a PoW; signing is cheap and gets cheaper all the
> time. I used to work in the email business and big bulk mailers all spent
> far more CPU time on other aspects of their business, the overhead of
> DKIM is irrelevant.
>

Well, as long as bulk mailing companies run around investing into
per-destination DKIM toggling, stating that they want to cut down CPU
usage due to crypto processing, I tend to believe that it can have an
important impact depending on the setup. Of course, I cannot rule out
the possibility that they would be better off investing into profiling
CPU usage, and/or exploring a higher ROI possibly coming from using
more CPU time on other processing. I see no point neglecting an issue
just because there are business models where it is irrelevant,
though.

> PoW didn't work in the anti spam world because it (amongst other
> problems) mixes up bulk mail and spam, which are not the same
> thing. Very common conceptual error though.
>

I did not say so, either. But bulk mailing and e-mail spam are not
orthogonal with respect to the technical characteristics that make
them possible. And nor are DKIM and PoW/hash-cash fully orthogonal.

I like the objections you raised. Avoiding DKIM because of the CPU
costs involved might be as groundless as stating "we don't use
HTTPS in order to save CPU time". Still, these substantiations can be
found in the wild, and they won't disappear because we discuss
them here on a theoretical level.

If you assume conceptual errors, though, I would suggest we discuss
the e-mail topic off-list, though. I simplify things a bit in order to
not bore the group with too much text about non-Bitcoin stuff, but
this does not mean that I'm not familiar with, or am not open for
discussing the subtle differences of different approaches that have
been researched in the e-mail business.

>
>> humans also don't care if their patience is put to the test by
>> having to wait until one Tor exit node is finally unbanned, or by
>> waiting for the connection PoW to finish because it temporarily got
>> harder due to an attack.
>>
>
> They don't? This is news to me. Humans always care. One of the
> surest ways to hurt your online business is to have a slow website
> because lots of users will give up rather than tolerate a few seconds
> of latency. At Google we actually had formulas that could relate a
> change in web search latency to revenue impact.
>

You might want to re-read my statement more carefully. I did not say
they don't care about delays, but I do say that they don't
care where the delays come from.

It is a known fact that Google will also penalize web sites which have
high latencies, so the top results appear as being also of technical
quality. But neither the users nor Google will care if the web site is
slow because the site owner did not allocate proper resources for
running the frontend quickly, or if the database server is making
things slow.

> So humans very much care! I actually doubt that any reasonable
> mobile wallet will use the new Tor support bitcoinj by default, for
> example, because it imposes quite some startup cost when the
> downloaded consensus isn't fresh, and slow startup is painful. It
> could be optimised but nobody has done that. For long running desktop
> wallets where startup time can be amortised over hours or days, I
> guess it makes more sense.
>

I agree that improving on the performance of the consensus
bootstrapping logic is an interesting topic.

> I agree that PoW tokens might make sense as a last resort if nodes
> can't even put a connection at the bottom of a priority queue and
> you're right that it may be a useful tool in a shared
> toolbox. However if we reach the point where users are all being PoWd
> then we're already pretty hosed and it's probably close to
> game over :(
>

I don't think this was ever about _all_ IPs suffering from DoS
measures. But I do think that Bitcoin will already suffer if we get to
a point where it is practically useless when being used over Tor, or
where this is only possible by immediately sacrificing the privacy
improvement Tor introduces.

>> I'd say, better have a few Tor-based users realize that they
>> should look for a fixed update because their client has to do PoW
>> for connecting, rather than having all Tor-based users locked out.
>>
>
> I think Tor is a separate issue. If an attacker wants to either
> force all users off Tor, or force them via a handful of exits, then
> this attack is quite detectable already and wallets could already
> decide to simply give up on Tor at that point automatically. No PoW
> needed. Well, ideally, nodes would disconnect a banned IP with some
> kind of notice saying why it was banned, but that's a small
> improvement.
>

I fully agree. A ban notice could also make it easier to track down
DoS handling issues triggered by incompatible updates, and possibly
make it harder for someone to issue bans for malicious reasons without
being noticed. Also, I see it as an important step towards a modern
security policy, because it would emphasize that the Bitcoin network
can be kept secure with minimum obscurity.

>> Still, users should be notified that something is unusual.
>>
>
> If we're talking mainstream success then users by and large do
> not care about technical mumbo jumbo like peer to peer networks or Tor
> ("that's the thing drug dealers and pedos use???"). They just want
> the damn thing to work reliably. So notifying them is unhelpful -
> it's not actionable. They would just see a message like
>
>    "The wizzle sprocket is kaput - keep working? YES NO"
>
> and then everyone presses yes.
>

As you say, the mainstream user won't care about technical mumbo
jumbo like Tor, so he won't be likely to run Bitcoin over Tor. So,
the most likely cases where he would encounter the notification would
be:

* incompatible update

* his machine / network is compromised and connects to Bitcoin,
  triggering DoS measures

In both cases, he would consider it as important to take action, so
even a scary notification might be the way to go.

The non-mainstream user who is willing to dive into the technical
details of running Bitcoin over Tor securely will generally be more
likely to be able to make more differentiated decisions about such an
anomaly, but I cannot see why we would want him to not have proper
tools to deal with the situation, or not to be informed about
something unusual happening.

> Stuff like Tor plays well in the crypto community but it's very
> hard to actually switch on by default, because it needs to have absolutely
> no cost at all, otherwise you'll just annoy the vast majority who
> don't want to pay for very abstract and hard to quantify privacy
> benefits.
>

Agreed. But as outlined above, those who enable it on purpose will
benefit, and those who don't also don't have a
disadvantage. Am I missing something?

> So I think it's worth considering the DoS problem and Tor
> somewhat separately, even though they're related. The solution to
> a crafty privacy-attacking DoS that tries to make exits useless is
> don't use Tor at all. The solution to "the entire Bitcoin network
> is under attack" is much harder.

Indeed. For the issues we're seeing, Tor can actually be regarded
to be at fault to some extent. So the Tor development might also
benefit from these things being researched. But I see no reason to
sacrifice the possibility to use Tor on Bitcoin properly at this
point.

I also agree that a solution which improves the situation of Tor nodes
must not make it easier to attack the entire Bitcoin network. I'm
just not seeing why this would be the case for the approach I
outlined. I actually think that having multiple values to tune in
order to throttle unwanted behaviour on the network might even improve
on Bitcoin's robustness as a whole, because it might enable better
targeted moves against other (non-Tor-related) threats. How do we know
if the most dangerous attacker Bitcoin will face has more resources
with respect to IP addresses, or CPU time?

> It's unclear to me we can ever
> solve it convincingly - banks don't connect together using private
> networks in which anonymity is forbidden because they're
> stupid. They do it because it solves DoS attacks in one solid move and
> they feel it's worth the high cost.

Well, banks did not even consider inventing something like Bitcoin
because what they have works well enough for their purposes. Still,
for some reasons, there are a lot of people interested in Bitcoin. I
would argue that it is because it tried to solve some things private
banking networks did not, so we might consider not only keeping
Bitcoin attractive for those who consider it as a badly implemented
form of what banking networks already provide.

Kind regards,

Isidor