diff --git a/tests/unit-tests/bzip2-helper.t.cpp b/tests/unit-tests/bzip2-helper.t.cpp
new file mode 100644
index 0000000..330f66b
--- /dev/null
+++ b/tests/unit-tests/bzip2-helper.t.cpp
@@ -0,0 +1,52 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012-2018 University of California, Los Angeles
+ *
+ * This file is part of ChronoSync, synchronization library for distributed realtime
+ * applications for NDN.
+ *
+ * ChronoSync is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation, either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * ChronoSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * ChronoSync, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "bzip2-helper.hpp"
+
+#include "boost-test.hpp"
+
+namespace chronosync {
+namespace test {
+
+using std::tuple;
+
+BOOST_AUTO_TEST_SUITE(TestBzip2Helper)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+  std::string message = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, "
+    "sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. "
+    "Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris "
+    "nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in "
+    "reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. "
+    "Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt "
+    "mollit anim id est laborum.";
+
+  auto compressed = bzip2::compress(message.data(), message.size());
+  BOOST_CHECK_LT(compressed->size(), message.size());
+
+  auto decompressed = bzip2::decompress(reinterpret_cast<const char*>(compressed->data()), compressed->size());
+  BOOST_CHECK_EQUAL(message.size(), decompressed->size());
+  BOOST_CHECK_EQUAL(message, std::string(reinterpret_cast<const char*>(decompressed->data()), decompressed->size()));
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace test
+} // namespace chronosync
diff --git a/tests/unit-tests/test-logic.cpp b/tests/unit-tests/test-logic.cpp
index fb0422a..83e8708 100644
--- a/tests/unit-tests/test-logic.cpp
+++ b/tests/unit-tests/test-logic.cpp
@@ -18,12 +18,15 @@
  */
 
 #include "logic.hpp"
+#include "bzip2-helper.hpp"
 
 #include "boost-test.hpp"
 #include "../identity-management-fixture.hpp"
 
 #include "dummy-forwarder.hpp"
 
+#include <ndn-cxx/util/random.hpp>
+
 namespace chronosync {
 namespace test {
 
@@ -319,7 +322,7 @@
   BOOST_CHECK_EQUAL(handler[1]->logic.getSessionNames().size(), 2);
 }
 
-BOOST_FIXTURE_TEST_CASE(ExplodeData, ndn::tests::IdentityManagementTimeFixture)
+BOOST_FIXTURE_TEST_CASE(TrimState, ndn::tests::IdentityManagementTimeFixture)
 {
   Name syncPrefix("/ndn/broadcast/sync");
   Name userPrefix("/user");
@@ -327,25 +330,47 @@
   Logic logic(face, syncPrefix, userPrefix, bind(onUpdate, _1));
 
   State state;
-  int i = 0;
-  while (state.wireEncode().size() < ndn::MAX_NDN_PACKET_SIZE) {
-    Name name("/test1");
-    name.append(std::to_string(i));
-    state.update(name, i++);
+  for (size_t i = 0; i != 100; ++i) {
+    state.update(Name("/to/trim").appendNumber(i), 42);
   }
 
-  Data syncReply(syncPrefix);
-  syncReply.setContent(state.wireEncode());
-  m_keyChain.sign(syncReply);
+  State partial;
+  logic.trimState(partial, state, 1);
+  BOOST_CHECK_EQUAL(partial.getLeaves().size(), 99);
 
-  BOOST_REQUIRE(syncReply.wireEncode().size() > ndn::MAX_NDN_PACKET_SIZE);
+  logic.trimState(partial, state, 100);
+  BOOST_CHECK_EQUAL(partial.getLeaves().size(), 1);
 
-  State partialState;
-  auto maxSize = ndn::MAX_NDN_PACKET_SIZE - (syncReply.wireEncode().size() - state.wireEncode().size());
-  logic.trimState(partialState, state, maxSize);
+  logic.trimState(partial, state, 101);
+  BOOST_CHECK_EQUAL(partial.getLeaves().size(), 1);
 
-  syncReply.setContent(partialState.wireEncode());
-  BOOST_REQUIRE(syncReply.wireEncode().size() < ndn::MAX_NDN_PACKET_SIZE);
+  logic.trimState(partial, state, 42);
+  BOOST_CHECK_EQUAL(partial.getLeaves().size(), 58);
+}
+
+BOOST_FIXTURE_TEST_CASE(VeryLargeState, ndn::tests::IdentityManagementTimeFixture)
+{
+  addIdentity("/bla");
+  Name syncPrefix("/ndn/broadcast/sync");
+  Name userPrefix("/user");
+  ndn::util::DummyClientFace face;
+  Logic logic(face, syncPrefix, userPrefix, bind(onUpdate, _1));
+
+  State state;
+  for (size_t i = 0; i < 50000 && bzip2::compress(reinterpret_cast<const char*>(state.wireEncode().wire()),
+                                                  state.wireEncode().size())->size() < ndn::MAX_NDN_PACKET_SIZE;
+       i += 10) {
+    Name prefix("/to/trim");
+    prefix.appendNumber(i);
+    for (size_t j = 0; j != 20; ++j) {
+      prefix.appendNumber(ndn::random::generateWord32());
+    }
+    state.update(prefix, ndn::random::generateWord32());
+  }
+  BOOST_TEST_MESSAGE("Got state with " << state.getLeaves().size() << " leaves");
+
+  auto data = logic.encodeSyncReply(userPrefix, "/fake/prefix/of/interest", state);
+  BOOST_CHECK_LE(data.wireEncode().size(), ndn::MAX_NDN_PACKET_SIZE);
 }
 
 class MaxPacketCustomizationFixture
@@ -361,6 +386,7 @@
 
   ~MaxPacketCustomizationFixture()
   {
+    unsetenv("CHRONOSYNC_MAX_PACKET_SIZE");
     if (oldSize) {
       setenv("CHRONOSYNC_MAX_PACKET_SIZE", oldSize->c_str(), 1);
     }