7
$\begingroup$

Given a bit string, is it possible to assign it an immutable time stamp that is verifiable as correct without assuming a (one or more) trusted time-stamping authority? A time-stamp is correct if it is within delta milliseconds of the creation of the (instance of the) bit string, for some fixed but small delta. The creation time of a bit string is chosen by its creator / owner (but it is immutable once stamped).

To start off the discussion, I suspect that there will be a need to connect to some sort of physical information source (a la atomic clocks, resistor noise, radioactive half-life etc.) and make some clever use of it.

If it is not possible, I would like an argument that exposes the fundamental barrier. If it is possible, I would like an exposition of the main idea and links to papers or patents for details.

I apologize if my question has a simple answer that my novice mind has missed.

Thank you for considering my question and I appreciate your spending any cycles on a stranger's query.

Update 1: When I say that the creator of the bit string may choose the timestamp, I mean that they can choose when to timestamp the bit string. If they decide to do so at some time t, then the bitstring must be time-stamped to show time t (within delta). It does not mean that the creator can choose any timestamp in the past or future. Such arbitrary stamping must be impossible in the scheme, of course.

Improve this question
$\endgroup$
6
  • $\begingroup$ Nope, its an information thing. I can prove to you that "i had this data at or before timestamp x" with a hash, but I cant prove to you that "I did not have this data before timestamp y" $\endgroup$
    – daniel
    Jun 19, 2017 at 22:06
  • $\begingroup$ @daniel You can't do that with a trusted time-stamping authority either; I assume the asker is looking for something roughly-equivalent to what you could get with a trusted time-stamping authority. $\endgroup$
    – Macil
    Jun 19, 2017 at 22:10
  • $\begingroup$ @AgentME so the answer is "build your own trusted time stamping authority"? $\endgroup$
    – daniel
    Jun 19, 2017 at 22:12
  • $\begingroup$ @daniel -- thanks. Why not? Central argument, links to papers etc. would help. Thanks again. $\endgroup$
    – Swapnil Bhatia
    Jun 19, 2017 at 23:25
  • $\begingroup$ @SwapnilBhatia An example would be if you wanted to prove you had an alibi to a second person. You could show a photo that matches a hash that was made public at some earlier time and then say "this proves I was here at or before this time" but it could be from any time before the hash was publicly disclosed. There is no way I know of to show the photo was from an exact time without using trusted third parties, because to extend with the hash you already have you would have to show that you were not there up until the time of the hash being made public as well. $\endgroup$
    – daniel
    Jun 20, 2017 at 9:31

5 Answers 5

Reset to default
3
$\begingroup$

If being decentralized with no trusted timestamping authority that could backdate things is a must, then the solution is Bitcoin's blockchain (or a similar cryptocurrency's blockchain). OpenTimestamps is a project for efficiently using it to timestamp files.

Most of the design for a possible basic decentralized cryptocurrency has been known since public key cryptography was invented (have a shared ledger of public keys with associated balances, and anyone can transfer currency from their balance to another by signing a transaction with their private key), but it had always been blocked by the double-spend problem (Alice could sign a transaction sending currency to Bob to buy a physical object, and then once it's in her possession, she could broadcast a second transaction with an older timestamp that sends that same currency to a 3rd address also controlled by herself instead, and try to convince everyone else that it came first and should be honored instead of the transaction to Bob). Essentially, without a decentralized timestamping service, there's no way for a decentralized cryptocurrency to get everyone to agree on the same order of transactions.

The double-spend problem was finally solved in 2009 by Bitcoin through its use of a proof-of-work blockchain. Each block contains a proof-of-work based on a hash of the rest of the block, the hash of the previous block, and a list of transactions. People ("miners") are incentivized to compute the blockchain proof-of-works by receiving newly minted bitcoins and bitcoin transaction fees. Each block contains a timestamp, and the proof-of-work difficulty automatically scales so that the proof-of-work (and therefore a new block) can be made every 10 minutes. Every Bitcoin node knows to use the longest blockchain. For an attacker to backdate a transaction N blocks into the past so that it would be before a conflicting transaction, they would have to calculate N proof-of-works, but the while they are computing these proof-of-works, the rest of the miners are on the network are still building the blockchain by creating more proof-of-works. The attacker would have to have more computing power than the entire rest of the miners on the network in order to race them and create a bigger blockchain.

Now to rewind a bit: to actually use this for timestamping files, then you would just want to encode a file (or merkle tree) hash into a transaction in the Bitcoin network. OpenTimestamps is a project for doing this efficiently. (There are other such projects, but OpenTimestamps is much more efficient than most and is made by a Bitcoin developer.) You might be wondering "why involve Bitcoin at all?" and want to extract out its blockchain, but that can't work as Bitcoin's blockchain only works because the miners have a cryptocurrency incentive to contribute, and a blockchain without a significant number of miners like Bitcoin's already has could be easily attacked.

Improve this answer
$\endgroup$
10
  • $\begingroup$ A potential issue with Bitcoin tied certification is that there is only one Bitcoin. When Bitcoin is upgraded, outlawed or plain disappears, all your time stamps become useless and you can't prove nothin' to no one anymore. Just like my 5" floppies. $\endgroup$
    – Paul Uszak
    Jun 19, 2017 at 23:23
  • $\begingroup$ @AgentME -- thank you for your answer. Could you explain how it gets away from assuming a trusted time-stamping authority? My limited understanding of blockchains is that they all require a time-stamping authority, even if decentralized/distributed. Thanks again. $\endgroup$
    – Swapnil Bhatia
    Jun 19, 2017 at 23:26
  • $\begingroup$ @SwapnilBhatia Bitcoin has no central authorities or specifically trusted members with the ability to forge an old block / timestamp. $\endgroup$
    – Macil
    Jun 19, 2017 at 23:45
  • $\begingroup$ @PaulUszak Everyone that runs the bitcoin node has a full copy of the blockchain. Even if everyone else stopped using Bitcoin, you could still have your copy of the blockchain. (It would be easier to attack if no one at all was mining any more, but an attack would still be very slow and expensive - measured in the millions of dollars easily -- for someone to make their own copy of the blockchain with backdated data.) Also, consider that the Bitcoin market cap is $42 billion. The many people owning that are heavily incentivized to keep maintaining Bitcoin and its blockchain continuity. $\endgroup$
    – Macil
    Jun 19, 2017 at 23:54
  • $\begingroup$ @AgentME Thanks. Still trying to understand your answer. So if I created a novel bit string at time t independent of any other "transactions" or other bit strings and submitted it for time-stamping, and say it got time-stamped as t - 2 x delta. Would any blockchain rules detect and refute this? Do any of blockchain rules imply real wall clock time or merely relative ordering? Also, my question specifically asks for a possible/impossible mathematical argument and not just a market cap difficulty. I'm looking for a trust-independent time-stamping mechanism. Thanks! $\endgroup$
    – Swapnil Bhatia
    Jun 20, 2017 at 6:15
1
$\begingroup$

Technically no. But practically, possibly, yes.

Time is an absolute measurement using an agreed standard (UTC, hours, minutes, seconds, etc...). It's a human construct to log a progression of local (cosmically speaking) events against. By its definition, it requires a "witness" to validate, which is the same as saying "authority".

Note: It's very important to consider the application of what you're trying to achieve with a time-like stamp without an "authority". You might have a very specific problem in mind, which might have a specific interesting solution.

Does this mean that there's nothing here to discover/invent? I don't think so. The problem is "time". I suspect, if you remove "time", and step back toward a more universal fundamental of "events", you might have a better chance of achieving your background requirements.

Consider, in a hostage situation, they will ask a hostage to record their plea while holding a current newspaper. Why? So they know the video was recorded very recently. Absolute time is a factor of the proof here, but importantly so are "events". The time is implied by the newspaper edition, the content, and the fact that no one can predict the future (tomorrow's newspaper). This doesn't work in digital timestamping type scenarios of course, but it helps to describe how "events" may be key, not quantum-level events, but most likely more macroscopic events.

Picture of the night sky

Here's a poor, but workable option which shows there may be hope. The planets, constellations, and more have been used for hundreds of years to determine "time". Manuals are required to map such cosmic "events" to our agreed standard of "time".

One could take one or more photos of key features in the night sky, possibly also requiring telescope(s), with superimposed hash value in the image.

There are many other possible schemes for making the night sky, but most (if not all) require a photo. Of course, it's possible to photoshop, so it's not perfect. Also the time precision is relatively low.

Relative events

Going back to "applications" and context. If your purpose was to ensure that you paid money before a package was sent, then it's all relative. It doesn't matter what the time is, you only want to determine which event happened first. This doesn't necessarily require an absolute event reference (space). If you're both in the same room hand over money, and then hand over the package, you see it happen. If you do this from a distance, you need a witness/authority/third-party.

So technically the way we do it currently is for a reason, no other compelling way has been found yet. The same issues compound problems with HTTPS certificates involving revocations list, OCSP stapling, and more.

It's good to step back to analyse the problem in more conceptual abstract ideas to answer such questions.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If you could successfully Photoshop a time stamped image, that would effectively be creating a hash collision in a modern hash like SHA256/512. It's not possible (yet). $\endgroup$
    – Paul Uszak
    Jul 7, 2017 at 3:14
  • $\begingroup$ You may have misunderstood (or I wasn't clear enough). RE: "photoshopping" - that would involve faking telescope and camera pictures of certain positions of celestial bodies. That's not equivalent to a hash collision, one can know the right positions for a given time and fake them visually in a picture. As I said, it was not a perfect scheme, but food for thought. $\endgroup$
    – Kind Contributor
    Jul 7, 2017 at 3:53
  • 1
    $\begingroup$ Timestamping based on bundling an item with a newspaper headline or a photo of the night sky works to establish that an event happened after another thing (the hostage is still alive after this point in time), but it doesn't work for establishing that an event happened before another thing (I invented this machine design before company X filed for a patent on it) because anyone in the future could find an old newspaper headline, sky photo, etc. $\endgroup$
    – Macil
    Jul 7, 2017 at 20:03
  • $\begingroup$ @AgentME Correct. That passage was a discussion about relative events. That example showed the use of a connection of events. I didn't claim it would work for "timestamping" situations. My answer was that it was not technically possible to do without a trusted authority/witness, but I suggest if there is a solution others should think down the path of "events" not "time". $\endgroup$
    – Kind Contributor
    Jul 8, 2017 at 1:30
  • $\begingroup$ @todd thanks for some interesting examples and avenues. As agentme points out, I am looking for an absolute timestamp provable to be within delta. Yes, I am open to a solution that involves events. Your chain of thoughts on celestial images is similar to the tracks I thought would be needed for this. I look forward to other ideas. Thanks again. $\endgroup$
    – Swapnil Bhatia
    Jul 11, 2017 at 1:55
0
$\begingroup$

It is mathematically possible to time stamp against publicly available information. I'm not aware of anyone doing so commercially (notwithstanding Bitcoin and derivatives), but I see no fundamental technical impediment. So we can do something as simple as:--

certificate = SHA256(bit string | public entropy)

where bit string is your document that you want time stamped, and public data is a freely available source of entropy for that particular day. The trick though is not to use physical entropy. That's impossible as entropy is only created by the observer and not the physical process, hence no two measurements of anything physical are 100% identical. The avalanche effect negates this possibility.

You use social entropy. For example the stock market. Every afternoon that the FTSE250 closes, well over 8000 bits of true entropy are created from the individual companies' transactions. (I haven't yet measured entropy generation for any other major index.) That's vastly more than the bits required for any possible contemporary hash. This entropy is well catalogued by many independent institutions and publicly available throughout the world. Simply hash your document against that day's close. The FTSE250 is never closed for more than three days at a time, so your time stamp would have a max. resolution of +/- 1.5 days. Not perfect, but something to consider.

To verify the time stamp, you just simply check a particular day's close and rehash your bit string against it.

Off topic issues (but very important):-

There is an argument to be made that the London Stock Exchange is an authority. Yes, but at some point along the line you have to trust some aspect of society. Or we'll all end up in a Mad Max scenario fighting over the last few cans of tuna. It's incredibly regulated and monitored by thousands of professionals and amateurs. If the FTSE100 /FTSE250 were to be adversely manipulated, your least concern will be whether you can verify your bit stings. Bitcoin or the NIST randomness beacon could easily disappear tomorrow without too much negative effect. Not so a major stock market.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ The main reason for timestamping is to prove something happened "long ago". The past is well recorded and public, so you can use that as a signature. That is, at 2000-02-02 you can use "public entropy" of the day, then later in 2010-01-01 before a court case, you can also know and use the "public entropy" as of 2000-01-01, and re-sign a document. Such entropy could be a useful entropy source for generating a random key (in addition to many other additional sources which are XORd), but not as a timestamping mechanism IMO. $\endgroup$
    – Kind Contributor
    Jul 7, 2017 at 3:57
  • 1
    $\begingroup$ Thanks Paul, for your answer. Perhaps my question is not completely clear. When I say the creation time of the bit string is chosen by the creator, I mean that the timestamp on the bitstring is may be chosen by the creator to be the current "time" at any time, and not that the owner can choose to timestamp it to any time in the past or future. Your scheme appears to fail this admittedly vague constraint. I will clarify my question so it is not confusing in this regard. Thank you again for your work! $\endgroup$
    – Swapnil Bhatia
    Jul 11, 2017 at 2:02
  • $\begingroup$ @SwapnilBhatia I'm probably still misunderstanding you . You can time stamp this comment as of yesterday's market close (1630 hrs). The few hours delay is the resolution /delta that you're talking about. And you clearly can't time stamp into the future as you don't have the market figures for next week. And you can't make them up either as you'd have to predict >8000 bits of entropy. $\endgroup$
    – Paul Uszak
    Jul 11, 2017 at 2:35
  • $\begingroup$ Thanks Paul. But could you not also timestamp it to Jan 1 2017 since that info is public? The delta is a fixed given resolution and you can "cheat" within it. But the scheme must prevent cheating outside of it. Is that clearer? Many thanks for giving my query the privilege of your thinking! $\endgroup$
    – Swapnil Bhatia
    Jul 12, 2017 at 16:55
0
$\begingroup$

If your definition of Timestamping Authority (TA) is relaxed enough, I can think of a few options, which are not a "remote server" TA. Also this is a very different approach and answer to my other one.

  1. If this doesn't need to support thousands of transactions per second, per user; and if it's about proving in court, then you can spend more time on the timestamping process.

1a. You could use one or more chemicals and isotopes and imbue paper with the claim information hashed and printed on that paper. Or something of this nature. Might need those chemicals in the ink which reacts with air.

1b. Or, you could copy the manual legal process: have someone "witness" your timestamp claim. They can physically sign some paper with the claim, or do so with digital signature means.

  1. Another approach, which deviates only a very little from your banned TA remote service, is to have a distributed and possibly hierarchical delegation of a trusted third party.

2a. So a post office could officiate with digital means, or perhaps extending 1b, but requiring a hash of claims to be sent back up the hierarchy periodically for ultimate authority.

2b. A portable tamperproof device could be used to delegate the authority. It would accept a hash, and output the timestamped signature. This could be a compact smartcard device, and may have USB interface. It would have a lifetime limited by battery.

  1. Trusted peers could be used without a hierarchy of authority. If you have a claim hash, you can ask those who you esteem to timestamp it. If a claim invokes a contract, each party would have their own set of peers to timestamp. If it went to court, those peers would need to inspect the timestamps and testify if they're valid. The more peers, and the greater their trustworthiness the better. But one need not have a "common" trusted third party.
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks @Todd. 1 an 1a are OK, but other points assume a trusted third party, so they violate the scope of this question. Thank you. $\endgroup$
    – Swapnil Bhatia
    Jul 16, 2017 at 21:23
0
$\begingroup$

The number of novelty chess positions in a grandmaster quality chess game is a measure of time. It is constantly updated and tracked in chessbase. Such novel position is on its own a proof of work. It can be used to timestamp something.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.