Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

New operation proposal: Bump Sequence #53

Closed
MonsieurNicolas opened this issue Oct 13, 2017 · 11 comments

Comments

@MonsieurNicolas
Copy link
Contributor

commented Oct 13, 2017

Description

Bump sequence allows to bump forward the sequence number of the source account of the operation.

If the specified bumpTo sequence number is greater than the source account's sequence number,
the account's sequence number is updated with that value, otherwise it's not modified.

Threshold: Low

Note:
This operation only allows bumping the sequence number up to (current_ledger_number<<32) - 1.

Return values

BUMP_SEQUENCE_SUCCESS

The source account's sequence number was successfully updated.

BUMP_SEQUENCE_TOO_FAR

The specified bumpTo parameter is greater than the maximum allowed, see note above.

XDR

struct BumpSequenceOp
{
    SequenceNumber bumpTo;
};

/******* BumpSequence Result ********/

enum BumpSequenceResultCode
{
    // codes considered as "success" for the operation
    BUMP_SEQUENCE_SUCCESS = 0,
    // codes considered as "failure" for the operation
    BUMP_SEQUENCE_TOO_FAR = -1 // operation would bump past the maximum sequence number allowed
};

union BumpSequenceResult switch (BumpSequenceResultCode code)
{
case BUMP_SEQUENCE_SUCCESS:
    void;
default:
    void;
};

Implementation considerations on how transaction sets are applied to ledgers

Some background

Currently a transaction set is processed in two phases:

  1. fees and sequence numbers are collected globally
  2. transactions (and their operations) are applied

The problem with this approach is that with the introduction of an operation like BumpSequenceOp,
we have some inconsistencies in the way transactions are processed:
if a transaction bumps the sequence number of an account used in a later transaction, the second
transaction is expected to fail but with the current implementation, it won't (as sequence number
checks are performed while collecting fees).
One the reasons that BumpSequenceOp is introduced is to invalidate ranges of transactions, and
with the current behavior it would make it difficult to reason about the correctness of sequence
of transactions.

Proposed update

Only process fees first:

  1. fees are collected globally
  2. transactions are applied, before applying individual transactions:
    • sequence numbers are checked for validity
    • if the sequence number was valid, update the account's sequence number

We would not change the logic to construct or validate a transaction set:
a transaction set would still be built with transactions that have consecutive sequence numbers.

The difference is that in the event that a transaction is invalidated by an operation from
a different transaction, it would fail (collecting fees), which allows for transactions that make use of BumpSequenceOp to be able to make clean assumptions for any operations scheduled for after the bump.

Example usage

A typical use for this is to allow invalidating large ranges of transactions that were pre-shared with others when implementing complex multi-party transactions that form workflows.

This example has two such workflows:

  • first one is the main path
  • second one is a dispute path, which itself may involve complex dependencies between transactions

Notation

(sequence number, tx source account)[operation1... operation b]

Transactions prepared

main workflow

(1, A)[...], ... , (99, A)[...]

Some transactions may have the same transaction number, as they are logically equivalent to branches:

  • regular flow
    • (5,A)(payment B->C)
    • (6,A)(payment B->E)
  • abort current workflow and enable jumping to the "dispute workflow"
    • (5,A)(bumpSeq 199)
      • when executed, it will invalidate any transactions numbered 6...199

dispute workflow

(200,A)(...), ..., (250, A)(...)

@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Nov 27, 2017

After playing a bit with the code, it looks like the fee changes are going to require an update to the meta format (used in Horizon for example).
The relevant XDR section would look like this:

struct TransactionMetaV1
{
    LedgerEntryChanges txChanges; // tx level changes
    OperationMeta operations<>; // meta for each operation
};

union TransactionMeta switch (int v)
{
case 0:
    OperationMeta operations<>;
case 1:
    TransactionMetaV1 v1;
};

in a nutshell:

  • right now, the txfeehistory table contains the fee and sequence number update to the account
  • in this new version, the sequence number update is moved to the txChanges field (stored in the txhistory table)

For code that only cares about operations side effects, the code has to be updated to read either tm.operations() or tm.v1().operations (depending on the value of tm.v())

@zulucrypto

This comment has been minimized.

Copy link
Contributor

commented Jan 25, 2018

@MonsieurNicolas The PR for Trezor support is currently under review and I'd like to get this operation in there now so it doesn't need to be added later.

How confident are you that the XDR is final? Will it be operation number 11?

@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Jan 26, 2018

@zulucrypto you like to live dangerously :) yes, likely to be be the one we end up with. I am currently working on the implementation.

@Ratniex

This comment has been minimized.

Copy link

commented Jan 26, 2018

@MonsieurNicolas
I was working at my own proposal similar to this one at my own pace and found out about issue 53 recently. My thoughts on the issue are this:
1.) It should be allowed to bump sequence backwards.
2.) It should be a high threshold operation.

The importance of second point is obvious from the first. If sequence can be bumped backward then transactions can be replayed and anything lower than high threshold should not be allowed to do this.

As stated in the current proposal a typical use case for this is to skip ranges of transactions in complex workflows. In this case ability to replay transactions adds lots of flexibility, namely loops. If we allow to bump sequence only forward then only conditionals are possible. My proposal is to have bump sequence operation in Stellar to be similar to a goto statement in programming.

An example of where this is useful is a mortgage loan. Suppose that Alice has a token t that represents ownership of real estate and Bob has lots of XML that he wants to lend and Alice will repay those XML with interest over N payments. They can set up a custodian account C with the following rules.
1.) Alice sends C her token t
2.) Bob sends Alice XML
3.) C adds txHash type signer transaction pay1
4.) C adds txHash type signer transaction claim1
5.) C adds txHash type signer transaction replay1
6.) C sets master signature weight to 0
Transaction pay{i} is this:
1.) C pays Bob XML (if Alice has not paid C this op will fail)
2.) C adds txHash type signer transaction pay{i+1}
3.) C adds txHash type signer transaction claim{i+1}
4.) C adds txHash type signer transaction replay{i+1}
5.) C removes txHash type signer transaction claim{i}
6.) C removes txHash type signer transaction replay{i}
Transaction claim{i} is this:
*.) this transaction has a lower time bound of t{i} where t{i} is according to payment schedule.
1.) C adds Bob as a high threshold signer. (now Bob can claim token t)
Transaction replay{i} is this:
1.) C bumps sequence number so that pay{i} and claim{i} can be published
note that transaction replay{i} cannot fail.
Transaction pay{N} is this:
1.) C pays Bob XML (if Alice has not paid C this op will fail)
2.) C adds Alice as a high threshold signer. (now Alice can claim token t)

The sequence numbers for these transactions are:
pay{i} has sequence 2i
claim{i} has sequence 2i
replay{i} has sequence 2i + 1

There are other use cases for this functionality for example a crowdfunding campaign that can end early. In general this functionality would allow Stellar developers to reason about Stellar accounts as deterministic finite automaton where sequence number combined with txHash signers are states and transactions are transitions.

I will try to wrap up what I have written so far into a serious counter proposal over the next two days and then post it here.

@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Jan 26, 2018

Thank you for bringing this up!

I do not want to allow jumping back wrt sequence numbers as it would violate one of the main tenets in Stellar: keep our users (this includes the devs) as much as possible from shooting themselves in the foot.

What kind of problems would that create:

  • it breaks too many things in downstream systems. In particular, it removes the invariant that a transaction can only be applied once in history - so it makes it difficult to know if a transaction was applied or not and analyze history
  • it allows observers of the network (not just the parties involved in the smart contract) to reinject transactions into a smart contract, which allows to do all sorts of bad things. For example, DoSing the smart contract (if it has branches, force a branch); or in the case of buggy loops deplete an account (could be fees that would deplete an account from XLMs, could be whatever was being transferred as part of the smart contract).

On the smart contracts front, the idea was always to unroll loops. This operation's purpose is just to allow to skip blocks of transactions.

Now your second point is still very relevant:
I agree with you that high is probably the safest threshold to have for this operation as it removes the possibility of a lower signer to jump into the wrong place in the workflow.

Another thing that I also realized is that we should also probably make it fail instead of no-op:

  • in the context of bumpseq being the only operation in a transaction it doesn't matter
  • if bumpseq is one of several operations in a transaction. it allows to have safe assumptions on the workflow.

For this last point, I am going to illustrate it with an example:

W is the account used for tracking the workflow's state
W { seqnum: 1000 , signers: A+B}
A & B are just worker accounts that participate in the workflow.

tx1:
{
   sourceAccount: A
   seqNum: 19000
   op1: { sourceAccount: W, bumpSeq: { to: 2000 } }
   op2: { payment: { dest: B, amount: 1K } }
}

tx2:
{
   sourceAccount: B
   seqNum: 25000
   op1: { sourceAccount: W, bumpSeq: { to: 2000 } }
   op2: { payment: { dest: A, amount: 1K } }
}

With the "fail" semantics, only one of those 2 tx will succeed even though they originate from a different account (A and B respectively).

I can see this being used by having multiple bumpSeq operations in certain transactions that want to combine several state transitions.

@Ratniex

This comment has been minimized.

Copy link

commented Jan 27, 2018

When you try to keep users from shooting themselves in the foot sometimes the opposite effect can occur, after all it is a basic principle of software engineering that user will find a way to shoot himself. If a developer needs to have some functionality x at all costs and the obvious way to implement x is not possible because it uses potentially dangerous operations then the developer will implement a complicated pirouette that does x in a strange way and in the end will be more error prone. From a philosophical standpoint I firmly believe users should have the right to shoot themselves, however I understand this is an issue of opinion and should be dropped. I have a personal insult because I performed the pirouette.

Regarding history recording I understand and agree. Changing creates to upserts is usually a bad idea and making new tables to keep history is not elegant as well. In fact this reason alone is good enough to reject my proposal. Other points you made I would still oppose and I will start by defining the security model.

The most convenient and secure way for multiple parties to sign a transaction is if each of them use the same software to generate the tx and then sign, exchange and combine signatures. We can assume that this software is mainstream and any observer can build a transaction for any smart contract with any given txHash (where txHash is applicable to smart contract).

Let us call a smart contract trustless if it has no external ec signatures and use txHash type signatures instead. Therefore under my security model any observer can inject transactions in a trustless smart contract. I am not going deep in why trustless smart contracts are important. Most notable reason is that it is possible to put an existing smart contract in another smart contract workflow without knowing the internals and not messing up permissions.

Two more fundamental assumptions come from Stellar design. If a transaction passes consensus then a tx fee has to be collected. Also if a transaction passes consensus then sequence number should be bumped otherwise an observer could resubmit the tx and deplete the account.

In this security model DoS is a non issue because in trustless smart contracts observers can inject transactions and force branches anyway.

As for depleting accounts I agree it is possible. For this reason the smart contract should be kept at minimum balance and XLM sent to it only when it is supposed to run. This concept is similar to Ethereum gas. Also note that account depletion is a low threshold attack and any non savings account should be kept little above minimum reserve.

Most useful loops cannot be unrolled. These include

  • infinite loops
  • when N > 30 and unrolling it requires 2^N or 3^N off-chain computations
    I have many very good examples for each of the cases.

On a side note I would like to propose to use a term 'scripted account' instead of 'smart contract' in Stellar terminology. I think 'smart contract' is misleading.

@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Jan 31, 2018

I think I see your point regarding the use of trustless contracts when used as a sub process of some sort. I imagine that to fix this would require having a way to perform some simple conditions as part of workflows - or at a minimum being able to perform branching from within a given transaction.

I didn't spend too much time yet on that front as we've been focusing on enabling the simpler scenarios, while at the same time letting the folks at Etherum experiment with more open ended contracts.

If you start to have good ideas on how we would solve that in Stellar - you should open a new issue to discuss it. This issue doesn't seem to be the right place for this and I don't want to lose valuable context.
Maybe it is related to the new issue that was opened around parametrized transactions as we will have to solve the "what is the ID of a transaction" problem ; maybe one of the parameters could be the sequence number while preserving the strictly monotonic property of sequence numbers.

So... going back to BumpSequenceOp, I think that with the amendment that I made after your comments, we have an operation that has the right properties to enable much simpler workflows than what is currently possible.

btw, when we use terms like "smart contract" we simply are using the definition that Nick Szabo put together 20+ years ago (something very simple); Etherum (for example) implements a lot more than that.

@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Feb 2, 2018

On the BumpSequenceOp front I discussed with a few other people and it seems that we can scope it even better.

First, it seems that keeping the weight to low as per the original proposal is the way to go for "BumpForward" (what this operation is).
Reason is: bump forward by 1 seq is already low, making it impractical to use sequence numbers as gating in the context of multi-sig where a "low" or "mid" set of signers can invalidate transactions from a "high" set.
Having a different weight for this operation would make it much harder for a "low" or "mid" set to "catchup" to a set of presigned transactions but would still allow those "low" or "mid" sets to skip arbitrary transactions in a set (exploitable as a timing attack), and as such would give a false sense of security.

Second, we need to move the restriction on the new value out of BumpSequenceOp (and remove the corresponding error BUMP_SEQUENCE_TOO_FAR), and instead move it into the MergeAccountOp operation.
That way we move the guard to where it's problematic (this is to avoid sequence number recycling after all). The check in MergeAccountOp is then to allow merging only if seqNum < (current_ledger_number<<32) - 1.

MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Feb 6, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Feb 6, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Feb 7, 2018
@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Feb 9, 2018

Circling back here after playing with the implementation.

One change that makes sense as part of this is to move to int64 (signed 64 bit integer) from uint64 (unsigned 64 bit integer) and make it that negative numbers are illegal values for the SequenceNumber type used in the xdr spec to reflect the limitations of the current implementation:

  • this makes it safe across all languages in client code (SQL, but also JS)
  • BumpSequence is what introduces the arbitrary high sequence numbers, so this change would not break any existing code
  • client code would still function before picking up the new XDR (when the network is still running the old version of the protocol)
  • client code may have to be updated when picking up the new XDR if it used the underlying type directly instead of SequenceNumber (some languages don't have type aliasing and/or don't allow assignment between signed and unsigned integers)
  • we already use this for amounts, for the same reason

Also, in case this was not clear, BumpSequence will not fail if attempting to bump backwards: it is not a necessary feature at this time and it's much cleaner to introduce bound checking as a condition at a later time for any operation (something that can only be done at the transaction level right now).

With this change the contract of BumpSequence would look like this (recap time!).

Description

Bump sequence allows to bump forward the sequence number of the source account of the operation.

If the specified bumpTo sequence number is greater than the source account's sequence number,
the account's sequence number is updated with that value, otherwise it's not modified.

Threshold: Low

Return values

BUMP_SEQUENCE_SUCCESS

The source account's sequence number was successfully updated.

BUMP_SEQUENCE_BAD_SEQ_NUM

The specified bumpTo sequence number is not a valid sequence number. It must be between 0 and INT64_MAX (9223372036854775807 or 0x7fffffffffffffff)

XDR

struct BumpSequenceOp
{
    SequenceNumber bumpTo;
};

/******* BumpSequence Result ********/

enum BumpSequenceResultCode
{
    // codes considered as "success" for the operation
    BUMP_SEQUENCE_SUCCESS = 0,
    // codes considered as "failure" for the operation
    BUMP_SEQUENCE_BAD_SEQ_NUM = -1 // the sequence number passed in is not within bounds
};

union BumpSequenceResult switch (BumpSequenceResultCode code)
{
case BUMP_SEQUENCE_SUCCESS:
    void;
default:
    void;
};

MergeAccount is modified to fail when the sequence number is too high:

/******* AccountMerge Result ********/

enum AccountMergeResultCode
{
    // codes considered as "success" for the operation
    ACCOUNT_MERGE_SUCCESS = 0,
    // codes considered as "failure" for the operation
    ACCOUNT_MERGE_MALFORMED = -1,       // can't merge onto itself
    ACCOUNT_MERGE_NO_ACCOUNT = -2,      // destination does not exist
    ACCOUNT_MERGE_IMMUTABLE_SET = -3,   // source account has AUTH_IMMUTABLE set
    ACCOUNT_MERGE_HAS_SUB_ENTRIES = -4, // account has trust lines/offers
    ACCOUNT_MERGE_SEQNUM_TOO_FAR = -5   // sequence number is over max allowed
};
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 13, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 13, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 16, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 16, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 20, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 20, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 20, 2018
MonsieurNicolas added a commit to MonsieurNicolas/stellar-core that referenced this issue Mar 20, 2018
@MonsieurNicolas

This comment has been minimized.

Copy link
Contributor Author

commented Apr 3, 2018

note: the change was merged in master on March-21st

@bartekn

This comment has been minimized.

Copy link
Member

commented Apr 4, 2018

Do you plan to publish this protocol change as CAP?

@jonjove jonjove closed this in #107 Jun 13, 2018

avi-kik added a commit to kinecosystem/core that referenced this issue Sep 10, 2019
avi-kik added a commit to kinecosystem/core that referenced this issue Sep 10, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
4 participants
You can’t perform that action at this time.