How to check if client's contacts are using my app?

I'm currently developing an app using Firebase.

My Firestore Database looks like below:

Once the user passes the Firebase authentication procedure, I'm creating a user document with a field "Phone:" which contains his phone number. Basically, everyone who is gonna using the app will be listed in the database.

And here is my challenge:

I'm using the plugin easy_contact_picker to store all the contacts of the users device to a List.

How can I find out whether the users contacts are using the app or whether they are listed in the database?

My goal is create a contact List Widget which shows me all my contacts. But those contacts which are using the app or which are listed in the database, should be highlighted or marked particularly.

Which is the best way to realize that if we consider that millions of users (to minimize computing power)are listed in the database?

Anyone has an idea?

Thanks a lot

With the help of Tarik's answer, Ayrix and I came up with the following solution.

Important: Read Tarik's answer for more information.

Client: callable_compare_contacts.dart

import 'package:cloud_functions/cloud_functions.dart';

Future<List<Object>> getMembersByPhoneNumber(List<String> allPhoneNumbers) async {
  HttpsCallable callable = FirebaseFunctions.instance.httpsCallable('membersByPhoneNumber');
  final results = await callable.call(<String, dynamic>{'allPhoneNumbers': allPhoneNumbers});

  return results.data;
}

Server: index.js

const functions = require("firebase-functions");
const admin = require("firebase-admin");
if (admin.apps.length === 0) {
  admin.initializeApp({
    credential: admin.credential.applicationDefault(),
  });
}

exports.membersByPhoneNumber = functions.https.onCall((data, context) => {
  return new Promise((resolve, reject) => {
    if (!data || !data.allPhoneNumbers.length) return resolve([]);
    const phoneNumbers = data.allPhoneNumbers;
    // TODO: different scope? move vars for future use
    const db = admin.firestore();
    const collectionRef = db.collection("User");

    let batches = [];
    // because of wrong eslint parsing (dirty)
    batches = [];
    while (phoneNumbers.length) {
      // firestore limits batches to 10
      const batch = phoneNumbers.splice(0, 10);
      // add the batch request to to a queue
      batches.push(
          new Promise((response) => {
            collectionRef.where("Phone", "in", [...batch]).get()
                .then((results) =>
                  response(results.docs.map(function(result) {
                    return result.data().Phone;
                  } )));
          })
      );
    }
    // response / return to client
    Promise.all(batches).then(function(content) {
      // console.log("content.flat()");
      // console.log(content.flat());
      return resolve(content.flat());
    });
  });
});

Note: This is our first callable/cloud function .. so Suggestions for changes are welcome.