How We Simplified Fees on the Stellar Network

How do you change the fee on a transaction? In a very technical sense, this is a trick question. It is impossible to change the fee on a transaction. What you can actually do is create a new transaction with the desired fee, then collect the necessary signatures to form a transaction envelope. You might argue that this is purely a semantic difference. It isn't. The two transactions require different signatures, so they are indeed different. If you need signatures from multiple parties, then there is no guarantee that you can convince everyone to actually sign the new transaction.

Perhaps you are familiar with our general rule of thumb for fees, "choose the highest fee you're willing to pay to ensure your transaction makes the ledger." Why would you ever want to adjust your fee if you follow this advice? You wouldn't — that's why it's good advice. But this strategy didn't even make sense prior to Protocol 11 because you always paid whatever fee you specified. The only obvious option for people constructing pre-signed or pre-authorized transactions was to simply guess a fee that seemed high at the time, perhaps 1 XLM. A few years later, when it is time to actually submit one of those transactions, you might find that the minimum fee to be included in the ledger is higher than you anticipated. Prior to Protocol 13, you would be out of luck.

We don't know how many people did this because pre-signed transactions aren't stored on the ledger. But we do know that we care about the problem, even if it only affected one transaction worth a single stroop of XLM. Users need to be confident that it will be possible to execute their transactions, otherwise they will simply use another financial network to avoid risk. Imagine that you were buying a house and your contract required you to escrow 1% of the sale price as an earnest payment. You enter into a contract with an escrow agent which authorizes the agent to disburse the funds under certain circumstances. When the time comes for disbursal, the agent informs you that the contract is legally unenforceable and your funds have been rendered inaccessible. You are very upset, and vow never to use that escrow agent again. Perhaps you even try to take legal action against the agent. This hypothetical is analogous to not being able to execute a pre-signed transaction, which is like a contract enforced by the network.

Before I can explain what a fee-bump transaction is, let's quickly review some Stellar terminology. An operation is the smallest unit of work in the Stellar protocol. Sending a payment or managing an offer are examples of operations. A transaction contains up to 100 operations which are applied atomically, along with other information such as the fee and the sequence number. Although we often talk about submitting a transaction to the Stellar network, this is a subtle abuse of language. In reality, transactions do not carry signatures so they cannot be submitted to the network. Transaction envelopes, which wrap a transaction and the corresponding signatures, are what clients actually submit to the network.

In Protocol 13, we have added not just a fee-bump transaction but also a fee-bump transaction envelope. Like a regular transaction envelope, a fee-bump transaction envelope wraps a fee-bump transaction and the corresponding signatures. But a fee-bump transaction does not contain operations. Instead, it contains a transaction envelope! A fee-bump transaction also specifies a fee and an account that will pay that fee, both of which override what was specified in the contained transaction.

Suppose that you have a transaction envelope which cannot be included in the ledger because the fee is too low. The transaction requires signatures from multiple parties, and one of the parties refuses to sign a new transaction with a higher fee because they will lose money if the transaction executes. Fee-bump transactions allow you to avoid this conflict entirely. First you create a fee-bump transaction which contains the transaction envelope that you want to submit, specifying the fee that you want to pay and the account that will pay it. If you control that account, then you can sign the fee-bump transaction and form a fee-bump transaction envelope from the fee-bump transaction and your signature. Now this can be submitted successfully if the new fee is sufficiently high.

What happens when you actually submit a transaction envelope to a Stellar-Core node? First, it validates the transaction envelope. The validation process can be thought of as Stellar-Core checking that there is no obvious reason that the transaction envelope cannot execute successfully. This includes checking that signatures are valid, that the fee per operation exceeds the base fee, and that the sequence number is sequential. Invalid transactions are discarded immediately, while valid transactions are stored in the transaction queue. The transaction queue — which is sometimes called a memory pool or mempool in other systems — is essentially the set of transaction envelopes that node would consider for inclusion in the next ledger if that node could choose unilaterally.

Submitted fee-bump transaction envelopes go through a similar process. But unlike transaction envelopes, fee-bump transaction envelopes support the replace-by-fee mechanism. When replace-by-fee occurs, a transaction envelope or fee-bump transaction envelope in the transaction queue is replaced by a fee-bump transaction envelope with the same sequence number and source account, but a fee that is at least 10x higher. Imagine, for example, that you submit a transaction envelope to a Stellar-Core node which is accepted because its fee was above the minimum fee. But your transaction envelope does not get included in the ledger due to surge pricing, and you want to accelerate the process. Without the replace-by-fee mechanism, you would not be able to successfully submit a fee-bump transaction envelope with a higher fee because the sequence number would not be sequential. With it, however, you are actually able to to bump the fee.

Why can’t replace-by-fee occur for any fee that is higher than the old fee? This definitely would have been simpler and less expensive to use. But it also would have created the potential for a denial-of-service attack. We take system security seriously, so we had to design a mechanism which mitigated this attack.

The original Core Advancement Proposal (CAP) for fee-bump transactions was written by OrbitLens of stellar.expert. This proposal contained an innovative solution: the Stellar-Core node should just add the fee-bump transaction to the transaction queue without discarding the original transaction. When choosing transactions to include in the next ledger, a node would include a transaction plus zero or more fee-bump transactions which contain it. This mitigated the potential denial-of-service attack, but it was also a huge departure from the existing Stellar protocol. Sometimes fundamental change is justified, even required. OrbitLens' proposal was accepted by the protocol committee on June 26th, 2019 and I began working on the implementation shortly after with the goal of including fee-bump transactions in Protocol 12. When I finished my first draft of the implementation, we were not confident in its correctness.

The implementation of Stellar-Core is held to the highest standards, so we had no option but to exclude fee-bump transactions from Protocol 12 and return to the drawing board. This was an opportunity, not a defeat. When we iterate on a CAP, we try to identify desirable properties and guarantees, then design a mechanism that achieves them. Our guiding principle is to get the strongest guarantees with the simplest mechanism. The original proposal provided a very strong guarantee, because it would have been possible to successfully submit any fee-bump transaction envelope that increases the fee of a valid transaction envelope to any fee that you can afford. The problem was that this guarantee could only be achieved with a complex mechanism.

So we turned our attention to the search for a simpler mechanism that could still provide relatively strong guarantees. We discovered that requiring 10x higher fees to trigger replace-by-fee mitigated the denial-of-service attack. While weaker than the original guarantee, this approach still guarantees that it is possible to bump the fee of any transaction envelope although you may not be able to choose the exact fee that you want. This approach became the basis for our current implementation.

There are important lessons here about changing the Stellar protocol. First, even changes that sound simple, such as making it possible to increase the fee on a transaction, can be extremely challenging to design and implement. Second, we need to strike the right balance between providing the strongest guarantees that we can and designing features which can actually be implemented safely.