and i want to make a question, may we can use double signature in one account?
Topic: One-time signatures to prevent double spends (Read 1371 times)
I don't see how this discourages double spends. If a double spender sends out his two transactions in the traditional race attack, then one will reach some miners, the others will reach other miners, if at all. However, only those nodes that receive both will know that a double spend occurred and only they can get the private key.
and i want to make a question, may we can use double signature in one account?
and i want to make a question, may we can use double signature in one account?
Do you believe that the nothing-at-stake problem is unavoidable? Ever better, is there any mathematical proof?
This is OT for this thread, but you don't need a mathematical proof to understand the problem with nothing at stake - it boils down to this: if block production has no ongoing costs, neither does attacking the chain.
How would this work with address reuse?
It won't.
This is normally called a single show signature.
If you search the #bitcoin-wizards logs for that term you'll see some instances of this proposal-- you might find it informative.
If you search the #bitcoin-wizards logs for that term you'll see some instances of this proposal-- you might find it informative.
Found it now. #bitcoin-wizards is not high enough in google search.
Also, I don't see how this discourages double spends. If a double spender sends out his two transactions in the traditional race attack, then one will reach some miners, the others will reach other miners, if at all. However, only those nodes that receive both will know that a double spend occurred and only they can get the private key. Those nodes will not broadcast the double spends (unless they are Bitcoin XT) so the double spend transaction won't reach some of the miners. Those who do know the private key after receiving those transactions are at a disadvantage since two transactions have already propagated faster than their own double spend can. Unless they are a miner, then knowing the private key would be pointless.
And with miners, if they don't receive the double spend transaction, how do they know that a double spend occurred? A smart attacker could simply broadcast the transaction to specific nodes, nodes that he controls, so that the miners only get one transaction and other nodes before them filter out the double spend. That way, the miners can't get his private key and anyone who does get it can't do anything with it.
And with miners, if they don't receive the double spend transaction, how do they know that a double spend occurred? A smart attacker could simply broadcast the transaction to specific nodes, nodes that he controls, so that the miners only get one transaction and other nodes before them filter out the double spend. That way, the miners can't get his private key and anyone who does get it can't do anything with it.
Quote from: gmaxwell link=https://botbot.me/freenode/bitcoin-wizards/2015-03-22/
E.g. they take 1 BTC, spend it 15 times, miner takes the coins, they get 4 BTC worth of goods from the three successful double spends.
This assumes the current relay rules stay as they are, that is nodes stick to the first version of a doublespend they received (unless they implement replace by fee). If we amend the rules and make nodes accept and relay all conflicting spends (it's up to miners to decide which version eventually gets into a block), then as soon as one honest node learns about a doublespend, all others, including the merchant, will also learn about it within seconds. So if each merchant is connected to at least one honest node and waits for typical propagation latency before recognizing an unconfirmed transaction, the attacker won't be able to get 4 BTC worth of goods. 1 BTC at most, which is the same he would've achieved by acting honestly.
If the attacker is mining, or colludes with a miner, he still can get his doublespend through.
I also disagree with the claim that it in any way addresses nothing-at-stake; in particular it's already common for schemes to suggest that duplicate signatures void coins (which can be done just by system rules without a single show signature) and yet those schemes also do not solve the nothing at stake problem: you cannot punish someone who has left the system and they can produce their conflicting signatures long after leaving it.
Do you believe that the nothing-at-stake problem is unavoidable? Ever better, is there any mathematical proof?
Hi Tonych, it's always good to have more crypto posts here.
This is normally called a single show signature.
If you search the #bitcoin-wizards logs for that term you'll see some instances of this proposal-- you might find it informative.
As you'll probably see in the logs, I disagree with the claims of this approach preventing doublespends. The result of it, at best, is similar to RBF scorched earth, which many people don't consider to be an improvement.
I also disagree with the claim that it in any way addresses nothing-at-stake; in particular it's already common for schemes to suggest that duplicate signatures void coins (which can be done just by system rules without a single show signature) and yet those schemes also do not solve the nothing at stake problem: you cannot punish someone who has left the system and they can produce their conflicting signatures long after leaving it.
There are some pratical concerns as well. For example, now ephemeral data k must be securely stored and if lost result in loss of the key. Signing devices must be carefully stateful and avoid repeated signatures. If the user pays inadequate fees, they'll have no mechenism to revise their transaction to update them-- as even a completely benign double spend (e.g. one that pays the same destination) would result in key loss.
Less importantly, miners also have free pass to ignore the effects of this scheme and there is a simple non-trustless but private protocol possible to allow someone to have a third party privately mine their transactions. (You put up a 25 BTC bond with the miner, and give them the transaction hash you want them to mine, with a promise that you'll instantly give them the full transaction if they present you with a winning block or else forefeit your bond).
This is normally called a single show signature.
If you search the #bitcoin-wizards logs for that term you'll see some instances of this proposal-- you might find it informative.
As you'll probably see in the logs, I disagree with the claims of this approach preventing doublespends. The result of it, at best, is similar to RBF scorched earth, which many people don't consider to be an improvement.
I also disagree with the claim that it in any way addresses nothing-at-stake; in particular it's already common for schemes to suggest that duplicate signatures void coins (which can be done just by system rules without a single show signature) and yet those schemes also do not solve the nothing at stake problem: you cannot punish someone who has left the system and they can produce their conflicting signatures long after leaving it.
There are some pratical concerns as well. For example, now ephemeral data k must be securely stored and if lost result in loss of the key. Signing devices must be carefully stateful and avoid repeated signatures. If the user pays inadequate fees, they'll have no mechenism to revise their transaction to update them-- as even a completely benign double spend (e.g. one that pays the same destination) would result in key loss.
Less importantly, miners also have free pass to ignore the effects of this scheme and there is a simple non-trustless but private protocol possible to allow someone to have a third party privately mine their transactions. (You put up a 25 BTC bond with the miner, and give them the transaction hash you want them to mine, with a promise that you'll instantly give them the full transaction if they present you with a winning block or else forefeit your bond).
Quote
especially those that already have stealth addresses.
Stealth addresses are linearly related, and the relation is known to the paying party. So if I use the stealth address method to create two one show public keys for you and you sign with both of them, I can derrive your private key. I am not aware of a mechenism to securely generate 'stealth address' pubkeys for single show signature without bilinear groups. If not for this a single round trip schnorr treshold signature would be possible. [I hope this point makes it clear how tricky working with an intentionally fragile cryptosystem is, as someone could have followed the suggestion in the original post without realizing that they were giving away their private keys.]
How would this work with address reuse? If someone sets up a donation address, then they can't send Bitcoin from it without having to change the address or reveal their private key.
Also, I don't see how this discourages double spends. If a double spender sends out his two transactions in the traditional race attack, then one will reach some miners, the others will reach other miners, if at all. However, only those nodes that receive both will know that a double spend occurred and only they can get the private key. Those nodes will not broadcast the double spends (unless they are Bitcoin XT) so the double spend transaction won't reach some of the miners. Those who do know the private key after receiving those transactions are at a disadvantage since two transactions have already propagated faster than their own double spend can. Unless they are a miner, then knowing the private key would be pointless.
And with miners, if they don't receive the double spend transaction, how do they know that a double spend occurred? A smart attacker could simply broadcast the transaction to specific nodes, nodes that he controls, so that the miners only get one transaction and other nodes before them filter out the double spend. That way, the miners can't get his private key and anyone who does get it can't do anything with it.
Also, I don't see how this discourages double spends. If a double spender sends out his two transactions in the traditional race attack, then one will reach some miners, the others will reach other miners, if at all. However, only those nodes that receive both will know that a double spend occurred and only they can get the private key. Those nodes will not broadcast the double spends (unless they are Bitcoin XT) so the double spend transaction won't reach some of the miners. Those who do know the private key after receiving those transactions are at a disadvantage since two transactions have already propagated faster than their own double spend can. Unless they are a miner, then knowing the private key would be pointless.
And with miners, if they don't receive the double spend transaction, how do they know that a double spend occurred? A smart attacker could simply broadcast the transaction to specific nodes, nodes that he controls, so that the miners only get one transaction and other nodes before them filter out the double spend. That way, the miners can't get his private key and anyone who does get it can't do anything with it.
It is well known that unconfirmed transactions are not safe because of the risk of double spend. Below is a proposal how to mitigate (not totally eliminate) this risk.
Imagine if the owner of the coin were not able to use his private key more than once, then he wouldn't be able to create another conflicting spend. We cannot take this ability away from him, however we can try to create a strong incentive (like all of Bitcoin which is built upon incentives) not to sign a conflicting transaction.
The good news is it is possible.
Bitcoin's ECDSA private keys can be used to sign any number of transactions. If you use the same address to receive coins and pay from this address for multiple purchases, you are already legitimately using the same private key to sign multiple transactions.
There is another class of signature schemes called "one-time signatures", which sounds like exactly what we need. Lamport signature is the most well known example. By nature of Lamport signature, every time you sign something you reveal a part of your private key, and security level of your second signature is half of security of the first signature. You see that despite the name, Lamport and similar signature schemes are not strictly one-time: if you take a Lamport private key with 128-bit security, your second signature will have security level 64 bit which is still moderately secure. Such slow degradation of security is not suitable for our purpose.
My idea is to modify the plain old ECDSA signature scheme and make it one-time. Here is how we can do it.
Standard ECDSA signature depends on a number k which should be kept private and never reused. ECDSA prescribes that this number should be generated anew for each new signature (randomly or deterministically per RFC 6979). If the same k is used to sign two distinct messages, the private key will be revealed. It is this nice property of ECDSA that I'm going to make use of: require that every signer commits to k at the same time that he generates his private key (and bitcoin address). That is, make k part of private key in the new signature scheme, and the commitment -- part of public key.
Below is full description of one-time ECDSA signature scheme.
Key generation:
Generate standard ECDSA private key as usual.
Generate random k.
oneTimePrivateKey = (standardPrivateKey, k)
Standard public key is x-coordinate of curve point standardPrivateKey x G, where G is generator, x is point multiplication.
Also calculate r as x-coordinate of curve point k x G (it is exactly the r from standard signature (r, s) ).
oneTimePublicKey = ( standardPublicKey, (k x G).x ) = ( standardPublicKey, r )
oneTimeAddress = base58( hash_and_checksum( oneTimePublicKey ) )
Signing:
Standard ECDSA signature is (r, s). r is already known from the public key. Calculate s as usual. Since r is already known from the public key, we can drop it from the signature and keep only s.
Verification:
Reconstruct the standard public key and signature by moving r from public key to the signature and apply standard ECDSA verification procedure.
The end result is, if the user tries to sign a second unconfirmed transaction with one-time private key described above, he will have to reuse k, hence disclose his private key. After his private key is disclosed, anyone can take his coins, the miners are, of course, in the best position to do that (they will not honor transactions that send the spilled coins to any address but theirs).
If the first signature is already deep in the blockchain, the second signature is harmless (unless the user had other unspent outputs on the same address).
This one-time signature scheme is most useful for securing unconfirmed transactions as any potential attacker has to consider the risk that the system strikes back and he loses his coins. Then all potential attackers without access to mining resources are probably out of the game.
Obviously, it is not compatible with address reuse. Also, wallet software has to be redesigned to treat creating a second signature on the same key as silly as posting the private key to facebook. If not forbidden in software, users can be tricked to think their transaction didn't come through for some reason, need to send it again ... private key exposed, coins lost.
Since making address reuse impossible in Bitcoin would require major modifications, and also because PoW already solves double spend problem fairly well, I don't see one-time signatures coming to Bitcoin any time soon. However, they may be a good fit for altcoins and sidechains, especially those that already have stealth addresses.
PoS currencies can use one time signatures to address nothing-at-stake issue and make double-voting too risky (double voting is essentially the same as double spending). To sign more than one block, one can derive consecutive private keys in BIP32 style from a master private key and block number.
I made ECDSA signatures one-timed by having signers commit to k. The same trick can be applied to other signature schemes that involve k, e.g. DSA, Schnorr.
This idea is not quite new, I searched and found a few publications where it was also mentioned:
https://bitcointalksearch.org/topic/ecdsa-2-of-2-signing-511074
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=057011325AE4FA29DFE5401D31C9AD04?doi=10.1.1.40.2274&rep=rep1&type=pdf
Imagine if the owner of the coin were not able to use his private key more than once, then he wouldn't be able to create another conflicting spend. We cannot take this ability away from him, however we can try to create a strong incentive (like all of Bitcoin which is built upon incentives) not to sign a conflicting transaction.
The good news is it is possible.
Bitcoin's ECDSA private keys can be used to sign any number of transactions. If you use the same address to receive coins and pay from this address for multiple purchases, you are already legitimately using the same private key to sign multiple transactions.
There is another class of signature schemes called "one-time signatures", which sounds like exactly what we need. Lamport signature is the most well known example. By nature of Lamport signature, every time you sign something you reveal a part of your private key, and security level of your second signature is half of security of the first signature. You see that despite the name, Lamport and similar signature schemes are not strictly one-time: if you take a Lamport private key with 128-bit security, your second signature will have security level 64 bit which is still moderately secure. Such slow degradation of security is not suitable for our purpose.
My idea is to modify the plain old ECDSA signature scheme and make it one-time. Here is how we can do it.
Standard ECDSA signature depends on a number k which should be kept private and never reused. ECDSA prescribes that this number should be generated anew for each new signature (randomly or deterministically per RFC 6979). If the same k is used to sign two distinct messages, the private key will be revealed. It is this nice property of ECDSA that I'm going to make use of: require that every signer commits to k at the same time that he generates his private key (and bitcoin address). That is, make k part of private key in the new signature scheme, and the commitment -- part of public key.
Below is full description of one-time ECDSA signature scheme.
Key generation:
Generate standard ECDSA private key as usual.
Generate random k.
oneTimePrivateKey = (standardPrivateKey, k)
Standard public key is x-coordinate of curve point standardPrivateKey x G, where G is generator, x is point multiplication.
Also calculate r as x-coordinate of curve point k x G (it is exactly the r from standard signature (r, s) ).
oneTimePublicKey = ( standardPublicKey, (k x G).x ) = ( standardPublicKey, r )
oneTimeAddress = base58( hash_and_checksum( oneTimePublicKey ) )
Signing:
Standard ECDSA signature is (r, s). r is already known from the public key. Calculate s as usual. Since r is already known from the public key, we can drop it from the signature and keep only s.
Verification:
Reconstruct the standard public key and signature by moving r from public key to the signature and apply standard ECDSA verification procedure.
The end result is, if the user tries to sign a second unconfirmed transaction with one-time private key described above, he will have to reuse k, hence disclose his private key. After his private key is disclosed, anyone can take his coins, the miners are, of course, in the best position to do that (they will not honor transactions that send the spilled coins to any address but theirs).
If the first signature is already deep in the blockchain, the second signature is harmless (unless the user had other unspent outputs on the same address).
This one-time signature scheme is most useful for securing unconfirmed transactions as any potential attacker has to consider the risk that the system strikes back and he loses his coins. Then all potential attackers without access to mining resources are probably out of the game.
Obviously, it is not compatible with address reuse. Also, wallet software has to be redesigned to treat creating a second signature on the same key as silly as posting the private key to facebook. If not forbidden in software, users can be tricked to think their transaction didn't come through for some reason, need to send it again ... private key exposed, coins lost.
Since making address reuse impossible in Bitcoin would require major modifications, and also because PoW already solves double spend problem fairly well, I don't see one-time signatures coming to Bitcoin any time soon. However, they may be a good fit for altcoins and sidechains, especially those that already have stealth addresses.
PoS currencies can use one time signatures to address nothing-at-stake issue and make double-voting too risky (double voting is essentially the same as double spending). To sign more than one block, one can derive consecutive private keys in BIP32 style from a master private key and block number.
I made ECDSA signatures one-timed by having signers commit to k. The same trick can be applied to other signature schemes that involve k, e.g. DSA, Schnorr.
This idea is not quite new, I searched and found a few publications where it was also mentioned:
https://bitcointalksearch.org/topic/ecdsa-2-of-2-signing-511074
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=057011325AE4FA29DFE5401D31C9AD04?doi=10.1.1.40.2274&rep=rep1&type=pdf
Jump to: