DEV Community: Ram Nad

C++ Templates and SFINAE

Ram Nad — Wed, 05 Feb 2020 17:42:28 +0000

Recently, I came across a problem while looking for good first issues on GitHub. I would like to share the problem and its solution with you in this post. Just for clarity, we would work with a simpler version of the problem.

Suppose there is a template class Container that takes a class as Backend conforming to a particular interface. This Container acts as a wrapper on the Backend providing it with extra functionalities.

template<typename Backend>
class Container {
    private:
    Backend b;
    int data;
    int data1, data2;

    public:
    Container(int data, int data1, int data2) : data(data), data1(data1), data2(data2) {}

    int get() {
        return b.getValue(data);
    }
};

Now all the Backends need to have the following particular function,

class Backend1 {
    public:
    int getValue(int data);
};

This function is called by a get() function inside our container. The problem is that we need to change this interface to add up new functionalities. So, we now need to call getValue() with 2 parameters, instead of 1. So, our interface should now be:

int getValue(int data1, int data2);

We cannot make this change suddenly, because many users and backends depend upon the old functionality. Therefore, for the backends that support new interface we will call getValue with two parameters else we would call it with one.

We need to somehow statically(that is at compile-time) detect if any backend supports the new interface we use it, else we should stick with older interface.

Now, this is where the magic of C++ templates come to picture.

class SupportedBackend {
    public:
    int getValue(int data1, int data2) {
        return data1 + data2;
    }
};

class UnsupportedBackend {
    public:
    int getValue(int data) {
        return data + 1;
    }
};

So, among above two backends, SupportedBackend supports new interface whereas UnsupportedBackend does not. (I could not come up with any other descriptive name)

Here, is the code that can do the work for us,

#include <type_traits>

template <class T>
class check_new_interface {
  template <class R>
  static auto check(int) -> decltype(std::declval<R>().getValue(0, 0));

  template <class>
  static double check(double);

 public:
  static constexpr bool value = sizeof(decltype(check<T>(0))) == sizeof(int);
};

check_new_interface<T>::value would be true if T supports new interface else it will be false.

Let us now understand the above code.

So, check_new_interface class has two template member functions with same name (but different signatures). Now the value of value depends upon the following expression: sizeof(decltype(check<T>(0))) == sizeof(int). This is where we need to understand a lot of things.

First, sizeof and decltype do not evaluate the expression they are called with. So, the following program would only print 4 (that is sizeof(int)) instead of hello4. (Did you notice that we did not define the check functions although we called it the above expression)

#include <cstdio>

int main() { printf("%lu", sizeof(std::printf("hello"))); }

Second, when C++ sees check<T>(0) expression, it trys to find a proper function declaration that matches this call. There are two options, so template function overload resolution comes into picture. As, 0 is an integer literal, so C++ would first try to associate this call with function that takes integer as its parameter. If it cannot do so it will then check other options. For example,

#include <iostream>

long echo_with_type(double a) {
  std::cout << "double: " << a << std::endl;
  return a;
}

void first_echo(int a) { echo_with_type(a); }

int echo_with_type(int a) {
  std::cout << "int: " << a << std::endl;
  return a;
}

void second_echo(int a) { echo_with_type(a); }

int main() {
  first_echo(2);
  second_echo(2);
  return 0;
}

If, you run the above code, you would find that first output would be double: 2 and second would be int: 2. This is because when first_echo function is called, it does not find any echo_with_type function with integer parameter so it calls the one which takes double as parameter, but second time it finds one with integer and therefore call its.

Similarly, in our situation for check<T>(0) compiler would try to substitute T into the first template before the second one (for similar reasons as above program). Now, this is where the real magic happens. When any type is substituted in place of R, then only if that type has a member function with signature getValue(int, int) the substitution would succeed. Else it will fail. So, in our case when we will substitute SupportedBackend then this substitution would be succeed but in case of UnsupportedBackend it will fail. (Sorry, I am skipping few details here, like what is declval and why we use it but we can get into that sometimes later.)

Now, if C++ did not support SFINAE, then the compiler would have thrown an error here. But luckily it does so we can continue.

SFINAE - Substitution Failure is not an Error

Basically SFINAE means that if a template substitution fails then compiler does not throw error but continues to find a valid template substitution until it succeeds. (If it does not find any then ofcourse it will throw error.)

So, in our case as well compiler continues to find a valid substitution for check<T>(0) [when T = UnsupportedBackend]. Because first template substitution failed, it will move to the second template and succeed. But when it succeeds for the second template then return type of check<T> would be double instead of int. (Where as in case of T = SupportedBackend it would be int)

So, it is clear that the check_new_interface::value would be true in case of SupportedBackend and false in case of UnsupportedBackend.

Now, we may be tempted to implement get() as follows:

int get() {
    if(check_new_interface<Backend>::value) {
        return b.getValue(data1, data2);
    } else {
        return b.getValue(data);
    }
}

But, compiler would give errors if we try to do this. The reason is although compiler knows for any given Backend whether if part will exceute or else part but it needs to generate code for both of them. So, obviously it will fail.

The solution again would be to use function overloading here. std::true_type and std::false_type are specialized types of class template std::integral_constant defined as following:

typedef std::integral_constant<bool, true> true_type;

typedef std::integral_constant<bool, false> false_type;

private:

inline int get(std::false_type) { return b.getValue(data); }

inline int get(std::true_type) { return b.getValue(data1, data2); }

public:

int get() {
return get(
    std::integral_constant<bool, check_new_interface<Backend>::value>());
}

Now, this would work flawlessly because, when compiler generates code for get() function then, it only needs to compile one of get(std::false_type) or get(std::true_type) depending upon the value of check_new_interface<Backend>::value.

So, finally we have our solution ready. You can find the complete code here.

I hope that you got to learn something new in this post. Thanks for reading.

JSON Web Tokens (Part 1)

Ram Nad — Tue, 04 Feb 2020 10:01:54 +0000

JSON Web Token (JWT) is an open standard (RFC 7519) that defines a compact and self-contained way for securely transmitting information between parties as a JSON object. This information can be verified and trusted because it is digitally signed. JWTs can be signed using a secret (with the HMAC algorithm) or a public/private key pair using RSA or ECDSA.

In this post I would like to explain how can we use JWTs for authentication in web applications. In the next part, we will be using NodeJS, Express and jsonwebtoken library for implementing a simple JWT based authentication. Note that, we would use the word system and server interchangeably.

So, a JWT looks typically like this:

Image Source: jwt.io

So, this token can be broken down into 3 parts each separted by a .(dot)

Header (Red colour)
Payload (Pink colour)
Signature (Light Blue colour)

The header and payload sections are just normal JSON strings that is encoded in base64. Now, there is a difference between encoding and encryption. Encryption is when you use a secret key to transform message into a cipher which can only be transformed back to original message if you have the key. But in encoding, we just transform the message into a format that is easy to transfer between computers. Anyone with an encoded message can transform it back and read its content(there is no key involved).

If you use a base64 decoder for decoding the header or payload section here is what you get,

{ "alg": "HS256", "typ": "JWT" }

{ "sub": "1234567890", "name": "John Doe", "iat": 1516239022 }

Third and final part, signature is also base64 encoded but if you try to decode it, you would get a gibberish text.

Header

Header section contains some information about the nature of this token. For example, in the particular token above, typ contains information about the type of this token(which is JWT) and alg says that the algorithm used to sign this token that is HMCASHA256.

Note: We will explain what does sign means later in this post. But for now you can take the analogy of signature that people do on documents to say that I have verified it and I approve of it.

Payload

Payload section contains of a set of claims that a party makes with this token. So, the contents of payload section says when, where, why and by whom this token can be used. Again continuing with the example given, sub stands for subject and it contains information about whom is this token concerned with, name is evidently name of the person and iat means issued at, It is Unix timestamp of the moment when this token was issued.

Side Note: Unix Timestamp is number of seconds that has passed since January 1, 1970. considering that every day has 86400 seconds. Also since this is calculated relative to UTC, it is same for all computers around the world.

Side Note: You will come across names John Doe quite frequently if you read posts like this. This is the frequently used name to refer to a male whose name is not known or is being concealed. Jane Doe is used for females.

Now there are certain standard claims that is specified in RC 7519 for a particular purpose:

iss (issuer): Issuer of the JWT
sub (subject): Subject of the JWT (the user)
aud (audience): Recipient for which the JWT is intended
exp (expiration time): Time after which the JWT expires
nbf (not before time): Time before which the JWT must not be accepted for processing
iat (issued at time): Time at which the JWT was issued; can be used to determine age of the JWT
jti (JWT ID): Unique identifier; can be used to prevent the JWT from being replayed (allows a token to be used only once)

Now before we get to the third and most important part of JWTs, let us first consider a scenerio where JWT is used for user authentication.

Consider how user's are authenticated normally(that is without the use of tokens). So, when user logs in for the first time, he gives an username and password. The system checks if username and password is correct. If it matches with the database records, then systems creates a random string (called session identifier), stores it in the database along with user's identification and sends the identifier back to the user.(It is usually send as a cookie, but that does not matter for our disscussion)

Next time when user visits the website, he sends this identifier along with the request. When system recieves this identifier, it matches that with information in the database. If the identifier matches, then the system knows that user is genuine. To log out a user, system simply deletes this identifier from the database.

Image Source: Medium

Now why does the system believes in this identifier? The reason is that this identifier is usually a long and random string. So, it is not possible for anyone to know it. Also if someone tries to randomly generate all the possible tokens, it might take him 10¹⁸ billion years to test every combination.(Assuming that identifier is 128 bits long and it takes 1 second for testing 10,000 strings) For reference, current age of universe is 13.8 billion years.

There are few problem with this session based approach though. First one which is that for every request the system needs to hit database to check if session identiifer is valid. (This is problematic because database access takes time) Other similar but related problem is with microservice architecture. In this case, identifiers need to be stored in a central server, because different servers need to access this information.(Therefore, this would take even more time and is much more difficult to manage) Both of this problems can be solved with the help of the JWTs.

So in the case of JWTs, when user first logs in the system generates one of this tokens and send it to the user. The claims that system usually put in this token is sub to identify the user and other details like the user's privilege level. So, when user makes a request to the server, then system checks if the token is well formed JWT and just by decoding the payload section it can verify the user which this token identifies.

Image Source: Medium

Now, the only problem is anyone can generate this token. (Remember that header and payload are just encoded) So, anyone in this world can generate a token containing anyone else's identification and send it to the server. The system would then not be able to distinguish wether the token came from the right person or someone else. This is the place where the signature comes into picture.

Signature

Signature is used to verify that this token (JWT) is issued only by the server and no one else could generate it.

The idea is very simple. Each system has a long and unique secret key with itself. This key cannot be guessed by anyone else. (Because of similar reasons of session identifier) When the system generates a token it then sends it through a Message Authentication Code Algorithm(HMACSHA256 is one of them. There are many others) along with the secret key. Now this algorithm gives a pattern of bits as its result. This bit pattern is then encoded into base64 format to form the signature.

The bit pattern(which we will call signature from now) given out by the algorithm is not random but it has two important properties.

Given the signature, one cannot guess the value of secret key or the contents of the message.(This is to say that the algorithm computes a one-way function)
Second if we change the contents of message or the secret key even slightly the signature would change completely.

This two properties make sure that only way to guess the correct signature for any given message is to randomly try all possible combination. (Which would again take 10¹⁸ billion years) Therefore it is highly unlikely that anyone would be able to do it.

Note: Scientists say that sun would burn out within 4-5 billion years from now.

Now, when someone sends this token back to the server, it just generates the signature again using the same key and algorithm. If the resulting signature matches with the signature that came with the token, then server can be pretty sure that this is a valid token.

Note: For this particular HMACSHA256 algorithm the signature is 256 bits long. If you want a rough idea of how unlikely it is to guess a signature watch this 3Blue1Brown video.

I hope that you have an idea of how JWT is used. I feel that this post is getting a bit long. So, we will continue with how to implement JWT using NodeJS in next part of this post.

You can verify the example signature using jwt.io. Just enter the header and payload given above. The secret I used is hello.

References: