--- a/toolkit/components/url-classifier/nsIUrlClassifierHashCompleter.idl
+++ b/toolkit/components/url-classifier/nsIUrlClassifierHashCompleter.idl
@@ -51,15 +51,18 @@ interface nsIUrlClassifierHashCompleter 
 {
   /**
    * Request a completed hash from the given gethash url.
    *
    * @param partialHash
    *        The 32-bit hash encountered by the url-classifier.
    * @param gethashUrl
    *        The gethash url to use.
+   * @param tableName
+   *        The table where we matched the partial hash.
    * @param callback
    *        An nsIUrlClassifierCompleterCallback instance.
    */
   void complete(in ACString partialHash,
                 in ACString gethashUrl,
+                in ACString tableName,
                 in nsIUrlClassifierHashCompleterCallback callback);
 };

--- a/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierDBService.cpp
@@ -928,17 +928,20 @@ nsUrlClassifierLookupCallback::LookupCom
       if ((!gethashUrl.IsEmpty() ||
            StringBeginsWith(result.mTableName, NS_LITERAL_CSTRING("test-"))) &&
           mDBService->GetCompleter(result.mTableName,
                                    getter_AddRefs(completer))) {
         nsAutoCString partialHash;
         partialHash.Assign(reinterpret_cast<char*>(&result.hash.prefix),
                            PREFIX_SIZE);
 
-        nsresult rv = completer->Complete(partialHash, gethashUrl, this);
+        nsresult rv = completer->Complete(partialHash,
+                                          gethashUrl,
+                                          result.mTableName,
+                                          this);
         if (NS_SUCCEEDED(rv)) {
           mPendingCompletions++;
         }
       } else {
         // For tables with no hash completer, a complete hash match is
         // good enough, we'll consider it fresh, even if it hasn't been updated
         // in 45 minutes.
         if (result.Complete()) {

--- a/toolkit/components/url-classifier/nsUrlClassifierHashCompleter.js
+++ b/toolkit/components/url-classifier/nsUrlClassifierHashCompleter.js
@@ -12,16 +12,19 @@ const Cu = Components.utils;
 // hash.
 const COMPLETE_LENGTH = 32;
 const PARTIAL_LENGTH = 4;
 
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/NetUtil.jsm");
 
+XPCOMUtils.defineLazyServiceGetter(this, 'gDbService',
+                                   '@mozilla.org/url-classifier/dbservice;1',
+                                   'nsIUrlClassifierDBService');
 
 // Log only if browser.safebrowsing.debug is true
 function log(...stuff) {
   let logging = null;
   try {
     logging = Services.prefs.getBoolPref("browser.safebrowsing.debug");
   } catch(e) {
     return;
@@ -168,32 +171,32 @@ HashCompleter.prototype = {
                                          Ci.nsIObserver,
                                          Ci.nsISupportsWeakReference,
                                          Ci.nsITimerCallback,
                                          Ci.nsISupports]),
 
   // This is mainly how the HashCompleter interacts with other components.
   // Even though it only takes one partial hash and callback, subsequent
   // calls are made into the same HTTP request by using a thread dispatch.
-  complete: function HC_complete(aPartialHash, aGethashUrl, aCallback) {
+  complete: function HC_complete(aPartialHash, aGethashUrl, aTableName, aCallback) {
     if (!aGethashUrl) {
       throw Cr.NS_ERROR_NOT_INITIALIZED;
     }
 
     if (!this._currentRequest) {
       this._currentRequest = new HashCompleterRequest(this, aGethashUrl);
     }
     if (this._currentRequest.gethashUrl == aGethashUrl) {
-      this._currentRequest.add(aPartialHash, aCallback);
+      this._currentRequest.add(aPartialHash, aCallback, aTableName);
     } else {
       if (!this._pendingRequests[aGethashUrl]) {
         this._pendingRequests[aGethashUrl] =
           new HashCompleterRequest(this, aGethashUrl);
       }
-      this._pendingRequests[aGethashUrl].add(aPartialHash, aCallback);
+      this._pendingRequests[aGethashUrl].add(aPartialHash, aCallback, aTableName);
     }
 
     if (!this._backoffs[aGethashUrl]) {
       // Initialize request backoffs separately, since requests are deleted
       // after they are dispatched.
       var jslib = Cc["@mozilla.org/url-classifier/jslib;1"]
                   .getService().wrappedJSObject;
 
@@ -272,55 +275,104 @@ function HashCompleterRequest(aCompleter
   this._requests = [];
   // nsIChannel that the hash completion query is transmitted over.
   this._channel = null;
   // Response body of hash completion. Created in onDataAvailable.
   this._response = "";
   // Whether we have been informed of a shutdown by the xpcom-shutdown event.
   this._shuttingDown = false;
   this.gethashUrl = aGethashUrl;
+
+  // Multiple partial hashes can be associated with the same tables
+  // so we use a set here.
+  //
+  // Question: is empty table name possible?
+  this.tableNames = new Map();
 }
 HashCompleterRequest.prototype = {
   QueryInterface: XPCOMUtils.generateQI([Ci.nsIRequestObserver,
                                          Ci.nsIStreamListener,
                                          Ci.nsIObserver,
                                          Ci.nsISupports]),
 
   // This is called by the HashCompleter to add a hash and callback to the
   // HashCompleterRequest. It must be called before calling |begin|.
-  add: function HCR_add(aPartialHash, aCallback) {
+  add: function HCR_add(aPartialHash, aCallback, aTableName) {
     this._requests.push({
       partialHash: aPartialHash,
       callback: aCallback,
       responses: []
     });
+
+    if (aTableName) {
+      this.tableNames.set(aTableName);
+      let isTableNameV4 = aTableName.endsWith('-proto');
+      if (1 === this.tableNames.size) {
+        // Decide if this request is v4 by the first added partial hash.
+        this.isV4 = isTableNameV4;
+      } else if (this.isV4 !== isTableNameV4) {
+        log('ERROR: Cannot mix "proto" tables with other types within ' +
+            'the smae gethash URL.');
+      }
+    }
+  },
+
+  fillTableStatesBase64: function HCR_fillTableStatesBase64(aCallback) {
+    if (!this.isV4) {
+      return aCallback(); // No-op to save a disk access.
+    }
+
+    gDbService.getTables(aTableData => {
+      aTableData.split("\n").forEach(line => {
+        let p = line.indexOf(";");
+        if (-1 === p) {
+          return;
+        }
+        // [tableName];[stateBase64]:[checksumBase64]
+        let tableName = line.substring(0, p);
+        if (this.tableNames.has(tableName)) {
+          let metadata = line.substring(p + 1).split(":");
+          let stateBase64 = metadata[0];
+          this.tableNames.set(tableName, stateBase64);
+        }
+      });
+
+      aCallback();
+    });
+
   },
 
   // This initiates the HTTP request. It can fail due to backoff timings and
   // will notify all callbacks as necessary. We notify the backoff object on
   // begin.
   begin: function HCR_begin() {
     if (!this._completer.canMakeRequest(this.gethashUrl)) {
       log("Can't make request to " + this.gethashUrl + "\n");
       this.notifyFailure(Cr.NS_ERROR_ABORT);
       return;
     }
 
     Services.obs.addObserver(this, "xpcom-shutdown", false);
 
-    try {
-      this.openChannel();
-      // Notify the RequestBackoff if opening the channel succeeded. At this
-      // point, finishRequest must be called.
-      this._completer.noteRequest(this.gethashUrl);
-    }
-    catch (err) {
-      this.notifyFailure(err);
-      throw err;
-    }
+    // V4 requires table states to build the request so we need
+    // a async call to retrieve the table states from disk.
+    // Note that |HCR_begin| is fine to be sync because
+    // it is not appeared in a sync call chain.
+    this.fillTableStatesBase64(() => {
+      try {
+        this.openChannel();
+        // Notify the RequestBackoff if opening the channel succeeded. At this
+        // point, finishRequest must be called.
+        this._completer.noteRequest(this.gethashUrl);
+      }
+      catch (err) {
+        this.notifyFailure(err);
+        throw err;
+      }
+    });
   },
 
   notify: function HCR_notify() {
     // If we haven't gotten onStopRequest, just cancel. This will call us
     // with onStopRequest since we implement nsIStreamListener on the
     // channel.
     if (this._channel && this._channel.isPending()) {
       log("cancelling request to " + this.gethashUrl + "\n");
@@ -329,30 +381,50 @@ HashCompleterRequest.prototype = {
     }
   },
 
   // Creates an nsIChannel for the request and fills the body.
   openChannel: function HCR_openChannel() {
     let loadFlags = Ci.nsIChannel.INHIBIT_CACHING |
                     Ci.nsIChannel.LOAD_BYPASS_CACHE;
 
+    let actualGethashUrl = this.gethashUrl;
+    if (this.isV4) {
+      // TODO: (Bug 1276826)
+      // 1) Build request for V4 by this.tableNames, this._requests.
+      // 2) Annotate the request to actualGethashUrl as the query string.
+
+      // We temporarily annotate |this.tableNames| so we can check
+      // if things go correctly in the test case.
+      // Note that the spread operator here is required to stringify the
+      // Map object...
+      actualGethashUrl += "&$req=" + JSON.stringify(...this.tableNames);
+    }
+
+    log("actualGethashUrl: " + actualGethashUrl);
+
     let channel = NetUtil.newChannel({
-      uri: this.gethashUrl,
+      uri: actualGethashUrl,
       loadUsingSystemPrincipal: true
     });
     channel.loadFlags = loadFlags;
 
     // Disable keepalive.
     let httpChannel = channel.QueryInterface(Ci.nsIHttpChannel);
     httpChannel.setRequestHeader("Connection", "close", false);
 
     this._channel = channel;
 
-    let body = this.buildRequest();
-    this.addRequestBody(body);
+    if (this.isV4) {
+      // TODO (Bug 1276826): Deal with v4 specific HTTP headers.
+      // e.g. "X-HTTP-Method-Override".
+    } else {
+      let body = this.buildRequest();
+      this.addRequestBody(body);
+    }
 
     // Set a timer that cancels the channel after timeout_ms in case we
     // don't get a gethash response.
     this.timer_ = Cc["@mozilla.org/timer;1"].createInstance(Ci.nsITimer);
     // Ask the timer to use nsITimerCallback (.notify()) when ready
     let timeout = Services.prefs.getIntPref(
       "urlclassifier.gethash.timeout_ms");
     this.timer_.initWithCallback(this, timeout, this.timer_.TYPE_ONE_SHOT);
@@ -408,16 +480,22 @@ HashCompleterRequest.prototype = {
   // Parses the response body and eventually adds items to the |responses| array
   // for elements of |this._requests|.
   handleResponse: function HCR_handleResponse() {
     if (this._response == "") {
       return;
     }
 
     log('Response: ' + this._response);
+
+    if (this.isV4) {
+      log("V4 is not supported yet.");
+      return;
+    }
+
     let start = 0;
 
     let length = this._response.length;
     while (start != length) {
       start = this.handleTable(start);
     }
   },
 
@@ -527,16 +605,17 @@ HashCompleterRequest.prototype = {
       httpStatus = channel.responseStatus;
       if (!success) {
         aStatusCode = Cr.NS_ERROR_ABORT;
       }
     }
     let success = Components.isSuccessCode(aStatusCode);
     log('Received a ' + httpStatus + ' status code from the gethash server (success=' + success + ').');
 
+
     let histogram =
       Services.telemetry.getHistogramById("URLCLASSIFIER_COMPLETE_REMOTE_STATUS");
     histogram.add(httpStatusToBucket(httpStatus));
     Services.telemetry.getHistogramById("URLCLASSIFIER_COMPLETE_TIMEOUT").add(0);
 
     // Notify the RequestBackoff once a response is received.
     this._completer.finishRequest(this.gethashUrl, httpStatus);
 

--- a/toolkit/components/url-classifier/tests/unit/head_urlclassifier.js
+++ b/toolkit/components/url-classifier/tests/unit/head_urlclassifier.js
@@ -422,9 +422,49 @@ LFSRgenerator.prototype = {
     let bit = ((val >>> 0) ^ (val >>> 10) ^ (val >>> 30) ^ (val >>> 31)) & 1;
     val = (val >>> 1) | (bit << 31);
     this._value = val;
 
     return (val >>> (32 - bits));
   },
 };
 
+function waitUntilMetaDataSaved(expectedState, expectedChecksum, callback) {
+  let dbService = Cc["@mozilla.org/url-classifier/dbservice;1"]
+                     .getService(Ci.nsIUrlClassifierDBService);
+
+  dbService.getTables(metaData => {
+    do_print("metadata: " + metaData);
+    let didCallback = false;
+    metaData.split("\n").some(line => {
+      // Parse [tableName];[stateBase64]
+      let p = line.indexOf(";");
+      if (-1 === p) {
+        return false; // continue.
+      }
+      let tableName = line.substring(0, p);
+      let metadata = line.substring(p + 1).split(":");
+      let stateBase64 = metadata[0];
+      let checksumBase64 = metadata[1];
+
+      if (tableName !== 'test-phish-proto') {
+        return false; // continue.
+      }
+
+      if (stateBase64 === btoa(expectedState) &&
+          checksumBase64 === btoa(expectedChecksum)) {
+        do_print('State has been saved to disk!');
+        callback();
+        didCallback = true;
+      }
+
+      return true; // break no matter whether the state is matching.
+    });
+
+    if (!didCallback) {
+      do_timeout(1000, waitUntilMetaDataSaved.bind(null, expectedState,
+                                                         expectedChecksum,
+                                                         callback));
+    }
+  });
+}
+
 cleanUp();

new file mode 100644
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/unit/test_hashcompleter_v4.js
@@ -0,0 +1,113 @@
+Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+Cu.import("resource://gre/modules/Services.jsm");
+
+// These tables have a different update URL (for v4).
+const TEST_TABLE_DATA_V4 = {
+  tableName: "test-phish-proto",
+  providerName: "google4",
+  updateUrl: "http://localhost:5555/safebrowsing/update?",
+  gethashUrl: "http://localhost:5555/safebrowsing/gethash-v4?",
+};
+
+const PREF_NEXTUPDATETIME_V4 = "browser.safebrowsing.provider.google4.nextupdatetime";
+
+let gListManager = Cc["@mozilla.org/url-classifier/listmanager;1"]
+                     .getService(Ci.nsIUrlListManager);
+
+let gCompleter = Cc["@mozilla.org/url-classifier/hashcompleter;1"]
+                    .getService(Ci.nsIUrlClassifierHashCompleter);
+
+// Handles request for TEST_TABLE_DATA_V4.
+let gHttpServV4 = null;
+let gExpectedGetHashQueryV4 = "";
+
+const NEW_CLIENT_STATE = 'sta\0te';
+const CHECKSUM = '\x30\x67\xc7\x2c\x5e\x50\x1c\x31\xe3\xfe\xca\x73\xf0\x47\xdc\x34\x1a\x95\x63\x99\xec\x70\x5e\x0a\xee\x9e\xfb\x17\xa1\x55\x35\x78';
+
+prefBranch.setBoolPref("browser.safebrowsing.debug", true);
+
+// The "\xFF\xFF" is to generate a base64 string with "/".
+prefBranch.setCharPref("browser.safebrowsing.id", "Firefox\xFF\xFF");
+
+// Register tables.
+gListManager.registerTable(TEST_TABLE_DATA_V4.tableName,
+                           TEST_TABLE_DATA_V4.providerName,
+                           TEST_TABLE_DATA_V4.updateUrl,
+                           TEST_TABLE_DATA_V4.gethashUrl);
+
+// This is unfortunately needed since v4 gethash request
+// requires the threat type (table name) as well as the
+// state it associated with. We have to run the update once
+// to have the state written.
+add_test(function test_update_v4() {
+  gListManager.disableUpdate(TEST_TABLE_DATA_V4.tableName);
+  gListManager.enableUpdate(TEST_TABLE_DATA_V4.tableName);
+
+  // Force table update.
+  prefBranch.setCharPref(PREF_NEXTUPDATETIME_V4, "1");
+  gListManager.maybeToggleUpdateChecking();
+});
+
+add_test(function test_getHashRequestV4() {
+  // TODO: Bug 1276826 to replace with the actual protobuf data.
+  gExpectedGetHashQueryV4 = '&$req=[%22test-phish-proto%22,%22c3RhAHRl%22]';
+
+  gCompleter.complete("", TEST_TABLE_DATA_V4.gethashUrl, TEST_TABLE_DATA_V4.tableName, {
+    completion: function (hash, table, chunkId) {
+      ok(false); // There should be no matches found.
+    },
+
+    completionFinished: function (status) {
+      equal(status, Cr.NS_OK);
+      run_next_test();
+    },
+  });
+});
+
+function run_test() {
+  gHttpServV4 = new HttpServer();
+  gHttpServV4.registerDirectory("/", do_get_cwd());
+
+  // Update handler. Will respond a valid state to be verified in the
+  // gethash handler.
+  gHttpServV4.registerPathHandler("/safebrowsing/update", function(request, response) {
+    response.setHeader("Content-Type",
+                       "application/vnd.google.safebrowsing-update", false);
+    response.setStatusLine(request.httpVersion, 200, "OK");
+
+    // The protobuf binary represention of response:
+    //
+    // [
+    //   {
+    //     'threat_type': 2, // SOCIAL_ENGINEERING_PUBLIC
+    //     'response_type': 2, // FULL_UPDATE
+    //     'new_client_state': 'sta\x00te', // NEW_CLIENT_STATE
+    //     'checksum': { "sha256": CHECKSUM }, // CHECKSUM
+    //     'additions': { 'compression_type': RAW,
+    //                    'prefix_size': 4,
+    //                    'raw_hashes': "00000001000000020000000300000004"}
+    //   }
+    // ]
+    //
+    let content = "\x0A\x4A\x08\x02\x20\x02\x2A\x18\x08\x01\x12\x14\x08\x04\x12\x10\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x02\x00\x00\x00\x03\x3A\x06\x73\x74\x61\x00\x74\x65\x42\x22\x0A\x20\x30\x67\xC7\x2C\x5E\x50\x1C\x31\xE3\xFE\xCA\x73\xF0\x47\xDC\x34\x1A\x95\x63\x99\xEC\x70\x5E\x0A\xEE\x9E\xFB\x17\xA1\x55\x35\x78\x12\x08\x08\x08\x10\x80\x94\xEB\xDC\x03";
+
+    response.bodyOutputStream.write(content, content.length);
+
+    waitUntilMetaDataSaved(NEW_CLIENT_STATE, CHECKSUM, () => {
+      run_next_test();
+    });
+
+  });
+
+  // V4 gethash handler.
+  gHttpServV4.registerPathHandler("/safebrowsing/gethash-v4", function(request, response) {
+    equal(request.queryString, gExpectedGetHashQueryV4);
+
+    response.setStatusLine(request.httpVersion, 200, "OK");
+    response.bodyOutputStream.write("", 0);
+  });
+
+  gHttpServV4.start(5555);
+
+  run_next_test();
+}
\ No newline at end of file

--- a/toolkit/components/url-classifier/tests/unit/test_listmanager.js
+++ b/toolkit/components/url-classifier/tests/unit/test_listmanager.js
@@ -329,48 +329,8 @@ function waitForUpdateSuccess(callback) 
 function readFileToString(aFilename) {
   let f = do_get_file(aFilename);
   let stream = Cc["@mozilla.org/network/file-input-stream;1"]
     .createInstance(Ci.nsIFileInputStream);
   stream.init(f, -1, 0, 0);
   let buf = NetUtil.readInputStreamToString(stream, stream.available());
   return buf;
 }
-
-function waitUntilMetaDataSaved(expectedState, expectedChecksum, callback) {
-  let dbService = Cc["@mozilla.org/url-classifier/dbservice;1"]
-                     .getService(Ci.nsIUrlClassifierDBService);
-
-  dbService.getTables(metaData => {
-    do_print("metadata: " + metaData);
-    let didCallback = false;
-    metaData.split("\n").some(line => {
-      // Parse [tableName];[stateBase64]
-      let p = line.indexOf(";");
-      if (-1 === p) {
-        return false; // continue.
-      }
-      let tableName = line.substring(0, p);
-      let metadata = line.substring(p + 1).split(":");
-      let stateBase64 = metadata[0];
-      let checksumBase64 = metadata[1];
-
-      if (tableName !== 'test-phish-proto') {
-        return false; // continue.
-      }
-
-      if (stateBase64 === btoa(expectedState) &&
-          checksumBase64 === btoa(expectedChecksum)) {
-        do_print('State has been saved to disk!');
-        callback();
-        didCallback = true;
-      }
-
-      return true; // break no matter whether the state is matching.
-    });
-
-    if (!didCallback) {
-      do_timeout(1000, waitUntilMetaDataSaved.bind(null, expectedState,
-                                                         expectedChecksum,
-                                                         callback));
-    }
-  });
-}

--- a/toolkit/components/url-classifier/tests/unit/xpcshell.ini
+++ b/toolkit/components/url-classifier/tests/unit/xpcshell.ini
@@ -6,16 +6,17 @@ support-files =
   data/digest1.chunk
   data/digest2.chunk
 
 [test_addsub.js]
 [test_bug1274685_unowned_list.js]
 [test_backoff.js]
 [test_dbservice.js]
 [test_hashcompleter.js]
+[test_hashcompleter_v4.js]
 # Bug 752243: Profile cleanup frequently fails
 #skip-if = os == "mac" || os == "linux"
 [test_partial.js]
 [test_prefixset.js]
 [test_threat_type_conversion.js]
 [test_provider_url.js]
 [test_streamupdater.js]
 [test_digest256.js]