With the backing of a bank, it's possible to be anonymous, offline, and prevent double spends with standard user-trustable computation - really, I kid you not.
It relies on having a third party that's trusted to be a reliable provider for value and knowing customers identities to punish double spenders (a Bank). (You can give up this requirement if you want to give up one of the other qualities I mentioned above, but those are different papers ;)
1. An account holder looking to spend creates a coin through a mutual process with the bank, which debits their account. The bank is unaware of the identity of the coin, but knows that it conforms to certain properties.
2. The coin is comprised of multiple parts P_1 - P_n, each of which has two pieces, P_i_1 and P_i_2. The account identity is encoded in the coin such that it is recoverable if and only if one has both P_i_1 and P_i_2 for any i.
3. To spend, for all i, a merchant requests either P_i_1 or P_i_2. (most likely based on the merchant's identity).
4. The merchant eventually turns these coin parts over to the bank, which credits their account. If the bank sees multiple spends of the same coin, only then can it put two corresponding pieces together and deduce the account holder's identity.
There are of course many details that force the parties to behave honestly at every step. The paper is somewhat old and I have no idea of further work (I'm not especially interested in protocols that require a bank or user identities). Main point being that if you do have a bank, designing protocols becomes much easier (Simple blind-signature tokens, for instance. These are anonymous but require online transactions).
Now I'm interested in how step 1 is accomplished, but that's probably too involved for a comment - I have the paper, I'll see if I can figure it out.
Thanks! That was very helpful. A quick skim of the paper backs up what I could find, so it looks like you remembered well enough :)
I think setting n = log_2(maximumNumberOfMerchants) and hardcoding which merchants ask for which pieces is a straightforward way of preventing all unpunished double spends while keeping n relatively small. BTW, with general progress of zero-knowledge techniques I'd be surprised if there weren't a more modern and concise paper in the same vein.