We study the design of secure protocols for efficiently verifying the results of queries on data structures that are outsourced to untrusted servers, where answers are processed over relational databases in the RAM model of computation. We introduce a new authentication framework that, by design and through the new concept of query certification, aims at verifying the validity of the answer, rather than each step of the algorithm that generates the answer. Our framework efficiently reduces the authentication of general queries to that of set-membership queries, and provides sufficient conditions for achieving super-efficient answer verification (in time asymptotically less than the time spent to answer the query).
The emergence of cloud computing has introduced new data management and dissemination models, where data is typically processed by untrusted, often unknown, machines. In this distributed computing setting, we would like to assure users that computations performed in the cloud have the same output as if they were locally executed.
In this paper, we study the design of secure and efficient protocols for proving the correctness of computations on data that is outsourced to remote untrusted servers. Here, a data owner outsources a database to a third-party responder who answers incoming queries on it. Assuming that the responder may erroneously or maliciously modify the query results, our goal is to augment the data structure and the associated protocols so that end-users receive efficiently verifiable proofs of the returned answers.
Verifying the output of algorithms has been the subject of research in the context of
correctness checking, including work on the certification of programs, data structures,
and graph and geometric algorithms (e.g., [
Extensive research over the last decade has led to the development of
authenticated data structures (e.g., [
Preliminary progress has also been made on the design of more general
authentication techniques for searching in directed acyclic graphs [
In this work, we propose an authentication framework that provides new techniques for systematically building efficient and secure data authentication schemes. We depart from previous approaches by (1) decoupling the answer-generation process and the answer-verification process in a general query model over dynamic data; and (2) achieving the separation of the algorithmic and cryptographic components in the design of data authentication schemes. Our main result is that a very general class of query types can be authenticated securely and without loss of efficiency.
We provide a formal definition for the problem of verifying query answers through query authentication schemes in a setting where the (honest) data owner and the (malicious) query responder are distinct entities, and where end-users do not trust (the authenticity of) the answers to their queries. Aiming at general results, we use the RAM computational model as well as a general data type and query model. The central idea in our framework is as follows: in contrast to approaches that authenticate the execution of the algorithm that answers a query, we propose an answer-based approach where only the information that is necessary for the answer verification is being authenticated.
To achieve our goal, and inspired by certifying algorithms (e.g., [
Moreover, this transformation of a certification data structure into an authenticated
data structure satisfies an important property: to verify an answer to a general query,
the authenticated data structure can only use a query authentication scheme for
setmembership queries, that is, protocols that verify membership in sets (actually, only
positive answers to these queries). To show this property, we introduce the concept of
query reducibility in data authentication. Informally, we say that query of type A is
authentically reduced to query of type B if a query authentication scheme for B leads to
a query authentication scheme for A. We thus show that any query problem over
relational databases is authentically reduced to the fundamental set-membership problem in
a way that preserves efficiency. The usefulness of this reduction stems from the fact that
several efficient cryptographic constructions exist for set-membership query
authentication schemes, including Merkle trees [
Finally, our framework yields a method for achieving super-efficient data
authentication, where verifying the answer is asymptotically faster than answering the query.
Indeed, although the above completeness result is proven by verifying the query-answering
algorithm (thus extending previous possibility results [
The rest of this paper is organized as follows. In Section 2, we introduce certification data structures, which model answer testability, a core concept in our work, and provide a constructive proof of their existence. In Section 3, we describe query authentication schemes. In Section 4, we present our main possibility results for data authentication and, in Section 5, we present some applications of our framework. 2
A (structured) data set S = (E , R) consists of: (i) a collection E = {E1, . . . , Et} of
sets of data elements such that, for 1 ≤ i ≤ t, set Ei is a subset of a universe Ui, and
(ii) a collection R = {R1, . . . , Rk} of indexed sequences of tuples of data elements
such that, for 1 ≤ i ≤ k, sequence Ri = (Ri[
Our data model shares concepts from the relational database model using indexed sequences of tuples, i.e., each member Ri of R is an array of tuples, where each tuple can be indexed by an integer. Thus, very general data organization and algorithmic paradigms are captured. For instance, a graph G = (V, E) may correspond to data set SG = (E , R), where E = V and R consists of a single sequence of indexed pairs representing relation E (edges in G). More complex graphs, e.g., with edge directions, weights, costs or associated data elements, can be represented by appropriately including new primitive data-element sets in E and corresponding sequences in R describing the structure of data elements as well as various relations among them.
A query operation QS on data set S = (E , R) is a computable function QS : Q → AS , where Q is the query space (the set of all possible queries q of specific type that can be issued about S) and AS is the answer space (the set of all possible answers to queries on S drawn from Q). The answer of a query q ∈ Q under QS is QS (q) ∈ AS . An element a ∈ AS of the answer space is the correct answer for query q if and only if QS (q) = a. The above description captures general query operations on data sets that are based on relations. The only requirement is that any query in the query space is mapped to a unique answer in the answer space and that any answer corresponds to some query.1
For example, if SG = (E , R) represents a subdivision of the plane into the polygons induced by the vertices and edges of a planar graph G embedded in the plane, the point location query operation maps a point in the plane (query) to the unique element of the subdivision (region, edge, or vertex) containing it (answer).
Regarding the complexity of query answering, we only require that query operation QS is efficiently computable. Typically, function QS is evaluated on query q ∈ Q by an algorithm that operates over S through a data structure that supports queries in Q. A query data structure D(QS ) for a query operation QS : Q → AS on data set S = (E , R) consists of a structured data set (EQ, RQ), such that E ⊂ EQ and R ⊂ RQ and an algorithm Answer, which on input a query q ∈ Q and data set (EQ, RQ), returns QS (q) ∈ AS in time polynomial in n and |q| by accessing and processing tuples in R. We write D(QS ) = (EQ, RQ, Answer). Given input query q, algorithm Answer operates over S through the use of D(QS ): by processing relations in RQ, Answer accesses relations in R, evaluates conditions over elements in S and produces the answer.
For example, for the point location algorithm based on the chain method [
A data set S is static if it stays the same over time and dynamic if it evolves through update operations performed on S. An update operation US for S is a function that given an update y ∈ Y, Y being the set of all possible updates, results in changing one or more data elements in E and one or more tuples in R. If S is static (resp. dynamic), data set (EQ, RQ) can be constructed (resp. updated) by some algorithm ConstrQ (resp. UpdateQ) that runs on input S (resp. S and y ∈ Y) in polynomial time in n.
Our data querying model achieves generality by combining the expressiveness of relational databases with the power of the RAM computation model. By using indexannotated relations, complex data organizations are easily represented and accessed. For instance, indirect addressing is supported by treating indexes as a distinct data type which is included in E . Thus, our model strictly contains the pointer machine model.
We now explore the decoupling of query answering and answer verification. We start by defining the notion of answer testability, formally expressed through a certification data structure. This notion captures the following property in data querying: query operations on any data set return verifiable answers that can be tested to be cor1 Unique answers are used without loss of generality as we can appropriately augment the query space to include the index of the answer (according a fixed ordering) that we wish to obtain. rect given a (minimal) subset of specially selected relations over elements of the data set. In essence, queries are information-theoretically certified to return valid answers. Definition 1 (Certification Data Structure). Let D(QS ) = (EQ, RQ, Answer) be a query data structure for query operation QS : Q → AS on data set S = (E , R) of size n. A certification data structure for S with respect to D(QS ) is a triplet C(QS ) = ((EC , RC ), Certify, Verify), where (EC , RC ), called the certification image of S, is a structured data set and Certify and Verify are algorithms with the following properties: Answer tests: On input query q ∈ Q and data sets (EQ, RQ) and (EC , RC ), algorithm Certify returns answer a = QS (q) and an answer test τ , which is a sequence of pairs (i, j), each indexing a tuple Ri[j] of RC . Answer test τ defines a subset RC (τ ) ⊆ RC , called the certification support of answer a.
Answer testability: On input query q ∈ Q, data set (EC , RC ), answer a ∈ AS and answer test τ , algorithm Verify accesses and processes only relations in RC (τ ) and returns either 0 (rejects) or 1 (accepts).
Test reliability: (i) For all q ∈ Q, Verify(q, RC , Certify(q, (EQ, RQ), (EC , RC ))) = 1 (completeness); and (ii) for all queries q, answers a, and answer tests τ , whenever it is Verify(q, RC , a, τ ) = 1, we have that a = QS (q) (soundness).
Regarding complexity measures for certification data structure C(QS ), we say: (1) C(QS ) is answer-efficient if the time complexity TC (n) of Certify is asymptotically at most the time complexity TA(n) of Answer, i.e., TC (n) is O(TA(n)); (2) C(QS ) is time-efficient (resp. time super-efficient) if the time complexity TV (n) of Verify is asymptotically at most (resp. less than) the time complexity TA(n) of Answer, i.e., TV (n) is O(TA(n)) (resp. o(TA(n))); and analogously (3) C(QS ) is space-efficient (resp. space super-efficient) if the space requirement SC (n) of (EC , RC ) is asymptotically at most (resp. less than) the space requirement SQ(n) of (EQ, RQ), i.e., SC (n) is O(SQ(n)) (resp. o(SQ(n))). If S is static, data set (EC , RC ) can be constructed by some algorithm ConstrC that runs on input S in polynomial time in n.
For simplicity, the above definition corresponds to the static case. The dynamic case can be defined similarly. Informally, an update algorithm UpdateC is responsible to handle updates in data set S by accordingly updating C(QS ); that is, it produces the updated set (E C′ , R′C ) and, in particular, the set of tuples where R′C and RC differ. Algorithm UpdateC additionally produces an update test (as the answer test above, a set of indices for tuples in RC ) that validates the performed changes. Similarly, an update testing algorithm Updtest, on input an update y ∈ Y , set RC , a set of tuples (changes in RC ) and an update test, accepts if and only if the tuples correspond to the correct, according to y, new or deleted tuples in RC . Similarly, we can define update efficiency and update-testing (super-)efficiency for C(QS ), with respect to the time complexity of UpdateC and Updtest, respectively, as they asymptotically compare to UpdateQ.
Certification data structures introduce a new dimension in the study of data querying and answer validation. They support certification of queries in a setting where the notions of query answering and answer validation are conceptually and algorithmically separated in a clean way. In particular, answer validation is based merely on the certification image (EC , RC ) of S = (E , R) (these two sets share tuples, possibly, through a subset relation) and not on set (EQ, RQ) of the query data structure. Also, query certification depends only on the certification support of the answer, i.e., subset R(τ ).
We first prove that for every query type, there is an efficient certification structure, a completeness result showing that all queries can be certified without loss of efficiency. Theorem 1. Any query data structure for any query operation on a data set admits a certification data structure that is answer-efficient, time-efficient, update-testing-efficient, and space-efficient.
Proof. (Sketch.) We discuss the static case; the dynamic case is treated analogously. Let S = (E , R) be a data set of size n, QS a query operation on S and D(QS ) = (EQ, RQ, Answer) a query data structure for QS . We describe a certification data structure C(QS ) = ((EC , RC ), Certify, Verify) for S with respect to D(QS ). First we set (EC , RC ) = (EQ, RQ). Algorithm Certify is an augmented version of Answer. Given a query q ∈ Q and sets (EC , RC ), (EQ, RQ), Certify creates an empty sequence τ of indices of tuples in RC and then it runs Answer on input (q, (EQ, RQ)) to produce the answer QS (q). Also, any time algorithm Answer accesses a tuple Ri[j] in RQ, algorithm Certify adds (i, j) to the end of sequence τ . When Answer terminates, so does Certify, and returns the output a = QS (q) produced by Answer and sequence τ as the corresponding answer test. Algorithm Verify as an augmented version of Answer operating as follows. On input a query q ∈ Q, set (EC , RC ), an answer a and a sequence τ , algorithm Verify starts executing algorithm Answer on input (q, (EQ, RQ)) and checks the execution of Answer subject to sequence τ . That is, each time Answer retrieves a tuple Ri[j] in (EQ, RQ), Verify removes the first element of τ and compares it to (i, j), rejecting the input if the comparison fails. When Answer terminates, the answer computed by Answer is compared with the answer provided as input: if the two answers agree (are equal) then Verify accepts its input, otherwise it rejects.
Completeness and soundness conditions are satisfied by construction. Finally, our certification data structure is answer-, time- and space-efficient. This follows from the fact that for any inputs, Certify and Verify do a total amount of work that is only by a constant factor more than the work of Answer, thus TC (n) = O(TA(n)) and TV (n) = O(TA(n)), and the fact that (EC , RC ) = (EQ, RQ), thus SC (n) = O(SQ(n)). Observe that each pair (i, j) in the answer test τ is accessed in constant time. ⊓⊔
Certification data structures are designed to accompany two-party data query
protocols as follows: party A possesses sets (EQ, RQ) and (EC , RC ) and runs Certify,
and party B possesses set (EC , RC ) and runs Verify. The underlying outsourced set
S is controlled by B by creating update and query operations for S. Although both
operations are performed at A, B is able to verify their correctness. Thus, this setting
models certified outsourced computation: at any point in time, B maintains a correct
certification image of S, allowing verification without loss of efficiency, by Theorem 1.
Although its existential proof is simple (both parties execute the same algorithms on the
same data) yet, its significance is justified by the following:
1. In addition to showing that Definition 1 is meaningful, Theorem 1 proves the
feasibility of answer testability for any computable query in a general querying and
computational model.
2. Time super-efficient certification is in general feasible (e.g., for range searching [
We describe a general model for data authentication by introducing query authentication schemes, cryptographic protocols for verifying the results of general queries over data sets. We extend certification structures to achieve correctness validation (in a computational sense) in a setting where the owner of a data set does not control the data structure used to answer queries. Instead, queries are answered by an untrusted, possibly malicious, party, and answers are augmented with a proof used to verify validity.
A three-party data querying model consists of a source S, a responder R and a user U , where: (1) source S creates (and owns) a dynamic data set S, which is maintained by query data structure D(QS ) for query operation QS : Q → AS on S; (2) responder R stores S, by maintaining a copy of D(QS ) and some auxiliary information for S; (3) user U issues queries about S to responder R by sending to R a query q ∈ Q; (4) on a query q ∈ Q issued by U , R computes answer a = QS (q) and sends a to U ; (5) on an update y ∈ Y for S issued by S, S and D(QS ) are appropriately updated by S and R. Definition 2 (Query Authentication Scheme). A query authentication scheme for query operation QS : Q → AS on set S is a quadruple of algorithms (G, Auth, Res, Ver) s.t.: Key generation: Algorithm G takes as input a security parameter 1κ, and outputs a key pair (PK , SK ). We write (PK , SK ) ← G(1κ).
Authenticator: Algorithm Auth takes as input the secret and public key (SK , PK ), the query space Q (or an encoding of the query type) and data set S of size n and outputs an authentication string α and a verification structure V, that is (α, V) ← Auth(SK , PK , Q, S), where α, V ∈ {0, 1}∗.
Responder: Algorithm Res takes as input a query q ∈ Q, a data set S of size n and a verification structure V ∈ {0, 1}∗ and outputs an answer-proof pair (a, p) ← Res(q, S, V), where a ∈ AS and p ∈ {0, 1}∗.
Verifier: Algorithm Ver takes as input the public key PK , a query q ∈ Q, an answerproof pair (a, p) ∈ AS × {0, 1}∗ and an authentication string α ∈ {0, 1}∗ and either accepts the input, or rejects, i.e., {0, 1} ← Ver(PK , q, (a, p), α). Updates: For the dynamic case, we additionally require the existence of an update algorithm AuthU that complements algorithm Auth and handles updates; namely, AuthU given update y ∈ Y, it updates the authentication string and the verification structure: (α′, V′) ← AuthU (SK , PK , Q, S, y, α, V).
We require two properties for a query authentication scheme: correctness and security. Correctness mandates that a verification algorithm should accept valid answerproof pairs generated by the responder. Security dictates that, given any query issued by U , a computationally bounded malicious responder R cannot compute an incorrect answer and an associated proof such that U accepts this pair (thus, incorrectly validating a fake answer). In our three-party data querying model, we assume that U trusts S but not R, and that R always participates in the protocol (i.e., we do not consider denial-of-service attacks).
Definition 3 (Correctness & Security). We say that a query authentication scheme (G, Auth, Res, Ver) is correct if for all queries q ∈ Q, if (α, V) ← Auth(SK , PK , Q, S) and additionally (a, p) ← Res(q, S, V), then with overwhelming probability it holds that 1 ← Ver(PK , q, (a, p), α) and QS (q) = a. We say that a query authentication scheme (G, Auth, Res, Ver) for query operation QS : Q → AS on structured data set S is secure, if no probabilistic polynomial-time adversary A, given any query q ∈ Q, public key PK and oracle access to the authenticator algorithm Auth, can output an authentication string α, an answer a′ and a proof p′, such that a′ is an incorrect answer that passes the verification test, that is, a′ 6= QS (q) and 1 ← Ver(PK , q, (a′, p′), α).
We say that a correct and secure query authentication scheme (G, Auth, Res, Ver) for queries in query space Q on a data set S constitutes an authenticated data structure for this type of queries. It is implied that, given an authentication string α, for algorithm Ver it holds that, for all queries q ∈ Q, with all but negligible probability (that is measured over the probability space of the responder algorithm) it holds that QS (q) = a if and only if there exists p s.t. 1 ← Ver(PK , q, (a, p), α). 4
We now describe the main results of our work. First, we introduce the notion of reducibility in data authentication by defining reductions between query authentication schemes. We then prove that the authentication of any query is reduced to the authentication of set membership queries. In fact, we need to authenticate only positive answers—that is, relation ∈, but not ∈/, is authenticated. Next, we present implications of this result.
Using certification structures, we provide a general methodology for constructing correct and secure query authentication schemes. Also, based on super-efficient query certification, we develop a method for data authentication where only the information necessary for answer verification is authenticated, and not the entire execution of the search algorithm, which leads to a framework for the design of authentication structures with super-efficient verification.
Let QAS (QS , S) denote a query authentication scheme (QAS) for QS and S. Authenticated reductions among QASs allow the design of a new QAS using no other tools but only what another QAS provides, in a way that preserves correctness and security.
In particular, let S and S′ be data sets, QS : Q → AS , Q′S : Q′ → A′S be query operations on S and S′ respectively, and QAS (QS , S) = (G, Auth, Res, Ver), QAS (Q′S , S′) = (G′, Auth′, Res′, Ver′) be query authentication schemes for QS on S and Q′S on S′ respectively. We say that QAS (QS , S) is authentically reduced to QAS (Q′S , S′), if key generation algorithms G and G′ are identical, QAS (QS , S) uses the public and secret keys generated by G never explicitly, but only implicitly through black-box invocations of algorithms Auth′, Res′ and Ver′, and QAS(QS , S) is correct and secure whenever QAS (Q′S , S′) is correct and secure.
Let S = (E , R) be a structured data set and QS : Q → AS be any query operation. Let D(QS ) = (EQ, RQ, Answer) be a query data structure for QS . By Theorem 1, we know that there exists a certification data structure C(QS ) = ((EC , RC ), Certify, Verify) for S with respect to QS . Let Q∈ : Q(RC ) → {yes, no} be the set membership query operation, where the query space Q(RC ) is the indexed tuples that exist in RC . Assuming the existence of a secure and correct QAS (Q∈, RC ) = (G′, Auth′, Res′, Ver′), we construct QAS (QS , S) = (G, Auth, Res, Ver), a query authentication scheme for QS and S, parameterized by QAS (Q∈, RC ) for set membership queries. Key-generation algorithm. Same as G′, thus, SK = SK ′ and PK = PK ′. Authenticator. The authenticator algorithm Auth computes structured data set SC = (EC , RC ) of the certification structure C(QS ) = ((EC , RC ), Certify, Verify) using S and ConstrC . Then Auth runs algorithm Auth′ on input SK ′, PK ′, Q∈ and RC .
Then, Auth outputs the pair (α′, V′) ← Auth′(SK ′, PK ′, Q∈, RC ).
Responder. The responder algorithm Res first computes the structured data sets SQ = (EQ, RQ) and SC = (EC , RC ) using S and algorithms ConstrQ and ConstrC . Then, on input q, SQ and SC it simply runs algorithm Certify to produce its pair (a, τ ). Then Res constructs the certification support RC (τ ) of answer a by accessing set RC with the use of indices in τ . For every tuple hti in RC , algorithm Res runs the responder algorithm Res′ on inputs hti, RC and V′ to get (a′(t), p′(t)) ← Res′(hti, RC , V′) and, if (t1, . . . , t|τ|) is the sequence of tuples accessed in total, Res creates sequence p′ = (p′(t1), . . . , p′(t|τ|)), sets p = (τ, RC (τ ), p′) and finally outputs (a, p).
Verifier. The verifier algorithm Ver first checks if the proof p and answer a are both well-formed and, if not, it rejects. Otherwise, by appropriately processing the proof p, algorithm Ver runs algorithm Verify on inputs q, RC (τ ), a and τ . Whenever algorithm Verify needs to access and process a tuple htii, where htii is the i-th tuple accessed by Verify, algorithm Ver runs Ver′ on inputs PK ′, htii, (yes, p′(ti)) and α′ and if 0 ← Ver′(PK ′, htii, (yes, p′(ti)), α′), algorithm Ver rejects. Otherwise, Ver continues with the computation. Finally, Ver accepts if and only if Verify accepts.
We have thus constructed QAS (QS , S), where QS is a general query operation of set S, parameterized by QAS (Q∈, RC ), where Q∈ is the set membership query and RC is the certification image of S with respect to the certification data structure in use. Theorem 2. Let QAS (Q∈, RC ) be a correct and secure query authentication scheme for set membership queries. Given any data set S and query operation QS , the query authentication scheme QAS (QS , S) constructed above is correct and secure. Proof. (Sketch.) We start by first discussing the correctness property. Suppose that query authentication scheme (G′, Auth′, Res′, Ver′) is correct. We want to show that scheme (G, Auth, Res, Ver) is correct. This follows from checking that the verifier Ver does not reject when given an answer-proof pair from the responder Res, for any query issued in Q. Indeed, from the completeness property of the certification data structure the answer testing algorithm Verify does not reject, and additionally the correctness of (G′, Auth′, Res′, Ver′) guarantee that Ver does not reject because of a rejection by Ver′. For the security we argue as follows. Suppose that (G′, Auth′, Res′, Ver′) is secure. Assume that (G, Auth, Res, Ver) is not secure, then with non-negligible probability Res responds to a query q ∈ Q incorrectly but still Ver fails to reject its input. Based on the soundness property of the certification data structure in use, we must admit that it is not Certify that cheats the verifier, that is, it is not the indices in sequence τ that cause the problem, but rather the fact that algorithm Verify runs on incorrect data. Then there must exist at least one element verified to be a member of RC that it is not authentic, meaning that its index is correct but one or more of the data elements in the tuple have been (maliciously) altered. We thus conclude that for at least one query the verification algorithm Ver′ of query authentication scheme (G′, Auth′, Res′, Ver′) failed to reject on an invalid query-answer pair, a contradiction. ⊓⊔ Theorem 3. For any query operation QS on any data set S, there exists a secure and correct query authentication scheme QAS (QS , S) based on a certification data structure C(QS ).
Proof. It follows from Theorem 1, Theorem 2 and the fact that there exist secure query authentication schemes for membership queries. ⊓⊔
By Theorem 3, all query operations can be authenticated in the three-party authentication model given a corresponding certification structure, which can be constructed for query problems from the query data structure (Theorem 1). Our results hold for the RAM model of computation, which strictly includes the pointer machine model. Our framework can be further extended to super-efficient verification, as described in the following theorem.
Theorem 4. Let S be a data set and Qs be a query operation on S. If there exists a time (space) super-efficient certification data structure for QS , then there exists a time (space) super-efficient authenticated data structure for QS . 5
We briefly overview applications of our framework. In the bounded computational model, we can achieve storage outsourcing, where the certification image (EC , RC ) of a data set S is stored by an untrusted entity. Consider a certification data structure, where party A (server computations are outsourced to) runs Certify and party B (client data originates from) runs Verify. It is possible for B to store only a cryptographic commitment of (EC , RC ) and still be able to verify its integrity throughout a series of updates on an initially empty set S. We refer to this property as consistency: data source B checks that any update on S, and thus on (EC , RC ), is in accordance with the history of previous updates. The idea is to use cryptographic primitives (e.g., hashing) that provide commitments of sets, subject to which membership can be securely checked. The following result finds applications to cloud storage, where a client (small computational device, B) uses space super-efficient protocols to check the integrity of data stored at an untrusted server (A).
Theorem 5. In the bounded computational model, any certification data structure can be transformed to a consistent client-server data outsourcing scheme with constantspace storage at the client.
This result can be used to extend the construction of Section 4, where the data
source stores the certification image, while the responder stores the data set and the
certification image (parties B and A in our previous discussion). Using Theorem 5, the
data source can outsource the certification image to the responder and still be able to
check the data correctness and consistency, using constant space (similar to [
Finally, applying our results to the peer-to-peer Merkle tree realization [