Topic: Concise but complete technical description of various proof-of-stake (PoS) schemes? - page 2. (Read 2814 times)

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

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.

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

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

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.

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

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.

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.

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?

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?  

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?

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.

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

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

...what is incorrect about my summary?

I'm wondering if I misinterpreted this statement:


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.  

How are new blocks added to the blockchain?

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

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 both parts are understood incorrectly. Sorry, can't tell how it should be, too late in my timezone.

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.

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

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

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.

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


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.  


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.

How are new blocks added to the blockchain?

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