The COVID-19 pandemic has been a global health emergency, spreading to more than 18 countries of the world and infecting more than 8,359,869 population. As an essential tool for public health officials and local communities to fight the rapidly spreading, contact tracing methods draw attention across the world. Early in the outbreak, when there were only a few cases, contact tracing can be done manually with a slight impact on society. Nevertheless, with the skyrocketing of the infections in the vast majority of countries, manual contact tracing tends to be unrealizable on both economy and policy considerations.
Location-Based Services (LBS) provided by Short-Range Communication (SRC) techniques are considered a viable solution to perform contact tracing. Due to the intensive penetration of mobile smartphones, wearable devices, and ubiquitous sensors, residents can opt-in contact tracing service via an over-the-air mobile application installation, whenever Internet access is available. The Singaporean government released a mobile phone app, TraceTogether, that is designed to assist health officials in tracking down exposures after an infected individual is identified.
In general, a recorded SRC interaction with timestamp and locationinfo can certify that, at a given moment and position, two radio terminals have been closer than the maximum transmission distance. If one of the two terminal owners is tested positive for COVID-19, the SRC record can be strong evidence of epidemiological exposure for the other owner. Therefore, the contact identification can be automatically made by analyzing the infected person's SRC records.
On the other hand, the chosen of SRC standard and storage methods would significantly impact the performance of SRC-based contract tracking. Shorter communication distance increases identity accuracy. An overlong communication range may result in excessive identified contactees whose physical exposure may do not actually occur. As an example, the South Korea government analyzes Call Detail Record (CDR) collected from telecommunication operators. When a COVID-19 patient is detected, the entire building should be quarantined, which results in a significant impact on the company business. Therefore, benefit from easy to deployment and stone-cast data transmission, Bluetooth Low Energy (BLE) has been considered as a possible contact tracing approach.
If we take a longer-term and world-wide perspective, increasingly more people rely on LBS apps to track, monitor, manage, and plan their daily life. These mobile apps have profoundly impacted and even initialized various industries, such as Uber [2] and DiDi in transportation sharing, Ele in food delivery, Fitbit and Nike+ in fitness, and Pokergo in augmented reality games. The key features of these apps are to collect location information in a certain time period and to perform path generation to share the personal location/activity path/summary with other users/service providers on a social network. For example, activity-tracking programs are developed in United Health and Aetna to modify insurance rates according to an activity analysis [3] .
However, these activity-tracking services assume users are trusted and honest to report their location and time information, which is generally impractical and unrealistic. Indeed, arXiv:2007.00894v1 [cs.CR] 2 Jul 2020 the fashion of self-reporting location information using global positioning system (GPS) coordinates, cell triangulation and IP address tracking are all susceptible to manipulation such that users can handily claim a mendacious location [4] , which may cause serious cheating issues, especially to financial and critical service providers. To address these issues, SRC records also consider being an applicable method to improve their location reliability.
Although LBS provided by SRC (especially BLE) techniques are highly demanded in the contact tracing of COVID-19 pandemic and many more daily demands, much uncertainty still exists on data security, privacy, and deployment efficiency.
• Security: Traditional security services such as authentication, integrity, and provenance provided by thirdparty brokers. However, the third-party brokers maybe not trustable. • Privacy: User privacy may be violated when service providers collect, store, and analyze customer's locations using a centralized database. The service providers can even sell customer data by taking a little advantage of the fine print in the service agreements. Although Europe's General Data Protection Regulation (GDPR) has been implemented, the unintended data leakage of service providers still call for technical privacy concerns. • Deployment Efficiency: A phone-to-phone SRC record demonstrates the spatial connection between two individuals. However, long-term monitoring of a high-risk hotspot area is still critical in contact tracing. Governments or philanthropic organizations are willing to deploy several IoT witnesses, e.g., BLE beacons, to achieve an allweather day-and-night low-cost area surveillance. These organizations may not cooperate. Therefore, an efficient deployment strategy is desired in the blockchain system. In this paper, we propose a permissionless blockchain for automated contact tracing and activity-proofing, named Bychain. An interactive zero-knowledge proof based protocol is designed to provide transaction security and identity privacy while taking advantage of cryptographic techniques instead of employing a trusted third party. The deployment problem is addressed by proposing an incentive allocation mechanism based on a visual potential field algorithm; a participant would be distributed the maximum reward when it is on the position of force equilibrium. Ideally, the blockchain network archives maximized monitoring area when the IoT witnesses in the blockchain are static equilibrium.
This protocol relies on the cryptography technique to create SRC proofs for its nearby mobile users. The proposed protocol consists of three stages: First, users obtain secure and privacypreserving proofs of location during their activities, by relying on an over-the-air lightweight message exchange between their mobile device and the witness point. Proof of Location (PoL) commitments are generated, digitally signed, and verified by their nearby witness nodes through BLE techniques. Second, the activity proofs are uploaded on a decentralized ledger that is transparently and distributively stored on the Internet. Finally, the trusted activity summary can be generated by using a zero-knowledge proof based authentication based on a smart contract after an ownership verification. The blockchain could compute an accurate and trusted activity summary of an authenticated user to fulfill the requirement of COVID-19 contact tracing, without revealing activity information to anyone else.
To empower Bychain with the ability of witness deployment, an incentive allocation algorithm is proposed based on the virtual potential field. Each witness node is treated as a charged particle, such that artificial electric fields are constructed in a way that each node is repelled by repulsive force from other nodes. As a result, the witnesses in blockchain could spread itself throughout the environment. Finally, the monitoring area of the blockchain system tends to maximize the monitoring area when the IoT witnesses in blockchain tend to static equilibrium.
Additionally, in the blockchain system, a semi-trusted decentralized activity-proofing system and zero-knowledge based authentication techniques could provide security from cheating and protect identity privacy. The public essential cryptography technique is naturally merged to provide an ownership certification of personal location information. As a benefit from the zero-knowledge proof technique, a user could claim data ownership without revealing the private key to anyone else. However, the decentralized ledger is transparent such that the public can verify the location information. Hence, we introduce a crucial escrow technique to alternate the traditional one-key-per-user with a one-key-per-proof scheme. The onchain data traceability becomes almost impossible, and the identity information is pseudonymous. Thus, data security and identity privacy requirements are met in our system. Consequently, the attack of controlling the certificate authority and the central database can be avoided. Furthermore, plenty of attacks can be avoided, such as the reply attack and the dust attack. We will discuss them in detail later in this paper.
The contributions of this paper can be summarized as follows:
• A proof-of-activities generation and verification protocol is introduced to achieve trusted activities proof for contact tracing and related SRC usage. Bychain protocol addresses the activity-proofing problem without a trusted third party while considering privacy and anonymity. Buchanan can also fastly applied in COVID-19 with a low economic cost. • By jointly design of crucial escrow and zero-knowledge proof method, the proposed protocol is able to obtain location identity privacy and security. It can resist various attacks and collusion. A generalized block structure is proposed to fulfill the requirement of new on-chain operations. Furthermore, to address the efficient deployment of IoT witnesses, an incentive allocation mechanism using virtual potential field is proposed to maximizing the monitoring area. • A prototype implementation is realized and verified on the Android platform. The performance analysis shows that our protocol requires preferably low computational time, energy, and storage. Experiments show that the proposed protocol is practical and can be applied in many scenarios, even in a highly dynamic environment. The rest of the paper is organized as follows. Section II discusses related work. Section III describes the overview of the proposed blockchain system. In Section IV, we discuss our proposed proof of activity protocol and incentive allocation mechanism. A security analysis of our proposed protocol against different types of attacks is provided in Section 5. In Section VI, we describe our implementation and simulation and present our experimental results on the performance evaluation. Finally, Section VII concludes the paper.
Security and privacy of LBS and activity-tracking services are becoming a serious problem. The GPS verification mechanism can be modified by simply and easily cheating by modifying the geolocation API value return [4] . Moreover, the work in [5] analyzed data from Foursquare and Gowalla and found that incentives to cheat exist because people actively check-in and collect rewards. Thus, it is necessary to carefully balance incentives with a more effective verification of users' location claims.
Many works have been discussed in the mobile computing society to offer secure verification of location information [6] - [8] . Short-range communication technologies, such as Bluetooth, have been proposed to generate location evidence from its neighbors. The mutual verification protocol of a set of users is proposed based on users' spatiotemporal correlation in [9] . A centralized location verifier is applied to verify mutually colocated users relying on Bluetooth communications. The privacy is performed by deciding whether to accept location proof requests and is decided by the users. APPLAUS is proposed in [10] as similar work on a collusion-resistant location proof updating system using collocated Bluetooth devices. In addition, STAMP provides a spatial-temporal probabilistic provenance assurance for mobile users [11] . The collision detection for such protocols is not 100 percent effective, and the protocol does not itself guarantee any collusion resistance.
SRC based contact tracing is developing by Google and Apple [12] in a privacy-preserving fashion. However, the SRC records are stored in mobile terminals facing storage shortage problems. The deployment of IoT witnesses is not supported as well. Indeed, blockchain technology and its applications have drawn enormous attention from various researchers. In [13] , highly reliable communication is supported by blockchain and neural networks for unmanned aerial vehicles. A blockchain protocol is also proposed to manage data for the vehicular network in [14] . However, the above applications can not address the location problems in this article.
The proposed blockchain protocol is a peer-to-peer system, which provides users with anonymous and trusted location proofing, transparent data storage, and zero-knowledge proof based data ownership authorization. Fig. 1 illustrates the proposed blockchain architecture, in which the network is summarized as three layers :
• The service layer contains honestly witnesses that afford location-proofing service to passing-by provers via nearfield communication techniques, and verifiers that finally generate activity certifications in the form of tabular activation summary. In a given time period, T n , a prover collects witness-signed PoL commitments and then uploads them on blockchain as the cornerstone of trust evaluation. A straightforward trust level evaluation via the cumulative method is marked as green labels in Fig.1 . • The network layer enables the peer-to-peer (P2P) transmission mechanism to exchange collected PoL commitments of each prover and virtual force of each witness. This information are carried by the Transactions (Tx) field in the proposed generalized data structure and received by chain nodes. • The blockchain layer is comprised of a distributed database recording immutable and continuously growing transactions and a location-based consensus mechanism maximizing total coverage of witness nodes, which is detailed in Sec.IV. The blockchain system disburses a budget coverage package per 24 hours to stimulate witness movement to form maximum coverage of the sensing area. During each round of consensus procedure, a miner calculates the incentive allocation scheme and then sticks it into the next block. The miner is pseudorandomly determined from a node sequence in the order of owned stock value. The proposed block is broadcasted and finally confirmed by an elected consensus committee according to the value of mortgaged stocks. The key entities and mechanisms in each layer would be detailed in the following subsections.
Individuals can access the blockchain with unified application software, which ensures data integrity by forcing a data consistency check when initializing. The service layer establishes a set of available application operations and coordinates the application's response in each operation. Although all IoT nodes with application installation are fully functional, the three logical roles involved in those operations need to be elaborated for a better understanding of readers.
1) Prover: In the proposed blockchain architecture, the prover acquires anonymous and trusted location proofing, transparent data storage, and zero-knowledge proof based data authorization. Provers indeed are a set of wireless nodes that desires location-based proof-of-activities. Each prover is equipped with a GPS module as well as Bluetooth, WiFi, or LTE antennas has Internet activity to the blockchain and moves in a given region that is covered by our wireless access point (AP) networks. These provers can communicate with AP nodes involved in our system only if their distance is lower than the communication distance R, where R is determined by the near-field communication technology, which means Bluetooth, WiFi or LTE will provide three kinds of distances, defined as R B , R W , and R L , respectively. The sum of communication durations between provers and AP nodes can be completed before the prover leaves the coverage area of AP, which is verified in our experiment. Each prover i is equipped with a memory as a critical escrow agent to stock pairs of cryptology keys. The stocked vital pairs are generated when service initializes and randomly sign each near-field communication message, which means the kth proof-of-location commitment is uniquely identified by public key pk k pi and a private key sk k pi . Without loss of generality, we assume provers will never hand or even reveal their private keys to anyone else.
2) Witness: Witnesses are wireless nodes that provide location-based proofs to provers. These witnesses may be fixed WiFi APs, Bluetooth low power equipment (BLE) or an LTE base station owned by an ISP provider, deployed in the area where provers pursue their proofs. More importantly, a witness could discover another if their distance is lower than its coverage radius. Hence, witnesses are aware of the locations of their neighbors.
All the witnesses and provers have synchronized clocks and are equipped with a GPS device that is aware of the location of itself. This WiFi AP localization technique can be realized by the analysis of communication channel state information. Different from provers, each witness i can be uniquely identified by a pair of cryptology keys, known as a public key pk wi and a private key sk wi . Without loss of generality, we also assume the witness will never hand or even reveal their private key or digital signature to anyone else. The witness can access the Internet and communicate with the blockchain.
In our system, we assume each witness is semi-trusted and privacy-honest, which means it does not reveal the prover's information to any nodes, but cheating such as collusion may occur. Practically, a witness is probably willing to collude with other witnesses or provers cheating for blockchain awards.
3) Verifier: A verifier is an entity that a prover wants to request an activity certification from, such that a prover's claim appears in a certain location at a particular time. The verifier is completed by interactive zero-knowledge proof based on the smart contract, such that it is self-running and able to protect the identity privacy of a specific user.
When the prover intends to request certification, a verification request including the on-chain index of PoL commitment, public keys of the prover, and witness are submitted to the blockchain system. The verifier smart contract is triggered when the particular verification request appears in a new block. Consequently, the ownership of the PoL commitment is verified by a zero-knowledge proof algorithm without revealing private keys to anyone else. Hence, the prover can be verified and certified as the owner of the particular PoL commitment, i.e., the prover is witnessed at a certain timestamp.
The network layer takes responsibility for routing data packages between blockchain nodes. Considering lacking retransmission and reordering in User Datagram Protocol (UDP), transmission reliability of large package (block size up to 4 MB) could not meet the network requirement. Bychain uses an unstructured peer-to-peer network with TCP connections as its foundational communication protocol.
Bychain introduces several novel operations in the service layer such that traditional blockchain data structure [22] could not be straightforwardly applied. Take several new operations as an example, 1) the prover intermittently broadcasts a package including multiple PoL commitments collected in a time window. 2) The witness reports its location and virtual forces during every round of consensus procedure. 3) In the blockchain layer, the miner publishes the incentive allocation into the next block, which will be detailed in the next section.
Hence, for efficient and confidential data transmission, Bychain reconstructs the transaction structure and then develops a general block format, as shown in Fig.2 . More precisely, Expiration and Signature fields are applied to indicate the producer and timeslot of one transaction. Hence, there would be multiple Operations happening over the specified identity and time duration. The broadcasted transactions are stored in a buffer pool to be serially packaged into Blocks. The buffer pool is maintained and checked by the consensus committee.
In contrast to existing location-proof methods, the proposed system does not require a trusted centralized third-party. Furthermore, aiming to endow the blockchain with maximizing the monitoring area, Bychain proposes a new location consensus based on the virtual electric field to maximizing the sum coverage of the location-proofing service. Furthermore, Bychain adopts an interactive zero-knowledge proof method to ensure data confidentiality and anonymity. We will describe the necessary entities and mechanisms in the following.
Blockchain is composed of a distributed database and a peer-to-peer node network. The blockchain database is a secured, shared, fault-tolerant, distributed, and append-only database that facilitates consensus-based recording and tracking information without a centralized, trusted third party. The blockchain network is based on the peer-to-peer communication protocol and untrusted nodes.
All the data processes on the blockchain are decided by the majority users in the blockchain network, and the decisionmaking procedure is called consensus generation or mining a block. All the network nodes attend a mining competition in each turn to decide which node can produce and broadcast the new block to the other nodes. The new blocks are composed of new unpacked data in the distributed database. There are several existing consensus generation algorithms, including Proof-of-Work (PoW) [15] , Proof-of-Stake (PoS) [16] , [17] , Proof-of-Space (PoSpace) [18] and practical Byzantine fault tolerance (PBFT) [19] .
The blockchain system produces cryptocurrency to incentivize miners to take part in competitions for block recording rights in each turn. Due to the majority decision and resourceconsuming competition, the blockchain does not rely on a traditional trusted third party when recording data if the majority of network nodes are honest. It is because a successful attack can only occur when the attacker wins enough mining competitions; however, the cost of this 51% attack would go beyond expectation. According to an analysis in 2018 December [20] , it will cost 1.4 billion dollars to realize the 51% attack in the Bitcoin blockchain.
Although a blockchain is composed of a database and a node network, the decentralized system is able to process some proper, on-chain, and heavily automated workflows by using the concept of the smart contract [21] . Smart contracts are self-executing scripts stored in the blockchain database and independently executed on each network node in a sandboxed virtual machine. The Turing-complete virtual machine allows us to implement complicated logic smart contracts with deterministic outputs and on-chain data interactions. The smart contract can be regarded as a predetermined on-chain rule triggered by particular on-chain data, such as a specific transaction.
1) Signature and Key Escrow: To validate the authenticity of PoL commitments and on-chain transactions, our blockchain employs the elliptic curve digital signature algorithm (ECDSA) asymmetric cryptography technique. The ECDSA cryptography is implemented by using the secp256k1based Koblitz curve for the ECDSA key-pair in the opensource project OpenSSL. The generated private witness key is able to sign the PoL messages to authorize that the prover appears in a particular location and at particular timestamps. Furthermore, the on-chain transaction data also need to be signed such that the transaction is traceable and verifiable.
Due to the on-chain data transparency, anyone can access and analyze the on-chain data freely. In this case, identity privacy becomes a critical problem introduced from the blockchain technique because the prover's activity information can be easily tracked on the blockchain. In our protocol, a key escrow is employed for the prover to achieve the separation of identity information and location information. A primary private key and several generated key pairs are initialized and stored in the memory when the system initializes. The generated vital pairs are iteratively employed for each PoL message interaction procedure, and consequently, the generated public key is uploaded into the blockchain database for verification. Because it is almost impossible to calculate the main private key based on the generated public key, we consider that the identity privacy is achieved.
2) Zero-Knowledge Proof Based Authorization: Because the key escrow is applied in our protocol, the only way to verify the identity information of the on-chain PoL commitment is by checking the private key. However, there is no third party that can be trusted to verify the private key on a blockchain system. Otherwise, location privacy may be 'stolen' by copying the private key.
zero-knowledge proof technique tries to help a verifier trust a prover without leaking any secret information to anyone else during the verification procedure. In this paper, we employ an interactive proof scheme in which the prover demonstrates its authorization information (private key) to the verifier by several interactive rounds. During the interactive procedure, the prover answers a randomly generated challenge from the verifier. However, most of the recent zero-knowledge proof based authorization to reply to a trusted third party, which is not always practical in the real world.
In our system, zero-knowledge proof based authorization procedure is considered part of our blockchain so that the information leakage risky from a third party is avoided. Hence, the private key is not required when verifying the clear onchain proof-of-location commitments.
Furthermore, the blockchain itself can generate and distribute and update sets of pseudonyms (the pairs of the public key and private key as mentioned above) for every prover and witness.
In contrast to existing location-proof methods, the proposed system does not require a trusted centralized third-party. Furthermore, Bychain proposes a new DPoS consensus based on the virtual electric field to maximize the sum coverage of the location-proofing service. We will describe the necessary entities and mechanisms in the following.
Our goal is to establish an activity-tracking and locationproofing system that guarantees the authenticity of the user location and activity data with respect to cheating nodes, the underlying untrusted centralized supernode, and malicious nodes, and provide almost complete privacy protection with respect to on-chain nodes that are trying to track provers. In this section, we detail our blockchain-based proof-of-location system. The system is shown in Fig. 1 , and the scheme is shown in Fig. 5 . Two stages are involved in our proof-ofactivities protocol, the proof-of-location stage, and the activity generation stage, and they are denoted as follows, Stage 1: Proof of Location 1) Broadcasting: The broadcasted PoL request can be descried by multiple witness nodes as shown in Fig. 3 . Suppose a prover p i at location L i,t wants to start an activity proof collection event at sampling time t, so it periodically generated a location proof request P k i using the kth pair of cryptology keys {pk k pi , sk k pi } and broadcasts P k i to nearby devices. Note that {pk k pi , sk k pi } will be updated as {pk k+1 pi , sk k+1 pi } when this PoL stage is completed. The PoL request is constructed as follows,
where nonce pi (t) is a random number with respect to prover p i and timestamp t and L pi,t represents the current location information at time t. The payload data is compressed by the SHA256 function H() to reduce the communication complexity in the signature. S sk k p i = Sign skp i {H(pk k pi , nonce pi (t), L pi,t , t)} denotes the signature of sk k pi agrees with the PoL request. The request is specified with respect to wireless protocols that are denoted as C{}.
2) Response: Each witness in its communication range decides whether to respond to the request. The witness node may reject the PoL request due to fake parameters, for example, the location information in P k i shows that distance between the prover and current witness is significantly larger than the communication range. Request rejection also happens if crypto-verification fails, i.e., S sk k
If the request is accepted by the witness j, the witness sends back a response message R k j at timestamp t . Without loss of generality, the time difference t − t is not enough for the prover to move out of witness j's communication range. R k j can be constructed as follows,
where nonce wj = {pk j ||n} is a combination of public key pk j of witness j and an unrepeatable built-in counter as n. It is worth noting that pk j is specific and unique to juser, and nonce wj functions as an on-chain index of the PoL commitments. Fig. 3 . The proposed protocol consists of two stages, including PoL stage and activity generation stage.
denotes that a signature of sk k pi agrees with this response. This response is sent back to the prover as a witness location proof.
3) Submission: Consequently, a dozen of responses with diverse witness signatures are collected at the prover's antenna in a short time window. If the responses originate from M receivers, then the PoL commitment can be constructed by combining all the PoL responses,
Com k i is uploaded on the blockchain such that the PoL commitment for kth PoL request at the ith prover is immutable. A trusted level of Com k i can be generated at the activation summary depending on number of combined PoL responses. The prover-witness collusion attack can be avoided when M is large enough and the honest witnesses are more than M 2 . These steps are illustrated in Fig. 3 .
For each submitting procedure k, a PoL note is stocked for a further zero-knowledge proof. The PoL note is a combination of private key sk k pi in the broadcasted request, the random number nonce pi (t) and the collected witness indices nonce w1 , . . . , nonce w M and can be written as,
PoL notes the function as an identifier of its corresponding on-chain commitment, prover always can precisely locate the on-chain commitment and proofs of the ownership to anyone else by a zero-knowledge proof smart contract verifier without revealing the private key sk k pi .
Input: Key pair {pk k pi , sk k pi }, Responsed Witeness Set w 1 , w 2 , ..., w M , Maximum Response Duration T max . Output: Activity Summary 1 Stage 1 : Proof of Location 2 for Prover p i do 3 Generate and Broadcast PoL request P k i according to (1) . A clock is initialized as T . Local storage for private key and nonces storage according to (5). 11 end 12 Stage 2 : Activity Generation 13 for Prover p i do 14 Generate and transmit verification request according to (6) . 15 r k pi is returned from contract. 16 Generate and transmit Proof according to (7). 17 for Verifier do 18 if Verify pki (Proof) == Sign skp i {H(nonce pi (t), r k pi )} then 19 if
Verify pki (S sk k p i ) equals to Sign skp i {H(pk k pi , nonce pi (t), L i,t , t)} then 20 Activity Summary transmission starts. The verification is failed. In our system, the activity summary is generated by two steps: location verification and summary generation.
1) Location Verification: To verify the kth commitment, a single-round interaction zero-knowledge proof is applied. Firstly, prover p i produces a verification request,
The smart contract verifier searches on-chain data according to index nonce w1 || · · · ||nonce w M . The outcome is the kth PoL broadcasting request, shown as {L i,t , nonce pi (t), pk i , t, S sk k p i }. Consequently, the verifier generates a pseudorandom number r k pi as response to prepare zero-knowledge verification.
Secondly, the prover signs a proof by using sk k pi , as
The verifier can identify the ownership of the commitment by comparing H(nonce pi (t), r k pi ) with on-chain nonce pi (t) and local r k pi , which is according to the randomness of r k pi and nonce pi (t). The private key sk k pi will not be revealed to the verifier such that no one can complete the ownership verification in the future except prover i.
Finally, the verifier returns true or false as a result of PoL verification. It implies whether or not the PoL commitment belongs to the specific prover i.
2) Summary generation: After each PoL is verified, the smart contract produces an activation summary, including the trusted level generated from the number of witnesses M and the activation path. In this subsection, we present the details of the locationbased consensus algorithm. Inspired from DPoS and aiming to maximize the monitoring area, the proposed consensus algorithm consists of six parts: 1) committee election, 2) block proposal, 3) block propagation, 4) block validation, 5) block finalization and 6) incentive mechanism. Different from DPoS or another consensus, the participants of Bychain are given a different number of votes according to its last location reward. The reward allocation (or incentive allocation) scheme is one of the vital consensus procedures for permissionless blockchain [23] , especially to encourage the profit-oriented blockchain participants to act in the way Bychain expect them to. The details about the proposed consensus are introduced in the following.
1) Committee Election: Although every participant in Bychain can be elected as a committee member, the computation capacity limited by hardware should meet the minimum requirement of the block and consensus computation. On the other hand, instead of DPoS, where stockholders vote for a committee candidate according to personal willingness, the IoT devices in Bychain prefer the candidate with high utility, i.e., the higher network quality and higher computation capacity, the higher probability to be voted.
From the viewpoint of IoT node n, the timestamps of transaction generation, block proposal and block finalization can be observed in the finalized blocks. Therefore, for given T th transaction that collected by mth committee member in block B, the delay of transaction and block procedure can be written as,
where τ T n→m denotes the delay of transaction propagation from node n to committee member m. The block computation delay τ C m consists of three parts: a) the hash time consumption τ ha m , b) the signature generation delay τ sig m , and c) the incentive computation delay τ ic m , τ C m = τ ha m + τ sig m + τ ic m . τ ic m will be described in next subsection IV-C. τ B f inal is the block finalization delay, which is determined according to the overall network quality. For the permissionless blockchain that may be world-widely deployed, τ B f inal is set to be 3s or 0.5s in Bitshares or EOSIO, respectively.
In general, τ B(T ) n→m implies the network quality and computation capacity of committee member m that observed by IoT node n. Consider the maximum block processing delay of being a committee member is Θ, we define an utility function to indicate the election,
where [a] + = max{a, 0}. U n→m is set to be 0 when the block processing delay observed by n is less than the given threshold Θ. Otherwise, U n→m would achieve a logarithmic increment. Therefore, the probability of n voting for m can be written as,
which means the higher utility of m, the higher chance to be voted. Then the committee M = {1, .., M c } is elected as the top M c winners.
2) Block Proposal, Block Propagation and Block Validation: When the committee is elected to take part in a consensus algorithm, at each block generation slot, the committee members take turns to act as a block miner proposing a block in a round-robin fashion.
In a specific block proposal process, the miner packages collected PoL transactions into an unverified block. The incentive allocation is also performed in this procedure. It is elaborated in the next subsection in IV-C. Then the unverified block is propagated to other committee members for block validation. The delay of information propagation highly depends on committee members' geographical distribution and the block size. The other committee members verify the signatures of the block proposer and transaction generator. If the verification is successful, the block is appended into the local block database. Otherwise, the appended procedure would be forbidden.
3) Block Finalization and Incentive Mechanisms: In Bychain, the block finalization follows the Longest-chain rule. Due to network uncertainty and possible malicious participant, the blockchain may be forked into the longest chain and several shorter chains. In this case, the block miner should always propose a block that extends the longest chain. Otherwise, a local database update should be performed ahead of the block proposal.
There are two kinds of incentive mechanisms involved in Bychain: 1) block generation can claim a certain amount of token reward, 2) IoT devices pursuing maximizing monitoring area can be rewarded a certain amount of votes. 1) is commonly applied to encourage more participants to join in the permissionless blockchain systems, e.g., Bitshares, Bitcoins, etc. We will describe 2) in detail.
In this subsection, we detail the incentive allocation mechanism to maximizing the total coverage area. For every 24 hours, or every 28800 blocks at 3s block production interval 1 , Bychain issues a fixed-value budget as total incentive of maximizing network communication coverage usage. With omnidirectional mobility, each IoT node is willing to find and deploy itself to where maximizes the next round reward. We define it as an Incentive Allocation for Maximizing Monitoring Area problem.
Problem: Given a coverage budget worth U, and N incentive-pursuing noncooperative nodes with isotropic communication module of available radius R, how should the budget be allocated so that the resulting configuration is tending to maximize the network communication coverage?.
Before going further, some underlying constraints need to be clarified:
• Global-class computing may not be feasible due to limited computation and power consumption of IoT devices. Furthermore, localization of devices is not globally available because, as mentioned in the last subsection, location ciphertext L pi,t cannot be publicly understood.
• Bychain opens for anyone to access, read, send, or receive transactions and blocks. Hence, the problem-solution requires high scalability and adaptivity to contain abrupt attendance or absence. • The connectivity between Bluetooth devices highly depending on the electromagnetic propagation characteristics of the natural environment. In certain scenarios with high path loss and shadow fading, the signal from sources in different directions is necessary to avoid the "dead" coverage zone.
Motivated by potential virtual field in robotic navigation and obstacle avoidance [24] , Bychain applies artificial virtual potential field to address above incentive allocation for maximizing monitoring area problem. Each witness node in the blockchain system is treated as a charged particle, such that artificial electric fields are constructed in a way that each node is repelled by repulsive force F (i,j) r from other nodes, thereby forcing the blockchain to spread itself throughout the environment. Bychain then introduces an attractive force F (i,j) a to gather nearby witness nodes, and keep the repetitive coverage area.
1) Potential Field of Single Node: According to the relationship between potential field and force, given ith witness node and jth near-by witness node, the repulsive force with respect to the scalar potential field P j can be written as,
where k rep denotes the strength constant of the repulsive field, r j is the Euclidean distance between node j and node i, where r j = || x j − x i || 2 , x j and x i denote the absolute position of node j and node i, respectively. In general, F (i,j) r is a conservative force that subjects to the gradient of potential field. The piecewise function indicates that each node out of the disc of radius R r would not affected by its repulsive potential field.
Let us focus on the potential field of ith witness node. As illustrated in Fig.4(a) , regardless of the attractive force F
could result in non-overlapping network coverage with uncovered gaps. Indeed, the repulsive-only field could perform well as an initial deployment solution of densely placed nodes. However, it probably conduces a discrete dot-like coverage in urban scene. Therefore, a larger range of attractive field is necessary to gether nearby nodes out of the repulsive field.
As illustrated in Fig.4(b) , an attractive field of F (i,j) a is constructed subjects to || F (i,j) a + F (i,j) r || = 0 on the circle of radius λR. Furthermore, for nearby node j, we wish F (i,j) a growth exponentially with r j , such that node i is able to pull far-distant node back. Hence, F (i,j) a is constructed as following, where k att denotes the strength constant of the attractive field. The resultant force between node i and node j is
Meanwhile, the combined attractive and repulsive potential field construct a zero potential ring at radius λR such that || F
shown as the red circle in Fig.5 . By substituting (11), (12) and r j = λR into constraint || F (i,j) a + F (i,j) r || = 0, the relationship between strengths of potential fields k rep and k att could be written as following,
Hence, λ 2 k att = (λ − 1) 2 k rep . 2) Potential Field and Intensive of Multiple Nodes: Let's extend the perspective to the relationship between multiple nearby nodes, denote as a node set K. The total force of node i can be given by,
The total force of node i results in an acceleration that adjust its velocity according to the well-known Equation of Motion. Therefore, given consensus round k, node i with velocity v k , the new velocity v k+1 can be written as:
where α < 1 denotes viscosity factor and m is the virtual mass of this node. Network Static Equilibrium and Intensive: It is obvious that the network could asymptotically approach a static equilibrium because the viscous friction term results in monotonically decreasing system energy over time. Hence, one can see a necessary condition for the maximum coverage of the network is the equilibrium on each node. Therefore, if blockchain aims to encourage nodes to participate in above coverage maximization, such objective should design proper budget allocation strategy to intensive motion of each node. Hence, Bychain allocates the coverage intensive to node i as follow,
where is a perturbation factor that sufficiently small preventing denominator to be 0. (18) performs three key characters: 1) the incentive of node i would decrease as || F i || increase.
2) When the network static equilibrium, each node would be distributed 1 n U budget.
3) The sum of network budget still approximately equal to U.
In this section, we analyze our proposed blockchain's security properties and prove that the protocol can achieve our security goals.
1) A prover cannot generate a location proof without a witness.
Since witnesses do not give away their private keys, a prover cannot claim the activities information by signing it using the private key of the witness. If this situation occurs, the blockchain key cryptography system can detect it.
2) If the witness does not reveal the private key, a prover cannot generate a legitimate location proof at the claimed location and claimed time without colliding with more than half of the witnesses.
If a witness does not provide its private key, the digital signature cannot be produced by any node except by the witness itself. In this case, there may be two kinds of attack:
(1) the prover may provide a false location claim, or (2) the prover may perform signature relaying attack, that is, store the digital signature in the last location and transmit it in the current location.
The attack (1) can be detected easily since the communication between the witness and prover is always nearrange communication. The witness will always calculate the distance between the prover and the witness. If the distance calculated from the physical layer is significantly different from the claimed location information, this attack can be easily detected by the witness. (2) There is an auto-increment field nonce wj corresponding to the jth witness w j . Consequently, the nonce wj is different in each PoL. If the attack (2) occurs, the signature could not be the same due to nonce wj . Therefore, attack (2) can be easily detected by verifying the content.
In the proof-of-location stage, the prover may receive more than one proof-of-location response. Since the witness is semitrusted and majority-honest, the attack can be conveniently detected by analyzing the proof-of-location responses if the prover does not collude with more than half of the witness nodes.
3) The prover, witness and verifier are not able to modify generated activity proofs.
In the second stage, the proof-of-location information is uploaded on the blockchain, and the data on the blockchain is transparent and tamper-resistant. It is almost impossible to modify the generated activity proofs. 4) This protocol is able to avoid the PoL replaying attack on the blockchain.
Due to the consistency of the blockchain database, the on-chain storage space is precious. A malicious user may resubmit the PoL commitment to occupy the storage space, named the PoL replaying attack. Since each peer of the blockchain network checks, if the current PoL is contained in the blockchain database before submitting, it is not possible to successfully complete the replaying attack.
5) A verifier can verify the activity information without the private key of the proof.
The zero-knowledge proof is applied in our protocol. The private key will not be revealed to the service provider. The signature of the activity information is verified by providing the verifier, a signed verifier-specified nonce, and this kind of attack can be avoided.
6) Only the prover and verifier can access the location information in this protocol, such that the privacy is maximized.
While these activity proofs are uploaded on the blockchain such that they are transparent to all the other users, the public key and private key are managed by key escrow and changed in each k proof-of-location stage. No one can connect this information with an uniform identity. At the same time, the user does not need to reveal its private key to anyone else when verifying ownership, such that the risk of revealing the private key is avoided. Hence, privacy is maximized.
To verify our system in a real-world setting, we implement production-grade software by using Bluetooth 5.0. The implemented system is shown in Fig.7 . In this section, we study the performance and constraints of our proposed protocol, such as the message interaction latency, power consumption, computation and storage limitations. The main software components and data structures are shown as follows.
• Programming Language: The client is implemented using Java and Kotlin while the blockchain server and smart contract are implemented using C++. Kotlin is a statically typed language with a type inference suggested as an alternative to Java on the Android platform. We use Kotlin to reduce the programming complexity on the client interface. Due to the low computation cost, C++ is considered to be one of the best choices of our blockchain system. • Bluetooth 5.0: This is latest version of the Bluetooth wireless communication protocol. We adopt Bluetooth 5.0 in our protocol to study the feasibility of our protocol under the latest wireless standards. The PoL message exchange can also benefit from the extended advertising data length such that the signal Bluetooth frame is able to carry our PoL requests and PoL responses. In our software, the Bluetooth 5 advertising extension mode is employed. The primary physical layer parameter is LE 1M and the secondary physical layer is LE 2M. • OpenSSL: This is a general-purpose cryptography library for the transport layer security (TLS) and secure sockets layer (SSL) protocols. The OpenSSL library is a successor of commercial-grade and full-featured cryptography implementations. OpenSSL is required in our protocol to provide signing, signature verification, key pairs generation and key escrow operations. • Bitcoinj-core: This is a Java implementation of the Bitcoin protocol for building blockchain applications. Peerto-peer communication, network nodes organization and the blockchain object database are implemented and applied in our protocol. • nRF-connect: This is wireless performance analysis software that is produced by Nordic Semiconductor, including Bluetooth, WiFi and cellular signals. The received signal strength indication (RSSI), packet history, packet changes, Bluetooth advertising intervals, etc., can be analyzed using nRF-connect in real time and in real-world applications. Fig. 7 . Implemented System which is composed of a Google Pixel2, an One Plus 6, several Bluetooth beacons and the blockchain nodes that running on Alibaba Cloud.
Blockchain network and nodes: We realize our protocol on Alibaba Cloud. On the blockchain, we generate the genesis block (known as the first block of blockchain) using the unique Merkle hash root at 2017-09-05 12:15:00. After two years of running, it is proved that our DPoS blockchain is stable in practice. We then modified its incentive mechanism from March 2020. Because the on-chain data transaction is not heavy, the current size of our private blockchain database is approximately 2.4 GB and the number of network nodes is approximately 65. Note the number of nodes varies from 60-68 during the experiment. To simulate the real world, our blockchain is implemented on an Intel(R) Xeon(R) CPU E5-2650 v3 platform with 2 GB RAM and 10 Mbps bandwidth for each node is provided by Alibaba Cloud and Amazon Cloud. Nodes in the blockchain network are virtual private servers such that they broadcast and receive block messages via a physical communication link. The mining interval is set as 3 s.
The provers and witnesses: To mimic real-world user activities, we developed a client to realize the functions required by the prover and witness. The client is implemented by Java and Kotlin on One Plus 6 and Google Pixel 2 (all with Android 9.0). One plus 6 equips Qualcomm SDM845 Snapdragon 845 (10 nm) with 4x2.8 GHz CPU cores and 4x1.7 GHz CPU cores, 6 GB RAM, WiFi 802.11 a/b/g/n/ac, Bluetooth 5.0 and a GPS module. Google pixel 2 equips Qualcomm MSM8998 Snapdragon 835 (10 nm) with 4x2.35 GHz CPU cores and 4x1.9 GHz CPU cores, 4 GB RAM, WiFi 802.11 a/b/g/n/ac, Bluetooth 5.0 and a GPS module. Both One Plus 6 and Pixel 2 can communicate with blockchain via the WiFi or 4G signal provided by China Mobile.
Data structure: The interacted message involved in our protocol includes the following: the PoL request P k , the PoL response R k , the PoL commitment Com k and the verification information N k . In our protocol, the length of P k advertising data is approximately 320 bytes including a 128-bit service UUID and payload data shown in (2) . The message length is heavily dependent on the key length of the cryptosystem. There always exists a trade-off between the performance and security level when deciding the public key length. Our public key is a 160-bit hash of the SHA256 hashed ECDSA public key and the private key is abstract syntax notation one (ASN.1) coded strings. The signature of the PoL commitment is a 65-bit ECDSA formed signature. As a comparison, the length of R k is approximately 540 bytes, and the PoL commitment under a single witness is approximately 520 bytes. The location information is required from the GPS module with 14 bit data and 10 −7 accuracy, i.e., centimeter-level location information.
In this subsection, we study the performance and cost of deploying our protocol including the storage, CPU, power consumption, and the latency in each procedure. We also measure the system performances under various relative velocities and number of witnesses.
1) Storage, CPU and Power Consumption: The running of the client code costs approximately 120 MB of data memory, while the blockchain system takes approximately 3.5 GB of data memory. With 62 blockchain network nodes mining the block, the blocks of uploaded location information generate each 6 seconds. Considering that the peer-to-peer network propagation delay is unstable, we monitor the arrived time interval of each block indicating the timestamp differences of the current arrived block and the last arrived block. The result shows that the minimum time interval is 6532 milliseconds and the maximum time interval is 13245 milliseconds. The arrived time interval depends on the network condition, such as the retransmission rate and the verification delay of the PoS algorithm. Therefore, we believe that a powerful CPU and the adjoining blockchain network node may have a positive effect on the blockchain propagation time.
We monitor the CPU utilization of each prover, the witness nodes and the blockchain nodes. When the prover node is broadcasting and the witness node is monitoring, the CPU consumption is approximately 4 percent and 0.5 percent, respectively. This may be due to the listening Bluetooth signal employing less computation than the emitting Bluetooth signals. Another possible reason is that the cryptosystem involved in the prover processing flow costs more in terms of computation. The CPU utilization of blockchain mining nodes is always above 30 percent. We also realize that the CPU utilization of the network mining node reaches a peak when it is mining the block, in which heavy computations such as authentication and encryption/decryption are involved.
The power consumption of the prover, witness and blockchain is studied as well. We monitor the device power consumption before and after the program launched as P before and P after , respectively. Hence the power consumption of each entity can be computed as P E = P after −P before . The experiment is evaluated 50 times for each entity to study its statistical properties, which is shown in Table I . For each experiment and each entity, we measure the CPU utilization and power consumption with distances d p−w = 3 m and 15 m between the prover and witness. It is shown that farther Bluetooth signal interaction causes higher power consumption while computation varies little.
2) Delay Evaluation: We evaluate the time delay of each procedure in a relative static environment, where the prover and witness are immobile. The system parameters are shown in Table II . During the evaluation, the PoS blockchain system is maintained by 65 mining nodes. The Pixel 2 is in witness mode and One Plus 6 phone is set in the prover mode with the advertising interval t adv = 100 ms, which is the minimum advertising interval provided in the Android Bluetooth Low Energy API . We set the maximum advertising duration t adv = 1000 ms in the implementation.
The reason for this setting is to try to minimize the detection delay that is caused by random access methods in the Bluetooth protocol. Ideally, the prover's Bluetooth module broadcasts an advertising frame in each advertising event, while the duration of advertising event is controlled by the advertising interval. However, the scanning window of the witness's Bluetooth module is independent of the prover's advertising event, such that the Bluetooth message interaction succeeds if and only if the witness's scanning window coincides with the prover's advertising event. Because the prover does not share its information with witnesses, the message interaction of the prover and witness is considered to be a random access event. We set the minimum advertising interval to improve the possibility of successive Bluetooth message interactions. Hence, the communication delay of the PoL message interaction will be minimized. Fig. 8 . Average time delay of each procedure. T1 is the key escrow generation (key-pair generation for 100 times), T2 denotes the PoL request generation, T3 represents the delay of the PoL request emission task, T4 is the time cost of signature generation, T5 is the time cost of PoL commitment uploading, T6 is the signal propagation delay between the prover and witness.
We also constrain the blockchain parameters' maximum block size S MAX block and maximum commitment size S MAX COMM as 2 MB and 9 KB to mimic real-world network conditions, respectively. In our experiment, the adoption of Alibaba Cloud and Amazon Cloud may cause unrealistic network conditions because the blockchain miner is considered to be worldwide and under various network conditions. The network condition of our miner nodes are much better than the average blockchain miners such as Bitcoin miners, including the average packet loss probability, the network bandwidth and average latency. A large block size (>2 MB) and commitment size (>9 KB) increase the computation complexity and bandwidth requirement such that it is much more difficult to maintain the data consistency of the distributed blockchain database. According to the running parameters of the Bitcoin blockchain, we adopt S MAX block = 2 MB and S MAX COMM = 9 KB to mimic a world-wide deployed blockchain system.
To study the sensitivity of our protocol to the time delay of each procedure, we evaluate the time durations of key escrow generation, PoL request generation, PoL request emission, signature generation, PoL commitment uploading and the overthe-air signal propagation delay. After a 50-turn test, the average time delay of each procedure is illustrated in Fig. 8 . Among these procedures, the key escrow generation, PoL commitment uploading and the over-the-air signal propagation delay are significantly higher than the others. The PoL commitment uploading is limited by the propagation delay and churn of the peer-to-peer blockchain network; thus it is observed to have high volatility that increases to 421 ms and decreases to 121 ms. The signal propagation delay is determined by the channel states of Bluetooth with respect to the relative velocity and activity between the prover and witness. We will further study the influence of key escrow generation and activity in next subsection.
The generation of key pairs and signature is studied to evaluate the authentication performance and security. The delay of the key and signature generation and verification is highly dependent on the device performance. We run key pair generation and signature verification 10,000 times regarding secp256k1 (with 128 bits of security strength), secp128r1 (with 64 bits security strength), secp192k1 (with 96 bits security strength), secp384r1 ((with 192 bits security strength)), secp521r1 (with 256 bits security strength), and curve25519 (with 128 bits security strength) on One Plus 6 and Pixel 2. The performances of key generation under different security strengths are shown in Fig. 9 . The performance evaluation shows that the time cost increase exponentially with the security strength. However, the curve 25519 algorithm performs with more complexity than secp256k1 even in same security strength. Hence, secp256k1 is implemented in our blockchain system.
3) Activities Evaluation: We further evaluate the sensitivity of over-the-air signal propagation to the received signal strength indication (RSSI) and various activity conditions. We adopt Pixel 2 as the prover, all witnesses are static, the experimental tests are conducted in an urban area, and the initial activity condition is shown in Fig. 10(a) . It is shown that the RSSI decreases with the more significant initial distance d p−w and the tremendous accelerated velocity of a; this confirms our intuition and suggestions. When a barrier wall appears in the experiment, the Bluetooth signal faces significant fading such that there appears a 2-second gap in subfigure (h). The PoL message interactions are impossible in this signal gap. A prover walking through multiple witness nodes is evaluated in (j),(k), and (l): the witnesses are placed around the prover in (j), and one-by-one in (k) and (l). The signals that originate from different witnesses are painted with different colors. The result confirms that our protocol works well to collect multiple witness messages in an urban area. Although the PoL message interaction could not coincide, the time interval between each PoL message interaction event is still acceptable at 0.4-2 s, such that a running user could not run out of the coverage area of Bluetooth 5.0 equipment.
In this paper, we proposed and implemented a decentralized blockchain system for activity-proofing and contact tracing. In the proposed protocol, activity and location-proof problems are addressed by a combination of cryptographic techniques and a decentralized blockchain system without reliance on trusted third parties. The identity privacy problem is protected by proposing a combination technique of zero-knowledge proof and key escrow. The connection of unique cryptographic identity and on-chain proof-of-location commitment is decoupled such that it is almost impossible to track and identify the owner of transparent on-chain data. Hence, security and identity privacy is protected. A location-based consensus algorithm is proposed aiming to maximize the monitoring area. The incentive allocation technology is performed by virtual potential fields. Several implement results are shown to provide a practical perspective. Yan Zhang (Fellow, IEEE) received the Ph.D. degree from the School of Electrical and Electronics Engineering, Nanyang Technological University, Singapore. He is currently a Full Professor with the Department of Informatics, University of Oslo, Oslo, Norway. His research interests include nextgeneration wireless networks leading to 5 G beyond/6 G, green and secure cyber-physical systems (e.g., smart grid and transport 