Concise but complete technical description of various proof-of-stake (PoS) schemes?

[Peter R]

Reading Andrew Poelstra's recent paper "On Stake and Consensus" got me interested in better understanding how various proof-of-stake schemes (cPOS, dPOS, etc.) work.

In particular, for each PoS scheme I want to know:

1.  After leaving the network for some length of time, how does a node determine the current state of the blockchain?

2.  How are new blocks added to the blockchain?

I'm finding it difficult, however, to extract the signal from the noise in the literature I find. Does anyone know of a concise but complete technical description of the various PoS schemes in use?


==================
SOME RESOURCES:

Original thread by QuantumMechanic:
https://bitcointalk.org/index.php?topic=27787.0

Nxt white paper:
http://wiki.nxtcrypto.org/wiki/Whitepaper:Nxt

Neucoin white paper:
http://www.neucoin.org/en/whitepaper/download

Bitshares PoS:
http://wiki.bitshares.org/index.php/DPOS

Wikipedia article:
http://en.wikipedia.org/wiki/Proof-of-stake

Bitcoin PoS wiki:
https://en.bitcoin.it/wiki/Proof_of_Stake

https://github.com/ConsensusResearch/articles-papers/blob/master/multistrategy/multistrategy.pdf

https://raw.githubusercontent.com/vbuterin/scalability_paper/master/scalability.pdf

[1714301219]

1714301219

[1714301219]

1714301219

[1714301219]

1714301219

[1714301219]

1714301219

[1714301219]

1714301219

[Peter R]

Reserved.

[Daedelus]

Concise and complete. I think the title is asking too much 

Have you posted this exact OP wording before? Seems very familiar

[Peter R]

Concise and complete. I think the title is asking too much  

By "concise but complete" I mean just enough details to understand how consensus is established and maintained [and not so much that the important points are obscured]. An example of what I'm looking for, applied to bitcoin, would be:

How are new blocks added to the blockchain?

Nodes assemble recent transactions into a block and attempt to find a nonce that when hashed with the new blockheader (which is cryptographically linked to the previous blockheader) produce a number less than some target:

    hash(blockheader, nonce) < target.

If a node finds such a nonce, it publishes the solution to the network.  Other nodes signal their acceptance of this new block by attempting to build new blocks on top of it.  

After leaving the network for some length of time, how does a node determine the current state of the blockchain?

Upon rejoing the network, a node considers valid chains where:

(1) the blockheaders form a cryptographic chain linking back to Bitcoin's genesis block,
(2) all transactions are permitted according to the protocol rules,

and selects the valid chain with the greatest cumulative work.  

Cumulative work is  
 
    cumulative work = work in block 0 + work in block 1 + … + work in block n-1 + work in block n,
    
where n is the number of blocks in the chain, and the work in the ith block is

    work_i = fcn(hash(blockheader_i, nonce_i)).

[Daedelus]

Ok. Concise: This is for Nxt.

http://chepurnoy.org/blog/2014/09/inside-a-cryptocurrency-slash-inside-nxt-announce/

Kushti can discuss if you think there are any holes

[Peter R]

Thanks. Here's what I've got so far for Nxt:

How are new blocks added to the blockchain?

Registered nodes (nodes with a private key whose pubkey has been registered as a Nxt account) assemble recent transactions into a block and attempt to find a nonce that when used to sign the generation signature from the previous block, results in a signature that hashes to a number less than some time- and balance-weighted target:

    hash(sign_with_node_privkey(previous_block_signature, nonce)) < target  x  balance of account  x  time in seconds since last block.

If a node finds such a nonce, it publishes the solution to the network.  Other nodes signal their acceptance of this new block by attempting to build new blocks on top of it.  

After leaving the network for some length of time, how does a node determine the current state of the blockchain?

Upon rejoing the network, a node considers valid chains where:

(1) the generation signatures form a cryptographic chain linking back to Nxt's genesis block,
(2) all transactions are permitted according to the protocol rules.

If more than one valid chain exists, the operator of the node would consult with people he trusts to determine the best chain.

[Come-from-Beyond]

Thanks. Here's what I've got so far for Nxt:

How are new blocks added to the blockchain?

Registered nodes (nodes with a private key whose pubkey has been registered as a Nxt account) assemble recent transactions into a block and attempt to find a nonce that when used to sign the generation signature from the previous block, results in a signature that hashes to a number less than some time- and balance-weighted target:

    hash(sign_with_node_privkey(previous_block_signature, nonce)) < target  x  balance of account  x  time in seconds since last block.

If a node finds such a nonce, it publishes the solution to the network.  Other nodes signal their acceptance of this new block by attempting to build new blocks on top of it.  

After leaving the network for some length of time, how does a node determine the current state of the blockchain?

Upon rejoing the network, a node considers valid chains where:

(1) the generation signatures form a cryptographic chain linking back to Nxt's genesis block,
(2) all transactions are permitted according to the protocol rules.

If more than one valid chain exists, the operator of the node would consult with people he trusts to determine the best chain.

The both parts are understood incorrectly. Sorry, can't tell how it should be, too late in my timezone.

[Peter R]

The both parts are understood incorrectly. Sorry, can't tell how it should be, too late in my timezone.

From this:

Each block on the chain has a generation signature parameter. To participate in the block forging process, an active account cryptographically signs the generation signature of the previous block with its own public key. This creates a 64-byte signature, which is then hashed using SHA256. The first 8 bytes of the resulting hash gives a number, referred to as the accounts hit.

The hit is compared to the current target value. If the computed hit is lower than the target, then the next block can be generated.

and from this:

In order to win the right to forge (generate) a block, all active Nxt accounts compete by attempting to generate a hash value that is lower than a given base target value. This base target value varies from block to block, and is derived from the previous blocks base target value multiplied by the amount of time that was required to generate that block…

...Each account calculates its own target value, based on its current effective stake. This value is:

   T = Tb x S x Be

where:

   T is the new target value
   Tb is the base target value
   S is the time since the last block, in seconds
   Be is the effective balance of the account

and from this:

...all accounts are stored on the network, with private keys for each possible account address directly derived from each accounts passphrase using a combination of SHA256 and Curve25519 operations...When an account is accessed by a secret passphrase for the very first time, it is not secured by a public key. When the first outgoing transaction from an account is made, the 256-bit public key derived from the passphrase is stored on the blockchain, and this secures the account.

I inferred that:

Registered nodes (nodes with a private key whose pubkey has been registered as a Nxt account) assemble recent transactions into a block and attempt to find a nonce that when used to sign the generation signature from the previous block, results in a signature that hashes to a number less than some time- and balance-weighted target:

    hash(sign_with_node_privkey(previous_block_signature, nonce)) < target  x  balance of account  x  time in seconds since last block.

If a node finds such a nonce, it publishes the solution to the network.  Other nodes signal their acceptance of this new block by attempting to build new blocks on top of it.

I know I've neglected details such as the 1440 blocks that coins must be stationary before they count towards the account's forging balance, as well as the rolling checkpoints 720 blocks back, but at a high-level, what is incorrect about my summary?

[Peter R]

I'm wondering if I misinterpreted this statement:

To participate in the block forging process, an active account cryptographically signs the generation signature of the previous block with its own public key. This creates a 64-byte signature, which is then hashed using SHA256.

I interpreted this to mean that the account produces an ECDSA signature of the previous block's generation signature with its private key (and that the word "public key" was a typo) and the resulting 64-byte signature got hashed.  

Does this instead mean that the generation signature is more like a fingerprint, and that the previous block's fingerprint gets mixed with the account's pubkey somehow in a deterministic way (hashing, XORing, etc.)?  This would make more sense because each account would then be restricted to one attempt to solve the block per second.  

[iGotSpots]

I don't really feel like going into detail, but I've recently warmed up to NXT, as well. I have issues with that particular network, but the tech itself is solid and worth looking into

[Peter R]

Here's what I've got so far for Peercoin (thanks in part to http://www.neucoin.org/en/whitepaper/download)

How are new blocks added to the blockchain?

Nodes wait for their turn to append a block containing recent transactions to the blockchain.  For each coin (UTXO) controlled by the node, the node checks to see if a specific data structure related to that coin hashes to a number less than some age- and balance-weighted target:

    hash(coin details, stake modifier, current time) < target  x  coin size  x  age.

If any coin controlled by the node meets this requirement, then the node signs the block it assembled and publishes it to the network.  Other nodes signal their acceptance of this new block by attempting to build new blocks on top of it.  

The data structure that gets hashed contains "coin details," something called the "stake modifier" and the "current time" in seconds.  The "coin details" for a particular coin are known the moment the coin is created and never change (but of course become useless if the coin is later spent).  The "stake modifier" is a sequence of bits that depend on details about the coin AND depend on details about the blockchain that correspond to times after the coin was created (and AFAICT the "stake modifier" remains constant once the coin reaches sufficient coinage to qualify for staking).  The "current time" increments each second and is the dynamic variable that causes the hash value to continually change, giving each coin a new opportunity once per second to create a block.    


One thing I appear to be missing: where do the details about the previous block go (in order to form a cryptographically-linked chain of blocks)?

After leaving the network for some length of time, how does a node determine the current state of the blockchain?

I'm not really sure yet, but I imagine the node would look for the chain that contained blocks regularly signed by Sunny King (the developer).  I'm also not sure what would happen if Sunny King signed multiple competing chains or stopped signing anything at all.  

[Come-from-Beyond]

...what is incorrect about my summary?

"Nonce". There is no "nonce" in Nxt.

I'm wondering if I misinterpreted this statement:

To participate in the block forging process, an active account cryptographically signs the generation signature of the previous block with its own public key. This creates a 64-byte signature, which is then hashed using SHA256.

I interpreted this to mean that the account produces an ECDSA signature of the previous block's generation signature with its private key (and that the word "public key" was a typo) and the resulting 64-byte signature got hashed.  

Does this instead mean that the generation signature is more like a fingerprint, and that the previous block's fingerprint gets mixed with the account's pubkey somehow in a deterministic way (hashing, XORing, etc.)?  This would make more sense because each account would then be restricted to one attempt to solve the block per second.  

In the very beginning (first 30'000 blocks) Nxt indeed used signing. It was an intentionally injected flaw that transformed PoS into PoW (one could generate different signatures for the same block). But then signing was replaced with hashing, restricting to one attempt to solve the block per block, not per second.

[Come-from-Beyond]

If more than one valid chain exists, the operator of the node would consult with people he trusts to determine the best chain.

This should be replaced with:

The software determines the best chain by analyzing ratio of transactions belonging to well-known participants (e.g. Walmart, Alibaba, Coinbase) of the economical cluster using Nxt. Non-legit chains can't include such transactions because every transaction refers to a block mined several minutes before the transaction timestamp, which prevents inclusion of majority of the transactions into chains with lower cumulative difficulty or into chains generated by an adversary.

[Tobo]

For people interested in knowing more about the Nxt code review - the intentionally injected flaws hunting with rewards - you can see the whole story of the peer to peer and line by line review here - https://bitcointalk.org/index.php?topic=397183.0

[Peter R]

In the very beginning (first 30'000 blocks) Nxt indeed used signing. It was an intentionally injected flaw that transformed PoS into PoW (one could generate different signatures for the same block). But then signing was replaced with hashing…

...There is no "nonce" in Nxt.

Haha. I found one of the intentionally-injected flaws without even looking at the source code.  BTW, I used the term "nonce" because the k-value used to produce an ECDSA signature could be used as a nonce to search the signature space for a {R,S} pair that hashes to a value that meets the target difficulty (thus creating a sort of PoW system as you pointed out).  

In any case, it sounds like the white paper is worded awkwardly.  Perhaps you could clarify:

To participate in the block forging process, an active account cryptographically signs the generation signature of the previous block with its own public key…

Should this instead say that the account hashes together the "generation signature" of the previous block with its own public key?

And does the "generation signature" of the previous block involve an ECDSA signature in some way?  Or is it more like a fingerprint that results from a hashing operation?

...This creates a 64-byte signature, which is then hashed using SHA256

Again, I'm confused because the ECDSA signatures used in Bitcoin are 64-bytes long.  But it sounds like the 64-byte signature is actually the output of a hash function.  Which hash function is used?  Do these 64-bytes get hashed again using SHA256, like the white paper says?  

But then signing was replaced with hashing, restricting to one attempt to solve the block per block, not per second.

OK, I think we're saying the same thing.  What I mean is that each second the quantity on the right-hand side (RHS) of this inequality grows:

    hash(previous block's generation signature, account's public key))  <  target  x  balance of account  x  time in seconds since last block.

Although the hash value on the LHS is static,  the RHS grows larger once per second, thereby giving the account one chance per second to produce the next block.  Is this not correct?

[Come-from-Beyond]

Should this instead say that the account hashes together the "generation signature" of the previous block with its own public key?

Yes.

And does the "generation signature" of the previous block involve an ECDSA signature in some way?  Or is it more like a fingerprint that results from a hashing operation?

No. Yes.

...This creates a 64-byte signature, which is then hashed using SHA256

Again, I'm confused because the ECDSA signatures used in Bitcoin are 64-bytes long.  But it sounds like the 64-byte signature is actually the output of a hash function.  Which hash function is used?  Do these 64-bytes get hashed again using SHA256, like the white paper says?  

This is outdated info. ECDSA is not used, only SHA256.

But then signing was replaced with hashing, restricting to one attempt to solve the block per block, not per second.

OK, I think we're saying the same thing.  What I mean is that each second the quantity on the right-hand side (RHS) of this inequality grows:

    hash(previous block's generation signature, account's public key))  <  target  x  balance of account  x  time in seconds since last block.

Although the hash value on the LHS is static,  the RHS grows larger once per second, thereby giving the account one chance per second to produce the next block.  Is this not correct?

This is incorrect. Chance is already predefined and it's not changed until the next block. One account can generate the next block in 47 seconds, another - in 112 seconds. If the account at mark 47 is mining then 112th doesn't have any chance (until the next block). This is how it looks - http://nxtportal.org/forgers/, - new block leads to a new picture.

[Peter R]

But then signing was replaced with hashing, restricting to one attempt to solve the block per block, not per second.

OK, I think we're saying the same thing.  What I mean is that each second the quantity on the right-hand side (RHS) of this inequality grows:

    hash(previous block's generation signature, account's public key))  <  target  x  balance of account  x  time in seconds since last block.

Although the hash value on the LHS is static,  the RHS grows larger once per second, thereby giving the account one chance per second to produce the next block.  Is this not correct?

This is incorrect. Chance is already predefined and it's not changed until the next block. One account can generate the next block in 47 seconds, another - in 112 seconds. If the account at mark 47 is mining then 112th doesn't have any chance (until the next block). This is how it looks - http://nxtportal.org/forgers/, - new block leads to a new picture.

Right, each participant in the network could calculate

    Q = hash(previous block's generation signature, account's public key)) / account's balance

for every account in the network, and then sort these from smallest to largest Q.  The participant who controlled the first account in that sorted list would forge the next block (once sufficient time has elapsed to meet the difficulty target), unless perhaps he goes offline (in which case the second account in that sorted list would forge).

[Peter R]

If more than one valid chain exists, the operator of the node would consult with people he trusts to determine the best chain.

This should be replaced with:

The software determines the best chain by analyzing ratio of transactions belonging to well-known participants (e.g. Walmart, Alibaba, Coinbase) of the economical cluster using Nxt. Non-legit chains can't include such transactions because every transaction refers to a block mined several minutes before the transaction timestamp, which prevents inclusion of majority of the transactions into chains with lower cumulative difficulty or into chains generated by an adversary.

Thanks for the response.  

I'd like to re-word this in a way that doesn't use the term "software"; the software is an implementation of a protocol.  A node is free to use different software provided it's compatible with the protocol.

I'd also like to re-word your description in a way that doesn't make statements about what is or isn't possible (e.g., the last sentence in your description), unless we can prove this mathematically.  In other words, I only want to describe how a node picks the best chain from multiple candidate chains.  

How's this:

============
Upon rejoing the network, a node considers valid chains where:

(1) the generation signatures form a cryptographic chain linking back to Nxt's genesis block,
(2) all transactions are permitted according to the protocol rules.

If more than one valid chain exists, the operator of the node would analyze each chain, calculating the ratio of transactions that belong to participants that were well-known the the node prior to him leaving, to transactions from other participants.  For each chain, the node applies a deterministic formula to get a score based on these ratios:

   score 1 = fcn(candidate chain 1)
   score 2 = fcn(candidate chain 2)
   …
   score n = fcn(candidiate chain n)

The node would select the chain that had the highest score.  
============

[Come-from-Beyond]

Thanks for response.  

I'd like to re-word this in a way that doesn't use the term "software"; the software is an implementation of a protocol.  A node is free to use different software provided it's compatible with the protocol.

I'd also like to re-word your description in a way that doesn't make statements about what is or isn't possible (e.g., the last sentence in your description), unless we can prove this mathematically.  In other words, I only want to describe how a node picks the best chain from multiple candidate chains.  

How's this:

============
Upon rejoing the network, a node considers valid chains where:

(1) the generation signatures form a cryptographic chain linking back to Nxt's genesis block,
(2) all transactions are permitted according to the protocol rules.

If more than one valid chain exists, the operator of the node would analyze each chain, calculating the ratio of transactions that belong to participants that were well-known the the node prior to him leaving, to transactions from other participants.  For each chain, the node applies a deterministic formula to get a score based on these ratios:

   score 1 = fcn(candidate chain 1)
   score 2 = fcn(candidate chain 2)
   …
   score n = fcn(candidiate chain n)

The node would select the chain that had the highest score.  
============

There are 2 rules for consensus in Nxt. Good old "longest chain wins" for short range (used by up-to-date nodes) and "stick to the economic cluster" for long range (used by catching up nodes). There is no a hard line between the rules, but if you suddenly join a wrong branch and make a payment then the counterparty won't see your transaction (you both must be on the same branch). The incentive to stay on the same branch is forced by economical laws, not by mathematical ones. I doubt you can formalize this with pure mathematical notation.

[presstab]

Don't know much about NXT, but for Peercoin and most of its derivatives:

Contrary to popular belief, Proof of Stake is not all that different from Proof of Work. When you are mining a PoW coin, your goal is typically to create a hash that has a value below a certain threshold. Your miner continuously hashes inputs until it produces a hash under the target threshold, and then announces the hash to all its peers, which scan the information and ensure it meets the rules. When it is confirmed that it met the rules, everyone moves on to the next block in the chain.

Proof of Stake also tries to produce a hash that is below a certain target. The target is different for each peer (but governed by the same rules), instead of the same target network-wide as is the case for PoW. The target is equal to coin weight multiplied by the bits in the block (bits is difficulty inversed). Coin weight is calculated a little bit differently for each PoS coin, but for a simple example we can say that coin weight is equal to the coin group (technically called UTXO, but also known as “pile”, “coin block”, etc.) multiplied by how many days old it is.

So if I have a group of 1,000 coins that is two days old, I would have a weight of 2,000. In order for this to “stake”, or to mine a new block, I would need to create a hash that is less than 2,000 multiplied by nBits. If nBits is equal to something like 100, then I would need to produce a hash that is less than 2,000 * 100 = 200,000. As you can see, the more weight I have, the easier the target is. If that group of coins was five days old, I would have to produce a hash less than 5,000 * 100 = 500,000.

The primary goal of Proof of Stake is to prevent a Proof of Work style system where the most hashing equipment you have, the more likely you will hit the target first. So in order to avoid someone from hooking up miners and hashing to create a PoS block first, the protocol only allows one hash to be created per UTXO per second. So if I were to be hashing on my desktop here and also have a server hashing the same wallet, they would create identical hashes and I would not have any extra advantage by hashing with more power at once.

If I have one UTXO held by my wallet, I am limited to 1 new hash per second. However, if I have 10 UTXOs in my wallet, I will have ten unique hashes I can create per second. Hashing is entirely random, so often you may have a large coin weight, but since you are only creating one hash per second, it does not have good odds of staking right away. This is why man people that understand the staking protocol will prefer 10 UTXOs of 1,000 coins instead of 1 UTXO of 10,000 coins.

http://bitcoinist.net/interview-presstab-pos-vulnerabilities/