Proof-of-Stake Research Group

[kushti]

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/
• Inside Proof-of-Stake CryptoCurrency pt. 2 - Forging Algorithm 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 (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)

[tromp]

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.

[kushti]

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.

[DrGrid]

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.

[kushti]

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?

[DrGrid]

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.

[Come-from-Beyond]

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

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

[kushti]

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.

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

[tromp]

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.

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.

[ChuckOne]

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?

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

[Come-from-Beyond]

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.

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.

[tromp]

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.

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?

[fivebells]

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.

[Come-from-Beyond]

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?

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

[raid_n]

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?

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.

[raid_n]

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.

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

[Come-from-Beyond]

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.

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.

[raid_n]

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.

[Come-from-Beyond]

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.

[raid_n]

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)