We study the problem of implementing a replicated data store with atomic semantics for non self-verifying data in a system of $n$ servers that are subject to Byzantine failures. We present a solution that significantly improves over previously proposed solutions. Timestamps used by our solution cannot be forced to grow arbitrarily large by faulty servers as in the case for other solutions. Instead, timestamps grow logarithmically in the number of operations. We achieve this saving by defining and providing an implementation for non-skipping timestamps, which are guaranteed not to skip any value. Non-skipping timestamps allow us to reduce the space requirements for readers to $O(max|Q|)$, which is a significant improvement over the best previously known solution which requires $O(fn)$ space, where $f$ is the maximum number of faulty servers in the system. The solution we present can have a low write-load if $f$ is small compared to $n$, whereas the previously proposed solution always has a high constant write-load.