Topic: DECENTRALIZED crypto currency (including Bitcoin) is a delusion (any solutions?) - page 56. (Read 91117 times)
January 11, 2016, 06:29:22 AM
@TPTB_need_war, what are the broad key features you're targeting in your new design?
January 10, 2016, 07:38:52 PM
My illness is flaring up, so I will need to hit the bed for now. Be back next day or when ever I feel okay.
January 10, 2016, 06:27:14 PM
January 10, 2016, 05:38:52 PM
Also, I haven't looked into how a QC would do this, but how would it get around the Bitcoin checkpoints? Surely it can only rewrite from the last checkpoint issued?
Yes, these checkpoints realize append-only subchain.
January 10, 2016, 05:25:29 PM
This is also the benefit of an append only ledger and an issue with POW.
Even a quantum computer cant rewrite history in a ledger that is append only.
Even a quantum computer cant rewrite history in a ledger that is append only.
I'm gonna go out on a limb here and state that having an append only ledger is impossible in trustless crypto.
January 10, 2016, 05:20:52 PM
The LCR insures no double-spend exist.
Once quantum computers hit the market everyone will be able to rewrite complete Bitcoin blockchain from the genesis. So I would add something to emphasize temporal nature of your statement.
This is also the benefit of an append only ledger and an issue with POW.
Even a quantum computer cant rewrite history in a ledger that is append only. Sure it might be able to disrupt future transactions if sufficient algorithms are not in place to account for quantum computing resources, but the fact still holds that the past data prior to any quantum influence is sound and can be trusted.
Also, I haven't looked into how a QC would do this, but how would it get around the Bitcoin checkpoints? Surely it can only rewrite from the last checkpoint issued?
January 10, 2016, 05:12:20 PM
Byzantine tolerance can not exceed 50% of failures.
Isn't it 33%?
You can achieve 50% in some circumstances by making sacrifices in the system.
If you have the inclination, I suspect readers would appreciate a layman's example.
Just punch "byzantine 2f+1" into Google
Plenty of papers on the subject, some sacrifice asynchronous comms, others adopt semi-trusted authorities etc etc
I didn't say it was pretty, or that it could be used here, but 2f+1 (or 50% near as damn it) is the best you can do.
January 10, 2016, 05:06:20 PM
Thank you for helping me remember all the thought process I went through and helping me to write it down. That should be very instructive to readers on how elusive flaws can be and why they should be very skeptical of claims of solving CAP without a LCR.
So now back to current and last attempt...searching for the flaw...
So now back to current and last attempt...searching for the flaw...
I can't remember if you're still holding the key details of this close to your chest? If you'd like help enumerating the potential problems, I'd be happy to assist
January 10, 2016, 05:02:47 PM
Thank you for helping me remember all the thought process I went through and helping me to write it down. That should be very instructive to readers on how elusive flaws can be and why they should be very skeptical of claims of solving CAP without a LCR.
So now back to current and last attempt...searching for the flaw...
So now back to current and last attempt...searching for the flaw...
January 10, 2016, 04:59:50 PM
We can't prove when those chains were created relative to each other. That was the point in my very first post on this.
Someone could 100 years later create a chain and claim it existed at the time and was part of the union.
The only proof we have for the union is what the chains record. This is the entire reason we need LCR.
You envision a union, but you have no way to prove what the union is. Propagation is not proof. I made this point several times now.
The flaws require very deep thinking.
Someone could 100 years later create a chain and claim it existed at the time and was part of the union.
The only proof we have for the union is what the chains record. This is the entire reason we need LCR.
You envision a union, but you have no way to prove what the union is. Propagation is not proof. I made this point several times now.
The flaws require very deep thinking.
Ahhhh, right of course - because the minority doesn't expend much energy by bundling the larger set of transactions, we have a sybil problem similar to long range attack in POS. And if they did expend energy linearly in the number of transactions they bundle, the majority always wins are we're back to the same old LCR.
edit: this is actually a really nice example of why you have to expend sufficient energy when you're creating blocks, and why POS is not tenable for a world currency.
January 10, 2016, 04:44:42 PM
But the flaw remains that there is no way to prove what the union is. At any given time the honest chain has all the transactions from the attackers chain plus censored transactions, but then the attackers chain releases a new block with more new transactions. How do we prove which was first? That is the entire point of a longest chain rule is we have no way to prove relative order otherwise. This is what I wrote several posts before. You will just chase your tail in circles. It violates CAP.
First doesn't matter. Cumulative POW matters - if the attacker extends his chain by another block, thereby increasing his weight, if he is still censoring transactions, the minority can easily extend their own chain by including all the transactions he has, plus the ones he leaves out?
We can't prove when those chains were created relative to each other. That was the point in my very first post on this.
Someone could 100 years later create a chain and claim it existed at the time and was part of the union.
The only proof we have for the union is what the chains record. This is the entire reason we need LCR.
You envision a union, but you have no way to prove what the union is. Propagation is not proof. I made this point several times now.
The flaws require very deep thinking.
Edit: this is example of what I mean by it is easy to be fooled into thinking one has a solution. So many times I thought I was close to a solution then banged my head against CAP over and over.
January 10, 2016, 04:32:52 PM
But the flaw remains that there is no way to prove what the union is. At any given time the honest chain has all the transactions from the attackers chain plus censored transactions, but then the attackers chain releases a new block with more new transactions. How do we prove which was first? That is the entire point of a longest chain rule is we have no way to prove relative order otherwise. This is what I wrote several posts before. You will just chase your tail in circles. It violates CAP.
First doesn't matter. Cumulative POW matters - if the attacker extends his chain by another block, thereby increasing his weight, if he is still censoring transactions, the minority can easily extend their own chain by including all the transactions he has, plus the ones he leaves out?
January 10, 2016, 04:29:18 PM
The LCR insures no double-spend exist. There is no fix for the idea of taking the conjunction of chains. The idea is flawed that is why I abandoned it. Also note I had added to my prior post.
That's why you'd need a new chain selection rule... what happens if you were to use to greatest set of all new transactions as the rule?
The greatest set of all new transactions would have the largest cumulative POW weight (in a system with a constant POW cost per transaction), such that any double spend by the attacker within this set would become the canonical spend, not the double spend.
Yes I remember now that was my next line of thinking too. If the rule is that the union is the canonical set, then the attacker's latter double-spend is the invalid transaction. Remember I wrote that in my vaporcoin thread last month.
But the flaw remains that there is no way to prove what the union is. At any given time the honest chain has all the transactions from the attackers chain plus censored transactions, but then the attackers chain releases a new block with more new transactions. How do we prove which was first? That is the entire point of a longest chain rule is we have no way to prove relative order otherwise. This is what I wrote several posts before. You will just chase your tail in circles. It violates the CAP theorem.
January 10, 2016, 04:21:11 PM
Your 4.3 section makes the point that the lower the difficulty, the lower the threat. Interesting. Thanks. Edit: I think I perhaps know how to incorporate this into my design...
That defense would already be in my design (before I even became aware of that in yours) because every transaction carries a PoW share, thus this share references a prior block hash. The cumulative difficulty could include all the shares.
January 10, 2016, 04:11:53 PM
It seems to me I derailed the convo. Continue, please, gentlemen.
Well kudos. You did demonstrate that the state might be able to win all block solutions due to building a very expensive computer, but which is (perhaps) exponentially less costly than building that many copies of mining equipment. Per the Berstein paper, apparently they can do it with parallel memory tables, no need to wait for a quantum computer (but I need to study that more closely).
And the defense is as in your Iota/Tangle paper to keep the difficulty of each confirmation step of the chain (each submitted PoW share) as low as possible to minimize the exponent of speedup.
January 10, 2016, 04:06:00 PM
It seems to me I derailed the convo. Continue, please, gentlemen.
January 10, 2016, 04:03:21 PM
However, I want to make you aware that quantum computers are unlikely to speed up anything[1] on a cost/performance basis.
Cost/performance is a good protection... until you meet an irrational attacker.
N(icholas) S(anta/atan) A(sshole)
January 10, 2016, 04:02:14 PM
However, I want to make you aware that quantum computers are unlikely to speed up anything[1] on a cost/performance basis.
Cost/performance is a good protection... until you meet an irrational attacker (e.g. the state).
January 10, 2016, 03:53:46 PM
That is still EXPTIME.
A single quantum computer working at speed of an average notebook would do mining like 21 billion notebooks. How is it EXPTIME?
Also:
And that doesn't speed up PoW, rather it speeds up finding a preimage.
#2 of http://bitcoin.stackexchange.com/a/10942
or
4.3 of http://188.138.57.93/tangle.pdf
I was stating there is a exponential speedup but the solution of a preimage is still EXPTIME (complexity) which means with say 256-bit hashes, then finding a preimage of a Lamport/Winternitz spend signature with Grover's algorithm is still intractable. Your SE link above makes me aware that Grover's can also be applied to finding PoW solutions with a relative exponential speedup, thus in that context you are correct PoW solutions are tractable with the speedup factor you provided. Thanks.
However, I want to make you aware that quantum computers are unlikely to speed up anything[1] on a cost/performance basis. Thus the threat appears to be very remote. The footnote below explains that when we can afford to build parallel memory tables to speed up operations as much as Grover's using classical computers, then we can afford to speed up using Grover's. Thus quantum computing may not really provide any breakthrough computational advantage.
Your 4.3 section makes the point that the lower the difficulty, the lower the threat. Interesting. Thanks. Edit: I think I perhaps know how to incorporate this into my design...
[1] http://cr.yp.to/hash/collisioncost-20090823.pdf
January 10, 2016, 03:38:10 PM
Please show me your calculation.
Current Bitcoin difficulty = 103880340815.
Difficulty of 1 requires 2^32 hashes.
Number of hashes for current difficulty = 103880340815 * 2^32 = 446162666497758986240.
A quantum computer needs only SQRT(446162666497758986240) = 21'122'562'971.8 hashes.
Jump to: