Quote from: havanabob on March 23, 2014, 04:35:21 PM

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

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.

dafqok

Posts

Merits