There are basically only two reasons (on a macro scale) why a currency would undergo deflation
You're missing a third one that's potentially very relevant to Bitcoin: the money supply decreases due to hoarders taking money out of circulation.
Consider that in the first case, this is entirely normal and healthy! If the money supply is held constant, yet the productive capacity of the economy increases, there will be the same number of dollars chasing more goods. Inflation is the exact opposite of this, whereby same dollars are chasing fewer goods (or more dollars chasing same/less goods). Clearly deflation in this sense is beneficial for consumers. We see this taking place in the electronics industry which is largely free from government regulation and subsidies. When competition is fierce, the productive capacity of industry over-rides the inflationary aspects of our fractional reserve economy and we see prices come down as more and more electronic goods are produced more efficiently.
Debatable. IIRC the problems caused by this are partly why no countries are on the gold standard anymore. More unpleasantly, there's a really nasty catch in the "productive capacity of the economy increases" part, which I'll come to in a bit.
So let us look at Krugmans second argument that deflation makes debtors worse off. What is left unsaid in this assumption is that debt is a good thing, while saving is a bad thing. Does this make any logical sense to anyone? Consider that if money is undergoing deflation, SAVERS benefit. Shouldnt the savers naturally benefit more than someone who is putting themselves into debt? Savers are forgoing pleasure in the moment for the expectation of even greater pleasure in the future. This means resources that could be consumed immediately for minimal productive gains are being put aside into bigger projects that could yield even greater gains in the future. Savings is what builds strong economic foundations. If the US wasnt so wildly in debt at the moment we would be in a better economic position with larger prospects for growth!
You seem to have got this exactly backwards. Remember that money itself isn't intrinsicly worth anything, it's just a way of allocating resources. So someone that stuffs $1 million under the mattress for future use actually benefits the ecomomy far less than someone that goes $1 million into debt in order to start up a new business. Now, what you were saying would be true if savings worked the same way in a deflationary economy as in an inflationary one with the money saved being loaned out through fractional reserve banking, but they won't - that's why savers can benefit even though it harms debtors.
But also let us consider the impacts of deflation on interest rates. People who lend and borrow money will know that money will be worth more in the future if the money supply remains constant (like Bitcoins) yet the productive capacity of the economy continues to increase. This leads to falling interest rates. Interest rates will naturally come down in a deflationary environment because savings will increase, thereby making more money available to banks to lend.
It may decrease interest rates in
nominal terms, but in
real terms - which is what matters to debtors - they will increase. If the real-world value of your debts increases due to deflation, that's effectively interest from your point of view, especially since your income will also be affected by deflation.
Consider if you were in this situation:
Your employer gathers up all the employees for a conference and tells you that because the economy is so productive and that the value of money is going up so much, that he is going to have to furlough the workforce to deal with the appreciating currency.
From your perspective, you are getting more time off while your income remains exactly the same in terms of purchasing power. Who doesnt want that? Further, consider that if you dont get a raise every year, YOU STILL GET A RAISE! Employers dont necessarily have to cut wages; they can cut hours or simply not give raises yet people would still be better off than they were the year before.
But lets say the economy is so productive that money gains so much value that employers are simply forced to cut wages if this was the case, would anyone seriously give a damn? We would be living in a nirvana society that had absolutely ridiculous amounts of abundance. Women could stay home to take care of the kids, one man could provide all the income necessary to take care of his family and still retire, kids wouldnt have to work three jobs to put themselves through school, etc
etc
etc
Less people would need to work in such an economy (like they did in the 50s and 60s) which would relieve the need of employers to cut wages.
OK, this is where things get nasty. You talk about productivity gains, but so far they've mostly happened through decreases in the amount of labour required to manufacture items; the raw materials and capital costs have remained substantial and often even increased. This means that wages have generally decreased far faster than the costs of items have - this is a problem even without deflation. So an increasing amount of the cost of goods and services is going to a handful of very wealthy individuals that control the resources required to produce them. While we might end up with ridiculous amounts of abundance, the vast majority of the population isn't going to see it. What's more, the gains don't happen evenly: the cost of producing shiny technological items has decreased massively, but the cost of essentials like food and homes hasn't.
The other catch is that not all sectors of the economy benefit equally from this increase in productivity: in particular, for the most part service sector jobs haven't changed very much at all.