Query Results Authentication of Outsourced Append-Only Databases

In the scenario of database outsourcing, database management is outsourced to the professional third-party, and one of the critical problems is integrity authentication of the query results. As far as we are concerned, we are the first to propose the problem of outsourced append-only database. According to the features of outsourced append-only database, a new authentication data structure, Min-Max Hash tree is proposed based on the current authentication data structure. It can be utilized by the clients to solve the problem of authenticating the query results. For the data owner side, a basic data forwarding algorithm is proposed; and for the service provider side, the algorithm of querying rise, fall or oscillation amplitude in price and the algorithm of query results authentication are proposed respectively for one-shot query and continuous query. Finally, optimization measures are proposed for data forwarding, storage of authenticated data structure in the data owner side and continuous query in the service provider side, by which the space of storage is diminished greatly and the whole efficiency of data processing is improved further. Extensive experiments have demonstrated the effectiveness and efficiency of the proposed Min-Max Hash tree. It can be utilized to authenticate the query results and to process the massive data.