Thanks! I finished implementing the blk0001.dat parser for Bitcoinj.

For me, it' was the most simpe way to get statistics out from the blockchain. Tomorrow I will post a histogram of average volume transacted depending on the amount range (eg. 0 to 1 BTC, 10 - 100 BTC, 100 to 1K BTC, etc.)
(Note that I had to assume that the last output from a transaction is the change).
This reveals interesting information regarding the average use.

If someone wants to experiment with it, send me a message.

Best regards,
 Sergio.

In Satoshi client every object can be serialized either to disk or to network.
Nevertheless I haven't found any difference between the serialization of the blockchain for SER_DISK compared to SER_NETWORK.

What classes are sensitive to SER_* serialization ?

I'm writing a Bitcoinj class to read and process Satoshi blockchain (blk*.dat) files and I want to know if I should care about SET_* flags.

Thanks, Sergio.

A month is more than enough to test and upgrade. Nevertheless, currently, Bitcoin users take 5 months to upgrade to 90% or so.

Check the thread https://bitcointalk.org/index.php?topic=106026.0 where I proposed an alternative alert system to the double-spend alert system proposed in "Two Bitcoins at the Price of One".

It's much better in terms of bandwidth usage, reliability and backward compatibility.

I know, but setting a maximum of 5x the average would be just fine.
Also, as I said, block transmission could be prioritized, giving extra quota to peers, since the proof-of-work can be checked in advance inspecting the block header.

A honest node can never trigger the attack heuristic: if you receive an authorization to send 500 Kb, and you send 1Mb, it's your fault.
It's like limiting the TCP window at the session level.

What could happen is that transaction load becomes higher than the average bandwidth limitation. But I doubt this would be a problem since we already know what the maximum tps/second or bytes/second is: it's limited by the 1M/10min block size.

Also, a special authorization to send a big chunk of block data could be sent to a peer if he announces the block by sending the block header containing the expected PoW

Please don't shout at me, since this it is a pure speculative (and crazily provocative) idea...

I'm thinking that a small scale attack to Bitcoin could help the user base adopt the habit of timely upgrades.

For example, 3 months have past since CVE-2012-3789 was issued and still 40% of the network is running v0.6.2!!

Why is people so slow at upgrading?
Do the same thing happens in other open source projects?

If someone attacked Bitcon, not a big panic but just some nodes going down here and there, the price won't go down (maybe just a few cents) then everyone will pay much more attention to upgrades...

Ohh, I miss the times when SolidCoin threatened to take down Bitcoin... 


PS: Please don't misinterpret: this is just speculation!

I was thinking about what could be done to proactively protect from future DoS attacks.

It's not only my opinion that this may be a weak point in the source code.
From https://en.bitcoin.it/wiki/Weaknesses:
Why not isolate clients from another. Suppose we add a "sliding window" of resources (CPU/RAM) for each node.

So, for example, when I client sends a transaction Tx1, it receives the message:

("avail-resouces" ,100 Kb, 75 sig)

Which means that he can send an additional 100 Kb of data containing no more than 75 signature verifications.

Every 1 minute (if no avail-resources message was previously sent in the last minute), a node broadcasts new avail-resources messages to every peer, with an update of the available resources for each one of them.

If a peer tries to overpass the resource limit, it is banned.

Also, counters should be maintained for every peer (for example dFreeCount should be local and not global)

As an additional benefit client isolation allows the user to specify how much CPU/RAM he is willing to give to the Bitcoin application.

eDonkey2000 and other similar P2P nets have a bandwidth control to limit use. Why not Bitcoin?

Best regards,
Sergio.

Hi!

Don't worry!

First, the dev team has already fixed this in 7.0. I hope the new stable release is ready soon and everybody upgrades.

Secondly, I won't be saying anything that can help an attacker exploit the vuln.

I will talk about many aspects of Bitcoin, and only one of them being the existence of DoS vulnerabilities, past heists in the ecosystem, and how Bitcoin has managed to handle them.

I will also talk about scalability, which has always been my deepest concern.

The conference titled "Bitcoin, Mavepay and the future of crytprocurrencies" is scheduled for Thursday 14:20 local time, Buenos Aires, Argentina at Ekoparty. Obviously I will also talk about my own proposals (Mavepay).

Come to Buenos Aires!
Juliano Rizzo and Thai Duong will be talking about CRIME, a devastating vulnerability they found in SSL!


Best regards,
 Sergio.

I understand your concerns regarding RIPEMD160, but that is another problem, unrelated to my question.

My question is, in other words: Can discrete log finding algorithms be modified to break many/all key pairs at a price not much higher than breaking a single pair.

I've read baby-step giant-step algorithm for solving the discrete log and it uses a pre-computed table that can be reused to break following keys, but I don't know how the cost of building the table relates to the total cost of the algorithm. If building the table is 99% of the required time, then one can break 100 keys at the price of one.

I don't see how Pollard's rho algorithm for logarithms can be optimized to break many key-pairs at the price of one.

I've been thinking about the idea of adding an optional 160-bit ECC curve to Bitcoin signatures in order to allow low-value payments to use half of CPU resources. I don't mind if individual keys are broken (since the cost of the attack will be orders of magnitude higher than the payoff). But I's a problem if all key-pairs can be broken at the same time.

Is there a method to break an ECC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair? Is there any memory trade-off that helps such attack?

If so, then, as Bitcoin grows, the monetary incentive for an attack to the curve will increase over time. An attacker that could break the whole curve at once could steal all the money.

If not, then there is nothing to worry about since the use of unique addresses and the slicing of payments of high value into low value payments can reduce the incentive to a minimum.

Obviously this is not a problem we should worry in the nearby future, but maybe we should in 30 years.

Best regards,
 Sergio.

Interesting. For each new double-spend the attacker needs a previously unspent outpoint (field p).
So the attacker would need first to own 100K outpoints (impossible without paying a huge amount in fees).
Also each message takes 8 ms to be sent though a 64 Kbytes/s connection, so CPUs won't be blocked in signature checks.
Alerts with invalid signatures are not relayed, so signatures must be valid.

Anyway I do think this may be a problem.

Two possible solutions:

1. The easy. Only check and relay an alert message for p if we already have a transaction that uses p in the memory pool
(the attacker would need to pay fees for each alert message in order to make the attack possible)

2. After n double-spends have been detected for outpoint p, disable the use of p in transactions for 2^n blocks (don't relay a transaction that uses p)
This reduces exponentially the benefit of such attack to the attacker.

An answer to a bit old post...


gmaxwell has pointer out that to me that there are some fields that are passed to the bitforce hardware. They are:

- timestamp    
- difficulty target

Any one of them can be used code a "time bomb".

I would have been better if Hash(Hash(Header-without-nonce) || nonce) would be chosen for PoW instead of Hash(header) for Bitcoin.

I still haven't heard any big problem with proposal 1, a new alert message in the form (p,Sign1_p,k,hash1_k, Sign2_p,hash2_j)

Pros:

- Doesn't give the attacker more power (more bandwidth)
- No modification to the proven protocol of rejection of double-spends
- Minimal interaction with the rest of the protocol
- Does not make worse the problem of "double-spend by mistake".
- Very low bandwidth usage, just 512-byte alerts
- Cannot be source of DoS: a maximum of one alert can be generated for any existing outpoint every 10 minutes.
- Backward compatible: Old clients simply discard the new message type
- Very clean implementation can be coded...

Con:
- It requires more coding than Gavin solution (but Gavin solution is, I think, very error-prone to code well)

First, I just want to thank kjj for linking the code that shows how BF work, gmaxwell for his proposal and all for this excellent discussion.

Maybe we could implement the idea of dynamic checkpoints (Gavin) but only if they come signed by the Alert signing key ...

Or even we could create a special Alert message that comes with a new checkpoint embedded.

This would be a mid point between Gavin and gmaxwell positions.

I vote for signed checkpoints, with a confirmation dialog shown to the user. +1

In the following months Butterfly Labs (http://www.butterflylabs.com/) will be introducing a new ASIC miner product.
This will increase the MHash/s/$ approximately 30 times. Other vendors such as http://www.btcfpga.com are building competing products.

Let's take the "BitForce Single SC" (BF) as reference:

- 40GH/s
- $1,299

Although at a first glance this look like a huge benefit for the network, there are new vulnerabilities we must face:

1. There will be a window of time where new vulnerabilities will be exposed to a government or anyone willing to invest 1M USD to temporarily (1 week?) disrupt Bitcoin and generate a rush to the coin (a big price fall). An attacker can exhaust the bandwidth of all the connections in the Bitcoin network.

The attacked needs a 820 BF (1M USD) to achieve 32800 GH/s (or 2^45 hash/s).

The attacker chooses the root block at index 193000 (which has an PoW of 2^53 hashes (53 zero bits)).
From checkpoints.cpp: (193000, uint256("0x000000000000059f452a5f7340de6682a977387c17010ff6e6c3bd83ca8b1317"))

Since block 193000 was issued at date 2012-08-09, the attacker waits 4 months so ComputeMinWork() allows the acceptance of
PoW of 4 bits less. (This lowers the money required 16 times)

He can reach 2^53 hashes in 53-4-45=16 seconds. Then he starts creating a branch from block 193000, each block being 1 Megabyte long, with current (not past) block time, and having a single coinbase transaction, and extending the chain of the previous created block.
Sending 1 block every 16 seconds.
All nodes start spreading these past blocks, possibly filling the entire network bandwidth and blocking normal blocks for as long as most of the nodes upgrade.
Also the attacker will be filling 5.4 GB of hard disk every day, and the blockchain on disk will need to be manually pruned to cut the offending branch so it is compacted to its normal size.
The only way to recover from these attacks is by downloading a new version of the client with a new checkpoint with a much
higher block difficulty. I can't think of any other possible patch. Maybe the interval between new releases
during the transition from GPUs to ASICs could be decreased.

2. What would happen if miners switch ALL to this cheap 30X ASIC solution and this vendor has build-in a backdoor in the chip to:

- Stop working after block height N
- Hide some private information (e.g. part of the private key) in the nonce (as a side channel attack)

In the first case, the network will suddenly stop and, because of a higher difficulty reached, there will one block every 5 hours during a
period of 14*30 days=420 days !!

This will destroy Bitcoin for a long while and will require a manual adjustment in the difficulty.

In the second case, an attacker may compromise the wallets of all miners!

People should use open source mining solutions....

Best regards,
 Sergio.
 

Two problems I see:

(A) I don't like the idea of giving the attacker more power.

For example, suppose the attacker has a connections to the main miners.
First he sends a small transaction to the network (or directly to a miner). This one travels fast.
Then he sends a double spend transaction of 100 Kbytes long to the network, with a high fee. Every node start relaying this double spend. As this transaction is huge, is travels very slow trough the network, consuming a lot of bandwidth.

The attacker is sure that the second one won't be included in a block because miners will reject it.

So miners should change the algorithm to choose the right transaction when a double-spend is detected: choose the one that pays more fees.

(B) How to allow a honest user to replace a transaction because of, for example, low fees specified in the first one?

You have to mark transaction in the pool to be automatically removed after some time, with some type of priority queue structure to allow fast search and removal of old transactions.

Marks in prevouts are lightweight, and easy to wipe out. Just erase them all every 10 minutes.


Best regards,
 Sergio.

So I see that proposal 2 is not a good solution, because of multiple devices.

Still proposal 1 is an effective layer of protection.

Did anyone found any problem in it? If not, then I may write a BIP.
Note that marks on prevouts are cleared every 10 minutes, so any problem regarding sending double-spends by mistake just fades away quickly.

Regarding transactions with 0 confirmations, is a matter of risk management, as Mike says.

Great, that means that there were no more vulnerabilities found.

Yes, that's why I added to the algorithm that if Tx1 and Tx2 have the same outputs with the same amounts, then the miner cannot claim any prize, and the block is invalid.