0

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 -

  1. 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?

  2. 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.

Improve this question

1 Answer 1

Reset to default
1

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 :-) ).

  1. 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.

  2. 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 :-)

Improve this answer
6
  • I am not particularly interested in Chrysalis but can you please elaborate more on how Coordicide is planning to deal with this computation or is it still undecided as of now? Thank you.
    – sarthak-ag
    Commented Jun 1, 2020 at 14:40
  • in coordicide you update the ledger state as transactions are coming in and you resolve conflicts with voting. No need for the computation
    – whomaniac
    Commented Jun 2, 2020 at 13:31
  • Not sure how voting can help in verification. Consider this scenario - there are 2 sub-tangles both of which stem from the same genesis but are otherwise disconnected entirely. I happen to have access to both the tangles so what I do is that I add the same transaction in both of the sub-tangles. Now let some time pass so that my transaction is buried somewhat deep inside the tangles. Now I maliciously issue a transaction that attempts to "merge" both the sub-tangles. In tangle such a transaction is considered invalid because it attempts to (indirectly) approve my 2 conflicting trans- (1/2)
    – sarthak-ag
    Commented Jun 3, 2020 at 6:00
  • But I nevertheless broadcast my merging transaction. In this case how will other network nodes verify that my issued transaction is invalid (and hence reject it) as it attempts to merge conflicting tangles. I see no other way for the network nodes than to walk through the sub-tangles until they realize something's fishy. What has voting to do here - I am confused.
    – sarthak-ag
    Commented Jun 3, 2020 at 6:02
  • In the minute a node sees the 2 subtangles merged it starts to ask the neighbor which tx it should accept I would suggest reading the new coordicide whitepaper or watching the youtube clips
    – whomaniac
    Commented Jun 7, 2020 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.