I posted some comments to the bitcoin-dev list (cc the authors). http://sourceforge.net/mailarchive/message.php?msg_id=31612133(Talking about the paper, not the BIP). With regard to racing the other winner which catches up when private pool length=1:
i) the model does not appear to take into account that when another pool goes on to mine a block, and the attacker publishes their selfishly-withheld block, the selfish pool will not be able to change the existing winners mind. This is not insignificant as the pools have 30%, 20%, 15%, 7% etc.
ii) The miners already have an incentive, as other big bitcoin processors, to maintain fast, secure and redundant links to other significant miners.
The attacker is giving up a large proportion of their winnings from the times that they win at all. Say the attacker IS the 30% pool, when he wins and waits for someone else to win, > 80% of the network is pool mined, so there is a good chance that the other winner individually represents a non-negligible proportion of the network or a sufficiently well connected portion of the network that the attacker will be unable to race them to publication with a useful proportion of the network.
iii) Also broadcast is not instantaneous, lets say network propagation takes 10 seconds; a big proportion of the time, the actual mining times will be more than 5 seconds apart so that by the time the selfish miner learns of the block, much of the network will already have accepted it block as first.
iv) Even within the 10 seconds ambiguity period, the more powerful miner will tend statistically to come first, and so reach a bigger portion of the network, as well as having a stronger incentive to maintain links as in ii).
These four factors erode the achievable \gamma parameter. I suspect it unlikely \gamma>0.5 would be achievable, putting the profitable threshold \alpha in 25% - 33%. (And assuming whatever techniques to reduce latency are used by the selfish pools can be used by other pools.)
Your main result that even with \gamma=0 (if you dont win any races) that you still win once the selfish pool reaches 33% is an important new indication, which needs further consideration. (And you could expect to win some percentage \gamma>0 even with the factors I mention, and full
implementation of the same latency reduction techniques in all moderate sized miners, selfish and normal).
It is also not clear what will happen if multiple selfish miners compete with each other. A selfish miner cooperating as a peer to increase percentage runs risk of mutual sabotage - he has to announce his private block to his co-conspirator, and the co-conspirator may publish, or collude
with another non-selfish miner.
Your supposition is there is a profit motive to collude. However there are other profit motives in bitcoin that are not exercised - for example there were for sometime 2 pools that had excess of 50% power, and yet this was not abused for double spending. Of course increasing profit by a new mining strategy is not theft as double spending which has a clear loser. Miners even exercised restraint and volutarily avoided growing over 50%.
As others have I think said by now analysis is welcome. It seems that Peter Todd may have observed the same or something similar wrt miner incentives some months ago, though it wasnt as widely read nor formally verified.
It might be useful to release the source for your simulator if that is open to you.
In my opinion a constructive direction for reducing centralization risks is to try to reduce the use of and motivation for pools. Even at <51% per pool there is (probabilistic) miner risk in double-spends. And there is risk that the large miners evolve to become a defacto policy enforcement point for policies not aligned with user interests, or with fungibility of bitcoin which itself presents another kind of risk (defacto reduced fungibility should this arise would also be bad for bitcoin).
Also without even having mining power, there is scope to network hacking (eg of routers in front of miners) to influence the mining profit, and even double spend. As I mentioned large miners have an incentive to maintain secure redudant links (probably some links using Tor for blocks) as a counter-measure.
Adam
On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote:
> Hello,
> Please see below our BIP for raising the selfish mining threshold.
> Looking forward to your comments.
Adam ps Presumably you sent the authors an email with a link to this bitcointalk topic thread? |
|
|
|
Need to update this - found a problem a week back, but lost part edited tab: [ECDSA related chameleon hash...] choose r' random, compute point R=[r',f(r')] from curve equation f(x), then calculate T=H(m)*G+rQ. Choose random s, compute R=s^-1*T so that sR=T, then can write sR=H(m)*G+r'Q however now r=R.x and r != r' (because R is some random point) so the r value is inconsistent with point R, adjust for that by finding Q'=cQ such that sR=H(m)*G+rQ', so c=r'/r, ie Q'=r'/rQ (then rQ'=r'Q as required).
standard ECDSA [...] forged by Alice signature [...] on a different public key Q' which is a known multiple c=r'/r of Q: Q'=cQ. The ECDSA signature is (r,s), and the chameleon hash is (r,s,c).
[...] dispute Alice shows c [...] anyone can check r,s is a signature of m with public key Q'=cQ.
To forge different hashes Bob finds m' and Q" such that sR=?H(m')*G+rQ" so he has to find Q" such that H(m)*G+rQ'=H(m')*G+rQ" and as he knows d this can be written [H(m)+dr'/r]*G = [H(m')+dc"]*G where Q"=c"Q. [...]
[Bob forging leaks d...] However [...] to fix [...] prove knowledge of a discrete log of Q" or Q' in base Q using... an ECDSA signature with base Q and public key Q" or Q' respectively.
[Difference ...] Alice can reveal c also to create a strong proof (where a signature involving c but not disclosing c is a weak proof) and it can be seen that it does not solve to d.
[...]
Bob could be coerced into proving that a forgery he makes is not authentic, by showing c" (instead of a DL proof of knowledge of c") which then allows his private key to be recovered. However Alice doesnt give Bob c, so Bob cant prove that Alice's message was not his, he could be lieing and actually have c.
There is a flaw in the logic in the last para. If Bob is coerced into revealing c" and hence d is recovered (or he is coerced to reveal d directly), then anyone can do n^2 analysis of the n signatures (one real and n-1 forged) pairwise and see that all the forgeries derive from Alice's deterministically with the private key, but Alice's key cant be derived from any, and hence Alice's is correct. Also Bob's only deterence to doing that at any time without coercion is revealing his private key. The root cause of the failure is there is no new randomness in the process of forging chameleon hashes by Bob. To the extent its still interesting if we change this much more, I think that might be repairable by having Alice not publish s (send it out of band to Bob, dont commit to it in the spend). Then the chameleon hash becomes (r,c). Alice cant find a different s that signs commits to a different message because she doesnt know d. And Bob can recover k as sR=H(m)G+rcQ => sk=H(m)+rd so k = s^-1(H(m)+rd), and armed with k Bob can create s' for any signature. Whats more this time those are all symmetric. With d he can as plausibly recover k from (r,c),s' so Alice's message is indistinguishable as desired. Not sure that overall is ECDSA like enough to be interesting and the schnorr method in https://bitcointalk.org/index.php?topic=318279.msg3417729#msg3417729 seems a lot simpler! Adam |
|
|
|
Yes, such a method was proposed in the Bitcoin Banknote scheme by Sergio. I like both ideas, although your solution works outside of the dollar bill scenario. Yes I was aware of that one, the original poster had a 2 of 2 sig which might a bit more like what discussed above (partly non-transferable) though it was hard to understand what he meant, and Sergio simplified it to literally non-respendable period - sacrifice a bitcoin to a non-spendable address being hash of bank note serial number. I had posted something earlier about fixing a coin public key while still being able to prove ownership also https://bitcointalk.org/index.php?topic=232787.5. That idea was to hold the public key constant and change the base (which is not bitcoin format compatible). There was also an idea to do something similar in a bitcoin standard way that could be a stable coin serial number (an auxiliary signed message, that the recipient would demand to be present). The purpose of which is to allow the user to check the coins current ownership status, with respect to a static identifier that is engraved around its rim say. I more like to think about a mostly online world where you want to ideally be able to check the status of a coin. So the ability to do that without the ability to transfer it back to the blockchain (or with a clear long lock-time) means one issue is taken out of the picture - that if you are not online for a while after receiving the coin, that a previous owner cant spend the bitcoin underneath you on the blockchain. Adam |
|
|
|
Just to be clear, the issue is not the maximum size of a single transaction. The issue is that in order for the offline computer to verify the transaction fee, you must supply every, full, supporting transaction along with the one to be signed. The offline computer must see the tx associated with every input, so it can verify the value of each input. Technically, there's a trivial hard-fork solution: https://bitcointalk.org/index.php?topic=181734.0 ... but I don't have much hope of it being adopted. I suppose there are two ways to view that: a) transaction fees should not be implicit (and outputs summing to inputs, including fee should be validated downstream); or b) the signer should state what he is spending (and the downstream should verify it) as you proposed in the above link. Either solution could be fine. Kind of frustrating the pace of progress on bitcoin main though one can fully appreciate the risks and resource constraints, but mostly the risks. It is why I proposed the bitcoin-staging idea. Now all we have to do is coax Warren Togami (formerly fedora distro founder) into taking the mantle. He already ventured from litecoin into spinning a bitcoin-OMG release (litecoin latest fork with bitcoin parameters reinstated, to give bitcoin users the advantages of litecoin validated fixes). Though something like that is less use to armory as armory is itself on the high value end of the bitcoin scale, and people may not use the fedora like variant on high value. Streamline and practice a system for hard forks? Stall and dont progress and get undertaken by faster progressing alt-coins? Move too fast and make a security mistake. Rock and hard-place. Hmmm. Adam |
|
|
|
Personally, I think this is an ideal steady-state solution once the offline system is setup. But you can't use plain QR codes, you'll have to do QR videos.
drazan's visualBTC android offline wallet uses "animated QR codes" which is consistent with what you said about the practical bandwidth requirements. https://bitcointalk.org/index.php?topic=210371.0The other thing is there's a sanity size cap on a transaction: the bitcoin block size is limited to 1MB for now, and I think its probably the bitcoin developers might have to take countermeasures or non-linear size related fees if people got in the habit of creating individual transactions that use a whole block - that would limits bitcoin to one transaction per 10 minutes. But there is still the concern about getting the system setup in the first place. I guess if you have a custom OS image with the camera software pre-installed, you could use the QR thing to move the Armory offline bundle intself onto the system.
Maybe there's a market to include a PGP code signing key. and a pre-installed armory client in an armory labeled cheap android tablet with the speaker, microphone, bluetooth, wifi, and USB cables cut. (Or one that could be made cheaper by not even including that hardware). Then you could send it via QR video, armory signed software upgrades;) I think a risk with USB is someone can infect the online wallet via remote internet compromise, infect a USB that gets plugged into it, and from there into the offline wallet. Adam |
|
|
|
dacoinminster, if badbios does what people are claiming it does, you're fcked no matter what. There's nothing a user-level program like Armory can do to protect you, except perhaps using a TPM chip. There are no robust wallet apps with TPM signers that I'm aware of*, although this would be a good addition to Armory...
Well there is also the air-gapped optical interface: scanning QR codes. drazvan made an offline QR code scanning wallet using network disabled cheap android wallet (can buy for $50 - $100) including camera. Then you can make payments. You do need no buffer overflows in the QR code scanner, but other than that... And at least thats code we get to look at, not USB firmware on a motherboard. Adam |
|
|
|
The problem is hash output approach is only secure up to the birthday attack which is a generic brute-force O(2^80) attack, not bitcoins O(2^128) design target.
Lets call the bitcoin address-hash AH(z) = RIPEMD160(SHA256(Q)) where Q is a public key or more generally a bitcoin script.
This is because I can use the birthday attack to search for strings s="SIG(A) and y=H(x)" and s'="SIG(B)" such that AH(s)==AH(s'). That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work.
One work-around is to use scripts directly serialised into the transaction rather than script hash, however that impacts UTXO size, P2SH is good because only the script hash goes on the blockchain which is typically smaller than the script itself. Note script addresses are intentionally incompatible (different version) with regular addresses, so its not possible to find AH(Q)==AH(script) where Q is a public key and script is a script. Probably the most generic approach is to increase the script hash address to 256-bit hash eg define new AH'(z) = SHA256( SHA256( z ) ). Alternatively work-arounds or security can be achieved by considering the size of the attack O(2^80) + TMTO is large even relating to a bitcoin hashrate. Users of hashlock as a protocol sub-step should avoid creating pre-computation attacks. Eg accept hashlocks only on strings they had input in shortly-before (few hours/days which might be needed for confirmation) or during the protocol. Adam ps thanks to sipa and gmaxwell for discussion on IRC about this topic, clarifying assumptions for me. |
|
|
|
Towards reducing the manufacturer and hardware trust of physical coins it occurred to me that you can easily and voluntarily create a non-block-chain-transferable bitcoin. Its a bit like partially destroying a coin (by spending it to an invalid address) where you create a coin that is not blockchain spendable (by bitcoins rules), but where you can still prove you half-own it, and can hence half-transfer it. Because you can half-transfer it, it can still be transferred outside of blockchain rules (eg offline or by a group of clients respecting these alternate rules). To summarize existing methods that coins can be sacrificed or made permanently non-transferable: spend the bitcoin to an invalid address, eg to the address 0, or H(digits of pi) or to an address formed from a public key of form H(random). Now back on topic, to create a coin that is partly spendable is analogous: a 2 of 2 signature with one invalid address. Or requiring hash preimage of 0, or digits of pi. (I mentioned the idea of having a multisig with one invalid address in the thread about fixed public key coins, also about physical coins, but I did not see this use case at that time.) Alternatively if the serial number were implemented as a demonstrably invalid optional second signing address added to a multisig, on each physical coin, probably tools could already index it; though invalid addresses are frowned on for frustrating compaction.
The partially-transferable coin means you have intentionally created a coin that can not be transferred on the blockchain but the physical ownership can still be demonstrated if you have an electronic coin like firmcoin ( https://bitcointalk.org/index.php?topic=232898.0 ). How does that help physical bitcoin security? Well it ensures that someone cannot empty a coin of its value undetectably by removing the SD card under the tamper evident sticker, or spending the private key where its hidden under a tamper evident sticker, or trusting the coin manufacturer that the coin is even in there in the first place. And relative to firmcoin (which allows coins to be unloaded and reloaded, but deletes the private key on unload, you no longer have to trust the manufacturer to do that as much, because even if they have the private key in unloaded state on their computer, they still cant spend it on the block chain). To double spend a coin the attacker would need an extra empty physical coin, or the manufacturer could put the same private key in multiple coins (or the user if the user loaded the private key). And whats more if multiple people think they own the same coin it can be somewhat obvious in that the coin is spent at locations too far apart to physically move in the time frame. (And this is a topic of another post, tracking that). If its permanently non-block-chain transferable that creates two non-intercheangeable bitcoins a physical coin that can not be unloaded, and an online bitcoin, and the only way to trade them is to swap them 1 for 1. You might also consider variants where the 2nd element is not invalid but heavily time-locked eg 1 year. To time-lock the person loading the coin would create a 1 year time-lock and put the time-lock private key in the physical coin. In this way anyone can validate the address and see it wouldnt have been possible to spend it yet. Or where the 2nd signature allowing online redemption can be spent but only in cooperation with a somewhat-trusted entity, or a quorum of entities or users (k of n of them.) Adam |
|
|
|
Unless I am misunderstanding something about the seralization, with pay to script hash, you create an address which is the hash of the script, and to claim you have to provide the script and the inputs to make it execute to true. A recurring pattern in cross-chain atomic swaps (litecoin for bitcoin) and atomic colored coin swaps, or fair-coin-toss / fair-roulette, CoinSwap etc like is use of "SIG(A) and SIG(B) and y=H(x)" where one party with-holds x and the other party builds a related transaction that he can see will become payable as a consequence of the counter-party spending the first transaction because both transactions rely on knowing x. One example is (to see what I mean about the two stage, this protocol was by iddo and optimized by myself, I think the y=H(x) idiom is used in multiple earlier protocols also): https://bitcointalk.org/index.php?topic=277048.msg3220019#msg3220019 The problem is hash output approach is only secure up to the birthday attack which is a generic brute-force O(2^80) attack, not bitcoins O(2^128) design target. Lets call the bitcoin address-hash AH(z) = RIPEMD160(SHA256(Q)) where Q is a public key or more generally a bitcoin script. This is because I can use the birthday attack to search for strings s="SIG(A) and y=H(x)" and s'="SIG(B)" such that AH(s)==AH(s'). That can be done in work O(2^80) (and massive storage), or various time memory tradeoffs with lower storage and more work. Sounds expensive but bitcoin right now is doing O(2^62) every 10 minutes or about O(2^78) per year. Maybe in a few years bitcoin will be doing O(2^80) every 10 minutes and 14nm ultra-dense energy efficient ASIC miners will fill racks of data-centers. Also worth thinking about that there are O(2^64) birthday attacks on SHA1, and no one has probably tried to find analogous attacks on RIPEMD160 but that is not proof that RIPEMD160 is immune. But note the SHA1 birthday attacks need multi-hash-block inputs, and the inner SHA256 output fits in one SHA1 input block; and SHA1 birthday attacks work by choosing and steering bits; SHA256 output is one-block and random and frustrates that. Realistically given the constraints therefore even SHA1(SHA256(z)) for this purpose probably retains O(2^80) birthday strength. Designing hashes immune to that class of multi-block steering attacks is what the SHA3 NIST competition is about... Adam |
|
|
|
Another alternative, if the device knows what the address of its private key is... is that it can give you SPV fragments to show that key being paid... and then you only have to have (possibly somewhat old) block headers, to verify the amount.
Well so long as we are relying on trusted things, one could have a virgin mined coin and a time-stamp authority using TPM hardware also, which would define just that coin is valid if its virgin (its address is in the coinbase/block that the card can present) and the public key is signed by a certified-as hardware contained key, and the difficulty of the mine is >= difficulty at that time-stamp (to prevent cheaper mining at historic difficulty rates. Thats a looser definition of time-stamping as its not directly blockchain auditable, though it can easily be made indirectly blockchain auditable by including the time-stamping authorities signed master-hash into a bitcoin message in the block chain. It is looser because doesnt quite adhere to the 21mil limit - its follows bitcoin difficulty but doesnt contribute to it. To track it strictly you'd need to what gmaxwell said with SPV. Btw I presume people also know about or recall firmcoin https://bitcointalk.org/index.php?topic=232898.0 by Sergio_Demian_Lerner, it also contains a private key, only in that case uses the hardware to sign transactions, and does do things with SPV information. I presume he made at least a prototype from the initial post photo. About the private key, and addative homomorphism, its not explicitly stated that I saw in the article or thread, but I think what is going on is that the smartphone app has the second half of the coin, to compose the address (as with BIP 38) except thats using ECDH (curve multiply) vs addative homomorphism (analogous effect). Then the smart phone transfers one half of the key to the other smartphone, and the hardware key container transfers the other half (via hw certified RSA as described in this thread). The key-half held by the phone cant be changed between transfers, without going via the block chain, so all previous parties who held the coin have enough to spend the coin online, once the coin private key is taken from a card. [EDIT: and the purpose of this is like a poor-mans observer protocol like in Brands and other offline ecash systems: the card cant tell much because what it knows is not correlateable with the public key]. What about instead at each transfer the private key (composed of x+y where the public key is Q=xG+yG, x held on card, y held on smart-phone) is resplit as in proactive security at each transfer? So far the design is smartphone and the card never know the full private key z=x+y mod n in one place, unless and until the coin is spent online (by removing it from the card). To preserve that security assurance, the card can instead create r=random, send RSA(z'=x-r) to the other card, and r to the other phone. Then the other phone learns y'=y+r and hte other card learns x'=x-r, and the private key and public key remain the same: z=x+y=x'+y' mod n. But yet the previous smartphone owner does not retain power to spend the coin, even if he physically stole it back from you as he is missing y'. The recipient smartphone will not consider the payment offline validated unless it can check that x'G+y'G=Q and that x'G is certified by the card. (I used this mechanism in my still not yet posted, really must get around to editing last bit and hitting send, non-TPM model for this). Adam |
|
|
|
[EDIT: its long and full of crypto, but read 6.5.1 last para or two; and 6.5.4 shows you what he's thinking this is good for "bearer certificates" = offline transferable pseudonymous ecash.]
In short it gives you a way to have a smart card that does something very cheap (like one 256-bit mod mul and 256-bit mod add to compute cx+w mod n (a contribution to the signature) Because of the inflow/outflow security arguments the card has no visibility into your privacy, its tamper resistance only protects double spending.
btw I its not so clear in the book, and I reinvented it in my 1995-2005 pre-bitcoin attempts to find a way to deploy a decentalized anonymous ecash, as specified what he is saying is actually not offline respendable, only offline spendable; ie after you've done your spend, before you can respend, you have to deposit the funds in an issuer bank. (And in bitcoin or zerocoin or the 1999 Ta-Shma & Sander "auditable anonymous electronic cash" paper there is no central bank, but you have to send it to the blockchain/zerocoin mix/shared blackboard respectively, but the dependency is still present). What I figured out is you can offline respend without deposit (without going online) using 0-value coin collection as the initial witness. Very excited when I figured out that in 2000, and I asked Stefan about it, but it turns out there was a masters thesis on this topic and its mentioned in a footnote somewhere in Brands PhD thesis/book referenced above. Anyway it seems to me you're more interested in offline re-spendability so you need to use that follow-on invention/re-invention. Why I did nothing with this protocol (eg like rush off and implement it with B-money) is I was thinking it was not good enough - its necessarily, like bitcoin, pseudonymous, and publicly linkable, which I considered, and still do consider to be a privacy problem (and in bitcoin whether you believe in privacy or not, a fungibility problem in addition, hence all the debate about zerocoin, coinjoin, mixers and taint, whether you actually even want anonymity or not, those security concerns of fungibility and anonymity are actually orthogonal - you can have fungibility (via coin anonymity) with pseudonymity, or escrowed identity and other variants just fine). Btw there is a difference between payment confidentiality and pseudonymity/anonymity also, you can have payment confidentiality with or without pseudonymity/escrowed identity pseudonymity/anonymity. Bitcoin has limited payment confidentiality (you have to work hard with wallet control, which is not implemented, and disciplined fund separation, and mixes/coinjoining is of apparently statistically weak value according to the data analysts who have looked at the network flow statistics. And thats a problem. If nothing else we need to make bitcoin payment amounts confidential (eg homomorphic value encryption). And even payees is extremely invasive if you think about it. Oh the public can see you bought an ebook from this publisher. Or you bought a condom pack from this supplier. etc Its ridiculously invasive as is, and if your credit card issue or bank account put your statements online like the block chain there would be a public outcry. Also I have to say I am not someone convinced by the offline respendability security argument. Even if there is a fidelity bond, the problem is offline respendable card is a license to print money, and people will just spend a multiple of the fidelity bond or try to. One somewhat defense is that if multiple people have offline respenable money flowing around, some of them are going to convert it to online ("deposit" it) and as soon as that happens the double-spend hw hack is blown. You want to pass a "this key and card series hacked" protocol revocation cert through the network, and switch to the ciphersuite/keyset B while working on deploying card C or firmware upgrade C. Adam |
|
|
|
I was also thinking of something similar (draft post sitting in another tab), not skimmed your paper yet though. I think I can get it to work, pseudonymously, somewhat online verification, but with untrusted open spec hardware, that anyone would be invited to produce and load bitcoins onto. So the design parameters are a bit different. But I share your excitement for physical electronic non-clonable coins (though I did not try to increase bitcoins privacy model in my idea) and encourage you if you're an operational guy who actually builds things go go for it  Specifically about your proposal and question the perf requirements of your card, I think you are not taking advantage of existing known technology. Read about Stefan Brands observer protocol, chapter 6 (whole book online as pdf in chapters): http://www.credentica.com/the_mit_pressbook.html[EDIT: its long and full of crypto, but read 6.5.1 last para or two; and 6.5.4 shows you what he's thinking this is good for "bearer certificates" = offline transferable pseudonymous ecash.] In short it gives you a way to have a smart card that does something very cheap (like one 256-bit mod mul and 256-bit mod add to compute cx+w mod n (a contribution to the signature) Because of the inflow/outflow security arguments the card has no visibility into your privacy, its tamper resistance only protects double spending. Furthermore its offline spend compatible using limited-show protocol, which allows things like retep's comments about good behavior bonds. You can put the private key for a high value coin (eg $10,000) in the private key certificates in such a way that if a single double spend occurs (which can only happen as a result of hacking a card) a simultaneous equation is released that allows recovery of the $10,000 private key (that is the basis of the limited-show protocol). Brands protocols are defined on Schnorr signatures (or ECSchnorr) and of course bitcoin uses ECDSA. It might be within the realms of possibility that you could achieve something analogous though DSA is a complexification of Schnorr that does nothing for security and just limits flexibility. Brands also has an RSA group variant but that doesnt help the compatibility. Adam |
|
|
|
simpler and use EC discrete log for more compact keys [...]:
A=kG+mQ where recipient knows d from dG=Q.
now recipient can compute A=k'G+m'Q as he knows k and m, and x: r=k+md mod n (r is same as from Schnorr signature in fact) and then k' = r - m'd = k+(m-m')d mod n. m would probably be H(msg).
Catching up the thread from #bitcoin-wizards (plus some fixes and new observations) gmaxwell posed the question if you could make a chameleon hash that is also a valid ECDSA signature (with the added benefit being its a bit more bitcoin integratable). Curiously it seems that you can and here's how: ECDSA: R=kG, r=R.x, s=k^-1(H(m)+rd) where d is private key Q is public key Q=dG, G is base point, k is random; signature is (r,s). A verification relation is: sR =? H(m)*G+rQ Alice is using the hash, Bob is the owner of the private key able to forge hashed values. Work backwards, choose r' random, compute point R=[r',f(r')] from curve equation f(x), then calculate T=H(m)*G+rQ. Choose random s, compute R=s^-1*T so that sR=T, then can write sR=H(m)*G+r'Q however now r=R.x and r != r' (because R is some random point) so the r value is inconsistent with point R, adjust for that by finding Q'=cQ such that sR=H(m)*G+rQ', so c=r'/r, ie Q'=r'/rQ (then rQ'=r'Q as required). Now we have a standard completely forged by Alice signature but not on Bobs public key but on a different public key Q' which is a known multiple c=r'/r of Q: Q'=cQ. This key is mismatched with The ECDSA signature is (r,s), and the chameleon hash is (r,s,c) the secret value which allow Bob to modify the chameleon hash is c (the factor for modifying the public key Q'=cQ). To reveal the hash in event of dispute Alice shows c (Q is anyway computable from r,s; and Q'=cQ). Then anyone can check r,s is a signature of m with public key Q'=cQ. The signature is verifiable without revealing c, but meaningless as no one knows who's key Q' corresponds to, not even Bob. To forge different hashes Bob finds m' and Q" such that sR=?H(m')*G+rQ" so he has to find Q" such that H(m)*G+rQ'=H(m')*G+rQ" and as he knows d this can be written [H(m)+dr'/r]*G = [H(m')+dc"]*G where Q"=c"Q. So solve to find c"=[H(m)-H(m')+dr'/r]/d and therefore Q"=c"Q. Bob can show (r,s,c") and anyone can check r,s is a signature of m' with public key Q"=c"Q. One comment in the paper Greg referenced in OP is Bob forging reveals his private key in some protocols (which is obviously no good, its more than an inconvenience as it also destroys the non-transferability if his private key leaks people can check which hash the private key can be computed from to know which is the forgery). In this case as c'=[H(m)-H(m')+dr'/r]/d = [H(m)-H(m')]/d+r'/r so d can be recovered d=[H(m)-H(m')]/(c"-r'/r). However its rather easy to fix this, instead of revealing Bob revealing c" or Alice revealing c they can prove knowledge of a discrete log of Q" or Q' in base Q using... an ECDSA signature with base Q and public key Q" or Q' respectively. However even that does not quite work the same way as the other chameleon hash because Alice can reveal c also to create a strong proof (where a signature involving c but not disclosing c is a weak proof) and it can be seen that it does not solve to d. While its different thats actually a feature, as if Alice reveals a strong proof, Bob's forgery is not plausible as he cant make strong proofs - if he does it reveals his private key which makes it obvious his messages are forgeries. (In the paper and the above Schnorr related scheme, in fact even if Alice does reveal her proof, an arbitrator cant tell which message was Alice's and which was Bob's, so in theory Alice could falsely claim to have made one of Bob's forged messages, though it assumed this is not generally a threat). Conversely Bob could be coerced into proving that a forgery he makes is not authentic, by showing c" (instead of a DL proof of knowledge of c") which then allows his private key to be recovered. However Alice doesnt give Bob c, so Bob cant prove that Alice's message was not his, he could be lieing and actually have c. So overall that seems like a slightly stronger chameleon hash property. So we get the new benefit of no forgery ability for Bob if Alice reveals a strong proof, and yet no ability for Bob in the normal case to transfer proof of what Alice said. He could reveal weak forgeries, and Alice's message is indistinguishable from them. He could make a strong forgery (reveal c") which reveals his private key, but that still doesnt prove that Alice's weak forgery was authentic - they could both be Bob's and he could be lieing about not knowing the secret value c (discrete log of Q' wrt to Q). Adam |
|
|
|
some contracts people form are _too low value_ to effectively use the kinds of tools to ensure honest dealing in wider western societies today (e.g. courts) or the easy centralized alternatives facilitate rent seeking (e.g. having to pay to use a game server in order to play a game with your friends, you all have network access and powerful computers, what do you need the server for?). If mathematical tools exist that allow cheat proof interacting they are often inherently scalable— we can apply them to high value things and low value things alike, because once they're coded they're nearly free.
Yes this is very true and a big potential for smart-contracts. It is possible smart-contracts maybe more important than bitcoin itself. Its a pre-singularity AI that can automatically and perfectly fairly apriori avoid disputes resulting from reneging, aborting and extorting virtual good exchanges. Surely its better to mathematically avoid the possibility of a dispute occurring than to pay a lawyer $500+/hr and court fees to try sort it out after the inevitable happens when you rely on reputation (like ebay) and trust etc. Smart-contracts also have huge potential in financial disintermediation, think about the trillions per year spent into the financial intermediaries for doing nothing but writing, and acting as middle man in contracts for financial products, and holding escrow funds, matching orders; with smart-contracts you could write your own structured product, and it does not need escrow and its self-enforcing and executing and survives the financial institution going bankrupt so less systemic risk also. Having good tools at our disposal allow societies to pick appropriate tools for appropriate situations, and we can all only benefit from that.
Yes. I would say abstractly that the more of law and contract law is implemented in mathematically enforced code with pre-emptive impossibility of crimes, the less reliance on courts which are unreliable, biased or subject to political interference, uneven enforcement etc its a huge financial and human capital cost saving and a reduction in the need for and influence of governments in human existence. And that is good because governments have inherent systemic problems, so less government is better. All roads lead to Rome Adam |
|
|
|
the point is the contracting parties should be free to contract without interference from outside parties (criminal or government) and the point of a chameleon hash based signature (or nearly equivalent designated verifier signature) is that the evidence evaporates because its intentionally non-transferable - they cant renege even if they wanted to.
Another analogy, its rather similar to why Ian Brown & I wrote the non-transferable PGP signatures draft (1998) and why Ian Goldberg's OTR (off-the-record) encrypted messaging protocol involves non-transferable signatures: you want the protocol to have properties that are aligned with the users interests, and to not have unintended and negative to you side-effects. When you're chatting in IM or email, its probably not your intention to create a legally binding non-repudiable permanent quotable provable record. Really its not, and there are many people who got burnt for saying off the cuff things, that even ended up in court to their pain, so anything that increases the unintended consequences of making that unintentionally non-repudiable is BAD for the user. Its in your interest to be sure that the party you are talking with is who you think it is, and not an impostor, and if you dont sign messages anyone can pretend to be anyone even with PGP encryption; but if you sign non-repudiable PGP signatures, the person you are talking with can renege on the implied confidentiality of a personal message and transfer that signature and show it to other people against your will, as the signature is verifiable by anyone. A non-transferable signature evaporates when its shown. In the non-transferable PGP sense its very simple you sign a random (session) symmetric encryption key, and MAC the message with it, and encrypt the key for the recipient. Now he can write any message he wants with that MAC key, but he knows he didnt write it himself and so he knows its authentic as you signed it. k=random, SIG(k), c=MAC(k,m), PKENC(B,k,c) something like that. OTR is doing something similar but interactive. The Chameleon hash signature has the same kind of designed to be aligned with user's interests design objective. Adam |
|
|
|
How do you mean here? Normally, in most societies, its frowned upon presenting a forged contract. For example here in sweden, its illegal to present a forged contract, even if you do it in a response to a threat or coercion.
I think you maybe dont understand the concept of smart contracts and anarcho-capltalism (as embodied by crypto-anarchy where crypto means cryptography, and I guess not anarchy also, just an egalitarian society without a force monopoly form of government). Basically the idea is using new crypto concepts its possible to contract without threat of violence/imprisonment as a disincentive to cheating, because the contracts are atomically self-enforcing. You might find sci-fi "Snow Crash" by Neal Stephenson interesting, and "Cyphernomicon" by Tim May a kind of crypto-anarchist manifesto (online http://www.cypherpunks.to/faq/cyphernomicron/cyphernomicon.html) (not to be confused with "Cryptonomicon" another sci fi work by Neal Stephenson, also fun but long and somewhat related). To quote Wei Dai from his motivation section intro to B-money (one of the main bitcoin precursors): http://www.weidai.com/bmoney.txtI am fascinated by Tim May's crypto-anarchy. Unlike the communities traditionally associated with the word "anarchy", in a crypto-anarchy the government is not temporarily destroyed but permanently forbidden and permanently unnecessary. It's a community where the threat of violence is impotent because violence is impossible, and violence is impossible because its participants cannot be linked to their true names or physical locations.
Until now it's not clear, even theoretically, how such a community could operate. A community is defined by the cooperation of its participants, and efficient cooperation requires a medium of exchange (money) and a way to enforce contracts. Traditionally these services have been provided by the government or government sponsored institutions and only to legal entities. In this article I describe a protocol by which these services can be provided to and by untraceable entities. I am not sure if Satoshi had crypto-anarchy in mind but folks like Tim May (cypherpunks co-founder/cyphernomicon), most of the cypherpunks, and people working on ecash like myself (Hashcash, distributed mining), Wei Dai (b-money) / Nick Szabo (bitgold), Hal Finney (RPOW), and most of the digicash tech guys (David Chaum long defunct payer anonymous ecash company), zero-knowledge systems guys (pre-Tor privacy networking) and others working on ecash 1995-2005 certainly did have that in mind as their burning motivation. I am also guessing Chris Odom (open transactions) who seems to enjoy distributed Chaum servers, with voting pool backing, though I cant speak for him. Since that time finally I also see some hope of political progress in the form of the meteoric rise of Rick Falkvinge & the pirate party (and the Libertarian party eg folks like Ron Paul to the extent the LP was slowly rising towards having a chance of being elected), but previously (eg back in 1995 - 2005) it seemed almost the only hope for humanity was a new wave of technological progress led shifts. In the same way that the internet tends to topple undemocratic states, non-state controlled free money tends weaken the grip of to varying degrees systemically corrupt and difficult to reform governments. [EDIT: btw other than the internet, another example of technological led power shift was the discovery of public key encryption and the ready availability of PGP, and later other communication security/privacy iike OTR, Tor etc. The fact that many governments tried to control access to and restrict encryption, before giving up, should tell you that you need to be using it: they were worried they can less control a populace with cryptographic free speech and cryptographic freedom of association, even those are legal rights in most countries, cryptographic enforced rights are more strongly held than legal rights, because as we see from Snowden, legal rights arent worth the paper they are written on. The reason they gave up is it became an untenable position for a notionally free democracy to enforce. More restrictive regimes tend to have more restrictive crypto usage regulations.] Anyway you can use bitcoin without caring about libertarian politics or its technical adjunct crypto-anarchy eg because its technically cool, or because you dislike governments doing money printing/quantitative easing to the benefit of connected banks, and detriment of individuals, or bank deposit seizures (like in Cyprus) or as a speculative investment, or because its faster and cheaper, or available in all countries, even without banking infrastructure and onwards And by doing so, in a neutral non-political way, you are also helping build the crypto-anarchic future, in the same way that promoting internet use indirectly helps topple dictators. But I do recommend anyone to read the Cyphernomicon and Snow Crash it might just open your mind to a new view point or even convert you. [EDIT I guess Assange et al's book "Cypherpunks" is probably on the money though I havent read it myself.] Circling back to why forge a contract, thats not the point: the point is the contracting parties should be free to contract without interference from outside parties (criminal or government) and the point of a chameleon hash based signature (or nearly equivalent designated verifier signature) is that the evidence evaporates because its intentionally non-transferable - they cant renege even if they wanted to. Designated verifier is a bit different as that means it convinces the recipient (Bob), but neither Alice nor Bob can prove/transfer the signature as either party could forge; with chameleon hash signatures only Bob can forge. Also bear in mind that other than the fact of shaming a pseudonym (Bob) and tarnishing his reputation that's may not be much of a disincentive, and another model is for the parties to agree on an arbitrator who has 3rd vote in 2 of 3 multisig. Probably you can use two designated verifier signatures so the the arbitrator could also have forged the contract. Adam |
|
|
|
m message to sign) with t=h(m). Then make random c, chameleon hash a=c^t mod n. Chameleon hash is (c,t=H(m)a). Bob has p & q so he can compute different t'-th root, for (c',t'=H(m'),a) from c'=a^(1/t') mod n where t'=H(m'), where as Alice can only go in the forward direction choose c, hash mesage to make t, raise c to power of t.
Occurs to me it can be even simpler and use EC discrete log for more compact keys (RSA keys are 3072-bit for security equal to 256-bit EC): relabelling t to be k to be more Schnorr like: A=kG+mQ where recipient knows d from dG=Q. now recipient can compute A=k'G+m'Q as he knows k and m, and x: r=k+md mod n (r is same as from Schnorr signature in fact) and then k' = r - m'd = k+(m-m')d mod n. m would probably be H(msg). (A real schnorr signature is A=kG, r=k+cd, c=H(a,m); verify: rG=?A+cQ). Adam |
|
|
|
I am thinking of coming up with a new encrypted minikey spec for physical bitcoins and secure paper wallets. - The ability for the costly scrypt step to be outsourced (eg by a mobile device, to a web service), without giving that service the key/factors or any advantage other than the single exception of being able to bruteforce the key without the cost of scrypt if they were to come into possession of the complete key independently
That is what this thread is all about. https://bitcointalk.org/index.php?topic=311000.msg3341985#msg3341985there are three specific proposals in there and it coincidentally references BIP 38 The first and simplest is you dont need to outsource - just create a random 32-bit salt and use scrypt(iter=1), then delete the salt, your smart phone can easily create problems it cant solve then. There is also a different way to outsource the work of redeeming a coin (so you could use a 46-bit salt and outsource to untrusted miners) something useful for litecoin miners to do. Adam |
|
|
|
message hash in the above basic pay-to-contract protocol is replaced with a chameleon hash ( such as this one based on gap-DH, [...] A chameleon hash is a hash function that takes a message, a pubkey, and a random value. The function is designed so that it works as a strong hash function but the holder of the corresponding private key can produce free collisions. E.g. he can easily find an random2 for message2 such that CH(message,random,pubkey) == CH(message2,random2,pubkey). btw a simpler chameleon hash involving conventional crypto can be seen as part of this indistinguishable shortcut hashcash variant based on RSA. https://bitcointalk.org/index.php?topic=308009.msg3307636#msg3307636Just replace the search for t =? h( s, i, a, m ) mod 2^k (where i is an iterator, s salt, a initial witness, m message to sign) with t=h(m). Then make random c, chameleon hash a=c^t mod n. Chameleon hash is (c,t=H(m)a). Bob has p & q so he can compute different t'-th root, for (c',t'=H(m'),a) from c'=a^(1/t') mod n where t'=H(m'), where as Alice can only go in the forward direction choose c, hash mesage to make t, raise c to power of t. I use it to create a hashcash variant with an indistinguishable short-cut which you could think of as a chamleon proof of work (a chameleon much repeated hash, or a single exercise of the trap door holders private key). I am guessing no one has thought of that particular chameleon hash construct for some reason because people do not usually reach for the esoterics gap DH or bi-linear DH unless they run out of flexibility with conventional hardness assumptions and need the extra degree of freedom. I could be off base, but this also does not leak the private key, and that seems to be the implication of the paper you referenced with the improved Chameleon hash. Adam |
|
|
|
|
Show Posts
