The first half is a bit easier - if you can show some implementation meets the specification it is at least consistent.
The second isn't so clear, but sometimes you can get a bit more confidence by showing that other good properties are implied by the specification alone.
Unfortunately, this is not enough. You need a consistent and complete specification, too.