CAP: 0042
Title: Multi-Part Transaction Sets
Working Group:
Owner: [email protected]
Authors: Dmytro Kozhevin <@dmkozh>
Status: Final
Created: 2021-11-29
Discussion: https://groups.google.com/g/stellar-dev/c/_h3hd_Y3IiY/m/5QeYy5kcBgAJ
Protocol version: 20
This CAP gives validators control of which fee policy to use for individual transactions included in a ledger.
TBD
Right now, there is no mechanism that makes it possible to implement different fee structures based on transaction set composition; as a consequence, transaction sets can sometimes be heavily biased towards undesirable behaviors such as spikes of arbitrage trades that eventually fail.
This CAP aims to correct this by isolating subsets of transactions that can compete on fees without causing overall fees to increase. At the same time, it makes it possible to expand policies to other dimensions in the future.
The Stellar network aims to give equitable access to the global financial infrastructure, in particular the network should not benefit a minority of participants at the expense of others.
This CAP aims at restoring balance between use cases on the network.
Right now transaction fees are computed for a given ledger based on CAP-0005 Throttling and transaction pricing improvements.
CAP-005 defines:
- How a transaction set (to be applied for the next ledger) gets constructed from an arbitrary number of candidate transactions as to enforce the policy that puts a bound on the number of operations present in any given ledger.
- The base fee to use when applying a transaction set
This CAP generalizes the above in the following way:
- It allows to subdivide transaction sets into components.
- Components are sets of transactions with their own fee policy.
- Validators get to select how to decompose and assign policies.
Note that this CAP does not modify how transactions gets applied (ie: the apply order) other than fee computation.
This patch of XDR changes is based on the XDR files in commit (b9501ae3288a5879d457841168cb4b249691cb43) of stellar-core.
---
src/protocol-curr/xdr/Stellar-ledger.x | 60 +++++++++++++++++++++++++-
1 file changed, 59 insertions(+), 1 deletion(-)
diff --git a/src/protocol-curr/xdr/Stellar-ledger.x b/src/protocol-curr/xdr/Stellar-ledger.x
index 84b84cbf..9c2cbcee 100644
--- a/src/protocol-curr/xdr/Stellar-ledger.x
+++ b/src/protocol-curr/xdr/Stellar-ledger.x
@@ -176,6 +176,29 @@ case METAENTRY:
BucketMetadata metaEntry;
};
+enum TxSetComponentType
+{
+ // txs with effective fee <= bid derived from a base fee (if any).
+ // If base fee is not specified, no discount is applied.
+ TXSET_COMP_TXS_MAYBE_DISCOUNTED_FEE = 0
+};
+
+union TxSetComponent switch (TxSetComponentType type)
+{
+case TXSET_COMP_TXS_MAYBE_DISCOUNTED_FEE:
+ struct
+ {
+ int64* baseFee;
+ TransactionEnvelope txs<>;
+ } txsMaybeDiscountedFee;
+};
+
+union TransactionPhase switch (int v)
+{
+case 0:
+ TxSetComponent v0Components<>;
+};
+
// Transaction sets are the unit used by SCP to decide on transitions
// between ledgers
struct TransactionSet
@@ -184,6 +207,19 @@ struct TransactionSet
TransactionEnvelope txs<>;
};
+struct TransactionSetV1
+{
+ Hash previousLedgerHash;
+ TransactionPhase phases<>;
+};
+
+union GeneralizedTransactionSet switch (int v)
+{
+// We consider the legacy TransactionSet to be v0.
+case 1:
+ TransactionSetV1 v1TxSet;
+};
+
struct TransactionResultPair
{
Hash transactionHash;
@@ -203,11 +239,13 @@ struct TransactionHistoryEntry
uint32 ledgerSeq;
TransactionSet txSet;
- // reserved for future use
+ // when v != 0, txSet must be empty
union switch (int v)
{
case 0:
void;
+ case 1:
+ GeneralizedTransactionSet generalizedTxSet;
}
ext;
};
@@ -358,9 +396,29 @@ struct LedgerCloseMetaV0
SCPHistoryEntry scpInfo<>;
};
+struct LedgerCloseMetaV1
+{
+ LedgerHeaderHistoryEntry ledgerHeader;
+
+ GeneralizedTransactionSet txSet;
+
+ // NB: transactions are sorted in apply order here
+ // fees for all transactions are processed first
+ // followed by applying transactions
+ TransactionResultMeta txProcessing<>;
+
+ // upgrades are applied last
+ UpgradeEntryMeta upgradesProcessing<>;
+
+ // other misc information attached to the ledger close
+ SCPHistoryEntry scpInfo<>;
+};
+
union LedgerCloseMeta switch (int v)
{
case 0:
LedgerCloseMetaV0 v0;
+case 1:
+ LedgerCloseMetaV1 v1;
};
}SCP messages and ledger header reference transaction sets by hash. Consequently, the preimage supplied can transparently be migrated to GeneralizedTransactionSet when voting for a transaction set that can be applied using the version of the protocol with this CAP.
The only place where it is not possible to transparently migrate to GeneralizedTransactionSet is in the TransactionHistoryEntry that are used in history archives where the txSet field is being deprecated instead.
This allows to publish the actual hash preimage used during consensus rounds.
In summary: if lcl.ledgerHeader.version is less than P (version this CAP takes effect), the preimage must be a TransactionSet, otherwise it must be a GeneralizedTransactionSet.
A v1TxSet is validated using the following rules:
previousLedgerHashis equal to the hash of the previous ledger.phasescontains exactly one element (this is an extension point).v0Components- contains at least one transaction (hence empty
v1TxSetcan only be represented by a single phase with no components) - transactions from different components do not overlap
- the union of all transactions together forms a valid transaction set that can be applied to a legder (transactions are valid, accounts can pay for fees, transactions sequence numbers form valid source account chains).
- fee bids for any transaction satisfy the "minimum fee requirement", i.e. its fee bid is greater or equal to the minimum fee derived from
ledgerHeader.baseFee - all the
baseFeevalues in differentTXSET_COMP_TXS_MAYBE_DISCOUNTED_FEEcomponents are unique TXSET_COMP_TXS_MAYBE_DISCOUNTED_FEEwith non-emptybaseFee:baseFee >= ledgerHeader.baseFee(a corollary from the global minimum fee bid requirement).- each transaction in this component has a fee bid greater than or equal to the minimum fee bid derived from
baseFee(for a regular transaction that would translate tobaseFee * numberOfTransactionOperations <= bidFee)
- contains at least one transaction (hence empty
The effective fee for a given transaction is computed in the following way:
- If the transaction is in a
TXSET_COMP_TXS_MAYBE_DISCOUNTED_FEEcomponent andbaseFeeis empty, its effective fee is its fee bid. - If the transaction is in a
TXSET_COMP_TXS_MAYBE_DISCOUNTED_FEEcomponent andbaseFeeis set, its effective fee is derived from a base fee equal to that component'sbaseFee.
Just like today, this CAP does not specify the exact algorithm used to produce a valid value as to make it easier for implementations to compete on the quality of transaction sets.
Here are a few example strategies that could be employed:
- Do not give any fee discount to transactions containing "high traffic operations" (validators may keep a tally of recent operations to decide when this makes sense).
- Limit the number of operations in a ledger that interact with the DEX (ie: any operation that could cross an offer).
- Reserve some ledger capacity for transactions that are simple payment.
- Define a few "high priority lanes" that can be easily identified, and one "catch all" lane limited in capacity for unknown transactions.
The order used by the nomination protocol's combine candidate function needs to be modified to support GeneralizedTransactionSet.
Values are sorted in lexicographic order by:
- number of operations (as to favor network throughput) unchanged,
- sum of all fee bids (as to maximize quality of transaction sets) new,
- total fee to collect (as to make sure that bids are actually meaningful; without this sets with constant minimal base fees ignoring any surge pricng could be preferred) unchanged,
- size in bytes of the XDR encoded
GeneralizedTransactionSetin decreasing order (as to reduce IO resource utilization) new, - hash as a tie-breaker unchanged
Not technically part of the protocol but described here for completeness.
Changes done at the transaction queue and flooding level should align as much as possible with what happens during Candidate Value Generation as to limit the number of transactions that could get delayed or dropped by nomination later on:
- limit the number of transactions in memory as to also take advantage of any potential additional limit on certain types of operations.
- flood higher fee transactions first from the accumulated set.
The update in LedgerCloseMeta will happen together with the switch to the new protocol. This way we don't need to maintain backwards compatibility with legacy TransactionSet in LedgerCloseMetaV1.
The proposal tries to limit to a minimum the number of things actually enforced at the protocol layer, leaving the door open to more flexibility at the node level.
In turn, this flexibility should allow for faster iteration without having to take a dependency on network wide protocol changes.
There is no enforcement at the protocol layer on which of fee regimes (discounted vs direct fee) is picked for a given transaction.
This changes the contract from a client point of view only slightly: the contract between the user and the network is still that the network should try to reduce fees when it can.
The difference is that with this CAP, the user cannot rely on the previous requirement that for "surge pricing" to be active, the ledger had to be at capacity (as per CAP-0005, the fee bid for the entire transaction set was derived from the cheapest transaction included in a full ledger), which limited the risk of paying extremely large fee bids greatly. As a consequence, with this CAP, a single transaction can be isolated by a validator and be forced to pay for its fee bid.
With the introduction of "fee bump", the need to specify fee bids much higher than recent ledgers was removed even for pre-signed transactions.
As soon as this CAP becomes active, validators will produce TransactionSetV1 in SCP.
As this CAP does not change transaction semantics, impact on the ecosystem should be minimal.
Systems that try to compute transaction fees that are close to market rate will have to be adjusted (by possibly interacting more with a local stellar-core instance) as "ledger capacity" would only be losely related to "local surge pricing".
As users are potentially exposed to higher fees, their bidding strategy can be updated to bid what they're comfortable paying at the time not counting on any discount, and gradually increase their bid if their transaction is rejected based on urgency.
The exact strategy for picking the starting bid and increasing transaction bid is outside the scope of this document. A possible approach for picking a good starting bid can be to use the fee stats endpoint, adjust it if rejected by core's tx endpoint (that rejects transactions based on fee bid and its local transaction queue state), and after that multiply its fee bid by 10 or 100 after each timeout.
As transaction sets are transmitted over the network, the overlay network will have to be updated to support the new format.
While this CAP doesn't define the candidate transaction set generation strategy, the initial approach would be to just continue using surge pricing approach described in CAP-0005. However, using it requires slightly changing the algorithm: instead of rounding up during the base fee computation we need to round it down. The reason for doing that is to satisfy the baseFee validation requirement of TXSET_COMP_TXS_MAYBE_DISCOUNTED_FEE component. With rounding up it's possible to have a valid transaction that doesn't satisfy that requirement. The impact of this change should be minimal.
This change will require a small increase in CPU and memory utilization which should easily be recovered by the expected decrease in failed transactions propagating on the network during spikes.
The changes on the security front are minimal as transaction semantics are not changed.
The biggest change comes from validators having more control over fee policy.
This should not be a problem in practice:
- transactions will never be charged more than their maximum bid, and people tend to put small multipliers on top of market rate (fees remain low).
- as validators do not receive fees from transactions processing, there is little incentive for a validator to do this.
- if certain validators adopt unfair fee policies
- they will accrue negative reputation on the network. All activity from validators is recorded and archived, also thanks to CAP-0034, the validator that introduced the GeneralizedTransactionSet to the network is recorded.
- thanks to SCP may cause other network participants to adjust their quorum configurations which could result from those validators to lose trust from the network.
- standards around fee policies can be established outside of the protocol on expectations around well behaved validators to help with auditing.
The TransactionPhase union is an extension point to make it easy to add more "phases" to apply transactions.
As of this CAP, there is only one such phase: the existing transaction subsystem, and we expect new ones to be introduced over time, such as "Speedex transactions" or "smart contract transactions".
This CAP also leaves the door open to different types of components and phases.
Here are a few examples:
- fee groups can be used to prioritize based on dimensions other than the order book as to rebalance use cases, for example based on the expected number of changes to the ledger.
- phases could be used to alter the "apply order" policy: phases could be applied in the order they appear, or allow for parallel execution.
- components could be added to add random numbers/seeds/parameters to update certain ledger entries (like oracles)
- components could be added to provide information related to network partition/shard (nominators could flood differently based on that)
TBD
TBD