The actual problem is discussed in the May, 23rd release note of https://developers.google.com/android/guides/releases#may_23_2018
Basically, you need to bump all Play Services and Firebase libraries to their latest version (which may be different for each since version 15).
You may use https://mvnrepository.com/ to find the latest version for each library.
See also: https://firebase.google.com/support/release-notes/android#20180523