diff --git a/src/interest.cpp b/src/interest.cpp
index 05951be..d618475 100644
--- a/src/interest.cpp
+++ b/src/interest.cpp
@@ -94,8 +94,10 @@
   }
 
   // Nonce
-  getNonce(); // to ensure that Nonce is properly set
-  totalLength += encoder.prependBlock(m_nonce);
+  uint32_t nonce = this->getNonce(); // assigns random Nonce if needed
+  totalLength += encoder.prependByteArray(reinterpret_cast<uint8_t*>(&nonce), sizeof(nonce));
+  totalLength += encoder.prependVarNumber(sizeof(nonce));
+  totalLength += encoder.prependVarNumber(tlv::Nonce);
 
   // Selectors
   if (hasSelectors()) {
@@ -128,7 +130,7 @@
   EncodingBuffer buffer(estimatedSize, 0);
   wireEncode(buffer);
 
-  // to ensure that Nonce block points to the right memory location
+  // to ensure that Link block points to the right memory location
   const_cast<Interest*>(this)->wireDecode(buffer.block());
 
   return m_wire;
@@ -155,7 +157,16 @@
     m_selectors = Selectors();
 
   // Nonce
-  m_nonce = m_wire.get(tlv::Nonce);
+  val = m_wire.find(tlv::Nonce);
+  if (val == m_wire.elements_end()) {
+    BOOST_THROW_EXCEPTION(Error("Nonce element is missing"));
+  }
+  uint32_t nonce = 0;
+  if (val->value_size() != sizeof(nonce)) {
+    BOOST_THROW_EXCEPTION(Error("Nonce element is malformed"));
+  }
+  std::memcpy(&nonce, val->value(), sizeof(nonce));
+  m_nonce = nonce;
 
   // InterestLifetime
   val = m_wire.find(tlv::InterestLifetime);
@@ -320,7 +331,7 @@
 bool
 Interest::matchesInterest(const Interest& other) const
 {
-  /// @todo #3162 match Link field
+  /// @todo #3162 match ForwardingHint field
   return (this->getName() == other.getName() &&
           this->getSelectors() == other.getSelectors());
 }
@@ -330,32 +341,17 @@
 uint32_t
 Interest::getNonce() const
 {
-  if (!m_nonce.hasWire())
-    const_cast<Interest*>(this)->setNonce(random::generateWord32());
-
-  if (m_nonce.value_size() == sizeof(uint32_t)) {
-    uint32_t nonce = 0;
-    std::memcpy(&nonce, m_nonce.value(), sizeof(uint32_t));
-    return nonce;
+  if (!m_nonce) {
+    m_nonce = random::generateWord32();
   }
-  else {
-    // for compatibility reasons.  Should be removed eventually
-    return readNonNegativeInteger(m_nonce);
-  }
+  return *m_nonce;
 }
 
 Interest&
 Interest::setNonce(uint32_t nonce)
 {
-  if (m_wire.hasWire() && m_nonce.value_size() == sizeof(uint32_t)) {
-    std::memcpy(const_cast<uint8_t*>(m_nonce.value()), &nonce, sizeof(nonce));
-  }
-  else {
-    m_nonce = makeBinaryBlock(tlv::Nonce,
-                              reinterpret_cast<const uint8_t*>(&nonce),
-                              sizeof(nonce));
-    m_wire.reset();
-  }
+  m_nonce = nonce;
+  m_wire.reset();
   return *this;
 }
 
diff --git a/src/interest.hpp b/src/interest.hpp
index a00bbc0..7a45bc8 100644
--- a/src/interest.hpp
+++ b/src/interest.hpp
@@ -155,20 +155,17 @@
   bool
   hasNonce() const
   {
-    return m_nonce.hasWire();
+    return static_cast<bool>(m_nonce);
   }
 
-  /** @brief Get Interest's nonce
+  /** @brief Get nonce
    *
    *  If nonce was not set before this call, it will be automatically assigned to a random value
    */
   uint32_t
   getNonce() const;
 
-  /** @brief Set Interest's nonce
-   *
-   *  If wire format already exists, this call simply replaces nonce in the
-   *  existing wire format, without resetting and recreating it.
+  /** @brief Set nonce
    */
   Interest&
   setNonce(uint32_t nonce);
@@ -406,7 +403,7 @@
 private:
   Name m_name;
   Selectors m_selectors;
-  mutable Block m_nonce;
+  mutable optional<uint32_t> m_nonce;
   time::milliseconds m_interestLifetime;
   DelegationList m_forwardingHint;
 
diff --git a/tests/unit-tests/interest.t.cpp b/tests/unit-tests/interest.t.cpp
index a4c78c0..f108be6 100644
--- a/tests/unit-tests/interest.t.cpp
+++ b/tests/unit-tests/interest.t.cpp
@@ -39,6 +39,7 @@
   Interest i;
   BOOST_CHECK_EQUAL(i.getName(), "/");
   BOOST_CHECK(i.getSelectors().empty());
+  BOOST_CHECK_EQUAL(i.hasNonce(), false);
   BOOST_CHECK_EQUAL(i.getInterestLifetime(), DEFAULT_INTEREST_LIFETIME);
   BOOST_CHECK_EQUAL(i.hasLink(), false);
   BOOST_CHECK(!i.hasSelectedDelegation());
@@ -187,6 +188,37 @@
   BOOST_CHECK_EQUAL(i2.hasSelectedDelegation(), false);
 }
 
+BOOST_AUTO_TEST_CASE(DecodeNoName)
+{
+  Block b(tlv::Interest);
+  b.push_back(makeBinaryBlock(tlv::Nonce, "FISH", 4));
+  b.encode();
+
+  Interest i;
+  BOOST_CHECK_THROW(i.wireDecode(b), tlv::Error);
+}
+
+BOOST_AUTO_TEST_CASE(DecodeNoNonce)
+{
+  Block b(tlv::Interest);
+  b.push_back(Name("/YvzNKtPWh").wireEncode());
+  b.encode();
+
+  Interest i;
+  BOOST_CHECK_THROW(i.wireDecode(b), tlv::Error);
+}
+
+BOOST_AUTO_TEST_CASE(DecodeBadNonce)
+{
+  Block b(tlv::Interest);
+  b.push_back(Name("/BJzEHVxDJ").wireEncode());
+  b.push_back(makeBinaryBlock(tlv::Nonce, "SKY", 3));
+  b.encode();
+
+  Interest i;
+  BOOST_CHECK_THROW(i.wireDecode(b), tlv::Error);
+}
+
 // ---- matching ----
 
 BOOST_AUTO_TEST_CASE(MatchesData)
@@ -310,22 +342,41 @@
 
 BOOST_AUTO_TEST_CASE(GetNonce)
 {
-  unique_ptr<Interest> i;
+  unique_ptr<Interest> i1, i2;
 
-  // getNonce automatically assigns a random Nonce, which could be zero.
-  // But it's unlikely to get 100 zeros in a row.
-  uint32_t nonce = 0;
+  // getNonce automatically assigns a random Nonce.
+  // It's possible to assign the same Nonce to two Interest, but it's unlikely to get 100 pairs of
+  // same Nonces in a row.
   int nIterations = 0;
+  uint32_t nonce1 = 0, nonce2 = 0;
   do {
-    i = make_unique<Interest>();
-    nonce = i->getNonce();
+    i1 = make_unique<Interest>();
+    nonce1 = i1->getNonce();
+    i2 = make_unique<Interest>();
+    nonce2 = i2->getNonce();
   }
-  while (nonce == 0 && ++nIterations < 100);
-  BOOST_CHECK_NE(nonce, 0);
-  BOOST_CHECK(i->hasNonce());
+  while (nonce1 == nonce2 && ++nIterations < 100);
+  BOOST_CHECK_NE(nonce1, nonce2);
+  BOOST_CHECK(i1->hasNonce());
+  BOOST_CHECK(i2->hasNonce());
 
   // Once a Nonce is assigned, it should not change.
-  BOOST_CHECK_EQUAL(i->getNonce(), nonce);
+  BOOST_CHECK_EQUAL(i1->getNonce(), nonce1);
+}
+
+BOOST_AUTO_TEST_CASE(SetNonce)
+{
+  Interest i1("/A");
+  i1.setNonce(1);
+  i1.wireEncode();
+  BOOST_CHECK_EQUAL(i1.getNonce(), 1);
+
+  Interest i2(i1);
+  BOOST_CHECK_EQUAL(i2.getNonce(), 1);
+
+  i2.setNonce(2);
+  BOOST_CHECK_EQUAL(i2.getNonce(), 2);
+  BOOST_CHECK_EQUAL(i1.getNonce(), 1); // should not affect i1 Nonce (Bug #4168)
 }
 
 BOOST_AUTO_TEST_CASE(RefreshNonce)