--- a/toolkit/components/url-classifier/nsIUrlClassifierUtils.idl
+++ b/toolkit/components/url-classifier/nsIUrlClassifierUtils.idl
@@ -43,9 +43,22 @@ interface nsIUrlClassifierUtils : nsISup
   /**
    * 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,88 @@ 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
+
+  return PLATFORM_TYPE_UNSPECIFIED;
+}
+
+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 .
@@ -181,16 +254,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

--- a/toolkit/components/url-classifier/tests/unit/xpcshell.ini
+++ b/toolkit/components/url-classifier/tests/unit/xpcshell.ini
@@ -16,8 +16,9 @@ support-files =
 [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]