Implementations efficiently verify an identity claim for an entity. An example method includes receiving a query key and a property identifying an entity and identifying a possible match for the property from graph access records, the possible match being a node in an identity chain. The method also includes verifying a complete chain from the possible match to a genesis node in the chain. The query key is used to find a next node in the chain. Failure to identify the genesis node results in an unsuccessful verification. The method also includes generating a response that indicates a successful verification request responsive to locating the genesis node and generating a response that indicates an unsuccessful verification request otherwise.