*for internal discussion, by ED*
# Syncing the ledger (PoI, blockchainization)

## Introduction
The writeup was inspired by recent discussions around topics of *proofs of inclusion (PoI) in the Tangle* and *data on the Tangle*.

Here we cut some corners and skip technicalities wherever possible and only rely on fundamental assumptions and strategical options for the protocol. Therefore the picture may be somehow incomplete.

The methodological premise is that we separate the reasoning around the *ledger* from the reasoning about *the Tangle* as such (the structure which is behind the distributed consensus on the ledger).

## UTXO ledger model
We are following semi-formal model of UTXO ledger presented in the [IOTA SC whitepaper](https://files.iota.org/papers/ISC_WP_Nov_10_2021.pdf). In short:
* Each *UTXO transaction* (or just *transaction*) is *inputs* and *outputs*; Each output is uniquely identified by its ID = (*containing transaction hash*, *index in the transaction*). Each *input* is a reference to some output by its ID. The *transaction* is an *atomic* unit which *consumes* inputs and *produces* outputs
* The *UTXO ledger* (or just the *ledger*) is a set of transactions $L=\{T_1, \dots T_m \}$. It is a subject of usual constraints of the UTXO ledger. The main constraints, among others, are:
* each input of any transaction must consume exactly 1 output (unless origin)
* any output can be consumed no more than by 1 transaction
* The *ledger state* consists of unconsumed outputs or UTXOs $state(L)= \{utxo_1, \dots, utxo_n\}$. By adding a transaction to the ledger, we consume some UTXOs (delete them from the ledger state) and produce new UTXOs (add them to the ledger state)
* ledger can be modified only by adding 1 transaction to the set $L$. The transaction to be added can only consume outputs from the ledger state $state(L)$ (*no loops rule*). This way each transaction is a *transition* of the ledger state: $state(L_{prev}) \rightarrow state(L_{next})$.

The UTXO ledger defines partial order between UTXOs through transactions.

## Syncing the ledger: deterministic
Let's see the UTXO ledger as a data structure in itself, without the Tangle or blokchain which enwraps it. It means, we only consider set of transactions $L$ of the ledger and, as a part of it, the ledger state $state(L)$.

So, let's say a new node comes to the network. The new node takes some starting ledger state $state(L_0)$ and assumes it is valid.

The node keeps quering spending UTXO transactions from other nodes, check if the transaction is applicable to the current ledger state $L_i$ and it is valid. The node can validate the transaction in context of the ledger state. If it is valid, the node spends existing UTXOs in the current ledger $L_i$ by adding the transaction to it. This results in a new ledger $L_{i+1}$. The node repeats the above until reaches some $L_N$ from which it cannot proceed, the *final* ledger state $state(L_N)$.

The $state(L_N)$ is always a valid ledger state wrt to all constraints imposed by the ledger rules. However, the $state(L_N)$ **may or may not be a final ledger state of the distributed ledger**. The syncing node may end up with the $state(L_N)$ which is not equal to the real ledger state if some node, instead of sending transaction which was included into the ledger by the consensus, sends a rejected transaction (a double spend). The rejected transaction perfectly fits the ledger but it was rejected by consensus because it conflicted with some other transaction.

However, if all transactions which reached the syncing node are *confirmed* (i.e. included into the ledger by the consensus of nodes), the $state(L_N)$ will be the true final state of the distributed ledger.

Important properties of the ledger syncing:
* it relies on the gurantee that each transaction sent by another node is a transaction from the distributed ledger, i.e. included there by the consensus (confirmed). So, the ledger syncing relies on the **finality** concept
* the exact **order in which the confirmed transactions are sent to the new node is unimportant**. The only requirement in each step is that received (confirmed) transaction is applicable to the $Li$ and is valid. It is a deterministic fact.
(The analogy is a **Jigsaw puzzle**: it does not matter the exact sequence how we assemble it, it will always lead to the only valid result)

**Conclusion**: if the syncing node had a proof the received transaction is confirmed (finalized), the exact order in which transactions reach the syncing node is irrelevant to the final result, the final state.

## Syncing the Tangle: non-deterministic
By syncing the Tangle we mean starting from some set of vertices (a snapshot) and replaying the Tangle: quering messages (vertices of the Tangle) and augmenting the local Tangle data structure with with them step by step.

The ledger transactions are wrapped into (some) messages, therefore syncing the Tangle leads to gradual ledger update and thus syncing the ledger state.

For the final DAG data structure, it is unimportant in which exact order messages arrive: the final DAG is deterministic. However, if we look at syncing the (wrapped) ledger state, the Tangle also contains conflicting ledger transactions and the on-tangle history how it was voted on those conflics. So, the syncing node essentially has to replay the voting itself (here not important how exactly). Therefore, **the exact order of how we add messages to the Tangle is important for the final ledger state**.

This makes syncing the ledger state via syncing the Tangle **non-deterministic**, i.e. depending on random factors.

(in IOTA 2.x we also have off-tangle global randomness, comming from FPC metastability breaker. The description above assumes that off-tangle voting is eventually incorporated into the Tangle).

**Conclusion:** In order to make syncing of the ledger deterministic via Tangle syncing, we need global ordering of the Tangle, i.e. consensus on the order of messages.

**Conclusion 2:** finality of the ledger state is equivalent to the total ordering of the Tangle.

## Syncing the ledger in IOTA 1.x
Leder state in the coordinated IOTA is finalized by the Coo. This makes it possible the deterministic syncing of the ledger without syncing the Tangle.

It means, if we start from a valid ledger state, we can come to the valid latest ledger state by quering UTXO transactions directly or indirectly confirmed by the latest milestone. We do not need Tangle messages for that.

(Note that the current implementation may be different, for example full transactions are not available in general. However, the principle still holds)

## Syncing the ledger in IOTA 2.x
The confirmation/finality concept in IOTA 2.x is based on the *approval weight* (AW). The AW of the message/transaction is calculated from the future cone, therefore it is not known without receiving the future cone in some deterministic order. In general, it makes the syncing of the ledger via the Tangle, non-deterministic. **It can be made deterministic by assuming the global total order** in the Tangle, i.e. equally perceived by all nodes. This fact is also related to absence of strict finality in the ledger.

The probabilistic finality based on AW thereshold and synchronicity assumptions is acceptable to the usual user. E.g. if the transaction is approved by 80% of the active mana, it is very safe to consider it is confimed.

However, for syncing, we need a *proof* that transaction is confirmed, i.e. a proof which is "consensused" and cannot be reverted. This can be achieved by providing *proof of inclusion* (PoI) of the transaction into some Merkle root value or equivalent commitment. The Merkle root must be equally perceived by all nodes (or certain majority), i.e. under consensus.

This leads to the idea of **eventual blockchainization** of the Tangle.

Here we consider some options for such *blockchainization*.

**Conclusion:** for syncing of the ledger state we only need PoI of the transactions, not all messages.

## Blockchainization
Let's envision the following structure (inspired by the discussion with Hans):
* let's divide time scale into *epochs*, say 5 minutes each. So epoch starts at some UTC time value rounded to 5 minutes and lasts 5 min. Perception of the epoch is local for each participant due to its local clock
* the **current epoch** is the one which didn't finish yet. The **last epoch** is the one right before the current one. Epochs can be enumerated $0 \dots N$.
* the UTXO transaction is assigned to epoch based on its timestamp
* the perceived *ledger delta* in the epoch are all transactions with *approval weight* higher than some threshold, but not included into earlier epochs. Upon the end of the *current epoch*, the transactions in the *last epoch* are 5 and more minutes back, therefore local perception of the *ledger delta* in the *last epoch* will be the same for most of the nodes (it is a conjecture. That of course depends on clock tolerance acceptable in the network. It would be wise to enforce certain policy of time sync with global beacon).
* *somebody* (see below *levels*) creates a Merkle tree out of transactions of the *last epoch delta*. It also includes the root of the previous epoch delta into the Merkle tree of the *last epoch*.
* the *somebody* puts this new Merkle root into the the *milestone* message and attaches it to the tangle in the *current epoch*.
* the merkle tree referenced by the milestone contains *proofs of inclusion* of any transaction in the *last epoch* and, indirectly, PoI of any transaction in the past.

The structure described above is equivalent to structures used by Bitcoin and Ethereum. Here *epoch delta* corresponds to the *block*.

The syncing node can download necessary proofs to prove inclusion (fact of confirmation) of any transaction it receives. The only thing the syncing node needs it is to make sure that the root of the proof is the top of the chain of proofs in the network (it is constantly moving).

<p style="text-align:center;"><img src="https://i.imgur.com/YEAMVP1.jpg" width="700">
</p>

Note, that:
* the above results in a linear structure of the proof, sequence of epochs are similar to chain of block headers. The linear structure itself can be merklized in order to provide logarithmic (not linear) proof size for any transaction in the history (optimization)
* Merkle tree is just one option. We can also use other commitment schemes and *verkle trees* for efficiency.

Question: **who creates those milestones?** Below are some options by the level of decentralization:

### Level 1
Some *milestone proposer* (a *finality gadget*), probably committee-based, issues milestones of the *last epoch* in the current epoch.

The milestone is signed, therefore this assumes (global) trust to the signer.

The nodes vote on the milestone by including it into the tip selection and collecting AW of the milestone up to a certain threshold.

The **problem with this approach** is that, at least in theory, a majority of nodes can disapprove milestone proposal. That leads to complex scenarios of forking and reorg.

### Level 2
There are several **competing** milestone proposers. Each of them is globally known to the network.

Each of them propose milestones with merkle root of the ledger state in it. There's a significant probability that in the *current epoch* the root of the *last epoch* will be the same from different proposers, but this depends on how widely spread in the network those proposers are.

Milestones with different Merkle roots are considered conflicts, so all proposals must be consensused via the AW and probably FPC. In the end, one of them will satisfy criterium of being "confirmed".

### Level 3
Each node proposes its own milestone with Merkle root of the *last epoch* in the *current epoch* (5 minutes old from its perspective).

The proposed message will bear mana weight of the proposer. Majority of nodes will propose the same Merkle root, otherwise they will be conflicting and will have to be consensus-ed via AW and/or FPC.

The difference from the *option 2* is that here the milestone proposing is completely permissionless. However, having 10000 nodes would mean 10000 milestone/Merkle root proposals. This is unreasonable.

The solution may be restricting proposals only from nodes above certain active consensus mana threshold, while ignoring the rest (invalidating immediately).

In the end, the **longest chain wins** rule should be used. It means, if a node finds out that it synced to the milestone which ultimately appeared in the side fork, it will have reconsider new syncing (reorg) with the new milestone on top of the longest chain.

## Conclusions
- *syncing the Tangle* and *syncing the ledger* are two different processes with different properties
- under strict finality assumption (IOTA 1.x) you do not need to sync the Tangle in order to sync the ledger
- under approval weight assumption (IOTA 2.x) the above will work with introduction of finality with *blockchainization* of the ledger state with proofs of confirmation of transactions (PoI into the merkle roots of epochs, described above)
- in any case, there's no need for artificial ordering or the messages or transaction, because transactions are implicitely ordered by (iteratively) calculating merkle tree of the ledger.

# Trustless syncing

The syncing scenarios described above assume that starting ledger state $L_0$ is a valid (past) ledger state of the distributed ledger. How could we ensure that $L_0$, dowloaded by the new node, is valid?

Note, that here we are talking about the **snapshot**, i.e. full ledger state, which includes all UTXOs of it, not some deltas.

Once each milestone contains a merkle root which allows proving the inclusion (or absense) of any of UTXOs of any interim ledger state (the snapshot) into the final commitement of the latest epoch. This way snapshots become verifiable too.

**Conclusion:** There's only a need to keep the Tangle for the *current epoch* and *last epoch*. After that the state is finalized and deterministic, there's no need for the voting history and the Tangle (unless it contains some other data).

**Conclusion 2**: same applies to UTXO transactions: once we have proof of any UTXO of the ledger state encoded into the confirmed milestone, we do not need transactions online: they can be pruned and stored somewhere else to ensure auditability.