How do reorganisations work?

[Avionic23]

Hey, community. I've been wondering to understand how spacemesh reorganisations differ from blockchains like ethereum or bitcoin. I have several questions and would be grateful if somebody responds on them.

1. In case of the longest chain it is easy to check on reorganisation by just checking whether the previous hash matches with yours. So, you need to go back in history until your hash matches in the new longest chain. How to detect reorganisation on spacemesh and figure out which blocks/layers/transactions are invalid? Are invalid layers/blocks sequential in history or it is possible that only some of them become invalid?
2. In case of the longest chain it is quite often that blocks are mined at the same time and there is possibility of small reorganisation (1-2 blocks). Is this possible on spacemesh network? How long the reorganisation could be?
3. Reorganisations make different implications on system like duplicate transactions. Are tx duplicates there? If yes, then at what lvl they happen (layer or block lvl)? What are other implications?
   Thanks.

[lrettig]

Thanks for the questions.

In case of the longest chain it is easy to check on reorganisation by just checking whether the previous hash matches with yours. So, you need to go back in history until your hash matches in the new longest chain. How to detect reorganisation on spacemesh and figure out which blocks/layers/transactions are invalid? Are invalid layers/blocks sequential in history or it is possible that only some of them become invalid?

The API will tell you when there's a reorg. This should be a distinct event and it should tell you the layer as of which the reorg occurred. In order to figure out which transactions are valid, and to know the canonical state of the chain after this point, you (as a client) should assume nothing and walk the entire chain forward since the point of the reorg. After the reorg event appears in the API you may also query the current state of a particular account or transaction and assume that this has been updated as well. (CC @kacpersaw)

You'd know there's been a reorg if the "state hash" for a layer changed, and/or if the canonical block ID for a given layer changed.

Please also see https://github.com/spacemeshos/wiki/wiki/Integration-guide#reorgs-and-canonicity.

Are invalid layers/blocks sequential in history or it is possible that only some of them become invalid?

In case of a reorg it's not safe to assume anything, other than that anything may have changed. Some txs may have been invalidated, other new ones may have appeared, etc. Unlike a chain-based protocol like Bitcoin, it's not the case that, in case of a reorg in Spacemesh, all intervening blocks and transactions are immediately invaliated.

In case of the longest chain it is quite often that blocks are mined at the same time and there is possibility of small reorganisation (1-2 blocks). Is this possible on spacemesh network? How long the reorganisation could be?

Blocks in Spacemesh don't appear at random times as in Bitcoin. Instead Spacemesh miners cooperate to produce blocks deterministically and predictably, once each layer. The only way competing blocks could appear "at the same time" is if there's an attack or a serious, temporary violation of security assumptions such as a long-lived chain split. So, no, frequent short reorgs should definitely not happen on Spacemesh the way they do on other chains.

As in Bitcoin there's no theoretical limit to how long a reorg could be - there could theoretically always be a longer chain that you're not aware of. As in Bitcoin, however, in practical terms the likelihood of this happening falls rapidly with each new layer that appears.

Reorganisations make different implications on system like duplicate transactions. Are tx duplicates there? If yes, then at what lvl they happen (layer or block lvl)? What are other implications?

A transaction may be included multiple times in multiple blocks, including in different layers and including after a reorg, but it will only be applied (i.e., will only be effective) the first time it appears:

go-spacemesh/mesh/executor.go

Lines 239 to 256 in a2cdfd3

	// getExecutableTxs retrieves a list of txs filtering transaction that were previously executed.
	func (e *Executor) getExecutableTxs(ids []types.TransactionID) ([]types.Transaction, error) {
	etxs := make([]types.Transaction, 0, len(ids))
	for _, tid := range ids {
	mtx, err := transactions.Get(e.db, tid)
	if err != nil {
	return nil, fmt.Errorf("executor get tx: %w", err)
	}
	if mtx.State == types.APPLIED {
	continue
	}
	if mtx.TxHeader == nil {
	txs.RawTxCount.WithLabelValues(txs.RawFromDB).Inc()
	}
	etxs = append(etxs, mtx.Transaction)
	}
	return etxs, nil
	}

Regarding "other implications" - you may thus safely assume that a tx will never be executed twice, even after a reorg. But as I said above you can't make many other assumptions after a reorg. Blocks may or may not be invalidated, new blocks may appear, txs may or may not be ineffective and new ones may appear, etc.

HTH, let us know if you have other questions!

[Avionic23]

@lrettig Thank you for such elaborated answers

[lrettig]

I'll close this for now but feel free to reopen if there are other questions