Topic: Protection against botnet DDoS of invalid (signature or otherwise) transactions? (Read 2372 times)

I have been composing a document compiling all my thoughts and research on this issue, which I will publish within days which I hope is more coherent on the holistic nature of the issues. Afaics, many factors are interrelated. My upthread elucidation is somewhat scattered and is missing some of these details.


I believe Johoe was not referring to amplification via reflection external to the Bitcoin network, rather using the Bitcoin network to replicate some spam to all peer nodes.

My coming research document will explain this holistic issue in more detail. For example, if the blacklist is not propagated, then the attacker has no asymmetric cost to spamming, because the attacker can move on to attacking another peer on the network after being banned on other node. Yet if the blacklist is propagated this can be a form of amplification. Again devil is in the details. My document will discuss the details.


I think you missed my point about the inappropriateness of blacklists on IP addresses at-scale (not the miniscule scale of Bitcoin as of now) being that the innocent payer (who didn't sign an invalid transaction) can end up banned (even temporarily) and finding a node where they are not banned is another cost to the innocent payer. And for IPv6, IP addresses are not scarce, so theoretically the attacker can have an unlimited number of them to cycle through, thus rendering IP blacklists useless.

DNS uses UDP, so the source IP can be spoofed (hence amplification works nicely). Bitcoin uses TCP, how do you plan to amplify using it?


It's temporary, they will have broadcast to other nodes as well (it can be something besides a bad sig, so it depends what clients will propagate it). Besides serious implementation flaws in underlying software, I don't see how this can happen by accident, or think it's bad for the person producing invalid signatures.

So we need a non-autonomous mixnet such as CoinShuffle to create an uncorrelated (to the input participants) set of hashes that can't be jammed or spammed (as I had previously explained these hashes being the anti-DDoS keys in the UTXO due to the orders-of-magnitude faster speed of verifying a Lamport/Merkel cryptographic hash signature than elliptic curve ECDSA or EdDSA and especially compared to the slow speed of confirming Confidential Transactions) as well as the additional benefit of obfuscating the correlation of IP addresses of the input participants to the outputs datums of the protocol, and the CoinShuffle can associate each transaction output with a specific hash in the grouping since it is passed along as another record in each output datum in the protocol, but although CoinShuffle can unmask the input public keys (associated with a UTXO resource that can be banned if DoS) which jam or corrupt the protocol, it can't insure the homomorphic sum of the outputs equals the sum of the inputs. I am not sure if it is possible to construct a homomorphic groupwise sum of inputs and outputs without jamming (DoS). I remember seeing some vague (not fully thought out w.r.t. to jamming?) discussion of this in the Confidential Transactions thread, but at least in the case of Compact Confidential Transactions, it doesn't seem as it would be possible because each the inputs' and outputs' fuzz has to coordinated for the entire transaction by someone who knows all the private values.

Thus it seems that we will still need Shen-Noether's Ring Confidential Transactions (or my claimed yet not yet published Zero Knowledge Transactions which integrates one-time rings with Compact Confidential Transactions). So Merkel tree (not Lamport because you may need to sign again else where if instance of protocol fails) sign the hash(es) for your transaction input(s) to enter the CoinShuffle protocol, then release your Ring Confidential Transactions (or Zero Knowledge Transactions) transaction (along with a new output hash) uncorrelated to IP addresses and transaction inputs via the CoinShuffle protocol. In the case where all the inputs and outputs are the same (which may often be the case with micro-transactions), then no need to use homomorphic sums and one-time ring signatures, and just release the uncommitted (not hidden values) outputs uncorrelated to the hash signature via the CoinShuffle (or any mixnet which defines an input set and can identify those who jam it) protocol.

So to correct my prior post, I still assert that "purely on chain anonymity is untenable" w.r.t. potential scenarios for DDoS at micro-transactions scale, i.e. neither Ring Confidential Transactions nor Zero Knowledge Transactions can scale to micro-transactions and remain entirely autonomous, as they will require some integration with a non-autonomous mixnet such as CoinShuffle. I reiterate the implied point from the upthread, that afaics it is not possible to mix hashes autonomously.

Edit: note the one-time rings must mix the transaction inputs of the participants of the CoinShuffle protocol (and not a systemic mixnet such as Tor or I2P which doesn't define an input set). Thus it enforces the rule that a group of UTXO must always mix with each other. That rule should normally be enforced so that rings can't be combinatorially unmasked, which is something I explained in detail in my Reddit discussion with Shen-Noether. Also since all the inputs can be thus marked as spent, they can be pruned from UTXO and thus enforced not be mixable again, and thus the combinatorial unmasking is prevented.

Edit#2: a flawed design which has better separation-of-concerns (could be used with any IP obfuscation mixnet such as Tor or I2P) is in round 1 for all participants to sign the hash(es) for their input(s) to the set of ECC public keys of the participants. Those who don't sign won't be included in the next round and if not enough sign, then round 1 is restarted with additional participants replacing those who failed to sign. Then in round 2 all participants who signed release their Ring Confidential Transactions or Zero Knowledge Transactions. The flaw is that round 2 can be spammed, because there is no correlation between those who participate in round 2 with those who signed in round 1.

I have been trying to think of some way to avoid CoinShuffle for micro-transaction anonymity because it is so slow due to multiple rounds of network communication. The only other solution I've thought of is to use the CoinShuffle method above to anonymously break your outputs into small morsels, then spend these morsels without homomorphic value hiding and via an IP obfuscation mixnet such as Tor or I2P. The untraceability and unlinkability is mostly retained as the CoinShuffle method will be employed to merge balances again (and then again to redistribute to anonymous output morsels).

IPv6 will not be a solution because it inverts the problem set by rendering the cost of an IP essentially free, so the adversary can in theory circumvent the ban on IP.


Note for CN one-time ring signatures, these target hashes (for the output of a transaction) would have to be sent to a public grouping (for the ring) before the transactions that will participate in that ring are signed. Note I am referring to presetting the hash that can be used to sign for the CN one-time ring when it is later spent, without identifying which public key in the ring will be signing in the future (similarly for CT + CN or CCT+ CN).

Thus this requirement for anti-DDoS would introduce a form of simultaneity requirement on CN one-time rings that could be jammed (spammed) as is the case for CoinJoin (and even the CoinShuffle improvement). As I had argued to gmaxwell in his CoinJoin thread in 2013, that blacklisting offenders is unworkable if there is no reference point, because precisely the point of adding anonymity is to destroy any reference point (other than an orthogonal one such as IP addresses, which as I have explained in this thread is also untenable at scale).

Thus I worried that anonymity might be untenable.

As we know that anonymity is fundamental to permissionless fungibility (note even governments have history of periodically decreeing prior issued cash as illegal). I think it has been generally the case throughout all cryptographic research I have reviewed that all anonymous mixnets have some DoS vulnerability if there isn't some identifiable non-free resource to attach to each participation.

Note if we have these Merkel tree hashes that must be signed for, then we have a blacklistable non-free resource (UTXO and assuming proofs of minimum values for CT or CCT) that can't be subverted. Thus if we can identify the adversary to a failed mixnet, then we can confiscate the UTXO. CoinShuffle offers a deterministic algorithm to unmask the adversary (so any resource committed with each public key can be confiscated).

For the mix group of hashes I proposed above, if each CN one-time ring spend transaction would claim one of the hashes (which is the hash can be used to spend the output created by that spend transaction), the problem is that signers can't know which public keys to include in their rings because there remains a simultaneity requirement on knowing the set of rings that match the set of hashes (without linking the each hash to a spendable public key which would defeat the entire point of CN ring signatures). The only solution I have been able to conjure is to use CoinShuffle to produce a group of hashes where every public key participating corresponds to some UTXO that can be confiscated.

[Edit: The other solution I considered is to force CN one-time rings to always mix with a defined set (e.g. by their ordering in the block chain), so that signers know which public keys to sign for irrespective of the group of hashes. Which I had pointed out (c.f. my last discussions with Shen-Noether in the Reddit thread for the citations) is required any way to prevent combinatorial unmasking. So then the group of hashes can be greater than than the number of input public keys for the ring, but the problem is the adversary can then spam the list of hashes and if spammer must associate a UTXO with each submission to the list, then again public keys are associated to the hashes.]

So while I believe I have refuted my worry that anonymity is entirely untenable, I now believe that purely on chain anonymity is untenable. Which I think was also obvious from that fact that CN one-time rings can be unmasked if an adversary can correlate IP addresses to persistent identities. So if we have to do the CoinShuffle any way (which also mixes the spenders' IP addresses so we don't have to rely on the unreliable anonymity offered by Tor of I2P), then there is no reason to do the CN one-time ring signtures. Just use CoinShuffle with either CT or CCT.

Thus note that Zerocash will always be (and Monero is until they replace CN with CoinShuffle) untenable.

It really helps to hear the perspective of core developers, so can know what they were thinking that I might have overlooked or error in my thought process and elucidation.


Yeah I thought of that too. As I think you have also implicitly alluded to above, one of the issues is that it can be an asymmetric attack if the adversary is calculating his hashes at a centralized location in Washington State or China where the electricity only costs 2 - 4 cents per kilowatt hour (which I think can be rented and I remember in the past how you mentioned the further economic asymmetry of renting versus the perpetual network hashrate which has varied amortizations) and is using the latest ASIC (and distributing the hashes over the wire to his bots).

If we are trying to maintain decentralization, then the verifier will assumed to have less than optimal access to those two resource costs.

Also userland payers (and payees if they need to hit up a full node, especially to lookup their Stealth address transactions) have an even higher asymmetry on PoW computation costs.

So by raising the cost sufficiently high enough on the adversary, maybe in some hypothetical scenario the entire network could be DoS'ed. In effect, this could resemble in some aspects a 51% attack. Note, please do not assume I am conflating proof-of-work for the block chain solutions with the PoW for submitting transactions, rather just recognizing some conceptual overlaps between the two.


But the banning is by IP. IP addresses are another finite resource (at least in IPv4 and the way ISPs employ it). If innocent users' IP addresses get banned because of this, they begin to see Bitcoin as unreliable or intermittent. Again hypothetical at some future scale wherein most users are sending micro-transactions every hour or minutes. And as that is scaling for the worst, if the Bitcoin network is also scaling in the wrong direction towards more centralized, then I am musing it becomes more vulnerable to such an attack.


I also contemplated this point when I wrote the OP.

But the two you compared are not symmetric threats relative to each other, because a relatively small quantity of bandwidth could ban a large quantity of IP addresses in Bitcoin's current anti-DDoS scheme.

Also to deal with bandwidth attacks effectively, one needs to move the filtering out to numerous points on the network. So if the filtering is resource intensive where electricity cost and ASIC amortization are significant potential asymmetry factors (which as you know is the case also for ECDSA, not just PoW employing SHA), then there is potentially less flexibility.

If the adversary can't get past your bandwidth filtering at the perimeter, then he switches to invalid signatures (or otherwise) where you must ban by IP address so it is not correct to assume that an adversary that can cause problems with banning by IP will also be able to cause problems with a bandwidth attack.

This is another reason I am trying to invert the asymmetric cost of filtering by forcing the adversary to burn UXTO (and as I said in the OP this demands a minimum transaction amount).

I had already thought through this deeply I think (even though I have 0 experience in networking and this is all just musings in my head).


I had read that mentioned some where before I wrote the OP.

But for the myriad of reasons above (e.g. losing the ideal of not relying on trust, centralized systems are easier to attack, and including my response to johoe including the issue of users finding a non-banned public node), I don't think that entirely solves the problem at-scale.

Trenchant to point out that DoS prevention exists not just to protect against DoS on all nodes directly, but also protection against using the nodes to attack each other (i.e. amplification). This is why it probably can't work for nodes to share information on which IPs they've banned— that is if we retain Satoshi's ideal of not needing to employ trust (i.e. that nodes are assumed to be untrustworthy yet the consensus algorithm of longest chain by PoW holds mathematically).


In the OP, I explained or at least vaguely alluded to my contemplation of users having difficulty finding a node that could accept their transaction if botnets were successful in getting the IP addresses of popular userland ISPs banned on many nodes (perhaps IPv6 could mitigate this?). I mentioned there would need to be some global way to look up which nodes hadn't yet banned which IPs. Then that global database could perhaps become another focal point of vulnerability. I am not at all confident if this is really a practical attack. I am musing about how it may be an issue at great scale when for example ever human on earth is sending 10 TX/s to the network. I have been thinking a lot about scaling and so I am trying to think how issue priorities morph at-scale.


Apparently Merkel signatures are orders-of-magnitude faster to verify than ECDSA.

Thus my idea is to use Merkel signatures instead of ECDSA (so the increased transaction space requirement may be mitigated since must fix block chain scaling any way before the attack I outlined becomes potentially practical). For anonymity signatures such as Confidential Transactions, also supply a Merkel signature (private key can be passed in the ECDH) but with the disadvantage that the payee must respend to self (to reset the private key so the payee doesn't know it in case the payee has a botnet) before finalizing the transaction.

There are ways to harden against these attacks-- e.g. require expensive POW on connect by the initiating party; but they have their own costs. (and are only somewhat helpful here, since botnets also tend to have a lot of cpu power)

Sending an invalid signature immediately get you kicked, Even with a botnet (or over tor) this significantly rate limits the behavior, even without the POW.

We don't consider this kind of attack a tier 1 denial of service because this, also because virtually any host that could be attacked this way could be attacked via a bandwidth exhaustion attack. There used to be variations of this were you could achieve many failed verifies per connection; but we eliminated those.

There is a widely deployed countermeasure, in any case: Do not accept inbound connections on high value nodes. Instead, run a couple public nodes, in place you don't care about, addnode those. For this particular attack you can also continue connecting out to random nodes (though there are other attacks which make it preferable to not do that and to only connect out to trusted and semitrusted nodes).

I believe that we'll eventually implement POW on connect, though more for other kinds of resource exhaustion attacks...

First, the anti-DDOS measure are there to prevent an attacker to use the distributed bitcoin network to DOS the network.  There is nothing that you can do in the bitcoin source to prevent DDOS attacks from Botnets that are under the control of the attacker.

I think you are correct with your assumptions.  Just like it is possible to DDOS the network from a botnet using DNS amplification attacks you can also use the bitcoin protocol.  I think the developers are aware of these and this is basically a risk that the bitcoin network has to live with.  Just like it is always possible to bring a big server farm down with a sophisticated DOS attack it would probably also be possible to DOS the bitcoin network.  The question is if the attacker has the bandwidth to sustain an attack to all nodes.  Note that all full nodes must be attacked individually for the attack you described.

I think there is no significantly faster way to distinguish a random number from a valid signature except by verifying the signature.  Banning based on IP address is the best one could do, with all its disadvantages.

For example, banning by IP address is incongruent with anonymity mixnets such as Tor.

Signature validation cost is critically significant if banning is by UTXO instead of IP.

Assuming the ban is by UTXO (instead of banning by IP) which have been correctly signed for but otherwise included in an invalid transaction previously, the banning is useless if validation cost is significant greater than cost to check if a UTXO is banned (because the adversary can simply send invalid signature transactions always to avoid the UTXO banning).

So the issue really hinges on whether IP banning is problematic at-scale, which is the issue I raised.


Thus I raised the issue that as TX/s scale, then probability of banning an innocent user by IP address increases. I am questioning whether banning by IP address is a robust DDoS defense at-scale.

At the generative essence conceptualization, doing any functionality by IP address breaks the fundamental end-to-end principle of the internet.


In my second suggestion, invalidly signed transactions would not ban the involved UTXO.

It bans not only those nodes which send invalid signature transactions but in general nodes that send any sort of invalid message too often. This can be invalid blocks, too many version messages, other messages without having sent a version message, too many address in ip addresses in addr message, messages that are too large, duplicate/expired/invalid-signature/whatever alerts, and invalid transactions.

There is no other way to validate a transaction besides validating everything. As soon as Bitcoin Core finds something invalid, it will stop the validation so as to not waste CPU power.

AFAIK the validation cost is not particularly significant.

Yes

Bitcoind will ban any node that is sending it spam, regardless of the number of users of that IP address. It won't take long for bitcoind to notice the spam and begin banning those misbehaving nodes. Also, bitcoind by default will only allow 125 connections total. This number can be configured to be more or less by the user.

With your second suggestion, wouldn't that make it possible for attackers to essentially DoS someone's address? They can just keep creating invalid transactions involving those addresses which then causes the actual owner of those addresses to be unable to spend his Bitcoin.

I have not looked at the code for bitcoind, and my Google searches have returned the following information for the anti-DDoS protection against spamming of invalid (signature or otherwise) transactions:



https://en.bitcoin.it/wiki/Weaknesses#Denial_of_Service_.28DoS.29_attacks


Five questions:

A) Thus am I correct to conclude that bitcoind bans IP addresses ("24 hours default") of peer nodes which too often send invalid signature transactions?

B) And I am correct to conclude that there is no less resource intensive algorithm to determine that an otherwise valid transaction (i.e. has valid UXTO, etc) has an invalid signature other than to expend the CPU resources to validate the signature (which is apparently on the order of up to 50,000 verifications per second on a late model top-of-line single Intel CPU)?

C) Am I correct that even if signatures are valid, then the cost of validating that the rest of the transaction is correct is not insignificant, especially if (Compact or just) Confidential Transactions is implemented?

D) Am I correct that ephemeral non-full node peers (a.k.a. userland "clients") connect to full-node peers in order to submit transactions to the bitcoind peer network?

E) If my assumptions A, B, C, and D above are correct, then am I correct to conclude that (although the above strategy is apparently acceptable now at current scale,) the existing anti-DDoS strategy in this case could potentially be inadequate when the number of clients submitting transactions to the peer network is greatly increased in scale (such as in a micro-transactions scenario) because it is often the case that multiple clients share the same IP address[1]. Thus botnets could be employed to spam the full nodes on the peer network with invalid transactions (not only to increase required peak CPU resources but also to flood the inbound connectivity bandwidth and/or thread pool of full nodes), then if bitcoind responds by banning IP addresses then innocent users might be banned too.

Afaics the only fully robust solution (at scale) is to either have sufficient full nodes to handle the peak potential botnet load (and a global database so valid clients know which full nodes haven't blocked their IP address, so clients don't have to contact multitudes of full nodes attempting to find one where their IP addresses isn't blocked), or to have some insignificant resources algorithm to determine if a signature is valid and then block on UTXO instead of IP address. One way I have contemplated to achieve the latter is that (at least when Stealth or Cryptonote destination addresses are not employed), then only the payer knows the public key of its hash that was publicly distributed (i.e. the UTXO refers to the hash of the public key address). Thus revealing the public key address is a 3-4 orders-of-magnitude faster[2] check that the sender likely knows the private key as well. Caveat that this is a heuristic and it suffers from being intercepted until the published transaction has propagated, although this can be fixed by using a Merkel tree signature, but the verification speed advantage drops to 1-2 orders-of-magnitude[3]. If Stealth or Cryptonote destination addresses are employed, then the prior payer knows the payee's public key address, thus could cause the payee's address to be banned, although this can be mitigated by having payee pay to himself and not release the good or service until that extra step is completed (which is another reason instant transactions would be useful). But his latter solution requires that the UTXO (or total of inputs to a transaction) not contain (total) values that are so small such that forfeiting them (and more so if bans are ephemeral) in spam attacks is an inconsequential cost to the spammer. But this will place a requirement on (Compact or just) Confidential Transactions that it must be able to prove that outputs are greater than a certain threshold, not just greater than 0.

Tangentially if one is thinking Lightning Networks (LN) is the solution to scaling, first note that LN requires block chain scaling as well (because participants have to execute enabling block chain transactions and these can be garbage collected in peak rates that require great peak load block chain scaling). And afaics LN can't support end-to-end principle anonymity, and in practice for it to work well (low latency, wide scale) the network will essentially be large corporate servers doing the glue for the user channels which can thus record all your transactions NSA-style.

Thoughts?

Edit: I am not referring to malleability attacks.

[1]	http://serverfault.com/questions/306837/how-many-computers-can-have-the-same-public-ip https://www.quora.com/How-many-home-customers-of-an-ISP-including-mobile-can-typically-share-the-same-IP-address-and-for-how-long
[2]	http://bench.cr.yp.to/results-hash.html https://www.imperialviolet.org/2010/12/21/eccspeed.html http://ed25519.cr.yp.to/ed25519-20110926.pdf http://security.stackexchange.com/questions/50878/ecdsa-vs-ecdh-vs-ed25519-vs-curve25519#comment80678_50890
[3]	http://bench.cr.yp.to/results-hash.html http://bench.cr.yp.to/results-sign.html http://bench.cr.yp.to/supercop.html http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.7139&rep=rep1&type=pdf#page=6 https://eprint.iacr.org/2005/442.pdf#page=10 http://www.cryptopp.com/benchmarks-p4.html