Migrating applications with strong consistency requirements to public cloud platforms remains risky since the data owner cannot verify the correctness of the public cloud's locking algorithm. In this paper, we identify new attacks that an untrusted cloud provider can launch via control of the locking mechanism, and propose an extension to existing locking scheme to address such attacks. Our solution modifies the locks to include a short history to allow \textit{data users} to determine correctness, and can also prevent the cloud from re-ordering operations for financial gain.