Blockchain Proof of Location

Bob McElrath
May 17, 2016 · 6 min read

An event (defined by the hash H) can be constrained to exist within a time window A < t < B by hashing H with the most recent block hash A in a blockchain, and incorporating them both into the next block B=hash(H,A,nonce). Bitcoin’s proof-of-work algorithm also has a nonce and I’m glossing over details of combining H from many participants into a Merkle tree. Knowledge or existence of the data corresponding to the hash H can be proven. This is sometimes called proof of existence (in time) and a number of companies are working on it. But spacetime has 4 dimensions (I’m 99% sure, even though silly people write papers about more dimensions than that). What about the other 3?

Can we prove that an event occurred at a particular location in space?

A GPS satellite and a pretty blue sphere

As with proof of existence in time, an “event” is defined by a hash H. Perhaps it’s a hash of a photo you at the Great Wall of China and you want to prove you were there, rather than downloaded an image from the internet and photoshopped yourself into it.

GPS determines location by trilateration on 4 or more “pings” from satellites. Imagine each “ping” comes with an unpredictable hash generated by the satellite, and this sequence of hashes are recorded somewhere for reference. Locations on Earth are then defined by a sequence of four hashes (P,Q,R,S) received simultaneously, along with satellite orbit information, and the creation timestamps associated with each of P, Q, R, S. This point is actually a 3D ellipse that grows with time. As time goes on, more and more people see the same pings, defining a larger error ellipse around the location. So after P, Q, R, S have had enough time to propagate everywhere on Earth, anyone could claim to have been at any point by presenting any four hashes they’ve seen. This happens very quickly because the ellipse expands at the speed of light. The Earth is only about 42 light-milliseconds in diameter, meaning if you could somehow shoot a laser through the center of the earth, it would take 42ms to reach the other side. If we restrict ourselves to lasers on the surface, it would take about 67ms for a signal to go halfway around the earth. So if we want to prove we’re at a particular location we’re going to have to do it much faster than 67ms. With bitcoin’s blockchain at 10 minutes, we could barely prove which side of the Sun we’re on! With a late-ish bitcoin block, we couldn’t prove that we were not on Mars!

“World line” by K. Aainsqatsi Licensed under CC BY-SA 3.0 via Commons (original)

So similar to proof existence in time, presenting four hashes is a one-sided bound. They define what’s known as a future light cone. The four hashes are not known by anyone before the satellites transmit them, so the event lies within this cone, and cryptographically cannot lie within the past light cone (unless your hash function is broken, or the hashes in pings not random).

In order to bound a location on both sides, similar to what I did above with time, we need to give information about the event H to the satellites so they can be incorporated into their pings. If I could communicate with the satellites directly, I would upload H to the 4 satellites I see, and in their next ping they incorporate H, generating a past light cone. The combination of a future light cone and a past light cone bound a region of space and time, and I wish to prove that I presented the hash H to the world within that space-time volume. What we’re really doing is proving that I generated a signal at a particular space-time point, the knowledge of which expands outward in a sphere with time (a light cone) until it is received by the satellites.

The satellites must then incorporate the data received from the ground as quickly as practical, and broadcast a new hash to the world indicating cryptographically that they saw my H. This is quite different from bitcoin which has intentionally slowed down its updates to a 10-minute target “block time,” in order to avoid simultaneous creation of blocks, generating an orphan block and depriving one miner of expected income. However the orphan phenomena is not fundamental and can be eliminated by moving to a slightly more complex data structure which I call a Braid (a small restriction on a Directed Acyclic Graph). More on that in a future blog post. For location determination, we will need to send out blocks very quickly, so simultaneous generation of blocks will happen far more often than in Bitcoin.

Proof-of-work (PoW) is time consuming, and while I’m computing my PoW hash, my light cone is growing and worsening the resolution on my location. So we don’t want to spend very long before throwing out a new block. We do want to keep PoW however because it provides protection against Sybil attacks and removes the possibility that someone can falsify location proofs. A system using signed blocks, sometimes called a Permissioned Distributed Ledger, requires permission to become a block signer. While PDLs have certain use cases, they aren’t as interesting as a public blockchain and aren’t terribly relevant to the topic in this blog.

A chip and a mysterious blue light

Now let’s go one ladder rung deeper into the rabbit hole. Let’s imagine that instead of the GPS satellites, the network of satellites are more akin to bitcoin nodes. Let’s imagine that they each have some PoW ASIC mining chip on board, and that they communicate with their nearest neighbors. Their job is to each collect hashes H from everyone, combine it with their PoW hash and a nonce, and broadcast it to all other nodes. Let’s assume that each node references one or more parents, generating a Braid DAG. The reason to do this is that it can remove the necessity of having a “block time” and allows the network to run as fast as it can.

The only piece preventing this from being a truly decentralized network like bitcoin is the necessity of determining orbital information about the satellites. With a fast enough block rate, this can in principle be determined automatically from the structure of the Braid using only a few reference points, since it forms a time-ordered and space-ordered graph if satellites broadcast hashes to their nearest neighbors much faster than 67ms. One can then have centralized sources periodically measure the orbital parameters of satellites and post that information itself into the Braid. Multiple sources could do this, but it’s a fact of physics that someone has to measure it with expensive telescopes and clocks, and get their orbital mechanics calculations correct.

Finally, one doesn’t actually need to do this with satellites. It could be done with cell phones and cell towers on the surface of the Earth using triangulation. It does require at least three cell towers to receive the same signal from a phone to define the past light cone, and would require cell carriers to do something about their horrendous latency, which is greater than 67ms for all US carriers. Congratulations customer, we have determined that you are on <Earth>! Also you will talk over each other on calls and switch entirely to text messaging. Yes I can hear you, from 500ms ago…

Note that all of the above does not prevent someone from generating a hash H and keeping it secret. The above algorithm really only bounds the presentation of the hash H to the world. H could have already existed. Proving that something does not exist in time or space is a much harder problem, and probably impossible.


SolidX Partners provides consulting and strategy solutions to organizations seeking to learn about blockchain and implementation solutions. The firm also provides blockchain-based software solutions relating to the indelible recording of records, transfer of assets, and identity. For more information, please visit www.sldx.com or email the team at info@sldx.com.

Bob McElrath

Written by

Reverse-engineering the universe and remaking money. Ph.D. Theoretical Physics; Bitcoin hacker; SolidX CTO

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade