search

iotaledger / iri

IOTA Reference Implementation
Other
1.15k stars 370 forks source link

Remove belowMaxDepth() call in tip selection algo #745

Open qriptau opened 6 years ago

qriptau commented 6 years ago

Description

Remove belowMaxDepth() call in service/TipsManager.java to improve the tip selection algo

Motivation

When selecting tips, nodes often stop the random walk early on a non tip because belowMaxDepth() returns true. This results in balls of unconfirmed transactions forming around milestones and also occasionally non milestones. The function does not seem to serve much purpose (from what i can tell, asked twice in discord tanglemath but was never answered) and without it, confirmation rate improves dramatically. Recent testing with majority hashpower removing this function from the IRI resulted in confirmation rate increasing from < 30% to > 70%.

Requirements

Modified tip selection

Open Questions

What is the purpose of the belowMaxDepth() check?

Am I planning to do it myself with a PR?

Yes if confirmed an ok change

qriptau commented 6 years ago

Alternative suggestion: keep belowMaxDepth() call but instead of iterating through all indirectly referenced transactions, only return true if the trunk or branch directly reference an old transaction.

GalRogozinski commented 6 years ago

belowMaxDepth() is used to protect against attacks forcing the nodes to perform very long walks as far as I know. Imo we should return an error if a client asks a node to perform a long walk.

Since I wasn't the one who decided on the current logic it will be best to consult @alon-e before any decision is made.

GalRogozinski commented 6 years ago

By the way, @qriptau, you can configure MAX_DEPTH in your iota.ini file. The default value is 15.

For example add for example: MAX_DEPTH = 20

qriptau commented 6 years ago

Thank you for your comment. However, i dont understand how belowMaxDepth() protects against long walks. It only checks if indirectly referenced transactions are old. Nodes often stop a random walk early on a milestone after finding a tip one step away just because the tip happens to indirectly reference an old transaction. But if a malicious user pre-computed a super long spam chain and attached it to recent milestones, the function wouldnt do anything to prevent other nodes from walking forward through the whole chain.

Also, MAX_DEPTH is not equal to the max depth variable i am referring to in belowMaxDepth(). MAX_DEPTH refers to the largest depth a user can set using the API. The max depth depth variable in belowMaxDepth() is equal to 2 times the user defined depth. It is not something a user can configure using the iota.ini file, although maybe it should be. The naming of these depth variables should probably be made clearer as well.

Another thing worth pointing out is that analyzedTranscations in belowMaxDepth() is misspelled and should be analyzedTransactions

GalRogozinski commented 6 years ago

  1. It protects against long range attacks. You won't be able to confirm a too old transaction with a recent attachment. Also the entryPoint() method determines where you start the walk according the depth parameter, thus protecting against very long walks that may consume too much resources. It doesn't protect against the attack you mentioned but it is not a reason to remove it. If someone wants to create blowballs they can make invalid txs with other methods.

  2. By mentioning MAX_DEPTH I wanted to demonstrate that a node operator can allow clients to start walks from larger depths. I didn't say it was equal to the depth parameter but I agree I should have been clearer.

  3. There are many more spelling errors in the code unfortunately... We will soon start a refactoring process where the spelling errors and other more urgent issues will be fixed.

qriptau commented 6 years ago

Assuming you are referring to parasite chains as long range attacks, those should be protected against naturally by the MCMC algo with the assumption that the main chain has more hashpower than the attacker. At least according to the whitepaper.

Even if belowMaxDepth() does protect against some sort of attack, i dont see how this function would translate well to a post-coordinator tangle when it is really needed to stop attacks. Without milestones to end on, belowMaxDepth() would always return true because each tx always indirectly references old txs.

The issue is that honest nodes using the default IRI are creating blowballs solely because of this function, causing conf rate to decrease as TPS increases (recently spamming 15 TPS with default IRI caused conf rate drop to near 5%). I think it will continue to be the case that conf rate decreases with increase in TPS unless one of the following things are changed:

  1. Removing the function (imo best option since i still dont believe it serves a useful purpose)
  2. Modifying it to only check trunk and branch
  3. Increasing max depth value to be >> 2*depth (or allow users to set it via iota.ini)
  4. Modifying coordinator to issue milestones at rate proportional to TPS (probably impractical)
  5. Coming up with some other less intuitive change relating to depth