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

[Daedelus]

Vitalik may have just done the proof you were looking for for Nxt.. and found it to be "cryptoeconomically secure"

Lemma 3.0.3. The NXT algorithm described above satisfies the conditions
for being a cryptoeconomically secure entropy source.

Proof. To prove unpredictability, we note that the NXT blockchain produces
a block every minute, and so the update v ← sha256(v, V (β)) takes
place once a minute. During each round of updating, there is a probability
1 − po(60) that the primary signer will be online, and po(60) that the
signer will be offline and thus a secondary signer will need to produce the
block. Hence, after 1
−log(po(60)) blocks, there is a probability p ≈
1
2
that the
resulting value will be the “default value” obtained from updating v with
the primary signers’ public keys at each block, and a p ≈
1
2
probability that
the resulting value will be different. We model 512 iterations of this process
as a tree, with all leaves being probability distributions over sequences
of 512 public keys of signers, where all probability distributions are disjoint
(ie. no sequence appears with probability greater than zero in multiple
leaves). By random-oracle assumption of sha256, we thus know that we have
a set of 2512 independently randomly sampled probability distributions from
{0, 1}
256, and so each value will be selected an expected {0, 1}
256 times, with
standard deviation 2128. Hence, the probability distribution is statistically
indistinguishable from a random distribution.
To show that the first uninfluenceability criterion holds true, note that
the only way to manipulate the result is for the block proposer to disappear,
leading to another proposer taking over. However, this action is costly for
the proposer as the proposer loses a block reward. The optimal strategy
is to disappear with probability 0 < q <= 1 only when the predicate will
be unsatisfied with the proposer participating but will be satisfied with
the next proposer partipating; if a predicate has probability p this entails
disappearing p ∗ (1 − p) ∗ q of the time, meaning that the predicate will be
satisfied p + p ∗ (1 − p) ∗ q of the time instead of p of the time, a probability
increment of p∗(1−p)∗q will have a cost of p∗(1−p)∗q∗R if R is the signing
reward (whose real value is proportional to the quantity of transaction fees, a
reasonable metric of economic activity). Hence, the desired condition holds
true with b = 1.
To show that the second uninfluenceability criterion holds true, note that
when one is not the signer, one has no influence on the entropy, and when
one is the signer one has the ability to not sign and instead defer to the
next signer. Hence, an attacker controlling 1
k
of all signing slots will be able
to defer to the second signer 1
k
of the time, to the third signer 1
k
2 of the
time (by being in the first two slots simultaneously), etc, so in total such an
attacker will on average be able to choose between 1 + 1
k−1
values and thus
multiply the probability of a desired predicate by a factor of 1 + 1
k−1
. If the
attacker controls 1
3
of all signing slots, the result will thus be increasing the
probablity by a factor of 3
2
.

***********
it seems vitalik made a proof about NXT algo

[1715619088]

1715619088

[1715619088]

1715619088

[Peter R]

Vitalik may have just done the proof you were looking for for Nxt...

Thanks for the info and I applaud efforts like this to formalize the consensus problem.  My take on what Vitalik has done is that he's defined a term "crypto-economically secure entropy source" and then provided what he claims is a proof that the Nxt algorithm¹ satisfies this.  But note that even if the proof is correct, and even if the definition of "crypto-economically secure entropy source" is useful, it is still a far cry from convincingly showing that "Nxt is as secure as Bitcoin."

Let's take a closer look: Vitalik specifies that a "crypto-economically secure entropy source" should posses (a) unpredictability and (b) uninfluenceability.  In plain words, his definition of "unpredictability" just means that, given enough time, the "state" of the currency system at some finite time in the future cannot be determined with information available in the present moment.  Regardless of whether the system became fully unpredictable 10 minutes or 100 years in the future, his condition would be satisfied.  Also note that his proof is only valid in the case where p0(60) is non zero, which is not true at least in the trivial case where an attacker is in control of 100% of the active accounts.  

His definition for uninfluenceability (I) just says that there's a minimum cost for an attacker to influence the probability of some blockchain event.  Even if the cost is very small, and even if the event he's influencing is very significant, his definition would still be satisfied.  

His definition for uninfluenceability (II) is confusing to me.  He says that an attacker controlling k of the stake should be unable to change the probability of some event to more than p' = p*(1+b) for some constant b.  But there's always a constant value of b that would make p' = 100%.  Perhaps I'm misinterpretting something, but if an attacker controlled 0.1% of the stake and could influence the outcome 100% of the time, his definition of uninfluenceability would still be satisfied [although such as system would be very influenceable].

Anyways, I'm not trying to be critical of Vitalik's efforts, I'm just pointing out that the results applied to Nxt may not be very significant in terms of Nxt's actual security properties.

¹Neglecting the algorithm for how nodes that were previously offline determine the best blockchain out of many valid candidate blockchains upon rejoining the network.

[Peter R]

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.

Thanks for the info, CFB.

I believe I fully understand the "longest chain wins" consensus rule for up-to-date nodes, but I'm still confused by the "stick to the economic cluster" rule for nodes that are catching up.  

You mentioned that the incentives to stay on the same branch are economic.  I take this to mean that upon rejoining the network, a node cannot determine the correct chain with perfect reliability from several candidate chains using only information contained in the chains.  The node needs to acquire new information (e.g., the last version of Nxt or other information from peers) in order to figure which chain is best.  But I think what you're saying is that this should be "obvious" and sort of like "how do you know if you're connected to the REAL Internet when you rejoin and not a fake one?  Haha...eventually you realize that none of your friends are getting your messages!!"

[Come-from-Beyond]

You mentioned that the incentive to stay on the same branch are economic.  I take this to mean that upon rejoining the network, a node cannot determine the correct chain with perfect reliability from several candidate chains using only information contained in the chains.  The node needs to acquire new information (e.g., the last version of Nxt or other information from peers) in order to figure which chain is best.  But I think what you're saying is that this should be "obvious" and sort of like "how do you know if you're connected to the REAL Internet when you rejoin and not a fake one?  Haha...eventually you realize that none of your friends are getting your messages!!"

Scenario 1

Alice has never used Nxt. Bob (her friend) tells how it's cool. Alice downloads client software. Bob sends her hash of one of the recent blocks that his software sees. She copy-pastes the hash into the client and let the software to pick the same chain.

Scenario 2

Charlie is a guy who has no friends. He orders "50 shades of grey" DVD. He runs the client and downloads blocks for the last 6 months. Then he makes the payment to the DVD store. If the store is on the same branch then they will see his payment, otherwise they will inform Charlie that he should pick the branch that contains the block with <insert recent block hash here> hash.

Scenario 3

Dave buys 1000 NXT on Coinbase with USD and withdraws them to his wallet. In the interface of the website he sees that the transaction is done. If his wallet doesn't show the transaction then he copy-pastes the hash of a recent block from Coinbase site (or the wallet can pull this automatically) and jumps to the same branch.

Scenario 4

Eve always buys food in Walmart. She adjusts settings of her wallet to connect to Walmart website to ask for recent block hash, just to make sure that they are on the same branch.


This is how Economic Clustering works. It's perfectly legit to have Nxt blockchain forked several times. At some point you have to decide what branch to stick to.

[Peter R]

You mentioned that the incentive to stay on the same branch are economic.  I take this to mean that upon rejoining the network, a node cannot determine the correct chain with perfect reliability from several candidate chains using only information contained in the chains.  The node needs to acquire new information (e.g., the last version of Nxt or other information from peers) in order to figure which chain is best.  But I think what you're saying is that this should be "obvious" and sort of like "how do you know if you're connected to the REAL Internet when you rejoin and not a fake one?  Haha...eventually you realize that none of your friends are getting your messages!!"

Scenario 1

Alice has never used Nxt. Bob (her friend) tells how it's cool. Alice downloads client software. Bob sends her hash of one of the recent blocks that his software sees. She copy-pastes the hash into the client and let the software to pick the same chain.

Scenario 2

Charlie is a guy who has no friends. He orders "50 shades of grey" DVD. He runs the client and downloads blocks for the last 6 months. Then he makes the payment to the DVD store. If the store is on the same branch then they will see his payment, otherwise they will inform Charlie that he should pick the branch that contains the block with <insert recent block hash here> hash.

Scenario 3

Dave buys 1000 NXT on Coinbase with USD and withdraws them to his wallet. In the interface of the website he sees that the transaction is done. If his wallet doesn't show the transaction then he copy-pastes the hash of a recent block from Coinbase site (or the wallet can pull this automatically) and jumps to the same branch.

Scenario 4

Eve always buys food in Walmart. She adjusts settings of her wallet to connect to Walmart website to ask for recent block hash, just to make sure that they are on the same branch.


This is how Economic Clustering works. It's perfectly legit to have Nxt blockchain forked several times. At some point you have to decide what branch to stick to.

OK, I think I can see clearly how Nxt solves the problem of "after leaving the network for some length of time, how does a node determine the current state of the blockchain?", and how Nxt's solution is different than Bitcoin's.  

A Bitcoin node does not need any new information beyond what is encoded in the candidate blockchains themselves.  It applies a systematic and predefined function/procedure to each candidate blockchain:  

   cumulative work 1 = fcn(candidate chain 1)
   cumulative work 2 = fcn(candidate chain 2)
   …
   cumulative work n = fcn(candidate chain n)

and, for example, if Candidate Chain #2 has the highest value for cumulative work, it picks this chain as the best chain.  

Nxt is different, because the node relies on new information in addition to what's encoded in the candidate blockchains:

   best chain = fcn(candidate chain 1, candidate chain 2, … , candidate chain n, NEW INFORMATION FROM PEERS)

in order to select the best chain.  


I don't want to argue the validity of either of these methods; what I'm trying to do is formalize how the methods are different, and I think I've done that.  

BITCOIN: a node rejoining the network can determine the best chain without any new information beside what is encoded in the candidate blockchains.

NXT: a node rejoining the network needs new information in addition to what's encoded in the candidate blockchains.  

[Come-from-Beyond]

I don't want to argue the validity of either of these methods; what I'm trying to do is formalize how the methods are different, and I think I've done that.  

Ok. For others I'd like to add that Nxt's approach solves problems like famous Bitcoin Fork 2013 in a decentralized manner (without necessity to have a developer saying what branch to follow).

[Daedelus]

This is good thread 

[YarkoL]

This is good thread 

Certainly sheds illumination on many things.

[Daedelus]

@Peter R, you might be interested in an expansion of CfB's last comment here:

https://nxtforum.org/general-discussion/on-economic-clusters-and-the-longest-chain/

It is an "essay about Economic Clustering and The Longest Chain written by BCNext".

[allwelder]

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.

communism need cooperation from all of us.

[Peter R]

OK, I think it's fairly clear that a formal difference between the consensus algorithms for PoW and PoS comes down to whether or not a node "catching-up" may need new information beyond what is encoded in the blockchain.  

A PoS node rejoining the network may need supplementary information beyond what's encoded in the blockchain to determine the best chain (e.g., the economic clustering method), while a PoW node can determine the best chain strictly from what's encoded in the blockchain.  

This brings up my next question: I hear people talk about "weak subjectivity" in relation to PoS.  Is the fact that a new node may need additional information why the term "weak subjectivity" exists?  ...A PoW node can determine the best chain in a strictly objective manner, whereas a PoS node needs to rely on weakly-subjective new information?

Once again, I'm not trying to argue in favour of PoS over PoW or vice versa.  I'm just trying to wrap my head around the specific differences.  

[smooth]

Let's conduct a thought experiment. Imagine that network splitted for 24 hours and there are 2 competing branches. Thousands transactions are processed, thousands goods are delivered to the buyers. Now the network is merged and we see that the longest chain contains only 30% of the transactions but the shortest the rest 70%. Which network will win? BCNext thinks that the shortest one, coz economic majority will decide to lose less than more (we assume that loss is proportional to number of rolled back transactions), and I tend to agree with him. The reader is free to have another opinion of coz.

Another experiment. 20% of Bitcoin economy that owns 65% of hashing power decided to fork Bitcoin and add unlimited supply of the coins. Let's assume that they would mine 25 BTC per block forever. There are no other differences. What blockchain will a new user download? Of coz the one with unlimited supply because "the longest chain wins". Will the user agree on that? I doubt he will chose 20% of economy instead of 80%. And again we see that economic laws are more important than "mathematical" ones.

These two cases are quite different.

In the first case, both chains are valid according to the protocol definition. In the second case they are not.

It is possible that "economic majority" would win over protocol in the first case, but I'm not sure about that. Although people conducting trade on the shorter branch stand to lose money, and that interest is stronger in the short term, it may still be the case that respecting the integrity of the protocol is viewed as more valuable because that is something that protects everyone, including those losing money in this particular instance, in the long term).

In the second case there is no issue here. A chain that does not conform to the protocol is not a valid chain at all, therefore it can't be the longest chain. It's just garbage.

There is a variation of the second case where the economic majority decides to change the protocol. That is more interesting.

[LiQio]

 ...
This brings up my next question: I hear people talk about "weak subjectivity" in relation to PoS.  Is the fact that a new node may need additional information why the term "weak subjectivity" exists?  ...A PoW node can determine the best chain in a strictly objective manner, whereas a PoS node needs to rely on weakly-subjective new information?
...

I don't know if this is a generally accepted "definition" or the true origin of the term, but V. Buterin put it that way:

Weakly subjective:
a new node coming onto the network with no knowledge except (i) the protocol definition, (ii) the set of all blocks and other “important” messages that have been published and (iii) a state from less than N blocks ago that is known to be valid can independently come to the exact same conclusion as the rest of the network on the current state, unless there is an attacker that permanently has more than X percent control over the consensus set.

Under this model, we can clearly see how proof of stake works perfectly fine: we simply forbid nodes from reverting more than N blocks, and set N to be the security deposit length. That is to say, if state S has been valid and has become an ancestor of at least N valid states, then from that point on no state S’ which is not a descendant of S can be valid.

Source: https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

[YarkoL]

OK, I think it's fairly clear that a formal difference between the consensus algorithms for PoW and PoS comes down to whether or not a node "catching-up" may need new information beyond what is encoded in the blockchain.  

A PoS node rejoining the network may need supplementary information beyond what's encoded in the blockchain to determine the best chain (e.g., the economic clustering method), while a PoW node can determine the best chain strictly from what's encoded in the blockchain.  

This brings up my next question: I hear people talk about "weak subjectivity" in relation to PoS.  Is the fact that a new node may need additional information why the term "weak subjectivity" exists?  ...A PoW node can determine the best chain in a strictly objective manner, whereas a PoS node needs to rely on weakly-subjective new information?

Once again, I'm not trying to argue in favour of PoS over PoW or vice versa.  I'm just trying to wrap my head around the specific differences.  

Based on what I've read here, it appears that term "best chain" is
no longer meaningful in NXT. If I understand correctly, it is perfectly
fine for multiple exclusive fork-branches to exist.

On the other hand, even with "economic clustering" there will be, I suppose,
the "best" chain - that's where McDonalds etc are. But that would not be "best"
in any formal sense at all, even if in practice it would be the most
favored one.

If that is so, the consensus algorithms of Bitcoin and NXT aren't
all that comparable.

[Daedelus]

Short term consensus in Nxt is still "best chain" or "chain with most work".

Economic Clustering is for long term consensus after a break and you haven't kept up with the blockchain.


So, a new user starts their node and goes to McDonald's or whoever they want to send transactions to (they both have to be on the same chain for them to be valid). A large enough cluster will reinforce itself for the same reason and forks tend towards 1. Once the new user is up to date with the blockchain, economic clustering is no longer required. The user is then competing with McDonald's or whoever to create the "chain with the most work wins" to determine short term consensus.


That is my understanding. CfB has said in the past the BTC and NXT are very similar, if you consider each Nxt a small mining rig.

[YarkoL]

So, a new user starts their node and goes to McDonald's or whoever they want to send transactions to (they both have to be on the same chain for them to be valid). A large enough cluster will reinforce itself for the same reason and forks tend towards 1

So far it is unclear to me how the size of a cluster
eliminates forks.

What about this scenario: Alice wants to buy an ounce
of weed from SilkRoadNXT. So Bob passes him a blockhash
and she can sync with the branch where SilkRoadNXT is.

Afterwards she gets the munchies, so she wants
to buy a burger from McDonalds. She again calls Bob, who
gives her a hash from the chain with McDonalds.

And from now on, she has two NXT wallets or accounts on
her desktop: one for the weed, one for the burgers.  (Until
eating meat gets criminalized of course)

[Daedelus]

So, a new user starts their node and goes to McDonald's or whoever they want to send transactions to (they both have to be on the same chain for them to be valid). A large enough cluster will reinforce itself for the same reason and forks tend towards 1

So far it is unclear to me how the size of a cluster
eliminates forks.

What about this scenario: Alice wants to buy an ounce
of weed from SilkRoadNXT. So Bob passes him a blockhash
and she can sync with the branch where SilkRoadNXT is.

Afterwards she gets the munchies, so she wants
to buy a burger from McDonalds. She again calls Bob, who
passes her a hash from the chain with McDonalds.

And from now on, she has two NXT wallets or accounts on
her desktop: one for the weed, one for the burgers.  (Until
eating meat gets criminalized of course)

Why would Silkroad and McDonald's choose to be on different chains? There is an incentive for everyone to be on the same chain. If you deliberately fork with 1% of the stake, you are giving people a disincentive to use your chain as you will only be able to transact with 1% of the economy (and the 1% transactions wouldn't be accepted by the 99%).

[YarkoL]

Why would Silkroad and McDonald's choose to be on different chains? There is an incentive for everyone to be on the same chain. If you deliberately fork with 1% of the stake, you are giving people a disincentive to use your chain as you will only be able to transact with 1% of the economy.

Well maybe McD would announce they'll
have nothing to do with Silkroad and want
a clean, family-friendly fork.

And if that happened, users who wanted
both services would then have to use two wallets,
right?

[Daedelus]

Why would Silkroad and McDonald's choose to be on different chains? There is an incentive for everyone to be on the same chain. If you deliberately fork with 1% of the stake, you are giving people a disincentive to use your chain as you will only be able to transact with 1% of the economy.

Well maybe McD would announce they'll
have nothing to do with Silkroad and want
a clean, family-friendly fork.

And if that happened, users who wanted
both services would then have to use two wallets,
right?

By the same token, maybe they would start their own interwebs as they want a clean, family friendly net? I don't think this is likely scenario.

If they did do it deliberately, they would be effectively leaving the network and starting on their own. It would be like "Physical Silkroad" moving it's one department store from America to Tahiti. Their user base is and economy is drastically reduced.

Maybe CfB can answer definitively (he wrote Economic Clustering).

[YarkoL]

Their user base is and economy is drastically reduced.

Why, if you can run multiple wallets on
different branches?