A lot of people out there are starting to do more interesting stuff with multi-sig, often involving multiple parties combining their keys in transactions to create a P2SH address.

When one of the parties comes to actually spend whatever's been sent to that P2SH address, they're going to need the original public keys to recreate the P2SH address, even if they don't actually need the corresponding private keys that would allow them to sign. So this information needs to be stored somewhere. We want this to be around even if whatever site may have helped set up the transaction has gone away, and it probably doesn't need to be secret, since it's ultimately going to show up on the blockchain anyway. I guess that implies we want it to be mirrored in several or more places, ideally run by a mix of different people in a mix of jurisdictions.

I know there are a bunch of clever data alt-coins and things in development, but has anyone got any suggestions for something practical we can use for a web app right now? We all love P2P but if there isn't a good fully P2P solution I think the "reasonably trustworthy vendor" model is OK here, as long as you have the data synced to reasonably diverse reasonably trustworthy vendors.

Basically I guess we're looking at an append-only public data storage for shortish bits of data. (I guess the fiddly bit is how you do anti-spam, since it's hard to squeeze "pay the data storage guy" in some of these workflows until you actually do the redeem.)

I know I'm not the first person to be feeling pain here - any suggestions for something that would be good to use, or if not any thoughts about what would be a useful thing to build?