New proposed relay policy for XT

[Tom Harding]

After some thought, followed by much slogging through cherry-picks from core, I've submitted what I believe would be a very good limited-memory relay policy for XT.  I hope to generate some discussion and find ways to make this policy better.

It's not possible to make these choices without guiding principles, so it was much easier to make these choices with the aid of the principles explained in the XT manifesto.  Here's what the change does

Transactions Are Dropped After 2 Hours
This is a very "XT" change.  Here's why:  XT users believe that unconfirmed transactions will always be important.  But at the same time, languishing transactions are a huge problem with bitcoin.

Dropping transactions when they remain unconfirmed for 2 hours gives a clear answer to the question of how to bump your fee.  The answer is to wait 2 hours, and submit another transaction with a higher fee to an XT node.  It won't complain.

After 2 hours, you can also use the funds to pay someone else instead.  Or you can pay yourself as a way of cancelling the transaction.


When Necessary, Drop the Lowest-Fee Transactions
This rule is also directly related to the XT accommodation of unconfirmed transactions.  Unconfirmed double-spends are much easier to pull off when different nodes have different ideas about which transactions were seen first.

There are two important network constituents that XT must do its best to match policy with, if it is to promote relay consistency.  The first is miners, and miners are directly incentivized to choose the transactions with the highest fees, while still, we ask, honoring first-seen.  The second is Bitcoin Core nodes, which are now beginning to adopt a mempool/relay policy that is essentially to keep those that pay the highest fees (although they also added a dynamic minimum fee which is NOT  part of this proposal for XT).

For the technically inclined, there is a tweak to pure feerate sorting.  The tweak is to include a transaction ancestors' SIZE but not their FEES in the effective feerate for a tx.  In other words, every tx is assumed to pay for the size of its required unconfirmed ancestors, in addition to its own size. Beneficial effects of this are:
 - Unconfirmed chains are directly discouraged, in proportion to their length in bytes
 - Memory attacks involving high-fee ancestors and low-fee tx, or vice versa, are avoided
 - The effect fades away as the ancestors are confirmed


Give it a try if you can. 
https://github.com/bitcoinxt/bitcoinxt/pull/90

[Tom Zander]

On Wednesday 28 Oct 2015 18:14:33 Tom Harding wrote:
> */Transactions Are Dropped After 2 Hours/*

> /*When Necessary, Drop the Lowest-Fee Transactions*/

These two proposals make sense only for a centralized system.
They are directly countering the advantages and differences that a distributed
system has.

I choose to interpret this in a positive way and that is you fundamentally
don't understand distributed systems.

I would be against this solution and if this goes into Core I think it would
very much strengthen our belief that Core is no longer a proponent of what
bitcoin (currently) is.


Distributed computing is a well documented concept and its main advantage is
redundancy. This is not redundancy of having fail-over, instead this is from
life where individual differences make the whole stronger.
Its about simple rules creating complex behaviour as a group.

In this case, and I'm stealing from Toomins excellent email last night (please
read it).

«If you have 5000 nodes, and each one randomly evicts 90% of the transactions
in their mempools all at once (non-bytewise-weighted) in a single round,
then the probability that an arbitrary transaction will be eliminated is
1.6E-229.»

This means that your chance has the effect of going from a "we never remove a
transaction sent to the network until its mined" to "it will be forgotten in 2
hours by everyone".

[Tom Harding]

XT took a step forward by sharing information on the network about the existence of conflicting spends.

The random drop policy goes in the opposite direction, by adding to uncertainty that ANY particular transaction will be mined, no matter how early it is sent, no matter how high a fee it pays -- we've made it more likely that a double-spend will be mined without the miner even knowing.

Consensus is the accomplishment of the blockchain.  The network should try to converge on it.

We're talking about resource-limited nodes here.  We can't pretend that we've somehow accidentally created a massive distributed mempool that will hold N*M transactions and get them all mined.

We need to think about the usability of this money.  Languishing transactions are a major problem for bitcoin users and they deserve a way to address that problem without having to defeat their own wallet.

[Mike Hearn]

The random drop policy goes in the opposite direction, by adding to uncertainty that ANY particular transaction will be mined, no matter how early it is sent, no matter how high a fee it pays -- we've made it more likely that a double-spend will be mined without the miner even knowing.

Remember that the random-drop happens only during transaction flooding attacks. It's simply never meant to trigger at all in normal operation. And unfortunately if the network is being flooded with transactions and goes over-capacity, you can never do a reliable job. Some people will always lose. There's an assumption that legit transactions will always have a higher fee than spam transactions, but I see no evidence that this is true: it amounts to wishful thinking.

Random drop with a large mempool can give >99.5% certainty that the selected transaction is a DoS transaction, for any given node. And because it's random by node, even in the unlikely event that the selected tx is legit, it'll live on in some other memory pool.

The problem with Core's order-by-fee policy is that when an attack starts, the algorithm is guaranteed to delete all the legitimate transactions waiting for confirmation .... because they'll be sitting at the min relay fee. That's the opposite of what is wanted!

[Tom Zander]

On Thursday 29 Oct 2015 06:46:57 Tom Harding wrote:
> The random drop policy goes in the opposite direction, by adding to
> uncertainty that ANY particular transaction will be mined, no matter how
> early it is sent, no matter how high a fee it pays -- we've made it more
> likely that a double-spend will be mined without the miner even knowing.

From this I read that you conclude that random dropping a transaction means a
miner will not see the transaction.

Is that right?

If you think that then you fundamentally don't understand distributed
computing. Or statistics. Or both.

Read my reddit post to get some more info;

https://www.reddit.com/r/bitcoinxt/comments/3qona7/distributed_nature_of_bitcoin_means_a_transaction/

> We need to think about the usability of this money. Languishing
> transactions are a major problem for bitcoin users and they deserve a way
> to address that problem without having to defeat their own wallet.

I agree. Please help support XT and get bigger blocks.

[Tom Harding]

I don't think the network can stop an "attacker" who wants to pay higher fees than everybody else.  The incentive for such an attacker to go directly to miners is too great.

[Gavin Andresen]

On Thu, Oct 29, 2015 at 11:46 AM, Tom Harding <to...@thinlink.com> wrote:

I don't think the network can stop an "attacker" who wants to pay higher fees than everybody else.  The incentive for such an attacker to go directly to miners is too great.

"Go directly to miners" is actually pretty difficult. And block propagation optimization work will give miners a strong incentive to announce the transactions they're planning on putting into their blocks. Actually, Matt's relay network already gives them a pretty strong incentive to broadcast transactions they're putting into their blocks before they find a block....

Of course if an attacker is willing to pay significantly higher fees for a sustained period of time they'll be able to crowd out lower-paying transactions. It is impossible to distinguish "attacker" from "legitimate high-transaction-usage of the chain" (and I don't think developers have any right to make policy on what is "legitimate" usage).

The advantage of random eviction schemes is they mitigate an attacker's ability to pay marginally more to crowd out other transactions; the more fees they pay, the more transactions they crowd out, but there's no point where they crowd out ALL other transactions (which is the "attacker wins" scenario).

--

--
Gavin Andresen

[Mike Hearn]

I don't think the network can stop an "attacker" who wants to pay higher fees than everybody else.  The incentive for such an attacker to go directly to miners is too great.

To me this is like saying

   "Any attacker can always pay miners to just shut Bitcoin down. Therefore we may as well make it easy for them to do so."

Well, no. Let's think about it.

Do you think that if someone just added up all the fee revenue miners get today, and then went to them individually and said "hey, I'll pay you X+1 satoshi if you just mine empty blocks", that they'd all say yes? As that's what you're arguing.

I'm pretty sure they wouldn't.  In this hypothetical case they can easily identify the attacker and ignore them. When the attacker doesn't talk to them directly but just floods the system with transactions, it gets harder to identify which transactions are the attackers and which aren't.

But if we have sufficient capacity we don't really need any clever mechanism to figure out which transactions are "bad" and which represent price-raising legitimate trading activity. When the mempool becomes vastly larger than the normal size we can just shoot at random and be correct nearly all the time.

[Tom Harding]

On 10/29/2015 9:09 AM, Mike Hearn wrote:

I don't think the network can stop an "attacker" who wants to pay higher fees than everybody else.  The incentive for such an attacker to go directly to miners is too great.

To me this is like saying

   "Any attacker can always pay miners to just shut Bitcoin down. Therefore we may as well make it easy for them to do so."

Well, pushing up the price of blockspace is not really shutting the system down.  But I rush to add, higher prices for blockspace are NOT some great thing.

There is a market; that is good.  Isn't our job is to make the market as efficient and high-volume as possible, without artificial constraints or distortions?

[Tom Harding]

With a feerate mempool-limit policy, if things get tight, the user knows how to deal with the problem -- pay more fees.

It  sounds like the alternative we are talking about is graceful service degradation for everybody.  That is the choice.

I'm happy to be offering the first alternative.  I think we should totally embrace tx relay and confirmation as the most fundamental service available to be bought with bitcoin -- and not passed around randomly.  Bitcoin is an economic system after all.

To the Zanders out there, I repeat -- in no way am I arguing for higher fees.  I am arguing for an efficient market and a product (the bitcoin network) that works better.  To back up this assertion, ask Jonathan Toomim, Adam (multipool), and Slush -- I'm pretty sure I've contributed the most hashing to BIP101 of anyone so far.  The rest of you should pick things up a bit.

[Jonathan Toomim]

On Oct 29, 2015, at 11:36 AM, Tom Harding <to...@thinlink.com> wrote:

With a feerate mempool-limit policy, if things get tight, the user knows how to deal with the problem -- pay more fees.

It  sounds like the alternative we are talking about is graceful service degradation for everybody.  That is the choice.

I don't think this is an accurate assessment of the two strategies. The mempool limiting policy has very little to do with the mining/CreateNewBlock policy. Miners will probably have much more RAM allocated to mempool than the average non-mining node, and if they don't (or if they want fast CreateNewBlock times, and we haven't fixed that function yet), they'll use minrelaytxfee to hard-limit their mempools. Even if miners don't, there will be quite a few different mining nodes out there, so the probability that a high-fee tx will get evicted and stay evicted from most of the major pools is small. Thus, with the random eviction mempool limiting policy, incorporation of a tx into a block will follow miner policies with about the same accuracy as when no nodes have limited mempools.

Random eviction means that you get a distributed mempool that is much more complete than any single node's mempool. 

If blocks are full, then a user who wants timely confirmation should pay more. That applies to both mempool strategies, because that's the mining policy in CreateNewBlock. The difference between the two strategies is that with the random eviction strategy, almost no transactions will be forgotten by the network, whereas with deterministic lowest-fee-first eviction, the low-fee transactions are systematically and predictably wiped out. The main problem with this strategy is that an attacker can spam low-fee transactions with the knowledge that only a constant number of them will ever get confirmed, allowing the attacker to wipe out 100% of transactions with fees below a certain threshold. For example, the attacker might spend a bunch of coin in a bunch of transactions with different vendors using low-medium fees, collect 0-conf rewards, then spam the network with tx with slightly higher fees and flush all the unconfirmed tx out of the mempools.

[Tom Zander]

On Thursday 29 Oct 2015 11:36:10 Tom Harding wrote:
> To the Zanders out there, I repeat -- in no way am I arguing for higher
> fees.

It was never my impression that you were :)

[Jonathan Toomim]

On Oct 29, 2015, at 12:57 PM, Jonathan Toomim <j...@toom.im> wrote:

Even if miners don't, there will be quite a few different mining nodes out there, so the probability that a high-fee tx will get evicted and stay evicted from most of the major pools is small. 

Should've proofread. I meant to say this:

Even if miners don't have enough memory for the whole mempool and a non-spam high-fee tx gets evicted from a miner's mempool, there will be quite a few different mining nodes out there, so the probability that a high-fee tx will get evicted and stay evicted from most of the major pools is small. 

[Tom Harding]

As you say, a fullnode plays a limited role.  The most important decision it makes is whether to add/relay a tx when it first sees it.

In times of high use, the fee-sorted mempool makes this decision using what can be considered a node-local minimum relay fee that adjusts in real time (unlike core, which pegs this fee with a half life, for unconvincing reasons).

By contrast, Gavin's emergency solution, which you are using, draws a line at the 2-block fee, which I think in all the attacks so far, is generally much higher than the lowest-fee tx in the mempool.

Below the 2-block level, the new tx is rejected, and not relayed.  The selection of the ejected tx is not nearly as important as the fact that, as soon as the mempool fills up, the minimum relay fee shoots directly up to the 2-block level.  *The attacker can do this without offering fees that high himself.*

To fix this, you need to sort the mempool.  After you do that, I suppose we could still evict randomly, but weighting by the "largest" heuristic is much inferior to weighing by feerate.  Low-feerate txes are the ones that clog things up the most.

In fact, a simple way to implement that would be to use PR 90 and pick a random offset into the feerate index, instead of evicting the last one.

[Jonathan Toomim]

On Oct 29, 2015, at 5:39 PM, Tom Harding <to...@thinlink.com> wrote:

By contrast, Gavin's emergency solution, which you are using, draws a line at the 2-block fee, which I think in all the attacks so far, is generally much higher than the lowest-fee tx in the mempool.

I am unfamiliar with this. Can you elaborate, or tell me where to find more information?

[Jonathan Toomim]

Oh, I see what you're referring to:

            else if ((int64_t)pool.size() < nMaxPoolTx) {
                pool.addUnchecked(hash, entry, !IsInitialBlockDownload());
            }
            else { // Mempool full...
                static int64_t lastEstimate = 0; // Only call estimateFee every 10 minutes
                static CFeeRate highFee;
                if (entry.GetTime()-lastEstimate > 600) {
                    lastEstimate = entry.GetTime();
                    highFee = pool.estimateFee(2);
                }
                if (dPriority < AllowFreeThreshold() && CFeeRate(nFees, nSize) < highFee) {
                    // Low-priority, low-fee: dropped immediately
                    LogPrint("mempool", "mempool full, dropped %s\n", hash.ToString());
                    SyncWithWallets(tx, NULL, false); // Let wallet know it exists
                    return false;
                }
                // High enough priority/fee: add to pool, we'll evict somebody below
                pool.addUnchecked(hash, entry, !IsInitialBlockDownload());
            }

You are incorrect that I am using that. PR #89 adds another variable, nMaxPoolBytes, and performs bytewise evictions when nMaxPoolBytes is exceeded. I did not change this to also test for nMaxPoolBytes. In the current flood, where we have a lot of 14 kB transactions, nMaxPoolBytes is exceeded long before nMaxPoolTx is. 

I did it this way out of ignorance, not by design. I hadn't actually read that part of Gavin's code closely.

Below the 2-block level, the new tx is rejected, and not relayed.  The selection of the ejected tx is not nearly as important as the fact that, as soon as the mempool fills up, the minimum relay fee shoots directly up to the 2-block level.  *The attacker can do this without offering fees that high himself.*

Refusing to accept a low-fee transaction is not a 0-conf attack risk. Systematically evicting low-fee transactions is. If nodes refuse to accept/relay a transaction, then the recipient doesn't see the transaction and doesn't consider himself paid. 

I'm not sure I like the 2-block fee limit, but I don't see it as a big problem. My preference is to not add nMaxPoolBytes as a condition for engaging that limit.

... I suppose we could still evict randomly, but weighting by the "largest" heuristic is much inferior to weighing by feerate.  Low-feerate txes are the ones that clog things up the most.

I don't agree. Memory is the constrained resource here, not feerate. There might be very important, high-value transactions in mempool that just happen to have very low feerates. It's important that the distributed mempool not forget such transactions. It might be a while before it confirms because the fee is low, but there is a lot more at stake than just the fee. This is node policy, not mining policy -- we're trying to keep an accurate copy of ledger changes that need to be made; we're not trying to maximize some 

miner's profit.

For 0-conf to be useful, it needs to be impractical for a sender to engineer a transaction that will never confirm.

[Note: I don't really like the lowest-feerate-of-two request that Hearn and Zander made for evictRandomBytewise, but I figured it's a pretty weak bias, and not likely to cause low feerate transactions to be systematically eliminable.]

[Tom Zander]

On Thursday 29 Oct 2015 17:39:04 Tom Harding wrote:
> As you say, a fullnode plays a limited role. The most important decision
> it makes is whether to add/relay a tx when it first sees it.

You state you are trying to make Bitcoin better at something, still not sure
what.
Then your characterization of the role of a validating node is plain wrong.
You can't expect to make a distributed system work properly if you dismiss
half the work that a validating node does.

We all agree that a transaction should be propagated as far as possible when
it is first offered to the network. Provided it is valid, naturally.

You would be missing the bigger picture if it stopped there. The only reason
for propagating is to essentially add it to the collective mempool that is
Bitcoin. Which works by redundancy and that is the reason you need to
propagate at firs sight.

But the details on how synchronization happens after that, how mempools are
filled when they are just turned on, etc. That is equally important.


I now understand why you are convinced that the random eviction makes no
sense. Its because you are ignoring the mempool as a distributed database.
Complete with synchronization features and self-protecting eviction policies.

This difference in perspective means that "times of high use" is a concept
that just doesn't apply.
Similarly to the Amazon cloud; if you have high use, just spin up a few more
nodes.
Don't make people pay more just to get the ability to get their request
serviced. We have massive redundancy, please use it.

> By contrast, Gavin's emergency solution, which you are using, draws a line
> at the 2-block fee, which I think in all the attacks so far, is generally
> much higher than the lowest-fee tx in the mempool.

I'm in agreement with you that that emergency solution should be replaced by
the one that Jonathan is working on.
Accept new ones regardless of fee and evict random based on Jonathans code if
the mempool is too large.

> To fix [2-block-fee rejects], you need to sort the mempool.

This has been addressed numerous times on this mailinglist, sorry for
rehashing.
The idea to use fees as some sort of indication that something is not
acceptable or spam is an idea that many here reject.
We have the free-tx limitation, and we have the minrelay fee. They are good.
But any dynamic fee determination makes me uncomfortable.

Therefore any solution that sorts the mempool based on fee makes no sense to
suggest.


I'd like to implore you to try to understand the points we make, because we
have so much in common and you keep on pushing your ideas and quite
aggressively telling us our solutions are wrong.
While as far as I can tell the solutions are born from a difference in
perspective, not a difference in ideology.

If you have any questions about the points we made in the last days, please
ask them. We are all friends here on this ML.

[Tom Zander]

On Thursday 29 Oct 2015 21:07:38 Jonathan Toomim wrote:
> For 0-conf to be useful, it needs to be impractical for a sender to engineer
> a transaction that will never confirm.

I would disagree with that conclusion because the need for zero-conf only
applies to a tiny subset of all the transactions Bitcoin sees whereas your
statement applies to all possible Bitcoin transactions.

For zero-conf to be successful, in my opinion, the merchant needs to do the
validation of the transaction to determine the success of confirmation.
For instance they can state that a zero-fee transaction won't be allowed as
payment for a coffee. Or one that is larger than 1KB. etc.

Any random eviction policies are completely irrelevant to this topic since any
good merchant software will keep (hopefully) that transaction in their mempool
and mark it as "their own" so it will not get evicted and will periodically be
re-broadcast.

Anyway, bottom line is that this isn't really our problem to solve.

[Tom Zander]

On Thursday 29 Oct 2015 21:07:38 Jonathan Toomim wrote:

> [Note: I don't really like the lowest-feerate-of-two request that Hearn and
> Zander made for evictRandomBytewise, but I figured it's a pretty weak bias,
> and not likely to cause low feerate transactions to be systematically
> eliminable.]

To give credit where it came from ;)

https://groups.google.com/d/msg/bitcoin-xt/3YwHm56RuLw/ItCJEm16AwAJ

[Mike Hearn]

Well, pushing up the price of blockspace is not really shutting the system down.  But I rush to add, higher prices for blockspace are NOT some great thing.

Sure, we all agree high fees are not good.

I suspect your first sentence gets to the core of the debate here. In my mind there's a clear delineation between "good/legit" transactions and DoS transactions. A DoS or spam transaction is an attacker moving coins around for no reason beyond trying to stop people who are actually trading from using the system.

If they do that by making it so expensive to use the system that actual traders go elsewhere, then that is in my eye a successful DoS attack - they have denied service, which is the essence of such an attack.

Note a few things about this definition:

• This is not the same as what Luke Dashjr uses, even though he talks about spam all the time. Luke tends to classify any usage he thinks is wasteful as spam even if there are in fact independent economic actors trading with each other for mutual gain.
  
  
• It isn't a nihilist worldview  - I disagree with Gavin that Bitcoin users/developers shouldn't try and handle the question of which transactions are 'legitimate' when talking about DoS attacks. In fact it was Gavin who suggested the idea of coin age/priority in the first place :)
  
  On the other hand, we agree that it can be very hard to do this, given the poverty of signals the Bitcoin protocol gives us.
  
  
• A mere rise in prices is not a DoS attack, if the transactions pushing out the lower-fee transactions have some economic purpose beyond the price rise itself.
  
  
• Given this definition, there is simply no downside to dropping DoS transactions if/when we can, as they exist only to get rid of other users who are actually sending money and giving Bitcoin value.

If you look at the Core worldview, they tend to see DoS attacks as not even attacks at all. It seems if they ended up with a system that has only one user, say, a world government that is willing to divert 0.01% of tax revenue to buying up all the block space, then they'd consider that a job well done and not a problem because fee revenue had been maximised thus the outcome is "rational". Even if that meant Bitcoin had no users.

That's an extreme example of what can happen if you become ultra-narrowly focused on a single factor or variable.

[Tom Harding]

On 10/29/2015 9:07 PM, Jonathan Toomim wrote:

This is node policy, not mining policy -- we're trying to keep an accurate copy of ledger changes that need to be made; we're not trying to maximize some 

miner's profit.

I agree with this and have suggested a metric that represents a full node's view of what should be minimized:

expectedByteStay [= sizeBytes * expectedBlocksToConfirm(feeRate)]

This quantity only depends on the confirmation time implied by the fee rate, not the rate itself.  Using it would isolate the node's actions from being unduly influenced by transactions that pay the miner exorbitantly but don't leave the mempool any quicker than other txes with a 1-block fee.

Something I really dislike about the random approach is that at the limit, a dumb spam flood will totally wreak havoc -- each incoming transaction will generally cause one random transaction to be evicted.

With a sorted mempool, a dumb spam flood first evicts all the transactions that pay less than the spam, then the spam itself starts getting rejected as soon as it's added.  The rest of the pool is untouched.

[Mike Hearn]

expectedByteStay [= sizeBytes * expectedBlocksToConfirm(feeRate)]

This quantity only depends on the confirmation time implied by the fee rate, not the rate itself.  Using it would isolate the node's actions from being unduly influenced by transactions that pay the miner exorbitantly but don't leave the mempool any quicker than other txes with a 1-block fee.

Right, the fee estimator code calculates that.

 

Something I really dislike about the random approach is that at the limit, a dumb spam flood will totally wreak havoc -- each incoming transaction will generally cause one random transaction to be evicted.

It won't cause havoc because the random tx that gets evicted will, with overwhelming probability, be a DoS transaction. And nobody cares if those get evicted: by definition. If someone cared (other than the attacker) then it wouldn't be a DoS tx.

This is the key point and I'm uncertain why we're unable to reach agreement on it. Random eviction yields ideal results practically all the time assuming a mempool that's much larger than the block size (actual not limit).

[Tom Zander]

On Thursday 29 Oct 2015 21:44:34 Tom Harding wrote:
> Something I really dislike about the random approach is that at the
> limit, a dumb spam flood will totally wreak havoc -- each incoming
> transaction will generally cause one random transaction to be evicted.

Ok, spam flood.

So lets do sme numbers.
We have a node that has 2K tx in its mempool and then a spam flood comes in,
adding 150Ktx of transactions that are twice the size of the average of 'real'
ones. (very similar to the last attack).

The spam is added with no restrictions until the nodes mempool is full.
Full is 50MiB (serialized TXes).
Lets assume a normal TX is 800 bytes on average. That means 1562.5kib of the
mempool is used by them. Or, 3% of the available space.
Conversely; 97% of the mempool is used by spam.

The remaining 118232 spam transactions come in and will each replace an
existing transaction.

Using XT master the chance of a 'good' tx being replaced ejected is 6% (1)

Using Jonathans latest patch the chance of a 'good' transaction being ejected
goes down to 0.009% (assuming the spam pays less fee). (2)


Now, if you a normal human and don't know the finer points of statistics you
might think that the repetitive ejecting makes things worse.
This is not the case; the statistics don't change because you do it often. The
inputs stay the same. The output too.

So, with the statistics staying the same, the actual amount of transactions
evicted after we added 150000 spam transactions on top of the 2K correct
transactions is 106. About half a percent.


We are only looking at a single node, mind you.
The neighbouring node has ejected about 106 valid tx-es too. But they are
different TXes. So nothing is actually lost because the whisper protocol
forwards txes to neighbours on a regular basis.


1) 2000 /(31768 + 2000) = 0.0592.

2) 3% * 3% is 0.03 * 0.03 = 0.0009

> With a sorted mempool, a dumb spam flood first evicts all the
> transactions that pay less than the spam, then the spam itself starts
> getting rejected as soon as it's added. The rest of the pool is untouched.

This scenario means its much more predictable what will happen. Because all
pools do the same thing. All you need to do is make spam of higher fee and you
are guaranteed to eject valid transactions. Most of them. On all nodes.
How is that better?

Please let me/us know which part doesn't "click" for you and still makes you
uncomfortable.

Have a nice day!

[Tom Harding]

Mike --

I completely agree with your characterization of the the debate, thank you.  It doesn't change my position, but at least I can agree that you've framed it well and honestly.

Bitcoin is unique among internet protocols in its ability to impose a direct monetary cost on spam, as a way of controlling it.  This should be leveraged to the absolute fullest extent possible.  We should not shy away from it.  It's the ultimate dog food.

The moment we try to reserve space for anything other than those who use the system itself to buy space within it, we have all the same anti-DoS problems as any other network.  Few know more about those other problems than you do.

It's not a panacea, but it is a no-brainer tool that should be maximized before looking elsewhere.

On 10/30/2015 3:35 AM, Mike Hearn wrote:

Well, pushing up the price of blockspace is not really shutting the system down.  But I rush to add, higher prices for blockspace are NOT some great thing.

--
You received this message because you are subscribed to the Google Groups "bitcoin-xt" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoin-xt+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Tom Harding]

On 10/30/2015 7:03 AM, Mike Hearn wrote:

Something I really dislike about the random approach is that at the limit, a dumb spam flood will totally wreak havoc -- each incoming transaction will generally cause one random transaction to be evicted.

It won't cause havoc because the random tx that gets evicted will, with overwhelming probability, be a DoS transaction. And nobody cares if those get evicted: by definition. If someone cared (other than the attacker) then it wouldn't be a DoS tx.

This is the key point and I'm uncertain why we're unable to reach agreement on it. Random eviction yields ideal results practically all the time assuming a mempool that's much larger than the block size (actual not limit).

I didn't stress a crucial point as much as I should have.  The selection of the ejected tx is not nearly as important as the decision to relay it.

With a full-byte pool, XT master and PR 89 still relay all the spam.  This is not okay.

With a full-count pool, XT master and PR 89 generally relays all the spam but makes an exception for not-low-priority or high-fee.

It's no mystery why this had to be done.  It's because there is no working definition of spam.  With PR 90, the working definition of spam is a transaction that pays less than the other 300MB of transactions in the pool.

expectedByteStay [= sizeBytes * expectedBlocksToConfirm(feeRate)]

This quantity only depends on the confirmation time implied by the fee rate, not the rate itself.  Using it would isolate the node's actions from being unduly influenced by transactions that pay the miner exorbitantly but don't leave the mempool any quicker than other txes with a 1-block fee.

Right, the fee estimator code calculates that.

The second part is the fee estimator.  The overall quantity is something I'm suggesting as an improvement to plain old feerate as the mempool tx sort.

[Tom Harding]

On 10/30/2015 7:38 AM, Tom Zander wrote:

Now, if you a normal human and don't know the finer points of statistics you might think that the repetitive ejecting makes things worse.

Sometimes disagreements are not caused by the other person not understanding.  But since you do understand statistics, could you please review this proposal?  I've had a tough time getting good questions asked by reviewers.

With a sorted mempool, a dumb spam flood first evicts all the
transactions that pay less than the spam, then the spam itself starts
getting rejected as soon as it's added.  The rest of the pool is untouched.

This scenario means its much more predictable what will happen.  Because all 
pools do the same thing. All you need to do is make spam of higher fee and you 
are guaranteed to eject valid transactions. Most of them. On all nodes.
How is that better?

I'm afraid this is another of those disagreements on premise.  Predictable blocks are good, and so are predictable mempools.  We can't force mempools to be predictable-- thankfully, nobody has that power.  But we wouldn't be talking about it if we didn't think XT's behavior had an influence, and we don't have to try to make them different.

Look at the transaction confidence services (mycelium, blochcypher, etc.).  They monitor how well-propagated a transaction is.  We've made those services work better by presenting them with hard evidence of double-spends.  Let's not allow a spammer to break them by getting his spam relayed all over the place and making all XT nodes have wildly different mempools.

[Jonathan Toomim]

On Oct 30, 2015, at 1:33 PM, Tom Harding <to...@thinlink.com> wrote:

Look at the transaction confidence services (mycelium, blochcypher, etc.).  They monitor how well-propagated a transaction is.  We've made those services work better by presenting them with hard evidence of double-spends.  Let's not allow a spammer to break them by getting his spam relayed all over the place and making all XT nodes have wildly different mempools.

If the network is under spam attack, and mempools are evicting transactions randomly, then a service like blockcypher will report low saturation, and may not consider them secure enough for 0-conf. I think this is correct, failsafe behavior (though there is obviously some calibration work that such services will have to do to prevent frivolous failure of 0-conf). We want the probability of confirmation to be greater than or equal to the estimates of confirmation probability.

Breaking 0-conf likelihood estimators is not a big deal. Making the transactions get forgotten by the network is a big deal. If a transaction gets reported as likely to confirm, but is subsequently forgotten because a spam attack hits, that's a big deal. If a transaction gets reported as very likely to confirm, but then a spam attack hits and is updated to somewhat likely to confirm, then gets confirmed a day later, that is not a big deal. It's bad UX, sure, but it maintains as much safety as feasible.

[Tom Harding]

On 10/30/2015 1:52 PM, Jonathan Toomim wrote:

Making the transactions get forgotten by the network is a big deal.

Fundamental disagreement here.  As is clear from the other component to PR 90, I believe we should actually encourage the network to forget about transactions after 2 hours, unless those who care about them retransmit them.

Core has a similar change merged, but with far too long a timeout (72 hours) to have any usability benefit.

Also, I think need to point out that after the initial relay, nodes do absolutely nothing to proactively share the contents of their mempools with other nodes.  It is by design only a relay network, not a global shared database.  I don't know what the "whisper protocol" Zander mentioned is.  If I've totally missed this, somebody please tell me where to find the code.

[Jonathan Toomim]

On Oct 30, 2015, at 1:15 PM, Tom Harding <to...@thinlink.com> wrote:

The selection of the ejected tx is not nearly as important as the decision to relay it.

I might support deterministic adaptive fee-based relay decisions combined with stochastic lightly-fee-biased evictions.

[Tom Harding]

So like, a quadratic weight towards the lower feerate end of the index?  Is this because you want to let some of the spam in, so the spammer has to pay more?

[Jonathan Toomim]

I'm not saying I'm convinced; I'm saying I might be convincible. And only for the relay decisions. I think the evictions are about as biased now as we should allow without having done more math/statistics/simulations.

For the relay/acceptance criteria, I don't currently see any reason why a hard floor (with automatic adjustment) would be improper or harmful.

[Mike Hearn]

Bitcoin is unique among internet protocols in its ability to impose a direct monetary cost on spam, as a way of controlling it.  This should be leveraged to the absolute fullest extent possible.  We should not shy away from it.  It's the ultimate dog food. 

The moment we try to reserve space for anything other than those who use the system itself to buy space within it, we have all the same anti-DoS problems as any other network.  Few know more about those other problems than you do.

Yes, I do indeed know something about handling spam and DoS. That's why I'm afraid I disagree that this is a no brainer approach.

Quick detour into the history of email spam:

In the early 2000's Bill Gates, not a man famous for being an idiot, had the same idea as Bitcoin Core devs do now. He wanted to use micropayments to solve the problem of spam. The project was called Penny Black after the stamp. Due to the lack of Bitcoin the original idea was to use PoW directly, as in Adam Back's Hashcash scheme, with migration to real money later.

This idea turned out to be simple, intuitive, and wrong.

The main problem was that it conflated bulk email with spam. They aren't the same thing though: spam is useless mail the recipient doesn't want. Bulk email can often be highly desirable, like delivery notifications from Amazon. Much spam is bulk, but not always.

The second problem was a built in but very lazy assumption that good bulk mailers would be totally OK with expending vast resources to send mails, and spammers wouldn't. But there was no reason to believe that. Some types of spam could be highly profitable even when the spammers were paying their own delivery costs, e.g. porn affiliates. And some types of organisation that relied on bulk email (e.g. open source announce lists) didn't have much money.

Using micropayments to fight spam would have been a scorched earth approach that treated all mail senders equally, even though they weren't at all equal.

The actual fix for email spam was to introduce the notion of sender reputation and recipient voting feedback. Senders that get positive votes can send as much bulk email as they like. Senders that get negative reputation get sent first to the sin bin (spam folder) and if they keep being sent there, eventually blocked entirely. 

That left the problem of sorting mail into streams by sender, and as SMTP wasn't designed to make that easy that is actually 95% of the work that goes into a spam filter. But that's a legacy issue. DKIM (digitally signing your mails using a DNS linked key) eliminates that work in cases where it's used.

Soooooo how does this apply to Bitcoin? Well, we can see the same thinking at work:

1. An assumption that heavy usage is always abusive. No. Heavy users like exchanges aren't bad, and the Bitcoin community should actually want to attract them, not tax them.
   
   
2. An assumption that attackers are cheap and will go away when presented with even a tiny cost, whereas legit users will not. So far Bitcoin's experience has been that fees have generally gone up over time (I once lowered them by 10x but that was due to a 10x increase in exchange rate, so the change just reset dollar-denominated fees to what they had previously been before the bubble). Yet attacks happen anyway.

I find the argument about relay bandwidth is unpersuasive. Spends are limited by the attackers UTXO availability.

Let's imagine you have enough UTXOs to put 200mb of data into the mempool and nodes have been limited by default to 100mb. So you use up half your UTXOs and now the pool is full. You continue broadcasting transactions to a few peers and they randomly free up UTXOs from your first half. But the problem is you don't know which ones. So by the time you broadcast your second set, your UTXO set is fragmented: a whole lot of these outputs have been freed up, but randomly so across nodes, so any transaction you send is very likely to use at least one that isn't free according to most of your nodes.

In the end even if you cycle back and try to spend all the UTXOs again, you won't get very far because so many of your attempts will be seen as double spends. (nb: i'm ignoring the double spend relay here as that is only supposed to happen once per utxo).

Now back here in the present day, relay bandwidth simply isn't a resource DoS attackers are attempting to use up. They are:

• Attacking RAM
• Attacking direct bandwidth using massive UDP floods

So it's tough to worry about abuses of relay bandwidth that are not likely to work very well, given the existence of attackers who can take out the entire network if they choose to.

[Tom Harding]

Mike,

The Penny Black story. When you asked the question "how does this apply
to bitcoin?" given the email spam solution you gave, I thought you were
going to lose everyone by proposing some kind of identity system.

But you only mentioned 1) a new uncontested point about heavy users, and
2) the fact that attacks happen even though average fees are rising,
which doesn't address what happens if relay fees rise in response to the
attack.

---
Limited UTXO's are pretty similar to limited money. Just add a step 0
where spammer converts his money to a maximal number of UTXO's.
Fee-prioritized relay aims to make him spend the money.

---
Consider our rich spammer. Suppose he offers just a little more than a
hypothetical full-pool floating minimum. Well, you can offer just a
little again more than him. No big deal.

Suppose he offers a lot more. Shall we conclude that the p2p network
must not have a full-pool floating minimum, because we must stop him
from buying all the relay space, and all the block space? We cannot
possibly stop him. He can just publish his own feed at
superhighfeetransactions.com and advertise it. He can mix in some
normal transactions, so mere appearance in the feed is not
proof-of-spam, and gives plausible deniability to miners.

[chaosgrid]

I'd like to re-visit this topic. I like the idea of a distributed mempool of nodes. But miners have to keep the whole mempool on their servers for this to work.

Never-expiring transactions are fine for situations where there is a spam attack, but this gets really messy in the situation we are experiencing now: a continuously growing backlog.

I think we desperately need a transaction timeout. We can probably discuss about the timeframe, but I think it is clear we need to evict transactions at some point. This has two benefits:

- Miners can estimate how large their mempool can grow at most. Since miners are encouraged to have an unlimited mempool, this is very useful.

- Users and wallets have a number of hours/days after which they can be fairly certain their transaction expired and will never get mined. They can then decide to re-broadcast with a higher fee or not.

I dont see any disadvantage in letting transactions expire. It also does not go against the idea of a distributed mempool.

Btw.: Could somebody point me at where Core merged the 72 hour eviction rule?

[Jonathan Toomim]

I think probabilistic eviction is sufficient to banish transactions that linger for a long time.

Random eviction will break IBLTs, though. That's probably a deal-breaker for random eviction once IBLT code gets finished.

Since miners are encouraged to have an unlimited mempool, this is very useful.

This is currently completely incorrect. CreateNewBlock takes a really long time when run on large mempools. This can be fixed with a rewrite of CNB, which has been done twice, but until that code is released, miners will maintain very compact mempools.

[chaosgrid]

I don't understand. How does XT's distributed mempool work if miners themselves have only a subset of transactions?

Let's assume that there are only 3 mining pools. All 3 of them have a compact mempool (-> 3 small mempools). This means a significant amount of transactions never gets mined, even transactions that paid a sufficient fee (since they might have been dropped randomly).

Am I missing something?

[Jonathan Toomim]

If there are only 3 mining pools, then you only get about 3x as many transactions in the distributed mempool as a single miner would have. If there are 10 mining pools, then 10x. 

It works better if miners operate nodes with greater mempool size than the average node. Unfortunately that's currently not the case, but I hope it will be soon once we finish fixing CreateNewBlock.

[chaosgrid]

That assumes that miners are the only nodes participating in the distributed mempool.

Assume every node has a max mempool limit of 10. There are 3 mining pools and 7 other nodes, 10 nodes total.

10 x 10 = 100 max transaction count in the whole system before it is guaranteed that a transaction is lost.

But in fact, of those 100 transactions, only 30 get mined since transactions are never re-broadcast on their own.

So, in conclusion, I don't understand how a distributed mempool can work at all if miners do not run with an unlimited mempool (or a calculated multiple of the average mempool limit but that's impossible to calculate). And an unlimited mempool is only possible if you can estimate how large it can grow. Without transaction expiration, you cannot estimate that.

Also, I think it is really sloppy to rely on these probabilistic assumptions that at some point old transactions get dropped. Let's assume BIP-101 gets activated and we never reach the mempool limit until in a few years. If you never restart your node, you can have transactions sitting in your mempool from ages ago. I don't understand what the benefit of that is.

I thought XT is about helping users and real world applications of bitcoin - and from a user perspective it absolutely makes sense to drop transactions after a certain timeframe. This is essentially an automatic un-stuck feature activated after X amount of time.

[Christophe Biocca]

> only 30 get mined since transactions are never re-broadcast on their own

Correct me if I'm wrong but doesn't the mempool trickle code mean that unconfirmed-but-still-valid transactions do get re-sent over time?

[Tom Harding]

Chaosgrid --

Expiration was merged to core as part of #6722, which was mostly about full-mempool limiting. 

That change did other things which are complex and not really warranted in my opinion.  Mainly it pegs the default relay fee higher for a period of time in an effort to "recover" fees for transactions that were relayed but later evicted.  The whole network has to pay for that.  It also has a complex scheme to divide part of the mempool into 75 "fee bands" and it fails to set incentives against chains (only providing hard limits).

And there have been / are about to be more changes after that, all of them making things even more complex.

XT #90 is a much simple fee-based proposal that includes a 2-hour mempool timeout, which is probably the most aggressive value that could work.  It might need to be less aggressive based on actual confirmation experience.  The fee-estimate data for a node with a very high limit should should be sufficient to make an informed decision.

[chaosgrid]

Thanks!

I think the current situation shows the benefits of your solution. Many users have problems with stuck transactions. After 2 hours, they could be certain that the transaction did not make it and can re-submit with a new (higher) fee. It does not solve any scalability issues but it sure makes the whole network more responsive for the end user.

Anyways, just now another problem occurred to me regarding the distributed mempool.

Lets say the network is at capacity. We submit a normal-fee transaction (as in, it does not get immediatly confirmed because there are priority transactions).

In a situation where the miners do not have an unlimited mempool, a distributed mempool now makes it easier(!) to doublespend. Because some nodes will evict our transaction while some others will not. This means that for example 50% of the nodes have our transaction. We can now send a doublespend with a higher fee and 50% of the network will happily accept it (FULL RBF behaviour).

Considering miners also don't have all transactions (no unlimited mempool), 50% of miners also happily accept the transaction. Because the fee is higher, it gets mined and we have now full RBF behaviour across the network. And since double spends get relayed by default with XT, it is even worse because you can be sure that every node that does not have the higher-fee transaction will include it.

So, I would really advise to ditch the distributed mempool idea alltogether and go with a more simple and user-friendly solution as Tom proposed.