Topic: Proof of location (Read 4813 times)

Spoofing can never be prevented as long as a piece of software relies on information from another piece of software or human...mainly how the big game companies have decided to try to "ban" GPS spoofing is from 'moving too fast' or just banning rooted devices/devices capable of spoofing. Which then you could just spoof your device to look like it isn't capable of spoofing...see the problem?

Topic is very interesting to follow, it seems this is worth following this thread so I got new experience from the topic being discussed. good luck and thank you.

Looking at this thread, I am having so many regrets right now.

I would think that it would cost a lot less then this to spoof your location.

Wouldn't it be cheaper for your friend to simply go to this location for a month, rent a room, buy a computer and actually be in this location?

Proof of Location - useful for contract law or proof of legal transaction.

Augmented reality games or not, if real value were ever associated with proof-of-location then I'd imagine people would attempt to develop and sell location remoting services. For the system to work the value of the proof has to be less than the cost of "spoofing" a location.

In a somewhat related example, I knew of somebody who needed to trade as a non-US person on a well known Bitcoin exchange. The cost of setting up a non-US account and a secure computer in a foreign country was well within his budget given the particular circumstances. So he went ahead and did it although it cost him almost $10K. The setup served him well and in spite of AML/KYC checks he was able to trade from a fake country under a someone else's name.

this topic relates to cheating in augmented reality games. I'm sure it is very popular still not solved problem

And it would solve it in a way where deployment of stake feeds back to the infrastructure Bitcoin lives on. Or to put it other words from a private discussion I've had:

By now, there was no theoretical argument which discards the proposed protocol. If issues under footnotes 4) 5) and 7) are addressed, it can be practical as well. What we'd need is further discussion from guys with hardcore implementation knowledge for sure. Probably this should go into the technical board, OP/Mod?

Community based currencies are a big topic, like "Brixton Pounds".   The idea has massive impacts on local economies.  Google prof Jem Bendall, he's the one that got Uni of Cumbria accepting BTC for tuition fees.  Its combining crypto with those philosophies.

I have been thinking about this idea too.  Would be interested to see what comes out of this thread.

This would solve the distribution problem of PoS crypto.

Nice work on your research project OP! - there are several intriguing points been made here. I'm just a lowly geologist so not proficient with coding and cryptographic signatures. However, I do frequently sell on Localbitcoins and the geographic data provided (IP, International phone code) acts as another level of security and authentication between myself and clients.

These are regional proxies and our actual location is never disclosed for security reasons akin to that reporter singling out Dorian Nakamoto.

Imagine this scenario; An organized, well funded group monitor larger transactions that pass through the blockchain, extrapolate your IP to GPS location, pay you a visit, forcibly make you transfer Ƀ holdings.

It's a serious issue, would like to hear more        

To curb contest of space which is unreasonable, just tie transaction rewards to where they've been initiated. So if you have users somewhere, providing resilient internet access + mining will be profitable (and make sense).

On the spatial partitioning scheme: one could refer to recursive schemes like BSP or octrees. Then, in places of high use, high density of mining and high competition, the space would be partitioned. Much like the self adjusting difficulty algorithm, only tied to actual meaningful supply/demand.

mobile phones have GPS and are more widely available than desktop PC's. Bitcoin is kind of a very clever hack on TCP/IP. but showing its limits these days. if 5 mining pool operators validate everything, there not much point in the P2P part anymore. proof of location is one of the approaches which could work. I'm not aware of any other than proof-of-work and proof-of-stake.

Countered by proof of tor? 

very good insights. I would note that hashing power accumulates in several distinct locations (data centers). The more geographically distributed mining would be, the more it would be owned by different people. unfortunately we can't just require that. imagine a reward that declines the more you mine from one location. miners would make the effort to open up new data centers, but this activity would be unprofitable, so that new miners could make more.

thinking about these things I find very fascinating, also because historically currencies were tied to geography / population, and there are good reasons for that. my idea of proof of location was a replacement for proof-of-work, or perhaps augment proof-of-work. essentially each of the describe segments (what you called cubes) would be tied to the money supply. the more segments get involved the better. one could imagine software for trading between those cubes as well. for example imagine a good being shipped from one location to another tracked by the Internet. each segment has a cost function. so instead of shipping companies you would have a public agent-transport-network. this can applied to just about any productive process.

Proof of location & connectivity could be huge for dezentralization, an utilitarian incentive mechanism, scalability issues and increasing overall internet resilience.
Here're my ideas to that.

Introduction

Essentially, current PoW schemes rely on fundamental physical objects that cannot be effortlessly replicated. In case of Bitcoin it's the existence of hashing power. Gold in that sense has has the same property: It can't exist in two locations at the same time. Either its in a vault at one given time, buried underground, used in electronic equipment, etc. However it cannot exist at different locations at the same time ¹⁾. This is a precondition of why people trust in bitcoin and trust in gold as an unforgeable signal of state and hence are willing to use it as money. Economists refer to that as scarcity.
Other phenomena exerting the same property and commonly accepted by mankind are space and time. In fact, everyone agrees that nothing with physical presence can exist at the same place at the same time ²⁾. Just as historians arguing to reach consensus on historic events and its many interpretations (records of history are by definition incomplete), the trick is now to reach consensus on what exists at a certain time at a certain location. In the virtual world of internet, existence of rudimentary form is usually implemented by simply pinging each other.
Now, what if you could incentivize discovery and disclosure of nodes' locations in a way that honest reports are rewarded and dishonest reports are rejected, set aside a sophisticated collusion of the majority?

Decentralized Graph of Connectedness

In the virtual world, distance can be measured in terms of stochastic sampling of minimal ping response times. The lower the response time, the closer A to B. This probably correlates with physical distance, but not necessarily so. Network topology, hardware and routing are determining factors above all.
Just as in the physical world, relative location in the n-th dimension can computed by triangulation if one knows the distance from a set of n+1 nodes. For the time being though, it suffices to ascribe every active node in the network its ping times to its peers. Because ping times in principle are the same in both directions, the stake of connectivity can easily be verified and agreed on.
But why would a node in the network even report the true ping time or even worse, refrain from emulating seemingly consistent response times with his peers to forge an arbitrary location? In other words, nothing should stop a hostile node to delay pong responses consistently but with random offsets in order to spoof identities.

Convergence of Virtual and Physical Space

Remember that one scarce and also unforgeable property of a node is time and space. More precisely, virtual space as evaluated by triangulation of ping times. A node cannot operate or pretend to operate at the same time from a different location ³⁾, as long as it responds the quickest way technically possible. Given the reward scheme miners currently follow, exactly such a reward can be issued to the fastest and most stable node in the network. Lets say three honest nodes A, B and C have the following ping times.
A <-> B : 20ms
B <-> C : 15ms
C <-> A : 10ms
Therefore A has a cumulated response time of 30ms to serve its peers. B 35ms and C 25ms. The obvious winner is therefore C which is entitled for the reward. C virtually is located somewhere in the middle of A and B and in coincidence, is also the most coveted node for reliable communication. In practice, you'd want to use a metric which also considers the amount of peers validated and connected to, which is then a degree of responsive and well vested connectivity ⁴⁾.
In this scheme however, the losers are A and B. As long as they don't position themselves differently or improve their network access, none of them could challenge the dominance of C. Eventually they'd turn down their chances to ever earn a reward (which could still happen if C goes offline or drops in connection quality) and leave. Even worse, being a potent hub to begin with, C could act hostile and start impeding traffic relayed over it to manifest its monopoly position.
So how to align the interest of the bully C, its challengers A and B towards a single goal? One idea is to introduce marginal rewards. That means, given the metric of connectivity, the second best, third best and so one will earn a degressional part of the reward. This maintains a more diverse network.


Enter the idea of contestable physical space

By now, each node is ascribed with a connectivity measure which is easily verifiable by other miners. Especially since ping statistics are garnered from every challenging node in the process of mining to begin with ⁵⁾.
With three participants, ranking the nodes with a 51% consent will be quick. Now what you'd really want to have is a system of global scale. Until each node pings its peers to broadcast either a claim to be the best connected one or verifies the best few, an unfeasible amount of time and coordination is necessary. Moreover, given changing topologies and routings of the underlying networks, consensus on ranking would hardly emerge at all globally. Besides, this would lead to a few supernodes, probably residing in the US/EU (or space) and would exclude late adopters of internet technology from mining rewards. That means the utilitarian approach for an arms race towards supreme network resilience must therefore be augmented with an egalitarian approach.
To really spawn a global effort, lets assume that every claim to have the best connectivity must also contain location stamp in physical space. Much like GPS coordinates. This ties in the whole mechanism into the real world where people actually live and access the network for their purpose. For sake of simplicity, divide the globe into reasonably granular cubes ⁶⁾. Now, competition and ranking is carried out in this subspaces alone.
So how is a powerful and well connected node prevented from claiming a high rank in an arbitrary space? Simply, it can't. If it reports a location far off, the peer consensus of ping times would discard it. It is bound to real world constraints. It can't supply quality network connectivity locally without facing high latency in more remote areas because of constraints of the underlying network sophistication. Even raising a red flag from one honest node can quickly impede attempts of collusion where groups report artificially low ping numbers ⁷⁾.
Moreover, the reward miners are entitled to, can be entirely made up from transaction costs from users which initiate transfers from this same space. Hence making local spaces self sufficient. Given local demand from users, establishing a new network node there becomes profitable. This scales from a hundred people in the same building to a one man show in the Sahara of Africa. In the latter case, the user could easily claim this unoccupied space but then has to be her own miner at the same time. Therefore receiving exactly the same amount of reward that is used to make a transaction ^8.).

Overall, this Proof of Location and Connectivity facilitates the very public good every cryptocurrency runs on: communication networks. It is utilitarian and egalitarian at the same time in that each corner of the world is open for profitable conquest as long as users are present who actually make transactions.

Of course it could just be thought of as a gimmick to location aware games. However, if this idea bears fruition it might elevate any cryptocurrency's use case and proliferation of a unified highly performant internet onto another level. Any thoughts welcome.

Footnotes

1) In the emerging privatized banking scene of the US, exactly these properties were subverted by moving gold faster from one bank to the other than the auditors were able to travel.
2) Except quantum stuff
3) Given that it has not access to a superior network coexisting to the TCP/IP based internet and colluding peers on the same coexisting network. Eventually, this would contribute to a faster and more reliable network again.
4) Maybe the average of the top quartile or proven network quality measures.
5) Jitter problems and consensus on sampling time window needs to be solved. But since every node is concerned with keeping track of time in ms accuracy, an accurate reference time can likely be established on the network.
6) Claims could also include more sophisticated volumes such as polygons to avoid predetermined boundaries and therefore artificial placement of competing miners in the centers of such cubes. If a threshold of competing miners is crossed, the volume is simply split. This works down to any accuracy the nodes will report their location. I.e, in a densely populated city, several spaces would cross the city but none of them occupied by an insurmountable number of miners.
7) Similar to the challenge-response protocol mentioned here: "proof of treachery" (http://bitcoinstats.com/irc/bitcoin-dev/logs/2012/07/18)
8.) Probably, you want to keep an inflationary reward to maintain some baseline participation. E.g. this reward can be issued per km^2.


Addendum: Sybil Attack Conundrum

If verification involves weeding out noisy data sets however, e.g. with a gaussian distribution, possibilities for sybil attacks creep in. This is the case with latency data, as well e.g. seismic profile data. Since it becomes easy to forge directly neighbouring nodes with little effort by running your software twice, spoofing IP addresses and adding some figures to your genuine pong response times.
One way people try to tackle this problem is to extract honesty metrics with with sophisticated statistic methods, e.g. EigenSpeed (https://www.usenix.org/legacy/event/iptps09/tech/full_papers/snader/snader.pdf). Although, what I grasped is not yet convincing.
The most straight forward approach to curb spawning sybils is requiring a proof of stake (of currency), Slasher like, in addition. Then, one would have the perfect model of expansive capitalism. Currency is invested to nodes with which they compete in yet uncontested space. Much to think about but definitely appealing big time.

There are augmented-reality games where people must physically go to a location to play some sort of action in the game.

However, I can see more useful applications, such as temporal-geotagged digital images. 

And who needs a project that requires proof-of-location? I don't.

Perhaps one design a system where proof of location is made by paying a small btc fee to a node that consists of a open wi-fi point.  If enough of a fee is sent to the node's dynamic bitcoin address, it will sign a bitcoin message certifying that the node was contacted over wifi at a certain time.  The location proof could be queried in some kind of decentralized database.  Secondly, nodes would have to overlap and communicate with each other, in essence, they would certify that they are in range of each other, and reported locations that appear to be outliers would be eliminated from the network.  Some kind of algorithm could be developed that establishes confidence of proof of location, depending on home many proofs that the locatee can obtain, and the trustworthiness of the locater nodes, based upon how many other nodes certify that node.

If there is a large enough user base of locatees willing to pay fees to local nodes for the service, the economic incentive to run a node should insure growth in urban areas where the user base is likely to use the service.

Cheating might be possible by establishing a relay point, and I'm not sure what can be done about that.