The miners can vote on whether they wish to change a protocol rule, as was the case with BIP16 (P2SH) in Bitcoin.
But do you hold the vote before or after the ASIC is deployed in significant quantity?  Before, maybe non-mining users can also vote via some sort of a fee, though this can be messy... BTW, I'll believe that ASICs that use 128.5kbytes (or less with TMTO) per scrypt() invocation exist only after I see any, the production cost of such an ASIC should be much higher than SHA256 ASIC. Maybe some Bitcoin ASIC manufacturer like Avalon can estimate for us how costly it is to manufacture scrypt ASIC ? |
|
|
|
Anyway, I believe it's morally wrong to change the POW 2+ years after launching a coin, if you did not at least mention that possibility when creating it.
coblee has initiated a public discussion on changing the scrypt params, a few months after Litecoin was launched ( link). |
|
|
|
Nobody wants to invest in something if the rules are just going to be changed later.
The miners can vote on whether they wish to change a protocol rule, as was the case with BIP16 (P2SH) in Bitcoin. |
|
|
|
As far as a PoW that will be more ASIC resistant. What about Momentum PoW.. what Protoshares is using: http://invictus-innovations.com/s/MomentumProofOfWork.pdfEDIT: After thinking about if for a bit, the Momentum PoW would not work as it would effectively cut out current GPU miners. Any change of the PoW must allow everyone that is already participating in mining Litecoin to continue to do so. Don't believe everything you read. These protoshare guys apparently have never heard of cycle detection algorithms (like Pollard's rho) that find collisions while avoiding the space complexity blowup, their whitepaper is nonsense. |
|
|
|
Nothing is ASIC proof,
A point I've argued many times. But in hindsight I was somewhat wrong. No finite collection of fixed algorithms (Even a large set) can be ASIC proof (in fact, large sets probably just lead to ASIC monopolies due to higher NRE). But if you change the POW periodically in ways which aren't predicable months in advance, and in ways that can't just be generalized with anything more specialized than general purpose consumer hardware... then I do think you would actually have achieved a fairly high degree of asic-proof-ness. There is just the question of the costs of periodic changes being worth the benefits, and what cadence is required to make investment unwise. Hmm continuously select the params of the PoW hash function deterministically according to pseudorandom bits of future blocks? Interesting idea... Edit: I think that maybe the idea is that if ASIC miners have a large fraction of the current hashpower, and they try to control the pseudorandom bits that will decide the next PoW params, then they will have a disadvantage in the competition against other miners because they'll have to re-solve blocks multiple times until they get params that they prefer? |
|
|
|
tacotime and myself did a few benchmarks with tweaked scrypt params: https://bitcointalk.org/index.php?topic=122256.msg1316383#msg1316383The creator of scrypt has said that the he thinks that scrypt params of Litecoin don't use enough memory ( link), probably before he fully considered the tradeoffs between cost-effectiveness of ASIC and verification/propagation of blocks by Litecoin (non-mining) nodes. He later said that for the Litecoin scrypt params may be good, estimating that still would 10x advantage over SHA256 in terms of the cost-effectiveness of ASIC vs genereal-purpose hardware like GPUs ( link). gmaxwell: regarding whether it will be too late to change the PoW hash function, as you've said in the past, miners exist at the pleasure of the users ( link). To take an extreme scenario, this should supposedly/hopefully mean that if say 90% of the mining power (i.e. ASIC miners) and 10% of the users decide to follow certain protocol rules while 10% of the mining power (i.e. non-ASIC miners) and 90% of the users decide to follow different protocol rules, then the fork with 90% of the users should win. But such scenarios are vague and no one can predict the future, Bitcoin could also have such conflicts with ASIC owners who e.g. wish to change the block size limit to gain higher fees, or other scenarios that we can try to come up with... I think that doing more scrypt benchmarks with the purpose of trying to see which scrypt params give the best tradeoffs is a good idea, coblee & warren what do you think? gmaxwell, do you an educated guess regarding which scrypt params should offer the best tradeoff between making ASIC less cost-effective and fast enough validation/propagation of blocks by regular nodes? |
|
|
|
You might be interested in my take on the issue (quite different from a computer science perspective). For me the crux of the matter is that miners own ASICs. ASICs are an illiquid asset, so miners care about what happens to their market value. This implies that the static game framework is completely inappropriate for analyzing this problem. The game is repeated. Here is my analysis: http://www.scribd.com/doc/182399858/Cunicula-s-game-theory-primer-pdfI haven't read your analysis yet, but I wanted to mention that there exist ASIC-resistant hash functions that cryptocurrencies can utilize for PoW (which would imply that the mining hardware does have resale value). So if your analysis is 100% correct, it will indeed apply to Bitcoin, but not to cryptocurrencies in general. Therefore Lear's academic paper can still have merit. |
|
|
|
I can confirm that Lear has discussed with me the results of his research a day before the paper by Eyal and Sirer was published.
I can also confirm that Lear has discussed with me these observations (with elaborate details) and his upcoming academic paper on this topic, about two weeks before the paper by Eyal and Sirer was made public. BTW, the word "published" is a little confusing in this context, it's more clear to say that it's "self-published" for now. Maybe their publicity stunts (like that "Bitcoin is broken" blog post) will interfere with the supposedly anonymous review process for publication, though I doubt that it would. |
|
|
|
|
I bought 3 shirts and received the (ground) shipment after 2 weeks.
Cool shirts, I recommend...
|
|
|
|
Anyway, IMHO, Namecoin, while perhaps not perfect, has been running for a couple of years, already has a large community (relatively speaking) involved in it, and, for these reasons, is the best shot we have at a decentralized DNS. This bug is critical but fixable from what I've gathered.
If Namecoin is the best shot we have at a decentralized DNS then that's bad news, because the Namecoin protocol wasn't well thought through and therefore it doesn't really enable a decentralized DNS, see here: https://bitcointalk.org/index.php?topic=233997.msg2534114#msg2534114https://en.bitcoin.it/wiki/User:Gmaxwell/namecoin_that_sucks_less |
|
|
|
But that sounds fragile per my comment above: what if the user is using deterministic wallet, and/or does reuse keys. Many users do reuse keys as a matter of practice - eg tipjar addresses, static published addresses, vanity addresses etc. Does that mean that step 8 allows an hostile gambler to use Bob as a blind signature oracle, where he'll sign anything at all?
Well, even if the user does reuse keys in general, he will be safe if for each coin toss session he will generate a fresh key for the refund transaction, because the attacker could only ask him to do a blind signature with this fresh key. |
|
|
|
If TxA' gets mined instead of TxA then TxB will be invalid and so no refund exists.
In the protocol here, you could refuse to reveal until TxA is confirmed. But if Bob broadcasts TxA without a refund already existing, Alice can just walk away and leave bob stuck at that point. "HaHa"
BTW, practically speaking, how easy is it to pull off this attack in the current state of the Bitcoin network? The attacker cannot change the fees in the transaction that he mutates, so he could make a separate transaction that pays the miners to replace TxA with TxA' in their memory pool, but there would be nothing that binds this separate transaction to TxA', i.e. the miners could just grab the payment that was given to them in the separate transaction and ignore TxA' ? If the attackers doesn't try to bribe the miners, and instead simply tries to to broadcast TxA' after TxA was broadcasted and thus revealed, what'd be his chances to win the race? There's that IEEE paper that claimed that the average propagation time in Bitcoin is about 12 seconds, so this attack can be practical? |
|
|
|
No Bob should broadcast his bet transaction before asking alice to do anything (other than provide A2=SHA1(A1) without disclosing A1.)
The locktime support in Bitcoin is quite basic, please read Greg Maxwell's explanation on how it works: https://bitcointalk.org/index.php?topic=193281.msg2060451#msg2060451The technical specification is at: https://en.bitcoin.it/wiki/Protocol_specification#txAnd then please review my description of your improved protocol again, to see if there are any mistakes. It works with Bitcoin as it is now, but whitelisting OP_XOR would make it a little more efficient.
Unless you have OP_BOOLXOR (logical xor ^^ in C syntax, which C lacks) I dont think it helps as you can do i with != (aka OP_NUMNOTEQUAL) if you anyway have to check a+b<=2. I meant OP_XOR to get the result of the bet in the MSB, and then use OP_GREATERTHAN to compare with a constant (mentioned in post #13 here). |
|
|
|
Before the escrow payment confirms, however, Alice announces a mutant version of TxA, TxA' which is TxA but it has the S value in the ECDSA signature replaced by S - secp256k1_order (or one of the many other permissible mutations). This changes the TXID. Alice may also have some helpful miners that have agreed to mine the mutant, though this isn't essential.
I see, so I guess that the problem here is that the blockchain rule doesn't force S to be a value between 1 and secp256k1_order-1  If TxA' gets mined instead of TxA then TxB will be invalid and so no refund exists.
In the protocol here, you could refuse to reveal until TxA is confirmed. But if Bob broadcasts TxA without a refund already existing, Alice can just walk away and leave bob stuck at that point. "HaHa"
Right, I see. Bob already signed the transaction and if Alice can mutate it and thereby invalidate the refund then she can easily extort Bob, because the transaction locked coins that belonged only to Bob, and now without the key that Alice holds it's impossible to redeem these coins. |
|
|
|
4. Bob creates a "bet" transaction that takes as input 2X of his own coins, and can be spent by: [Alice's signature + Bob's signature] OR [SHA256(A)==A2 AND SHA256(B)==B2 AND (((A xor B) mod 2 == 0, and Alice's signature) OR ((A xor B) mod 2 == 1, and Bob's signature)))]
5. Bob asks Alice to signs a "refund_bet" transaction which spends his 2X coins to an address that he controls, and has locktime of (say) 20 blocks into the future.
Unfortunately no protocol which requires a blind refund transaction can be completely secure in the Bitcoin network as it exists today. (The reason may be obvious to you if you think about it for a bit. I'll gladly describe it, however, if no one else is aware of anyone currently using blind refund transactions right now.) Not sure if you mean something else than the danger of tricking the user to blindly sign a transaction that spends some other output that he controls instead of the supposed refund transaction. We have discussed it on IRC once ( link), where you explained that there's no danger if the user never re-uses the same pubkey more than once, if I understand correctly what you said is true because the attacker couldn't specify the user's pubkey in the transaction that spends the output (though the attacker could extract the pubkey from the signature afterwards, so if he could convince the user to sign again then the attack will succeed, assuming that they user had an output that's controlled by the same ECDSA key as the key that he used for the refund transaction). But are you referring to a different danger here? Anyway, for the fair coin toss protocol, it's fine to have non-blind refunds, i.e. in step (5) Bob will send Alice the entire "bet" transaction, and Alice will create the "refund_bet" transaction on her own, sign it, and send it back to Bob. |
|
|
|
One very tiny request - could you please use regular script form instead of inventing new notations for transactions? I found the non-words version of Adam's protocol a little hard to decipher. In my experience formal notation obfuscates as often as it enlightens.
I'll attempt to fully describe Adam's protocol here. Please see if the language that I use is clear enough, and whether you agree that the risks of double-spending are pinpointed correctly (in step 8 and step 10). 1. Alice and Bob wish to do a fair coin toss where each of them inputs X coins and the winner gets the 2X coins. 2. Alice picks some random secret A1 and sends a private message to Bob with the value A2=SHA256(A1). 3. Bob picks some random secret B1 and sends a private message to Alice with the value B2=SHA256(B1). 4. Bob creates a "bet" transaction that takes as input 2X of his own coins, and can be spent by: [Alice's signature + Bob's signature] OR [SHA256(A)==A2 AND SHA256(B)==B2 AND (((A xor B) mod 2 == 0, and Alice's signature) OR ((A xor B) mod 2 == 1, and Bob's signature)))] 5. Bob asks Alice to signs a "refund_bet" transaction which spends his 2X coins to an address that he controls, and has locktime of (say) 20 blocks into the future. 6. Bob broadcasts the "bet" transaction to the Bitcoin network. 7. Alice creates a "reveal" transaction that takes as input X of her own coins, and can be spent by: [Alice's signature + Bob's signature] OR [SHA256(B)==B2 and Bob's signature] 8. Alice asks Bob to signs a "refund_reveal" transaction which spends her X coins to an address that she controls, and has locktime of (say) 10 blocks into the future (if she exposes the entire "reveal" transaction rather than just the txid of the "reveal" transaction then she has to be confident enough here that the "bet" transaction won't be reversed, otherwise she would have to be confident enough that the "bet" transaction won't be reversed before doing the next step). 9. Alice broadcasts the "reveal" transaction to the Bitcoin network. 10. Bob redeems the "reveal" transaction by revealing B1 (when he is confident enough that the "reveal" transaction won't be reversed). 11. Alice redeems the "bet" transaction if she won, otherwise she sends A1 to Bob so that he could redeem the "bet" transaction without waiting for the locktime to expire. What script forms would need to be whitelisted to allow for the second form?
It works with Bitcoin as it is now, but whitelisting OP_XOR would make it a little more efficient. |
|
|
|
OK here's a better, and still round efficient, algorithm that doesnt require any new script features. Same idea as before player B pays player A $2 with probability 0.5 and then player A pays player B $1 (with probability 1) in such a way that collecting the $1 requires player B to accept the game (reveal enough information to allow player A to claim the $2 with probability 0.5).
But we can do it without requiring atomic simultaneous scripts: just broadcast the $2 first, I think no bitcoin changes required.
1: A->B private msg: h(a)
2. B broadcast msg: $2,{(a'=h(a) ^ b'=h(b) ^ ((a+b>n/2 ^ SIG(A)) v (a+b<=n/2 ^ SIG(B)))) v LOCK(time) ^ SIG(B)}
3. A broadcast msg: $1,{(b'=h(b)^SIG(B))vLOCK(time)}
4. B broadcast msg: b,SIG(B)
5. IF a+b>n/2 THEN
A broadcast msg: a,b,SIG(A)
ELSE
A->B private msg: a
B broadcast msg: a,b,SIG(B)
So in words:
1. A sends B h(a),
2. B broadcasts a $2 payment payable to A if A can also show a such that a'=h(a) and show b st b'=h(b) (and of course provide a signature).
3. A broadcasts a payment of $1 payable to B if B can also show b such that b'=h(b).
4. B cashes A's $1 payment from step 3, and therefore has to broadcast b, SIG(B), so accepting the game.
5. Now A knows b so he can find out if he won. IF A won (a+b>n) THEN he can broadcast a,b,SIG(A) claiming B's $2 payment ELSE if B won, A should send B privately the value a, then B can reclaim his bet without waiting for the lock time.
There is no financial advantage for aborting as the game only starts proper after step 4 where B claims A's $1 conditional payment accepting the game. A needs no further input from B to decide if he won or not, so if B aborts A can still claim his win. If A aborts he loses by default (whether or not he actually would have won had a revealed a).
A should reveal a whether or not he wins because it avoids stalling the game waiting for LOCK(time), presuming that B will want to know if he won or not before playing another round.
Adam
Nice! In step (3) it should be "v (LOCK(time) ^ SIG(A))" where the locktime of step (3) is shorter than the locktime of step (2), therefore B cannot cheat by broadcasting the transaction of step (4) right before the locktime of step (2) expires. This protocol has less communication complexity than my OP protocol, and also before the bet starts it only requires one party to possess 2X coins and the other party to possess X coins, unlike the OP protocol that requires each party to possess >3X coins. In terms of security, it behaves the same as the OP protocol, i.e. 0-confirmations security for relatively small instant bets, and if the parties wish to make sure that the transaction won't be reversed then they can wait for one or more block confirmations. I'll wait a little for more comments in this thread in order to see that we're not missing anything, and then I'll edit the OP to mention that this protocol improves upon my OP protocol. |
|
|
|
|
Hi Adam,
Your post #32 is a little unclear to me: when you say INPUT(2v) I think that you mean that those 2v consist of v that A supplied and v that B supplied (if it's 2v that only B supplies then A will win 2v while risking only v), so it's a bit confusing when you said that B is "committing to 2x the value", maybe I misunderstand?
As far as I know, Bitcoin scripts cannot access the amount of the inputs, in order to enforce this 2v requirement here.
You're saying that with your protocol(s) only one party commits, but we can view it as if B also commits, either by hashing its commitment with A's witness and signing (your post #27) or by just committing the needed coins and some signed value (your post #32), and if A aborts then the data that B committed allows him to win. In post #33 I'm concerned with a malicious B who tries to do a timing attack by broadcasting his data before A has a chance to claim that she won. I think that we must allow A the ability to win even after B's data was included in a block, which is a little messy in terms of what the Bitcoin nodes should verify (and if we add new syntax to Bitcoin scripts then we should beware of potential DoS attacks).
Intuitively, we cannot have a fair coin toss protocol that always works with 0-confirmations security, because we then don't use the PoW irreversibility property that Bitcoin gives us. The question is what's the best way to design a fair coin toss protocol so that the extra complexity of the needed transactions data is used only if the parties are dishonest (i.e. one of the parties aborts). This question is also relevant for the OP protocol, we can do there an instant bet by relying on irreversibility of the "bet","reveal1","reveal2" transactions with 0-confirmations, or the parties can wait for more confirmations as they please if the amount X of the bet is relateively large, but maybe there could be a better way to eliminate the "reveal1","reveal2" transactions when Alice and Bob are honest.
If it's not so important for the bet to be instant, then I still claim that an opcode that puts on the stack the hash of the block in which the transaction resides is the most elegant implementation. I suppose that such an opcode should return e.g. 0 if the transaction doesn't reside in a block yet, because I think that the Bitcoin protocol allows you to have a transaction that spends the output of another transaction where both of those transactions would reside in the same block, even though the Satoshi client disallows it. BTW if we do it for example with Litecoin instead of Bitcoin then the parties will know the result of the bet after 2.5 minutes instead of 10 minutes on average.
|
|
|
|
|
Show Posts
