Yes, you're right. These are not the same vulnerabilities that were fixed in 0.6.3, they may be the ones reported by me or other reported by somebody else, I don´t know.

One possibility is to "flag" transactions for 0/unconfirmed. Suppose each transaction has a "FAST" bit stored somewhere.  If two transactions are received referring to the same prevout and at least one has the FAST=TRUE, then the alert is sent. If both have FLAG=false, then no alert is sent. Merchants must accept only transactions with FAST=TRUE, for 0/unconfirmed.

For the proposal 2, people using multiple devices for the same wallet should avoid using FAST=TRUE and 0/unconfirmed altogether.


Originally Bitcoin had the field nSequence in previns for this purpose, but now is not checked.

Nevertheless, with the proposal 1, if you just wait 2 blocks to be broadcast, you're sure that the marks in prevout have been erased, so you should be able to send a new tx without problem.

But anyway there is a simple modification to prevent this problem:

The code that checks if Tx1 and Tx2 are trying a double-spend is skipped if both of them have the same outpoints with the same amounts. (I will edit the main post to reflect this new check)

Best regards

Some months ago there was a enlightening debate about the paper "Two Bitcoins at (sic) the Price of One? Double Spending attacks on Fast Payments in Bitcoin." (http://eprint.iacr.org/2012/248.pdf) in the thread https://bitcointalk.org/index.php?topic=79090.0;all.

I recommend anyone who is dealing with 0/unconfirmed payments to read this thread.

The authors of the paper suggest using an alert system to tell nodes if a double-spend has occur. Some have critic the double-spend alert system of being another vector of DoS attacks. First I will describe a modified double-spend alert system does do not suffer from abuse by spamming alerts.

The paper proposes sending (Tx1,Tx2) whenever Tx1 and Tx2 are valid and they share a prevout.
(Tx1,Tx2) may be very large and and it's easy to generate a high number of alerts by combinations of prevouts.

I think the concept of double-spend alert system is not flawed and may add a new layer of certainty for merchants using 0/unconfirmed.
Here is my proposal.

Proposal 1)

Suppose Tx1 refers to the provout p in its input k, with signature script Sign1_p,k, that signs the hash of Tx1 for k, hash1_k
Suppose Tx2 refers to the provout p in its input j, with signature script Sign2_p,j, that signs the hash of Tx2 for j, hash2_j

EDITED: If Tx1 and Tx2 have the same outpoints (addresses and amounts) then no alarm is sent since only fees or previns may have changed. (thanks Etlase2 for pointing out this problem)

Obviously Sign1_p,k != Sign2_p,j and hash1_k !=hash2_j

A node that receives Tx1 and Tx2 builds the alert A=(p,Sign1_p,k,hash1_k, Sign2_p,hash2_j) and sends it to its peers.

This message is, on average, 36+139+32+139+32= 378 bytes
Alerts with length over 512 bytes should be ignored. Merchants can simply accept only standard transactions for 0/unconfirmed.

When a node receives a well-formed alert message A=(p,s1,k,h1, s2,h2)

1) If p is already maked as "double-spended", the client ignores the alert.
2) If p does not yet exists in a block, the client ignores the alert.
3) Alert signatures are checked. If invalid, the client ignores the alert.
4) Mark the outpoint p as "double-spended".
5) Send the alert to the remaining peers.

When a new block arrives, all double-spend marks are removed from previous outpoints.

Also, when a transaction Tx3 is received and refers to a previously marked outpoint, the transaction is ignored and not relayed, no new alert is sent.
(note: The LockTime field was not taken into account in this description)

The crypto part of system works because signatures are non-malleable, so the sole existence of a signature of something, even if the content is unknown, is enough proof.

Proposal 2) Also I'll propose still another layer of security, but this requires a hardfork: If a miner finds two transactions that spend the same prevouts (edit: but have different outputs), both of them can be included in a block (always one after the other), and all the money from prevouts in conflict is given to the miner, the remaining prevouts are untouched. Who will dare to try a double-spend?

Obviously all this measures do not apply to a Finney attack, which is still possible.


Best regards,
 Sergio.

No, since CVE-2012-4682 and CVE-2012-4683 have different numbers, they are new vulnerabilities fixed in 7.0rc1 by the dev team.

Thank you Sipa and Gavin, I'll keep researching on this..

Very interesting software archeology

Like a part of DNA of an extinguished specimen that got trapped in the DNA of Bitcoin.

I'm re-investigating this past problem because I think there are some other possibilities for this attack vector.

Did Sipa implemented a patch back on MAY 2011 to check the uniqueness and correctness of signatures?

I don't see a IsValidSig() method in the source code.

Bet regards, Sergio.

Great work Forrest and the dev team!
Best regards, Sergio.

In the https://en.bitcoin.it/wiki/OP_CHECKSIG wiki, the process behind OP_CHECKSIG is described.

Why  TxPrev.PkScript is inserted into TxCopy ?
(In the source code the method is called SignatureHash() and the temporary tx is TxTmp not TxCopy, and the input is nIn.)

I think that the point is to "mark" the transaction input that is being signed to prevent one signature to be used for more than one input.
But why not only insert a single char '*' into the script of input nIn ? Why a big chunk of the  TxPrev.PkScript is inserted ?

What is the functionality I'm missing?

Thanks, Sergio.

Strange, it's it?
But is works as good as setting a minimum fee/byte, plus a little automatically-controlled inflation....

The advantage of my proposal it that it generates controlled and predictable inflation without government intervention.

When the blocks are not completely filled, it's is a sign of recession, so the extra reward creates money and stimulates the economy by generating inflation.

On the contrary, if blocks are completely full then not inflation occurs.

There is a theoretical problem (https://en.bitcoin.it/wiki/Tragedy_of_the_Commons) that may affect Bitcoins future.

From the article:


There is a possible solution for this problem (if it really is so). The solution is to gracefully push transaction fees to match electricity cost. I think SolidCoind tried that, by manually adjusting the block reward. This is obviously completely undesirable and opposed to the “not centrally controlled” idea behind Bitcoin.
A realistic and simpler solution is to give some extra reward to miners proportional to the number of bytes unused of the 1M available bytes in a block. This extra reward should be fixed forever, and should be much lower than the initial reward of 50 BTC. Obviously this will break the deflationary base of Bitcoin. But anyway, the effect of very little inflation would be almost imperceptible for users, so from any practical point of view the coin would still be deflationary.

Example:
   Initial reward (prize) = 50 BTC, halved every X blocks.
   Extra reward “e” = 0.000005 BTC for each unsent byte. (Maximum = 1M*0.000005 = 5 BTC )

If a transaction of size “s” specifies a fee lower than (s*e) then no miner will include it, since they would prefer getting the extra reward for those bytes unused. The extra reward can reach a maximum of  262800 BTC/year, which is 1.2% of the 21M maximum coins created by prizes (but it will be probably much lower, at 0.12% since blocks will be almost full, e.g. 90%). This is a very low inflation rate.

Let me show how equilibrium is reached when prize goes down to almost zero.

1. If the coin value goes up →
   transaction cost (in USD) goes up →
      people sell coins because fees are to high to transfer money  →
         coin price goes down
         (equilibrium is reached)

Obviously the opposite direction implication is also true, inverting the actions.

2. Too many coins in circulation →
   merchant increase prices since people are willing to pay more →
   coin price goes down →
      transaction cost (in USD) goes down →
         new people buy coins because it's cheap to transfer money →
            coin price goes up
            (equilibrium is reached or price goes down very gracefully)      

Please forgive me for my little knowledge in economics, but this implications seems to be for me very straightforward.

It would be very easy to modify the behavior for Bitcoin  (1 line of code). But it's obviously a hard-fork and needs large consent.

What do you think?

Best regards, Sergio.

Note to the moderator: Fell free to move this thread to the Economics section if you think it should be there.

Does this mean that you can´t  buy USD with Bitcoins and withdrawal USD?

But is seems you can deposit USD and withdrawal Bitcoins...

I completely agree with you about holdup / extortion.

But don't say that ZNPs are "impractical" . There are plenty of practical protocols that rely on ZNPs.

In your proposal you say: " The reason this isn't something people are using yet is because while the academics have proven it to be possible actually converting complicated programs like compositions of ciphers and hash-functions into zero-knowledge proofs is apparently not something anyone has figured out how to do practically.".

Your proposal is, as you say, completely impractical. What you are saying in why_hash_locked (if possible) requires a huge amount of computation and probably 100 Megabytes message as proof.

A zero knowledge proof of knowledge of k in k*GPub is only a hundred bytes long, and takes only three EC multiplications to achieve. What more practical than that!!
You can do it either by Chaum-Pedersen protocol , Schnorr’s Id Protocol or even naive cut-and-choose.
(edit: The first two protocols were designed for the Poligh-Helman cipher, and must be adapted to ECC)

Please Max !!!

Fundamentally new p2p systems exists: check MAVEPAY. You can get 10K transactions/second with enough bandwidth.  It hasn't been implemented. But unluckily is it completely incompatible with Bitcoin.

I really don't think that 8 hours is too much waiting right now. Probably in 1-2 years the problem must be addressed somehow.

Best regards,
 Sergio.

Yes, but the ratio is an integer value, modulo a prime p. 
finding such ratio is a very difficult problem.


There so many k values that is not possibly to find the right k value by brute force. (in Bitcoin curve, there are 2^256 possible k values)

About Bitcoin's curve is secp256k1:
" taking the name secp256k1 apart, sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard." (see Hal comment, https://bitcointalk.org/?topic=2699.0)

Yes, that's true. Good point etotheipi !

Emulating 2-3 multisig with DAA is easy too. You don't need to use OP_CHECKMULTISIG

Suppose the parties are A, B and C. Suppose any two of them can decide if the money should go to one of them.

1) A chooses a random Ak, B chooses a random Bk, C chooses a random Ck.
2) A does: 
- ABpub=Ak*BPub and sends a ZNP of that operation to B and C.
- ACpub=Ak*CPub and sends a ZNP of that operation to B and C.

3) B does: 
- BCpub=Bk*CPub and sends a ZNP of that op to A and C.
- BApub=Ak*APub and sends a ZNP of that op to A and C.

4) C does:
  CBpub=Ck*BPub and sends a ZNP of that op to A and B.
  CApub=Ck*APub and sends a ZNP of that op to A and B.

5) A creates the transaction with the script:

scriptPubKey:
   <ABpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <ACpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <BCpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <BApubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <CApubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF
   <CBpubKey> OP_CHECKSIG OP_IF OP_1 OP_VERIFY OP_ENDIF


5) Then for any party X and Y
- If X and Y wants to pay the money to Y, X privately send Xk to Y, and Y can get the money.
- If X and Y wants to pay the money to X,Y privately send Yk to X, and X can get the money.

As etotheipi posted while I was typing, math possibilities are endless and any secret sharing scheme can be implemented. Obviously if you think this is high-order math and it's too complicated, then don't use it. Although generally after is implemented, it's completely transparent to the user.
 

Interesting, exactly the same functionality can be done with DAA:

--Buyer (A) commits X funds to a k*Bpub and publish the transaction, and sends the ZNP to B.
--B sends the goods. 
--If product is good - A sends k to B
--If produce is bad/returned -  B chooses a random z, sends X coins to z*Apub and the sends the ZNP to A. A sends k to B. B sends z to A.
--If can't agree, funds are locked indefinitely

No need for 2-of-2 multi-signature.
Maybe the two tools could be used together to do more advanced contracts!