Proof of Location & Connectivity: decentralized, utilitarian, scalable, global resilience network

cybertreibercybertreiber Vienna, AustriaMember Posts: 29 ✭✭

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. In case of Ethereum/Dagger computing and 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 1). 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 2). 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, 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 3), 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 4).
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 5).
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 6). 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 7).
Moreover, the reward miners are entitled to, can be entirely made up from transaction and GAS 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 run the contract or 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.

I shared this first on the Ethereum forums because it offers the biggest potential for a breakthrough. Notwithstanding the high awareness for PoW innovations from the developers. 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: http://blog.ethereum.org/2014/02/18/ethereum-scalability-and-decentralization-updates/
8) Probably, you want to keep an inflationary reward to maintain some baseline participation. E.g. this reward can be issued per km^2.

Comments

  • avsaavsa Member Posts: 68 ✭✭
    There's another way of using proof of geolocation: seismic data.

    Accelerometers are cheap and come in most electronics, and can be used as very reliable seismometers. IF a device left alone for long enough can detect a small earthquake (depending on the region those happens all the time), and broadcast it on the network before anyone else, it can be used as a proof that it was there. By knowing other known quakes and their epicenters, each device should have a unique "geologic" signature that can be easily verified, but can't be faked.

    I don't know enough about earthquakes to know if it would be practical (are small quakes detectable by different smartphones kilometers away? Do geological stable areas have small quakes?), but maybe there are other small scale natural phenomena that can be used, along with a proof of connectivity like you described, that can be used as sources of entropy to prove that a device was in a position on the globe.

    Also, in the plus side, Earth science would certainly benefit from having more data, and if someone is able to predict earthquakes he would get a very good reward!

  • cybertreibercybertreiber Vienna, AustriaMember Posts: 29 ✭✭
    @avsa That's a brilliant example and only the beginning of what could be done with, or on top of incentivized Location & Connectivity. It just happened today that a tweet titled "In one map: Every major recorded earthquake since 1898, showing how Earth is put together" caught me ().
    I'm not a geologist, but if it fulfills the criteria of precise and easy verification and hard to establish stake, which is the essence of any trapdoor function, it's suitable. However, if verification involves weeding out noisy data sets, e.g. with a gaussian distribution, possibilities for sybil attacks creep in. This is the case with latency data, as well as with seismic 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. With seismic data, you'd just do the analogous thing.
    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.
  • ranfordranford Member Posts: 25 ✭✭
    @avsa @Alex_GuangTou : yet another wonderful discussion... I was just commenting on a different discussion and connecting some dots. @Stephan_Tual pointed us to http://boinc.berkeley.edu/

    and in the list of projects at the site, you might be interested in the quake grid project using boinc, the site is http://qcn.stanford.edu/sensor/

    You could create an ethereum contract that builds on that fine work. I can definitely imagine such a dao having multiple uses and value
  • rplevyrplevy Member Posts: 3
    edited April 2015
    This is really exciting if it solves the problem of location spoofing. How is this not vulnerable to sybil attacks though? What's to stop you from spawning lots of nodes to subvert the peer consensus of ping times? The tentative conclusion I arrive at is that some hopes are being pinned on the ranking metric not being just based on ping times, but something like a proof of stake. I doubt proof of stake is solid enough though. Good old proof of work combined with the ping time metric could solve the sybil problem perhaps? Then what you have is not an alternative kind of unforgeable costliness but a very powerful decentralized unspoofable location service that opens the door to a whole class of decentralized applications.

    Or am I missing something fundamental about the design that already addresses the problem?
  • manuel_velezmanuel_velez Medellín, ColombiaMember Posts: 14
    Very interesting post. Thanks for sharing it.

    With regards to dividing the globe into granular cubes,


    For sake of simplicity, divide the globe into reasonably granular cubes 6).

    Not long after reading your post, I came across an article that described what3words, a company that splits the whole surface of the earth into 57 trillion 3m-by-3m squares.

    While their aim is different (they seem to be going for a replacement of traditional addresses), the globe splitting method aligns nicely with this.
  • rplevyrplevy Member Posts: 3
    I thought about this some more... Only the consensus of the fastest ranking miners matters, so they have to be nearby to achieve that. So does that mean the location must indeed be accurate? Even if I spawn lots of them?
  • rplevyrplevy Member Posts: 3
    So... only the consensus of the fastest ranking miners matters, so people have to be actually nearby to achieve that. So it seems true to assume the fastest ranking miners are actually where they say they are. There is still a sybil problem that I could launch a multitude of miner nodes all with very fast connectivity in the vicinity of where I wish to do a double-spend. Also that means that practically speaking every honest miner would also be motivated to launch as many nodes as they have the resources to afford, making it vaguely similar to proof of work.

    Perhaps to avoid this problem there's some way to count the consensus at a coarser grain than the individual node, but rather by aggregates of nodes distributed throughout the spatial section. The point is that if all the dishonest nodes are clustered in one spot, they would only count as one node. This would make it harder to pull off an attack because you would have to spread the true location of your sock puppets around the full area of the spatial section which as the network grows, would require a sophisticated virus botnet.
  • eaglgenes101eaglgenes101 Member Posts: 43
    avsa said:

    There's another way of using proof of geolocation: seismic data.

    Accelerometers are cheap and come in most electronics, and can be used as very reliable seismometers. IF a device left alone for long enough can detect a small earthquake (depending on the region those happens all the time), and broadcast it on the network before anyone else, it can be used as a proof that it was there. By knowing other known quakes and their epicenters, each device should have a unique "geologic" signature that can be easily verified, but can't be faked.

    I don't know enough about earthquakes to know if it would be practical (are small quakes detectable by different smartphones kilometers away? Do geological stable areas have small quakes?), but maybe there are other small scale natural phenomena that can be used, along with a proof of connectivity like you described, that can be used as sources of entropy to prove that a device was in a position on the globe.

    Also, in the plus side, Earth science would certainly benefit from having more data, and if someone is able to predict earthquakes he would get a very good reward!

    Don't forget all the spacial data that can be used: temperature, wind velocity, pressure, etc. Perhaps this info can be fed into a bayesian algorithm to determine who might not be trustworthy...

  • cybertreibercybertreiber Vienna, AustriaMember Posts: 29 ✭✭
    @rplevy Thx for your input!
    The idea of subjective blacklisting ties somewhat back to what I ment with footnote 7. However, I think it can be solved even more elegantly.

    "Moreover, the reward miners are entitled to, can be entirely made up from transaction and GAS 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."

    If the reward is entirely handed out to nodes spreading and incorporating the transaction, there is no point in spawning local sybils. The proof of spreading can be determined maybe somehow similar to the Uncle block reward of the current Ethereum approach. More precisely, only if randomly sampled nodes from all over the map (not only close by ones) report incorporation of the transaction, the seeding one gets the reward. Lets ponder if something like that is feasible.
Sign In or Register to comment.