Consensus improvement draft

There is block confirmation, that's the voting process.

It sounds like you might be operating under the original whitepaper understanding where voting only occurs when a fork is detected. That hasn't been the case for years - nodes vote on all transactions up front now. Iirc, accidental forks are still possible if users broadcast transactions from multiple wallets ("Natrium didn't work, let me try Nault"), or if someone tries sending transactions while bootstrapping a new node without being fully synced. Official implementation guidance is already to explicitly check transactions for confirmation

1 Like

You are right, I was basing my analysis on the 2017 whitepaper. Anyway, I think we had better to resume this talk after the new draft will have been improved. After my second reading the main problems I've noted are:

  • it needs a "context" paragraph at the beginning, explaining in which situation voting is involved (each transaction or fork?), how blocks are confirmed and what is the maximum size of unconfirmed blocks in the system.
  • figure 3 is missing (that's a copy of fig.1)
  • paragraph 4 (Consensus) really needs a section where types are explained (is time slice an integer? In this case, how the integer is related to local time? Is a vote a structure containing hashes of unconfirmed transactions and a boolean? etc.).

If we get a good draft, community could propose exploits or improvements without necessarily analysing the source code.

4 Likes

I know the Nano community is very fond of Nano's status as a deterministic ledger, but has there been any consideration for using a leaderless probabilistic consensus protocol like Avalanche Consensus?

2 Likes

Funny, I was thinking the exact same thing the last couple of days

1 Like

Seems like a combination of the random leader selection in Algorand's Pure Proof of State and fast probabilistic ledger state consensus via Avalanche Consensus would be close to as optimal as possible, and remove the need for representative nomination while keeping the principals of no direct monetary incentives, while also reducing knowledge of the current randomly selected leaders.

Rather than designating representatives with 0.1% voting weight as consensus participants, which then have a random leader for each period, could you maybe have a "representation period" (something equivalent to something like 1-12 hours) during which nodes are randomly selected for representation, then for each round of consensus, a random subset of those randomly selected representatives could be selected ("summoned") as leaders, synced via Avalanche Consensus, etc?

Wouldn't this allow for near-instant probabilistic finality with potentially thousands of nodes eligible for random leadership selection, without the leaders being known long in advance?

1 Like

Just a small addition to the above in case someone says that Avalanche is not good because it's probabilistic in nature: so is cryptography! I'd rather have a 1 in a quintillion chance that my transaction is not final rather than having a consensus protocol with a small chance of split brain at saturation.

1 Like

Random SELECTED leaders?
Selected by whom? A central coordinator?

Sorry but I disagree a lot with everything, the strength of the network is people putting their weight where they trust and being able to change it anytime they want.

this is not how the protocol works, nodes randomly pick samples of peers, there is no central coordinator. there is a paper from 2018 you can read and videos online.
Also he was referring to the current protocol, we randomly select leaders because we have no idea if they are evil or not, until something bad happens that is...

As gurghet touched on, the random leaders in the Avalanche protocol aren't selected by any centralized coordinator. They are essentially selected by themselves using what's called a verifiable random function (VRF), which is basically a way for individual nodes to show that they were randomly selected. It's a complicated topic, but there's a lot of material on it available.

My main pitch is that, rather than do this among the entire network, as is done in Algorand and Avalanche, Nano could do this in two rounds. The first to select representatives for a specified period of time, and the second to select a subset of those to act as leaders for each round of Avalanche consensus. This would result in maintaining Nano's performance/speed, while also improving randomization of leaders compared to the current dynamic principal representative protocol.

the random leaders in the Avalanche protocol aren't selected by any centralized coordinator

This was supposed to say "random leaders in the Algorand protocol" :man_facepalming:

Here is a quick visualization I did of my proposal. Is this feasible, or too significant of a change for Nano?

I fail to see the need to select leaders, we are just counting the weight for a block, we don't need to select anyone. Excluding some nodes would only make ORV weaker.

Leaders are already selected in the current form of ORV, it's just done by >0.1% total nomination weight. I'm proposing to swap that system out for a system with periodic VRF randomly selected leaders.

The reason Nano already does this is to reduce the number of nodes that need to be kept in sync via consensus, to optimize for speed. My proposal for randomly-selected leaders doesn't change this at all.

The other part of my proposal is to use the probabilistic Avalanche consensus protocol to achieve consensus rather than the current implementation that uses an old-school gossip protocol. This would allow for consensus to be reached in the same amount of time even with 5-10x the number of principal rep nodes.

Hey, you know every node simply sums all the principal reps signatures until they go over 67%, right?
There's no "elected" node to sign blocks since the wallet owners sign the block and then signatures are exchanged between nodes.
You do know that, right?

The reason nodes ignore signatures of other nodes that are less than 0.1% is performance, right, but there's nothing that preventing some principal nodes from "voting" would achieve.

I've been gradually reading through the whitepaper for the Stellar Consensus Protocol (SCP) after reading mention of it being used in MobileCoin. It's interesting stuff. I haven't gone through it with a fine tooth comb, but the whitepaper appears to have a bunch of formal proofs that the consensus is eventually sound/consistent.

The neat thing is that it is a voting protocol, like Nano, but without any need for stake or weight. Anyone can spin up a node, join the network and vote. Nodes consider a transaction finalised when their selected "quorum slice" has voted in favour of it. It's a federated system, so your node's quorum slice might only be a dozen nodes in which you have reasonably high levels of trust. Those each have a dozen nodes in their own slices and so on until the overlapping slices cover the whole network. If it works the way that I think it does, it could dramatically lower the bandwidth required to run a node. You wouldn't need to observe votes from every rep, or even every principle rep. You would only need to observe votes from a relatively small handful of nodes. And the whole problem of getting users to choose a principle rep could be done away with.

Not sure if the reality actually lives up to the promises. But if the dev team is considering alternative consensus protocols, SCP definitely looks like it's worth considering.

Stellar has slower confirmation time since a transaction has to be accepted by each quorum slice to be considered final. Quorum network topology would trade bandwidth for CPS then. David Mazières is one smart dude though and would probably have tons of insights for getting ORV proofs. Sounds like proofs are the big hold up before Nano can go to the big FX leagues.

Without weight you get vulnerable to Sybil attacks, you just need to spin up a bunch of nodes...

Saying there is "no weight" is probably a bit of a misleading way to describe it. As best as I understand the protocol, it's more like each node assigns whatever weight it wants to the nodes it chooses to be a part of its quorum slice.

For example, by choosing the NF node to be a part of my node's quorum slice (which also includes 9 other nodes), I am effectively saying "I personally deem the NF node to be a very trustworthy node, I will treat it as if it had 10% of the weight". The NF node has the Natrium node in its quorum, so the NF node treats the Natrium node as if it had 10% weight, regardless of what I think of the Natrium node. I might not even know what Natrium is, but since the NF node won't confirm a transaction without Natrium node agreeing, and I won't confirm a transaction without NF node agreeing, in practice I won't confirm without Natrium agreeing, even though Natrium is not directly in my set of trusted nodes.

I trust NF, and NF trusts Natrium, so I kind of "inherit" NF's trust in Natrium.

So there is "weight", but there is no need to try and synchronise every node's view of how much weight is held by each voting node. Each node can assign whatever weights they deem appropriate to a subset of nodes they hold in relatively high regard, and in practice, the trust then spreads out across the network.

Can you or someone elaborate here on what makes the ideal consensus algorithm for Nano? Maybe in brief pseudo code how a broadcast algorithm differs from #3 an interactive/acknowledge algorithm?

Would Avalanche's consensus algorithm be considered a request/acknowledge system because of the multiple rounds of sampling/voting?

Just want to make sure I understand what is desired as ideal and right for nano. Thank you for your time in advance.

2 Likes