Subject: [icnrg] ContentObject matching against a ContentObjectHashRestriction

From: "Thompson, Jeff" <[email-masked]>
Date: Thu, 2 Jul 2015 08:56:52 +0000

An Interest with a ContentObjectHashRestriction is typically used to fetch the Content Objects from a manifest which lists all the contents only by hash. In this case, the Interest only has a name for routing purposes plus the ContentObjectHashRestriction from the manifest. Since a manifest can be used for large content like video, it's likely that a large portion (a majority?) of the Content Objects on the network will be fetched by ContentObjectHashRestriction. Therefore, it is worth clarifying the semantics of Content Object matching in this case.

Section 8 of draft-irtf-icnrg-ccnxsemantics-00.txt currently says "A Content Object satisfies an Interest if and only if (a) the Content Object name exactly matches the Interest name and (b) the ValidationAlgorithm KeyId of the Content Object exactly equals the Interest KeyIdRestriction, if given, and (c) the computed ContentObjectHash exactly equals the Interest ContentObjectHashRestriction, if given." But if the ContentObjectHashRestriction is given in the Interest, then the name in the Interest is only needed for routing the interest to the producer but is not needed for matching since the hash specifies an exact match. On the return path, the Content Object can have an empty name and can be matched on the ContentObjectHash only, therefore saving space in the Content Object for an unnecessary name. (See other advantages below for omitting an unnecessary routing name in the Content Object.)

A typical objection for matching on hash only is that the Forwarder would have to compute the hash of every incoming Content Object. But this is not true. A Forwarder only needs to compute the ContentObjectHash of an incoming Content Object with an empty name, since in this case it could only match an Interest with a ContentObjectHashRestriction. Another typical reaction when hearing about matching on hash only is to say "fetching by hash is a flat name space and routing on flat names does not scale." But this is a misunderstanding. The Interest still contains the name and is used to route in the normal way. It is only the Content Object on the return path which can have an empty name.

Therefore, section 8 should be modified to have a separate case when the interest gives a ContentObjectHashRestriction: "A Content Object satisfies an Interest if and only if the computed ContentObjectHash exactly equals the Interest ContentObjectHashRestriction, if given or (a) the Content Object name exactly matches the Interest name and (b) the ValidationAlgorithm KeyId of the Content Object exactly equals the Interest KeyIdRestriction, if given."

To spell it out, fetching with a manifest would work as follows:

  *   The consumer sends an Interest and receives a manifest Content Object in the normal way. The manifest contains the list of ContentObjectHash for all the parts.
  *   For each part, the consumer sends an Interest with the routable name to the producer and the ContentObjectHashRestriction from the manifest.
  *   A Forwarder receives this Interest and routes it to the producer in the normal way. Since the Interest has a ContentObjectHashRestriction, for Forwarder may index the PIT entry by the hash since this is how it will match the return Content Object.
  *   The producer receives the interest and returns a Content Object matching the ContentObjectHashRestriction. The Content Object only needs to have content. It does not need to echo back the name which is only for routing.
  *   A Forwarder receives this Content Object with an empty name, computes the ContentObjectHash and matches the Interest with the ContentObjectHashRestriction. It does not need to match on name. (This is the only change to the semantics.)
  *   The Forwarder optionally caches the Content Object in its Content Store. This has the advantage that it will match this Content Object against a future Interest with the same ContentObjectHashRestriction, *even if that Interest has a different name and is routing to a different producer.* For example, Alice has fetched the content for a popular video by routing interests to producer X and these are in the Content Store. Bob gets the manifest for the same video from a different producer, and sends the Interests with the listed ContentObjectHashRestriction. The Forwarder will reply to Bob from its Content Store, even though the Interests have a different routing name, because the ContentObjectHashRestriction says it's the same content. There's no need to forward the Interest to fetch the same content from a different producer.
  *   Similar arguments apply when multiple producers keep a mirror of historical or popular content. If a consumer can do one operation to get the routable prefix to a viable producer, then the mirror producer can serve the exact same thousands of Content Objects because they have no name and the network will return them by hash.

Thank you,
- Jeff T

On 2015/6/29, 13:35, "icnrg on behalf of [email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]> on behalf of [email-masked]<mailto:[email-masked]>> wrote:

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Information-Centric Networking Working Group of the IETF.

        Title           : CCNx Semantics
        Authors         : Marc Mosko
                          Ignacio Solis
Filename        : draft-irtf-icnrg-ccnxsemantics-00.txt
Pages           : 24
Date            : 2015-06-29

Abstract:
   This document describes the core concepts of the CCNx architecture
   and presents a minimum network protocol based on two messages:
   Interest and Content Object.  It specifies the set of mandatory and
   optional fields within those messages and describes their behavior
   and interpretation.  This architecture and protocol specification is
   independent of a specific wire encoding.

   The protocol also uses a Control message called an InterestReturn,
   whereby one system can return an Interest message to the previous hop
   due to an error condition.  It indicates to the previous hop that the
   current system will not respond to the Interest.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-icnrg-ccnxsemantics/

There's also a htmlized version available at:
https://tools.ietf.org/html/draft-irtf-icnrg-ccnxsemantics-00

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

_______________________________________________
icnrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/icnrg

---

From: David Oran <[email-masked]>
Date: Thu, 2 Jul 2015 09:04:28 -0400

I may be wrong, but I think I found a couple of holes, although the scenarios may be corner cases and unrealistic. See below.

> On Jul 2, 2015, at 4:56 AM, Thompson, Jeff <[email-masked]> wrote:
> 
On broadcast links, there is the possibility of passive listeners wanting to opportunistically cache data packets for which they have not received an interest. If they don’t receive the name, then they could only respond to a future interest with a hash restriction.

> 	• The consumer sends an Interest and receives a manifest Content Object in the normal way. The manifest contains the list of ContentObjectHash for all the parts.
> 	• For each part, the consumer sends an Interest with the routable name to the producer and the ContentObjectHashRestriction from the manifest.
> 	• A Forwarder receives this Interest and routes it to the producer in the normal way. Since the Interest has a ContentObjectHashRestriction, for Forwarder may index the PIT entry by the hash since this is how it will match the return Content Object.
I’m not certain this optimization is a win, if you mean trying to match the PIT on the *interest* as opposed to the returned data. Even if you have a content object hash restriction, if you have a PIT entry and no content object in the CS, I think you need to get the interest to the producer so it can respond with an authoritative NAK. However, I may be misunderstanding the wording here.

> 	• The producer receives the interest and returns a Content Object matching the ContentObjectHashRestriction. The Content Object only needs to have content. It does not need to echo back the name which is only for routing.
> 	• A Forwarder receives this Content Object with an empty name, computes the ContentObjectHash and matches the Interest with the ContentObjectHashRestriction. It does not need to match on name. (This is the only change to the semantics.)
while I think this works and does save bandwidth, there is somewhat of a computation vs. bandwidth tradeoff so it may or may not be a win overall.

> 	• The Forwarder optionally caches the Content Object in its Content Store. This has the advantage that it will match this Content Object against a future Interest with the same ContentObjectHashRestriction, *even if that Interest has a different name and is routing to a different producer.* For example, Alice has fetched the content for a popular video by routing interests to producer X and these are in the Content Store. Bob gets the manifest for the same video from a different producer, and sends the Interests with the listed ContentObjectHashRestriction. The Forwarder will reply to Bob from its Content Store, even though the Interests have a different routing name, because the ContentObjectHashRestriction says it's the same content. There's no need to forward the Interest to fetch the same content from a different producer. 
All true, and if you have enough confidence in the global resilience agains hash restrictions the name match is a waste. I wonder if we want to depend on this property - I’m not enough of a SHA256 expert to gauge the safety, and there’s also the question about debuggability and instrumentation.

> 	• Similar arguments apply when multiple producers keep a mirror of historical or popular content. If a consumer can do one operation to get the routable prefix to a viable producer, then the mirror producer can serve the exact same thousands of Content Objects because they have no name and the network will return them by hash.
> Thank you,
> - Jeff T
> 
> On 2015/6/29, 13:35, "icnrg on behalf of [email-masked]" <[email-masked] on behalf of [email-masked]> wrote:
> 
>> 
>> [email-masked]
> [email-masked]

---

From: "Thompson, Jeff" <[email-masked]>
Date: Thu, 2 Jul 2015 15:31:25 +0000

Hi Dave. Thanks for your feedback. See responses inline.

On 2015/7/2, 6:04, "David Oran" <[email-masked]> wrote:

>I may be wrong, but I think I found a couple of holes, although the
>scenarios may be corner cases and unrealistic. See below.
>
>> An Interest with a ContentObjectHashRestriction is typically used to
>>fetch the Content Objects from a manifest which lists all the contents
>>only by hash. In this case, the Interest only has a name for routing
>>purposes plus the ContentObjectHashRestriction from the manifest. Since
>>a manifest can be used for large content like video, it's likely that a
>>large portion (a majority?) of the Content Objects on the network will
>>be fetched by ContentObjectHashRestriction. Therefore, it is worth
>>clarifying the semantics of Content Object matching in this case.
>> 
>> Section 8 of draft-irtf-icnrg-ccnxsemantics-00.txt currently says "A
>>Content Object satisfies an Interest if and only if (a) the Content
>>Object name exactly matches the Interest name and (b) the
>>ValidationAlgorithm KeyId of the Content Object exactly equals the
>>Interest KeyIdRestriction, if given, and (c) the computed
>>ContentObjectHash exactly equals the Interest
>>ContentObjectHashRestriction, if given." But if the
>>ContentObjectHashRestriction is given in the Interest, then the name in
>>the Interest is only needed for routing the interest to the producer but
>>is not needed for matching since the hash specifies an exact match. On
>>the return path, the Content Object can have an empty name and can be
>>matched on the ContentObjectHash only, therefore saving space in the
>>Content Object for an unnecessary name. (See other advantages below for
>>omitting an unnecessary routing name in the Content Object.)
>> 
>> A typical objection for matching on hash only is that the Forwarder
>>would have to compute the hash of every incoming Content Object. But
>>this is not true. A Forwarder only needs to compute the
>>ContentObjectHash of an incoming Content Object with an empty name,
>>since in this case it could only match an Interest with a
>>ContentObjectHashRestriction. Another typical reaction when hearing
>>about matching on hash only is to say "fetching by hash is a flat name
>>space and routing on flat names does not scale." But this is a
>>misunderstanding. The Interest still contains the name and is used to
>>route in the normal way. It is only the Content Object on the return
>>path which can have an empty name.
>> 
>On broadcast links, there is the possibility of passive listeners wanting
>to opportunistically cache data packets for which they have not received
>an interest. If they don¹t receive the name, then they could only respond
>to a future interest with a hash restriction.

The use case I describe is for a data packet with an empty name. If the
data packet has an empty name, it is intended to only be matched by a hash
restriction. So in this case you are correct that the opportunistic cache
would only respond to a future interest with a hash restriction. That is
the intention for a data packet with an empty name.

>
>> Therefore, section 8 should be modified to have a separate case when
>>the interest gives a ContentObjectHashRestriction: "A Content Object
>>satisfies an Interest if and only if the computed ContentObjectHash
>>exactly equals the Interest ContentObjectHashRestriction, if given or
>>(a) the Content Object name exactly matches the Interest name and (b)
>>the ValidationAlgorithm KeyId of the Content Object exactly equals the
>>Interest KeyIdRestriction, if given."
>> 
>> 	€ The consumer sends an Interest and receives a manifest Content
>>Object in the normal way. The manifest contains the list of
>>ContentObjectHash for all the parts.
>> 	€ For each part, the consumer sends an Interest with the routable name
>>to the producer and the ContentObjectHashRestriction from the manifest.
>> 	€ A Forwarder receives this Interest and routes it to the producer in
>>the normal way. Since the Interest has a ContentObjectHashRestriction,
>>for Forwarder may index the PIT entry by the hash since this is how it
>>will match the return Content Object.
>I¹m not certain this optimization is a win, if you mean trying to match
>the PIT on the *interest* as opposed to the returned data. Even if you
>have a content object hash restriction, if you have a PIT entry and no
>content object in the CS, I think you need to get the interest to the
>producer so it can respond with an authoritative NAK. However, I may be
>misunderstanding the wording here.

In case there is no content object in the CS, then the Forwarder save the
interest in the PIT and forwards it to the producer in the normal way.
Normally the PIT is indexed on the name of the interest so that the
Forwarder can use the name in a received content object to look up the
interest in the PIT. But in the case I'm describing, the content object
has an empty name. So the forwarder hashes the content object and searches
the PIT for an interest with a matching ContentObjectHashRestriction. When
I say "the Forwarder may index the PIT entry by the hash" I should haves
said "by the ContentObjectHashRestriction of the interest". This is an
optional optimization to find the interest in the PIT more quickly.

>
>
>> 	€ The producer receives the interest and returns a Content Object
>>matching the ContentObjectHashRestriction. The Content Object only needs
>>to have content. It does not need to echo back the name which is only
>>for routing.
>> 	€ A Forwarder receives this Content Object with an empty name,
>>computes the ContentObjectHash and matches the Interest with the
>>ContentObjectHashRestriction. It does not need to match on name. (This
>>is the only change to the semantics.)
>while I think this works and does save bandwidth, there is somewhat of a
>computation vs. bandwidth tradeoff so it may or may not be a win overall.
>
>> 	€ The Forwarder optionally caches the Content Object in its Content
>>Store. This has the advantage that it will match this Content Object
>>against a future Interest with the same ContentObjectHashRestriction,
>>*even if that Interest has a different name and is routing to a
>>different producer.* For example, Alice has fetched the content for a
>>popular video by routing interests to producer X and these are in the
>>Content Store. Bob gets the manifest for the same video from a different
>>producer, and sends the Interests with the listed
>>ContentObjectHashRestriction. The Forwarder will reply to Bob from its
>>Content Store, even though the Interests have a different routing name,
>>because the ContentObjectHashRestriction says it's the same content.
>>There's no need to forward the Interest to fetch the same content from a
>>different producer.
>All true, and if you have enough confidence in the global resilience
>agains hash restrictions the name match is a waste. I wonder if we want
>to depend on this property - I¹m not enough of a SHA256 expert to gauge
>the safety, and there¹s also the question about debuggability and
>instrumentation.

Is there an attack based on the global resilience agains hash restrictions
in SHA256, which also wouldn't affect the hash in the digital signature?

>
>> 	€ Similar arguments apply when multiple producers keep a mirror of
>>historical or popular content. If a consumer can do one operation to get
>>the routable prefix to a viable producer, then the mirror producer can
>>serve the exact same thousands of Content Objects because they have no
>>name and the network will return them by hash.
>> Thank you,
>> - Jeff T
>> 
>> On 2015/6/29, 13:35, "icnrg on behalf of [email-masked]"
>><[email-masked] on behalf of [email-masked]> wrote:
>> 
>>>

---

From: "Thompson, Jeff" <[email-masked]>
Date: Thu, 2 Jul 2015 15:38:50 +0000

Hi again Dave. I missed one response (inline below).

>computation vs. bandwidth tradeoff so it may or may not be a win overall.

In the use case I describe there no new computation. If the interest has a
ContentObjectHashRestriction, the Forwarder is required to hash a content
object to match it.  And I emphasize that the Forwarder does *not* waste
computation automatically hashing *every* content object it receives. It
only automatically hashes a content object which has an empty name, which
is intended to be matched by a hash restriction (typically the parts from
a manifest that are listed by hash).  The Forwarder would have to hash the
content object anyway to fulfill the requirements of
ContentObjectHashRestriction. No new computation there. What do you have
in mind for a tradeoff with computation?

---

From: David Oran <[email-masked]>
Date: Thu, 2 Jul 2015 11:54:25 -0400

I think I mostly agree with your analysis but see inline.

> On Jul 2, 2015, at 11:38 AM, Thompson, Jeff <[email-masked]> wrote:
> 
I was saying that if you included the name, the forwarder could delay the hash verification until it gets an interest asking for the object by hash restriction, as opposed to having to do it when it gets the nameless object.