Topic: Proof-of-Stake Research Group (Read 3036 times)

Hi guys!

Finally, we've changed the group's name to Consensus Research and issued research plan & assets to get funding:

Fundraising Letter -> https://nxtforum.org/consensus-research/first-fundraising-letter/
Asset: "consensus" on AE  https://trade.secureae.com/#5841059555983208287  (it's possible to buy them with Bitcoins there as well)

Sorry guys, we're reading forums, but prefer to reply in more deep manner
andruiman is preparing another paper on Nxt forging. Then we'll investigate common problems around proof-of-stake.

Why do you think those branches will ever win the longest branch race?

Maybe. But other factors clearly outweigh this because we don't observe such behavior in the wild. One of such factors may be incentive to forge a single branch to secure value of owned coins (which are used for forging).

Extending multiple branches indefinitely is clearly harmful to reaching consensus.

The point of forging is to reach consensus.

So the point of forging is not to reach consensus?

There is no a dis-incentive to forge multiple branches because there is no a proof that such activity is harmful.

So it would seem to benefit a forger to forge on all the chains they see,
even if not the longest, or if the timestamp is more than 15s ahead.

Because any branch they forge on could eventually become the longest.

Example: last block is at timestamp ts=10.
At time 55, blocks A is announced with ts=60,
and people forge on that, which will lead to a next block at time 115.

At time 60, block B is announced with ts=80.
Now even though not longer and ahead of time by 20s,
everyone might as well forge on that, which could lead to a next block at, say, time 110.

Or block B could be announced at time 120 and be on a strictly shorter chain.
Then it should still be forged on and immediately announce its successor with ts=110.

This would seem to lead to a multitude of branches all extended in parallel.

In bitcoin there is a clear dis-incentive to work on multiple branches.

What dis-incentive is there in NXT?

Yes. Eventually you connect to that node and if it still offers that block and that branch is the longest then you'll download it.

You mean that blocks with late timestamps are delayed rather than rejected?

If the timestamp of an incoming block is 5 minutes ahead of my time, do I reconsider it in 5 minutes?

You can model the distributed system as individual nodes each with the same amount of voting power but where an entity controls multiple nodes (i.e has x hash power or y coins at stake).
Alternatively one should weigh nodes based on their share of the voting power. It really makes no difference though.

The longest chain is created by each consecutive block "agreeing" on the sequence as the longest chain. If you reduce the entire system down to two entities, a and b you see why the majority eventually wins.
While individual blocks alternate between a and b if a has a larger share of resources used to determine the next block they will get drawn more often.
A can decide to allow b's blocks to stay in the chain but can also ignore them completely and make a longer chain. At no point in time can b be absolutely sure that a does not change their mind and start a new chain without him. Eventually that alternate chain will overtake the original one if the distribution of resources stays the same.

The majority always eventually decides on a chain it deems valid. It is important to stress the eventual because the apparent decision on the longest chain is only stable with a certain probability unless it is actually hard coded into the client.

I think it is important to make the distinction because at any one time no "real" decision is made when using blockchain consensus. You are just increasing the probability that that particular reality you perceive won't change again.

Timestamp is used to counteract attempts to forge blocks earlier than allowed. If you send a block very late then indeed it will likely not be accepted. The same in Bitcoin, if you send a freshly mined block late then it will become an orphan. Majority will indeed overrule but only because of longest chain wins rule, not because majority == a lot of nodes. A single node can overrule too if it has the longest chain.

It is no different to Bitcoin or any blockchain consensus for that matter. I'm not trying to attack NXT here but simply want to point out that your statement about agreeing on a timestamp is misleading.

I don't see how your correction to my statement is correct. If I send out a block very late and only a single other node accepts it it will most likely never make it into the longest chain.
Hence the majority has voted that my broadcast block was invalid. With ambiguity there is no "right" or "wrong" while being undecided.

If a majority receives the block late there is a strong probability it will not be included in the longest chain, ultimately deciding it was invalid.
If only few nodes discard the late block but the majority is building a chain on top of it it will be included, hence those nodes were overruled and they will also accept the block.

This is not a factor of time but one of blockchain length if something will be in the chain or not.

How is it different from Bitcoin? As I said, replace time drift with network latency (5 sec difference means 5 sec latency for block propagation). There are not many differences between Bitcoin and Nxt. Almost none if you think of every coin as of a small mining rig.

This is an incorrect statement: "To those that receive it late the block is invalid and they ignore it."
It should be: "To those that receive it late the block is invalid and they ignore it for several seconds."

Either we have a strong misunderstanding or you do not understand how blockchain consensus works.

Blockchain consensus is a majority vote. Each participant has a unique view of the system and will "blindly" follow its perception of the majority, which is the longest chain it knows of.
There can and will be concurrent chains for some time but eventually a majority is formed on one such chain (because it contains the majority of eligible voters).

I will give you an example of how a timestamp disagreement could play out (no idea if that could or does apply to this specific implementation):

Individual clients discard blocks with a timestamp >= 15 seconds in the future
Individual clients see a block with a timestamp of t+x | x < 15 as valid.

Node n has the ability to create a block. It is directly connected to a vast majority of other nodes via direct links.
Node n broadcasts its block rather late for some reason, say at t+14 seconds.
Taking transmission times and local clock differences into account some nodes will receive the block at t>= 15 while some will receive it at t<15.
To those receiving it within the permissible bound it is a perfectly valid block and they will happily continue on using it.
To those that receive it late the block is invalid and they ignore it.

You now basically have two groups of nodes that have a different belief of the blockchain with an equal length. (considering another block is created in time)
Luckily blockchain consensus is exactly built to resolve this issue. As new blocks are added one chain (the one with a majority of participants) outgrows the other in length, persuading more and more
nodes to accept it as the longest chain.


The above example is an abstract description and the problem can be replicated for any element where nodes can potentially disagree on a block.
It says nothing about the probability of occurrence or how the implementation deals with it.

Simply put, if there is ambiguity in accepting a block or not there is always the potential for a temporary fork.

Blocks rejected only if timestamp is far in the future (more than 15 sec ahead). There is no bound for the past and "longest chain wins" rule determines what branch will be accepted.

> If a majority of participants considers the block invalid, will it be dropped in favour of a different block?
Majority is irrelevant. Every nodes decides itself by following longest chain wins rule.

> If a majority of participants considers the block to be valid, will it be included?
Majority is irrelevant. Every nodes decides itself by following longest chain wins rule.

> Can both parties mentioned be in disagreement if the block should or should not be included?
Yes. Eventually the network will converge because of longest chain wins rule.

I am intrigued. As a disclaimer I'm not overly familiar with NXT specific PoS consensus.

From this discussion I gather that a new block might be discarded if the timestamp exceeds certain bounds.
Here are my questions:

If a majority of participants considers the block invalid, will it be dropped in favour of a different block?
If a majority of participants considers the block to be valid, will it be included?

Can both parties mentioned be in disagreement if the block should or should not be included?

If the timestamp has no effect on whether the block is included or not there is no point in going further in this discussion as time drift in this context is irrelevant (though in general the problem persists, I only wanted to point out that time cannot and should not be seen as an infallible tool for consensus)

That half of nodes that rejected the block will accept it 1 second later. Or even 5 seconds later. With 60 sec blocks it doesn't create any problem. Time drift causes the same effect as network latency.

You do understand that even if clocks are perceived to be synchronous you will always have a potential time drift so that at the edges of the permissible time interval there can be disagreement.

Synchrony makes many problems easier to solve because you are shifting the problem into a different domain. Agreement is more readily solvable in a synchronous system because you are essentially already agreeing on time or time intervals (with all the advantages and disadvantages it brings).

Time is relative to the observer and a guaranteed notion of common time is infeasible. You can reduce clock drift etc. but that won't prevent the issue of having to decide if something is "in" or "out" of the permissible time interval you specified.

With probabilistic consensus such events of indecision (a message at the edge of permissible time that some perceive as valid while others don't) are eventually corrected through the majority taking one side.
However there has to be a time where the network is partitioned into two groups, one believing the message was valid, the other rejecting it.
The only way to prevent such a splitting is always requiring a majority for decisions to be made. The downside of this approach is that a) you need to have an agreed upon set of voters e.g. group membership b) minority partitions need to block

For any synchronous system you can think of a situation where half of the nodes have a time t and the other half t+1 that are both within the permissible time drift.
If you want to make a binary decision of the form (received before time x) you cannot guarantee that all nodes will make the same decision.
Usually you will give permissible time ranges but there can be situations where an event is right at the edge of your defined time bounds.