From: Isidor Zeuner <cryptocurrencies@quidecco.de>
To: Mike Hearn <mike@plan99.net>
Content-Type: text/plain; charset=UTF-8; format=flowed
References: <CANEZrP2rLUW2-SZXjEKMvgZVjjHwz-4TEHJoAaMd5=1N8R3G3Q@mail.gmail.com>
	<20140823115321.AC158E07036@quidecco.de>
In-Reply-To: <CANEZrP2rLUW2-SZXjEKMvgZVjjHwz-4TEHJoAaMd5=1N8R3G3Q@mail.gmail.com>
Message-Id: <20141113225243.9DDF37C8853@quidecco.de>
Date: Thu, 13 Nov 2014 23:52:43 +0100 (CET)
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>,
	Ivan Pustogarov <ivan.pustogarov@uni.lu>
Subject: Re: [Bitcoin-development] Proposal: PoW-based throttling of
 addresses (was: Outbound connections rotation)
Precedence: list

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