Blockchain technologies have received a considerable amount of attention, and immutability is essential property of blockchain which is paramount to applications such as cryptocurrency. However, “Right to be Fogotten" has been imposed in new European Union's General Data Protection Regulation, making legally impossible to use immutalbe blockchains. Moveover, illicit data stored in immutable blockchain poses numerous challenge for law enforcement agencies such as Interpol. Therefore, it is imperative (even legally required) to design efficient redactable blockchain protocols in a controlled way. In this paper, we present a redactable proof-of-stake blockchain protocol in the permissionless setting with fast confirmation. Our protocol uses a novel mechanism based on verifiable random functions to randomly select voters on different slots in a private and non-interactive way, and also offers public verifiability for redactable chains. Compared to previous solutions in permissionless setting, our redaction operation can be performed quickly, even only within one block in synchronous network, which is desirable for redacting harmful or sensitive data. Moreover, our protocol is compatible with current proof-of-stake blockchains requiring only minimal changes. Furthermore, we prove that our protocol can achieve the security property of redactable common prefix, chain quality, and chain growth. Finally, we implement our protocol and provide experimental results showing that compared to immutable blockchain, the overhead incurred for different numbers of redactions in the chain is minimal.