Consensus Masterclass


Author
Message
Winston
Winston
Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)Forum Admin (33K reputation)
Group: Administrators
Posts: 3.5K, Visits: 6.6K
Masterclass given by Come-from-beyond. Archived on March 3, 2017
===========================================
As more and more people are beginning to find out about IOTA and its inherent differences to previous technology such as Blockchain, one topic that has been coming up is how the IOTA network - which uses a DAG, known as the Tangle - reaches consensus.

First some basics: in IOTA, every new (unconfirmed) transaction is known as a tip. These tips should each reference two previous transactions.

Choosing which tips to extend is decided by a Random Walk Monte Carlo algorithm which uses random tip selection to ensure that only good transaction branches grow. In this way, we build a Tangle structure.

To help explain how consensus on which transactions are valid can be reached - despite the random nature of tip selection - a Consensus Masterclass was recently held in the IOTA Slack by Come-from-Beyond.
-----------------------------------------------------------
Come-from-Beyond:
"There were a lot of questions recently about IOTA consensus and how it can be achieved if we are using Monte Carlo algorithm. I'm opening a master class dedicated to the esoteric art of achieving consensus in IOTA now.
There will be 2 phases.
During the 1st phase every participant is supposed to color this picture:



by following a simple rule:

Color each white square with green color if the square is referenced (directly or indirectly) by all gray squares.
Once the coloring work is completed, post your results and we can move onto the 2nd phase.
People soon took up the challenge and began posting their completed pictures.

Scott J:


stardust:


Pascal L:


Krischan L:


Michael K:


Jimmy Xiong:


Paul H:


Come-from-Beyond then explained what these pictures show and how to view consensus within IOTA:

"The main question that arises sounds approximately this way: how can you achieve a consensus if Random Walk Monte Carlo algorithm gives different gray squares?

Let's look at these pictures... we see that green squares are referenced no matter what gray square was picked by the Monte Carlo. This is the nuance which some people don't see.

We come to consensus on the status of green squares only.

More time passes - more transactions added - and eventually those white squares will be colored with green too.;

We don't know if young transactions are legitimate or not, but old ones are legitimate with very high probability (if they are referenced by the majority of tips returned by the Monte Carlo Random Walk)."

Participants were then invited to ask questions:

Question by Pascal L:
If each node has a different view of the tangle, then that would mean also a different set of Tips, right?
Now the consensus was reached here because we all used the same view of the tangle with the same set of Tips...what if I have a different set of tips that reference other transactions?

Come-from-Beyond:
If our views diverge too much we won't come to consensus, private subtangles branch-out and extra effort is required for them to branch-in later. There will still be some "green" transactions even we diverge, these are transactions we came to consensus on. They'll be just very old though. Worse connectivity between you and me = older txs with "green" status will be.

Question by Scott J:
Before I didn't realise at what point transaction get 'confirmed' without a Coordinator. So effectively, it is when they are referenced by all tips?

Come-from-Beyond:
Not by all tips, you set confirmation level for yourself. You may decide that if 95 tips of 100 returned by Monte Carlo reference your tx then it's legit. Some merchants may wait for 99 of 100.

Question by Michael K:
Is every node free (no protocol rules etc.), which squares have to be picked for a new tip for referencing?

Come-from-Beyond:
The protocol doesn't enforce tip selection algo, but for the system to work the nodes should use similar algos. A higher difference in the algos - longer adaptation period will be (adaptation period = time required for a tx to become "green").

Michael K:
And if a group is using a different alog, which is placing a lot of tips, which are referencing to 'old' transactions (the green squares on the left side in the example)?

Come-from-Beyond:
If their algo is too bad then their txs won't be referenced by the others. We use algo which benefits others for using it too.

Michael K:
So there is an algo (tip selection) in the reference implementation, which you should follow, or at least should not differ too much, because you will risk that the group which is using the reference implementation (or a similar tip selection algo) will never reference your tips?

Come-from-Beyond:
Yes.

Question by Pascal L:
So all nodes should still have close to all transactions to come to consensus. The less transactions of the whole tangle I have, the smaller the number of confirmed transactions.
Ah and that is why a narrow tangle is not good, as then one missing transaction can lead to all other transactions to not be confirmed?

Come-from-Beyond:
Yes, narrow tangle is bad

Question by Michael K:
If some nodes will never refer some tips, these tips still exist as tips also from their point of view, or do tips which didn't get a reference over a a specific time 'die'?

Come-from-Beyond:
They keep sticking around.

Michael K:
Why is it necessary to keep them sticking around, even if they didn't get any reference over a very long time?

Come-from-Beyond:
It's not necessary, they are just kept on some nodes, recently joining nodes will likely not see these tips

Michael K:
So a node can safely forget about this tips after a specific time?

Come-from-Beyond:
Yes.

project Shift
Shouldn't we implement a "lost old tip" tie-up algo also? I mean, if they are open forever, they can always be referenced and create a useless branch. If somehow we "close" them by doing some housekeeping and tie them up to a recent one?

Come-from-Beyond:
The protocol doesn't enforce this, you can create something for removing tips but they don't interfere into tangle evolution

Question by Pascal L:
Whats the big difference then between the tangle and a blockchain? If the tangle still needs most of the transactions to get confirmed transactions, then why should it scale that much better?

Come-from-Beyond:
In tangle there is no a single point of bottleneck (miners).

Pascal L:
No, but there still is the bandwidth and size issue?
If every machine uses it to make transactions, then that will be 100k's if not million transactions second. No node could ever keep up with that?

Come-from-Beyond:
Nodes can split the burden and solve this problem in swarm-like manner. IOTA is designed with this approach in mind.

Pascal L:
So I have that picture in mind where we have that huge tangle that no single node can run, now I was thinking that can be solved making branch tangles or sub tangles, that branch of and from there on will reference only the branch tangle transactions.
Which if I understand it right is the same logic of offline tangels...but if thats the case, how can double spends be detected?

Come-from-Beyond:
They can't be detected if you don't see most of issued txs, if majority of txs reference your tx then there is no a doublespending with high probability.

If you are a small merchant with low-end hardware then I suggest you listen for new txs and pick part of them and then fetching txs they reference until you see your tx.

Question by Pascal L:
So how do offline transactions work on a offline tangle?

Come-from-Beyond:
We add extra assumptions like the inability of all participants to doublespend before connection to global tangle is restored. If you can't use such an assumption then you can use multisigs, create a big multisig address, make sure it's confirmed and then go offline.

Once your connection is restored you'll need to broadcast your private subtangle to the rest of the network and connect it by issuing a tx referencing the both tangles.

Pascal L:
So offline tangles will be used for inner company transactions or where ever, where there is trust that the original funds don't get moved until the offline transactions are merged to the main tangle?

Come-from-Beyond:
There are several tricks to assure that doublespending won't happen, if we remove trust-based ones then we still have security deposits - an assurance that you won't doublespend and if you will then it will be covered from the deposit.

Also, multi-sig: if Samsung sells you hardware with IOTA inside and it's digitally signed then you can be sure that it won't doublespend.

Question by Pascal L:
So assuming that IOTA will gain adoption to where most IoT devices use it and there are 100k's of transactions per second, who will run those super nodes that can handel such amounts of transactions? Large company's?
Cause obviously my Notebook will not be able to run a full node then any more.

Come-from-Beyond:
Why supernodes?

Pascal L:
Lets say there are 100k TPS...won't that require a really strong server?

Come-from-Beyond:
Yes, or 100 weak ones.

Pascal L:
Now thats the interesting part! So there could be pools for full nodes, like there are pools for Bitcoin mining? So hundred small businesses could connect and pool a full node?

Come-from-Beyond:
Yes, as an example: https://en.wikipedia.org/wiki/MapReduce
GO

Merge Selected

Merge into selected topic...



Merge into merge target...



Merge into a specific topic ID...




Reading This Topic

Login

Explore
Messages
Mentions
Search