Does proof-of-work solve the Byzantine generals problem?

[tinybike]

I have read several times that proof-of-work solves the Byzantine generals problem.  I am curious how it does so.  A bit of Googling turns up this page:

https://bitcointalk.org/oldSiteFiles/byzantine.html

As I understand it, the problem described on that page is that disagreements could arise among the generals due to network delay.  Each time the plan is broadcast, the likelihood of the same disagreement arising decreases.  (Exponentially, if the disagreements are due only to random chance.)

However, it is not clear to me what role proof-of-work plays in this scheme.  My understanding of proof-of-work is, essentially, that its purpose is to prevent sybil attacks, by making forgeries computationally prohibitively expensive, and of course I get that this is crucial for Bitcoin.  But, it seems to me this is sort of an auxiliary problem: now, in addition to network delay, the generals are also faced with an enemy who is trying to forge messages.

What I'm trying to figure out is, does proof-of work also address the problem of network delays?  It seems to me that the chaining the plan hashes together solves this problem -- at least, from a practical perspective -- without needing proof-of-work.

[jl2012]

I have read several times that proof-of-work solves the Byzantine generals problem.  I am curious how it does so.  A bit of Googling turns up this page:

https://bitcointalk.org/oldSiteFiles/byzantine.html

As I understand it, the problem described on that page is that disagreements could arise among the generals due to network delay.  Each time the plan is broadcast, the likelihood of the same disagreement arising decreases.  (Exponentially, if the disagreements are due only to random chance.)

However, it is not clear to me what role proof-of-work plays in this scheme.  My understanding of proof-of-work is, essentially, that its purpose is to prevent sybil attacks, by making forgeries computationally prohibitively expensive, and of course I get that this is crucial for Bitcoin.  But, it seems to me this is sort of an auxiliary problem: now, in addition to network delay, the generals are also faced with an enemy who is trying to forge messages.

What I'm trying to figure out is, does proof-of work also address the problem of network delays?  It seems to me that the chaining the plan hashes together solves this problem -- at least, from a practical perspective -- without needing proof-of-work.

Yes, assuming all players are honest, the network must converge after sufficient time, since mining is a random process.

Let's say the network delay is somewhere between 0s to 10s, and we have 2 competitive forks of the same length, fork A and fork B. Let delta be the difference between the time of finding the next block in the 2 forks. If delta is smaller than 10s, the network may not be able to decide the order of the the 2 blocks and the fork would continue. However, since mining is a random process, there is a chance (P) that delta is much larger than 10s. When this happens, the network will converge to the longest fork immediately. P approaches 1 as we wait longer.

That's why it's a bad idea to have a block interval of 1min or even shorter. When the block interval approaches the network delay, we will have more forks and more work is wasted.

[tinybike]

Yes, assuming all players are honest, the network must converge after sufficient time, since mining is a random process.

Let's say the network delay is somewhere between 0s to 10s, and we have 2 competitive forks of the same length, fork A and fork B. Let delta be the difference between the time of finding the next block in the 2 forks. If delta is smaller than 10s, the network may not be able to decide the order of the the 2 blocks and the fork would continue. However, since mining is a random process, there is a chance (P) that delta is much larger than 10s. When this happens, the network will converge to the longest fork immediately. P approaches 1 as we wait longer.

That's why it's a bad idea to have a block interval of 1min or even shorter. When the block interval approaches the network delay, we will have more forks and more work is wasted.

Ah, right.  That makes sense!  Kinda seems obvious, now that you've explained it  

Thanks very much for the explanation.

Follow-up thought:  To avoid forking, it seems like the "best" PoW scheme would be one where block-finding times are close to the mean (i.e., variance is low).  Since mining is essentially random, I guess the right mental model would be a renewal process -- almost Poisson, actually, but mining always gets more difficult over time.

Makes me think that the multi-hash-function algorithms popular in altcoins right now (X11, X13, etc.) are inherently more prone to forking, because of the extra among-hash-functions variance.  And, coins with random "superblocks" would be bad for the same reason.  Hmm.  I wonder if this is true empirically.

[jl2012]

Yes, assuming all players are honest, the network must converge after sufficient time, since mining is a random process.

Let's say the network delay is somewhere between 0s to 10s, and we have 2 competitive forks of the same length, fork A and fork B. Let delta be the difference between the time of finding the next block in the 2 forks. If delta is smaller than 10s, the network may not be able to decide the order of the the 2 blocks and the fork would continue. However, since mining is a random process, there is a chance (P) that delta is much larger than 10s. When this happens, the network will converge to the longest fork immediately. P approaches 1 as we wait longer.

That's why it's a bad idea to have a block interval of 1min or even shorter. When the block interval approaches the network delay, we will have more forks and more work is wasted.

Ah, right.  That makes sense!  Kinda seems obvious, now that you've explained it  

Thanks very much for the explanation.

Follow-up thought:  To avoid forking, it seems like the "best" PoW scheme would be one where block-finding times are close to the mean (i.e., variance is low).  Since mining is essentially random, I guess the right mental model would be a renewal process -- almost Poisson, actually, but mining always gets more difficult over time.

Makes me think that the multi-hash-function algorithms popular in altcoins right now (X11, X13, etc.) are inherently more prone to forking, because of the extra among-hash-functions variance.  And, coins with random "superblocks" would be bad for the same reason.  Hmm.  I wonder if this is true empirically.

No matter what algorithm you use, POW Mining is a Poisson process and the block interval follows exponential distribution. The variance is the square of the mean block interval. Since exponential distribution is the ONLY memoryless continuous distribution, it is the "best" and  at the same time the "worst" we may have.

http://en.wikipedia.org/wiki/Exponential_distribution

[tinybike]

No matter what algorithm you use, POW Mining is a Poisson process and the block interval follows exponential distribution. The variance is the square of the mean block interval. Since exponential distribution is the ONLY memoryless continuous distribution, it is the "best" and  at the same time the "worst" we may have.

http://en.wikipedia.org/wiki/Exponential_distribution

Mining is a renewal process, but I do not think it is Poisson, since even for single-function coins, the difficulty grows over time.  (In fact, it should be non-homogeneous Poisson: the block interval distribution should get lower and flatter as the difficulty gets higher, although it is still exponential.)

If the hashes are in a predetermined order, multi-hash-function (chained-PoW) mining block arrival times should also be exponential, since sums of Poisson processes are also Poisson processes.  (Assuming a fixed difficulty level, for the sake of discussion.)  However, choosing the hashes randomly results in an iterated (compound) Poisson process.  Here, the block intervals should have a more complicated distribution:

http://en.wikipedia.org/wiki/Compound_Poisson_process
http://arxiv.org/abs/1107.2876

If I remember right, Quark used randomly selected hashes.  I'm not sure about X11/13/others.  PoW schemes that include superblocks are also iterated Poisson processes, for the same reason.

[jl2012]

No matter what algorithm you use, POW Mining is a Poisson process and the block interval follows exponential distribution. The variance is the square of the mean block interval. Since exponential distribution is the ONLY memoryless continuous distribution, it is the "best" and  at the same time the "worst" we may have.

http://en.wikipedia.org/wiki/Exponential_distribution

Mining is a renewal process, but I do not think it is Poisson, since even for single-function coins, the difficulty grows over time.  (In fact, it should be non-homogeneous Poisson: the block interval distribution should get lower and flatter as the difficulty gets higher, although it is still exponential.)

If the hashes are in a predetermined order, multi-hash-function (chained-PoW) mining block arrival times should also be exponential, since sums of Poisson processes are also Poisson processes.  (Assuming a fixed difficulty level, for the sake of discussion.)  However, choosing the hashes randomly results in an iterated (compound) Poisson process.  Here, the block intervals should have a more complicated distribution:

http://en.wikipedia.org/wiki/Compound_Poisson_process
http://arxiv.org/abs/1107.2876

If I remember right, Quark used randomly selected hashes.  I'm not sure about X11/13/others.  PoW schemes that include superblocks are also iterated Poisson processes, for the same reason.

Difficulty changes over time only because the hashing power is increasing, and happens only once in 2016 blocks. We can just assume it is fixed.

With some tricks we may reduce the variance without reducing the mean block interval. However, mining is no longer progress-free and the fastest miner will earn more reward than he should. This has been discussed here: https://bitcointalk.org/index.php?topic=572816.0

I don't have much idea about those alt coins. If their mining are not Poisson process, they are flawed.

[dreamhouse]

Yes, assuming all players are honest, the network must converge after sufficient time, since mining is a random process.

Let's say the network delay is somewhere between 0s to 10s, and we have 2 competitive forks of the same length, fork A and fork B. Let delta be the difference between the time of finding the next block in the 2 forks. If delta is smaller than 10s, the network may not be able to decide the order of the the 2 blocks and the fork would continue. However, since mining is a random process, there is a chance (P) that delta is much larger than 10s. When this happens, the network will converge to the longest fork immediately. P approaches 1 as we wait longer.

That's why it's a bad idea to have a block interval of 1min or even shorter. When the block interval approaches the network delay, we will have more forks and more work is wasted.

Ah, right.  That makes sense!  Kinda seems obvious, now that you've explained it  

Thanks very much for the explanation.

Follow-up thought:  To avoid forking, it seems like the "best" PoW scheme would be one where block-finding times are close to the mean (i.e., variance is low).  Since mining is essentially random, I guess the right mental model would be a renewal process -- almost Poisson, actually, but mining always gets more difficult over time.

Makes me think that the multi-hash-function algorithms popular in altcoins right now (X11, X13, etc.) are inherently more prone to forking, because of the extra among-hash-functions variance.  And, coins with random "superblocks" would be bad for the same reason.  Hmm.  I wonder if this is true empirically.

Not sure I understand why "superblocks" would cause any problem. These are the blocks with only payout difference, no hash algo diff. Can you explain some more?

[jonald_fyookball]

PoW works because state changes (information propogated from nodes) happens orders of magnitude faster than complexity changes (new blocks)

[tinybike]

Ah, right.  That makes sense!  Kinda seems obvious, now that you've explained it  

Thanks very much for the explanation.

Follow-up thought:  To avoid forking, it seems like the "best" PoW scheme would be one where block-finding times are close to the mean (i.e., variance is low).  Since mining is essentially random, I guess the right mental model would be a renewal process -- almost Poisson, actually, but mining always gets more difficult over time.

Makes me think that the multi-hash-function algorithms popular in altcoins right now (X11, X13, etc.) are inherently more prone to forking, because of the extra among-hash-functions variance.  And, coins with random "superblocks" would be bad for the same reason.  Hmm.  I wonder if this is true empirically.

Not sure I understand why "superblocks" would cause any problem. These are the blocks with only payout difference, no hash algo diff. Can you explain some more?

I did not realize that superblocks are of the same difficulty as normal blocks.  If this is the case, then superblocks should be fine.

This conversation makes me think that a "crypto dictionary" would be very useful.  What are superblocks?  What is X11?  X13?  What algos are used, and are they selected randomly or deterministically?  It's hard to find clear definitions for anything (aside from the tech in Bitcoin itself).

[dreamhouse]

Ah, right.  That makes sense!  Kinda seems obvious, now that you've explained it  

Thanks very much for the explanation.

Follow-up thought:  To avoid forking, it seems like the "best" PoW scheme would be one where block-finding times are close to the mean (i.e., variance is low).  Since mining is essentially random, I guess the right mental model would be a renewal process -- almost Poisson, actually, but mining always gets more difficult over time.

Makes me think that the multi-hash-function algorithms popular in altcoins right now (X11, X13, etc.) are inherently more prone to forking, because of the extra among-hash-functions variance.  And, coins with random "superblocks" would be bad for the same reason.  Hmm.  I wonder if this is true empirically.

Not sure I understand why "superblocks" would cause any problem. These are the blocks with only payout difference, no hash algo diff. Can you explain some more?

I did not realize that superblocks are of the same difficulty as normal blocks.  If this is the case, then superblocks should be fine.

This conversation makes me think that a "crypto dictionary" would be very useful.  What are superblocks?  What is X11?  X13?  What algos are used, and are they selected randomly or deterministically?  It's hard to find clear definitions for anything (aside from the tech in Bitcoin itself).

Yes no diff change for superblocks. Superblocks are random blocks (depends on the hash) that will generate 10X or 100X even 1000X the normal payout. The algorithm usually use deterministic random number generation and the seed is based on some part of the hash.

[TPTB_need_war]

Satoshi did not solve the Byzantine Generals Problem.

[amaclin]

Satoshi did not solve the Byzantine Generals Problem.

The cost is too high.
It is economically unreasonable to solve 'Byzantine generals problem' if the cost of solution is higher than the cost of army/victory

[monsterer]

The cost is too high.
It is economically unreasonable to solve 'Byzantine generals problem' if the cost of solution is higher than the cost of army/victory

The cost of the solution is less than 51% of the total cost at all times.