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

monsterer

legendary

Activity: 1008

Merit: 1007

Quote from: amaclin on February 28, 2016, 07:12:45 AM

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.

amaclin

legendary

Activity: 1260

Merit: 1019

Quote from: TPTB_need_war on February 28, 2016, 04:28:18 AM

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

TPTB_need_war

sr. member

Activity: 420

Merit: 262

Satoshi did not solve the Byzantine Generals Problem.

dreamhouse

hero member

Activity: 1073

Merit: 666

Quote from: tinybike on August 26, 2014, 05:15:51 PM

Quote from: dreamhouse on August 26, 2014, 12:39:40 AM

Quote from: tinybike on August 24, 2014, 11:41:01 PM

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

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.

tinybike

jr. member

Activity: 39

Merit: 13

Last of the freelance physicists

Quote from: dreamhouse on August 26, 2014, 12:39:40 AM

Quote from: tinybike on August 24, 2014, 11:41:01 PM

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

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

jonald_fyookball

legendary

Activity: 1302

Merit: 1008

Core dev leaves me neg feedback #abuse #political

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

dreamhouse

hero member

Activity: 1073

Merit: 666

Quote from: tinybike on August 24, 2014, 11:41:01 PM

Quote from: jl2012 on August 24, 2014, 09:46:58 PM

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 Cool

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?

jl2012

legendary

Activity: 1792

Merit: 1111

Quote from: tinybike on August 25, 2014, 03:05:24 AM

Quote from: jl2012 on August 25, 2014, 12:58:24 AM

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://bitcointalksearch.org/topic/decreasing-the-variance-of-block-interval-wo-decreasing-the-mean-of-interval-572816

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

tinybike

jr. member

Activity: 39

Merit: 13

Last of the freelance physicists

Quote from: jl2012 on August 25, 2014, 12:58:24 AM

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

legendary

Activity: 1792

Merit: 1111

Quote from: tinybike on August 24, 2014, 11:41:01 PM

Quote from: jl2012 on August 24, 2014, 09:46:58 PM

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 Cool

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

jr. member

Activity: 39

Merit: 13

Last of the freelance physicists

Quote from: jl2012 on August 24, 2014, 09:46:58 PM

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 Cool

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

legendary

Activity: 1792

Merit: 1111

Quote from: tinybike on August 24, 2014, 07:24:42 PM

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

jr. member

Activity: 39

Merit: 13

Last of the freelance physicists

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.

Topic: Does proof-of-work solve the Byzantine generals problem? (Read 2303 times)