While RRSIG records prove the authenticity of a DNS record that exists, there also needs to be a method to authenticate the non-existence of a given record. In other words, we need to be able to sign NXDOMAIN responses.
The initial implementation of this used the NSEC record (Next SECure):
The records in the zone are sorted into canonical order and an NSEC record is computed for each one.
The format of the NSEC RR is:
<OWNER-NAME> TTL IN NSEC <NEXT-LABEL> <RR-TYPES>
Given a bar.example.dom record with the SRV, TXT, MX and NS RRs, and the next record in the zone being foo.example.dom, the resultant accompanying NSEC record would be:
bar.example.dom. 3600 IN NSEC foo.example.dom. NS SRV TXT MX RRSIG NSEC
A bar.example.dom query for ...