Authoritative GIS without Trusted Third Parties

Geographic Information Systems (GIS) are crucial for various applications that include emergency response and national security. The primary vulnerability of GIS systems lies in their reliance on the integrity of numerous third parties. Such third parties include government bodies at both national and local levels, GIS applications developed by private companies, and notoriously insecure general purpose computers that host GIS data and run GIS applications. Consequently, GIS processes - for collecting, storing, organizing and communicating geographic information - are susceptible to wide a range of malicious attacks and/or uninten-tional bugs. The proposed AGS protocol aims to rectify this vulnerability by obviating the need for trusted third parties. This is achieved through i) the use of Merkle tree proofs for incrementally, and eciently, computing a succinct cryptographic commitment to important geographic data; and ii) permitting updates to GIS data only through well-formed blockchain transactions. In the proposed approach leaves of Merkle hash trees are used to represent line segments forming the boundary of a geographic region and irregular triangular tiles that are guaranteed to tile the entire region. The Merkle trees are constructed incrementally, through transactions executed in a blockchain network. The response to any query regarding a point in the globe is a triangular tile in which the point falls, along with succinct Merkle tree proofs for the correctness of information.