Let's Embrace BTC Trusted Timestamping

[AsymmetricInformation]

Many people, including myself, have a vision of using BTC to make an unalterable timestamp of a file.

________
Background for those unaware:
Unfakeable timestamping is easy to do with Bitcoin because you can just use a SHA256 of any file as a privatekey, import it, and then send BTC to it and back. The fact that you sent BTC to, and then from, the file's associated Bitcoin-key-and-address proves that you had access to the file at a certain time (the time of the transactions).

The low-tech, quick-and-dirty way is to:
1] SHA256 a file containing the contract/great ideas you want to take credit for later.
23e039cf88c6f2fe89415b938d62245af3f339ccf734d8d0c939422c7e4bb8b8

2] Hit up brainwallet.org
2.1] Convert Hex (hash) to Base58 using the convert tab of brainwallet.
5J65yxHPWGfNrXatL8gKwqhFJh9tAXKPmAxYHxFk8b9ACsxd9jS
2.2] Import this as a Private Key on the Generator tab of brainwallet...you will get an associated public key and Bitcoin Address.
1LHnjmyNPDmb9PopeBNrnhNTGVkVkhTGgY

3] Send some BTC to that address using your client.
4] Use brainwallet (transactions tab) to send that money back to your main wallet (the temp wallet created in 2.2 will not be secure when you release the file with all your great ideas, as anyone can hash it).

5] Wait patiently at http://blockexplorer.com/q/addressfirstseen/ for your BTC to show up in the network. Unfortunately this functionality has yet to be incorporated into open-source Abe (and I failed to replicate it myself).
http://blockexplorer.com/q/addressfirstseen/1LHnjmyNPDmb9PopeBNrnhNTGVkVkhTGgY
2013-01-28 05:30:09
________
Previous discussion of this:
https://bitcointalk.org/index.php?topic=52715.20
https://www.strongcoin.com/en/blog/using_the_blockchain_as_a_trusted_timestamping_service
Goblin invented a version of this, but I could not get it to work (sorry!): https://github.com/goblin/chronobit
Someone wrote a paper about this and related ideas: http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=11&cad=rja&ved=0CC8QFjAAOAo&url=http%3A%2F%2Feprint.iacr.org%2F2011%2F677.pdf&ei=OwIGUcqoCarD0AHDy4D4Bg&usg=AFQjCNE53BUwzCopGFXB9lX7F4tOYEpyzw&bvm=bv.41524429,d.dmQ
________


Personally, I envision this as something that would actually make a great core feature. Much in the way that gold is used in industry/jewelry (in addition to being a store of value and medium of exchange) Bitcoins can be used to timestamp files in an unalterable way for ~free (and used for sending international transfers for ~free, unfreezable assets, brain-storage, etc), in addition to being a store of value and medium of exchange.

Personally, I envision a drop down selection in the client GUI (for example **File > Timestamp File**) that just asks you for the path of the file. Easy to use, mainstream for everyone! Likely also a **File > Get File Time** to verify that a file was stamped. Obviously for this to happen there would need to be widespread community support.

Having millions of copies of proof of existance/ownership is way cooler than jewelry! Am I wrong? There are other minor benefits, like responding to people who say that "Bitcoins are inherently worthless / not 'backed' by anything" and helping to explain the sheer quantity of BTC addresses (at minimum 1 per possible MS Word document you could ever create) to people who worry about collisions or make similar arguments.

Your thoughts?

Note: I tried to code all of this myself but I ran into two snags, replicating /addressfirstseen/ and getting a ecdsa public key from a given private key (where is brainwallet.org getting 'G' to do the multiplication???). Im sure the core developers could do the whole thing in like 15 minutes if they wanted to, though, even if it needs to rely on blockexplorer.com's /addressfirstseen/  for now.

[bitfreak!]

I would prefer to have a separate app which is designed specifically for this purpose. Having it rely on blockexplorer wouldn't be too bad imo.

[apetersson]

we had some very similar ideas and came up with these  prototype implementation for both android  (end-user) and python (server) - they work independently.
we also use sha256(file) as the private key, but for now we don't send the money back.

https://github.com/bitcoinaustria/bitnotar

because of the workings of intents, you can use this tool in basically any Android app that supports sharing of content. (text, pictures, videos) it utilizes a generic bitcoin URI intent to send the funds, so you can use bitcoin wallet for android, bitcoinspinner and possibly others in the future.

i think this would be a great addition to dashcam software, for on-the-fly video notarisation if properly extended.

[Andreas Schildbach]

Maybe the "sending back" is actually a not so good idea. Will tx with all outputs spent not be pruned from the blockchain at some time in future?

Just make the amount small enough to not matter.

Then again, if my suspicion is correct and tx will get pruned, and also the private key will be public, people can cover evidence just by collecting the last Satoshis that prove the existence of the evidence...

Generally it's a neat idea but IMHO Bitcoin should not be overloaded with lots of services that are unrelated to payment. We will have a lot of work scaling the payment alone, if Bitcoin catches on.

[Mike Hearn]

I think having this option in wallets would mostly confuse people. It's an obscure concept that has limited utility. Standalone apps are the way to go. If you want to really push this, please make sure OP_FALSE is a standard script type so such outputs can be pruned in future.

[kjj]

Agreed.  This isn't something that should be in the reference client, nor widely deployed at all.  The correct way to do this is either with one of the zero-bloat merged mining systems, or with a web service that can collect a batch of hashes to reduce the blockchain load to one transaction per day, or hour, or block or whatever, and can respend the proof transaction to prevent UTXO pollution.

I've written such a web service.  It is pretty easy to do it right.

[Peter Todd]

Agreed.  This isn't something that should be in the reference client, nor widely deployed at all.  The correct way to do this is either with one of the zero-bloat merged mining systems, or with a web service that can collect a batch of hashes to reduce the blockchain load to one transaction per day, or hour, or block or whatever, and can respend the proof transaction to prevent UTXO pollution.

Agreed.

I've written such a web service.  It is pretty easy to do it right.

Oh yeah? Where is it? I wrote one too, but haven't promoted it because I want to see if I can get a version going that has a P2P layer of co-operating nodes doing the actual timestamping tx. (coinbase or not) Currently mine only supports a single timestamping server, although it's easy to extend it to multiple redundant servers if the servers have co-operating sysadmins.

If there is demand for this stuff, please let us know and we can get a better solution than polluting the blockchain, and especially creating a bunch of unspent transaction outputs. This won't take much time either; I've already done nearly all the work myself. You have to remember that the total number of unspent outputs will be a really big issue in the future, because while not every validating node needs a full copy of the blockchain, every validating node does need a full copy of the unspent outputs. In addition any solution that needs a transaction per timestamp is also going to be paying fees - prohibitive for the dash-cam example above - while the non-blockchain-bloating solutions will be free to use.

[kjj]

I've written such a web service.  It is pretty easy to do it right.

Oh yeah? Where is it? I wrote one too, but haven't promoted it because I want to see if I can get a version going that has a P2P layer of co-operating nodes doing the actual timestamping tx. (coinbase or not) Currently mine only supports a single timestamping server, although it's easy to extend it to multiple redundant servers if the servers have co-operating sysadmins.

If there is demand for this stuff, please let us know and we can get a better solution than polluting the blockchain, and especially creating a bunch of unspent transaction outputs. This won't take much time either; I've already done nearly all the work myself. You have to remember that the total number of unspent outputs will be a really big issue in the future, because while not every validating node needs a full copy of the blockchain, every validating node does need a full copy of the unspent outputs. In addition any solution that needs a transaction per timestamp is also going to be paying fees - prohibitive for the dash-cam example above - while the non-blockchain-bloating solutions will be free to use.

Hidden on my webserver, of course.  I tested the interface and the automation (by running the cron jobs by hand) and made sure it worked.  I just ran out of steam thinking about the next steps (security review, polish, release).  The bitcoin parts of it really are easy; anyone can write one.  Maybe I'll even finish mine some day.

Mine derives a pubkey using the hash of the list of hashes as the privkey and spends all collected fees to that address, then spends it back to a real wallet before publishing the final list.  Zero UTXO pollution, maximum of 2 transactions per block, usually MUCH less.  There was a minimum fee for the notary service with a long service window, and people could pay extra to hurry it along.  The holding time was calculated based on the fees collected and the ages of the documents, so that even a single document with the minimum fee would trigger it after 24 hours.

[Peter Todd]

Hidden on my webserver, of course.  I tested the interface and the automation (by running the cron jobs by hand) and made sure it worked.  I just ran out of steam thinking about the next steps (security review, polish, release).  The bitcoin parts of it really are easy; anyone can write one.  Maybe I'll even finish mine some day.

Mine derives a pubkey using the hash of the list of hashes as the privkey and spends all collected fees to that address, then spends it back to a real wallet before publishing the final list.  Zero UTXO pollution, maximum of 2 transactions per block, usually MUCH less.  There was a minimum fee for the notary service with a long service window, and people could pay extra to hurry it along.  The holding time was calculated based on the fees collected and the ages of the documents, so that even a single document with the minimum fee would trigger it after 24 hours.

Mine is a much more generalized system. The core is a generalized mechanism that takes digests and applies operations to them to produce other digests. Provided the series of operations is one-way, you know that any mechanism that has timestamped the resulting digest, implies every other digest in the chain is also timestamped. To support structures like merkle trees there is code that operates on directed-acyclic-graphs of these operations, and further more code to maintain various merkle tree structures efficiently. It's generalized enough that the whole blockchain can be represented within the system, as well as alt-chains and a whole bunch of other stuff. The actual timestamping mechanism is then called a "notary method" and Bitcoin is just one of many possible ones.

The Bitcoin-specific stuff I have implemented uses multi-sig transactions. For each timestamp I create a transaction spending an input, usually an earlier timestamp, with a scriptPubKey consisting of a bare 1-of-2 CHECKMULTISIG. One of the pubkeys is a real 33-byte compressed pubkey, and the other is just the digest to be timestamped. Thus per digest you just need a single transaction about 200 bytes in size, and again the output is spent and thus prunable. Equally you can use coinbase transactions, and because of the flexibility the client software doesn't care. Each timestamp also includes the merkle path all the way up to the block header itself, so you verify a timestamp you just check that the block header hash is a valid block; this can be done efficiently without the full block chain by SPV clients. You also don't need to implement any ECDSA crypto operations to create or validate these timestamps; just easy SHA256 hashing. An example tx is a467025de01a7707b0f0e3f7bd9ffb94a2eeb02eede115e0dfe4590361655e02

The service I setup just takes submitted digests and builds a merkle tree of them every 10 minutes (currently) and submits the top digest. The intermediate nodes in the tree are saved temporarily for clients to retrieve them once they confirm; I could also email back the timestamps. With the generality you could also use trusted-signature-based stuff like RFC3161 or PGP signing in parallel to Bitcoin to get better timestamp resolution.

I suspect you built your system in significantly less time than I did mine.  

[kjj]

I suspect you built your system in significantly less time than I did mine.  

Not counting the time I spent writing encoders and decoders, and learning the raw transaction API, I'd say less than three hours.  But mine was intended to be a minimum-effort system that does nothing more than prove that some hash X existed prior to some block Y.

[Peter Todd]

I suspect you built your system in significantly less time than I did mine.  

Not counting the time I spent writing encoders and decoders, and learning the raw transaction API, I'd say less than three hours.  But mine was intended to be a minimum-effort system that does nothing more than prove that some hash X existed prior to some block Y.

I started working on mine last June, and went through three designs before I settled on a core structure that I liked. I also was thinking I might be able to write it up as a masters thesis. ("it" as in a complete system including actual applications, good UI's, etc. more of a masters in UI design than cryptography really)

But it still has the "O(n)" problem in that once released people will start running their own servers - n of them - rather than using efficient centralized ones. I was hoping to design a workable, DDoS resistant way of creating a P2P co-operative network for building up the merkle tree that actually gets timestamped, preferably in a coinbase tx, but I haven't figured that part out yet.

Still, as I said above, if people are actually doing blockchain bloating timestamping already, maybe I should just release what I have... I don't mean to offend apetersson, but your bitnotar app really worries me.

[Gavin Andresen]

Is there a lot of demand for timestamping? Are people willing to pay for it?

There are already free, centralized services that will timestamp arbitrary hashes for you. Besides the risk that they might go away (which you could mitigate by getting timstamps from several of them), is there any real advantage to using the blockchain?

If I can already get timestamps for free, why would I bother to pay a transaction fee to get a blockchain timestamp?

I'm often wrong, so feel free to ignore me, but blockchain timestamping seems to me like one of those gee-whiz ideas that appeals to us techies but isn't "enough better" than existing solutions to be interesting to non-techies.

[Gavin Andresen]

There are already free, centralized services that will timestamp arbitrary hashes for you.

.... another random thought:  I wouldn't be surprised if you could get tricky with nonces to get any https-enabled web server to act as a free timestamping service, too...

[gmaxwell]

Timestamping in a scalable way (zero cost) has already been implemented:  https://github.com/goblin/chronobit

No one seems to care about time-stamping at all— so no one is maintaining it, or bothering to build nice interfaces for it.

[Atruk]

Is there a lot of demand for timestamping? Are people willing to pay for it?

There are already free, centralized services that will timestamp arbitrary hashes for you. Besides the risk that they might go away (which you could mitigate by getting timstamps from several of them), is there any real advantage to using the blockchain?

If I can already get timestamps for free, why would I bother to pay a transaction fee to get a blockchain timestamp?

I'm often wrong, so feel free to ignore me, but blockchain timestamping seems to me like one of those gee-whiz ideas that appeals to us techies but isn't "enough better" than existing solutions to be interesting to non-techies.

I'm thinking this might be one of those applications that would be perfect for a merge mined altchain. If the desired feature is timestamping, it shouldn't matter that timecoins aren't worth anything.

[Peter Todd]

Is there a lot of demand for timestamping? Are people willing to pay for it?

Lots of demand, which is why guardtime, Surety and a bunch of other services exist. On the other hand, I'd argue that what those people are selling isn't timestamping, it's lawyers. Specifically the legal frameworks to convince juries and judges in court cases that the timestamps were valid. The actual mechanism is secondary. The clients are specific, regulated markets such as digital evidence, medical trials etc. Note how services not targetting those markets, like CertTime, (graphics designers, now closed) haven't done so well.

There are already free, centralized services that will timestamp arbitrary hashes for you.

Yup, CA's supporting RFC3161 or Authenticode are common.

Besides the risk that they might go away (which you could mitigate by getting timstamps from several of them), is there any real advantage to using the blockchain?

Frankly trust is a big one. RFC3161 and Authenticode are pure "signature-only" timestamps that trust the issuer %100; they don't even have hash-chain-based logging to reduce fraud. (guardtime does this, but it's expensive) Scalability is also a problem: they need n units of server capacity for n timestamps, and the secure hardware running the servers is expensive; all the CA-run servers heavily rate-limit and will ban you if you try to use them in an automated way. This means isn't a free way to timestamp, say, log files as they come in, git revision id's, or say archive.org's webcrawler. Scalability is actually a big part of why I wrote OpenTimestamps: even without the blockchain it'd make timestamping with centralized servers much more usable.

I'm often wrong, so feel free to ignore me, but blockchain timestamping seems to me like one of those gee-whiz ideas that appeals to us techies but isn't "enough better" than existing solutions to be interesting to non-techies.

You can say that for timestamping in general... What a timestamp does security-wise is tricky to understand and use to make something else secure. It's precisely why I thought I could make a masters out of the subject, and a masters that I could actually do at the industrial design department at the art school I got my degree at.

Timestamping in a scalable way (zero cost) has already been implemented:  https://github.com/goblin/chronobit

No one seems to care about time-stamping at all— so no one is maintaining it, or bothering to build nice interfaces for it.

There is a lot of truth to that statement: look at how few RFC3161 implementations there are in the open source world and how there isn't a single package in the Ubuntu or Debian repositories related to timestamping at all. Having said that I think this is because all the existing solutions come from the commercial world of regulated industries and require central services that must be trusted %100 - anathema to open-source philosophy, and more practically, difficult to use because of the need to keep track of revocation lists and other on-going maintenance.

As for chronobit, like Gavin said about ease of use, why would you use something that requires dedicated mining hardware running for a few hours to make a single timestamp when you could bloat the txout set instead? It's bloody inconvenient, and on top of that the resulting timestamps are huge because they depend on P2Pool's linear block chain. (note that without a link to the Bitcoin blockchain the P2Pool timestamp is worthless, and additionally P2Pool follows Bitcoin's 2 hour rule so your resolution isn't any better) It's the same problem with coinbase timestamping: if you implemented it on just Eligius - as Luke graciously offered - it'll easily take a day or two before your timestamp gets into the blockchain. Even just having to wait up to an hour (what I've written) is problematic enough because you really need a server-side mechanism to later send the completed timestamp or the client, or maintain something like a 1s resolution calendar database for later retrieval by the client. (this is how guardtime works)

Ultimately the big thing you're up against is whatever solution you come up with has to be less expensive, in fees and in whatever else the user wants, than the fee to create a transaction. I also suspect that if we do nothing people will gradually find useful things to do with blockchain timestamping, and there's no guarantee the application that does find traction does it right. The dash-cam example above is a good, and scary, example as dash-cam's are really popular in some parts of the world.

I'm thinking this might be one of those applications that would be perfect for a merge mined altchain. If the desired feature is timestamping, it shouldn't matter that timecoins aren't worth anything.

The obvious way to do it - a pure chain with timestamps - is unlikely to work because you probably won't be able to get enough hash power to trust it by itself. Now the shares that make it to the Bitcoin blockchain directly can be trusted but you're back to the "takes a few hours" problem. That said an alt-chain might be part of a protocol to do P2P co-operative timestamping.

[kjj]

Is there a lot of demand for timestamping? Are people willing to pay for it?

No one seems to care about time-stamping at all— so no one is maintaining it, or bothering to build nice interfaces for it.

Indeed.  The world hasn't exactly been beating a path to my door to urge me to release my timestamper.  I made it because of posts here and chats on IRC about the topic, and promptly dropped it when I realized that I had no use for it, and neither did anyone else, so far as I could see.

Bitcoin timestamping has one huge advantage over other services; it is plainly and transparently verifiable.  Other services require trust. *

I might dust it off and polish it up some day as an amusement.  And maybe it'll even be useful some day.  Bitcoin is, after all, teaching all of us to live with trust-free money.  Perhaps some day, we'll have a good use for trust-free timestamping.

* Amusingly enough, this trust is already abused in real life timestamping systems.  Most courts will accept postmark dates as fact, but all serious offices have postage machines that print their own dates, so they are super easy to fake.  The good news is that the post office will scribble out your date and put their own on your mail if they notice something like that happening.  And not much pisses off a judge quite like a lawyer disregarding his duty as an officer of the court.

[Peter Todd]

Bitcoin timestamping has one huge advantage over other services; it is plainly and transparently verifiable.  Other services require trust. *

Note how the need for trust makes existing timestamping useless for anything anonymous, or even just that some large entity doesn't like; Satoshidice timestamped their secrets on the blockchain for a reason.

[kjj]

I'm thinking this might be one of those applications that would be perfect for a merge mined altchain. If the desired feature is timestamping, it shouldn't matter that timecoins aren't worth anything.

The obvious way to do it - a pure chain with timestamps - is unlikely to work because you probably won't be able to get enough hash power to trust it by itself. Now the shares that make it to the Bitcoin blockchain directly can be trusted but you're back to the "takes a few hours" problem. That said an alt-chain might be part of a protocol to do P2P co-operative timestamping.

Check out chronobit.  The merged mining system allows arbitrary numbers of alt-chains to ride along with no additional cost to the bitcoin chain, beyond the first one.  Chronobit uses that system to create provable timestamps.  Oh, and it uses the p2pool sharechain to give (relatively) high precision, and to allow timestamping to anyone that can generate a p2pool share.

chronobit is really nifty.  If I had learned about it before making my timestamper instead of after, I probably never would have started.

[Peter Todd]

Check out chronobit.  The merged mining system allows arbitrary numbers of alt-chains to ride along with no additional cost to the bitcoin chain, beyond the first one.  Chronobit uses that system to create provable timestamps.  Oh, and it uses the p2pool sharechain to give (relatively) high precision, and to allow timestamping to anyone that can generate a p2pool share.

chronobit is really nifty.  If I had learned about it before making my timestamper instead of after, I probably never would have started.

I know about chronobit and knew about it before I started my project - it's clever but it's not a good solution. As you know it works by getting the digest into the P2Pool share chain. The problem is the length of the chain from your share to the blockchain proper is hundreds or thousands of shares, which means a self-contained timestamp is huge - the included sample proof is 475KiB of data.

You also do not get any better precision. P2Pool shares do contain timestamps, but the timestamps follow the same 2 hour rule that Bitcoin proper does. Of course you could try counting the number of shares and multiplying by the average share time, but that doesn't work either as there isn't any way to know if the share chain ending in a Bitcoin block is actually a real p2pool share chain because old shares in the chain are discarded, and it's impractical to store every share ever made. It might be possible to convince forrest to make the p2pool chain an incremental merkle tree so that paths from the chain to a block are short, but you certainly won't be able to convince him to tighten up the 2 hour rule. We've discussed that on the forums before, and any tighter than 2 hours means mining is dependent on centralized timesources, unacceptable.