Update "surge pricing" to be more fair/limit based on operations

[MonsieurNicolas]

I think that the implementation to enforce a maximum number of transactions predated the addition of operations.

How this works today:
the "surge pricing" logic kicks in when a validator encounters more transaction candidates than maxTxPerLedger (defined in the ledger header). The first pass at filtering is done by sorting transaction candidates by fee ratio (defined as fee/min_fee where min_fee is base_fee*nb_operations).
The idea is that in a situation where too many transactions are pending, we prioritize the ones with higher average fees.
If fees are equal, the sourceID of the transactions is used as a tie breaker.

Proposal for new behavior:

1. build a transaction set that maximizes the number of operations in a ledger, up to the maximum maxOperationsPerLedger defined by the network
2. sort transactions using the average fee per operation as the way to compare transaction fees (done simply by comparing left.fee * right.nb_ops with right.fee * left.nb_ops)
3. break ties using a deterministic yet randomizing scheme, giving priority to different accounts for each ledger. Using sourceID XOR hash_ofPreviousLedger seems to fit the bill.

In order to implement 1 and 2, the candidate transaction set is build as follows:

1. trim the transaction set such that it only includes valid transactions (including sequence number and fee)
2. perform a lexicographical sort the candidate transactions by fee (descending), xored source ID (ascending), sequence number (ascending)
3. iterate over that sorted list:
   1. if the transaction can fit in the candidate set (ie, newTxSetOpCount <= maxOperationsPerLedger), add it to the set
   2. otherwise, skip the transaction and any other transactions from the same source account

Something else to discuss here is what to do with the ledger header.
Right now the XDR is:

struct LedgerHeader
{
    uint32 ledgerVersion;    // the protocol version of the ledger
    Hash previousLedgerHash; // hash of the previous ledger header
    StellarValue scpValue;   // what consensus agreed to
    Hash txSetResultHash;    // the TransactionResultSet that led to this ledger
    Hash bucketListHash;     // hash of the ledger state

    uint32 ledgerSeq; // sequence number of this ledger

    int64 totalCoins; // total number of stroops in existence.
                      // 10,000,000 stroops in 1 XLM

    int64 feePool;       // fees burned since last inflation run
    uint32 inflationSeq; // inflation sequence number

    uint64 idPool; // last used global ID, used for generating objects

    uint32 baseFee;     // base fee per operation in stroops
    uint32 baseReserve; // account base reserve in stroops

    uint32 maxTxSetSize; // maximum size a transaction set can be

    Hash skipList[4]; // hashes of ledgers in the past. allows you to jump back
                      // in time without walking the chain back ledger by ledger
                      // each slot contains the oldest ledger that is mod of
                      // either 50  5000  50000 or 500000 depending on index
                      // skipList[0] mod(50), skipList[1] mod(5000), etc

    // reserved for future use
    union switch (int v)
    {
    case 0:
        void;
    }
    ext;
};

in particular the line

    uint32 maxTxSetSize; // maximum size a transaction set can be

There are two options on how we would change the ledger header:

1. change the name of maxTxSetSize to be more generic, something like txSetSize, that maps to "number of transactions" in older versions of the protocol and "number of operations" in newer versions of the protocol (binary format stays the same).
2. make the ext union support v = 1, we would add the new field

    // reserved for future use
    union switch (int v)
    {
    case 0:
        void;
    case 1:
        uint32 maxOperationsPerLedger;
    }
    ext;

maxTxSize would be set to numeric_limits<uint32>::max()

I prefer option 1 as it keeps the ledger header tidy.
There are very few consumers of this field, and for the most part only use it for reporting. Code that actually cares about it can, just like core's implementation, use it based on what the protocol version is.

This issue was first opened as a core issue stellar/stellar-core#1030

[vogel]

I'm not sure that

The first pass at filtering is done by sorting transaction candidates by fee.
is true.

TxSetFrame::surgePricingFilter sorts accounts by min(getFeeRatio) per account. getFeeRatio counts ratio of fee being paid to minimum fee that should be paid by transaction. So a tx with 1 op that pays 1 XLM of fee (ratio 100000) will be choosen over tx with 100 op that pays 2 XLM of fee (ratio 2000).

Comment sort tx by amount of fee they have paid is just false.

[MonsieurNicolas]

Oh I see - I missed that part. It makes the change even simpler. As part of this change we should ditch the fee ratio and implement proper comparison between transactions, converting to a ratio (double) is suboptimal. I am editing the proposal to reflect that.

[robdenison]

1. trim the transaction set such that it only includes valid transactions (including sequence number and fee)

Does this mean that for a given account, you will include only the transaction with the lowest sequence number (i.e. the sequence number that is the account's current sequence number plus one)? Or (as the next step leads me to believe) will you include any transaction whose sequence number is part of a continuous range starting with the account's current sequence number plus one?

2. perform a lexicographical sort the candidate transactions by fee (descending), xored source ID (ascending), sequence number (ascending)
3. iterate over that sorted list:
   i. if the transaction can fit in the candidate set (ie, newTxSetOpCount <= maxOperationsPerLedger), add it to the set
   ii. otherwise, skip the transaction and any other transactions from the same source account

I'm not sure lexicographic sort works here. If I understand this correctly, it would result in Alice's transaction 6 being ordered before Alice's transaction 5, if the former has a higher fee-per-operation. You could skip over such out-of-order transactions, but then you'll have to do another sweep to include them, leading to the counterintuitive property that setting a higher fee on transaction 6 would mean that it gets included later than if it had the same fee as transaction 5.

I think the best sorting algorithm might be what Geth does—for each account, construct a queue of transactions for that account, sorted with the lowest sequence number first. Then construct a heap of those queues, sorted based on the feerate of the first transaction in each queue (so that the queue whose first transaction has the highest feerate is on top of the heap). After each transaction, shift that transaction out of the queue, then fix the heap.

This suggests another possible tiebreaker: the feerate of the second transaction in the queue for that account (and then the third, and so on and so forth). But this wouldn't even get you to complete optimization (which is a pretty complex knapsack problem), and you would still need to ultimately resort to a final psuedo-random tiebreaker like xored source ID.

[MonsieurNicolas]

I'm not sure lexicographic sort works here. If I understand this correctly, it would result in Alice's transaction 6 being ordered before Alice's transaction 5, if the former has a higher fee-per-operation. You could skip over such out-of-order transactions, but then you'll have to do another sweep to include them, leading to the counterintuitive property that setting a higher fee on transaction 6 would mean that it gets included later than if it had the same fee as transaction 5.

yes you are correct that if somebody submits a transaction with higher fee it may cause artificial delay in their account's queue.

Reason I kept the simple sort (we do a similar sort today) as opposed to a more complex scheme is that it seems to be the wrong trade off: we can avoid making our implementation more complex and less efficient by not accommodating something that clients can easily deal with (in this case, submit batches of transactions at the same price).

[MonsieurNicolas]

Something that I forgot to mention in the changes that we should make:
right now if an account blows past their limit in a transaction set (ie, they submit too many transactions to the network), all their transactions are removed from the proposed set.

With this change, we should keep track of that limit as we add transactions to the txset (instead of post processing).

[MonsieurNicolas]

I have been thinking about this a bit more.

As we're looking at fairness, I think that it's actually important to preserve the "round robin" property that we have when applying transactions (for transactions with the same fee ratio) otherwise we may end allocating too many transactions from the same account in the same ledger.

This ends up being pretty much what @robdenison described (reworded below to summarize).

I would suggest not using the next transaction fee ratio to break ties, but instead use pseudo-randomness.

So the algorithm is:

1. for each account, construct a queue of transactions for that account, sorted by sequence number in ascending order
2. construct a heap of those queues, sorted by:
   • the fee rate of the first transaction in each queue (so that the queue whose first transaction has the highest fee rate is on top of the heap)
   • account ID (pseudo-random)
3. nb_operations_to_add = txSetSize
4. while (nb_operations_to_add > 0 && !heap.empty())
   • queue = heap.pop()
   • if nb_operations(first transaction "tx" from queue) <= nb_operations_to_add
     • push tx into txSet
     • nb_operations_to_add = nb_operations_to_add - nb_operations(tx)
     • pop tx from queue
     • if queue non empty, push it into the heap

[hmatejx]

Would it be detrimental to order the queues in the heap randomly after sorting by fee rate, that is without referring to sourceID? To eliminate predictability in the filter?

I was thinking of a hypothetical spammer with many (tens of thousands) accounts "racing" the sort by choosing the particular one that results in the lowest sourceID XOR hash_ofPreviousLedger.

[MonsieurNicolas]

ah yes, when I first wrote the proposal I thought we would need surge pricing at the consensus layer (we don't).

Instead, we can use any random seed for sorting accounts (ie, replace hash_ofPreviousLedger by any good local source of entropy). Reason for this is that we can't expect the set of transactions to be the same on all validators anyways and surge pricing is local to validators anyways.

The problem that is left is to design a good function to pick between two transaction sets during consensus (which txset to pick when there are several nominated): right now we pick the one with the highest number of transactions first then the highest hash.
I think that instead, the sort order should be ("operations count", "highest combined fee", "highest hash"), or something like that in order to preserve the output of surge pricing.

[MonsieurNicolas]

I put together a first draft of https://github.com/stellar/stellar-protocol/blob/master/core/cap-0005.md that should address this particular issue.

I had to add a policy to disallow arbitrary increase of txSetBaseFee.

[MonsieurNicolas]

I thought of an issue in transaction submission that needs to be addressed.

With the current proposal, the replace by fee mechanism is actually not a real deterrent against DoSing the network:
while an attacker has to submit a transaction with an increased bid of basefee, the effective fee that will be paid out is unchanged if there is no network congestion (as it's determined by the last transaction in the transaction set), and is only marginally increased if there is.

The problem can be mitigated in two ways:

• don't flood transactions that replaced another right away, delay by some time (like 5 seconds). If that transaction gets replaced before getting flooded, cancel the pending flood. As the new transaction is known to the node, it may be considered during nomination but doesn't propagate too fast otherwise.
• increase in fee should not be basefee but the minfee for the transaction getting replaced, as this allows to reflect the fact that the new transaction really pays for the overhead of both the old and new transaction (overhead in signature verification in particular). This makes the overall network converge towards actually charging for both transactions when it gets over network capacity.

[theaeolianmachine]

Closing this issue, as CAP-0005 has been accepted.