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.