Sorry for replying to myself, but I have some more info:

I've found the protocol that is used by that "Bitcoin message service":
http://btcmsg.staticloud.com/btcmsg_protocol_v1.txt

Actually that's pretty smart, and I feel a bit stupid for not having thought of that!

I can do the same of course, and nobody will be able to stop me from doing it (except by convincing me it's a bad idea of course), since this scheme only uses "standard transactions". This does indeed look like the easiest way to achieve my goal, although I need to put a sha256sum into the transaction, so I'll use a new message type ID.

As I said before, I'll use a very low number of transactions (max once every 12 hours in the current design), so my load on the block chain shouldn't be too big. Still, the scheme as used by the "Bitcoin message service" is far from optimal. I think the transaction containing the message could be much smaller if a special transaction type was used, that just pushes some unused data on the stack.

The policy of only accepting "standard transaction" and not "messages" really works counterproductive here. Since nobody can stop people from using the block chain for messaging anyway, wouldn't it be better to have a standard transaction that allows for efficient insertion of small messages? A sha256sum would be the minimum that should be supported IMO. That would allow people like me to insert secure hashes of documents of arbitrary size.

BTW, this reminds me of some people I used to know who played a game of chess by making small bank transfers to each other and putting the chess moves in the transaction comments  .

or use OP_DROP

Another possible approach that had been mentioned before is to make a "fake" bitcoin address that is appears to be valid but instead of being a real address it is actually a user provided hash (after the 1) and then a suffix (to ensure it is parsed as being valid).

You then burn a small amount of BTC by sending to this address (this amount will never be able to be claimed and so cannot be pruned) and then you would have for example the hash of a document permanently recorded in the blockchain.

I guess perhaps even better would be to include a URL in the tx (as a message) so that the tx indicates the original document location (or perhaps just its name or something else).

From https://bt.irlbtc.com/view/2358.0 made by grondilu

Just creates a hash in Bitcoin address format. Sent a small amount to this address. The likelihood of an address existing that matches the hash of your file are pretty darn small!!! Great to prove that something has existed since at least the time of the tx.

The script creates a Bitcoin address only and that address is the hash of the file. There is no private key go along with it. So any BTC you send to that address is gone. It would be pretty much impossible to create a private key to go along with it. BUT, it does create a visible hash that's permanently set in the block chain.

My intended way of dealing with pruning of spent transactions is simple: keep a local copy of the relevant part of the Merkle tree of the block. If I am correct, the root of the Merkle tree is part of the block header, which will be kept forever. And actually spending the coins is not just good for me: it also allows for the pruning to take place, which will help save disk space in the future. I already feel a bit like a socially responsible blockchain-environmentalist  .

If it is possible to use a SHA256 hash as private key and generate a public key and Bitcoin address from that, it seems like an efficient method (less block chain pollution  than the "Bitcoin message service" approach). Of course I'll need to transfer the coins to another address with a second transaction, before publishing the SHA256 hash of the document, or otherwise the coins are free to be grabbed by anybody who knows my method and the published hash.

I think I can make an implementation of this, but I'd appreciate some help on the following:

• How can I generate a private and public key from a SHA256 hash, e.g. using bash and openssl?
• Is it possible to import such a key pair into Bitcoin while bitcoind is running? I have no experience with the JSON API, but from what I read, it doesn't seem to support this.

Someone correct me if I'm wrong, but pruning is just the act of a miner forgetting something they don't need to know anymore. The tx will still have happened and still be in the chain and any service doing lookups of hashes of documents for the purpose of time stamping will be smart enough to not prune. Or maybe you can mark it in some way that lets timestamp checking services forget everything else and remember only the non-financial tx.

If people are worried about the size of the chain, maybe a way to do it is for a company to accumulate documents to be stamped, hash them all together and just include 1 hash per block/hour/day.

In order for this to work, the timestamp has to be easy to verify by a third party.  Keep that in mind when designing your system.  It can't be 100% trusted if it relies on any more than the document and the blockchain IMO.  If you hash a whole bunch of documents together, than all of those documents will need to be available to the third party.  This seems like it would be a problem.

The "master document" need not actually be all the day's collected documents - just a list of their hashes.  i.e. on day X at time Y in block B, a transaction occurred to a private key equal to the hash of master document Z, which therefore existed at that time.  In document Z, presented here Your Honours, we can see that there is the hash of "bob's_contract_of_employment.doc" exactly as shown here.

the master document will have to be published. period

everybody will be able to see the content of it (should be anyway only the list of document IDs and their hashes) and the hash of the document itself would be in the blockchain.
this way anyone could verify if the document of his interest is in any of the master documents, if yes, which one and then test/compare the hashes and verify in blockchain.

edit: this approach will be used for official eu publications. they will sign 1 document containing list of hashes of all files published that day and anybody can verify that a pdf comes from the publication office by checking the hash of pdf, checking if the hash matches the info in the list which was signed and then verify signature (certificate used, if it was not revoked, etc).
the bitcoin/blockchain timestamping is kind of different, has no certicate issuer nor not known yet how the master document (daily list) would be published. but it should be public and tamper proof