Methods and systems allow for the deployment of private (i.e., not necessarily publicly available) and reversible (or replaceable) smart contracts to create the stateless blockchain overlay layer. For example, the stateless blockchain overlay layer allows developers to deploy private smart contracts as overlays on top of any existing blockchain. The deployment of these private smart contracts is instantaneous, reversible, and free. Furthermore, the private smart contracts may be called at any block, including past ones. The private smart contracts may be used to expose arbitrary blockchain-based computation at arbitrary block heights to their developers.