Note: we can recover the publicKey from a signature when using secp256k1. So we don't need to keep publicKeys around.