Blockchain blocks are provided with either or both of two element types that enable later verification of block validity. One element type is identifiers, such as signatures, of trusted validators that approve entry of the block into the blockchain. Another element is a history hash tree that encodes data from not only the current block, but also at least one previous block.