diff --git a/src/access_api_handler.cc b/src/access_api_handler.cc
index fc7b97b..ec22094 100644
--- a/src/access_api_handler.cc
+++ b/src/access_api_handler.cc
@@ -23,6 +23,7 @@
 const char kUserId[] = "userId";
 const char kApplicationId[] = "applicationId";
 const char kExpirationTime[] = "expirationTime";
+const char kRevocationTimestamp[] = "revocationTimestamp";
 const char kBlackList[] = "revocationListEntries";
 
 bool GetIds(const base::DictionaryValue& parameters,
@@ -65,6 +66,9 @@
             "applicationId": {
               "type": "string"
             },
+            "revocationTimestamp": {
+              "type": "integer"
+            },
             "expirationTime": {
               "type": "integer"
             }
@@ -85,6 +89,9 @@
                   "applicationId": {
                     "type": "string"
                   },
+                  "revocationTimestamp": {
+                    "type": "integer"
+                  },
                   "expirationTime": {
                     "type": "integer"
                   }
@@ -132,15 +139,25 @@
     return;
   }
 
-  int time_j2k = 0;
-  if (!parameters.GetInteger(kExpirationTime, &time_j2k)) {
+  int expiration_j2k = 0;
+  if (!parameters.GetInteger(kExpirationTime, &expiration_j2k)) {
     Error::AddToPrintf(&error, FROM_HERE, errors::commands::kInvalidPropValue,
                        "Expiration time is missing");
     command->Abort(error.get(), nullptr);
     return;
   }
 
-  manager_->Block(user_id, app_id, FromJ2000Time(time_j2k),
+  int revocation_j2k = 0;
+  if (!parameters.GetInteger(kRevocationTimestamp, &revocation_j2k)) {
+    Error::AddToPrintf(&error, FROM_HERE, errors::commands::kInvalidPropValue,
+                       "Revocation timestamp is missing");
+    command->Abort(error.get(), nullptr);
+    return;
+  }
+
+  manager_->Block(AccessBlackListManager::Entry{user_id, app_id,
+                                                FromJ2000Time(revocation_j2k),
+                                                FromJ2000Time(expiration_j2k)},
                   base::Bind(&AccessApiHandler::OnCommandDone,
                              weak_ptr_factory_.GetWeakPtr(), cmd));
 }
diff --git a/src/access_api_handler.h b/src/access_api_handler.h
index 83f0973..19fe799 100644
--- a/src/access_api_handler.h
+++ b/src/access_api_handler.h
@@ -20,8 +20,7 @@
 // Objects of the class subscribe for notification from CommandManager and
 // execute incoming commands.
 // Handled commands:
-//  accessControlBlackList.block
-//  accessControlBlackList.unblock
+//  accessControlBlackList.revoke
 //  accessControlBlackList.list
 class AccessApiHandler final {
  public:
diff --git a/src/access_api_handler_unittest.cc b/src/access_api_handler_unittest.cc
index 79f2d49..0a01d4f 100644
--- a/src/access_api_handler_unittest.cc
+++ b/src/access_api_handler_unittest.cc
@@ -104,6 +104,9 @@
           "applicationId": {
             "type": "string"
           },
+          "revocationTimestamp": {
+            "type": "integer"
+          },
           "expirationTime": {
             "type": "integer"
           }
@@ -124,6 +127,9 @@
                 "applicationId": {
                   "type": "string"
                 },
+                "revocationTimestamp": {
+                  "type": "integer"
+                },
                 "expirationTime": {
                   "type": "integer"
                 }
@@ -150,9 +156,14 @@
 }
 
 TEST_F(AccessApiHandlerTest, Revoke) {
-  EXPECT_CALL(access_manager_, Block(std::vector<uint8_t>{1, 2, 3},
-                                     std::vector<uint8_t>{3, 4, 5}, _, _))
-      .WillOnce(WithArgs<3>(
+  EXPECT_CALL(
+      access_manager_,
+      Block(AccessBlackListManager::Entry{std::vector<uint8_t>{1, 2, 3},
+                                          std::vector<uint8_t>{3, 4, 5},
+                                          base::Time::FromTimeT(946686034),
+                                          base::Time::FromTimeT(946692690)},
+            _))
+      .WillOnce(WithArgs<1>(
           Invoke([](const DoneCallback& callback) { callback.Run(nullptr); })));
   EXPECT_CALL(access_manager_, GetSize()).WillRepeatedly(Return(1));
 
@@ -162,7 +173,8 @@
     'parameters': {
       'userId': 'AQID',
       'applicationId': 'AwQF',
-      'expirationTime': 1234
+      'expirationTime': 7890,
+      'revocationTimestamp': 1234
     }
   })");
 
@@ -174,8 +186,14 @@
 
 TEST_F(AccessApiHandlerTest, List) {
   std::vector<AccessBlackListManager::Entry> entries{
-      {{11, 12, 13}, {21, 22, 23}, base::Time::FromTimeT(1410000000)},
-      {{31, 32, 33}, {41, 42, 43}, base::Time::FromTimeT(1420000000)},
+      {{11, 12, 13},
+       {21, 22, 23},
+       base::Time::FromTimeT(1310000000),
+       base::Time::FromTimeT(1410000000)},
+      {{31, 32, 33},
+       {41, 42, 43},
+       base::Time::FromTimeT(1300000000),
+       base::Time::FromTimeT(1420000000)},
   };
   EXPECT_CALL(access_manager_, GetEntries()).WillOnce(Return(entries));
   EXPECT_CALL(access_manager_, GetSize()).WillRepeatedly(Return(4));
diff --git a/src/access_black_list_manager.h b/src/access_black_list_manager.h
index eb3f06a..edbb3f2 100644
--- a/src/access_black_list_manager.h
+++ b/src/access_black_list_manager.h
@@ -14,6 +14,16 @@
 class AccessBlackListManager {
  public:
   struct Entry {
+    Entry() = default;
+
+    Entry(const std::vector<uint8_t>& user,
+          const std::vector<uint8_t>& app,
+          base::Time revocation_ts,
+          base::Time expiration_ts)
+        : user_id{user},
+          app_id{app},
+          revocation{revocation_ts},
+          expiration{expiration_ts} {}
     // user_id is empty, app_id is empty: block everything.
     // user_id is not empty, app_id is empty: block if user_id matches.
     // user_id is empty, app_id is not empty: block if app_id matches.
@@ -21,18 +31,20 @@
     std::vector<uint8_t> user_id;
     std::vector<uint8_t> app_id;
 
+    // Revoke matching entries if |revocation| is not less than
+    // delegation timestamp.
+    base::Time revocation;
+
     // Time after which to discard the rule.
     base::Time expiration;
   };
   virtual ~AccessBlackListManager() = default;
 
   virtual void AddEntryAddedCallback(const base::Closure& callback) = 0;
-  virtual void Block(const std::vector<uint8_t>& user_id,
-                     const std::vector<uint8_t>& app_id,
-                     const base::Time& expiration,
-                     const DoneCallback& callback) = 0;
+  virtual void Block(const Entry& entry, const DoneCallback& callback) = 0;
   virtual bool IsBlocked(const std::vector<uint8_t>& user_id,
-                         const std::vector<uint8_t>& app_id) const = 0;
+                         const std::vector<uint8_t>& app_id,
+                         base::Time timestamp) const = 0;
   virtual std::vector<Entry> GetEntries() const = 0;
   virtual size_t GetSize() const = 0;
   virtual size_t GetCapacity() const = 0;
@@ -40,8 +52,8 @@
 
 inline bool operator==(const AccessBlackListManager::Entry& l,
                        const AccessBlackListManager::Entry& r) {
-  return l.user_id == r.user_id && l.app_id == r.app_id &&
-         l.expiration == r.expiration;
+  return l.revocation == r.revocation && l.expiration == r.expiration &&
+         l.user_id == r.user_id && l.app_id == r.app_id;
 }
 
 inline bool operator!=(const AccessBlackListManager::Entry& l,
diff --git a/src/access_black_list_manager_impl.cc b/src/access_black_list_manager_impl.cc
index 3a54073..48c998b 100644
--- a/src/access_black_list_manager_impl.cc
+++ b/src/access_black_list_manager_impl.cc
@@ -10,6 +10,7 @@
 
 #include "src/commands/schema_constants.h"
 #include "src/data_encoding.h"
+#include "src/utils.h"
 
 namespace weave {
 
@@ -19,6 +20,7 @@
 const char kUser[] = "user";
 const char kApp[] = "app";
 const char kExpiration[] = "expiration";
+const char kRevocation[] = "revocation";
 }
 
 AccessBlackListManagerImpl::AccessBlackListManagerImpl(
@@ -34,19 +36,22 @@
     return;
   if (auto list = base::ListValue::From(
           base::JSONReader::Read(store_->LoadSettings(kConfigFileName)))) {
-    for (const auto& e : *list) {
+    for (const auto& value : *list) {
       const base::DictionaryValue* entry{nullptr};
       std::string user;
       std::string app;
-      decltype(entries_)::key_type key;
-      int expiration;
-      if (e->GetAsDictionary(&entry) && entry->GetString(kUser, &user) &&
-          Base64Decode(user, &key.first) && entry->GetString(kApp, &app) &&
-          Base64Decode(app, &key.second) &&
+      Entry e;
+      int revocation = 0;
+      int expiration = 0;
+      if (value->GetAsDictionary(&entry) && entry->GetString(kUser, &user) &&
+          Base64Decode(user, &e.user_id) && entry->GetString(kApp, &app) &&
+          Base64Decode(app, &e.app_id) &&
+          entry->GetInteger(kRevocation, &revocation) &&
           entry->GetInteger(kExpiration, &expiration)) {
-        base::Time expiration_time = base::Time::FromTimeT(expiration);
-        if (expiration_time > clock_->Now())
-          entries_[key] = expiration_time;
+        e.revocation = FromJ2000Time(revocation);
+        e.expiration = FromJ2000Time(expiration);
+        if (e.expiration > clock_->Now())
+          entries_.insert(e);
       }
     }
     if (entries_.size() < list->GetSize()) {
@@ -66,9 +71,10 @@
   base::ListValue list;
   for (const auto& e : entries_) {
     scoped_ptr<base::DictionaryValue> entry{new base::DictionaryValue};
-    entry->SetString(kUser, Base64Encode(e.first.first));
-    entry->SetString(kApp, Base64Encode(e.first.second));
-    entry->SetInteger(kExpiration, e.second.ToTimeT());
+    entry->SetString(kUser, Base64Encode(e.user_id));
+    entry->SetString(kApp, Base64Encode(e.app_id));
+    entry->SetInteger(kRevocation, ToJ2000Time(e.revocation));
+    entry->SetInteger(kExpiration, ToJ2000Time(e.expiration));
     list.Append(std::move(entry));
   }
 
@@ -79,7 +85,7 @@
 
 void AccessBlackListManagerImpl::RemoveExpired() {
   for (auto i = begin(entries_); i != end(entries_);) {
-    if (i->second <= clock_->Now())
+    if (i->expiration <= clock_->Now())
       i = entries_.erase(i);
     else
       ++i;
@@ -91,13 +97,11 @@
   on_entry_added_callbacks_.push_back(callback);
 }
 
-void AccessBlackListManagerImpl::Block(const std::vector<uint8_t>& user_id,
-                                       const std::vector<uint8_t>& app_id,
-                                       const base::Time& expiration,
+void AccessBlackListManagerImpl::Block(const Entry& entry,
                                        const DoneCallback& callback) {
   // Iterating is OK as Save below is more expensive.
   RemoveExpired();
-  if (expiration <= clock_->Now()) {
+  if (entry.expiration <= clock_->Now()) {
     if (!callback.is_null()) {
       ErrorPtr error;
       Error::AddTo(&error, FROM_HERE, "aleady_expired",
@@ -116,22 +120,36 @@
     return;
   }
 
-  auto& value = entries_[std::make_pair(user_id, app_id)];
-  value = std::max(value, expiration);
+  auto existing = entries_.find(entry);
+  if (existing != entries_.end()) {
+    Entry new_entry = entry;
+    new_entry.expiration = std::max(entry.expiration, existing->expiration);
+    new_entry.revocation = std::max(entry.revocation, existing->revocation);
+    entries_.erase(existing);
+    entries_.insert(new_entry);
+  } else {
+    entries_.insert(entry);
+  }
+
   for (const auto& cb : on_entry_added_callbacks_)
     cb.Run();
 
   Save(callback);
 }
 
-bool AccessBlackListManagerImpl::IsBlocked(
-    const std::vector<uint8_t>& user_id,
-    const std::vector<uint8_t>& app_id) const {
+bool AccessBlackListManagerImpl::IsBlocked(const std::vector<uint8_t>& user_id,
+                                           const std::vector<uint8_t>& app_id,
+                                           base::Time timestamp) const {
+  Entry entry_to_find;
   for (const auto& user : {{}, user_id}) {
     for (const auto& app : {{}, app_id}) {
-      auto both = entries_.find(std::make_pair(user, app));
-      if (both != end(entries_) && both->second > clock_->Now())
+      entry_to_find.user_id = user;
+      entry_to_find.app_id = app;
+      auto match = entries_.find(entry_to_find);
+      if (match != end(entries_) && match->expiration > clock_->Now() &&
+          match->revocation >= timestamp) {
         return true;
+      }
     }
   }
   return false;
@@ -139,10 +157,7 @@
 
 std::vector<AccessBlackListManager::Entry>
 AccessBlackListManagerImpl::GetEntries() const {
-  std::vector<Entry> result;
-  for (const auto& e : entries_)
-    result.push_back({e.first.first, e.first.second, e.second});
-  return result;
+  return {begin(entries_), end(entries_)};
 }
 
 size_t AccessBlackListManagerImpl::GetSize() const {
diff --git a/src/access_black_list_manager_impl.h b/src/access_black_list_manager_impl.h
index e41a93a..ff91a8f 100644
--- a/src/access_black_list_manager_impl.h
+++ b/src/access_black_list_manager_impl.h
@@ -5,7 +5,7 @@
 #ifndef LIBWEAVE_SRC_ACCESS_BLACK_LIST_IMPL_H_
 #define LIBWEAVE_SRC_ACCESS_BLACK_LIST_IMPL_H_
 
-#include <map>
+#include <set>
 #include <utility>
 
 #include <base/time/default_clock.h>
@@ -25,12 +25,10 @@
 
   // AccessBlackListManager implementation.
   void AddEntryAddedCallback(const base::Closure& callback) override;
-  void Block(const std::vector<uint8_t>& user_id,
-             const std::vector<uint8_t>& app_id,
-             const base::Time& expiration,
-             const DoneCallback& callback) override;
+  void Block(const Entry& entry, const DoneCallback& callback) override;
   bool IsBlocked(const std::vector<uint8_t>& user_id,
-                 const std::vector<uint8_t>& app_id) const override;
+                 const std::vector<uint8_t>& app_id,
+                 base::Time timestamp) const override;
   std::vector<Entry> GetEntries() const override;
   size_t GetSize() const override;
   size_t GetCapacity() const override;
@@ -40,13 +38,22 @@
   void Save(const DoneCallback& callback);
   void RemoveExpired();
 
+  struct EntryIdsLess {
+    bool operator()(const Entry& l, const Entry& r) const {
+      if (l.user_id < r.user_id)
+        return true;
+      if (l.user_id > r.user_id)
+        return false;
+      return l.app_id < r.app_id;
+    }
+  };
+
   const size_t capacity_{0};
   base::DefaultClock default_clock_;
   base::Clock* clock_{&default_clock_};
 
   provider::ConfigStore* store_{nullptr};
-  std::map<std::pair<std::vector<uint8_t>, std::vector<uint8_t>>, base::Time>
-      entries_;
+  std::set<Entry, EntryIdsLess> entries_;
   std::vector<base::Closure> on_entry_added_callbacks_;
 
   DISALLOW_COPY_AND_ASSIGN(AccessBlackListManagerImpl);
diff --git a/src/access_black_list_manager_impl_unittest.cc b/src/access_black_list_manager_impl_unittest.cc
index 0f21c3e..3be9287 100644
--- a/src/access_black_list_manager_impl_unittest.cc
+++ b/src/access_black_list_manager_impl_unittest.cc
@@ -24,11 +24,13 @@
     std::string to_load = R"([{
       "user": "BQID",
       "app": "BwQF",
-      "expiration": 1410000000
+      "expiration": 463315200,
+      "revocation": 463314200
     }, {
       "user": "AQID",
       "app": "AwQF",
-      "expiration": 1419999999
+      "expiration": 473315199,
+      "revocation": 473313199
     }])";
 
     EXPECT_CALL(config_store_, LoadSettings("black_list"))
@@ -40,7 +42,8 @@
               std::string to_save = R"([{
                 "user": "AQID",
                 "app": "AwQF",
-                "expiration": 1419999999
+                "expiration": 473315199,
+                "revocation": 473313199
               }])";
               EXPECT_JSON_EQ(to_save, *test::CreateValue(json));
               if (!callback.is_null())
@@ -60,7 +63,10 @@
   EXPECT_EQ(1u, manager_->GetSize());
   EXPECT_EQ(10u, manager_->GetCapacity());
   EXPECT_EQ((std::vector<AccessBlackListManagerImpl::Entry>{{
-                {1, 2, 3}, {3, 4, 5}, base::Time::FromTimeT(1419999999),
+                {1, 2, 3},
+                {3, 4, 5},
+                base::Time::FromTimeT(1419997999),
+                base::Time::FromTimeT(1419999999),
             }}),
             manager_->GetEntries());
 }
@@ -75,22 +81,31 @@
             std::string to_save = R"([{
                 "user": "AQID",
                 "app": "AwQF",
-                "expiration": 1419999999
+                "expiration": 473315199,
+                "revocation": 473313199
               }, {
                 "app": "CAgI",
                 "user": "BwcH",
-                "expiration": 1419990000
+                "expiration": 473305200,
+                "revocation": 473295200
               }])";
             EXPECT_JSON_EQ(to_save, *test::CreateValue(json));
             if (!callback.is_null())
               callback.Run(nullptr);
           })));
-  manager_->Block({7, 7, 7}, {8, 8, 8}, base::Time::FromTimeT(1419990000), {});
+  manager_->Block({{7, 7, 7},
+                   {8, 8, 8},
+                   base::Time::FromTimeT(1419980000),
+                   base::Time::FromTimeT(1419990000)},
+                  {});
   EXPECT_TRUE(callback_called);
 }
 
 TEST_F(AccessBlackListManagerImplTest, BlockExpired) {
-  manager_->Block({}, {}, base::Time::FromTimeT(1400000000),
+  manager_->Block({{},
+                   {},
+                   base::Time::FromTimeT(1300000000),
+                   base::Time::FromTimeT(1400000000)},
                   base::Bind([](ErrorPtr error) {
                     EXPECT_TRUE(error->HasError("aleady_expired"));
                   }));
@@ -105,18 +120,30 @@
           })));
   for (size_t i = manager_->GetSize(); i < manager_->GetCapacity(); ++i) {
     manager_->Block(
-        {99, static_cast<uint8_t>(i / 256), static_cast<uint8_t>(i % 256)},
-        {8, 8, 8}, base::Time::FromTimeT(1419990000), {});
+        {{99, static_cast<uint8_t>(i / 256), static_cast<uint8_t>(i % 256)},
+         {8, 8, 8},
+         base::Time::FromTimeT(1419970000),
+         base::Time::FromTimeT(1419990000)},
+        {});
     EXPECT_EQ(i + 1, manager_->GetSize());
   }
-  manager_->Block({99}, {8, 8, 8}, base::Time::FromTimeT(1419990000),
+  manager_->Block({{99},
+                   {8, 8, 8},
+                   base::Time::FromTimeT(1419970000),
+                   base::Time::FromTimeT(1419990000)},
                   base::Bind([](ErrorPtr error) {
                     EXPECT_TRUE(error->HasError("blacklist_is_full"));
                   }));
 }
 
-TEST_F(AccessBlackListManagerImplTest, IsBlockedFalse) {
-  EXPECT_FALSE(manager_->IsBlocked({7, 7, 7}, {8, 8, 8}));
+TEST_F(AccessBlackListManagerImplTest, IsBlockedIdsNotMacth) {
+  EXPECT_FALSE(manager_->IsBlocked({7, 7, 7}, {8, 8, 8}, {}));
+}
+
+TEST_F(AccessBlackListManagerImplTest, IsBlockedRevocationIsOld) {
+  // Ids match but delegation time is newer than revocation time.
+  EXPECT_FALSE(manager_->IsBlocked({1, 2, 3}, {3, 4, 5},
+                                   base::Time::FromTimeT(1429997999)));
 }
 
 class AccessBlackListManagerImplIsBlockedTest
@@ -132,13 +159,16 @@
               if (!callback.is_null())
                 callback.Run(nullptr);
             })));
-    manager_->Block(std::get<0>(GetParam()), std::get<1>(GetParam()),
-                    base::Time::FromTimeT(1419990000), {});
+    manager_->Block({std::get<0>(GetParam()),
+                     std::get<1>(GetParam()),
+                     {},
+                     base::Time::FromTimeT(1419990000)},
+                    {});
   }
 };
 
 TEST_P(AccessBlackListManagerImplIsBlockedTest, IsBlocked) {
-  EXPECT_TRUE(manager_->IsBlocked({7, 7, 7}, {8, 8, 8}));
+  EXPECT_TRUE(manager_->IsBlocked({7, 7, 7}, {8, 8, 8}, {}));
 }
 
 INSTANTIATE_TEST_CASE_P(
diff --git a/src/test/mock_black_list_manager.h b/src/test/mock_black_list_manager.h
index 6b55b86..2f6d7eb 100644
--- a/src/test/mock_black_list_manager.h
+++ b/src/test/mock_black_list_manager.h
@@ -16,14 +16,11 @@
 class MockAccessBlackListManager : public AccessBlackListManager {
  public:
   MOCK_METHOD1(AddEntryAddedCallback, void(const base::Closure&));
-  MOCK_METHOD4(Block,
-               void(const std::vector<uint8_t>&,
-                    const std::vector<uint8_t>&,
-                    const base::Time&,
-                    const DoneCallback&));
-  MOCK_CONST_METHOD2(IsBlocked,
+  MOCK_METHOD2(Block, void(const Entry&, const DoneCallback&));
+  MOCK_CONST_METHOD3(IsBlocked,
                      bool(const std::vector<uint8_t>&,
-                          const std::vector<uint8_t>&));
+                          const std::vector<uint8_t>&,
+                          base::Time));
   MOCK_CONST_METHOD0(GetEntries, std::vector<Entry>());
   MOCK_CONST_METHOD0(GetSize, size_t());
   MOCK_CONST_METHOD0(GetCapacity, size_t());