Android 4.4 and later supports verified boot through the optional device-mapper-verity (dm-verity) kernel feature, which provides transparent integrity checking of block devices. dm-verity helps prevent persistent rootkits that can hold onto root privileges and compromise devices. This feature helps Android users be sure when booting a device it is in the same state as when it was last used.
Clever malware with root privileges can hide from detection programs and otherwise mask themselves. The rooting software can do this because it is often more privileged than the detectors, enabling the software to "lie" to the detection programs.
The dm-verity feature lets you look at a block device, the underlying storage layer of the file system, and determine if it matches its expected configuration. It does this using a cryptographic hash tree. For every block (typically 4k), there is a SHA256 hash.
Because the hash values are stored in a tree of pages, only the top-level "root" hash must be trusted to verify the rest of the tree. The ability to modify any of the blocks would be equivalent to breaking the cryptographic hash. See the following diagram for a depiction of this structure.
A public key is included on the boot partition, which must be verified externally by the OEM. That key is used to verify the signature for that hash and confirm the device's system partition is protected and unchanged.
Establishing a verified boot flow
To greatly reduce the risk of compromise, verify the kernel using a key burned into the device. For details, see Verifying boot.
Switching to block-oriented OTAs
To enable dm-verity for a device, you must use block-based over-the-air (OTA) updates to ensure all devices use the same system partition. For details, see Block-Based OTAs.
After switching to block-oriented OTAs, incorporate the latest Android kernel
or use a stock upstream kernel and enable dm-verity support by including the
relevant configuration option
When using the Android kernel, dm-verity is turned on when the kernel is built. For details, see Implementing dm-verity.
cryptsetup - dm-verity: device-mapper block integrity checking target
The Chromium Projects - Verified Boot
Linux Kernel Documentation: verity.txt