Serguei Popov has been an integral part of the IOTA project since inception. He wrote the Tangle white paper and has guided the protocol toward its new consensus mechanism over years of hard work. He's a cofounder of IOTA, yes, but much more than that he's a calm, steadying scientific voice of reason that pierces through the deafening emotionally labile cross-winds of crypto.
As a mathematics professor, Dr. Popov fulfills his dual duties of both teaching at university and leading the IOTA research and development team. He's the project's senior-most resident research mathematician. His specialty is Markov chains and random walks, so he legitimately might be the perfect person to lead IOTA into its new fast probabilistic consensus (FPC) solution for Coordicide. Having observed from afar, he certainly loves MCMC, chess (he'll probably crush you), and music.
The IOTA Foundation is so lucky to have a brilliant mind and wonderful person of the caliber of the Professor. His revered presence at IF has surely lent the project immense credibility, and a seat at at least a few tables that wouldn't have otherwise been made available. Prof. Popov has recently collaborated with another academic heavyweight William Buchanan to (soon) publish a paper in the Journal of Parallel and Distributed Computing named Fast Probabilistic Consensus within Byzantine Infrastructures. Additionally, IOTA has gotten into the door of numerous academic institutions and partnered with top notch departments for collaborative research on Tangle consensus.
We feel it necessary to highlight an interview that Prof. Popov did with the IEN a few months ago. It has a mere 1,400 views, which means that a majority of the community still has yet to see it. It's a gem of a talk that must not go unwatched by anyone interested in the project. As always, HelloIOTA is here to provide a full written summary of the interview for those readers who obtain information more quickly by reading than by watching a 65 minute video. The full writeup is below, and the video is linked at the bottom of this page.
The video contains an extremely digestible powerpoint-supplemented talk on FPC followed by a brief round of questions from the audience. Note that professor Popov includes multiple questions, and at his usual best. Please be aware that the answers to those are included in the writeup below. Scroll straight down to the video if you want the full interactive audiovisual experience.
_____________________________________________________________
Be sure to take a look at Seguei Popov's new book, Two-Dimensional Random Walk - From Path Counting to Random Interlacements
_____________________________________________________________
The talk has three things in its title:
1. Coins - which have heads and tails randomness
2. Walks - which are random walks (think Markov)
3. FPC - which will meld the ideas of probabilities with random walks in the context of consensus in IOTA.
It begins with a thought experiment to challenge the viewer's intuition. Imagine this situation: 1,001 people toss a coin and report their result. Imagine a scenario in which a group of N malicious actors decide to collude to try to report heads so that heads win with 3/4 probability. What do you think the minimal size of N of the colluding group should be so that this case can be achieved?
Should N be small like less than 15 or 50? Medium like 100? Larger like 200?
The answer is that you need only 22 people to collude in this situation. Many people tend to overestimate this size, and hopefully this shows you how unreliable our intuition is when it comes to estimating probabilities.
We move on to a simple random walk that takes place in dimension 1. A coin is tossed, and the walker will go up for heads down for tails, taking one step forward along the x-axis for each toss. This is a very simple example of a stochastic process or a Markov chain. A simple random walk like this is very interesting and serves as a surprisingly rich model.
Let's question your intuition again: Consider the fact that there are two variables. Time spent above zero on the y-axis of the graph described above, and a variable called Z that represents the last time that both sides (heads and tails) were tied. In other words Z represents how long it's been since the plot touched zero on the y-axis. Again, probably going against your intuition, because it seems like these two variables should have no relationship, in fact they have the exact same probability of occurring.
When you think about the trajectory of the plot, you think it'll randomly go up and randomly go down. Therefore it should make sense that one player would lead about half the time, right?
Looking at the arcsin function, you can see that it attains its minimum at 1/2, and it integrates to 1 which allows it to be used for density of a random variable.
So imagine that two players toss a coin once per second over the course of one year. Would you ever have guessed that the probability that one of the players leads for less than 9 days out of the entire year is 20%?! And that the probability that one of them leading for less than 3 minutes is 2%! This means means that there's a 2% chance that one player leads for nearly an entire year. 2% is not a trivial chance, so this should again upset your intuition.
Next we take a look at integer lattices to gain an understanding of how dimensionality might affect the end point of a random walk. It turns out that the Polya theorem proved that if you start a random walk in dimension 1 or dimension 2, you will return to that same spot. But as dimensionality exceeds 2, you won't return to the same spot.
As the saying goes, " A drunken man always returns home. A drunken bird will eventually be lost." The man is walking on a 2D plane while the bird is operating in 3D space. The man's random walk will eventually bring him back to the same spot, but the bird isn't so lucky.
The catch, of course, is that the drunken man doesn't have it so easy. If you give the man 1 meter steps, what is the probability of starting in the middle of Paris, doing a random walk, and returning home after having the walk take you outside of Paris before returning home? And what about the probability of going out of our galaxy on your random walk before returning home? It's important to remember, again, that it's mathematically proven that being in dimensions 1 and 2 will return home after a random walk (we're treating the galaxy as a 2 dimensional saucer for this thought experiment).
The odds of your random walk taking you outside of Paris are 15%, and the odds of it taking you off the edge of the galaxy are 3.1%. Playing with a 3+ percent chance of walking off the edge of the galaxy is no laughing matter.
Now go back to only one dimension so that we can start with a more general random walk. In these cases, the probability of the walk isn't equal weighted on each side, and instead the "ground" is shifted one way or another. You can think about it like this: If a drunkard is walking on a sloped surface that slopes down and to his left, it more likely that his next step/stumble will be down the slope rather than up it. This can be applied in either direction and by any amount/slope. It can then be made more complex by combining two slopes to make a trough, or a mountain.
These are great models for studying real world applications. And he points out that thinking about random walks as being analogous to the motion of a drunkard is a great way to mentally frame the concept. Even some mathematics textbooks do this.
Taking the complexity of this model one step further, imagine a squiggly line that's broadly sloped down and the to the right, but it has two local minima on the way to the global minimum at the bottom right side. If a ball takes a random walk, it'll likely go down into the first local minimum, get stuck for a while before working its way down through the local minimums before reaching the global minimum.
He defines metastability as being the long amount of time it takes to get out of one local minimum - the time it's stuck in a trough that isn't the global minimum. It's called metastability because it appears to be generally stable because it takes so long to find the next minimum.
The amount of time the walker remains metastable - or stuck for a long time in a local minimum - can be mathematically modeled as being some random constant raised to its depth. The deeper the minimum, the exponentially longer it'll likely take to escape.
Global minimum is referred to as ground state, or stable state in physics, although Professor Popov says that this isn't the precise language used in mathematics. But it makes it easy enough to picture in your mind. Some number of metastable areas must be traversed before reaching steady state.
And with the probability background in place, and our probabilistic intuitions/egos thoroughly discarded by now, we put the pieces together and learn about IOTA's voting mechanism.
IOTA uses a voting mechanism in case of conflict to decide which transaction is valid, and which is invalid. This is formally referred to as "majority dynamics".
0 = invalid, 1 = valid
Nodes are nodes of the network, have a small number of neighbors, and adopt opinions using the majority rule. This is different than other consensus models in computer science because you're not polling almost every other node like you do in most CS algorithms.
The professor points out that majority dynamics have now been studied for 50 years, and that they have the interesting property known as extremal invariant measures: if everyone has the same opinion, everyone will remain that way forever. That's the nature of these dynamics, and we care about this because we want to achieve consensus.
We set up another graph that represents a probability distribution: 0 (invalid) to 1 (valid) is the x-axis, and the y-axis is likelihood of consensus. The graph looks like a mountain with a smooth rounded peak. Nodes in the IOTA network will take a random walk on the mountain, and should always be roughly 50/50 to fall either direction when at the top of the mountain. Notice that if it tips over, the node will eventually fall down to one side or the other.
This is majority dynamics as a random walk on a potential.
Things get more interesting when we introduce bad actors to nodes in the network. This is now majority dynamics with Byzantine actors, and drawing the new probability curve depends solely on the strategy that the bad actors decide to take. You'l see a differently shaped curve for each of their attempts.
"Help the weakest" is one malicious strategy which transforms the previously smoothly curved mountain top into what looks like a bowl. Remember that the time it takes to get out of one of these bowls/dips/minimums is proportional to the exponent of the depth. So this attack has potentially trapped some good nodes and separated them from creating proper consensus in the network.
"Let's bias it" is another malicious strategy that attempts to systematically bias the shape of the bowl at the top of the mountain to lean one way. If they initially lean it to the right (toward 1 on the x-axis), they'll capture some good nodes in the minimum and then be able to thrash the bias back and forth and potentially fork the network by breaking consensus.
He likes to call these problems (that look like bowls or dips at the top of the mountain) "the curse of metastability", because good nodes get stuck for so long in a local minimum. This is also why this sort of majority dynamics is not really Byzantine resistant.
Not to fear, though. There is a device that let's us defeat the curse of metastability. And it's simple.
Simply shoot honest nodes that are stuck waiting for time exponential with depth out of the bowl and off to the sides of the distribution curve. Fast Probabilistic Consensus uses an external source of random numbers to construct these random thresholds which successfully defeat metastability. We don't even need a lot from the random number generator. With this strategy, malicious nodes now have no vector by which to curse the network with metastability.
Q&A Summarized:
Q1: How will random walks change between the current implementation and the future Coordicide implementation?
A: Everything will change, because the way random walks are used in today's implementation are completely different to how they'll be used in the final version. Coordicide will be using random walks to gain intuition on what's going on with voting procedures. This means that the random walks are completely different things between the two implementations.
Q2: In FPC, is there a way to flip a node's vote once the voting process is finished?
A: In the unlikely situation where your node is really unlucky and disagrees with the rest of the network, it's easy to detect that your node is on the wrong side and get it fixed. So we have a trigger that indicates to your node that it should switch its vote. This is, of course, likely happen very rarely to rare individual nodes that'll just re-sync and get back in consensus. But the answer to the question is no - once the voting is completed, there's no going back and changing votes.
Q3: What force should cause this gravitation toward a desired direction?
A: The force is probability. Everything is a function of probability here.
Q4: In Coordicide when a transaction is sent, how long must it wait to see if there's a conflicting transaction?
A: The guess is some arbitrary small number like 10 seconds. They want to start from a pre-consensus state already so that, with high probability, the majority of nodes will already more or less agree on the status of a transaction. Then it'll let the voting mechanism work for some fixed time of on the order of seconds. You'll be reasonably sure that in normal circumstances the majority of nodes will receive all transactions issued in this amount of time. This is all to be tested in GoShimmer of course.But to be tested in goshimmer of course
Q5: How many transactions per second will the Tangle be able to do after Coordicide and after sharding?
A: Dr. Popov says that he's not the right person to answer this questions, although he points out that after sharding its TPS are theoretically unlimited. This is because the more transactions you get, the more you shard. He tosses out a guess of TPS in the thousands within the first cluster after Coo, but he emphasizes again the fact that he's not the one to be answering this question.
Q6: How can consensus be found when a node is offline for some time? Can consensus be found after connecting again?
A: If your node comes online after being offline, it'll have to listen to the network and download everything to see the state of the ledger. It'll look at the consensus and take into account the status of the high mana nodes. He notes that coming back online with a node is similar to starting a node up from scratch.
Q7: What are the biggest challenges on IOTA's path to solving the "trilemma"?
A: He tries to engage with the question without dismissing it out of hand, and says that he doesn't like when people use "theorems" in this way. The question is asking about some hypothetical trilemma that presupposes that only two of three things in a group can be achieved at the same time. He doesn't consider this to be a scientific obstacle on their path. He and the team are only interested in probabilistic consensus, which has nothing to do with a trilemma, so the question doesn't apply. They're building a real world system that aims for probabilistic consensus. They have probability to guide things, and he stresses again that he doesn't care about trilemmas. They just want to build the stuff and show that it works.
