Proposal: Preauthorized transactions with flexible sequence numbers

[robdenison]

This proposal would change how preauthorized transactions are checked to allow preauthorization of transactions without committing to a specific sequence number.

Under the current behavior, a signer of type preAuthTx is checked by comparing the hash of the unaltered transaction to the hash specified in that signer. This proposal would change that behavior so that the signer can also be satisfied if the hash of the transaction with its sequence number changed to 0 (or some other magic number) matches the hash specified in the signer.

All other transaction behavior would remain the same. The transaction ID would still include the sequence number (so all transactions would still have unique sequence numbers). The sequence number of the transaction would still be incremented by one if the transaction succeeds. The preauthorized transaction would be removed from the account when it is used, preventing it from being replayed.

EDIT: We could apply this behavior to signed transactions as well as preauthorized transactions, which would be particularly useful for Starlight. These transactions should only be used in protocols that ensure through other means (such as by having the transaction change the signers on the account) that they cannot be replayed.

Rationale

It is sometimes useful to preauthorize a transaction without knowing what its sequence number will be. It is particularly useful to be able to preauthorize multiple transactions without knowing ahead of time the order in which they will be published to the chain.

For example, this change would significantly reduce the overhead and complexity of hashed timelocked contracts (HTLCs) on payment channels in Stellar Lightning. HTLCs are agreements that can be concluded in two ways—by revealing a hash preimage, which results in some steps (such as a payment) being "fulfilled," or by satisfying a timeout, which results in those steps being "cancelled." They can be implemented in Stellar (with some other unrelated protocol changes). However, it is currently difficult to set up a payment chanel with multiple HTLCs (as is required by Lightning), because those HTLCs need to be fulfillable or cancelable in any order. The most efficient known way to implement them in the current protocol would involve preauthorizing a separate aggregate key for each HTLC and pre-signing N fulfill and N cancel transactions for each HTLC, with O(N^2) off-chain overhead. This method also appears to have other limitations (for example, each HTLC fulfillment would likely be limited to a single operation).

Alternatives

An alternative would be to not increment the sequence number when such a condition is satisfied. This would be a more radical change to the protocol and implementation (even though it would still not allow replay) and would violate some invariants.

A more radical design would be to allow transactions with sequence numbers of 0 to be valid regardless of the current sequence number of the account. This would be strictly more powerful than this proposal, but is potentially much more dangerous (since a signed transaction with a 0 sequence number would be replayable any number of times, unless it changed the state in some other way that prevented it from being replayed). However, such a design could be very useful. One potential application is to be able to pre-sign transactions from an account that has not yet been created (and whose starting sequence number is therefore unknown). This would allow you to pre-sign a series of transactions that create a new account and endow it with arbitrary signers, which is currently impossible (and which could be used as an alternative way to implement HTLCs or a host of other smart contract designs).

A final option would be to add flexible preauthorized transactions as a new signer type, or as a flag that can be set on the preAuthTx signer type. This would be a more extensive change to the implementation and the product's surface area, but might avoid even a small risk of upending user expectations (see Backwards Compatibility.

Implementation

The signature checker could be initialized with an additional argument—the hash of the transaction with its sequence number changed to 0. The preAuthTx signer check would check for equality with either the hash of the transaction or this alternative hash.

The additional overhead would be the computation of this hash for each transaction that is checked, and an extra 32-byte comparison for each preAuthTx signer that is checked. (This could be optimized by only computing this hash lazily, when a preauthorized transaction signer check fails.)

Backwards Compatibility

This will make previously invalid (unauthorized) transactions valid, making it a breaking consensus change.

This probably will not cause any breaking changes in application or user code. This change does not make any previously valid transactions invalid. Additionally, as far as I know, there is currently no reason to preauthorize transactions with a sequence number of 0 (and no way to satisfy such preauthorized transactions), so nobody should have been relying on this behavior.

However, it is possible that some application code might rely on some situational invariant that is broken by this change. For example, this breaks the invariant that an account whose only signer is a preauthorized transaction can only be updated by a transaction whose hash matches that one precisely. If any application code relies on watching for a particular user-specified preauthorized transaction hash, this change might disrupt it. As far as I can tell, there is no reason for an application to watch for updates to an account in this way (rather than watching the account directly).

Forwards Compatibility

It is possible that future proposals may want to use a 0 sequence number for some other, incompatible feature.

One possible feature would be to allow transactions themselves to have a 0 sequence number (as described above in Alternatives). This would be its own breaking consensus change, but would be completely compatible (from the user and application perspective) with this proposal. A user on an account with a preauthorized 0-sequence-number transaction would simply have the additional option of publishing the 0-sequence-number transaction itself.

If an incompatible use of a 0 sequence number were developed (such as one where the transaction did not increment the account's sequence number), it could always use some other magic number, such as -1.

[JeremyRubin]

I'm in favor of this feature.

I am worried though, that in your description, you are open to malleability.

I think it should be designed such that it is immediately obvious that the transaction can have any sequence number, rather than to have the validator set it to zero. Therefore I favor broadcasting the transaction with a SequenceNumber of 0.

Actually, I think it might be better to use -1. typedef int64 SequenceNumber;, so we may as well make use of -1 to indicate a replayable txn. We could even use -n to indicate playable up to sequence n.

I also am curious if it would be better to, despite the overhead, to not have the arbitrary hash removed after the transaction by default. Perhaps it would be preferable to just have such transactions specify a setoptions (and add a new feature to setoptions to allow self-reference if it is a presigned transaction).

[robdenison]

Good point about malleability.

So you're in favor of allowing any transaction to have a sequence number of 0 (or -1) to indicate that it's replayable, rather than making this feature specific to preauthorized transactions? I'm ok with that (and it enables some powerful additional possibilities, as I describe in Alternatives above). But it seems somewhat dangerous. To be safe, any such transaction would have to manage its own replayability (perhaps by removing a signer, or by depleting a balance). It's true that this is an opt-in feature, but is it possible that some software out there might sign transactions without checking anything about the sequence number? If so, this could allow an attacker to drain such an account by tricking its controller into signing a replayable transaction.

Love the idea of -n indicating "replayable up to sequence number n." But in that case, -1 would mean replayable until sequence number 1. Infinitely replayable should be MIN_INT64, yeah?

When would we ever not want the preauthorized transaction hash removed from the account? (I guess maybe if you wanted a preauthorized transaction to debit some account and be replayable until that account was empty, so you could use the account balance to control how many times the transaction was replayable.) If you ever needed to do that, you could just pre-sign rather than preauthorize the transaction (and preauthorize a transaction adding the public key as a signer, if you must). Besides, removal is consistent with how preauthorized transactions already work, which is too important and established to break (and which we wouldn't want to break for specific-sequence-number preauthorized transactions, because it would always be pointless to leave that hash on the account).

[JeremyRubin]

If/when we add relative timeouts, an infinitely replayable transaction could be quite useful.

[robdenison]

Like I said, you could always do that with a presigned transaction rather than a preauthorized one.

[JeremyRubin]

The thing that is nice about preauthorized txns v.s. preauthorized is that you can add preauthorized txns to an account from another transaction, but I don't quite see how presigned would achieve the same thing without introducing the ability to approve an arbitrary transaction (e.g., if you presign and then add one of the keys).

[MonsieurNicolas]

Wondering if this conversation would benefit from looking at what it would take to fix the issues with the current way of solving the "I want to presign N transactions that can be applied in any order" problem.

The current semantics to achieve this are to create N temporary accounts and use them as source account.

Basically:

• create N temporary accounts
• assign each transaction to one of those temporary account
• transaction may merge the temporary account, but doesn't have to

I think issues are:

• all accounts must be created in advance in order to generate the transactions (sequence number would not be known otherwise)
• accounts must be "cleaned up" after use
• this is wasteful (creates a lot of temp objects in the ledger, burning fees and locking up reserve)

Which issue is the sticky one in this context?

I think it's important to look at this with a critical eye as so far we've been able to avoid having replayable transactions by instead defaulting to behaviors equivalent to "being stuck" (temporarily or permanently).

Another useful lens is also that enabling replayable transactions have a bunch of consequences to the ecosystem as many systems identify transactions by hash which would not be possible anymore.

[robdenison]

Thanks, Nicolas. The primary sticking point is issue 1—in the context of a payment channel, you can't create the extra accounts ahead of time. If there were a way to predict the sequence number of a new account deterministically, that might solve the problem. (Indeed, it would give us another way to do HTLCs that might eliminate the need for #89 as well, although the 1-lumen account balance minimum would certainly make the solution a bit awkward.)

Yes, the replayability is definitely an ecosystem issue, which is why I suggested having the 0 sequence number only be allowed on a preauthorized transaction (so the actual transaction that gets authorized would have the proper, in-order sequence number). This would preserve the invariant that no two transactions would ever have the same hash. But Jeremy pointed out that that could cause its own malleability issues.

[MonsieurNicolas]

Well, it could be conceivable to allocate an upper bound of accounts, but that's not super flexible as there is always the chance that closing the channel would require that pesky extra transaction.

One avenue that may be worth exploring is something I discussed with @JeremyRubin before: allow CreateAccount to inherit the sequence number from its source account (let's call it CreateAccount2 for now), which could make things deterministic.

That potentially creates a bunch of other problems though on the replayability front:

1. A: createAccount2 B1
2. perform a bunch of transactions with B1
3. B1: mergeAccount into X
4. A: createAccount B1
   at this point, the transactions from 2 could be replayed.

We avoid this in the current design by setting the high 32 bits of the sequence number to the ledger number when creating an account.

An equivalent, but not as safe version could be to cause CreateAccount2 to work like this:

• create an account with sequence number N = sourceAccount.SeqNum + buffer
• bump sourceAccount.SeqNum by 2*buffer
  buffer would be something like 2^32, and basically leaves plenty of room for that temporary account to perform transactions .

Now, to break this, I think you would have to either use BumpSeq on the new account to "catchup" with the source account or merge the new account, and recreate it at the right time (depending on how big buffer is).

The first one we could just disallow BumpSeq (with a flag) on an account that was created like this, the second I don't see an obvious solution.

I am not sure those are intractable problems - there might be ways to play with "auto expiring accounts" (there is a need for expiring ledger entries in general) for example.

[robdenison]

Maybe you could prevent replays using the account ID rather than the sequence number.

Suppose you made the account ID of accounts created by createAccount2 not a public key, but rather a hash, say sha256(initialPublicKey, sourceAccountId, sourceAccountSequenceNumber). The initial sequence number of the account could be the same as the parent's initial sequence number. (Or it could just be zero, maybe?) You would be guaranteed that an account with that ID could never be created again, so there'd be no replay problem.

EDIT: Welp, one catch—you would be able to recreate an account with the same ID by using createAccount and using the hash as the initial "public key." But 1) you wouldn't know the corresponding private key, so you could never spend from that account, and 2) that account would have its sequence number generated in the normal way, so as long as those couldn't conflict with createAccount2 sequence numbers (for example, if the latter started at 0), we'd be fine. EDIT 2: Nope, this really does cause a problem, because someone could create the account with old-style createAccount before it is created using createAccount2. We would need to use a different prefix for these accounts.

[jedmccaleb]

I definitely think we need some mechanism to allow you to preauth regardless of the seqnum. I like the idea of just saying that a seqNum of 0 means re-playable.

I'd actually like to think if there is a simple way to be even more general. Maybe instead you can preauth a transaction template where particular fields are variable. This would allow you to do other things also like auth a tx with a variable amount or any tx to a particular account works and other things.

The other way to do this would be to allow the creation txs that take some of their values from the current state of the world. This would allow you to say seqNum= seqNum of source account, and other things like amount = balance of some other account, destination = piece of data on account B, etc

I'll propose something more concrete soon but wanted to share these ideas first.

[JeremyRubin]

@jedmccaleb, I like that!

Can you open a new issue for it so as not to clog discussion here as I think these features should be considered separately?

In my haste to reply, I missed that this is a generalization, by templating the sequence number. Carry on.

[MonsieurNicolas]

Every time I think about parameterized transactions I end up with a solution that is equivalent to utxo in order to avoid double spend as we must guarantee that the transaction without its parameters cannot be spent twice (ie there is something tracking the partial transaction directly or indirectly on the ledger). If this is the direction that we are thinking about going, we may not have to figure out the general solution for parameterized transactions at all in this context and just need to focus on a minimalist utxo model for Stellar.