Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Xp4XV-00070R-Eh for bitcoin-development@lists.sourceforge.net; Fri, 14 Nov 2014 00:15:02 +0000 X-ACL-Warn: Received: from quidecco.de ([81.169.136.15]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256) (Exim 4.76) id 1Xp4XT-0006P6-A4 for bitcoin-development@lists.sourceforge.net; Fri, 14 Nov 2014 00:15:01 +0000 Received: from localhost (localhost [127.0.0.1]) by quidecco.de (Postfix) with SMTP id 9DDF37C8853; Thu, 13 Nov 2014 23:52:43 +0100 (CET) From: Isidor Zeuner To: Mike Hearn Content-Type: text/plain; charset=UTF-8; format=flowed References: <20140823115321.AC158E07036@quidecco.de> In-Reply-To: Message-Id: <20141113225243.9DDF37C8853@quidecco.de> Date: Thu, 13 Nov 2014 23:52:43 +0100 (CET) X-Spam-Score: -1.0 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.0 RP_MATCHES_RCVD Envelope sender domain matches handover relay domain X-Headers-End: 1Xp4XT-0006P6-A4 Cc: Bitcoin Dev , Ivan Pustogarov Subject: Re: [Bitcoin-development] Proposal: PoW-based throttling of addresses (was: Outbound connections rotation) X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 14 Nov 2014 00:15:03 -0000 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