Tangle : Algorithm to determine if a transaction is valid or not

Question

A node needs to verify that all transaction that it receives are valid before adding it to its local copy of tangle. For this we would need an algorithm which given the cone of this transaction would assert whether the sub-table is valid or not. In this regard I have 2 questions -

What is the definition of valid exactly other than syntactical validness. If I understand correctly for a transaction to be valid it must not approve (either directly or indirectly) conflicting pair of transactions. Is this correct?
Algorithm to actually assert this validity? If my understanding of a valid transaction is correct than in order to determine if a transaction is valid we would need to start from genesis and create a state of ledger for the sub-tangle and then check if the ledger is in valid state (non-negative balances). Although this is correct it seems to me that this is computationally very expensive considering that we would need to run this algorithm many times a second (=TPS). Are there any known efficient ways to tackle this situation?

PS : In the discussion above tangle is assumed to be (pure) COO-less.

whomaniac · Answer

First, pay attention that with Chrysalis iota fundamentally changes. It will change farther with coordicide, which is nothing like the original white-paper. White paper ideas will never come to fruition it seems...

However, I'll answer your question in the context of the old whitepaper (because this is what you are asking about :-) ).

A transaction (bundle) is semantically valid if the total sum of inputs and outputs is 0, and the signature is correct. Also the transaction is valid for tip selection if the resulting subtangle it produces (by merging 2 subtangles) is free of conflicts. So then answer is yes.
It wasn't in the white paper, but there should be a mixing point (transaction) that is not the genesis that you can start the walk from. A mixing point is simply a confirmed transaction that is deep enough in the tangle. Walking from/down to it would theoretically be equivalent to using the genesis.

I don't exactly remember the algorithm to find this mixing point, not even sure if it was formulated (I think it was). Since the original WP version of IOTA has been scratched, you will have to excuse me for not looking it up now :-)

Tangle : Algorithm to determine if a transaction is valid or not

One Answer

Add your own answers!

Ask a Question