In a centralized system, the server could simply keep a list of extraNonces in active use and give out the lowest free one.  Then you would avoid collisions without requiring more than one unique extraNonce per client.  A 3-byte extraNonce would be sufficient for millions of clients.  Note that clients of realistic performance do not really need the extraNonce to handle nonce overflow today, since such overflows happen less frequently than the periodic nTime updates (but this is not considered by the standard client today, which updates the extraNonce more liberally).

But that effect would be totally insignificant.  Even the standard client is optimized so that it doesn't need to hash the entire block header if only the last part of it has changed.  That last part includes the nonce but not the extraNonce, so a larger extraNonce wouldn't cost anything for the vast majority of all hashes, namely those where only the normal nonce has been incremented.  With today's transaction volumes, the cost of hashing the extraNonce should be less than a millionth of a percent for pools with thousands of members. 

Agreed, that also solves the problem.  But is a much more extensive change to the system that changes it in many other ways as well.  It is more difficult to analyze.  My proposal is just a small tweak to the existing algorithm that preserves most of its current characteristics.  Adjustments would still be synced on a block boundary, so no stronger time synchronization would be needed.  No additional communications between clients would be needed.  The frequency of the adjustments would still be low (but more stable) so no additional sensitivity to latencies.

Running 32-bit Linux on an AMD Athlon 64 X2, I get the following results:

  normal: 2850 khash/s
  with -4way: 1708 khash/s

I haven't checked if the hashes are correct, just the speed.

Sweden.

This is a good point.  I don't think I underestimated people's ability to generate bitcoins efficiently and legitimately - the difficulty adjustment does a good job of compensating for that, and that makes it a non-issue in my scenario.  But I probably underestimated the effect of minters using other people's resources without their knowledge and consent.  The FAQ theorizes that the cost of minting will approach the price of electricity minus a thin profit margin, and I probably accepted that theory too uncritically. If resource theft becomes the primary way to finance bitcoin minting, flaws in the difficulty adjustment will have a more subtle impact. 

Could you elaborate on what kind of scenarios you see where the proposed algorithm would be more vulnerable than the current one? Note that the current algorithm also uses wallclock time in the difficulty adjustment calculation and is synchronized using newly generated blocks.

It's in my original post:

Sorry, I was wrong about that.  I though I had read something on the forum to that effect, but now I can't find it.  Looking at old sources, I see that the 4x cap was there as early as bitcoin-0.1.0.rar, so this is definitely not a new modification.

1) No.

2) Yes.

3) About three weeks.

4) 3 blocks.

5) Mostly for fun, but I won't keep generating once the difficulty adjustment turns the profit into a loss, which I believe will happen quite soon.

Sure, I just thought this was an unnecessary cost, best avoided by fixing the algorithm before it causes real problems and associated costs.  I understand that the 4x limit to the difficulty adjustment was added quite recently, so there is some precedent in fixing problematic aspects of the algorithm.

Actually, I was not assuming that.  In the scenario, the profit margin of 10% was the typical profit margin, by which I meant that most of the minting was done by players with a profit margin around 10%.  The scenario assumed the fluctuation in minting activity to be 20%, so it allows quite a lot of variance around the 10% mean without affecting the outcome as long as the bulk is within the 0%-20% interval (and the bulk cannot very well be above 20% - then the typical profit margin would not be 10%).

Regarding the effect of transaction fees, they may alleviate the problem somewhat, but at an unnecessary cost.  There will be some balance between monetary costs and convenience costs, but avoiding the costs altogether seems preferable to me.

Well, there might be an important psychological difference between being marginally profitable and by clearly losing money.  The range of efficiency in bitcoin minting is such that some people may be profitable at a difficulty level where most are clearly losing money.  If this happens, I suspect the share of nonprofit minting activity would dwindle quite quickly.  We are then in the unstable situation I warned about.


Of course I'm worrying - my entire bitcoin fortune (150 BC) is at stake here! 

There is a limit to the difficulty adjustment, but for upward adjustments it is 300% (factor of 4 between new and old) rather than the 20% in my scenario, so it wouldn't help. 

I would argue that a 20% difficulty adjustment is in no sense extreme - the last five adjustments were 44%, 35%, 300%, 93%, and 21%.  This hasn't been a problem up to now, but obviously not because a 20% adjustment would be too extreme, but more likely because it hasn't been enough to make minting unprofitable (or otherwise uninteresting).  My scenario does not assume that a single entity is responsible for a jump in difficulty - it is just as problematic if e.g. publicity makes minting 20% more popular at a time when the profit margin is less than 20%.  The extreme effects come from the proportion of minters who are unwilling to continue minting at a loss.  If this proportion is large while the profit margin is low, the system becomes very unstable.

Also, if I am right about the 4-year halving of bitcoins generated (i.e. that it doesn't affect the difficulty adjustment) such events alone would be equivalent to a 100% upward difficulty adjustment.  And it seems very reasonable to assume that most minters will have a lower profit margin than 100% in the future.

The difficulty for generating bitcoins is periodically adjusted using a method
that has worked well this far.  However, I am afraid there are plausible
scenarios where the current method would misbehave quite spectacularly.

One scenario goes like this:

1) As bitcoins become more known, competition among minters continues to
    increase, with corresponding increases in difficulty.  The increased
    difficulty will eventually make bitcoin minting clearly unprofitable for
    those who do not have access to good energy prices and cheap access to an
    energy-efficient HW/SW combination.

2) Some bitcoin users may continue to mint bitcoins even though it is not
    profitable for them.  This could be due to ideology, the fun factor, or
    just ignorance.  But it is quite plausible that the vast majority of
    bitcoins will be minted by those who profit from it.  Let's say that 99% of
    all bitcoins are eventually minted by for-profit-minters.

3) The competition among for-profit-minters will drive profit margins down, to
    the point where it is profitable to continue minting, but barely so.  Let's
    say that the typical profit margin during one difficulty adjustment period
    (2016 blocks) is 10%.

4) Since bitcoin minting is a decentralized uncoordinated process, we can
    expect random fluctuations in bitcoin minting activity.  This does not
    affect the difficulty during a specific 2016-block period, so the minting
    activity can e.g. increase by 20% during a period without making minting
    unprofitable within that period.

Given the above assumptions, we now have a disaster at hand at the next
difficulty adjustment.  As bitcoin production was 20% more than target,
difficulty is adjusted upwards by 20%.  But the profit margin was only 10%, so
for-profit-minters would now lose money if they continued minting.  They will
therefore stop minting, and as they make up 99% of the minting capacity,
generating the next 2016 blocks will take 100 times longer than normal.
Everything that depends on block generation will slow to a crawl, and this
slowness will persist for a very long time, since the next 2016 blocks will
take 100 times longer to generate (almost 4 years rather than two weeks).

Now, if this was to happen, I guess a new client could be released that resets
the difficulty to some sensible number and started using a better algorithm
for difficulty adjustment.  But it would be much better to do it proactively
before it becomes a problem (perhaps with a predetermined "flag day"
activating the new algorithm at a certain time in the future, giving the new
client a chance to propagate).

A simple(?) modification of the algorithm would be to apply the adjustment
after a certain amount of time rather than at a certain block number.  The
switch could still be synced to take effect for the next block, so time
synchronization between clients would not need to be super exact to have the
vast majority of them agree on when the new difficulty is to be applied.

Also, the difficulty adjustment should probably take into account the
adjustments of the number of bitcoins minted per event (now 50, halved every 4
years).  Halving the number of bitcoins generated each time is equivalent to
doubling the difficulty as far as profitability is concerned, and such a
drastical drop in profitability is unnecessary if it can be avoided easily.
I'm not sure if the current adjustment algorithm already takes that into
account somehow, but I couldn't see any obvious adjustment for it in the
source code.

Perhaps it would help to be more clear about the Faucet operating on an honor principle, and that no one is really allowed more than 5.05 bitcoins (or 0.55 bitcoins if you change it to that).  When I revisit the site today it says "Right now the rule is 0.05 bitcoins given per unique IP address."  Such language could be interpreted as if it was actually OK to get more payouts from the Faucet using several unique IP addresses, since it would not be "against the rules".  Improving the technical system to prevent cheating is probably a good idea anyway, since there are probably cheaters who don't care about being cheaters.  But some may actually think they are just being clever, maximizing their benefit without breaking any rules.