  Auditability is crucial for data outsourcing, facilitating accountability and
identifying data loss or corruption incidents in a timely manner, reducing in
turn the risks from such losses. In recent years, in synch with the growing
trend of outsourcing, a lot of progress has been made in designing
probabilistic (for efficiency) provable data possession (PDP) schemes. However,
even the recent and advanced PDP solutions that do deal with dynamic data, do
so in a limited manner, and for only the latest version of the data. A naive
solution treating different versions in isolation would work, but leads to
tremendous overheads, and is undesirable. In this paper, we present algorithms
to achieve full persistence (all intermediate configurations are preserved and
are modifiable) for an optimized skip list (known as FlexList) so that
versioned data can be audited. The proposed scheme provides deduplication at
the level of logical, variable sized blocks, such that only the altered parts
of the different versions are kept, while the persistent data-structure
facilitates access (read) of any arbitrary version with the same storage and
process efficiency that state-of-the-art dynamic PDP solutions provide for only
the current version, while commit (write) operations incur around 5% additional
time. Furthermore, the time overhead for auditing arbitrary versions in
addition to the latest version is imperceptible even on a low-end server...
