for internal discussion, by ED, see original in HackMD
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. 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 querying spending UTXO transactions from other nodes, checks if the transaction is applicable to the current ledger state L_i and is it 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 guarantee 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 wrt the ledger
By syncing the Tangle we mean starting from some set of vertices (a snapshot) and replaying the Tangle: querying 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 of the Tangle, 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, coming 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, for example “objective” timestamp.
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 threshold 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 confirmed.
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 discussions):
- 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 numbered 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).
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.
- there’s no need to order the Tangle messages (timestamps etc)
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.