Thoughts on the Mempool Issue and Upgrading

[aszepieniec]

@danda

But critically, this is only true if they are not performing wasteful work duplicating the work of other nodes. So, as I’ve been saying since day 1, it is important for the network’s health that a mechanism is found to help proof-upgraders to coordinate so that we get close to a situation where only one upgrader works on each transaction that needs to be upgraded.

We are observing transactions that are broadcast but do not make it into blocks, even when no other transactions are broadcast at the same time. At first approximation the logical explanation would seem to be not enough Upgrade work, not too much Upgrade work.

While I agree that work duplication is a problem worthy of attention, I don’t see how it is an adequate explainer for the observed problem.

@danda

The first thing I notice about this proposal is that it changes the mining dynamics and would thus appear to require a fork. I don’t see that as a big problem at this early stage, but I would like to have a discussion of the tradeoffs and merits of this proposal vs the much simpler scheme I proposed before that does not require any changes to mining.

I do not think it requires a fork. How did you come to this conclusion?

As for your suggestion, let me respond to this:

@danda

A simple improvement would be to add a message so that a prover can tell other peers “hey I’m working on Transaction X”, so they can ignore transaction X for some time, perhaps something like 10 minutes or 2 more blocks. After that if the transaction is still in their mempool (has not been included in a block) they might consider it again.

1. It solves a different problem, one we do not have presently.

The problem addressed by this note is the very high likelihood of a transaction not being confirmed in the next block, even when no other transactions are being broadcast in the same time.

The problem addressed by the cited proposal is the reasonable likelihood of an initiated transaction being ignored when broadcast more or less simultaneously with others.

2. It involves modifying the P2P message format, which is possible but fraught with difficulties. The last time we tried to add a new message type, nodes instantly closed the connection after receiving such a message. Did we solve that issue yet?
3. Upgraders are in adversarial relationships with each other. If I know which transactions you are working on, I can deprive you of fees by upgrading the same ones.

@danda

I think I would need more convincing that a node should only be allowed to do one of the 3.

If you are going to do more than one, you are bound to do two or more poorly. I think it is beneficial to the node operator and to the network to specialize. But that’s just an intuition. I’m not willing to die on this hill.

@danda

So they are not competing with eachother unless and until there are more proof upgraders available than transactions in the mempool. And until then, and perhaps after, coordination is the most profitable strategy for them individually and collectively.

Even if there are two Upgraders and 100 transactions in the mempool, the Upgraders can be in competition with each other. The fees they can collect are not necessarily the same for every transaction. So conceivably all transactions have a fee of 0.01 NPT except for one whose fee is 10 NPT. Obviously the two Upgraders will compete to Upgrade the one high-fee transaction because if they cede that task to the counterparty they will have less profit.

If instead they coordinate to divide the fees more or less equally, then whoever doesn’t get the high fee paying transaction takes on the task of upgrading 99 low fee paying transactions. So in this case there is still an imbalance of workload.

@danda

it does’t make any sense to select a Tx to upgrade that another node is already upgrading.

This is true from a collective perspective, but false from an individual perspective. An individual Upgrader can rationally decide to Upgrade the same transaction they know others are Upgrading so that they can benefit from the fee instead.

@danda

@aszepieniec

Ultimately the throughput capacity is limited by the block size and the number of Upgraders on the network

That statement is incomplete. Consider the two extreme cases:

1. all proof upgraders upgrade each tx
2. only one proof upgrader ever performs work for a given tx.

The throughput capacity of the network will be very different for these two scenarios.

(2) is clearly more optimal, and any design should attempt to achieve it, or get near it, at least while Tx outnumber upgraders.

The statement is false in case (1). Assume the system is running at full capacity. Then double the number of Upgraders and double the number of transactions. The workload of every Upgrader has doubled and they can’t keep up with the block time. Only half of the transactions can make it through.

The statement is true in case (2). Assume the system is running at full capacity. Then double the number of Upgraders and double the number of transactions. The workload of every individual Upgrader is the same. (There is an overhead due to one extra merge step being required but this one extra step is asymptotically negligible.)

So clearly the system I am describing resembles (2) more than it resembles (1).

However, the question is not: what is the optimal distribution of work, in the abstract? That answer is obvious. The question is, how best to approximate the optimal distribution of work in an adversarial environment? I think you will be hard-pressed to find a solution that works better than markets and prices.

So how does the present proposal approximate the optimal distribution of work in an adversarial environment? In a (probably way too abstract) nutshell, Upgraders adopt a Nash-optimal strategy, which most probably balances profit with randomness. How to find this Nash equilibrium? We can discuss strategies but ultimately the best way is to leverage arbitrage: let Upgraders chase profits and over time they will converge to a Nash equilibrium.