Bitcoin Forum
December 09, 2021, 01:43:50 PM *
News: Latest Bitcoin Core release: 22.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 [3] 4 5 6 7 8 9 10 11 »  All
  Print  
Author Topic: Satoshi didn't solve the Byzantine generals problem  (Read 13519 times)
smooth
Legendary
*
Offline Offline

Activity: 2758
Merit: 1170



View Profile
February 07, 2016, 01:23:42 AM
 #41

<r0ach> you can't solve byzantine generals problem with a probabilistic model unless you've first solved sybil with a probabilistic model and Bitcoin doesn't do that
<r0ach> because there's no way of telling if all pools are owned by the same person, then it's not collusion or 51% attack, it's a sybil attack
<r0ach> since the essence of the byzantine generals problem is sybil attack, dealing with sybil comes first in the hierarchy before byzantine generals is discussed at all

I made this same point in either 2013 or 2014.

Afaics, the only solution is unprofitable PoW which is the design I am now pursuing.

Bitcoin solves the byzantine generals problem within the bounds of the assumptions in the model. If one entity controls a majority of hashing power, that is outside of the bounds.

Circular logic. Bitcoin didn't solve the Sybil attack problem when pools control 51% and no one can know whether they do and reroute their PoW shares.

The stated problem bounds do not include being able to tell whether someone controls >50% of the hash rate. That isn't in the paper at all. The wording of the paper is "As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network". It doesn't matter whether they cooperate via pools or otherwise, either way it is outside the bounds.

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1639057430
Hero Member
*
Offline Offline

Posts: 1639057430

View Profile Personal Message (Offline)

Ignore
1639057430
Reply with quote  #2

1639057430
Report to moderator
1639057430
Hero Member
*
Offline Offline

Posts: 1639057430

View Profile Personal Message (Offline)

Ignore
1639057430
Reply with quote  #2

1639057430
Report to moderator
1639057430
Hero Member
*
Offline Offline

Posts: 1639057430

View Profile Personal Message (Offline)

Ignore
1639057430
Reply with quote  #2

1639057430
Report to moderator
David Rabahy
Hero Member
*****
Offline Offline

Activity: 709
Merit: 500



View Profile
February 07, 2016, 03:25:26 AM
 #42

http://research.microsoft.com/en-us/um/people/lamport/pubs/reaching.pdf
http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 05:13:22 AM
 #43


First let us realize that the weaknesses of those approaches is they must use some centralization to prevent Sybil attacks:

Still another approach to consensus is Byzantine agreement [Pease et al. 1980; Lam-
port et al. 1982], the best known variant of which is PBFT [Castro and Liskov 1999].
Byzantine agreement ensures consensus despite arbitrary (including non-rational) be-
havior on the part of some fraction of participants. This approach has two appealing
properties. First, consensus can be fast and efficient. Second, trust is entirely decou-
pled from resource ownership, which makes it possible for a small non-profit to help
keep more powerful organizations, such as banks or CAs, honest. Complicating mat-
ters, however, all parties must agree on the the exact list of participants. Moreover,
attackers must be prevented from joining multiple times and exceeding the system’s
failure  tolerance,  a  so-called  Sybil  attack  [Douceur  2002].  BFT-CUP  [Alchieri  et  al.
2008] accommodates unknown participants, but still presupposes a Sybil-proof cen-
tralized admission-control mechanism.

Generally, membership in Byzantine agreement systems is set by a central authority
or closed negotiation. Prior attempts to decentralize admission have given up some of
the benefits.

The new Stellar SCP protocol/algorithm (above white paper) morphs the Sybil attack problem from one of divergence to one of perpetual preemption (unless of course centralization of trust is used by participants to thus remove the Sybil attack). It also provides asymptotic security that Satoshi's PoW doesn't have.

Note that Bitcoin does not have asymptotic security, meaning if ever someone with greater hashrate could come along in the future, they could rewrite the block chain. Iota has an interesting point about the insecurity of PoW hashes in the context of quantum computing. However, I argue that the community will enforce checkpoints, because our transaction history is valuable to us.



<r0ach> you can't solve byzantine generals problem with a probabilistic model unless you've first solved sybil with a probabilistic model and Bitcoin doesn't do that
<r0ach> because there's no way of telling if all pools are owned by the same person, then it's not collusion or 51% attack, it's a sybil attack
<r0ach> since the essence of the byzantine generals problem is sybil attack, dealing with sybil comes first in the hierarchy before byzantine generals is discussed at all

I made this same point in either 2013 or 2014.

Afaics, the only solution is unprofitable PoW which is the design I am now pursuing.

Bitcoin solves the byzantine generals problem within the bounds of the assumptions in the model. If one entity controls a majority of hashing power, that is outside of the bounds.

Circular logic. Bitcoin didn't solve the Sybil attack problem when pools control 51% and no one can know whether they do and reroute their PoW shares.

The stated problem bounds do not include being able to tell whether someone controls >50% of the hash rate. That isn't in the paper at all. The wording of the paper is "As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network". It doesn't matter whether they cooperate via pools or otherwise, either way it is outside the bounds.

Without considering the Sybil attack, then one isn't solving the Byzantine fault issue, i.e. isn't solving the Byzantine Generals problem (which is the correct title of this thread). Just because Satoshi failed to mention that he hadn't solved what he was implying to have solved, doesn't make that just having a majority of the hashrate is the only consideration in a PoW solution to the Byzantine Generals problem.

Even if we remove the economics which drives hashrate to concentrate into mining farms such as my suggestion to make mining unprofitable (and an ASIC resistant PoW protocol such as a memory hard hash would help improve the ratio of PoW shares from the marginal mines which are the payers required to make mining unprofitable for the lowest-cost miners which are the mining farms), we still have the problem that if payers are not full nodes and thus have to choose another server to do verification and select transactions for each block, the Sybil attack problem remains in that one can't know if many servers are owned/controlled by the same entity. And in fact, I have shown that verification MUST due to economics be centralized because those full nodes which have higher hashrate (even if hidden behind a Sybil attack from the public's perspective) thus earn more block reward and/or transaction fees per verification than those who control less hashrate, thus pools/full nodes are forced to be centralized (and hide it from the public with a Sybil attack because we all are delusional and expect Satoshi's design to remain decentralized when it can't).

But let's consider what damage the Sybil attack on full nodes can do, and how it can be detected and mitigated. In Satoshi's design, the Sybil attacking full node has lower costs for verification (and maybe can also potentially do a selfish mining attack but that isn't required to make my point) and thus will eventually drive the other full nodes bankrupt as a result. Thus Satoshi's design centralizes because of the inviolable and insoluble economic reality.

The other bad things centralization can do is censor some transactions and execute long-con double-spend attacks.

The solution is to centralize only the verification, but keep the control of the PoW computation decentralized, and make it such that the blame for censoring transactions and long-con double-spending is not ambiguous as it is in Satoshi's design.

That is exactly what my design accomplishes, while also enabling instant transactions that are sound. White paper and implementation forthcoming.

smooth
Legendary
*
Offline Offline

Activity: 2758
Merit: 1170



View Profile
February 07, 2016, 07:27:37 AM
 #44

Quote
The stated problem bounds do not include being able to tell whether someone controls >50% of the hash rate. That isn't in the paper at all. The wording of the paper is "As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network". It doesn't matter whether they cooperate via pools or otherwise, either way it is outside the bounds.

Without considering the Sybil attack, then one isn't solving the Byzantine fault issue, i.e. isn't solving the Byzantine Generals problem (which is the correct title of this thread). Just because Satoshi failed to mention that he hadn't solved what he was implying to have solved, doesn't make that just having a majority of the hashrate is the only consideration in a PoW solution to the Byzantine Generals problem.

There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

This does not mean that Bitcoin will be a great success and moon to $10 million/BTC, or even that it will survive at all more than another year or two, or anything in between. It is possible to conclude that the consensus algorithm does exactly what Satoshi said it does (putting aside possible selfish mining attacks), and still conclude that such a security margin is too weak to be useful, because of all of the ways the precondition itself can fail (pooling, of course, can contribute to some of them).


TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 09:17:35 AM
Last edit: February 07, 2016, 09:44:56 AM by TPTB_need_war
 #45

Quote
The stated problem bounds do not include being able to tell whether someone controls >50% of the hash rate. That isn't in the paper at all. The wording of the paper is "As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network". It doesn't matter whether they cooperate via pools or otherwise, either way it is outside the bounds.

Without considering the Sybil attack, then one isn't solving the Byzantine fault issue, i.e. isn't solving the Byzantine Generals problem (which is the correct title of this thread). Just because Satoshi failed to mention that he hadn't solved what he was implying to have solved, doesn't make that just having a majority of the hashrate is the only consideration in a PoW solution to the Byzantine Generals problem.

There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

The Byzantine Generals problem does not state "A majority of CPU power" as the problem. I already stated that is Satoshi's requirement but as the correct title of this thread points out, Satoshi's stated requirement is not a solution to the Byzantine Generals problem. Period.

One of the attack vectors in solving the Byzantine Generals is the Sybil attack. The Byzantine Generals problem is all about the need to trust that 2/3 of the generals are loyal without centralization where all generals are the same person, i.e. that there is no Sybil attack.

Anyone who has studied all the variants of consensus algorithms (as I have) will know clearly that Sybil attacks are always resolved via centralization of the protocol.

This is why as I looked for an improvement over all of what has already been tried, I was cognizant of that I would need to accept centralization in some aspect and so I began to look for the possibility of controlling centralization with decentralization, i.e. a separation of orthogonal concerns which is often how paradigm shifts arise to  solve intractable design challenges.

Every consensus design creates centralization. This will always be unavoidable due to the CAP theorem. The key in my mind is to select carefully where that centralization should be.

  • Satoshi's PoW consensus design centralizes because a) SHA256 has orders-of-magnitude lower electrical cost on ASICs, b) full nodes must centralize (maximize pooled hashrate) to win the battle over who will have the most profitable verification costs (which can be accomplished with a Sybil attack), and c) variance of block rewards require maximizing pooled hashrate (at least up to double-digit percentages and Sybil attack incentives kick in from there).
  • Stellar's SCP consensus design centralizes because although it can't diverge, it requires that slices are not Sybil attacked to avoid eternal preemption (being jammed stuck forever).
  • Ripple's consensus algorithm diverges unless it is centralized trust, as confirmed by Stellar's divergence before it switched to the SCP algorithm.
  • Iota's (any DAG's) consensus diverges unless centralization can force the mathematical model that payers and recipients encode in their interaction with the system.
  • Ethereum never solved the issue that verification of long running scripts can't be decentralized. They are now off another deadend tangent (consensus-by-betting, Casper, shards) trying to deny the CAP theorem.
  • PoS is centralization.

Extracting the generative essence of an issue is what I do. That is where I have made my career in the past and will do so again.

monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
February 07, 2016, 10:33:32 AM
 #46

Bitcoin solves the byzantine generals problem within the bounds of the assumptions in the model. If one entity controls a majority of hashing power, that is outside of the bounds.

Circular logic. Bitcoin didn't solve the Sybil attack problem when pools control 51% and no one can know whether they do and reroute their PoW shares.

I've been guilty of making this same mistake myself in the past, but byzantine faulty nodes can be colluding (or sybil), so the failure tolerance of 51% includes sybil nodes.
smooth
Legendary
*
Offline Offline

Activity: 2758
Merit: 1170



View Profile
February 07, 2016, 10:43:18 AM
Last edit: February 07, 2016, 10:56:37 AM by smooth
 #47

Quote
The stated problem bounds do not include being able to tell whether someone controls >50% of the hash rate. That isn't in the paper at all. The wording of the paper is "As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network". It doesn't matter whether they cooperate via pools or otherwise, either way it is outside the bounds.

Without considering the Sybil attack, then one isn't solving the Byzantine fault issue, i.e. isn't solving the Byzantine Generals problem (which is the correct title of this thread). Just because Satoshi failed to mention that he hadn't solved what he was implying to have solved, doesn't make that just having a majority of the hashrate is the only consideration in a PoW solution to the Byzantine Generals problem.

There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

The Byzantine Generals problem does not state "A majority of CPU power" as the problem. I already stated that is Satoshi's requirement but as the correct title of this thread points out, Satoshi's stated requirement is not a solution to the Byzantine Generals problem. Period.

Okay, but so what?

Bitcoin also didn't solve P ?= NP or any number of other problems.

And unless I'm mistaken, Satoshi did not say that it did solve the Byzantine Generals problem, especially in the specific manner that problem is formulated (with discrete General-actors, something that doesn't even exist in Bitcoin at all). At best there is a rough similarity. Correction: Satoshi did say it was a solution in this email. But again, he formulated in a very careful manner, stating that each general has a laptop, which ends up making "majority of CPU power" equivalent to a majority of discrete General-actors.

He said exactly what it does solve. If a majority of the CPU power is not conspiring to attack the network, then it reaches consensus that is final and secure (though slowly in the case close to 50%).

It is up you as a prospective user or investor to decide whether "a majority of the CPU power" is an acceptable requirement. It seems at this point there isn't anything better, and some number of people think it is useful (most of the world does not).
monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
February 07, 2016, 11:16:31 AM
 #48

And unless I'm mistaken, Satoshi did not say that it did solve the Byzantine Generals problem, especially in the specific manner that problem is formulated (with discrete General-actors, something that doesn't even exist in Bitcoin at all). At best there is a rough similarity. Correction: Satoshi did say it was a solution in this email. But again, he formulated in a very careful manner, stating that each general has a laptop, which ends up making "majority of CPU power" equivalent to a majority of discrete General-actors.

He may not have said it in the bitcoin paper, but others have proved it:
http://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf
enet
Member
**
Offline Offline

Activity: 81
Merit: 10


View Profile
February 07, 2016, 12:53:15 PM
Last edit: February 07, 2016, 01:13:37 PM by enet
 #49

Yes, Bitcoin solves BGP (in some way). It solves also a bunch of other completely unknown problems:

* how to prove some information existed at a certain time
* how to create a public ledger of ownership
* how to issue a currency without requiring a nation state army to enforce scarcity
* how to reach agreement over a communications channel on value

BGP is a term Lamport came up with, to describe a certain theoretical model.

Quote
He may not have said it in the bitcoin paper, but others have proved it:
http://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf

Okay paper, but I wish they would have referenced Lamport and more relevant work on quorum systems. Bitcoin implements Lamport's partial order of events for the first time, yet its not described here.

Quote
There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

True, but there are other "attacks". Such as calling up Chinese miners and convince them to do a certain thing. The smaller that number and the more closer related, the worse the situation. I believe the best thing to do is to recognize the genius of this invention, but then think about how to do something better on that basis. One of the biggest problems is the complexity of the system, i.e. the large technical debt. E.g. last year there has been 1B$ investment in this area, and there been almost no progress at all in terms of advanced applications (just an increase in noise levels). I think the possibilities are largely not explored. Mostly because the Bitcoin system is extremely complex and actually not that versatile compared to what might be possible. Most discussions take many design aspects for granted, when they might be a hinderance. The PoS systems have been very helpful thinking about these things in different ways. Many also don't know the pre Bitcoin designs, Bitgold and b-money, which are also helpful to consider, see http://www.weidai.com/bmoney.txt and https://en.bitcoin.it/wiki/Bit_Gold_proposal . Actually quite surprising since satoshi said Bitcoin is an implementation of those ideas:

Quote from satoshi:
Quote
Bitcoin is an implementation of Wei Dai's b-money proposal http://weidai.com/bmoney.txt on Cypherpunks http://en.wikipedia.org/wiki/Cypherpunks in 1998 and Nick Szabo's Bitgold proposal http://unenumerated.blogspot.com/2005/12/bit-gold.html

https://bitcointalk.org/index.php?topic=342.msg4508#msg4508

See also:
https://bitcointalk.org/index.php?topic=583.msg11405#msg11405
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 03:27:19 PM
Last edit: February 07, 2016, 03:48:56 PM by TPTB_need_war
 #50

...and another incentive structure must be developed to encourage decentralized p2p mining.

Switching to an ASIC resistant PoW coin doesn't solve this problem but merely delays the inevitable. As interest and hash power grows ASICS will be developed within time regardless.

I believe it is possible to design a memory hard PoW that is not electrically more efficient on an ASIC, but it will be very slow. I originally didn't think so, but have since realized I had a mistake in my 2013/4 research on memory hard hashes. It is possible that Cuckoo Hash already achieves this, but it is more difficult to be certain and it is very slow when DRAM economics are maximized (although it adds asymmetric validation which is important for DDoS rejection if the transaction signatures are ECC and not Winternitz and for verification when PoW share difficulty can't be high because each PoW trial is so slow).

Cryptonote's memory hard hash can't possibly be ASIC resistant, because by my computation it could not possibly have 100 hashes/second on Intel CPUs and be ASIC resistant.

See also Zcash's analysis thus far.

Correction follows.

It will be impossible to design a memory hard PoW that is not electrically more efficient on an ASIC, unless the hash function employed (for randomizing the read/writes over the memory space) is insignificant w.r.t. the RAM power consumption, which is probably not going to be the case in any design where that hash function has sufficient diffusion to be secure.

The only way to make an ASIC resistant PoW is for the proving computation to be memory latency bound, because DRAM latency can't be improved much in general (whereas hardwired arithmetic computation and memory bandwidth can be accelerated with custom hardware):

http://community.cadence.com/cadence_blogs_8/b/ii/archive/2011/11/17/arm-techcon-paper-why-dram-latency-is-getting-worse
http://www.chipestimate.com/techtalk.php?d=2011-11-22

However, what a GPU (which starts with 4 - 10X worse main memory latency than CPUs) and especially an ASIC will do to get better DRAM amortization (if not also lower electricity consumption due to less latency) is run dozens or hundreds of instances of the proving algorithm with the memory spaces interleaved such that the latencies are combined and amortized over all instances, so that the effective latency drops (because reading from the same memory bank of DRAM is latency free if multiple accesses within the same bank are combined into the same transaction). This can even be done in software as interleaved memory spaces without needing a custom memory controller. More exotic optimizations might have custom memory controllers and larger memory banks (note I am not expert on this hardware issue). This is probably why Cryptonote includes also AES-NI instructions because GPUs have only at best at parity in performance per watt on AES, but that won't be enough to stop ASICs.

However that optimization for ASICs will bump into memory bandwidth limit so the amortization will have a limit. Theoretically memory bandwidth can be increased with duplicated memory banks for reads but not for writes!

Using larger memory spaces in a properly designed memory hard PoW hash function (not Scrypt) can decrease the probability of that instances will hit the same memory bank within a sufficiently small window of time necessary to reduce the latency. Also using wider hash functions (e.g. my Shazam at 2048 to 4096-bits) reduces the number of instances that can be interleaved in the same memory bank (and standard DRAM I think has bank/page size of 4KB?). The ASIC can respond by designing custom DRAM with larger memory banks and run more instances, but that not only raises the investment required but the memory bandwidth limit for writes seems to be an insurmountable upper bound.

So although I think a memory hard PoW hash can be made which is more ASIC resistant than current ones, I think it will be impossible to sustain parity in hashes/Watt and hashes/$hardware. Perhaps the best will be within 1 to 2 orders-of-magnitude on those.

So all profitably mined PoW coins (with sufficient market caps) are destined to be centralized into ASIC mining farms running on cheap or free electricity, but the scale and rate at which this happens can be drastically improved over SHA256 (Bitcoin, etc).

My design of unprofitably mined PoW will only require that the difficulty from the PoW shares sent with transactions is sufficient to making ASIC mining unprofitable for the level of block reward offered. Keeping the CPU implementation of the PoW prover within 1 to 2 orders-of-magnitude of an ASIC implementation reduces the level of such aforementioned difficulty needed.

I hope I didn't make another error in this corrected statement. It is late and I am rushing.

TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 03:59:44 PM
Last edit: February 07, 2016, 04:39:31 PM by TPTB_need_war
 #51

Yes, Bitcoin solves BGP (in some way). It solves also a bunch of other completely unknown problems:

* how to prove some information existed at a certain time

Incorrect. It only proves some information existed at a certain block. There is no way to put[objectively prove] a clock time in the block chain.

* how to create a public ledger of ownership

Incorrect. A longest-chain-rule (LCR) block chain records non-conflicting state transformations. That isn't limited to a ledger of ownership.

* how to issue a currency without requiring a nation state army to enforce scarcity

Incorrect. A block chain can distribute tokens. That doesn't guarantee anything about it becoming a currency and being immune to nation state armies. If not immune (i.e. not defensible against), then 'without' is incorrect. (it doesn't even guarantee the distribution won't be centralized by mining farms)

* how to reach agreement over a communications channel on value

Again you are pigeon-holing what a block chain does. Again a longest-chain-rule (LCR) block chain records non-conflicting state transformations.

E.g. last year there has been 1B$ investment in this area, and there been almost no progress at all in terms of advanced applications (just an increase in noise levels).

Thanks for ignoring my progress and thereby insinuating my sharing/progress has been noise.

I think the possibilities are largely not explored.

I appear to be reasonably skilled at distilling to the generative essence and I will assert that there isn't a large space of possible designs that will work to eliminate the centralization issue. Mine seems to be the only possible one.

Many also don't know the pre Bitcoin designs, Bitgold and b-money, which are also helpful to consider, see http://www.weidai.com/bmoney.txt and https://en.bitcoin.it/wiki/Bit_Gold_proposal . Actually quite surprising since satoshi said Bitcoin is an implementation of those ideas:

Quote from satoshi:
Quote
Bitcoin is an implementation of Wei Dai's b-money proposal http://weidai.com/bmoney.txt on Cypherpunks http://en.wikipedia.org/wiki/Cypherpunks in 1998 and Nick Szabo's Bitgold proposal http://unenumerated.blogspot.com/2005/12/bit-gold.html

https://bitcointalk.org/index.php?topic=342.msg4508#msg4508

See also:
https://bitcointalk.org/index.php?topic=583.msg11405#msg11405

Now that is noise or at least veering very far from a solution to the problem this thread raises.

enet
Member
**
Offline Offline

Activity: 81
Merit: 10


View Profile
February 07, 2016, 04:06:40 PM
Last edit: February 07, 2016, 04:40:59 PM by enet
 #52

TPTB, your style is not productive. I'm putting you on ignore, since you seem to have no intention in engaging in meaningful dialogue.

To answer this:

"Incorrect. It only proves some information existed at a certain block. There is no way to put a clock time in the block chain."

Blocks are of course timestamped with actual UTC timestamp from the node that generates it, and then validated by other nodes. Below is the code in the 0.0.1 version. The timestamp mechanism is the entire point of adjusting difficulty through time. Otherwise the PoW would be worthless. For more accuracy atomic clocks via NTP could be used. Without the timestamp nothing in Bitcoin works (that's the double-spend problem).

See also: http://szabo.best.vwh.net/distributed.html#Secure Time-stamping,
http://szabo.best.vwh.net/distributed.html#The Byzantine Generals Problem
http://web.archive.org/web/20090309175840/http://www.bitcoin.org/byzantine.html

where all this is explained in relation to BGP (more accurate would be the term logical broadcast).

Quote
The simple protocol of the bell tower, which broadcast to every resident of a medieval town the same time, can now be implemented on a network -- either through logical broadcast on the Internet or physical broadcast with radio. For the first time we can implement on the Internet the integrity properties on which civilization depends -- including synchronized clocks, unforgeable transactions, and censorship-proof publishing. Where today's Internet, lacking this technology, fails to provide many of these properties, we now know how to provide them with a greater degree of integrity and availability than either the Internet or any previous media was capable of.


https://github.com/benjyz/bitcoinArchive/blob/eabf96b83e7608bff0149dc1fbaee1dd844429c8/bitcoin0.1/src/main.cpp#L1163

Code:
   // Check timestamp
    if (nTime > GetAdjustedTime() + 2 * 60 * 60)
        return error("CheckBlock() : block timestamp too far in the future");

https://github.com/benjyz/bitcoinArchive/blob/eabf96b83e7608bff0149dc1fbaee1dd844429c8/bitcoin0.1/src/util.cpp#L320

Code:
//
// "Never go to sea with two chronometers; take one or three."
// Our three chronometers are:
//  - System clock
//  - Median of other server's clocks
//  - NTP servers
//
// note: NTP isn't implemented yet, so until then we just use the median
//  of other nodes clocks to correct ours.
//
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 04:16:19 PM
Last edit: February 07, 2016, 04:37:21 PM by TPTB_need_war
 #53

"Incorrect. It only proves some information existed at a certain block. There is no way to put a clock time in the block chain."

It seems you really haven't understood the most basic things. Blocks are of course timestamped with actual UTC timestamp from the node that generates it.

You do not understand basic issues.

A 51% attacker can put any time he wants in the block chain.

Honest nodes can sync to a global clock, but this is not guaranteed to be accurate unless an offline node can later prove that the chain was not generated by a 51% attack on the clock records. And of course there is no objective way to prove this, other than trusting the community. And so then you lose the objective, trustless quality.

This is fundamental and if you don't understand this, then you are not qualified as a block chain expert. Block chains are only objective relative to blocks. Period.

Sorry you lose again. And I know damn well the underhanded methods you are employing to try to discredit me and sorry you will lose.

TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 05:48:17 PM
 #54

Yes, Bitcoin solves BGP (in some way)...

Quote
There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

True, but there are other "attacks". Such as calling up Chinese miners and convince them to do a certain thing.

Incorrect again.

BGP is not solved if there is Sybil attack vulnerability. The following is not "other attack" but rather it is a Byzantine fault (because the loyal participants can't be certain of Consistency by keeping the control of the hashrate below 51%). Since you have no way to know which pools are controlled by the same entity and thus which pools have the lowest VERIFICATION costs per block reward (which is very important once you scale Bitcoin to Visa scale), then you have no way to know where to send your PoW shares so as to prevent that Sybil attacker from leeching off of the other pools and driving them bankrupt thus centralizing all pools under one control but hidden by a Sybil attack. In other words, the system is GUARANTEED to become 51% attacked due to the economics and the fact that control can be hidden behind a Sybil attack.

I wrote that already upthread and you just don't read apparently.

monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
February 07, 2016, 05:52:44 PM
 #55

BGP is not solved if there is Sybil attack vulnerability.

In bitcoin, BGP is solved to within the stated tolerance of 51% byzantine faulty nodes.
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 06:03:53 PM
 #56

BGP is not solved if there is Sybil attack vulnerability.

In bitcoin, BGP is solved to within the stated tolerance of 51% byzantine faulty nodes.

Satoshi's PoW does not distinguish between faulty and non-faulty nodes.

The following is not "other attack" but rather it is a Byzantine fault (because the loyal participants can't be certain of Consistency by keeping the control of the hashrate below 51%).

There is no way to distinguish a 51% attack from a non-attack, e.g. for example censoring transactions, in a way that is provable with block chain data (i.e. to an offline node that comes online). One of the key innovations in my design, is it is possible for a payer to send his PoW share away from a "pool" (not example the same as pool in Bitcoin) that is provably (from that payer's individual perspective) responsible for censoring the transaction.

Since nothing about faults is provable from the block chain, then there is no provable Consistency (w.r.t. to what loyal nodes would consider a fault, e.g. censoring txns) and thus the BGP has not been solved.

We use community monitoring to estimate that we have Consistency, but this can't be proven objectively just from the block chain. We must correlate user experiences and other data points such as pool concentration.

A Sybil attack against the means by which loyal participants determine whether 51% control has been perhaps ceded to pools removes one of the key data points.

So we can conclude Bitcoin didn't solve BGP because there is no block chain objectivity about faults. And then we can say that Sybil attacks on pools destroy one of our subjective metrics for community appraisal of Consistency.

TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 06:18:33 PM
 #57

Quote
The stated problem bounds do not include being able to tell whether someone controls >50% of the hash rate. That isn't in the paper at all. The wording of the paper is "As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network". It doesn't matter whether they cooperate via pools or otherwise, either way it is outside the bounds.

Without considering the Sybil attack, then one isn't solving the Byzantine fault issue, i.e. isn't solving the Byzantine Generals problem (which is the correct title of this thread). Just because Satoshi failed to mention that he hadn't solved what he was implying to have solved, doesn't make that just having a majority of the hashrate is the only consideration in a PoW solution to the Byzantine Generals problem.

There is no Sybil attack possible on the problem as stated. "A majority of CPU power" is a physical quantity which can't be Sybil attacked. Period.

The Byzantine Generals problem does not state "A majority of CPU power" as the problem. I already stated that is Satoshi's requirement but as the correct title of this thread points out, Satoshi's stated requirement is not a solution to the Byzantine Generals problem. Period.

Okay, but so what?

Bitcoin also didn't solve P ?= NP or any number of other problems.

And unless I'm mistaken, Satoshi did not say that it did solve the Byzantine Generals problem, especially in the specific manner that problem is formulated (with discrete General-actors, something that doesn't even exist in Bitcoin at all). At best there is a rough similarity. Correction: Satoshi did say it was a solution in this email. But again, he formulated in a very careful manner, stating that each general has a laptop, which ends up making "majority of CPU power" equivalent to a majority of discrete General-actors.

He said exactly what it does solve. If a majority of the CPU power is not conspiring to attack the network, then it reaches consensus that is final and secure (though slowly in the case close to 50%).

It is up you as a prospective user or investor to decide whether "a majority of the CPU power" is an acceptable requirement. It seems at this point there isn't anything better, and some number of people think it is useful (most of the world does not).

Because as I explained to monsterer in the prior post, Satoshi's design is ambiguous about Byzantine faults such as censoring transactions and thus it does not solve the BGP.

And because I assert there are other ways to organize a PoW block chain design so that some of those faults can be objectively identified and reacted to (e.g. the fault of censoring transactions). The fact that in Satoshi's design these faults can't even be objectively identified (and the Sybil attack on pools is another one that destroys any objectivity), then there is no recourse other than for the system to centralize and fail. Pool centralization is increasing despite the move away from pools that had too much hashrate (and the linked data doesn't even account for the Sybil attack we can't see).

monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
February 07, 2016, 06:23:20 PM
 #58

Satoshi's PoW does not distinguish between faulty and non-faulty nodes.

In bitcoin, faulty nodes = sybil nodes.

A byzantine fault in bitcoin is a fork.

Quote
So we can conclude Bitcoin didn't solve BGP because there is no block chain objectivity about faults. And then we can say that Sybil attacks on pools destroy one of our subjective metrics for community appraisal of Consistency.

A poor conclusion. LCR provides the objectivity; branches which get orphaned were objectively selected against as being byzantine faulty.
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 06:44:52 PM
 #59

Satoshi's PoW does not distinguish between faulty and non-faulty nodes.

In bitcoin, faulty nodes = sybil nodes.

A byzantine fault in bitcoin is a fork.

Quote
So we can conclude Bitcoin didn't solve BGP because there is no block chain objectivity about faults. And then we can say that Sybil attacks on pools destroy one of our subjective metrics for community appraisal of Consistency.

A poor conclusion. LCR provides the objectivity; branches which get orphaned were objectively selected against as being byzantine faulty.

So if the LCR is creating censored transactions is that not a fault/failure? What the hell use of Byzantine fault tolerance if it doesn't guarantee a system that can be used by the participants?

The following practical, concise definitions are helpful in understanding Byzantine fault tolerance:[3][4]

Byzantine fault
    Any fault presenting different symptoms to different observers
Byzantine failure
    The loss of a system service due to a Byzantine fault in systems that require consensus

Loss of Access is a failure. CAP theorem applies.

TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
February 07, 2016, 06:50:44 PM
 #60

Go ahead. Find a way to put me down. I dare you all!

Fuck I am tired of this forum.

Pages: « 1 2 [3] 4 5 6 7 8 9 10 11 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!