The majority of modern location-based services rely on GPS to verify the location of different subjects. This approach is acceptable as long as the user is not interested in location data corruption, for instance, the usage of navigation utilities. On the other hand, when a service depends on the reliability of location data, then GPS is not acceptable. One of the most interesting examples of location data reliability dependent services is a smart contract, which needs to verify the location of a certain subject. The only way to verify a location within a smart contract is to rely on a third party. This fact breaks the decentral ization principle of smart contracts. This paper introduces a novel algorithm of location proof within the smart contract by leveraging a p2p mesh network of Wi-Fi access points and a distributed key generation algorithm.
The location-based services like package delivery in urban areas is something that ev eryone is using today. Internet-based technologies, such as e-commerce, made the ac quisition of any goods almost flawless. A regular customer is not interested in the underlying processes of buying something online and having it delivered at their doorstep. This is because the customer has a payment card, a smartphone, and ten minutes of their time, and there is almost nothing to worry about. However, from the perspective of a business owner the organization of such service is complicated, te dious, expensive, and requires a lot of trust in other people. This includes at least, the development of a website, signing a contract with the bank acquirer and signing a contract with a logistics company. At least two of those three tasks are now obsolete, which are the bank contracts and logistics company.
To support the above statements, a survey of existing technologies will be provided
here. In 2008, the probabilistic solution for “Byzantine Generals Problem” [
One of the interesting cases of using smart contracts is robonomics. Robonomics is
an informal term used to describe how cyber-physical agents can co-exist within the
human economy. One of the projects in that area, called AIRA [
The Global Positioning System (GPS) was developed to help a human with navigation problems. Today, GPS is one of the most important features of a cell phone. It makes possible navigation apps, but not the only. FourSquare entertainment app uses GPS to “award” people for visiting different locations. SnapChat messaging app has the feature that shows where your contacts are currently located. Most probably, these popular applications are not a complete list of GPS use cases. Transportation companies use different GPS enabled proprietary devices that are tracking vehicles for different reasons. GPS is a mature and highly efficient technology, but it has only infor mational nature. GPS is ideal for personal use to assist yourself in different tasks, but when it comes to using GPS to get another subject's location and verify it for different reasons, then we are not protected from a scam. For example, the above-mentioned transportation companies need to spend money on expensive proprietary devices that track a location using GPS. Why do they need a separate device, while any smartphone has a GPS module? Because when the other subject is interested in not providing, at all, or providing a wrong location, it can be achieved relatively easily, unless the device is tamper-proof. This is because the GPS location is just temporary binary data stored in the device memory. For services where a location is economically im portant, we cannot simply rely on GPS data. For most nowadays services, centralized proprietary location solutions are expensive, but an acceptable choice. But in the de velopment of decentralized autonomous solutions using smart contracts, it will not work, and we will discuss why further.
We will assume the existence of the delivery service based on a smart contract. Some customers want to order package delivery to some location. We will not consider how the contract knows which package the customer wants to get for the sake of problem model simplicity. So, the customer sends the order to the contract with location and time, as well as the payment for the service, which will be deposited and will go to the service provider, as a fee, if the package will be delivered correctly. The contract’s role in this scenario is the third party auditor, that needs to hold money on deposit and unlock it for the service provider if the job is done. We assume that the service provider uses autonomous drones to deliver packages. It is necessary somehow to formalize the definition of a completed job in the smart contract. In our case, a completed job means that a specific package is at the specified location at some point of time. Firstly, it seems like the customer can verify the job by himself, by roughly speaking, pressing a button in the app when he took the package from the drone. But such an approach will not satisfy the service provider, because the customer can misuse service by placing orders and not confirming delivery. If the contract cannot check that the job was done, then the deposit will be returned to the customer. So, we can use a GPS module that is attached to the drone to verify that the drone is at the specified location. Then from the contract perspective, the definition of a complete job will be defined as the following algorithm: Get the order from the customer with location data and payment Get the confirmation from the service provider that the order is accepted Wait for the input message with the courier location data from the courier Compare the arrived location data with the location data specified in the order If the data are the same, then unlock the deposit for the service provider. Hence, right after the service provider confirms the order, it also sends the location specified in the order and gets the customer’s money, by not even starting the drone. Maybe, we can use a combination of both parties' confirmation as the definition of a complete job? This will lead to the equivalent of the “only customer” confirmation scheme which means that a customer can still misuse with a service provider. We now understand that 2 parties alone cannot organize themselves without leaving one of the parties vulnerable to “attacks”. Hence, without the secure algorithm for verification of the complete delivery job, we cannot fully automate the location-based services using smart contracts.
Another way to solve the location verification problem in smart contracts is to convert this issue to the problem of trust between client and service and apply blockchain-based reputation models. Such an approach does not provide the framework for autonomous, decentralized robonomic chains, but either advocates service to do everything to make their rating high enough. If the requirement is to build an endto-end delivery service using decentralized solutions, then such an approach will not work. 3
Here we conduct a historical literature review on the topic of the location proof. In
one of the first papers about location proof [
There are also a few ongoing projects [
In this chapter, we will describe the novel algorithm that solves the problem defined in the second chapter. 4.1
Suppose we have a straight street in the urban area. On both sides of the street, there are multistory buildings. There are many private Wi-Fi access points in this area. We will use those as an oracle mesh network to sign the location proofs of different sub jects. In Fig. 1, we see a potential topology of Wi-Fi access points where the edges denote that two nodes can communicate with each other directly.
Point A refers to the customer of the delivery process introduced in chapter two. The point B is a service that will deliver a good. There is also some delivery app (maintained by B) that the customer uses to place the delivery order.
In Fig. 3, we can see the UML sequence diagram of the algorithm. When the
service received an order from a new customer DeliveryRequest(A_pub) via the delivery
app - our algorithm starts. First, the service needs to know if the customer is some
where within the network boundaries. The network has a public interface with a set of
commands. First command is RequestDKGContract(A_pub) (short DKGRequest).
DKG abbreviation in command's name stands for Distributed Key Generation [
To collectively sign something using private keys, peers will need to reach some threshold number. For example, ten peers received the customer’s beacon. Each of them received his unique private key after the DKG procedure. Now, to sign some thing, at least six from ten peers need to apply his private key, otherwise, it is "impos sible" to produce a valid signature of the current DKG_Pub key. The main property of the DKG scheme is that the algorithm requires no third party to help generate keys.
Peers send produced DKG_Pub to the customer. The customer generates a smart contract with GPS coordinates and deposits the delivery service fee there. The contract has a simple predicate in it: if decrypt(m, DKG_Pub) = true, then release the fee to service. The customer sends this contract to the service. Service checks that the contract is created by some standard interface and if everything is correct, it can start delivery.
When the courier approaches the delivery zone, it starts to broadcast signed beacons. All the nodes that participated in the DKG collect beacons from the courier. When the courier stops, every node encrypts all the collected data with their private keys. The nodes broadcast their encrypted data to each other. Each node needs to verify two facts: first, received signed beacons refers to the original node that called DKGRequest; second, received beacons were not sent from a static position. The first assertion is trivial and essential. The second assertion is an additional verification of the delivery work because otherwise, it is much simpler to mimic the delivery fact by just transmitting the right beacon. By encrypting every node's recorded data, we ensure the uniqueness of every version of the recorded trajectory of the delivery agent. After that, nodes use Lamport’s algorithm to achieve consensus (will be described in the next section).
After the consensus is achieved, nodes sign the verdict with their DKG private keys and send it to the delivery service. If the consensus is not achieved, then the message will not be signed. Considering that, the threshold also will not be reached, then there is no chance to get decrypt(m, DKG_Pub) = true. Otherwise, if the threshold is reached, the delivery service could withdraw the fee from the contract with the signed message from the network. 4.2
We can use two approaches to achieve consensus on whether the delivery was done
correctly. The first is to achieve consensus only between nodes N1, N2, N3, and N4
(Fig. 1). This means DKGs will be triggered only between nodes that are located
directly on the target location. The second is to try to achieve consensus in all zones
where there was a delivery path. This is a topic for separate research, but in the cur
rent paper, we only describe the first approach. We consider our oracle network to be
Byzantine fault-tolerant (BFT) and can handle no more malicious/faulty nodes than in
Eq. (1), where m is the total number of nodes [
( m − 1) / 3
(1)
Eq. (1) states that, if nodes N1, N2, N3, and N4 want to reach consensus on the fact of
delivery, then at least 3 nodes must be loyal. The fact that each node can be malicious,
it can try to break protocol in any possible direction, potentially stopping the network
to reach consensus. This implies that the only way to avoid this is to implement BFT
consensus. For now, we can assume that the network will use the BFT consensus al
gorithm from Lamport’s paper [
To ensure that the algorithm will work in a hostile environment we need to make sure every node has at least 2/3 loyal neighbors. Let’s call it “condition 1”. This condition will ensure the possibility of final consensus according to Lamport's algorithm. There is one problem which is called “Sybil attack”. Theoretically, nothing prevents one malicious node from acting as many nodes. This will break any consensus because condition 1 will not be accomplished. In order to distinguish nodes, we can utilize information from Wi-Fi CSI (Channel State Information). This allows a node to calculate signal location in space, which implies the identification of nodes based on public key and CSI.
If the customer is malicious, it is relatively easy for him to fail condition 1 using a set of real physical nodes in some area. For example, DKG occurred in such an area, where more than 1/3 nodes are owned by a malicious customer. When service delivers a package in this area, malicious nodes simply will not sign the message for the contract. This allows a malicious customer to misuse with a customer and waste his time/money.
We still can make a dishonest customer’s life more uncomfortable. We need to introduce the risk that attackers can lose deposited service fees. If that risk will be high enough, it will respectively reduce the chance of someone misusing the service. There is no way for the service to distinguish malicious contracts/nodes before the consen sus phase. This means that we should search for a probabilistic solution. For example, we can let service deliver on adjacent sectors to a customer area. Let’s imagine that the malicious area has more than 1/3 dishonest nodes, but probably there are still at least a few loyal nodes. Now, each of them will set up DKG. There is a high probabil ity that at least one DKG area will be loyal. Ultimate contract might have the following assertion: decrypt(m, DKG1_Pub) = true or decrypt(m, DKG2_Pub) = true or... This means for service that it can choose in which area to deliver and if in some area consensus will not be reached it can still try a few adjacent
The last problem we need to solve is how the service will know, which DKGn_Pub must be in the ultimate contract that he receives from the customer? All loyal nodes which received DKGRequest at the beginning will essentially send their DKGx_Pub to service, so that service knows there are multiple areas that are ready to do loyal consensus. Now, if the customer will not include some of the DKGs into the contract, the service simply might ignore that contract and decline delivery. This means proto col protects, to some degree, service from malicious customers. What about malicious services? The only attack which malicious service can do is to fully blockade the cus tomer’s area with malicious nodes. Probably this attack is too expensive to organize compared to what malicious service could "earn" by stealing customers' service fees. 4.4
There are several directions for further research on this topic. First of all, the analysis of CSI-based solutions that can calculate signal source location in space. In the algo rithm described in the current paper, those solutions are vital for node identification and delivery verification. Secondly, analysis of existing synchronous and asynchronous DKG protocols implementations. And of course analysis of existing BFT con sensus algorithms. 5
A novel theoretical algorithm that solves proof of the location problem in smart contracts was introduced. This algorithm assumes the decentralized p2p network of Wi-Fi nodes that forms a mesh network. The network by itself does not store any history of the location proof and works only on demand. The use of the distributed key genera tion algorithm allowed to establish a smart contract between two parties. The network monitors subject beacons and uses byzantine fault-tolerant algorithm to achieve consensus on the location proof of the subject.