If our interest is an append-only database, then each operation can be described as adding entry
E = F(U, Q)
to the database, where U is user data, Q is result of query on the current state of the database, and F is a function which transforms U and Q into what we want to add.
In this case commitment to E can be replaced to commitment to pair (U, Q). So a commitment to database state can be
replaced with a commitment to a transaction log, where client creates transactions in the following way:
- client sends a query to a database and retries result Q which is relevant to his transaction
- he adds hash of Q (or Q in its entirety if it is small) to his transaction T which includes operation data U
- Transaction T which is added to the transaction log
A proof that entry E was added to the database should consist of:
- U
- Q
- Merkle tree proof that T containing U and Q is contained in transaction log T