Skip to content
Permalink
master
Switch branches/tags
Go to file
 
 
Cannot retrieve contributors at this time

Preamble

CAP: 0021
Title: Generalized transaction preconditions
Author: David Mazières
Status: Draft
Created: 2019-05-24
Updated: 2021-03-04
Discussion: https://groups.google.com/forum/#!topic/stellar-dev/NtCwqWwAxRA
Protocol version: TBD

Simple Summary

This proposal generalizes the timeBounds field in Transaction to support other conditions, including conditions that relax sequence number checking and provide relative timelocks.

Motivation

Sequence numbers are tricky for anything other than simple payments. For instance, pre-authorized transactions can only execute when the source account has a specific sequence number. Worse yet, sequence numbers make it difficult for protocols such as payment channels to guarantee that one participant can execute a transaction signed by all participants. In general, an N-party protocol requires N auxiliary accounts, one for each participant; each logical transaction pre-signed by all N participants must actually be implemented as N pre-signed transactions using each auxiliary account at a source, so that one participant can still submit a pre-signed transaction even if another participant has changed the sequence number on a different auxiliary account. This is further complicated by the need to maintain a reserve balance on each auxiliary account.

Goals Alignment

This proposal advances network scalability by facilitating off-chain payment channels. It advances security and simplicity and interoperability with other networks by enabling relative timelocks. Finally, the proposal makes it easier for developers to create highly usable products by enabling time-delayed key recovery.

Abstract

This proposal extends AccountEntry to keep track of the time and ledger number at which the account's sequence number was last changed. It also replaces the timeBounds field of Transaction with a union that allows more general transaction preconditions. One of these preconditions requires that the sequence number of sourceAccount have been modified at least some period of time in the past, effectively providing a relative timelock. Another precondition optionally weakens sequence number checking so as to allow a transaction to execute when the sourceAccount is within some range.

Specification

AccountEntry's ext field is extended to keep track of seqLedger and seqTime--the ledger number and time at which the sequence number was set to its present value. These values are updated for the sourceAccount of every executed transaction, and also for the sourceAccount of every successfully executed BumpSequenceOp operation (regardless of whether the BumpSequenceOp actually increased the sequence number).

Note that unlike the v1 and v2 extensions, we do not add an extra union at the end, because further changes can be accomplished by re-versioning ext. To minimize source-code changes required in the face of such future extensions, the version 3 arm is called cur, and can be renamed to v3 when version 4 is added. At that point a single function can be used to translate v3 to the new cur, rather than smearing the updated logic throughout the code.

[Note: This point about extension structure is orthogonal to the goals of this CAP, which can just as easily dangle AccountEntryExtensionV3 off the end of AccountEntryExtensionV2 if the protocol working group so decides.]

const ACCTENTRY_EXT_CUR_V = 3;

struct AccountEntryExtensionV3
{
    Liabilities liabilities;

    uint32 numSponsored;
    uint32 numSponsoring;
    SponsorshipDescriptor signerSponsoringIDs<MAX_SIGNERS>;

    // Ledger number at which `seqNum` took on its present value.
    uint32 seqLedger;

    // Time at which `seqNum` took on its present value.
    TimePoint seqTime;
};

struct AccountEntry
{
    AccountID accountID;      // master public key for this account
    int64 balance;            // in stroops
    SequenceNumber seqNum;    // last sequence number used for this account
    uint32 numSubEntries;     // number of sub-entries this account has
                              // drives the reserve
    AccountID* inflationDest; // Account to vote for during inflation
    uint32 flags;             // see AccountFlags

    string32 homeDomain; // can be used for reverse federation and memo lookup

    // fields used for signatures
    // thresholds stores unsigned bytes: [weight of master|low|medium|high]
    Thresholds thresholds;

    Signer signers<20>; // possible signers for this account

    // reserved for future use
    union switch (int v)
    {
    case 0:
        void;
    case 1:
        AccountEntryExtensionV1 v1;
    case 3:
        AccountEntryExtensionV3 cur;
    }
    ext;
};

Preconditions are represented by a new Preconditions union with discriminant type. Values PRECOND_NONE and PRECOND_TIME are binary compatible with the current timeBounds field (which is of type TimeBounds*). Value PRECOND_GENERAL is the new type of precondition. Note that minSeqNum, if non-NULL, relaxes the range of sequence numbers at which a transaction can be executed. However, after executing a transaction, sourceAccount's sequence number is always set to the transaction's seqNum--like an implicit BUMP_SEQUENCE operation. This guarantees transactions cannot be replayed, even when the previous account seqNum is well below the transaction's seqNum. The final element of Preconditions is an array of extra signers required for the transaction. This can be used with SIGNER_KEY_TYPE_HASH_X to sign a transaction that can only be executed in exchange for disclosing a hash preimage.

typedef int64 TimePoint;
typedef int64 Duration;

struct LedgerBounds {
    uint32 minLedger;
    uint32 maxLedger;
};

struct GeneralPreconditions {
    TimeBounds *timeBounds;

    // Transaciton only valid for ledger numbers n such that
    // minLedger <= n < maxLedger
    LedgerBounds *ledgerBounds;

    // If NULL, only valid when sourceAccount's sequence number
    // is seqNum - 1.  Otherwise, valid when sourceAccount's
    // sequence number n satisfies minSeqNum <= n < tx.seqNum.
    // Note that after execution the account's sequence number
    // is always raised to tx.seqNum, and a transaction is not
    // valid if tx.seqNum is too high to ensure replay protection.
    SequenceNumber *minSeqNum;

    // For the transaction to be valid, the current ledger time must
    // be at least minSeqAge greater than sourceAccount's seqTime.
    Duration minSeqAge;

    // For the transaction to be valid, the current ledger number
    // must be at least minSeqLedgerGap greater than sourceAccount's
    // seqLedger.
    uint32 minSeqLedgerGap;

    // For the transaction to be valid, there must be a signature
    // corresponding to every Signer in this array, even if the
    // signature is not otherwise required by the sourceAccount or
    // operations.
    SignerKey extraSigners<1>;
};

enum PreconditionType {
    PRECOND_NONE = 0,
    PRECOND_TIME = 1,
    PRECOND_GENERAL = 2,
};

union Preconditions switch (PreconditionType type) {
    case PRECOND_NONE:
        void;
    case PRECOND_TIME:
        TimeBounds timeBounds;
    case PRECOND_GENERAL:
        GeneralPreconditions general;
};

This proposal changes TimePoint to be signed rather than unsigned, and adds a signed Duration type. These types should also be adopted by ClaimPredicate. There is little need for time points more than 2^{63} seconds in the future, but many databases and languages do not store unsigned 64-bit values conveniently. Thus, it is better to use signed values.

[Note: An alternate approach would be to provide an array of preconditions, so as to make it easier to add new preconditions. However, there is already extensibility through the outer Preconditions union, which could update the Preconditions structure, change PRECOND_GENERAL to 3, and add a PRECOND_GENERAL_V2 arm for backwards compatibility.]

We then make use of the new Preconditions type by replacing timeBounds in the Transaction structure as follows:

struct Transaction
{
    // account used to run the transaction
    MuxedAccount sourceAccount;

    // the fee the sourceAccount will pay
    uint32 fee;

    // sequence number to consume in the account
    SequenceNumber seqNum;

    // validity conditions
    Preconditions cond;

    ...
};

A transaction whose preconditions are not satisfied is invalid and must not execute (even to fail), meaning it cannot change the sourceAccount sequence number or charge a fee. To insure that invalid transactions do not propagate, a transaction with a non-zero minSeqLedgerGap or minSeqAge may not execute in the same ledger as a transaction with a lower seqNum on the same sourceAccount.

Transaction forwarding and ordering

A transaction submitted to the network is valid only if it is part of a valid series of pending transactions on the same sourceAccount that can all be valid in the same block. For example, if a source account has seqNum 10, then a submitted transaction with seqNum 12 and no preconditions is valid (and should be forwarded) only if there is also a pending valid transaction with sequence number 11. The minSeqNum field in this proposal relaxes validity to allow a valid series of transactions on the same sourceAccount with discontinuous seqNum fields. Regardless of these gaps, all transactions on the same sourceAccount in the same block must be executed in order of increasing seqNum. Hence, the presence of the minSeqNum field may make transactions valid that would not otherwise be valid, but cannot invalidate otherwise valid transactions, since lower seqNum fields always execute first before higher ones that would invalidate them.

A transaction with a non-zero minSeqAge or minSeqLedgerGap must be treated as invalid and not forwarded--as if its minTime has not yet arrived--if either A) the appropriate condition (minSeqAge or minSeqLedgerGap) does not yet hold, or B) there are pending valid transactions with lower sequence numbers on the same sourceAccount. However, a nominated block is valid so long as its transactions can be executed. This means a validator can vote for a block containing transactions the validator would not otherwise have forwarded. For example, consider the following two transactions on the same sourceAccount which currently has seqNum 10:

  • T1 has seqNum 11 and no preconditions.
  • T2 has seqNum 12, minSeqNum 10, and minSeqLedgerGap 1.

Any validator that receives both of these transactions will only forward T1. However, if a validator sees a nomination vote for a block that contains T2 but not T1, the validator will nonetheless vote for the block. The logic is identical to a situation in which T1 and T2 have the same sequence number but T1 has twice the fee--validators seeing both should preferentially forward T1, but also accept T2 in nominated blocks.

All transactions are validated, sequence numbers increased, and fees deducted before any operations are executed. One consequence is that BUMP_SEQUENCE operations, though they update an account's seqTime and seqLedger, do not affect the validity of other transactions in the same block.

XDR diff

diff --git a/src/xdr/Stellar-ledger-entries.x b/src/xdr/Stellar-ledger-entries.x
index 26ff33d43..d96f55ea6 100644
--- a/src/xdr/Stellar-ledger-entries.x
+++ b/src/xdr/Stellar-ledger-entries.x
@@ -12,7 +12,8 @@ typedef opaque Thresholds[4];
 typedef string string32<32>;
 typedef string string64<64>;
 typedef int64 SequenceNumber;
-typedef uint64 TimePoint;
+typedef int64 TimePoint;
+typedef int64 Duration;
 typedef opaque DataValue<64>;
 
 // 1-4 alphanumeric characters right-padded with 0 bytes
@@ -126,6 +127,24 @@ const MAX_SIGNERS = 20;
 
 typedef AccountID* SponsorshipDescriptor;
 
+
+const ACCTENTRY_EXT_CUR_V = 3;
+
+struct AccountEntryExtensionV3
+{
+    Liabilities liabilities;
+
+    uint32 numSponsored;
+    uint32 numSponsoring;
+    SponsorshipDescriptor signerSponsoringIDs<MAX_SIGNERS>;
+
+    // Ledger number at which `seqNum` took on its present value.
+    uint32 seqLedger;
+
+    // Time at which `seqNum` took on its present value.
+    TimePoint seqTime;
+};
+
 struct AccountEntryExtensionV2
 {
     uint32 numSponsored;
@@ -187,6 +206,8 @@ struct AccountEntry
         void;
     case 1:
         AccountEntryExtensionV1 v1;
+    case 3:
+        AccountEntryExtensionV3 cur;
     }
     ext;
 };
@@ -325,10 +346,10 @@ case CLAIM_PREDICATE_OR:
 case CLAIM_PREDICATE_NOT:
     ClaimPredicate* notPredicate;
 case CLAIM_PREDICATE_BEFORE_ABSOLUTE_TIME:
-    int64 absBefore; // Predicate will be true if closeTime < absBefore
+    TimePoint absBefore; // Predicate will be true if closeTime < absBefore
 case CLAIM_PREDICATE_BEFORE_RELATIVE_TIME:
-    int64 relBefore; // Seconds since closeTime of the ledger in which the
-                     // ClaimableBalanceEntry was created
+    Duration relBefore; // Seconds since closeTime of the ledger in which the
+                        // ClaimableBalanceEntry was created
 };
 
 enum ClaimantType
diff --git a/src/xdr/Stellar-transaction.x b/src/xdr/Stellar-transaction.x
index b2a4f420b..ce933d909 100644
--- a/src/xdr/Stellar-transaction.x
+++ b/src/xdr/Stellar-transaction.x
@@ -507,6 +507,58 @@ struct TimeBounds
     TimePoint maxTime; // 0 here means no maxTime
 };
 
+struct LedgerBounds
+{
+    uint32 minLedger;
+    uint32 maxLedger;
+};
+
+struct GeneralPreconditions {
+    TimeBounds *timeBounds;
+
+    // Transaciton only valid for ledger numbers n such that
+    // minLedger <= n < maxLedger
+    LedgerBounds *ledgerBounds;
+
+    // If NULL, only valid when sourceAccount's sequence number
+    // is seqNum - 1.  Otherwise, valid when sourceAccount's
+    // sequence number n satisfies minSeqNum <= n < tx.seqNum.
+    // Note that after execution the account's sequence number
+    // is always raised to tx.seqNum, and a transaction is not
+    // valid if tx.seqNum is too high to ensure replay protection.
+    SequenceNumber *minSeqNum;
+
+    // For the transaction to be valid, the current ledger time must
+    // be at least minSeqAge greater than sourceAccount's seqTime.
+    Duration minSeqAge;
+
+    // For the transaction to be valid, the current ledger number
+    // must be at least minSeqLedgerGap greater than sourceAccount's
+    // seqLedger.
+    uint32 minSeqLedgerGap;
+
+    // For the transaction to be valid, there must be a signature
+    // corresponding to every Signer in this array, even if the
+    // signature is not otherwise required by the sourceAccount or
+    // operations.
+    SignerKey extraSigners<1>;
+};
+
+enum PreconditionType {
+    PRECOND_NONE = 0,
+    PRECOND_TIME = 1,
+    PRECOND_GENERAL = 2,
+};
+
+union Preconditions switch (PreconditionType type) {
+    case PRECOND_NONE:
+        void;
+    case PRECOND_TIME:
+        TimeBounds timeBounds;
+    case PRECOND_GENERAL:
+        GeneralPreconditions general;
+};
+
 // maximum number of operations per transaction
 const MAX_OPS_PER_TX = 100;
 
@@ -558,8 +610,8 @@ struct Transaction
     // sequence number to consume in the account
     SequenceNumber seqNum;
 
-    // validity range (inclusive) for the last ledger close time
-    TimeBounds* timeBounds;
+    // validity conditions
+    Preconditions cond;
 
     Memo memo;
 

Design Rationale

Relative timelocks are a known mechanism for simplifying payment channels, implemented by Bitcoin and used in lightning payment channels. Stellar's lack of UTXOs combined with transaction sequence numbers make payment channels harder to implement. This proposal rectifies the problem in a way that is not too hard to implement in stellar-core and provides a good degree of backwards compatibility.

Fundamentally, a payment channel requires a way to enforce a time separation between declaring that one wants to execute a pre-signed transaction T and actually executing T. Furthermore, between the declaration and execution, other parties need a chance to object and invalidate T if there is a later T' superseding T. The relative timelock provides this separation, while the relaxing of sequence numbers makes it easy to object by pre-signing a transaction invalidating T that can be submitted at a variety of sequence numbers. Without such a mechanism, multiple auxiliary accounts are required.

An earlier version of the proposal did not contain the minSeqLedgerGap field. However, members of the payment channel working group were concerned that the network could, in a worst-case scenario, experience downtime right after someone incorrectly closes a payment channel, precluding the other party from correcting the problem. minSeqLedgerGap guarantees that there will be an opportunity to correct the problem when the network comes back up, because the pre-signed transaction with a minSeqLedgerGap will still not be immediately executable.

It's worth asking whether we need minSeqAge if we have minSeqLedgerGap. One reason to keep it is that, under heavy load, the network could start processing ledgers faster than once every 5 seconds. This might happen after periods of downtime.

One possible efficiency problem is that transactions with a minSeqAge or minSeqLedgerGap cannot be pipelined behind other transactions on the same sourceAccount. Though this might seem to reduce efficiency, in fact such time-delayed transactions are intended to be delayed for some "disclosure period" during which the account remains idle. Typically such time-delayed transactions are intended to correct an abnormal situation (e.g., one end of a payment channel failing, or an account owner losing the key) and so don't actually get submitted in the common case.

Two-way payment channel

The proposed mechanism can be used to implement a payment channel between two parties, an initiator I and a responder R. The protocol assumes some synchrony period, S, such that both parties are guaranteed to be able to observe the blockchain state and submit transactions within any period of length S.

The payment channel consists of a 2-of-2 multisig escrow account E, initially created and configure by I, and a series of pairs of declaration and closing transactions on E signed by both parties. The two parties maintain the following two variables during the lifetime of the channel:

  • s - the starting sequence number, is initialized to one greater than the sequence number of the escrow account E after E has been created and configured. It is increased only when withdrawing from or topping up the escrow account E.

  • i - the iteration number of the payment channel, is initialized to (s/2)+1. It is incremented with every off-chain update of the payment channel state.

To update the payment channel state, the parties 1) increment i, 2) sign and exchange a closing transaction C_i, and finally 3) sign and exchange a declaration transaction D_i. The transactions are constructed as follows:

  • D_i, the declaration transaction, declares an intent to execute the corresponding closing transaction C_i. D_i has source account E, sequence number 2i, and minSeqNum set to s. Hence, D_i can execute at any time, so long as E's sequence number n satisfies s <= n < 2i. D_i always leaves E's sequence number at 2i after executing. Because C_i has source account E and sequence number 2i+1, D_i leaves E in a state where C_i can execute. Note that D_i does not require any operations, but since Stellar disallows empty transactions, it contains a BUMP_SEQUENCE operation as a no-op.

  • C_i, the closing transaction, disburses funds to R and changes the signing weights on E such that I unilaterally controls E. C_i has source account E, sequence number 2i+1, and a minSeqAge of S (the synchrony period). The minSeqAge prevents a misbehaving party from executing C_i when the channel state has already progressed to a later iteration number, as the other party can always invalidate C_i by submitting D_i' for some i' > i. C_i contains one or more CREATE_CLAIMABLE_BALANCE operations disbursing funds to R, plus a SET_OPTIONS operation adjusting signing weights to give I full control of E.

For R to top-up or withdraw excess funds from the escrow account E, the participants skip a generation. They set s = 2(i+1), and i = i+2. They then exchange C_i and D_i (which unlike the update case, can be exchanged in a single phase of communication because D_i is not yet executable while E's sequence number is below the new s). Finally, they create a top-up transaction that atomically adjusts E's balance and uses BUMP_SEQUENCE to increase E's sequence number to s.

To close the channel cooperatively, the parties re-sign C_i with a minSeqNum of s and a minSeqAge of 0, then submit this transaction.

One-way payment channel

A one-way payment channel enables an initiator I to make repeated payments to a recipient R. Unlike the two-way payment channel, I can unilaterally set up the payment channel without R's cooperation. Moreover, R can unilaterally withdraw funds from the payment channel at any point with no close delay.

The channel consists of a an escrow account E, initially created by I. Let s be E's sequence number after it has been created and configured. Define the following transactions with source account E:

  • D, the disclosure transaction, has sequence number s+1 and a vacuous BUMP_SEQUENCE operation.

  • C_i, version i of the closing transaction, has sequence number s+2. It disburses funds to R through one or more closing transactions and uses SET_OPTIONS to increase I's signing weight to 2. Each C_i disburses more funds to R than C_{i-1}. Only one C_i can execute since they all have the same sequence number.

  • F, the fault-recovery transaction, allows I to recover E in case R fails. It has sequence number s+2, a minSeqAge of S (some synchrony period), and gives I signing weight 2 on the account.

After adding appropriate trustlines and funding the escrow account E, I issues a transaction configuring E to have signing threshold 2 (for low, medium, and high) and to have the following signers all with weight 1: I, R, D, and F (the latter two as SIGNER_KEY_TYPE_PRE_AUTH_TX).

To submit series of payments, I sends R successive C_i transactions each of which reflects the cumulative sum of all previous payments. R accepts these so long as E has a sufficient balance. To close the channel, R submits D and C_i. If R fails, I can close the channel by submitting D, waiting S time, and then submitting F.

Hash Time Locked Contract (HTLC)

HTLCs are a key building block for many blockchain protocols such as cross-chain atomic swaps and payment channels. An HTLC is a transaction T characterized by two values: a hash h and an expiration time t. Before the expiration time, anyone who knows the hash preimage of h can execute T in exchange for disclosing that preimage. Typically disclosing the preimage unlocks a different transaction on the same or a different blockchain.

To make a transaction into an HTLC, the following preconditions should be set:

  • timeBounds->maxTime should be set to the expiration time t.

  • extraSigners[0] should be set to a SIGNER_KEY_TYPE_HASH_X with the hash value h.

Note that the maximum size of a hash pre-image on Stellar is 64 bytes. On Bitcoin, a hash preimage could potentially be up to 520 bytes. Hence, when pairing Stellar HTLCs with transactions on other blockchains for cross-chain operation, care must be taken to ensure that the other blockchain does not accept preimages larger than 64 bytes. Otherwise, a larger preimage disclosed on another blockchain would fail to unlock an HTLC on Stellar.

Key recovery

The owner of account A may wish for a friend with key K to gain access to A in the event that the owner loses her keys, but not otherwise. This scenario can be accommodated with pre-authorized transactions as follows.

Let s be a sequence number much higher than any that will be used in the future on A (e.g., A's current sequence number plus 2^{32}). The owner constructs the following 2 transactions:

  • The recovery transaction T_R has source account A, sequence number s+1, and minSeqAge one week. It contains a SET_OPTIONS operation giving K signing weight on A.

  • The declaration transaction T_D has source account A, sequence number s, and minSeqNum 0. It doesn't need to contain any operations, but since Stellar requires at least one operation per transaction, it contains a BUMP_SEQUENCE as a no-op.

The owner of A signs T_R and T_D, and gives them to the friend for safe keeping. If the owner loses her keys, the friend submits T_D, then a week later submits T_R, and finally uses key K to help the user recover her funds.

If T_D and K are ever compromised and an attacker unexpectedly submits T_D, then the user simply submits any transaction on A to consume sequence number s+1 and invalidate T_R.

Parallel transaction submission

A farm of 100 servers is constantly submitting transactions on the same source account, and wishes to coordinate use of sequence numbers. This can be achieved by having server number N always submit transactions with sequence numbers congruent to N modulo 100. Sending the transaction at s with minSeqNum s-99 ensures that if any of the servers do not submit transactions, the gap will not prevent other transactions from executing.

Backwards Incompatibilities

The binary XDR of all previously valid transactions will also unmarshal to a valid transaction under the current proposal. Obviously legacy software will not be able to parse transactions with the new preconditions, however.

Security Concerns

The security concerns stem primarily from new types of transaction making use of the new features. As such, the new preconditions, particularly minSeqNum, should make pre-signed transactions less brittle and simplify protocols. Nonetheless, there is still a lot of room for error in protocols.

The fact that BUMP_SEQUENCE operations are executed after all transactions have been validated leads to a counterintuitive situation in which two operations can execute in the same block but not in different blocks. This was already the case before the current proposal, but the minSeqAge and minSeqLedgerGap fields create more such situations. Fortunately, it appears that in most useful protocols time-delayed "closing" transactions use a NULL minSeqNum, while transactions with non-NULL minSeqNum are "disclosure" transactions intended to be valid at any time.

Test Cases

None yet.

Implementation

None yet.