That's the best part of the attack.. the community is sponsoring it! 

It was an awkward way to say that the block is disposed and a new block is created (on top of the best chain), containing the same transaction  txwhenlost. Obviously the parent block will be different.

Have you considered that maybe SatoshiDice is a government sponsored attack on Bitcoin ? 

Ohh! It's a pity they don't said that on the web page, it would have saved me and you time. They clearly said the response is immediate, probably for  marketing.

There has been some discussion regarding Double Spend against a Satoshidice loss, but it seems that no one has seriously considered Finney Attack against SatoshiDice. This attack is both simple and (IMHO) very easy to mount by an attacker-miner.

The idea is simple: Suppose a miner has any percentage of the network hashing power, say 1%.
Suppose a miner has 241 BTC in an previous output X.
This miner creates a block containing ONLY a single transaction TxWhenLost that pays 241 from X to a new address he owns.

Then the attacker starts mining as normal (and updates the special block to a new parent whenever a new block is solver by the network).
After 16.6 hours on average, his solves a block. Then instead of broadcasting it, he first creates a transaction TxTest that bets the 241 BTC in X against SatoshiDice. Suppose the bet is:

TxTest bets 241 BTC against less than 6000
(address 1dice6wBxymYi3t94heUAG6MpG5eceLG1).
The winning probability is 9.1553% and the multiplier is 10.666x.
That means that approximately every 7 days the attacker wins SatoshiDice.

Now he sends TxTest to SatoshiDice. SatoshiDice replies broadcasting the result TxResult (they say this is almost instantaneously).  Now the attacker decides:

if he has won, he discards the solved block without broadcasting.
If he has lost, he broadcasts the block as soon as possible. Since the block has very few bytes, it will propagate fast. The attacker may also have many nodes in the network to propagate faster the block.

Analysis

9.1553% of the times the attacker wins 241*10.666-25=2545.506 BTC
90.8447% of the times the attacker wins 25 BTC

So the expected income PER SOLVED BLOCK is 233.04+22.71=255.75 BTC !!

That 10x more the 25 BTC a miner normally receives.

Even if 1/10 times the attack fails, the expected income is notably higher than normal.
This is not the best possible attack: if the attacker has greater hashing power or doesn't mind to wait more, he can try bets to "lessthan 1500". In this case the earnings 3 times more (750 BTC per solved block).

The only assumption I'm making is that SatoshiDice responds with TxResult within a short time interval (say 30 seconds).

The only way I think SatoshiDice can protect from this attack is by waiting for 1 confirmation from the transactions they receive or by delaying TxResult 5 minutes or so.

I haven't  contacted the owner of SatoshiDice since there is no contact information in the web page. If you know who the owner is, please tell him to follow this thread.

Disclaimer: as always, I haven't test the attack, so I may be wrong.
Think for yourself.

Best regards,
 Sergio

My proposal is almost stateless. There are no unknown or intermediate states. A single decision is made when a "inv" arrives containing a block hash.

Why write code if you know nobody will be using it? I prefer to know in advance.

The existent command is "headers" not "header" 

I don't think so. Since only the missing transactions are transmitted, the worst case is just like it is today. Maybe a little worse in the limit case that the decision to request individual txs instead of the full block was not a good one (many requested are made instead of a single request).

Ok, it's not clear. What I meant is that the parent block may have required a difficulty adjustment that should be taken into account.

No, that's not correct.

If the parent is known, then we keep propagating the "header" command. If it's unknown, then we just wait for the full "block" command to arrive.

A single decision is made whenever a new block X is advertised with "inv":

If I have a previous "header" description of block X, then evaluate if it's better to download the block or to download the transactions separately.
If you decide the former, keep as normal.
If you decide the later, then ignore this "inv" command forever, and store a remainder in a memory table to reconstruct the block when all txs are received.

(If I have no "header" of X, keep as normal. )

This simplifies the implementation a lot. There is no race condition, no unstable state. Convergence is guaranteed.


Yes, I had noticed that too.

Hi!
I'm sending this BIP for the community to discuss. I hope I get good feedback so I can proceed to implementing it, publish it in the BIPs wiki, and make it into the protocol.

BIP: <unassigned number>
Title: Increasing the Network Hashing Power by reducing block propagation time
Author: Sergio Demian Lerner
Status: Draft (incomplete)
Created 19-Feb-2013

Abstract

When a block get orphaned, it means that some of the available network hashing power has been wasted. This wasted hashing power does not benefit anyone in the Bitcoin network.
Orphan blocks are created mostly because of the network propagation time of new blocks. A 1 Mbyte block, sent over a 50 Kbytes/sec connection, takes 20 seconds. Assuming an average network graph diameter of 4 hops, it takes more than 1 minute for such a block to propagate throughout the network. Current block average size is 150 Kbytes, so this is not an issue today. As we expect the Bitcoin network to grow upto its maximum capacity, it's reasonable to expect a 13% waste in network hashing power in the near future because of orphaned blocks.

One of the ways to reduce block propagation time is by sending only the block header and transactions hashes in a first command payload ("header"), and then sending the remaining data (the transactions) in a second command payload ("block"). Since the coinbase transaction cannot be sent to peers without the block enclosure, the "header" command must also send this special transaction.

Specification

"header" command format is:

- Block header
- transactions hash list
- Coinbase transaction (maximum 10 Kbytes in size)

An average "header" command size (for an 1 Mbyte block, considering an average 400 bytes tx) is 80 kbytes, that takes 1.5 seconds per hop.

The "header" command should only be sent for newly created blocks and not for historical ones.

Semantics

Just after the first command "header" is received, a node should:

1. Verify that the block parent is known. If it's not, then discard the command.
2. Verify that the block is the last block of a chain (by the time field)
3. Compute the PoW and check if it's similar to the parent block PoW (+/- the possible expected variation). If it's not, then the command is ignored and the sender is blacklisted (DoS prevention).
4. Resent the "header" command to all peers.
5. Check if transaction hashes contained in the "header" command are already in the Tx pool.
6a. If all hashes are in the pool, reconstruct the block referred by the "header" and announce to peers.
6b. If very few are not in the pool, then the missing txs can be requested from peers.
6c. If almost all of them are not, ignore the "header" command and request the block from the peer having sent the "header" command by using "getblocks".
7. After the complete block X is reconstructed/received, proceed as normal (announce the block by "inv" to peers and forward when requested)

Miners should, after doing the previous steps 1-6, do:

1. Wait until the full block is reconstructed or received (while mining as normal without interruption)
2a. If the block X is received before our own block is solved, start over trying to solve a block whose parent is X.
2b. If a block is solved locally before the complete block X is reconstructed, discard X and try to win the block chain race against X.

This BIP does not require any soft-fork or hard-fork and is 100% backward compatible because it only involves changes in the p2p communication protocol. Peers that do not understand the "header" command will process the "block" command instead.

Reference Implementation

<not yet implemented>

Further related improvements

With a maximum 10 seconds propagation time, a 2 minute block confirmation interval should be stable, so it might be possible in the future (with the community acceptance) to reduce the block interval to 2 minutes or less with a hardfork (reducing also the fees and the block size proportionally to keep the same economic properties of Bitcoin intact and keep the contract with the community).

Who benefits from this BIP?

Miners: miners that implement this protocol (even if privately between them) get a 10% advantage over the remaining ones.

Users: They get 10% additional security for almost no extra cost (overhead should be negligible). Also if blocks are reconstructed using existent transaction in the pool, and not sent, bandwidth usage is reduced to a half.

This is a win-win situation.

Best regards,
 Sergio.

Ohh I see, txn_count is not included in the PoW hash computation...

The wiki https://en.bitcoin.it/wiki/Protocol_specification#Block_Headers says that in response to getheaders, nodes send block headers with the field  txn_count set to zero. The code seems to agree.

Wouldn't be a lot more helpful if the returned headers contained the correct txn_count field so receivers could validate the block PoW before requesting the full block?

Thanks, Sergio.

New DoS vuln by Forcing Continuous Hard Disk Seek/Read Activity (fixed in 0.8.0)

Private Release Date: 08-JAN-2013
Public Release Date: 14-FEB-2013

Systems Affected

- Satoshi Bitcoin Client (Bitcoin-Qt, bitcoind)
- All Bitcoin clients that mimic the behavior related to transaction validation of Satoshi client versions prior 0.8.0

Affected Versions

- Bitcoin version 0.7.2 released 2012-12-14
- Bitcoin version 0.7.1 released 2012-10-19
- Bitcoin version 0.7.0 released 2012-09-17
- Bitcoin version 0.6.3 released 2012-06-25
- Bitcoin version 0.6.2 released 2012-05-08
- Bitcoin version 0.6.1 released 2012-05-04
- Bitcoin version 0.6.0 released 2012-03-30
- Bitcoin version 0.5.3.1 released 2012-03-16
- Bitcoin version 0.5.3 released 2012-03-14
- Bitcoin version 0.5.2 released 2012-01-09
- Bitcoin version 0.5.1 released 2011-12-15
- Bitcoin version 0.5.0 released 2011-11-21
- Bitcoin version 0.4.0 released 2011-09-23
- Bitcoin version 0.3.24 released 2011-07-08
- Bitcoin version 0.3.23 released 2011-06-14
- Bitcoin version 0.3.22 released 2011-06-05
- Bitcoin version 0.3.21 released 2011-04-27


Overview

Transaction processing has two stages in Satoshi Bitcoin client. In the first stage, transaction inputs are fetched.
This is done by bringing to RAM the transactions that contains the outputs referred by the inputs.
In the second stage, previous outputs are verified to be unspent and the related scripts are evaluated.
Since double spends are not considered to be a DoS attempt by the protocol rules, a transaction that refers to previous spent outputs will pass the first processing stage without being discarded. An attacker can therefore construct transactions that, before being discarded in the second stage of processing, require the victim application to seek and read too many parts of the block chain that could be scattered thought the storage files, delaying any other processing.

Details

We assume that the whole block chain does not fit in RAM, so each transaction fetch requires a HD seek and read. An average 7200 rpm hard drive
can random seek/read a 1Kb block in a non-cached 2 Gb file in 12 msec. Each prevout of a transaction consumes 44 bytes, with empty sigscripts.
The attacker creates transaction with many inputs an one output. In this way, the other sections of the transaction (output scripts, headers) are amortized and become irrelevant to this analysis.
For an Internet connection of 50 Kbytes/sec bandwidth, sending 45 bytes requires less than 1 msec.
By continuously sending this specially crafted transactions an attacker can block any Bitcoin peer from performing other tasks.
Also the attacker may be able to block 10 peers at the same time, since the relation of 1:10 in required resources.
Note that the attacker does not need to sign the inputs nor to have the full block-chain to perform the attack. He only requires the hashes of all previous transactions, which currently requires only 10876856*32=332 Mbytes of storage.

Version 0.8.0 of the Satoshi client stores only unspent prevouts in memory and can abort processing right after a spent prevout is referred by a transaction.

Possible Attack Scenarios

1. Because of the small resources required to mount the attack, it could be performed by botnets to massively attack the Bitcoin network.

2. The attack can be used against miners to prevent them from sending blocks. Nevertheless, currently big miners are ony connected  to there own front-line of Bitcoin nodes to preven such attacks.

3. By using many nodes at once, an attacker may try to create a barrier that splits the network in unconnected components, in order to carry another kind of attack.


Not-a-problem variations

1. A valid 1M transaction could be constructed to reference more than 22K unique input transactions. In theory that transaction would take more than 5 minutes to be verified. Nevertheless the attack is unpractical for two reasons:
a. The attacker should have to own those 22K transactions.
b. Those 22K transactions should have to be  scatterer thought the blockchain to force HD seeking activity. If they were created in a limited period of time, they would end up confined in a limited portion of the block chain file. The result would be that the hard disk cache will help to reduce the read latency and so attack effectiveness will be reduced. Nevertheless version 0.8.0 of the Satoshi client considers transactions greater that 100K to be non-standard, so the vulnerability is further reduced.

Suggested Solution for 0.6/0.7 versions


The client application could verify that prevouts are not spent each time they are fetched, and abort if a spent prevout is found.

bool CTransaction::FetchInputs(CTxDB& txdb, const map<uint256, CTxIndex>& mapTestPool,
                               bool fBlock, bool fMiner, MapPrevTx& inputsRet, bool& fInvalid)
{
  ..
 for (unsigned int i = 0; i < vin.size(); i++)
    {
    // Read txPrev
    CTransaction& txPrev = inputsRet[prevout.hash].second;
    ....
   // NEW CODE BEGINS
    if (prevout.n >= txPrev.vout.size() || prevout.n >= txindex.vSpent.size())
        {
        fInvalid = true;
                return DoS(100, error(" .....
      }
    if (!txindex.vSpent[prevout.n].IsNull())
     return false;
   // NEW CODE ENDS
   }
}


Disclosure Timeline

2013-01-09 - Vulnerability reported to Gavin Andressen and other core devs.
2013-01-09 - Gavin Andressen aknowledges report and confirms version 0.8 will not be vulnerable, permits disclosure after 0.8.0 release candidate 1 is available.
2013-02-09 - Bitcoin version 0.8.0 release candidate 1 is available, fixing the vulnerability
2013-02-14 - Vulnerability disclosure

Credit

This vulnerability was discovered by Sergio Demian Lerner, from Certimix.com
This report was written by SDL.
Disclaimer: I haven't tested the attack with exploit code, but it seems to be real and practical.

Great!

So, to clear this issue: Gavin stated there is NO WAY OF MAKING TxAttack STANDARD.

That's relieving.

I respect very much all the hard work all the core devs do designing and writing code. I have no time to code, so my contribution is to think.

Even if a block containing a 3min tx is ever mined and buried into the blockchain, the 0.9 version of the Satoshi client could just check for the tx hash and, as an exception, set the transaction as verified without actually doing any verifications.

As we already have good prevention measures in 0.8, as Gavin said, I really dubt that during the update process a 3min transaction will be mined. The time window is short and the attackers benefit, almost none (for a single tx mined).

The real problem starts is if a hundred 3min transactions are mined, not just one.

I would say miners have at least a month to upgrade.

Retep:
First, when I first published the vulnerability, I thought I wasn't critical. Almost each time I do responsible disclosing (and I did it more than 5 times), the core devs disregard the issues, so I really thought it was another minor vuln. The fact that Gavin disregarded it in this thread means that I would have published it anyway, even after going through the undocumented process of responsible disclosing.

Second, after I published the first details, the extension to standard tx would be pretty obvious to anybody willing to think about it a minute.

So the best I could do was to tell the truth and protect the network from attackers telling miners to prepare from such attack.

Third, anyone willing to invest 100K USD in ASIC will always be able to disrupt the network, so it's no difference before and after this vuln was disclosed.

Protecting the network is very easy: don't include non-standard transactions in blocks.

My final word is that the attack is not critical, nothing to start shouting everywhere, but it's real.

Best regards, Sergio.

I have good news and bad news.

The good news (as I already said) is that it can be patched by caching the last tx hash AND checking the key/pubkey format before hashing (or at least check that the size of the arguments is correct)

The bad news is that I came across a new attack that can DESTROY the credibility of the network in a few days. So please Eligius, you better stop allowing non-standard transactions for a while until everybody upgrades or every miner in earth conforms to reject non-standard transactions.

The idea is to make the splitting of TxPrep/TxAttack in such a way that the TxPrep part is non-standard, but it´s also small and will be included in blocks like the ones mined by Eligius.

Then TxAttack is made standard, so IT WILL BE FORWARDED by nodes.
An attacker can send many TxPrep(i) during a preparation phase (and also during the attack) interlaced with TxAttack(i). So the attacker can, at any time and for any amount of time, pose an enormous amount of work to the network for very little cost.

The scripts look like this:


TxPrep: NON-STANDARD
100 outputs:
scriptPub:
OP_0 { 199 times}
OP_CHECKSIG {198 times}
OP_DROP
<pubKey>
OP_CHECKSIG
{leaves the stack as: [BOTTOM] <pubKey> [TOP]}
Size: 46 Kbytes.


TxAttack: STANDARD
100 inputs:
scriptSig: <sig>
Size of inputs: 10 Kbytes.
Size of outputs: 990 Kbytes.
Size of transaction: 1Mb
Time to verify: 990 Kbytes * 20000 / 100000000 = 198 secs
Time to send the tx: 20 seconds. (at 50 Kbytes/sec)

So imagine an attacker prepares the attack for a few days, by storing into the blockchain a hundred TxPrep(i), and the suddenly releases all of the TxAttack(i).

I nobody finds a good reason not to, I will be changing the title of this thread to reflect the change in impact of the attack.

Best regards,
 Sergio.

There is at least one mining pool that accepts direct connections to be used to send non-standard transactions. So the attack could in theory be done by anyone willing to pay some fees (that, right now, are very cheap).

I realized that the "Quite Good" solution only does not work alone. It's not enough to verify that the arguments are well-formed.
A complete solution requires that the last hash digest of the transaction is cached and reused in the following verifications of the same prevout.

Here is a modified attack that verifies 19932 well-formed signatures against a well-formed public key.

I use 151 inputs. Each input requires 132 verifications. That's 19932 verifications in total.

ScriptSig:
OP_PUSHDATA1
<sig-size>
<signature>
OP_PUSHDATA1
<pubkey-size>
<pubkey>

{ repeat the following part 66 times
OP_2DUP
OP_CHECKSIG
OP_DROP
}
>> stack after execution  of ScriptSig:
   [bottom] <signature> <pubkey-size> [top]

ScriptPub:
{ repeat the following part 66 times
OP_2DUP
OP_CHECKSIG
OP_DROP
}
OP_DROP
OP_DROP
OP_TRUE

>> stack after execution  of ScriptPub:
   [bottom] <1> [top]

The part that does not contribute to hashing is 76 Kbytes long, so the remaining 924500 bytes are hashed.

The transaction takes at least 184 seconds to verify.
Without the signature cache, it would take an additional 40 seconds.

If the last hash of the transaction used while evaluation a script is cached, then only the first hash of each prevout is computed, and that will require only 151 evaluations (not 19932)


Best regards! Sergio.

New Bitcoin vulnerability: A transaction that takes at least 3 minutes to be verified by a peer

What is the most CPU consuming transaction an attacker can create? (*)


Don't keep reading. Take a minute to think about it...

.
.
.
.
.
.

Most people will immediately look for a transaction that verifies as many signatures as possible.
One can achieve this by trying to spend many previous outputs that you own, with a single signature verification for each.
But it turns out that that attack is quite expensive: given that each TxIn requires at least 100 bytes to hold a signature,
a 1Mb transaction would only hold 10K signatures. Assuming each signature verification takes 2 msec, processing the transaction
would take 20 seconds. But even then we would need 10K previns ready to be spent, which would be quite hard to achieve.
If the attacker is a miner, he can create a transaction that exposes 10K outputs (TxPrep), and follow it by the transaction that consumes them (TxAttack). But TxPrep would require an  additional 340 Kbytes, so TxAttack would be shorter than expected.

Repeated SHA-256 hashing

There is a another way of forcing clients to do expensive computations with less resources, and that is by forcing clients to hash
the transaction many times: by design each time a signature is verified, the whole transaction is hashed, with some minor modifications.
(check  https://en.bitcoin.it/wiki/OP_CHECKSIG and the beautiful accompanying graph made by Etotheipi)
Using this fact, a miner can construct a transaction take takes more than 3 minutes to be verified (assuming 100 MiB/sec of SHA-256 hashing speed).
First the attacker creates a a transaction that sends 1 satoshi to 100 outputs. Each output is not a standard scriptPub, but special scriptPub that consist of the opcodes: OP_CHECKSIG (200 times) OP_TRUE
This script constains no more than 200 sigops, so is a valid script (200 is the limit).
TxPrep takes aproximately 21 Kbytes from the 1M block.
Then the attacker builds the transaction TxAttack which uses all these TxPrep outputs.
To make the transaction valid, each scriptSig is:  OP_0 (201 times)
The previn part of the Txattack transaction takes aproximately 24 Kbytes.

The rest of the TxAttack transaction (upto 1Mb is filled) is made of a few outputs with long scripts (or a lot of outputs with short scripts).
This part of the transaction is almost 955 Kbytes long. (**)
Now, to verify a single script (scriptSig+ScriptPub) the client tries to verify 200 signatures.
Obviously each of those verification return false, since 0x00 is neither a valid ECDSA public key nor a valid ECDSA signature.
But the client has to rehash the 955 Kbytes of data 200 times.

The total size hashed is 100*200*955000=19 100 000 000 bytes
Assuming that OpenSSL code performance of SHA-256 hashing is 100 MiB/sec, then the hashing takes 191 seconds.

The proposed attack requires that miners includes both TxPrep and TxAttack in blocks (but I may be different blocks).
This could be achieved by any user by adding some BTC as fees (I think 1 BTC will do).

Nevertheless, another attack can be constructed by using a standard transaction, that is relied normally from peer to peer.
The attacker can use a standard multisignature transaction to try to pack more verifications in less space ( 1-in-3 OP_CHECKMULTISIG ).
This attack is much more difficult, since it requires the attacker to prepare more than 6000 outputs to be used.

How this vulnerability could be used to perform an attack?

1. A miner that can mine one of these block every 10 blocks (having 10% of the network hashing power) can force the blockchain verification  process to be a lot slower. Verifying a year of the blockchain would take more than 10 days of CPU time.

2. A miner could use this attack combined by other idea gets a greater probability of finding a block the next block.

3. A peer wants to DoS attack another peer. (but the penny-flooding protection must be bypassed somehow)

4. If miners do not prevent these transactions from being included in their blocks, an attacker can create a TxPrep/TxAttack pair transaction for every block mined, and send the pair every 10 minutes, with a 1 BTC fee, to be included in the next block. Validating the blockchain would take almost half the time it takes to generate it, then the coin price would collapse, the attack becomes cheaper, ... dooms day. Obviously miners will stop including such transactions and nothing horrible really happens. But miners should have to reject tasty fees, and I don't know how the incentives will play for them.

Not a Solution (without hard-forking)

Create a Transaction hash cache to temporarily store the last used hash during the evaluation of a script.
Note that the attack can still be executed by using independent outputs.
(TxPrep creates 20K outputs, using 200 Kbytes, then TxAttack consumes these 20K outputs, and requires 152 seconds to be verified)


Quite good Solution (without hard-forking)

Verify that the ECDSA signature and the ECDSA public key are well-formed before hashing the transaction.
(this reduces the maximum CPU time to about 30 seconds, since now TxAttack wastes more bytes in signatures)

My Solution proposals

1. Soft-forking: Reduce the maximum transaction size to 100 Kbytes. (AGAIN Sergio !?!)
  
2. Hard-forking: For script evaluation purposes Define
   Hash(Tx,previn-index) = Hash ( Hash(outputs) || Hash (Inputs-with-script-cleared) || <previn-index> )
   (for SIGHASH_ALL)
   This way the values "Hash(outputs)" and "Hash(Inputs-with-script-cleared)" can be cached and reused.

Best regards,
 Sergio.

(*) Note that I have excluded the hard-disk resource on purpose, since that's another story I'll be telling you in some time
(**) I've not created and tested the transaction, but it seems to me that there is nothing in the protocol that stops it.