Decentralized milestone issuance scheme?

Question

I decided to preserve the original post in a pastebin for reference but the edits here address pretty much everything i think. Here is the link to the original post. There is also a link to a fresh chat at the bottom where we can continue the discussion.

Each node listens for a transaction hash (bundle hash probably is not the best option) containing some number of random characters, if possible I agree with Mihi and Saint Hill that changing the string each milestone and or obfuscating the string so that it is more difficult to predict and produce by an adversary would be best. However, for the sake of simplicity lets assume that it is just some random string short enough for the network to create regularly but long enough so that it would be difficult to produce over and over by an attacker. Ex: “ABCVIDSOQYEGHBF9QHOQNDUFAQ”. We would also have to test different attack vectors just in case an attacker could create milestones over and over in order to understand how serious of an issue that might be. Maybe the length should be variable based on the current throughput of the network. Once the node see’s this transaction it goes through checks:

• Is it valid? ( isBundle() )

• Is the history non-conflicting?

• Does it reference the previous milestone?

• Is the height from the previous milestone above a minimum threshold? (to ensure that the tangle has grown and many transactions are being immutably confirmed by it)

• Wait until it is considered confirmed by the network. (from it's point of view)

• Other normal checks that the Coo performs now that I may be leaving out.

My knowledge of how Qubic works is limited so this part may need to wait for more information to work out the details, but it can probably all either be coded into a Qubic or directly into the IRI. Once the node itself has determined that it believes this transaction would be a good milestone it submits it as an answer to an assembly. Here is how I imagine the assemblies to be assembled: 100 assemblies of variable size, the number of assemblies cannot change but the members within them can. The assemblies all submit their answer about which transaction they believe is a milestone to another Qubic that simply derives the answer based on a quorum of the 100 assemblies. This Qubic which is one layer higher than the 100 assemblies is what every node in the cluster listens to for the answer and would achieve a similar affect as the coordinator does now. Of course, that Qubic needs to be run by another assembly but the entire process should be auditable and each node can verify for itself whether or not it agrees with the answer given by the final assembly. There should probably be a fallback if the node disagrees.

This obviously needs to all be thoroughly tested for various attack vectors and Sybil resistance, and further refined in order to keep it as simple as possible and minimal overhead.

In this next section I address questions issues and concerns. I really appreciate these so keep them coming, this is how we develop ideas into bullet proof systems.

You say that a centrally issued Milestone system can't scale…why not? -Saint Hill

I may have overlooked a distributed coo environment where distributing it would be horizontal scaling. I was referring to vertically scaling a single coo. But maybe it would work, admittedly that was an assumption. Although I think most people would prefer a coo-less tangle anyway, if possible.

The idea that Validation and Proper Tip Selection is trivial -Saint Hill

The isBundle() function is trivial(debatable) . Tip selection may be more resource intensive but I was assuming that the potential milestone is like any other transaction so if it’s history cannot be validated then that would cause more issues with normal tip selection which would be a bigger issue. Either branch or trunk need to indirectly reference the most recent milestone but if the other is not referencing the most recent milestone and also has a height greater than some threshold it probably shouldn’t be chosen as a milestone or a tip because of resource constraints (might also help w.r.t GH issue #846).

High TPS Temporarily Solves Security Issues -Saint Hill

What makes you believe that TPS leads to reliable tip selection? I didn’t say that although my statement was kind of confusing. I should have taken more time editing and refining the post before submitting it. I sort of rushed it because I was in the process of creating it when suddenly I wanted to post it in response to a conversation I was participating in on Discord. Anyway, I meant that this scheme would work best in a high throughput environment because nodes shouldn’t really rely on milestones for confirmation but rather as an extra layer of protection (immutability), and that all of this extra complexity will probably take longer to complete than a central issuer so I figured 5-minute milestones is a reasonable time frame. But also, the timer might not be such a good idea now that I have had more time to think about it, minimum height is probably better.

A high TPS network may also have many long side-tangles and many networking issues that would prevent reliable tip selection. -Saint Hill

If this becomes a problem I think it transcends the system I am proposing bc it is more of a tip selection issue whereas the milestone candidates are already considered confirmed and not tips.

as the network grows, latency can also grow resulting in important changes to the DAG state while tip selection(s) are in progress. -Saint Hill

I believe walking from a deep enough depth is supposed to mitigate this but still not really relevant to this particular milestone scheme because they are not tips anymore, unless I misunderstood.

Having decentralized state/checkpoint/milestone guarantee 100% approved by the whole network is something that none of the existing truly decentralized DLT is able to produce today. -ben75

We have to also think longer term and bigger than just one cluster. If the network could scale infinitely with just one cluster of nodes i would agree with you but when EC comes into play we will have essentially separate networks of nodes that do not see each other’s transactions. I am not entirely sure how we expect to prevent double spends in a timely fashion (no DLT is safe from this reality). This method could potentially be a building block to a solution. In my mind I can imagine another class of nodes that are kind of like oracles updating the snapshot ledgers of all other clusters. So, essentially this cluster comes to consensus on a milestone and now all of those transactions are immutable, there will be a bunch of cluster oracle nodes listening exclusively for milestone ledger changes and they would neighbor with other cluster oracles in other clusters doing the same thing and those oracles would have to also neighbor with a bunch of neighbors in the same cluster as itself and the regular fullnodes would listen to the cluster oracles for updates that happened outside of their scope. Actually, maybe these cluster oracles could even participate in the final milestone Qubic and include their ledger changes. Sort of like a pyramidal structure of nodes communicating between clusters making sure the global snapshot state is consistent. Using that model I would think that confirmations would have 3 levels of confirmation: pending, confirmed(mutable), and confirmed(immutable). This has also been an idea simmering in my mind for a while.

Here is the chat

Answer 1

Nobody will say internet is centralized, but there is something call IANA(Internet Assigned Numbers Authority) for internet. The same thing can be done to tangle.

And IF can be IANA of tangle, and tangle will be still decentralized. i.e. instead of COO generating milestone, IF can have a list millstones that fullnotes can use.

Now the issue is how to add milestones on this list, it can be manually for beginning, then we can have software to check/validating as discussed and automatically add to the list.

you can either use this list or validating itself.

Answer 2

IMO, your proposal don't address the key question :

Wait until it is considered confirmed by the network.

This leads to the tricky questions :

1. Waiting for how long ?
2. Most important : how the IRI knows that it is considered confirmed by the network ?

The IRI have no knowledge of the network, it only knows it's neighbors. ( Using Qubic may help, but AFAIK assemblies don't work for free, so who is going to pay to have a Qubic calculating an approval rate ? )

I think the IRI can only make decisions based on it's local knowledge of the tangle and may also establish some kind of (semi-)trust with it's direct neighbors.

Based on this semi-trust and local knowledge of the tangle, the IRI should decide what transaction can be a suitable checkpoint for himself. That's the concept of private milestone (I already suggested this concept in another post), not shared by the whole network, but approved locally.

---

EDIT

Here is a suggestion to get rid of centralised milestones.

Basically, it's just a suggestion to implement a decentralised coo, based on auditable IRI and reputation.

If you look at the centralised coo, what is it doing ?

1. Periodically, it publish a milestone.
2. Milestone are authenticated.
3. The milestones issued by the central-coo are auditable. i.e. anyone can trace the milestones and check that any new milestone don't contradict a previous one (that's what IRI do).
4. So far, the network consider that a milestone issued by the central coo is 100% trustable (because auditable, and so far never failed).

Now, let's think about a de-centralized version of this process.

This approach use MAM in public mode and assume that every IRI participating in decentralised coo publish (in getNodeInfo response) information about it's own MAM channel.

1. Let's say that periodically, the IRI publish an authenticated message stating that it consider transaction X confirmed at 99% (or any other probability).
2. Because the message is published using MAM: it is authenticated.
3. Because using MAM, the complete history of any IRI is auditable.

4. By inspecting the history of IRI, other participants (i.e. other IRI) will be able to evaluate if the IRI is trustable or not (i.e. assign kind of reputation score). (if message N-1 say that transaction X is 99% confirmed, we can expect that message N is about a transaction approving X, just like milestone N reference milestone N-1: a trustable IRI will publish a "chain" of valid transactions).

5. Based on the reputation and the published trust level of other IRI, the IRI can decide what transactions can be considered as checkpoints and used as starting point for the random walk.

How to discover trustable MAM channels ?

Initially, the IRI knows only it's neighbors and their MAM channels. We can imagine that in addition to it's own MAM channel, IRI also publish channel information for it's most trusted peer. This mechanism will somehow propagate reference to trustable channels so that any IRI can select trustable channels to ensure that it stay aligned with the global tangle direction.