Recently we presented a single-party cryptographic timestamping mechanism based on proof-of-sequential-work, which we proved secure in the universal composability framework [16]. This paper describes this construction and its security claims and uses it to construct a multi-party permissioned blockchain protocol and show that it achieves an immutability notion. Finally we discuss applications of this protocol, including unpermissioned blockchains, and how these may benefit.