Bitcoin Forum

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

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?

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?

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.

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.

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.

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?

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

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

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.

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

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

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?

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.

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

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.

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

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

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.

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.

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.  

This is good thread  :)

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.

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.

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

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.

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.  

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.

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?

Their user base is and economy is drastically reduced.

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

McDonald's then tries to buy supplies for 100 they got from B. There is no one who wants to accept their transactions as the economy is so small, there are no fries suppliers running nodes on network B. They are all still doing business on network A.

I applaud you for attempting to spell
it out in so concrete terms. I think I understand
the argument, but


Is this a realistic assumption? wouldn't the fries suppliers have an
incentive to follow and open up an account on branch with McDonald's, so as
not to lose their large customer. And all the people with a liking
to hamburgers? Especially since they all - including McDonald's -
can still run wallets on the other forks.

I'm just not convinced that economic incentives are enough to
keep everyone on the same boat. To me they could under certain
circumstances encourage splitting. Please note that I don't think
this is a necessarily a bad thing at all.