Firebase Google Auth: The supplied auth credential is malformed or has expired

I attempted to setup Google Auth using Firebase but got:

{
  "code": "auth/invalid-credential",
  "message": "The supplied auth credential is malformed or has expired."
}

In the network tab, I notice

{
  "error": {
    "code": 400,
    "message": "INVALID_IDP_RESPONSE : Error getting access token from google.com, OAuth2 redirect uri is: https://....firebaseapp.com/__/auth/handler, response: OAuth2TokenResponse{params: error=invalid_client&error_description=Unauthorized, httpMetadata: HttpMetadata{status=401, cachePolicy=NO_CACHE, cacheDuration=null, cacheImmutable=false, staleWhileRevalidate=null, filename=null, lastModified=null, headers=HTTP/1.1 200 OK\r\n\r\n, contentSecurityPolicies=[], cookieList=[]}}",
    "errors": [
      {
        "message": "INVALID_IDP_RESPONSE : Error getting access token from google.com, OAuth2 redirect uri is: https://....firebaseapp.com/__/auth/handler, response: OAuth2TokenResponse{params: error=invalid_client&error_description=Unauthorized, httpMetadata: HttpMetadata{status=401, cachePolicy=NO_CACHE, cacheDuration=null, cacheImmutable=false, staleWhileRevalidate=null, filename=null, lastModified=null, headers=HTTP/1.1 200 OK\r\n\r\n, contentSecurityPolicies=[], cookieList=[]}}",
        "domain": "global",
        "reason": "invalid"
      }
    ]
  }
}

I am testing on localhost at the moment, how can I make this work? Under authorized domains, I already see localhost. Whats wrong?