How is same signed transaction not reusable, also quantum security of ECDSA?

[AnonyMint]

Please excuse my raw ignorance, could someone be so kind as to explain to me how Bitcoin prevents a same signed transaction from being reused in a subsequent block to send the same amounts from the same inputs to the same outputs again? Is there a Nonce hashed in the signature and the Nonce is also retrievable?

Tangentially I understand a Nonce is part of the ECDSA algorithm and that can be problematic if the RNG is defective:

http://blog.cryptographyengineering.com/2012/03/surviving-bad-rng.html
http://bitcoin.stackexchange.com/questions/12879/would-a-transition-to-a-different-signature-scheme-be-feasible
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Security

My second question is there any signature algorithm that is both quantum secure and can have unlimited use (data size of the signature is not a concern in my case, yet data size of the public key needs to be compact):

http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-and-how-we-can-fix/

Third question is doesn't the above obviate one of the reasons given for allowing multiple transaction outputs (i.e. sending change to yourself), and leave only remaining dubious justification?

http://bitcoin.stackexchange.com/questions/1629/why-does-bitcoin-send-the-change-to-a-different-address#comment2088_1637

[1714192701]

1714192701

[1714192701]

1714192701

[gmaxwell]

Please excuse my raw ignorance,

To correct this ignorance please start by reading the Bitcoin whitepaper: http://bitcoin.org/bitcoin.pdf

and erase from your mind the memory of any block explorer, as they're misleading.

could someone be so kind as to explain to me how Bitcoin prevents a same signed transaction from being reused in a subsequent block to send the same amounts from the same inputs to the same outputs again? Is there a Nonce hashed in the signature and the Nonce is also retrievable?

It sounds as though you believe the Bitcoin system tracks balances. This is a common misunderstanding created by the cooked interfaces shown in popular block explorers. The backend system in bitcoin has no concept of a balance and basically no concept of an address even.

Bitcoin tracks atomic coins (transaction outputs). Each coin is unique and can only ever be spent once. A replay of a transaction would just be invalid because the coin it spent has already been consumed.

Systems based on balances have many complicated race conditions far beyond the problem of a simple spend replay.

My second question is there any signature algorithm that is both quantum secure and can have unlimited use (data size of the signature is not a concern in my case, yet data size of the public key needs to be compact)

A merkle signature system can have arbitrary reuse levels with constant size public keys and either linear increases in generation time and log increases in signature size, or log increases in generation time and polylogarithmic increases in signature size.

Besides, lamport signatures don't lose all their security at once, the fact that the blockchain looks like a guy fawkes signature system itself means that short term somewhat fragile signatures are probably pretty harmless.

Third question is doesn't the above obviate one of the reasons given for allowing multiple transaction outputs (i.e. sending change to yourself), and leave only remaining dubious justification?

Allowing multiple outputs is deeply fundamental to the system, a point which is more obvious once you're not under the impression that Bitcoin keeps balances: spending consumes the inputs completely, so multiple outputs are required in order to receive your change.

The use of new addresses for change is important because the privacy of the system is paper thin and rests entirely on the weak pseudo-anonymity of using a unique address for every transaction.  If addresses are reused a party analyzing the highly public transaction log can trivially reach conclusions about who owns what.  Few people would want to use a system where their barresta can see their paycheck and their grandkid crazy nosy in-laws can see them buying contraception.

[AnonyMint]

Thank you for the reply.

Please excuse my raw ignorance,

To correct this ignorance please start by reading the Bitcoin whitepaper: http://bitcoin.org/bitcoin.pdf

and erase from your mind the memory of any block explorer, as they're misleading.

I did re-scan the Satoshi whitepaper before posting this question. I did consider that if the entire input is spent, then it couldn't be re-spent. However, the following comment from Gavin Andresen led me to believe it was possible to send the change back to the sending address:

http://bitcoin.stackexchange.com/questions/1629/why-does-bitcoin-send-the-change-to-a-different-address#comment2139_1629

Also the following comment by cdecker implied that less than the entire balance at an address could be sent as an input to another address:

http://bitcoin.stackexchange.com/questions/12735/multiple-outputs-address-forking#comment16483_12737

Also the following answer from ripazha lead me to believe that it is possible to do what Gavin Andresen mentioned.

http://bitcoin.stackexchange.com/a/12750

I've looked again at the 2. Transactions section of the Satoshi paper, it doesn't appear to say anything relevant. And in the 7. Reclaiming Disk Space section, Satoshi wrote, "Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space". That seems to imply that there can be multiple transactions per coin and thus partial spends of a coin balance. The section 9. Combining and Splitting Value doesn't appear to provide an unambiguous relevant specification either.

Does anyone know of any documentation that specifies this clearly, concisely, and unambiguously? My google foo didn't turn up anything. I did peruse the Bitcoin wiki hits that showed in google and didn't find anything, at least not concise.

could someone be so kind as to explain to me how Bitcoin prevents a same signed transaction from being reused in a subsequent block to send the same amounts from the same inputs to the same outputs again? Is there a Nonce hashed in the signature and the Nonce is also retrievable?

It sounds as though you believe the Bitcoin system tracks balances. This is a common misunderstanding created by the cooked interfaces shown in popular block explorers. The backend system in bitcoin has no concept of a balance and basically no concept of an address even.

Bitcoin tracks atomic coins (transaction outputs). Each coin is unique and can only ever be spent once. A replay of a transaction would just be invalid because the coin it spent has already been consumed.

Isn't an address a coin? When multiple inputs are sent to my public key, that creates a new coin with that value? So if the change is sent back to the same address (coin) as one of the inputs, then what prevents a replay of that transaction until the change is exhausted?

Systems based on balances have many complicated race conditions far beyond the problem of a simple spend replay.

Interesting. Does anyone know where I can read more about this, or can someone provide some cases?

I can't fathom a race condition, except within the same block with multiple transactions to spend more than the available balance, then which transactions to reject and which to allow. Yet I don't see how this is different then sending double-spends from the same coin in Bitcoin in the same block. In both cases, all the transactions should be rejected.

Third question is doesn't the above obviate one of the reasons given for allowing multiple transaction outputs (i.e. sending change to yourself), and leave only remaining dubious justification?

Allowing multiple outputs is deeply fundamental to the system, a point which is more obvious once you're not under the impression that Bitcoin keeps balances: spending consumes the inputs completely, so multiple outputs are required in order to receive your change.

The use of new addresses for change is important because the privacy of the system is paper thin and rests entirely on the weak pseudo-anonymity of using a unique address for every transaction.  If addresses are reused a party analyzing the highly public transaction log can trivially reach conclusions about who owns what.  Few people would want to use a system where their barresta can see their paycheck and their grandkid crazy nosy in-laws can see them buying contraception.

But I can send the change back to my spending address?

Seems that research has shown that maintaining privacy (not to mention anonymity) utilizing this fan-out is not going to work for those who don't know what they are doing (carefully and meticulously), i.e. it won't work well for most everyone? (at least at this time, and) I realize you are trying to improve on this with your CoinJoin efforts. I can't comment on whether CoinJoin will make this easy enough for the mainstream, but I can at least say I am skeptical but have only spent a modicum of time thinking about it. I hope something very easy-to-use and effective will come from that, because I do want to use Bitcoin with increased privacy (and I would like anonymity also).

[cp1]

Even if the coins were sent back to the same address they would have different unspent transaction output IDs.

[AnonyMint]

Even if the coins were sent back to the same address they would have different unspent transaction output IDs.

So the spending signature incorporates the transaction output IDs?

I am trying to get at the why the signature can't be reused.

[cp1]

Yeah, check out this demo in creating a raw transaction:  https://people.xiph.org/~greg/signdemo.txt

[bitfair]

Even if the coins were sent back to the same address they would have different unspent transaction output IDs.

So the spending signature incorporates the transaction output IDs?

I am trying to get at the why the signature can't be reused.

A transaction consists of a list of inputs (IDs of previous transactions + the number of the output in that transaction), then a list of outputs (address + amount of BTC to send to that address, up to a maximum of the sum total of the inputs). The hash of these two lists is then signed with the ECDSA keys referenced in the input list.

If any of the inputs have been spent before (i.e. it appears in the list of inputs to another transaction already in the blockchain), then the transaction will be discarded and won't be mined.

Also, if you try to reuse the signature from one transaction on another transaction, then the old signature will not be valid for the new transaction, because the hash is different. I.e. the signature signs the hash of the transaction using the ECDSA key, and will not be valid for other transactions because they have a different hash.

Does that answer the question? [And for you smart guys: did it answer it correctly?;]

[AnonyMint]

Thanks guys. So the one sentence answer to my OP is "yes the Nonce is the txid". So my OP logical assumption was correct; it can't be any other way, either the input address is spent entirely and is never used again, else the signature must sign a Nonce.

If Bitcoin used Lamport signatures (secure against quantum computers) instead, then it should enforce that the output change was send to a new public address (to guard against user error), since Lamport signatures are only secure if used once. Thus the Nonce wouldn't be necessary for preventing this sort of replay (I am not asserting whether the txid would still be required for other reasons).

Note the the P-256 version of ECDSA that Bitcoin is using has recently become untrusted by some (more than one person):

http://crypto.stackexchange.com/questions/10263/should-we-trust-the-nist-recommended-ecc-parameters

And ECDSA was never trusted as much as RSA by that someone important (and both are compromised if there exists a quantum computer):

https://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography

Even shifting to Berstein's  curve25519 (as Tor and others are)...

http://stackoverflow.com/questions/2515948/use-of-curve25519
http://bitcoin.stackexchange.com/questions/12879/would-a-transition-to-a-different-signature-scheme-be-feasible

....doesn't alleviate the (perhaps slim) possibility that the NSA already has a quantum computer because if anyone has invented one the NSA has certainly put a National Security Letter on it or done what ever necessary to keep it secret:

http://www.wired.com/opinion/2013/09/black-budget-what-exactly-are-the-nsas-cryptanalytic-capabilities/

Remember throughout the 70s and 80s, the NSA secretly had differential cryptoanalysis and didn't announce that they could break most existing crypto.

Note actual size of the black budget is in the $trillions, i.e. two orders-of-magnitude larger than published by Snowden:

http://solari.com/archive/missing_money/ (Catherine Austin Fitts, former assistant to secretary of HUD)
http://screwloosechange.blogspot.com/2006/11/missing-trillions.html (counter-argument)
http://armstrongeconomics.com/2013/08/10/platinum/

I had all the names and who was paid what in Russia by whom. That is part of what was taken by the government and then it miraculously was destroyed in World Trade Center building 7 that collapsed with nothing hitting it. The SEC replied to my request for my files saying they were all destroyed in WTC 7 (see below). Curious as well, the plane that hit the Pentagon hit the records room where everything was documenting the missing $2.3 trillion that Rumsfeld admitted the day before. While I am not a big proponent of conspiracy stories, I do not put it past the government...

Note those who doubt what Schneier has seen in the Snowden documents should note implied attempts from Intel to pollute all RNG:

https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J

And the NSA (Never Say Anything) has been caught lying in public under oath:

https://www.schneier.com/blog/archives/2013/09/conspiracy_theo_1.html

Refer to the link in my OP about how important is that we insure our RNG implementations have sufficient entropy.

Bitcoin's non-balances design probably doesn't not let it switch (the design and implementation) from 20 byte to 16KB public keys, and to 8KB signatures.

This is a major revelation for me about Bitcoin insecurity. I no longer unequivocally trust Bitcoin against the NSA, nor the future in general.

I hope the gravity of this post is understood. I am pointing out that the entire design of the block chain probably has to change to balances in order to be surely secure. However, what is the range of harm the attacker could do?

the fact that the blockchain looks like a guy fawkes signature system itself means that short term somewhat fragile signatures are probably pretty harmless.

As the link I provided in the OP explains, if there exists a quantum computer, as soon as you attempt to spend your Bitcoin, you are vulnerable. But what could the attacker do? If they controlled the winning mining peer for that block, they could steal the value in the coin. Even if they didn't control the winning block, they could send double-spends in the same block and thus causing a race condition and the value to be unspendable. This could cause people to not trust Bitcoin and BTC exchange value could plummet. The community could attempt a solution, yet it would necessarily require loss of some decentralization and/or anonymity during the transition to prove your signature is the first (or valid) one and not the attacker's.

[gmaxwell]

Thanks guys. So the one sentence answer to my OP is "yes the Nonce is the txid". So my OP logical assumption was correct;

This might functionally result in reaching the same conclusion in this case, but it still sounds like your understanding is incomplete.

In no place does Bitcoin have or maintain a balance. It doesn't even really have any concept of addresses (except in the front end wallet software) transaction outputs just list rules which must be satisfied to consume them.   A transaction selects outputs by txid:vout and satisfies their rules. Nowhere is the prior coin's to 'address' repeated in the spending transaction. Every coin is distinct, identified by its output index and the txid that created it. Every transaction names the coins which it is consuming and the txid:vout is the only specification of what coins are being spent. Every coin is consumed completely.

If Bitcoin used Lamport signatures (secure against quantum computers) instead, then it should enforce that the output change was send to a new public address (to guard against user error), since Lamport signatures are only secure if used once.

This would be a somewhat pointless restriction at the network level.  If users want to leak their private keys they are free to do this in many ways and it cannot be prevented.  The interesting case is when someone sends a second payment (perhaps at the same time as a first) to the same scriptPubKey requiring two signatures. Your rule would not prevent this, but a simple merkle signature scheme would remove this bit of brittleness without unduly constraining users or slowing transaction processing by requiring more database queries to check for admissible transactions.

(oh how I'd love to reject sending change to yourself today so that ignorance client authors couldn't crap so easily over the privacy of all Bitcoin users and the fungibility of Bitcoin as a side effect, but alas, this is now politically impossible.  ... but my point here is that it would kinda be a pointless security improvement in anycase. The possibility of payments strongly encourages the use of merkle signatures...)

Note the the P-256 version of ECDSA that Bitcoin is using has recently become untrusted by some (more than one person)

Bitcoin does NOT use the NIST P-256 curve. Please spend a moment of your time researching before spreading FUD, especially FUD magnified by language like "the gravity of this post". Remember the story of chicken little.

The curve we use has its parameters fixed by performance considerations, similar to the construction of the curve used by Ed25519 (though not quite identical performance considerations) and is not one of the NIST curves.

the fact that the blockchain looks like a guy fawkes signature system itself means that short term somewhat fragile signatures are probably pretty harmless.

As the link I provided in the OP explains, if there exists a quantum computer, as soon as you attempt to spend your Bitcoin, you are vulnerable. But what could the attacker do? If they controlled the winning mining peer for that block, they could steal the value in the coin.

I was responding specifically to your comment about lamport signature reuse. A single duplicated spend for a lamport key reduces the effective key-size by half on average (and you can reduce this somewhat with modest computation by choosing a pair of messages which have a minimum hamming distance), which is not great, but you're generally only concerned with the exposure between the time you spend and the time your transaction is buried in the chain.

Though you're likely exaggerating the risk in the ECDSA case, "if there exists" is not sufficient. Even ignoring the (probably enormous) overhead of the required error correction, solving a 256 bit discrete log problem on a QC requires a QC with thousands of bits of state to perform billions of operations. To perform any attack at all you must not have a unicorn"QC" but a rather large one and because the exposure time (assuming keys are not being reused) is only however long it takes to get a transaction mined, the window of your attack is somewhat limited.

In any case, Bitcoin was designed to be forward adaptive and new signature cryptosystems could be deployed very rapidly and completely compatibly with existing software.

Bitcoin's non-balances design probably doesn't not let it switch (the design and implementation) from 20 byte to 16KB public keys, and to 8KB signatures.

This is more uninformed confusion. Lamport/merkle signatures can have compact (e.g. 256 bit) public keys just fine, and an implementation of hash based checksig in Bitcoin is under 500 lines of code. Because of the possibility of tree compression to reduce pubkey and signature size public keys for lamport signatures would always be handled this way by anyone that cares at all about bandwidth.

Nothing in the design inhibits the usage of lamport or other post-quantum signature systems in the slightest, except that the system is predicated on a trustless globally visible consensus model, which means that the storage and bandwidth costs of transactions is very important, and thus larger transactions mean a corresponding reduction in capacity.

Balances have basically no bearing on this, and a balance based bitcoin would have far less than the already paper thin privacy of the current system.

[gmaxwell]

Systems based on balances have many complicated race conditions far beyond the problem of a simple spend replay.

Interesting. Does anyone know where I can read more about this, or can someone provide some cases?

I can't fathom a race condition, except within the same block with multiple transactions to spend more than the available balance, then which transactions to reject and which to allow. Yet I don't see how this is different then sending double-spends from the same coin in Bitcoin in the same block. In both cases, all the transactions should be rejected.

Double spends are not always malicious.

In a balance based system:

Alice has 2.1 BTC.
Alice pays Bob 1 BTC.
Alice pays Carol 1 BTC.

The transactions are taking a long time to confirm because Alice did not include a fee. Four hours later Bob is angry and threatening to cancel the deal.

Alice rewrites Bob's transaction, this time including a transaction fee.  Then bob gets paid twice and carol doesn't get paid.  Bitcoin has no such problem, and you can productively use non-malicious double spends to create intentionally mutually exclusive transactions to positive effect... both for replacements, as in this example, and also in more complex protocols (like auctions).

Etc.  You end up having to to obnoxious things like basically emulating a non-balance system with most coins sent to distinct addresses and never accepting a payment from an address that has another outgoing payment... or the likewise to close these holes. The net net is something which is more complicated and has the overhead of maintaining balance indexes as well as still tracking individual coins.  I'm sure they could all be closed, but it's tricky and it doesn't appear that you usefully get anything out of it, except now that privacy takes an even more concerted effort to maintain.

[AnonyMint]

Thanks guys. So the one sentence answer to my OP is "yes the Nonce is the txid". So my OP logical assumption was correct;

This might functionally result in reaching the same conclusion in this case, but it still sounds like your understanding is incomplete.

In no place does Bitcoin have or maintain a balance.

You first raised the issue of balances in this thread. In the OP, I admitted my understanding was incomplete (of the details), yet no where in the OP did my logic assert balances in Bitcoin. I asserted that whatever Bitcoin is doing it had to be a Nonce in the transaction signature. I was correct in my logic. My mind often works in generative essence mode, meaning I distill away details down to the essence so I can factor the domain efficiently (especially initially in a field where my detailed domain knowledge is weak).

If Bitcoin used Lamport signatures (secure against quantum computers) instead, then it should enforce that the output change was send to a new public address (to guard against user error), since Lamport signatures are only secure if used once.

This would be a somewhat pointless restriction at the network level.  If users want to leak their private keys they are free to do this in many ways and it cannot be prevented.

I did realize they could reuse the key again later, e.g. sending from key that received the change back to the key they previously spent from. And a system that employed balances and discarded transaction records after some interval, would not be able to prevent this.

I didn't think it is entirely pointless since a Lamport signature is so brittle. However...

The interesting case is when someone sends a second payment (perhaps at the same time as a first) to the same scriptPubKey requiring two signatures.

Here is where my detailed domain knowledge is weak. I don't understand this. I am thinking a coin is spent only once entirely and its change it sent to another key.

Your rule would not prevent this, but a simple merkle signature scheme would remove this bit of brittleness without unduly constraining users or slowing transaction processing by requiring more database queries to check for admissible transactions.

In what way does forcing all of a coin to be spent and change sent to another key constrain users?

I will leave the performance claim on the back-burner, since it may be irrelevant or not, and would require much more study.

(oh how I'd love to reject sending change to yourself today so that ignorance client authors couldn't crap so easily over the privacy of all Bitcoin users and the fungibility of Bitcoin as a side effect, but alas, this is now politically impossible.  ... but my point here is that it would kinda be a pointless security improvement in anycase. The possibility of payments strongly encourages the use of merkle signatures...)

Payments? You mean a fan-out of more than 2? Why does that conflict with my assumption above?

Note the the P-256 version of ECDSA that Bitcoin is using has recently become untrusted by some (more than one person)

Bitcoin does NOT use the NIST P-256 curve. Please spend a moment of your time researching before spreading FUD, especially FUD magnified by language like "the gravity of this post". Remember the story of chicken little.

The curve we use has its parameters fixed by performance considerations, similar to the construction of the curve used by Ed25519 (though not quite identical performance considerations) and is not one of the NIST curves.

Mea culpa, I missed the one letter difference ("k" instead of the "r"):

https://bitcointalk.org/index.php?topic=151120.0

Note the above link and the following have no proof that it is not a honeypot:

https://bitcointalk.org/index.php?topic=2699.msg37328#msg37328

The doubt raised for P-256 is that NIST is working hard to pollute standards, the seeds were not chosen in a way that involved no human judgement, and the same problem exists for the "k" standard. And it has been chosen by someone anonymous (Satoshi) with no justification and we also have some reason to suspect Satoshi wasn't some unfunded cryptographer acting alone.

I am not spreading FUD, rather the FACT that we don't have the usual safeguards as was the case for SHA-1 which had seeds sqrt(1), sqrt(2), etc.

Blind faith is for religion.

the fact that the blockchain looks like a guy fawkes signature system itself means that short term somewhat fragile signatures are probably pretty harmless.

As the link I provided in the OP explains, if there exists a quantum computer, as soon as you attempt to spend your Bitcoin, you are vulnerable. But what could the attacker do? If they controlled the winning mining peer for that block, they could steal the value in the coin.

I was responding specifically to your comment about lamport signature reuse. A single duplicated spend for a lamport key reduces the effective key-size by half on average (and you can reduce this somewhat with modest computation by choosing a pair of messages which have a minimum hamming distance), which is not great, but you're generally only concerned with the exposure between the time you spend and the time your transaction is buried in the chain.

Though you're likely exaggerating the risk in the ECDSA case, "if there exists" is not sufficient. Even ignoring the (probably enormous) overhead of the required error correction, solving a 256 bit discrete log problem on a QC requires a QC with thousands of bits of state to perform billions of operations.

If you don't also have a weak curve, nor some publicly unknown new algorithm.

Fact is that we are using shorter bit lengths, because we think ECC is more difficult to hack. Why has the NSA pushed the ECC, when we could be using longer key lengths with Lamport or Merkel on factoring algorithms that have been more well studied. The fact that there are so many variants of ECC curves means there is so much more domain to study.

I don't trust it. NSA has been pushing it.

To perform any attack at all you must not have a unicorn"QC" but a rather large one and because the exposure time (assuming keys are not being reused) is only however long it takes to get a transaction mined, the window of your attack is somewhat limited.

Unless you control much of the hash power and can delay transactions. And where is Bitcoin headed now with pools and ASICs.

In any case, Bitcoin was designed to be forward adaptive and new signature cryptosystems could be deployed very rapidly and completely compatibly with existing software.

Yet everyone has to sign first with their ECC keys and so my point about losing decentralization and/or anonymity during the transition remains.

Bitcoin's non-balances design probably doesn't not let it switch (the design and implementation) from 20 byte to 16KB public keys, and to 8KB signatures.

This is more uninformed confusion. Lamport/merkle signatures can have compact (e.g. 256 bit) public keys just fine, and an implementation of hash based checksig in Bitcoin is under 500 lines of code. Because of the possibility of tree compression to reduce pubkey and signature size public keys for lamport signatures would always be handled this way by anyone that cares at all about bandwidth.

I am not knowledgeable about how much they can be compressed, yet I think the signatures are larger than ECDSA.

Nothing in the design inhibits the usage of lamport or other post-quantum signature systems in the slightest, except that the system is predicated on a trustless globally visible consensus model, which means that the storage and bandwidth costs of transactions is very important, and thus larger transactions mean a corresponding reduction in capacity.

Exactly. And note the comment about pools above.

Balances have basically no bearing on this, and a balance based bitcoin would have far less than the already paper thin privacy of the current system.

I don't believe this to be true at this point in my study. But I guess we'd need to explore a balances design to have this discussion? You raised balances in this thread and I followed through, since indeed I am thinking about the merits of a balances design (i.e. a fixed Mini-Block Chain).

[AnonyMint]

Systems based on balances have many complicated race conditions far beyond the problem of a simple spend replay.

Interesting. Does anyone know where I can read more about this, or can someone provide some cases?

I can't fathom a race condition, except within the same block with multiple transactions to spend more than the available balance, then which transactions to reject and which to allow. Yet I don't see how this is different then sending double-spends from the same coin in Bitcoin in the same block. In both cases, all the transactions should be rejected.

Double spends are not always malicious.

In a balance based system:

Alice has 2.1 BTC.
Alice pays Bob 1 BTC.
Alice pays Carol 1 BTC.

The transactions are taking a long time to confirm because Alice did not include a fee. Four hours later Bob is angry and threatening to cancel the deal.

Alice rewrites Bob's transaction, this time including a transaction fee.  Then bob gets paid twice and carol doesn't get paid.  Bitcoin has no such problem, and you can productively use non-malicious double spends to create intentionally mutually exclusive transactions to positive effect... both for replacements, as in this example, and also in more complex protocols (like auctions).

Etc.  You end up having to to obnoxious things like basically emulating a non-balance system with most coins sent to distinct addresses and never accepting a payment from an address that has another outgoing payment... or the likewise to close these holes. The net net is something which is more complicated and has the overhead of maintaining balance indexes as well as still tracking individual coins.  I'm sure they could all be closed, but it's tricky and it doesn't appear that you usefully get anything out of it, except now that privacy takes an even more concerted effort to maintain.

Why is that example better than forcing all coins to spent entirely and change to be sent to another coin? If Alice wants to pay two in the same block, she can use a fan-out of 3 (1 is for the change).

Then Bob doesn't get paid twice and Carol doesn't get cheated out of her payment.

And then we don't have race conditions nor need such a complex logic for a balances system.

I don't know what you are thinking about auctions, while I am thinking orthogonal block chains (merged mined) can be built for esoteric features.

As for what we might gain with a balances system (more study needed though):

1. Decentralization since peers don't need so much resources (RAM, CPU, and network bandwidth).

2. Block chain scaling to Visa scale.

3. Replace ECDSA with lamport or Merkel with huge key lengths (e.g. 4096 bit). Public key hashes might remain 256-bit.

4. Radically improved anonymity per my posts you moved out of your CoinJoin thread.

[gmaxwell]

I am not spreading FUD, rather the FACT that we don't have the usual safeguards as was the case for SHA-1 which had seeds sqrt(1), sqrt(2), etc.

Actually, we have a stronger assurance than for SHA-1. The parameters in secp256k1 (which is not a NIST selected curve, contrary to your repeated instance) are fixed entirely by performance considerations, similar to the Ed25519 work which you lauded up-thread. There (far) are fewer degrees of freedom in secp256k1 than in SHA1.

This isn't to say that it might not turn out that there are snazzy new mathematical weaknesses possible, but there appears to be no room to have forced the selection of them. ... and snazzy new mathematical weaknesses are possible for anything. As soon as you've gone down the paranoid path of ANYTHING IS POSSIBLE OMG.  ... Well, anything is possible, and anything else might be insecure for unknown reasons too.

I am not knowledgeable about how much they can be compressed, yet I think the signatures are larger than ECDSA.

Yes, the signatures are larger. But you were saying

Bitcoin's non-balances design probably doesn't not let it switch (the design and implementation) from 20 byte to 16KB public keys, and to 8KB signatures. This is a major revelation for me about Bitcoin insecurity.

Which is just @#$@#$ nonsense, and I was responding pointing out that public keys would be no larger, and so your invocation of balances is just hysterical jibberish.

You've continually repeated misinformation in this thread (and in other threads, now that I connect your name). I realize that it's due to your ignorance and not due to malice, but it means that interacting with you is a waste of time.  ... and I'm worried that I'm rewarding your poor understanding and poor research by continuing to respond to ridiculous claims.

Do your own work for a bit, instead of making me feel like you're just converting every doubt you have into a FUDdy misstatement of fact in order to make other people do the work in refuting you.

Why is that example better than forcing all coins to spent entirely and change to be sent to another coin?

Because that is an emulation of exactly what we have now!  It's fine but it's effectively what we have now. Jesus.

As for what we might gain with a balances system (more study needed though):

None of these things follow from that premise. You might as well have listed "Peace on earth and goodwill towards men".  We can already deploy merkel signatures, with no incompatibility at all—(many) existing clients can already send coins to them, and would deploy them in weeks if there were ever an indication of our current checksig becoming weak. "Balances" are entirely orthogonal.

[AnonyMint]

(which is not a NIST selected curve, contrary to your repeated instance)

Hey you keep trying to put words in my mouth that I have not written.

Please learn to read more carefully. Go back and re-read my post please. I never insisted nor asserted that in the last reply that you are replying to.

I will kindly ask you to stop trolling, even though you are the moderator. You first asserted that I was talking about balances and went into long diatribes, when in fact my logic was correct and I never mentioned balances nor alluded to them.

You are hearing voices apparently.

[jl2012]

Using merklized key, a Lamport public key could be reused (for limited times) https://en.wikipedia.org/wiki/Lamport_signature#Public_key_for_multiple_messages

Using CHECKSIG 2.0 I proposed at https://bitcointalk.org/index.php?topic=258931.0 , we can use one signature for many inputs from the same "address"

[AnonyMint]

...similar to the Ed25519 work which you lauded up-thread...

I had enough of your insults.

You need to work on your reading comprehension. Let me re-quote what I wrote about Ed25519, "Even shifting to Berstein's  curve25519 (as Tor and others are).......doesn't alleviate the (perhaps slim)".

Now I will compose a response to the points you've made.

[AnonyMint]

I am not spreading FUD, rather the FACT that we don't have the usual safeguards as was the case for SHA-1 which had seeds sqrt(1), sqrt(2), etc.

Actually, we have a stronger assurance than for SHA-1.

No you do not! Are you sure you are qualified as a cryptographer?

The parameters in secp256k1 (which is not a NIST selected curve, contrary to your repeated instance) are fixed entirely by performance considerations, similar to the Ed25519 work which you lauded up-thread. There (far) are fewer degrees of freedom in secp256k1 than in SHA1.

I did not laud Ed25519. Performance "considerations" is a human value judgement, assuming the performance domain has not been provably explored to its limits, thus the lower degrees-of-freedom claim is vacuous. (I wonder how many readers have the IQ to comprehend that? I hope many) Additionally the orthogonal point that focusing on performance is not same as focusing on security considerations. I don't know all the details, but Bernstein did apparently at least include some security considerations (some mention about primes, etc) too, nevertheless that is orthogonal to my first point. Also the third orthogonal point that I see merit in Schneier's logic on not using ECC unless it is necessary (some of his reasons I repeated in my prior post in this thread, yet you should read his words).

This isn't to say that it might not turn out that there are snazzy new mathematical weaknesses possible, but there appears to be no room to have forced the selection of them. ... and snazzy new mathematical weaknesses are possible for anything. As soon as you've gone down the paranoid path of ANYTHING IS POSSIBLE OMG.  ... Well, anything is possible, and anything else might be insecure for unknown reasons too.

As Schneier says we play the best odds. And as cryptographers we shouldn't take risks that can be avoided.

ECC has a few reasons to be suspected (read Schneier's words), and specific curves even more suspect and I included suspicion on the k variant used by Bitcoin with the justifications upthread.

And it is not just the mathematical attack, it is that there are 4 or more possible attacks combined:

1. Mathematical attack given shorter keys
2. Quantum Computer with Shor's algorithm
3. NSA possibility planted weak curves in standards
4. NSA possibility attempting to weaken many RNGs (this affects all crypto, but adds to the 3 above giving them more weight)

I am not knowledgeable about how much they can be compressed, yet I think the signatures are larger than ECDSA.

Yes, the signatures are larger. But you were saying

Bitcoin's non-balances design probably doesn't not let it switch (the design and implementation) from 20 byte to 16KB public keys, and to 8KB signatures. This is a major revelation for me about Bitcoin insecurity.

Which is just @#$@#$ nonsense, and I was responding pointing out that public keys would be no larger, and so your invocation of balances is just hysterical jibberish.

It is my understanding that the entire history of unpruned signatures are stored in the block chain.

My current understanding is that a balances design would not require such an extensive history of signatures.

You've continually repeated misinformation in this thread (and in other threads, now that I connect your name). I realize that it's due to your ignorance and not due to malice, but it means that interacting with you is a waste of time.  ... and I'm worried that I'm rewarding your poor understanding and poor research by continuing to respond to ridiculous claims.

I will grant you are good at insults and judging others.

Perhaps if you slow down and give others a chance to present their responses to your thoughts, we could get to a conclusion and then know what is what.

It may be that I am entirely wrong, but I don't see you've made all the winning points yet.

And even if you are entirely correct, the entire point of discussion is to help clarify everything. So how is that a waste of time? You ask for donations for helping, yet then hurl insults. I was actually earlier thinking about sending you 0.1 BTC as a token of my appreciation and was even not offended by your initial diatribe about balances that didn't come from anything I wrote in my OP.

I figured you were helping me any way, even if you seem so cocky to assume that others are idiots and must be thinking stupid.

But now you've gone completely overboard with your personality and comprehension defects.

Do your own work for a bit, instead of making me feel like you're just converting every doubt you have into a FUDdy misstatement of fact in order to make other people do the work in refuting you.

Refutation (entertaining potential issues and then proving they are not an issue) is one of the most important jobs of a cryptographer and security analyst isn't it?

You should applaud probing.

Rather I detect that you are angry that you would offer any assistance to anyone who might upset the Bitcoin applecart or create an alternative coin. Sorry if I refuted resoundingly what you probably thought were slamdunks to shut me up. My IQ tends to find the maximum breadth tree of possibilities, so you better make sure there is no stone unturned before you cockeyed (as in cocky) assume you've won an argument with me.

It is necessary that in the process of everything assistance will flow around. That is how open source and academic research works.

If Bitcoin is rock solid, it will all flow back mostly to Bitcoin any way. I want the best coin, and if it ends up Bitcoin, then great.

So far, I think my logic is sound, yet I am open to any convincing logic you can present. But it is clearly becoming very difficult to have any discussion with you that doesn't conform to your biased vested interests.

I am trying to look at this objectively. We shouldn't take risks if there are not tradeoffs to not taking them. Note I did specifically write "need more study" above, so I am not yet asserting there are no counter-balancing tradeoffs.

Why is that example better than forcing all coins to spent entirely and change to be sent to another coin?

Because that is an emulation of exactly what we have now!  It's fine but it's effectively what we have now. Jesus.

You conflate orthogonal concerns.

While we may have feature A now, we may still have feature A and get rid of a doubt that we don't need, while gaining other features too. Maybe without tradeoffs, but I am not asserting that "until more study".

You are really frightened of any talk about an alternative coin design.

As for what we might gain with a balances system (more study needed though):

None of these things follow from that premise. You might as well have listed "Peace on earth and goodwill towards men".  We can already deploy merkel signatures, with no incompatibility at all—(many) existing clients can already send coins to them, and would deploy them in weeks if there were ever an indication of our current checksig becoming weak. "Balances" are entirely orthogonal.

Then the Bitcoin blockchain bloat will grow worse due to longer signatures and that may be a factor that is driving centralization of pools. And other considerations...

Because that is an emulation of exactly what we have now!  It's fine but it's effectively what we have now. Jesus.

So deploy them now to eliminate the doubt if you conflate the tradeoffs because you assert by implication there are none.

And don't wait until after the attack has started, because then weeks will be weeks too late.

Jesus indeed, especially the humorous part about my ignorance. Got a mirror handy?

[AnonyMint]

Cripes even you admit the higher probability of the vulnerability of the math:

The SEC random curves have "random numbers" in them, but are they really random?

FWIW, the "random" curves have their parameters selected by a deterministically random machine search... this seems like it would have made choosing their parameters maliciously even harder.

I do sometimes worry about ECC since there are techniques for DLP solving which have scalability more like modern factoring but which (currently) only apply to supersingular curves. If someone figures out how to apply them to ordinary curves, e.g. by solving a related problem on extension fields, we'd need to use ECC with more RSA like key sizes to obtain comparable security.

Fortunately none of this is fundamental to Bitcoin— Bitcoin could add another checksig operator very quickly if there appeared to be an urgent need... and addresses which are not reused only have their public keys exposed to a hypothetical ECC cracker for a brief time between a spend announcement and confirmation.

[AnonyMint]

Hilarious. You admit everything I was saying. Did you forget what you wrote, or are you just in vendetta mode against me?

EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this.

Not for the "Koblitz" (in quotes because normally Koblitz refers to curves over a field of characteristic 2 and not a prime field)  curves but for the random ones which almost everyone else uses.

Thats why I think the claim is kind of odd, virtually all EC usage on the internet uses the prime random ones (like P-256r) which have their selection scheme published as part of the SEC document. I believe Bitcoin is the only widespread user of the SECP*k curves.  (Although the curve used in Ed25519 has a similar structure, which is also why it's performance is similar).

P256k1 was not included in any of the NIST standards, it's only a part of the certicom spec. So if you're hypothesizing NIST as the _specific_ vector of pushing for weak ECC then your theory really should exclude Bitcoin's curve from the start.  (In other words: good rational reasoning is that if your argument is ECC is dubious because NSA influences NIST, then you should equally find our use of a non-nist curve comforting, no?)

(This isn't to say that I would find it hard to believe that certicom is a pawn of CSE. )

I would, however, be concerned that the "vulnerability" were the use of koblitz form alone. Part of the problem is that once you start assuming mystery math anything is possible.  My comments about the public keys not being disclosed with good use and our ability to upgrade still stand... though, uh, if our upgrade option were to change to a non-koblitz curve (or a much larger field) I'd have some concerns about the scalability impact.  Making things more secure against conjectured weaknesses doesn't help if the fixes make the system non-viable or drive us into centralization.  (Though I've long wondered with PGP, which doesn't really have the same scaling concerns doesn't use multiple asymmetric schemes in parallel in such a way that an attacker would have to break all of them...)

Personally, I'd like to see us deploy— as an option— Lamport/Merkle signatures because they have totally orthogonal security properties and are based on assumptions most cryptographers would consider fundamentally stronger... plus they answer any QC fud. They also permit very fast validation, even with trivially implemented code (fast SECP256k1 validation is far from trivial).  The tradeoff is that the signatures are much larger... but at least signatures don't end up in the UTXO set. I haven't considered this urgent, but it's been on my long term wishlist since early 2011.

It might be fun to ask certicom to publish the procedure used to select SECP256k1's parameters. Though the design space of near maximally sized "Koblitz"  curves is smaller than you may be guessing. It may be the case that we could reverse engineer the procedure.

There is something I need to research in there. You wrote that signatures don't end up in the UTXO set. So perhaps signatures are not in the blockchain...which would be news to me.

Edit: So UTXO is the "set of spendable coins" thus I think gmaxwell is pointing out above that the increased signature sizes won't impact the memory requirements of verifying transactions. Yet I am still thinking the increased signature sizes will bloat the downloadable blockchain (and thus also memory or hard disk seek speed requirements for producing the UTXO), for those that can't be pruned. Incorrect?  (with pruning, this might or might not be too onerous, I haven't done the calculations at Visa scale)

[AnonyMint]

Bitcoin's non-balances design probably doesn't not let it switch (the design and implementation) from 20 byte to 16KB public keys, and to 8KB signatures. This is a major revelation for me about Bitcoin insecurity.

Which is just @#$@#$ nonsense, and I was responding pointing out that public keys would be no larger, and so your invocation of balances is just hysterical jibberish.

You've continually repeated misinformation in this thread (and in other threads, now that I connect your name). I realize that it's due to your ignorance and not due to malice, but it means that interacting with you is a waste of time.  ... and I'm worried that I'm rewarding your poor understanding and poor research by continuing to respond to ridiculous claims.

Do your own work for a bit, instead of making me feel like you're just converting every doubt you have into a FUDdy misstatement of fact in order to make other people do the work in refuting you.

A balances design such as the mini-blockchain of Cryptonite, is able to prune transaction history after some period of aging, thus indeed the transaction signature size does matter relative to a non-prunable Bitcoin, not just the public address which can be the hash of the public keys as you explained.

Also the transaction signature size impacts the maximum transaction rate per second for a given bandwidth of full clients.

So who was "@#$@#$ nonsense, hysterical jibberish".

Edit: Note pruning Bitcoin's txids won't require that transactions include a block chain length expiration field, because address reuse can't create a duplicate txid. The txid in Bitcoin is not a nonce rather the hash of the transaction which contains the output being spent, i.e. there is no way to reload an address with a duplicate txid, because all transactions are iterative hashes of hashes of hashes (etc) of the historical tree of preceding transactions history feeding the input.