--- a/toolkit/components/url-classifier/nsIUrlClassifierUtils.idl
+++ b/toolkit/components/url-classifier/nsIUrlClassifierUtils.idl
@@ -25,9 +25,40 @@ interface nsIUrlClassifierUtils : nsISup
   /**
    * Get the protocol version for the given provider.
    *
    * @param provider String the provider name. e.g. "google"
    *
    * @returns String to indicate the protocol version. e.g. "2.2"
    */
   ACString getProtocolVersion(in ACString provider);
+
+  /**
+   * Convert threat type to list name.
+   *
+   * @param Integer to indicate threat type.
+   *
+   * @returns The list name.
+   */
+  ACString convertThreatTypeToListName(in uint32_t threatType);
+
+  /**
+   * Convert list name to threat type.
+   *
+   * @param The list name.
+   *
+   * @returns The threat type in integer.
+   */
+  uint32_t convertListNameToThreatType(in ACString listName);
+
+  /**
+   * Make update request for given lists and their states.
+   *
+   * @param aListNames An array of list name represented in string.
+   * @param aState An array of states (in string) for each list.
+   * @param aCount The array length of aList and aState.
+   *
+   * @returns A string to store request. Not null-terminated.
+   */
+  ACString makeUpdateRequestV4([array, size_is(aCount)] in string aListNames,
+                               [array, size_is(aCount)] in string aStates,
+                               in uint32_t aCount);
 };

--- a/toolkit/components/url-classifier/nsUrlClassifierUtils.cpp
+++ b/toolkit/components/url-classifier/nsUrlClassifierUtils.cpp
@@ -6,16 +6,17 @@
 #include "nsString.h"
 #include "nsIURI.h"
 #include "nsUrlClassifierUtils.h"
 #include "nsTArray.h"
 #include "nsReadableUtils.h"
 #include "plbase64.h"
 #include "prprf.h"
 #include "nsPrintfCString.h"
+#include "safebrowsing.pb.h"
 
 #define DEFAULT_PROTOCOL_VERSION "2.2"
 
 static char int_to_hex_digit(int32_t i)
 {
   NS_ASSERTION((i >= 0) && (i <= 15), "int too big in int_to_hex_digit");
   return static_cast<char>(((i < 10) ? (i + '0') : ((i - 10) + 'A')));
 }
@@ -67,16 +68,86 @@ IsOctal(const nsACString & num)
     if (!isdigit(num[i]) || num[i] == '8' || num[i] == '9') {
       return false;
     }
   }
 
   return true;
 }
 
+/////////////////////////////////////////////////////////////////
+// SafeBrowsing V4 related utits.
+
+namespace mozilla {
+namespace safebrowsing {
+
+static PlatformType
+GetPlatformType()
+{
+#if defined(ANDROID)
+  return ANDROID_PLATFORM;
+#elif defined(XP_MACOSX)
+  return OSX_PLATFORM;
+#elif defined(XP_LINUX)
+  return LINUX_PLATFORM;
+#elif defined(XP_WIN)
+  return WINDOWS_PLATFORM;
+#else
+  #error Unrecognized platform type.
+#endif
+}
+
+typedef FetchThreatListUpdatesRequest_ListUpdateRequest ListUpdateRequest;
+typedef FetchThreatListUpdatesRequest_ListUpdateRequest_Constraints Constraints;
+
+static void
+InitListUpdateRequest(ThreatType aThreatType,
+                      const char* aState,
+                      ListUpdateRequest* aListUpdateRequest)
+{
+  aListUpdateRequest->set_threat_type(aThreatType);
+  aListUpdateRequest->set_platform_type(GetPlatformType());
+  aListUpdateRequest->set_threat_entry_type(URL);
+
+  // Only RAW data is supported for now.
+  // TODO: Bug 1285848 Supports Rice-Golomb encoding.
+  Constraints* contraints = new Constraints();
+  contraints->add_supported_compressions(RAW);
+  aListUpdateRequest->set_allocated_constraints(contraints);
+
+  // Only set non-empty state.
+  if (aState[0] != '\0') {
+    aListUpdateRequest->set_state(aState);
+  }
+}
+
+static ClientInfo*
+CreateClientInfo()
+{
+  ClientInfo* c = new ClientInfo();
+
+  nsCOMPtr<nsIPrefBranch> prefBranch =
+    do_GetService(NS_PREFSERVICE_CONTRACTID);
+
+  nsXPIDLCString clientId;
+  nsresult rv = prefBranch->GetCharPref("browser.safebrowsing.id",
+                                        getter_Copies(clientId));
+
+  if (NS_FAILED(rv)) {
+    clientId = "Firefox"; // Use "Firefox" as fallback.
+  }
+
+  c->set_client_id(clientId.get());
+
+  return c;
+}
+
+} // end of namespace safebrowsing.
+} // end of namespace mozilla.
+
 nsUrlClassifierUtils::nsUrlClassifierUtils() : mEscapeCharmap(nullptr)
 {
 }
 
 nsresult
 nsUrlClassifierUtils::Init()
 {
   // Everything but alpha numerics, - and .
@@ -122,16 +193,55 @@ nsUrlClassifierUtils::GetKeyForURI(nsIUR
   rv = CanonicalizePath(path, temp);
   NS_ENSURE_SUCCESS(rv, rv);
 
   _retval.Append(temp);
 
   return NS_OK;
 }
 
+// We use "goog-*-proto" as the list name for v4, where "proto" indicates
+// it's updated (as well as hash completion) via protobuf.
+static const struct {
+  const char* mListName;
+  uint32_t mThreatType;
+} THREAT_TYPE_CONV_TABLE[] = {
+  { "goog-malware-proto",  MALWARE_THREAT},            // 1
+  { "goog-phish-proto",    SOCIAL_ENGINEERING_PUBLIC}, // 2
+  { "goog-unwanted-proto", UNWANTED_SOFTWARE},         // 3
+};
+
+NS_IMETHODIMP
+nsUrlClassifierUtils::ConvertThreatTypeToListName(uint32_t aThreatType,
+                                                  nsACString& aListName)
+{
+  for (uint32_t i = 0; i < ArrayLength(THREAT_TYPE_CONV_TABLE); i++) {
+    if (aThreatType == THREAT_TYPE_CONV_TABLE[i].mThreatType) {
+      aListName = THREAT_TYPE_CONV_TABLE[i].mListName;
+      return NS_OK;
+    }
+  }
+
+  return NS_ERROR_FAILURE;
+}
+
+NS_IMETHODIMP
+nsUrlClassifierUtils::ConvertListNameToThreatType(const nsACString& aListName,
+                                                  uint32_t* aThreatType)
+{
+  for (uint32_t i = 0; i < ArrayLength(THREAT_TYPE_CONV_TABLE); i++) {
+    if (aListName.EqualsASCII(THREAT_TYPE_CONV_TABLE[i].mListName)) {
+      *aThreatType = THREAT_TYPE_CONV_TABLE[i].mThreatType;
+      return NS_OK;
+    }
+  }
+
+  return NS_ERROR_FAILURE;
+}
+
 NS_IMETHODIMP
 nsUrlClassifierUtils::GetProtocolVersion(const nsACString& aProvider,
                                          nsACString& aVersion)
 {
   nsCOMPtr<nsIPrefBranch> prefBranch = do_GetService(NS_PREFSERVICE_CONTRACTID);
   if (prefBranch) {
       nsPrintfCString prefName("browser.safebrowsing.provider.%s.pver",
                                nsCString(aProvider).get());
@@ -141,16 +251,50 @@ nsUrlClassifierUtils::GetProtocolVersion
       aVersion = NS_SUCCEEDED(rv) ? version : DEFAULT_PROTOCOL_VERSION;
   } else {
       aVersion = DEFAULT_PROTOCOL_VERSION;
   }
 
   return NS_OK;
 }
 
+NS_IMETHODIMP
+nsUrlClassifierUtils::MakeUpdateRequestV4(const char** aListNames,
+                                          const char** aStates,
+                                          uint32_t aCount,
+                                          nsACString &aRequest)
+{
+  using namespace mozilla::safebrowsing;
+
+  FetchThreatListUpdatesRequest r;
+  r.set_allocated_client(CreateClientInfo());
+
+  for (uint32_t i = 0; i < aCount; i++) {
+    nsCString listName(aListNames[i]);
+    uint32_t threatType;
+    nsresult rv = ConvertListNameToThreatType(listName, &threatType);
+    if (NS_FAILED(rv)) {
+      continue; // Unknown list name.
+    }
+    auto lur = r.mutable_list_update_requests()->Add();
+    InitListUpdateRequest(static_cast<ThreatType>(threatType), aStates[i], lur);
+  }
+
+  // Then serialize.
+  std::string s;
+  r.SerializeToString(&s);
+
+  nsCString out;
+  out.Assign(s.c_str(), s.size());
+
+  aRequest = out;
+
+  return NS_OK;
+}
+
 /////////////////////////////////////////////////////////////////////////////
 // non-interface methods
 
 nsresult
 nsUrlClassifierUtils::CanonicalizeHostname(const nsACString & hostname,
                                            nsACString & _retval)
 {
   nsAutoCString unescaped;

new file mode 100644
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/unit/test_safebrowsing_protobuf.js
@@ -0,0 +1,23 @@
+function run_test() {
+  let urlUtils = Cc["@mozilla.org/url-classifier/utils;1"]
+                   .getService(Ci.nsIUrlClassifierUtils);
+
+  // No list at all.
+  let requestNoList = urlUtils.makeUpdateRequestV4([], [], 0);
+
+  // Only one valid list name.
+  let requestOneValid =
+    urlUtils.makeUpdateRequestV4(["goog-phish-proto"], ["AAAAAA"], 1);
+
+  // Only one invalid list name.
+  let requestOneInvalid =
+    urlUtils.makeUpdateRequestV4(["bad-list-name"], ["AAAAAA"], 1);
+
+  // One valid and one invalid list name.
+  let requestOneInvalidOneValid =
+    urlUtils.makeUpdateRequestV4(["goog-phish-proto", "bad-list-name"],
+                                 ["AAAAAA", "AAAAAA"], 2);
+
+  equal(requestNoList, requestOneInvalid);
+  equal(requestOneValid, requestOneInvalidOneValid);
+}
\ No newline at end of file

new file mode 100644
--- /dev/null
+++ b/toolkit/components/url-classifier/tests/unit/test_threat_type_conversion.js
@@ -0,0 +1,35 @@
+function run_test() {
+  let urlUtils = Cc["@mozilla.org/url-classifier/utils;1"]
+                   .getService(Ci.nsIUrlClassifierUtils);
+
+  // Test list name to threat type conversion.
+
+  equal(urlUtils.convertListNameToThreatType("goog-malware-proto"), 1);
+  equal(urlUtils.convertListNameToThreatType("goog-phish-proto"), 2);
+  equal(urlUtils.convertListNameToThreatType("goog-unwanted-proto"), 3);
+
+  try {
+    urlUtils.convertListNameToThreatType("bad-list-name");
+    ok(false, "Bad list name should lead to exception.");
+  } catch (e) {}
+
+  try {
+    urlUtils.convertListNameToThreatType("bad-list-name");
+    ok(false, "Bad list name should lead to exception.");
+  } catch (e) {}
+
+  // Test threat type to list name conversion.
+  equal(urlUtils.convertThreatTypeToListName(1), "goog-malware-proto");
+  equal(urlUtils.convertThreatTypeToListName(2), "goog-phish-proto");
+  equal(urlUtils.convertThreatTypeToListName(3), "goog-unwanted-proto");
+
+  try {
+    urlUtils.convertThreatTypeToListName(0);
+    ok(false, "Bad threat type should lead to exception.");
+  } catch (e) {}
+
+  try {
+    urlUtils.convertThreatTypeToListName(100);
+    ok(false, "Bad threat type should lead to exception.");
+  } catch (e) {}
+}
\ No newline at end of file

--- a/toolkit/components/url-classifier/tests/unit/xpcshell.ini
+++ b/toolkit/components/url-classifier/tests/unit/xpcshell.ini
@@ -10,13 +10,15 @@ support-files =
 [test_bug1274685_unowned_list.js]
 [test_backoff.js]
 [test_dbservice.js]
 [test_hashcompleter.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]
 [test_listmanager.js]
 [test_pref.js]
+[test_safebrowsing_protobuf.js]