Analysis of the probabalistic filters usage for authentication tokens invalidation in distributed systems

Abstract

The article investigates the problem of centralized user authentication in complex distributed systems using cryptographic tokens based on JWT (JSON Web Token). Such systems allow decreasing request processing times comparable with conventional centralized authentication systems by allowing offline token verification. However, this creates problems with revoking of compromised or blocked tokens. The traditional approach used in such protocols as OAuth2, shifts this problem to the client side, complicating the client side and making the API more difficult to use. The article discusses the use of an approach that allows developers to keep all costs on the validation token validation on the server side without making significant changes to the system by blocklists. It is suggested to use probabilistic filters to transmit updates about blocked tokens. Such filters at the cost of losing some precision in checking if the entry belongs to the set of elements, using significantly less memory than would be necessary to store all the elements of the set. They are usually used to avoid slow operations such as disk or network access. As a result, it significantly reduces the memory usage on the services end and decreases the traffic volumes between the system components. The criteria for evaluating the performance of probabilistic filters were discussed for the task of periodically updating the lists of blocked identifiers of access tokens. Also various implementations of probabilistic filters were analyzed according to criteria. At the end recommendations for the application of specific probabilistic filters implementations and their parameters for distributed systems of various sizes are provided.