Bitcoin Forum

Proof-of-Stake is going to be popular distributed consensus algorithm these days. Some properties of the algorithm are very promising, but there are some concerns about it around also. Proof-of-Stake Research Group is here to make research about that!

In the first place, let me introduce myself. I'm Nxt core developer for last few months. To better understand Nxt forging algo I started to model it with Haskell(which is awesome for modelling purposes). Based on the model, two articles were published in my blog:

• Inside Proof-of-Stake CryptoCurrency pt. 1 - Basic Structures  http://chepurnoy.org/blog/2014/10/inside-a-proof-of-stake-cryptocurrency-part-1/ (http://chepurnoy.org/blog/2014/10/inside-a-proof-of-stake-cryptocurrency-part-1/)
• Inside Proof-of-Stake CryptoCurrency pt. 2 - Forging Algorithm http://chepurnoy.org/blog/2014/10/inside-a-proof-of-stake-cryptocurrency-part-1/ (http://chepurnoy.org/blog/2014/10/inside-a-proof-of-stake-cryptocurrency-part-1/)

Using this model a friend of mine , andruiman (writing math phd now) made academic-like paper about statistical properties of Nxt forging algo: https://www.scribd.com/doc/243341106/nxtforging-1 (https://www.scribd.com/doc/243341106/nxtforging-1) (scroll down to view online, to download PDF without FB login use Mega hosting  https://mega.co.nz/#!MJoRnByZ!9i6cZ89SvgtafIAVdlyuJEyqmNAPnvysxF6BCIKjePA ).

We plan to go further, and not around Nxt only. The next step is to make executable open-source simulation of forging process, then expand model. In the first place, we think to model blocktree storage for a forger with contributing to all possible chains of a tree (it's claimed to be a way to produce "nothing-at-stake" issue). We're also going to model some properties of proof-of-stake in more formal way with Coq theorem prover.


From this moment, we're going to call ourselves "Proof-of-Stake Research Group". Both of us are writing phds now(Computer Science / Math). In future we can expand number of participants for sure, but there's no need in that for now.

We're open to communicate with researchers / developers interesting in the topic.


P.S. We would like to get community support for sure:
BTC: 17YksFD7eRB4NhPfEtGrGnuvuwpkAeBd7f
NXT: NXT-R58Z-PUMK-JCG4-5TC6M

(PM for other possible options)

In part 2, the function
  verifyHit :: Integer -> Block -> Timestamp -> Integer -> Bool
relies on a timestamp.

How do you propose to deal with the fact that different participants
in the network will have different verification outcomes (due to clock variation)
and the resulting large scale disagreement?

It appears you just shifted the problem from next-block-consensus to time-consensus...

Also see
  https://nxtforum.org/general/forging-questions/?PHPSESSID=q72j729c59804eajc23qt07uo3
where NXT people failed to acknowledge the issue.

Timestamp is to be included into block so network members have ability to have determined verification result. However, a node can cheat by shifting timestamp a little bit (see 15 seconds rule in the topic).  Due to this rule difference in clocks should be within a range of few seconds. But that's not the important issue for network-wide consensus, I guess.

Just wanted to to present a sidekick of Proof of Stake: Proof of Research. It is based on Blackcoin's proof of Stake but contains some extra information in the block header. Miners may choose to partake in BOINC hosted scientific projects. Depending on the amount of quantified work they give for the specific BOINC project, they get an extra reward for a Proof of Stake Block next to their forging reward for the amount of BOINC work. This extra information has the potential of making certain aspects of Proof of Stake more secure.
Currently its only implementation is in the currency it was designed for: Gridcoin.

Does Gridcoin have a whitepaper with details on that?

The whitepaper was supposed to be released yesterday evening (the current Gridcoin whitepaper being completely outdated). I will post it, once the developer has published it.

A whole thread can't be used as a reference. Why didn't you point to a whole forum then? Waiting for the exact quote...

Thank you. The most interesting topics for me here is interaction of ordinary p2p computing network with blockchain and taking rewards confirmed externally into PoS system

What if a node purposely sets the timestamp 15 seconds ahead so that there will be large disagreement
on whether the new block has a valid timestamp?
This is a critical issue for network-wide consensus.

What do you except to happen? Maybe, it is the lack of imagination of what could happen, so please enlighten us.

Nxt uses so-called "Transparent Forging". In plain English it means that the forger of the next block is known, the timestamp of that block is also known in advance. It's not allowed to set another value for the timestamp, blocks with incorrectly set timestamps are considered invalid and rejected.

Answering your question: If a node purposely sets the timestamp 15 seconds ahead then all other nodes will ignore such the block.

With timers not being perfectly synchronized,
some will see the timestamp as only 14.999 seconds late, and thus acceptable,
while others will see it as 15.001 seconds late, and thus not acceptable.
Isn't that what your 15sec rule decrees?

Isn't every blockchain vulnerable to a similar attack?  For instance in bitcoin when you get a block you could delay releasing it until immediately after you see the next winner.  Some people who are closer to you on the network than to the next winner will then be forked.  If you had enough mining power and fast connections to different places in the world, you might be able to fork off a significant amount of hash power this way.

Explain what timestamp is, please. For me, timestamp is a number written in a block header. It can't vary. It's several bits that can't be interpreted differently. If one node sees it as "October 22, 2014, 03:26:16 PM" than all other nodes will see it as "October 22, 2014, 03:26:16 PM".

It is not the definition of a point in time that is the issue, it is that everyone has a different idea of what the current time is in relation to that point.
Tromp points out the issue that wanting to agree on time is just that, an agreement problem requiring a form of consensus in a distributed system.

How that agreement is formed is another story.

Yes. A long block interval softens the issue a bit because there is more time for information to propagate.
As you reduce block interval times connectivity gets more weight. Move block intervals to very very small values and effectively your connectivity will determine the winning chain (given a reasonable distribution of forgers/miners).

Nxt can't work properly in a non-synchronous network. We assume that nodes have clocks that don't diverge too much. +/-5 sec divergence is a reasonable window, an ordinary personal computer is able to keep itself within that window without any problems if Internet is available.

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.

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.

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)

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.

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.

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."

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.

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.

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.

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?

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.

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?

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

So the point of forging is not to reach consensus?

The point of forging is to reach consensus.

Extending multiple branches indefinitely is clearly harmful to reaching consensus.

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).

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

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.

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)