I did a simulation of two cartel strategies along the lines of my previous post. I have assumed that the cartel does not have any superior ability to propagate its blocks across the network. If the cartel and the non-cartel miners publish a block at the same time I have assumed that they have an equal chance of being accepted by non-cartel miners. This therefore is a lower bound on the cartel attack effectiveness.

When the network generates a block, if the cartel has just one unpublished block then the best strategy seems to be to immediately publish the stored block and let the two race across the network.

Neglecting the benefit to the cartel of punishing non-cartel members, the cartel starts to pay off when its fraction of the generating power exceeds about 41% of the total.

ByteCoin

The raw percentages are as follows:
Cartel power Cartel block fraction
0%   0.00%
1%   0.46%
2%   0.92%
3%   1.41%
4%   1.89%
5%   2.50%
6%   2.96%
7%   3.50%
8%   3.97%
9%   4.56%
10%   5.17%
11%   5.68%
12%   6.52%
13%   7.10%
14%   7.85%
15%   8.42%
16%   9.37%
17%   10.02%
18%   10.76%
19%   11.91%
20%   12.53%
21%   13.51%
22%   14.49%
23%   15.29%
24%   16.25%
25%   17.42%
26%   18.59%
27%   19.53%
28%   20.90%
29%   22.01%
30%   23.27%
31%   24.80%
32%   25.94%
33%   27.28%
34%   28.96%
35%   30.49%
36%   31.56%
37%   33.86%
38%   35.82%
39%   37.23%
40%   39.13%
41%   41.19%
42%   43.12%
43%   44.39%
44%   47.07%
45%   49.41%
46%   51.29%
47%   53.41%
48%   54.98%
49%   56.91%
50%   59.86%

The mining cartel problem is real. The basic implementation outlined by RHorning is well understood but the more effective version outlined by mtgox is a serious problem. I have an obvious improvement to mtgox's improvement as follows:
Cartel miners only communicate their new generated blocks to other cartel miners.
The cartel miners then try to find new blocks based on the previously found but unpublished block.
The cartel miners have a certain probability of being one or more blocks in advance of the rest of the network.
When a non-cartel miner finds a block then the cartel miners attempt to punish them by publishing up to 2 of their precomputed blocks.
If the cartel miners were 1 block ahead then the non-cartel miner stands a fair chance of winning. Obviously the cartel miners will be busy using their block as the base to build the next block.
If the cartel miners were 2 blocks or more ahead then their chain is longer and the non-cartel miner is punished.

People thinking that being a cartel member is suboptimal because honest miners supposedly make more money are neglecting the value to the cartel of punishing non-cartel miners.

ByteCoin

The solution to the front running problem has been solved by Hal in http://bitcointalk.org/index.php?topic=1790.msg29919#msg29919
A suitably salted hash of the required name is submitted for inclusion into the chain. After it has been confirmed then the name (and salt) are published and everyone now accepts the new registration.


I agree that the theymos/nanotube "solution" to this problem is ugly.
There are also serious problems outlined by RHorning which need addressing.

ByteCoin

Awesome, theymos! Thanks for that.

It'll be handy to see during the next spam flood.

ByteCoin

To clarify, the block size limit is the size beyond which a received block will be rejected by a client just because it's too big.

I agree with caveden that having a fixed block size limit could cause problems in future.

Let's consider the scenario in which Bitcoin becomes popular and the non-spam transaction rate starts to rise. The current fees and priority scheme is fine until the size of the fees required becomes a disincentive for new users to start using Bitcoin. The miners must choose between taking a smaller fee from a given transaction or maintaining their fee schedule and effectively turning away lots of new users perhaps to other competing cryptographic currency schemes.
I think it's reasonable to imagine that everyone will decide to drop fees to a level that encourages the widest possible adoption of Bitcoin until other limiting factors (such as network bandwidth) come into play.
So with the reduced fees, block sizes increase until blocks get rejected by old clients with lower hard block size limits. These clients can't relay the new blocks and so new clients would have to only connect to other new clients. Miners which reject the large blocks would continue to build a block chain of "normal" sized blocks. As soon as transactions start to refer to coins in new large blocks then the old clients would reject these transactions and these coins could be double spent on the "old" client network. I don't think this would be pretty.

The ostensible reason for hard block limits is to prevent spam. As ribuck mentions current spam attacks have two effects, one which you can see and one that you can't. You can see block sizes rising but this is an effect which counteracts the less visible problem of your transaction cache filling up with spam transactions. I believe that memory exhaustion due to transaction cache filling will be the main problem with spam attacks so large blocks removing lots of transactions from it will mitigate it. The real solution to spam is "shunning" which I will outline in another post. I believe having any block limits is likely to exacerbate the adverse effects of spam transactions.

As FreeMoney observes, in the absence of block limits there's nothing to stop a miner from including arbitrary amounts of its own spam transactions in the block. This is true. However, it's certainly not in the non-generating client's interest to reject the block even if it only removes a few transactions from the cache. Rather the onus is on the other miners to notice that the new block does not remove enough transactions from the cache and reject it. They will then build the longer chain while ignoring that block which will be an orphan. Hence the spamming miner is punished.

The moral of this story is that the non-generating clients operate on the network at the pleasure of the miners. The miners are effectively in control of the "health" of the network and the current block size limits reflect that. So for example block http://blockexplorer.com/b/92037 is about 200455 bytes long and mostly contains spam. Normal blocks max out at 50k. This shows that at least one generator has chosen to waive the current fees scheme. I think that letting miners effectively decide their own fees scheme will be seen to be the least bad option.

ByteCoin

I agree.

It would be nice to move to an architecture where bitcoind does all the p2p, blockchain maintenance, transaction verification stuff. A gui-less wallet manager connects to some bitcoind via TCPIP to send transactions and receive new payments. This would mean that people can still handle bitcoin payments even if they are not allowed or cannot run a p2p client. The gui should just provide a pretty way of communicating information and commands from and to the wallet manager.

ByteCoin

I believe that it is possible to have a decentralized peer-to-peer crypto-currency solution for frequent micropayments.
There are many parameters to be specified before an appropriate design can be made. Among them are:

• How do you seed the clients with the initial money to make transactions?
• Can they accumulate debts?
• What sort of communication exists "naturally" between the clients apart from the payments?
• Must offline payments be possible?
• Is the system "closed"? Can new arbitrary clients join?
• Is full anonymity desirable or is pseudonymity acceptable?
• Are the transactions a fixed small set of types or do you have to be able to "roll your own" like bitcoin?

If you go into more detail about the application then we can probably infer most of these parameters.

ByteCoin

Does every client have the same list of orphan blocks? Is everyone's blk0001.dat file identical?

I'm trying to investigate the "wasted block generation" issue and it's fairly obvious that my client doesn't have all the orphan blocks. What I'd really need to generate good data is the orphan blocks extracted from the blk001.dat file of clients that have been running continuously for a long time. Better still would be orphan blocks from miners.

I believe that the blocks are only relayed after checks have been carried out and after it has been written to disk. The checks are necessary to avoid relaying junk in the event of an attack but the relaying should happen before writing to disk to keep the latency down and to avoid block loss.

ByteCoin

Artforz data indicates that he sees 0.2% of his blocks "go missing". Our guess is that satoshi saw this happening and fixed the UI to hide the problem but overestimated the frequency of occurrence. 10% block loss implies a propagation delay of the order of tens of seconds which seems rather high.

I requested that miners look for lost blocks and share their data in
http://bitcointalk.org/index.php?topic=1799.msg22508#msg22508

ByteCoin

The .06 in 17yhRAYKJvVmBh14HMxYRHp2Z4erWgk1ne which was MrBurns old spam eventually was transferred to 1GcbuFVxrjstRoGzChn5t2xJnm2HKoDBSE 0.05 and
15JzKgaSoW5nX3qJKh6ze1uCojn9WVVnDE 0.01
in transaction c37dd025e8b7329989ab9ac378604d015895e4ec630c863620a90f3a12f73e76
in block 92767 (2010-11-18 22:51:36)

It got 0.05 back from 1GcbuFVxrjstRoGzChn5t2xJnm2HKoDBSE in block 92767
which was transferred to 14mUbjiofYY2F6h3ZGUSoTo3kxdqtajVTp in 92875

There has been a lot of spamming with 14mUbjiofYY2F6h3ZGUSoTo3kxdqtajVTp but also with
1NNVFX7SiJF44fkqB27QbARXojhRSotF2o which was created from 14mUbjiofYY2F6h3ZGUSoTo3kxdqtajVTp
via 1H2aPofjULC65MBeojs3eVpPvdScV8H9ou
in block  92877 (2010-11-19 15:12:33)

So it's the same person.

ByteCoin

The short answer is yes, it can be done. Unfortunately, evolving attacks to get round the countermeasures is considerably easier than developing reliable, side-effect free countermenasures so it's probably worth thinking about ways to prevent or discourage or minimise these attacks.

The "pruned chain" you suggest is quite a large change to the client and probably can't really solve the problem. A torrent of the chain is just admitting defeat; that the client can't cope with the data distribution.


So who are they and what did they say? I was actually worried that people might blame me!

Ok just found out it's MrBurns... see http://bitcointalk.org/index.php?topic=1835.0

The number of spam transactions vs time between blocks plot is fairly linear. It looks like one transaction is being included every 15 seconds. I think we're getting away lightly at the moment as there seems little obstacle to me to including 50k (or more (500k?) thanks to Artforz) of free transactions in every block.

ByteCoin

The above address has intermittently been flooding the real network with transfers of 0.06BTC to itself. A the time of posting there have been about 2350 such transactions in the block chain. See the following link for details

http://theymos.ath.cx:64150/bbe/address/17yhRAYKJvVmBh14HMxYRHp2Z4erWgk1ne

The transactions must be sized somewhere in the region of 210 bytes which means that half a megabyte of useless block chain has just been generated.

At the risk of belabouring the point, I'd like to point out that clients using "balance sheets" to facilitate deletion of spent transactions would not have their storage requirements increased by the recent attack. An attack differently structured however would have a negative effect on both types of client but the effects on "balance sheet" clients would be limited by the finite divisibility of the coins.

Both client types would suffer from an attack which padded the script instead but again the effect on "balance sheet" clients is considerably smaller.

ByteCoin

In the current block chain, all the transactions (with very few exceptions) are just plain transfers from one address to another. It's therefore easy for the client to work out the current balance but this is something just synthesized from the transactions. If lots of non-standard transactions existed it might be very difficult for the client to work out whether you could spend them and hence it would not be able to determine your balance.

The idea of balance sheets has changed somewhat over time as I understood more about how the scripting functioned. In order to implement a full client while throwing away the most unecessary information, the balance sheet client has to keep all the relevant details of all the unspent transactions. When spent, they are forgotten. It also has to remember a certain number of past blocks.

If balance sheets were implemented then it would no longer make sense to have a fee based on transaction size. Instead the fee would be related to how much new information needed to be stored compared to how much could now be forgotten. It raises the prospect of people getting paid the fees to make the transaction!

Also, for clients using balance sheets the transaction rate would be limited by network bandwidth rather than the block size limits. One might imagine that miners using balance sheets might have a competitive advantage over traditional miners.
Bitcoin peers wishing to use the lower fee structure of balance-sheet based miners might neglect to forward their transactions to traditional miners. This might fracture the network somewhat but the issue is complicated and I will make a separate post about it.


ByteCoin

I've been thinking about your scheme appamato and as we discussed, rejecting invalid blocks and only working on the longest chain is a critical part of the security of these schemes. Therefore all hashing clients need to have the logic to tell the good from the bad. Ths could be done by distributing the appropriate logic for each app as java bytecode or .NET stuff. All clients would therefore understand all apps.

There would have to be some incentive to support an app in this way. Some form of payment.... hmmm

ByteCoin

You don't need to know the contents of every other transaction. You need to have a current list of all the unspent coins and to keep abreast of the changes when they are spent. Spent transactions can be forgotten forever. The advantage of balance sheets over lightweight clients is that lots of the block chain can be forgotten and there are not merkle tree stubs hanging around which are a non-trivial size.

No. Balance sheets are script friendly as they would store the scriptPubKeys of all the unspent coins. I'll admit that when I came up with the scheme I was hazy about how scripts work.


Could you please explain what the real problem is? Balance sheets was intended to enable a fully featured mining-capable client while considerably reducing storage requirements. I believe that hard disk space will become a problem for average users long before network bandwidth or cpu usage.

I'm sorry I didn't notice both your continuations of this thread until today.

ByteCoin

I presume you got your 279 byte figure from the start of key.h. Regardless of what that says the private keys are actually a maximum of 256 bits long. This is because Bitcoin uses the secp256k1 curve. I have also done the maths and it checks out.

The private key is just a number and like a number, the smaller it is, the fewer digits are required to specify it. Therefore, a scratch-off card manufacturer would choose a private key short enough to type but long enough not to be brute forced.
Note that an attacker would not be able to distinguish a scratch-off card generating transaction from a normal transaction in the block chain and so they would have to brute force all suspected unspent coins.

A 13 character case insensitive password of such as WTUYZFK64BOAD would imply a search space of about 2^66 curves. The last characters digits might be exhaustively searched by your client program as you typed it in by exhausting about 50k possibilities so you'd have to enter about 10 characters.


ByteCoin

OP_BLOCKNUMBER transactions are not understood by the current client and their use should come with the proviso that under certain rare conditions problems might occur without any malicious intent. Exactly how rare is made clear below.

At the moment, if you send BTC to an address and for some reason the owner has lost the private key then your coins are lost forever. Payees can lose private keys due to hacking activity, hardware theft, hard disc crashes etc.. OP_BLOCKNUMBER transactions would allow you to recover your money and the transaction could imply a reversion time of months or years in future. In order for a segmentation to accidentally cause problems then the coins would have to go unspent until the deadline was just about to expire at which point the network would have to segment at which point the payee would have to be in the minority portion and try to spend them at which point the network would have to stay segmented until the reversion time had expired. That's a long list of coincidences for it to happen by accident.

On the other hand, exploiting segmentation for double spending is not difficult. Please show me what is difficult about the method I posted. All that is required is one adequately prepared attacker waiting for the network to segment. Anyone on the minority network portion offering goods or services for sale is at risk.

ByteCoin

I've just looked at Artforz scheme which is simpler than yours but my scheme is simpler still and looks like a normal transaction so is less likely to be speculatively brute-forced by an attacker. You say it's horribly insecure. How so?

ByteCoin

OP_BLOCKNUMBER does not introduce any new vulnurabilities compared to the existing system as segmentation can be exploited to defraud people at the moment. This is accomplished as follows:

An opportunistic attacker has clients running in multiple locations around the world. The attacker's clients have the same wallets and connect to different subsets of peers, probably perferring local ones and definitely keeping in touch with local mining peers. The clients communicate with each other at intervals to check whether the network has segmented and exchange the list of peers that they are talking to.
If communication is lost to one or more of the attacker's clients (they go offline) then the remaining clients attempt to communicate with all the offline client's peers. If they all succeed then it's likely that that attacker's client has just crashed or lost its internet connection. If however that client goes offline and a number of the peers are uncontactable then it's possible that the network has segmented. The attacker's clients determine whether they are on the network portion with the majority of the mining power or the minority. They also guess whether the other inaccessible portion of the network has enough mining power to generate blocks over the time it is imagined to be isolated. If the conditions are favourable then the attack proceeds as follows:
The attacker's clients on the majority of the network send coins from the wallet to new addresses in plausible innocent looking transactions. The attacker's clients on the minority of the network use the same coins in the same wallet to buy whatever goods they can find for sale on the subnetwork. When the network joins up again, it's highly likely that the majority part of the network has generated more blocks and all the transactions in blocks on the minority part of the chain re-enter the transaction pool. The attacker's transactions on the shorter chain are discarded as the coins have already been spent on the longer chain. Fraud complete!

So you can see that OP_BLOCKNUMBER does not introduce any new risks and that the real prevention of segmentation-based fraud must rely on some sort of detection of the loss of mining power.

ByteCoin

Are there really so many hashes found that go to waste?

The quote in the comment in ui.cpp says that by design something in the region of 10% of blocks generated won't be accepted, presumably because another block has been found slightly before and is propagating across the network but hasn't reached our computer yet. For about 10% of blocks to be wasted the propagation time for a block from one generator to another would have to be of the order of about a minute! Surely block propagation can't take that long?

Could some keen miner (Artforz) please scour their logfile and find out what the ratio of accepted to rejected blocks is in real life?

Also, I notice that it's in the miner's mutual best interests (jointly and severally) to ensure that they connect directly with each other and not with or via non-generating clients.  It's most important to connect to generators with the highest hash rate.
In fact, there's no incentive for generators to talk to non-generators at all unless non-generators are offering a transaction with a fee!

ByteCoin