Serguei Popov [2017.06.08 2:46 AM] The idea of MCRW tip selection strategy: it should be (a) sufficiently random (otherwise too many "unlucky" tips would be left behind), and (b) resistant to attacks one can imagine
Micah Zoltu [2:48 AM] In the whitepaper it says the walkers should start "deep in the tangle".  How is deep defined?
Serguei Popov [2:48 AM] Don't know. As deep as possible, depending on practical viability
Micah Zoltu [2:49 AM] I mean, how are you defining "deep"? Far from all tips via all paths? (edited)
Serguei Popov [2:49 AM] yes
Micah Zoltu [2:49 AM] It seems that if you can answer the "what is deep" problem you don't actually need to walk at all? Or do you walk randomly backwards from known tips, then walk randomly forward from wherever you land? Or perhaps it just means "old" (e.g., transactions you saw come through a long time ago).
Serguei Popov [2:50 AM] well, you can just choose among all tx's that appeared between (say) 1 hour and 30 min ago
Micah Zoltu [2:50 AM] OK.  So you choose _old_ (but not necessarily deep) transactions.
Serguei Popov [2:51 AM] these are _likely_ to be also deep
Micah Zoltu [2:52 AM] Sure, though I think the paper should be updated to say "old" rather than "deep" because "deep" implies that the selection algorithm is based on depth, not on age. In reality, you select on age and then compute depth (sort of).
Serguei Popov [2:53 AM] well, I don't really know what is the "best" selection algorithm. we can probably think of many _reasonable_ ones
Micah Zoltu [2:53 AM] OK, so you choose `n` random old transactions then you walk forward from each of them randomly choosing a child at each step until you reach a tip.  Once you have done this for all `n` (or they have timed out) you then choose the lowest distancet two tips?
So this tells me that as a selfish actor _not_ following this strategy, the optimal strategy is to build on other of my transactions that I want to promote.
That is, any of my old transactions that are within the selection time window that have stuff built on top of them.  The more they have built on top of them, the less likely they are to be selected for (since they will have a long walk to a tip).
Serguei Popov [2:58 AM] time to tip shouln't be important. exit probabilities matter
Micah Zoltu [2:58 AM] from the white paper: "the two random walks that reach the tip set first will indicate our two tips to approve"
My goal as a selfish miner is to increase the probability as much as possible that average distance-to-tip for any one of my transactions in the starting point eligibility window is as short as possible.
Serguei Popov [3:00 AM] "My goal as a selfish miner is ..." <- You need to control the exit probabilities too.
Micah Zoltu [3:01 AM] If I understand your goal correctly, you are trying to achieve an parent selection strategy such that the optimal strategy in face of others following the same strategy is to similarly follow that strategy.
Serguei Popov [3:01 AM] the same or at least similar; to know which tips are likely to be selected by the others, you'll have to do MCRW anyway
!! Micah Zoltu [3:03 AM] I'm operating under the assumption that the cost of selection is marginal compared to other costs and it is relatively trivial for a selfish miner to pick the mathematically best parents to maximize their chances of being selected for in the future, without having to run any randomized simulations.
Serguei Popov [3:05 AM] "I'm operating under the assumption .." <- I'm not sure it's a reasonable assumption. How exactly the selfish miner would do that?
Micah Zoltu [3:05 AM] A selfish miner can track all live tips as well as track all of the transactions that are in the common selection window and the distance from each of those to all of their tips.
Serguei Popov [3:06 AM] I have to go, sorry.
...
Micah Zoltu [4:00 AM] I would _like_ to be convinced that following MCMC _is_ the optimal strategy for a selfish miner when all other miners are behaving the same way, but I don't see that as being the case at the moment.
So there is the question of whether the majority of IoT devices will include ASICs and burn electricity doing proof of work.  For that discussion I believe that in the long run that won't happen because that strategy is marginally more expensive than the alternative "do nothing" strategy and I don't see a campaign for social welfare of Iota winning out over a campaign for lower energy consumption/costs.
But its possible that with the right connections you can influence _enough_ big players and drive marginal costs down low enough that most people don't care.
Paul H [4:03 AM] I don't think that PoW locality is relevant to tip selection
Micah Zoltu [4:03 AM] Right, that was the first half of my discussion with Serguei.
The second half was tip selection strategy for a selfish miner.
Where in this case a selfish miner's goal is to make his tip _most-likely_ to be selected by others while also (if possible) not selecting anyone else's tips.
That is, the selfish actor wants others to select his tip while never selecting anyone else's tips.
The reason for not wanting to select anyone else's tips is because he recognizes that as someone with substantial hashing power, if he and other heavy-hashers follow the "don't help the network" strategy then they can change the market dynamics so that they can run their miners at a profit.  If others _don't_ join him in his strategy then at worst he simply is as well off (if not better) than using the default strategy. (edited)
So, the question is, is there a tip selection strategy that a miner can take such that he will bias tip selection of the common strategy actors towards his tips without having to include anyone else's tips in his selection.
Such a strategy would create a trustless conglomerate that could alter the market dynamics such that they can start charging inclusion fees.
e.g., someone could release such a client to high-hash-power individuals that would yield same rewards if no one else uses it, and _better_ rewards if others _do_ use it.
Paul H [4:09 AM] I'm probably about to lose wifi again, sorry (back on the road)
Micah Zoltu [4:09 AM] Finally, there is a third point of argument that I haven't really brought up yet which is total network hashing power will likely be _very_ low if there is no incentive to hash more than is minimally necessary to get included, since extra hashing costs money and without transaction fees there is no return on that investment.
projectShift (Ricardo) [4:10 AM] but why would that be a problem?
Micah Zoltu [4:10 AM] Looking at the selection strategy in the whitepaper, it doesn't appear that there is compelling reason to hash heavily since tip selection is random-ish.  The gains of hashing are marginal relative to the energy costs.
Well, it becomes a problem because it lowers the cost of a sybil attack.
e.g., if total hash power is small enough, a single entity could spin up a giant sub-tangle with enough hash power behind it and enough transactions in it that it dwarfs the main tangle.  That actor could double-spend (traditional double-spend with lots of power attack).
The entire point of doing PoW anything is to drive that price up.  But that only works if people are sufficiently incentivized to give away non-trivial amounts of hashing power.
e.g., if every transaction has 1 unit of hash power behind it and I can generate 1 gigaunits of hashing power per second, I can sipn up a complete isolated side-tangle, double spend, then merge it right at the optimal time (middle of the MCMW tip selection window).
projectShift (Ricardo) [4:11 AM] ah! (sybil) the ever present issue
Paul H [4:15 AM] This assumes that you have enough hash power to overcome the present hash rate of the network.
projectShift (Ricardo) [4:15 AM] his point was just that, the network would have low hash power because there is no incentive (edited)
Micah Zoltu [4:16 AM] Also, in the MCMW algorithm in the white paper it didn't see anywhere where weight actually came into the tip selection process significantly.
There was the weight range thing, but it seems incredibly gamable to ensure that you fall within that range. (just requires distributing your hashing power across an optimal amount of tangle, which the random selection people will not be doing). (edited)
projectShift (Ricardo) [4:17 AM] ^we played around with that in testnet, didn't really play as a factor of importance
Micah Zoltu [4:17 AM] Which?  The weight range thing?
projectShift (Ricardo) [4:18 AM] yeah, the range; we tried various intervals with spamming, it didn't amount to what was expected
projectShift (Ricardo) [4:18 AM] but that was 4 versions ago, ofc, may not stand like that anymore
Micah Zoltu [4:18 AM] So without weight playing in at all, hashing power is effectively meaningless and the strategy boils down to setting up the optimal sub-tangle such that it is incredibly likely to be chosen in a conflict.
Which means you _must_ have weight be a significant part of (tip) parent selection, but then it means someone with high hash power can bias selection towards their tangle because they are focusing their hashing power while everyone else is distributing it.
Paul H [4:21 AM] Currently, the own weight is not considered in the tip selection (all tx are counted as 1), but a tx rating for tip selection is the sum of its own weight and the cumulative weights of its approvers
Micah Zoltu [4:21 AM] ^ So at the moment, it sounds like (tip) parent selection is basically just "shortest path to tip" from random transaction within a given time window.
Paul H [4:24 AM] it's not shorest path, but weight-est path
tx with most tx packed on it is the one that becomes most likely to be selected starting from a tx somewhere in the past ( currently milestones )
Micah Zoltu [4:24 AM] According to the whitepaper: "the two random walks that reach the tip set first will indicate our two tips to approve"
Reaching tip first is shortest path since all walkers walk in lockstep, right?
My interpretation of the strategy based on whitepaper and earlier discussions is:
So choose `n` random transactions between `x` seconds ago and `y` seconds ago.  Randomly walk towards tips from each of those in lockstep with eachother (they all step simultaneously) until two have reached a tip.  Those two are selected as parents.
I suspect my interpretation is wrong since it doesn't include weight (hash power) at all.
Its effectively a "without burning too much resources on optimization, try to find the least connected transactions and connect them to each other.  Over time this should lead to a general merging of all known sub-tangles. (edited)
AFK (for reals this time).
projectShift (Ricardo) [4:29 AM] ^that is an important factor, so we can have one big Tangle ... but only one.
Matthew Niemerg [4:33 AM] How I read the WP with the MCMC method, you take `n` random walkers placed on `n` random transactions. They walk towards the tips independently.  Choice in which direction to go is weighted more towards a transaction with higher cumulative weight if you are deeper in the tangle and then as you get closer to the tips, this spreads out to more of a random walk.  Then, in order to determine what your transactions' confirmation threshold is, you take number of random walkers that reach a tip that directly or indirectly reference the transaction of interest and divide that by `n` to give you percentage.
So I don't understand why walkers would be in lockstep.  They all reach a tip at some point (finite path length) and are independent.  You just need to know how many walkers reference the transaction of interest to get a probability that you are 'good'.
And as Paul mentions, all weights of each transaction are 1, but cumulative weight of a transaction isn't the sum of the path length.  Cumulative weight is the sum of all direct or indirect references of other transactions (only counted once), as per the definition.
Micah Zoltu [5:53 AM] What you just described doesn't sound like (tip) parent selection, it sounds like confirmation probability calculation.
It _feels_ like an altruistic (tip) parent selection algorithm would want to choose the heaviest weight tip and combine it with the tip with the highest unique weight.  The goal of this altruistic miner would be to attempt to get all transactions to converge to a single tip.
Of course, this strategy doesn't do anything to defend against an attacker generating a larger subtangle, double-spending on it and the current dominant tangle, then introducing their subtangle into the network and convincing everyone to build off of it instead.
Matthew Niemerg [6:12 AM] No. Tip selection is still a random walk. You have walkers that are moving towards the tips. Hence the walkers land on tips and that is selection. Oh you mean, tip selection as in, new transaction picks transactions to refer to.
Micah Zoltu [6:13 AM]
Right.  What I was describing above was "parent selection" selection, not confirmation calculation.