Authoritative and Unbiased Responses to Geographic Queries
- 1 Mississippi State University, Starkville, MS, USA
- 2 Slippery Rock University, Slippery Rock, PA, USA
Abstract
A protocol for processing geographic data is proposed to guarantee authoritative and unbiased responses to geographic queries, without the need to rely on trusted third parties. The integrity of the proposed authoritative and unbiased geographic services (AUGS) protocol is guaranteed by employing novel hash tree based authenticated data structures (ADS) in conjunction with a blockchain ledger. Hash tree based ADSes are used to incrementally compute a succinct dynamic commitments to AUGS data. A blockchain ledger is used to record 1 ) transactions that trigger updates to AUGS data, and 2 ) the updated cryptographic commitments to AUGS data. Untrusted service providers are required to provide verification objects (VOs) as proof-of-correctness of their responses to AUGS queries. Anyone with access to commitments in ledger entries can verify the proof.
- Mockapetris, P.V. (1987) Domain Names—Concepts and Facilities. RFC Editor. https://doi.org/10.17487/rfc1034
- Arends, R., Austein, R., Larson, M., Massey, D. and Rose, S. (2005) RFC 4033: DNS Security Introduction and Requirements. https://doi.org/10.17487/rfc4033
- Chang, K. and Tsung, K. (2016) Introduction to Geographic Information Systems. 9th Edition, McGraw-Hill, New York.
- ESRI White Paper (1998) ESRI Shapefile Technical Description. https://www.esri.com/library/whitepapers/pdfs/shapefile.pdf
- Weiler, S. and Ihren, J. (2006) RFC 4470: Minimally Covering NSEC Records and DNSSEC On-Line Signing. https://doi.org/10.17487/rfc4470
- Laurie, B., et al. (2008) DNS Security (DNSSEC) Hashed Authenticated Denial of Existence. RFC 5155. https://doi.org/10.17487/rfc5155
- Topologically Integrated Geographic Encoding and Referencing (TIGER) Database, United States Census Bureau. https://www.census.gov/geo/maps-data/data/cbf/cbf_state.html
- Baugmgarten, H., Jung, H. and Mehlhorn, K. (1994) Dynamic Point Location in General Subdivisions. Journal of Algorithms, 17, 342-380. https://doi.org/10.1006/jagm.1994.1040
- Dobkin, D. and Lipton, R.J. (1976) Multidimensional Searching Problems. SIAM Journal on Computing, 5, 181-186. https://doi.org/10.1137/0205015
- Nekrich, Y. (2021) Dynamic Planar Point Location in Optimal Time. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Rome, 21-25 June 2021, 1003-1014. https://doi.org/10.1145/3406325.3451100
- Arya, S. and Mount, D.M. (2005) Computational Geometry: Proximity and Location. In: Mehta, D. and Sahni, S., Eds., Handbook of Data Structures and Applications, Chapman & Hall/CRC, Boca Raton, 22.
- Anagnostopoulos, A., Goodrich, M.T. and Tamassia, R. (2001) Persistent Authenticated Dictionaries and Their Applications. Information Security Conference (ISC), Vol. 2200, 379-393. https://doi.org/10.1007/3-540-45439-X_26
- Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A. and Stubblebine, S. (2001) A General Model for Authentic Data Publication. VC Davis Department of Computer Science Technical Report.
- Ramkumar, M. (2014) Symmetric Cryptographic Protocols. Springer, Berlin. https://doi.org/10.1007/978-3-319-07584-6
- Adhikari, N., Bushra, N. and Ramkumar, M. (2019) Complete Merkle Hash Trees for Large Dynamic Spatial Data. The 2019 International Conference on Computational Science and Computational Intelligence (CSCI’19), Las Vegas, 5-7 December 2019, 1318-1323. https://doi.org/10.1109/CSCI49370.2019.00246