Iota White paper section 4.4. Random walkers

Question

My question is regarding section 4.1 of Iota white paper. I really don't understand how particles or random walkers will be actually placed by the nodes in the tangle. What they state is : "The node just use their own pseudo-random number generators to simulate the random walk" Iota White Paper page no.20. But I am not able to grasp this.

extract from the Whitepaper:

The idea is to use a MCMC algorithm to select the two tips to reference. Let H x be the current cumulative weight of a site. Recall that we assumed all own weights are equal to 1. Therefore, the cumulative weight of a tip is always 1, and the cumulative weight of other sites is at least 2. The idea is to place some particles, a.k.a. random walkers, on sites of the tangle and let them walk towards the tips in a random 28 way. The tips “chosen” by the walks are then the candidates for approval.

So the question is "How random walkers are placed, on sites of tangle?"

Answer 1

A random walker on it's way to tip to approve must randomly select a path at each step. The random walker have the choice between all transactions (i.e. site) directly approving it's current site.

Here is an example, let's assume that the random walker is currently on a site (i.e. a transaction) directly approved by 3 transactions. Let's call those 3 transactions : next-site-1, next-site-2 and next-site-3.

Let's assume that the tip selection algorithm don't introduce weight (i.e. the probability to select any "next-site" is the same). The fullnode have to generate a pseudo random number between 0 and 1. If pseudo-random < 0.33 select "next-site-1", if 0.33<=pseudo-random<0.66 select "next-site-2", otherwise select "next-site-3".

Now, if the tip selection algorithm use weights: the fullnode will compute the weight of each next-site. Assume that the weights are as follow :

• next-site-1 : weight=50
• next-site-2 : weight=40
• next-site-3 : weight=10

Again, the fullnode use it's pseudo-random generator to pick a pseudo-random number between 0 and 1. With a pseudo-random < 0.5 select next-site-1. If 0.5<=pseudo-random<0.9 select next-site-2, otherwise select next-site-3

Regarding starting point of the random walkers, the white-paper states that there is no reason to start from the genesis, but that starting from reasonably old and randomly selected sites should be OK.

According my understanding:

• starting from genesis would be too costly in term of computing resources
• starting from too young sites could affect the stability/convergence of the tangle.

Answer 2

Currently we have the Coo node running and placing milestones at regular intervals and these milestones are used by the nodes to determine the 'direction' that consensus is forming among all the transactions.

When a wallet requests some tips to verify, the node makes two random walks from within the tangle to find those tips.

The first random walk begins from the last milestone that was issued. This ensures that one tip is going to be in the vicinity of other most recent transactions.

The second random walk begins from an older milestone defined by a parameter that can be chosen by the wallet/node, called "depth". The recommended depth is currently 3. With this value the second random walk will begin from the 3rd most recent milestone. This means that the second tip has an increased chance to be an older transaction.

With this system where the depth can be altered, the width of the tangle can be controlled. A lower depth will make a narrower tangle with more old txs left behind. A higher depth will make a wider tangle that includes older txs.

I leave it to someone else to explain how the nodes will decide these starting points in the absence of Milestones.

Answer 3

Selection of start points of random walkers is quite random in the Tangle.

1. First, it considers a subset of the Tangle with a cumulative weight between the range L and 2L where L is reasonably large enough.
   (The idea to select a subset between L and 2L and keeping L somewhat large enough is to place the particle deep into the tangle network so that the walk doesn’t end by just a couple of hops or just reach the tip straight away. However, We do not want to place the tip too deep into the tangle because it needs to find a tip to approve in a reasonable amount of time. Also, the interval [L, 2L] is largely arbitrary as one could choose [L, 4L] as their subtangle interval. There are also other ways to select the subtangle interval based on time. However, Tangle doesn’t have a native timestamp function and thus can't keep track of the time and therefore to use that technique we have to set t0 as a fixed point on some node)
   
2. After selecting the subtangle place N particles or walkers on N different transactions within that subtangle arbitrarily.
   (N is also selected arbitrarily and should preferably be more than 2 for additional security against a parasite chain being formed in parallel with the Tangle. The idea would be if any walker accidentally hops on to the attacker’s parasite chain, which will generally be longer, then it would spend a lot of time there and thus other tips would be chosen before that walker reaches first)