A system and methods for providing guarantees about faithful execution of databases that run under the control of an untrusted entity—such as a cloud computing service provider—that is different than the owner of the data and applications being outsourced; or runs on a server that may be compromised by unauthorized users. Specifically, the system and methods establishes that an untrusted database is being faithfully hosted and provides indemnity for the service provider from false claims, enabling the server to prove its innocence against untrue claims of faulty operation. The invention also provides assured provenance for all changes made to the database.