| Internet-Draft | FLIC | March 2025 |
| Tschudin, et al. | Expires 4 September 2025 | [Page] |
This document describes how to encode an application data objet into a structured manifest using Information Centric Networking (ICN) data objects, creating a File-Like ICN Collection (FLIC). The manifest is an "index table" of objects that make up the manifest itself and the application data. It records the hash value (content object hash) of each item so a consumer using the manifest may request each piece by a complete hash name. The manifest is hierarchical and may be encoded into realtively small ICN objects to fit within network MTU sizes. FLIC has several methods to guide a consumer in constructing appropriate Interest names based on the manifest. It also supports encryption of the manifest data. FLIC may be used in CCNx or Named Data Networking, or other ICNs.¶
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶
This Internet-Draft will expire on 4 September 2025.¶
Copyright (c) 2025 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.¶
ICN architectures, such as Content-Centric Networking (CCNx)[RFC8569] and Named Data Networking [NDN], are well suited for static content distribution. Each piece of (possibly immutable) static content is assigned a name by its producer. Consumers fetch this content using said name. Optionally, consumers may specify the full name of content, which includes its name and a cryptographic digest of said content, so the reques is self-verifying.¶
To enable requests with full names, consumers need a priori knowledge of content digests. A Manifest, a form of catalog, is a data structures commonly employed to store and transport this information. Typically, ICN manifests are signed content objects (data) which carry a collection of hash digests. As content objects, a manifest itself may be fetched by full name. A manifest may contain either hash digests of, or pointers to, either other manifests or content objects. A collection of manifests and content objects represents a large piece of application data, e.g., one that cannot otherwise fit in a single content object. Because a manifest contains a collection of hashes, it is by definition non-circular because one cannot hash the manifest before filling it in.¶
Structurally, this relationship between manifests and content objects is reminiscent of the UNIX inode concept with index tables and memory pointers. In this document, we specify a simple, yet extensible, manifest data structure called FLIC - File-Like ICN Collection. FLIC is suitable for ICN protocol suites such as CCNx and NDN. We describe the FLIC design, grammar, and various use cases, e.g., ordered fetch, seeking, de-duplication, extension, and variable-sized encoding. We also include FLIC encoding examples for CCNx and NDN.¶
The purpose of a manifest is to concisely name, and hence point to, the constituent pieces of a larger object. A FLIC manifest does this by using a root manifest to name and cryptographically sign the data structure and then use concise lists of hash-based names to indicate the constituent pieces. This maintains strong security from a single signature. A Manifest entry gives one enough information to create an Interest for that entry, so it must specify the name, the hash digest, and if needed, the locators.¶
FLIC is not an archive format, like tar or LTFS or iso. FLIC represents a single object that may be reconstructed by concatenating all the data pieces. Future extensions could define a new type of structure that aggregates multiple FLIC manifests into an archive.¶
FLIC is a distributed data structure illustrated by the following picture. The FLIC manifest is encoded in the Payload of a Content Object. A root manifest has a name and a publisher signature. Subsequent manifests, because they hare in a cryptographic hash tree using SHA256 pointers, do not need to be signed; they have implicit trust. In the figure we call out "data pointer" and "manifest pointer", but in the actual encoding they are all just hash values and the consumer does not necessarily know what it is fetching until it has fetched it.¶
A key design decision is how one names the root manifest, the application data, and subsidiary manifests. FLIC uses the concept of a Name Constructor. The root manifest (in fact, any FLIC manifest) may include a Name Constructor that instructs a manifest reader how to properly create Interests for the associated application data and subsidiary manifests. The Name Constructors allow interest construction using a well-known, application-independent set of rules. Some name constructor forms are tailored towards specific ICN protocols, such as CCNx or NDN; some are more general and could work with many protocols. We describe the allowed Name Constructor methods in Section 3.3. There are also particulars of how to encode the name schema in a given ICN protocol, which we describe in Section 3.9.¶
FLIC has encodings for CCNx (Section 3.9.1) as per [RFC8609] and for NDN (Section 3.9.2). For the implementor, the section Section 3.9.1.5 succintly defines the CCNx TLV structures and the format of each TLV value.¶
An example implementation in Python may be found at [ccnpy].¶
FLIC enables experimentation with how to structure and retrieve large data objects in ICN. By having a common data structure applications can rely on, with a common library of code that can be used to create and parse manifest data structures, applications using ICN protocols can both avoid unnecessary reinvention and also have enhanced interoperability. Since the design attempts to balance simplicity, universality, and extensibility, there are a number of important experimental goals to achieve that may wind up in conflict with one another. We provide a partial list of these experimental issues in Section 4. It is also important for users of FLIC to understand that some flexibility and extensions might be removed if use cases do not materialize to justify their inclusion in an eventual standard.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
The FLIC design adopts the proven UNIX inode concept of direct and indirect pointers, but without the specific structural forms of direct versus indirect. FLIC is a collection of pointers, and when one de-references the pointer it could be an application object or another FLIC manifest. The pointers in FLIC use hash-based naming of Content Objects analogous to the function block numbers play in UNIX inodes.¶
Because FLIC uses hash-based pointers as names, FLIC graphs are inherently acyclic. Both CCNx and NDN support hash-based naming, though the details differ (see Section 3.9.1 and Section 3.9.2 ).¶
The FLIC data structure is an acyclic digraph of Content Objects. In this document, our examples are mostly trees, but that is not a requirement. For example, a de-duplication representation might have a common object or common sub-graph that is referenced from multiple parents in the tree. As another example, there could be a common sub-collection of objects organized in a Manifest, and that sub-manifest could be included in multiple places. Each node has a total order of all its children and they are visited in a specific traversal order. This leads to an unambiguous traversal even if a node has multiple in-edges.¶
A FLIC manifest graph does not need to have a unique root. When a publisher initially creates a FLIC manifest, it likely creates a unique root manifest. Over time, however, there may be additional root manifests. These could be used to update the root (e.g. replace an expired key or use a new certificate). Or the root might be renamed, or new locators used because the location of the data changed. An updated root might even point to the prior roots to maintain a history or access to prior cryptographic signatures or co-signatures.¶
In FLIC terms, a direct pointer links to application-level data, which is a Content Object with application data in the Payload. An indirect pointer links to a Content Object with a FLIC Manifest in the Payload. There is no distinction in the manifest between these two types of pointers.¶
A publisher creating a FLIC manifest may choose one of many permissible acyclic graph structures. Some examples are:¶
As an example of choosing graph structure, the [ccnpy] implementation has a TreeOptimizer
that calculates an optimal number of indirect and direct pointers per manifest node, given the limitations
of a maximum object size and the overhead of necessary fields in each manifest object.
The optimizer will find a set of tree parameters that minimizes the tree height and
minimizes the number of wasted pointers due to the size of the application data.¶
A RECOMMENDED FLIC structure is to use a distinguished root manifest with exactly one pointer to the top manifest of a regular n-ary graph. The root manifest is signed by the publisher and contains links to certificates or public keys. It also specifies the Name Constructors used in the manifest. If using RSA-OAEP key wrapping, it contains the wrapped key. These one-time data structures take significant space, so off-loading them to the root manifest is needed to use a regular n-ary graph for the rest of the manifest. In CCNx, the root manifest is the only one in the graph that needs to have a name if using nameless objects.¶
This method allows an intermediary service to respond to client requests with its own signed root Manifest that then points to the original root manifest. The client trusts the intermediary's response because of the intermediary's signature, and then trusts the content because of the Root manifest. In some cases, the intermediary could embed the original root manifest and avoid additional round trips before beginning download. This technique is used in a peer-to-peer sharing protocol [ProjectOrigin].¶
FLIC supports manifest encryption separate from application payload encryption (See Section 3.8). It has a flexible encryption envelope to support various encryption algorithms and key discovery mechanisms. The byte layout allows for in-place encryption and decryption.¶
A limitation of this approach is that one cannot construct a hash-based name for a child until one knows the payload of that child. In practical terms, this means that one must have the complete application payload available at the time of manifest creation. One workaround is to batch publication of a block of data, then extend that manifest tree as the top-left-child of a subsequent manifest tree. This results in multiple, signed, root manifests with two pointers (to the prior root manifest and the new manifest tree).¶
FLIC's design allows straightforward applications that just need to traverse a set of related objects. FLIC has two extensibility mechanisms that allow for more sophisticated uses: manifest metadata, and pointer annotations. These are described in Section 3.4 and Section 3.5 respectively.¶
FLIC goes to considerable lengths to allow creation and parsing by application-independent library code. Therefore, any options used by applications in the data structure or encryption capabilities MUST NOT require applications to have application-specific Manifest traversal algorithms to correctly re-construct the original data. This ensures that such application agnostic libraries can always successfully parse and traverse any FLIC Manifest by ignoring the optional capabilities. An application MAY include optimization or other hints to allow an application to use that data in different ways.¶
The reader may find it useful to refer to Section Example Usages (Appendix A) from time to time to see worked out examples.¶
Node section of a manifest holds the manifest information. It has
node-wide metadata in a NodeData section, and then a series of HashGroups
.¶
Node that is encrypted as specified in the Manifest's SecurityCtx.
It is opaque octets.¶
Locators are routing hints used by forwarders to get an Interest to a node in the network that can resolve the Interest's name. In some naming conventions, the name might only be a hash-based name so the Locator is the only available routing information. Locators exist in both CCNx and NDN, though the specific protocol mechanisms differ. A FLIC manifest represents locators in the same way for both ICN protocols inside Name Constructors (Section 3.3), though they are encoded differently in the underlying protocol. See Section 3.9 for encoding differences.¶
CCNx only uses locators with nameless objects, whereas NDN may use multiple ForwardingHints per interest.¶
A name constructor definition may define one or more Locator prefixes that can be used in the construction of Interests from the pointers in the manifest. The Locators are inherited when walking a manifest tree, so they do not need to be defined everywhere. It is RECOMMENDED that only the Root manifest contain Locators so that a single operation can update the locators. One use case when storing application payloads at different replicas is to replace the Root manifest with a new one that contains locators for the current replicas.¶
A manifest organizes pointers inside Hash Groups. Each Hash Group uses an NCID to indicate what Name Constructor to use to generate the name of an Interest for pointers inside that Hash Group.¶
A Manifest may define zero or more name constructors in Name Constructor Definitions (NCDs) located in the Manifest Node. An NCD associates a Name Constructor Id (NCID) to a Name Constructor definition. The NCID is used in other parts of the Manifest to refer to that specific definition.¶
A name constructor definition, NcDef, is placed in a NodeData field.
An NcDef applies to that Node and all subsequent nodes along that manifest branch,
until superceded by a new NcDef with the same NcId. A subsequent NcDef
applies from that point onward in the manifest branch. It does not affect its ancestors.¶
In a non-tree FLIC graph, a node may have multiple parents, with different NcDef for
the same NcId (i.e. parent 1 has NcDef A for the NcID and
parent 2 has NcDef B for the same NcID). This is allowed.
A consumer traversing the tree performs a specific
traversal order. It must apply its current branch's name constructor to its visited children.
Of course, if a consumer has already visited a sub-tree, it likely already has the hash named
objects fetched and does not need to re-fetch them.¶
A common practice is to have the manifest nodes in one namespace and the application data objects
in a different namespace. For example, ccnx:/foo/photo.jpg/manifest/ManifestId=N for a manifest tree and
ccnx:/foo/photo.jpg/Chunk=M for the application data. Or if using nameless objects, the manifest
tree and data objects might have different locators. In these cases, a FLIC manifest usually has
two name constructor definitions (e.g. NCID 0 for the data and NCID 1 for the manifest tree). This results
in the direct pointers being in one hash group and then the indirect pointers being in a second
hash group.¶
If a traversal of a FLIC manifest encounters an unknown NCID, the RECOMMENDED action is to report a malformed manifest to the user and abort the traversal.¶
It is RECOMMENDED to have NcDef fields only in the root or top manifest.
It is RECOMMENDED to not re-define NcId values within the same manifest.¶
An explicit name constructor has an NcDef in a NodeData and a corresponding NcId
in a HashGroup.
NcId 0 is a special NCID that may be used implicitly.¶
NCID 0 is an implicit name constructor. If a Hash Group does not have a GroupData
with an NcId element, it is assumed to use NCID 0.¶
NCID 0 has an implicit definition as a Hash Schema. If NCID 0 has no NcDef, it is
assumed to be a HashSchema with no locators. It is RECOMMENDED to define NCID with Locators
to avoid repeatedly defining locators elsewhere.¶
It is more efficient, encoding-wise, to always have an NcDef for NCID 0 (if it is used) that enumerates
its Locators once rather than having to put them in each NodeData or GroupData.¶
NCID 0 MAY be re-defined as any name constructor type. It does not need to remain a Hash Schema.
In this case, a publisher may be able to omit a GroupData for a group that uses NCID 0,
or at least omit the 5 bytes of an NcId field within a GroupData.¶
FLIC defines the following types of Name Constructors. Additional name constructor types may be specified in a subsequent revision of the specification. The section Section 3.6 specifies the encoding of each name constructor.¶
Locators
of the NcDef, or the HashGroup, or the NodeData, in that order
if the more specific definition does not exist. CCNx can only use one locator per Interest (in the Name),
so if there are more than one available Locator, it must choose one, such as in the order listed.¶
NcDef> specifies a name, which will appear in every content object for that
name constructor. The consumer uses it in an interest with the appropriate hash. The NCD
may specify locators, which NDN uses as ForwardingHints. They are not used by CCNx, as
these are not nameless objects. In Prefix Schema, all object have an identical name and
are only differentiated by their hash.¶
StartSegmentId field in the HashGroup or use
a SegmentIdAnnotation for each pointer. The consumer will use
the Name in the NcDef as a prefix, append a TLV of the given
type, and set the TLV value to the segment ID. The resulting name is used
in the Interest. For NDN, Locators may also be used as Forwarding Hints.¶
The Segmented Prefix schema uses a different name in all Content Objects and distinguishes them via their ContentObjectHash. Note that in CCNx, using a SegmentedPrefixSchema means that only the Root Manifest has a Locator for the Segmented Prefix (minus the segment ID).¶
The consumer must determine the segment ID to use in the name. Typically, the application data would use a chunk number in the content name, which is a compact sequence number. These could be computed based on the in-order traversal, assuming one knows which manifests point to data versus other manifests. Manifests, however, may not use a compact sequence number and there is no simple way to predict the names.¶
The SegmentedSchema uses a name component suffix to distinguish each content object.
This name component will be of type SuffixComponentType. In CCNx, this would
be a ChunkNumber or ManifestId type (T_MANIFEST_ID is defined in
this document's IANA section (Section 5)), though one may specify different types.
The reason for specifying the
SuffixComponentType in the name definition is that application data would
typically use chunked names with sequential identifiers and the FLIC manifest tree
would typically use the ManifestId.¶
A publisher may name the manifest tree and the application data as desired, as long
as the consumer can generate the required Interest names. FLIC provides two mechanisms:
AnnotatedPointers and StartSegmentId. One could use an annotated pointer
to specify the exact name or name suffix for each pointer, so the consumer does not
need to calculate anything; it simply uses the name specified. The downside is there
is an annotation for each pointer, which reduces the number possible pointers in a
given MTU. The StartSegmentId is a single integer per hash group that indicates the
beginning ID for the pointer array. The consumer calculates each pointer's name suffix
from the start segment ID plus pointer offset, and then wraps it in a name component
of type SuffixComponentType.¶
Because FLIC uses a preorder tree traversal, the node IDs of a manifest's children
in the traversal order are not compact. They will skip around based on the preorder recursion. This means one
needs a different ID for each manifest if one wants to use the StartSegmentId
hint. A publisher may use any form of integer ID in the ManifestId name
component so long as it is locally (within a hash group) sequential and globally
unique.¶
As an example, the [ccnpy] implementation uses the regular k-ary tree IDs per tree height as the manifest IDs (where k is the number of allowed indirect pointers per manifest). These are globally unique and locally sequential for all the children of a manifest.¶
There are two methods to guide a consumer in generating segment IDs for hash pointers:¶
SegmentIdAnnotation (see Section 3.5),
the consumer MUST use that segment ID for the pointer.¶
StartSegmentId parameter, then the segment ID of each pointer
is calculated the StaretSegmentId plus the offset of the pointer from the first
pointer of the Hash Group. Pointers with a SegmentIdAnnotation still count against
the offset even though the annotation takes precedence.¶
As an example, consider the manifest shown in Figure 2. The Interests generated, in order, have these names and hash restrictions. We have used short example hash values for the sake of clarity.¶
/foo/7=10, hash=0x0001¶
/foo/7=20, hash=0x0002¶
/foo/7=12, hash=0x0003¶
/bar/8=0, hash=0x0004¶
/bar/8=1, hash=0x0005¶
/bar/8=2, hash=0x0006¶
Meanifest
Node
NodeData
NcDef NcId 1 SegmentedSchema Name '/foo' SuffixComponentType 7
NcDef NcId 2 SegmentedSchema Name '/bar' SuffixComponentType 8
HashGroup
GroupData NcId 1 StartSegmentId 10
AnnotatedPtrs
PointerBlock
Ptr HashValue(0x0001)
Ptr HashValue(0x0002) SegmentIdAnnotation(20)
Ptr HashValue(0x0003)
HashGroup
GroupData NcId 2 StartSegmentId 0
Ptrs
HashValue(0x0004)
HashValue(0x0005)
HashValue(0x0006)
Every group of a segmented NcId MUST have either a GroupData with a StartSegmentId, or use annotated pointers with SegmentIdAnnotation.¶
A producer MUST ensure that a segment ID names exactly one data item. That is, the
producer MUST NOT duplicate the segment ID in an object name for
a different object. The object hash MUST be the same for the same segment
ID of a name, within the longest of the ExpiryTime of the manifest or the named object.
In other words, there is a one-to-one correspondence between a segment ID and a hash
for the lifetime of the manifest and the constituent objects.
Note that a consumer should not assume this is true, as a bad actor could
violate this rule. A consumer should only assume the uniqueness of cryptographic hashes.¶
It is allowed to have multiple manifest entries with the same segment ID (see below).¶
While a producer MAY mix using GroupData StartSegmentId and
SegmentIdAnnotation, we in general do not consider that a good idea. It is up to the
manifest producer to ensure that every segment may be fetched, and fetch in the right
order. Segments, when fetched in the manifest order reconstruct the
original data.¶
Let us make this clear, the original data is constructed by the in-order manifest traversal, not the segment ID order. The consumer should make no assumptions about reconstructing the original data and the names of those data elements.¶
A consumer MAY skip fetching some segments. A consumer MAY> fetch segments in any order it chooses. It may skip around or omit segments.¶
A manifest MAY have multiple pointers to the same segment ID (and thus same hash). This can be used for data de-duplication, e.g. multiple occurrences of the same binary string within the reconstructed data object. If the producer uses this method, then the original data cannot be reconstructed by simply fetching the segment IDs in order.¶
The FLIC Manifest may be extended by defining TLVs that apply to the Manifest as a whole, or alternatively, individually to every data object pointed to by the Manifest. This basic specification does not specify any, but metadata TLVs may be defined through additional RFCs or via Vendor TLVs. FLIC uses a Vendor TLV structure identical to [RFC8609] for vendor-specific annotations that require no standardization process.¶
For example, some applications may find it useful to allow specialized consumers such as repositories (for example [repository]) or enhanced forwarder caches to pre-place, or adaptively pre-fetch data in order to improve robustness and/or retrieval latency. Metadata can supply hints to such entities about what subset of the compound object to fetch and in what order.¶
It is RECOMMENDED that the root manifest have a SubtreeDigest
field in the NodeData with the cryptographic hash of the entire application data. This allows the
manifest consumer to validate that the final reconstructed data is correct.¶
A consumer SHOULD validate the outer-most SubtreeDigest, if any. If this digest
does not validate, a consumer SHOULD validate nested SubtreeDigest or LeafDigest
to help pinpoint where there is a discrepancy.¶
As an example, a publisher might include a SubtreeDigest in the root manifest NodeData
and then a LeafDigest in every manifest with direct pointers. It is not necessary to validate every
LeafDigest if the overall SubtreeDigest checks. If the SubtreeDigest does not check,
then the consumer could locate where the problem is by validating the LeafDigests.¶
A consumer SHOULD inform the user when a digest does not validate.¶
A discrepancy in a digest should be considered an error condition.¶
The SubtreeSize and LeafSize fields are provided to help a consumer seek
through a manifest to specific locations. They are not intended to validate the application
data.¶
A consumer MAY compare the sizes in SubtreeSize and LeafSize to
the true application payload sizes retrieved from the manifest nodes and report any discrepancies to
the user.¶
FLIC allows each manifest pointer to be annotated with extra data. Annotations allow
applications to exploit metadata about each Data Object pointed to without having to first
fetch the corresponding Content Object. This specification defines three annotations:
SizeAnnotation, SegmentIdAnnotation, and LinkAnnotation.¶
The SizeAnnotation specifies the number of application layer octets covered by
the pointer.¶
The SegmentIdAnnotation is a unique suffix for the pointer for use with the
Segmented Schema name constructor. Using annotations allows non-sequential segment IDs,
which could happen if manifest trees are named in the traversal order. See
Section 3.3.3 details on using the annotation.¶
The LinkAnnotation is a link to be used to name the pointer (less the pointer
itself). For NDN, the pointer would be appended to the name for a complete name. In CCNx,
the name would be used in the Interest along with the pointer in the
ContentObjectHashRestriction field. The link may include a KeyId restriction.¶
Other annotation may, for example, give hints about a desirable traversal order for fetching the data, or an importance/precedence indication to aid applications that do not require every content object pointed to in the manifest to be fetched. This can be very useful for real-time or streaming media applications that can perform error concealment when rendering the media.¶
Additional annotations may be defined through additional specifications or via Vendor TLVs.¶
The manifest grammar is mostly, but not entirely independent of the ICN protocol used to encode and transport it. The TLV encoding therefore follows the corresponding ICN protocol, so for CCNx FLIC uses 2 octet length, 2 octet type and for NDN uses the 1/3/5 octet types and lengths (see [NDNTLV] for details). There are also some differences in how one structures and resolves links. [RFC8609] defines HashValue and Link for CCNx encodings. The NDN ImplicitSha256DigestComponent defines HashValue and NDN Delegation (from Link Object) defines Link for NDN. Section 3.9 below specifies these differences.¶
The basic structure of a FLIC manifest comprises a security context, a node, and an
authentication tag. The security context and authentication tag are not needed if the node
is unencrypted. A node is made up of a set of metadata, the NodeData, that
applies to the entire node, and one or more HashGroups that contain pointers.¶
The NodeData element defines the namespaces used by the manifest. There may be
multiple namespaces, depending on how one names subsequent manifests or data objects. Each
HashGroup may reference a single namespace to control how one forms Interests from
the HashGroup. If one is using separate namespaces for manifests and application
data, one needs at least two hash groups. For a manifest structure of "MMMDDD," (where M
means manifest (indirect pointer) and D means data (direct pointer)) for example, one
would have a first HashGroup for the child manifests with its namespace and a
second HashGroup for the data pointers with the other namespace. If one used a
structure like "MMMDDDMMM," then one would need three hash groups.¶
TYPE = 2OCTET / {1,3,5}OCTET ; As per CCNx or NDN TLV
LENGTH = 2OCTET / {1,3,5}OCTET ; As per CCNx or NDN TLV
Manifest = T_FLIC_MANIFEST LENGTH
[SecurityCtx] (EncryptedNode / Node) [AuthTag]
SecurityCtx = T_SECURITY_CTX LENGTH AlgorithmCtx
AlgorithmCtx = AEADCtx / RsaWrapCtx
AuthTag = T_AUTH_TAG LENGTH *OCTET ; e.g. AEAD authentication tag
EncryptedNode = T_ENCRYPTED_NODE LENGTH *OCTET ; Encrypted Node
Node = T_NODE LENGTH [NodeData] 1*HashGroup [Pad]
NodeData = T_NODE_DATA LENGTH [SubtreeSize] [SubtreeDigest]
[Locators] 0*Vendor 0*NcDef
SubtreeSize = T_SUBTREE_SIZE LENGTH INTEGER
SubtreeDigest = T_SUBTREE_DIGEST LENGTH HashValue
Pad = T_PAD LENGTH 0*OCTET ; as per RFC8609
NcDef = T_NCDEF LENGTH NcId NcSchema
NcId = T_NCID LENGTH INTEGER
NcSchema = InterestDerivedSchema / DataDerivedSchema /
PrefixSchema / SegmentedSchema / HashSchema
InterestDerivedSchema = TYPE LENGTH [ProtocolFlags]
DataDerivedSchema = TYPE LENGTH [ProtocolFlags]
PrefixSchema = T_PrefixSchema LENGTH Name [Locators] [ProtocolFlags]
SegmentedSchema = T_SegmentedSchema LENGTH Name SuffixComponentType
[Locators] [ProtocolFlags]
SuffixComponentType = T_SUFFIX_TYPE LENGTH 1*OCTET
HashSchema = T_HashSchema LENGTH Locators [ProtocolFlags]
Locators = T_LOCATORS LENGTH 1*Locator
HashValue = TYPE LENGTH *OCTET ; As per ICN Protocol
Locator = TYPE LENGTH Link ; Link As per ICN protocol
ProtocolFlags = T_PROTOCOL_FLAGS LENGTH *OCTET
; ICN-specific flags, e.g. must be fresh
HashGroup = T_HASH_GROUP LENGTH [GroupData] (Ptrs / AnnotatedPtrs)
Ptrs = T_PTRS LENGTH *HashValue
AnnotatedPtrs = T_ANNOTATED_PTRS LENGTH *PointerBlock
PointerBlock = T_PTR_BLOCK LENGTH *Annotation Ptr
Ptr = T_PTR LENGTH HashValue
Annotation = SizeAnnotation / SegmentIdAnnotation /
LinkAnnotation / Vendor
SizeAnnotation = T_ANN_SIZE LENGTH Integer
SegmentIdAnnotation = T_ANN_SEGMENT_ID LENGTH Integer
LinkAnnotation = T_LINK LENGTH Link
Vendor = T_ORG LENGTH PEN *OCTET
PEN = 3OCTET ; IANA Private Enterprise Number
GroupData = TYPE LENGTH [NcId] [LeafSize] [LeafDigest]
[SubtreeSize] [SubtreeDigest] [StartSegmentId]
[Locators] 0*Vendor
LeafSize = T_LEAF_SIZE LENGTH INTEGER
LeafDigest = T_LEAF_DIGEST LENGTH HashValue
StartSegmentId = T_START_SEGMENT_ID LENGTH Integer
AEADCtx = T_AEAD_CTX LENGTH AEADData
AEADData = KeyNum AEADNonce AEADMode [KDFData]
KeyNum = T_KEYNUM LENGTH INTEGER
AEADNonce = T_NONCE LENGTH 1*OCTET
AEADMode = T_AEADMode LENGTH (AEAD_AES_128_GCM / AEAD_AES_256_GCM /
AEAD_AES_128_CCM / AEAD_AES_128_CCM)
; RFC5116 definitions
KDFData = T_KDF_DATA LENGTH KDFAlg [KDFInfo]
KDFAlg = T_KDF_ALG LENGTH INTEGER
; IANA "HPKE KDF Identifiers" [RFC9180]
KDFInfo = T_KDF_INFO LENGTH 1*OCTET
; Passed to the KDF Info
RsaOaepCtx = T_RSAOAEP_CTX LENGTH RsaOaepData
RsaOaepData = AEADData [RsaOaepWrapper]
RsaOaepWrapper = KeyId [KeyLink] HashAlg WrappedKey
; KeyId as pre RFC8609 for CCNx
; KeyLink as pre RFC8609 for CCNx
HashAlg = T_HASH_ALG LENGTH alg_number
; alg_number from IANA "CCNx Hash Function Types"
WrappedKey = T_WRAPPED_KEY LENGTH RsaOaepEnc{4OCTET 1*OCTET}
; Encrypted 4-byte salt plus AES key
EncryptedNode. The structure will depend
on the specific encryption algorithm.¶
As mentioned in the introduction, FLIC uses a directed acyclic graphs that is not necessarily a tree. A tree requires a unique path to each node. FLIC allows multiple pointers to the same subtrees or application data.¶
The FLIC traversal rule for a given manifest is to visit each of its Hash Groups, in
order, and within each Hash Group to visit each pointer, in order. It is a left-to-right reading
of the pointers. We will use the term "child" for each pointer in a FLIC Node, where
each child has an implicit order based on its position with a hash group, and the order of the
hash groups within the node.¶
If the FLIC manifest is a tree, and all direct pointers occur before all indirect pointers,
then the traversal is pre-order. This is the RECOMMENDED encoding order, as it minimizes
the time to the first application data object (assuming one is not using leaf-only storage).¶
The pre-order encoding and decoding of a FLIC manifest works even if the manifest is not a tree. The [ccnpy] README file has examples of data de-duplication where both manifest nodes and application data nodes are de-duplicated and appear more than once in the traversal. There is no special encoding or decoding: it is all pre-order, but it does not build a tree.¶
FLIC manifests use a pre-order traversal. This means pointers are read top to bottom, left
to right. The algorithms in Figure 4 show the pre-order forward
traversal code and the reverse-order traversal code, which we use below to construct
such a graph. This document does not mandate how to build FLIC graphs. The function visit(node)
means to enumerate the direct pointers of the node before the loop visits the indirect pointers.
Appendix B provides a detailed example of building FLIC graphs.¶
preorder(node)
if (node = null)
return
visit(node)
for (i = 0, i < node.child.length, i++)
preorder(node.child[i])
reverse_preorder(node)
if (node = null)
return
for (i = node.child.length - 1, i >= 0, i-- )
reverse_preorder(node.child[i])
visit(node)
In terms of the FLIC grammar, one expands a node into its hash groups, visiting each hash group in order. In each hash group, one follows each pointer in order. Figure 5 shows how hash groups inside a manifest expand like virtual children in the tree. The in-order traversal is M0, HG1, M1, HG3, D0, D1, D2, HG2, D3, D4.¶
Using the example manifest tree shown in Figure 25, the in-order traversal would be: Root, M0, M1, D0, D1, D2, M2, D3, D4, D5, M3, D6, D7, D8.¶
This document specifies two encryption modes. The first is a preshared key mode, where the parties are assumed to have the decryption keys already. It uses AES-GCM or AES-CCM. This is useful, for example, when using a key agreement protocol such as CCNxKE [I-D.wood-icnrg-ccnxkeyexchange]. The second is an RSA key wrapping mode using RSA-OAEP, similar to [RFC8017]. This may be used for group keying.¶
Additional modes may be defined in subsequent specifications. We expect that an RSA-KEM mode and Elliptic Curve mode should be specified.¶
To distribute a decryption key with the manifest itself, FLIC uses RSA-OAEP to wrap the WrappedKey
element. This specification only details the pertinent aspects of the encryption. It
describes how a consumer locates the appropriate keys in the ICN namespace. It does not
specify aspects of a key manager which may be used as part of key distribution
and management, nor does it specify the protocol between a key manager and a publisher. In
its simplest form, the publisher could be the key manager, in which case there is no
extra protocol needed between the publisher and key manager.¶
The manifest is always encrypted with an AEAD algorithm. The difference between the preshared key mode and the RSA wrapped mode is how the parties communicate the AES decryption key. The RSA OAEP mechanism facilitates the distribution of the shared key without an on-line key agreement protocol like (the expired draft) CCNxKE [I-D.wood-icnrg-ccnxkeyexchange].¶
This mechanism uses AES-GEM [NIST-800-38D] or AES-CCM [RFC3310] for manifest encryption. A publisher creating a SecurityCtx
SHOULD use the mechanisms in [RFC6655] for AES-CCM IV generation
and [RFC5288] for AES-GCM IV generation.¶
When the publisher and consumer establish the KeyNum, they SHOULD
also establish a salt. This results in a 4-byte salt and 8-byte nonce. If no salt
exists, the AEADNonce may be the entire IV.¶
The scope of the KeyNum is upto the publisher and consumer agreement. It may
be for a specific manifest, or a specific session (e.g. a CCNxKE session), or some
longer period. FLIC does not specify how the publisher and consumer agree on shared
keys, their lifespan, or scope. See the Section 6 section for a
discussion.¶
As these references specify, the publisher MUST use unique nonces on each Manifest that uses the same key or derived KDF key. A publisher MAY use the mechanisms of Section 3.2 of [RFC5116] for nonce generation (what we cal "salt" is termed "fixed-common" therein).¶
The AEAD Mode uses [RFC5116] defined symbols AEAD_AES_128_CCM, AEAD_AES_128_GCM, AEAD_AES_256_CCM and AEAH_AES_256_GCM to specify the key length and algorithm.¶
The KeyNum identifies a key on the receiver. The key MUST be
exactly of the length specific by the Mode. Many receivers may have the same key with
the same KeyNum.¶
The publisher MAY use a KDF for the manifest. If KDFData is
present, the consumer MUST derive a manifest-specific key from the shared
key identified by KeyNum. The KDFAlg is taken from the IANA registry
for [RFC9180]. If KDFInfo is present, the consumer uses that
string as in the KDF's info parameter. If the KDFInfo is not present,
then the consumer must use the Name TLV of the enclosing Content Object. This
option is only possible for Segmented Schema name constructors, where each
manifest has a unique name. If the publisher and consumer have agreed on a salt to be
associated with the key for use in the AEAD algorithm, this salt should not be used in
the KDF. The publisher and consumer may agree on a separate random salt as part of their
key agreement on the KeyNum for use in the KDF.¶
Within a single manifest tree, a publisher MAY use the same KDFData
and KDFInfo over multiple manifests, so long as it uses unique Nonce.
This allows a consumer to cache a single derived key based on the (KeyNum, KDFInfo)
pair. This is the normal use of the KDF mode: the publisher only needs to track a single
unique value for each manifest using KeyNum, not all the individual Nonces used
with in a manifest tree. If the publisher uses a sequence number or timestamp, it does
not even need to record previous KDFInfo, so long as they are unique.¶
When a Consumer reads a manifest that specifies a KeyNum, the consumer SHOULD
verify that the Manifest's publisher is an expected one for the KeyNum's usage. This
trust mechanism employed to ascertain whether the publisher is expected is beyond the
scope of this document, but we provide an outline of one such possible trust mechanism.
When a consumer learns a shared key and KeyNum, it associates that KeyNum
with the publisher ID used in a public key signature. When the consumer receives a
signed manifest (e.g. the root manifest of a manifest tree), the consumer matches the
KeyNum's publisher with the Manifest's publisher.¶
Each encrypted manifest node has a full security context (KeyNum, Nonce,
Mode). The AEAD decryption is independent for each manifest so Manifest objects
can be fetched and decrypted in any order. This design also ensures that if a manifest
tree points to the same subtree repeatedly, such as for deduplication, the decryptions
are all idempotent.¶
If KDFData is present, one derives a manifest-specific key as:¶
KDFInfo is present, the TLV (not just the value) is used as the
Label below. Otherwise, the Content Object Name TLV (including type type
and length fields) is used as the Label. If the content object does not have
a name, it is an error.¶
FixedInfo = "FLIC" || KeyNum || AEADMode || Label, where KeyNum
and AEADMode are the respective TLVs (including type and length).¶
Salt. Otherwise, the KDF's default salt is used.¶
bits of the KDF output to satisfy the
AEADMode key length (typically 128 or 256 bits).¶
To encrypt a Manifest, the publisher:¶
SecurityCtx or AuthTag from the Manifest.¶
SecurityCtx and adds it to the Manifest.¶
KDFData is present, derives a key as above.¶
AuthTag to the end of the Manifest, increasing the
Manifest's length¶
EncryptedNode.¶
To decrypt a Manifest, the consumer:¶
KeyNum exists and the publisher is trusted for that
KeyNum.¶
AuthTag and removes it from the Manifest, decreasing the Manifest
length.¶
EncryptedNode type to Node.¶
KDFData is present, derives a key as above.¶
AuthTag.¶
The RsaOaepCtx> mode uses RSA-OAEP (see Section 7.1 of [RFC8017] and [NIST-800-56Br2]) to encrypt a symmetric key
that is used to encrypt the Manifest. We call this RSA public key the Key Encryption Key (KEK)
and the consumer has the private key. A separate key distribution system is
responsible for distributing the KEK. The publisher MAY include a
KeyLink to help a consumer find the corresponding private key, such as from a
key distribution service. An ICN system may use the RSA-OAEP mode as part of a group keying
protocol. Key distribution and group keying are both beyond the scope of FLIC.¶
This usage of RSA-OAEP is intended to be compliant with KTS-OAEP [NIST-800-56Br2]. See Section 6.4 for a discussion of compliance with NIST recommendations.¶
T_RSA_WRAP_CTX uses RSA-OAEP [RFC8017] with mask
generation function MGF1 [RFC8017] and the specified hash algorithm.
The hash algorithm number is taken from the IANA registry "CCNx Hash Function Types,"
which are all NIST approved hash functions.¶
The RsaOaepData includes an AEADData that indicates how to use the
wrapped key to decrypt the manifest. It optionally includes the wrapped key itself. A
publisher using RsaWrapCtx MUST include the optional wrapped key
information in the first manifest node that uses it. The publisher MAY
include the wrapped key in other manifest nodes. It MUST use distinct
KeyNum for distinct WrappedKey.¶
The RSA-OAEP KeyNum is only significant within a given manifest.¶
The AEADData MAY include a KDFData element, in which
case it is used the same was as with AEAD Mode.¶
In a typical usage, the publisher would begin encryption at the root manifest. It must
include the full WrapedData here, as it is the first usage of the KeyNum.
In subsequent manifests, the publisher may only include the AEADData in the
RsaOaepData to save space.¶
The KeyId identifies the KEK. If the consumer already has the private key
corresponding to KeyId locally, it does not need to fetch it from the
KeyLink. The KeyId is similar to the Content Object KeyId field [RFC8609].¶
The symmetric key MUST be one that is compatible with the AEAD Mode, i.e. a 128-bit or 256-bit random number. Further, the symmetric key MUST fit in the OAEP envelope. Note that for a 128-bit key (16 bytes) plus a 4-byte salt requires a minimum 688-bit RSA key and a 256-bit key requires a minimum 816-bit RSA key. So in practical terms, a 1024-bit RSA key is the minimum for the RSA-OAEP encryption with a SHA-256 hash algorithm (it is recommended to use at least 2048-bit RSA keys [NIST-800-131Ar2]).¶
Any group key protocol and system needed are outside the scope of this document. We assume there is a Key Manager (KM) and a Publisher (P) and a set of group members. Through some means, the Publisher therefore has at its disposal:¶
This specification requires that if a group member fetches the KEK key at Locator, it
can decrypt the WrappedKey and retrieve the CEK. The WrappedKey
includes a 4-byte salt plus an AES key. The 4-byte salt is used by the AEAD algorithm as
part of the IV, and MUST remain the same for the given KeyNum.¶
In one example, a publisher could request a key for a group and the Key Manager could
securely communicate (CEK, Wapped_CEK, KeyId, KeyLink) back to the publisher.
The Key Manager is responsible for publishing the link. In another example, the
publisher could be a group member and have a group private key in which case the
publisher can create their own key encryption key, publish it under the Locator and
proceed. The publisher generates CEK, Wrapped_CEK, KeyId, and a KeyLink on its
own.¶
The RSA-OAEP "label" ("additional information" in [NIST-800-131Ar2]) is
constructed as shown in Figure 6. It is the concatenation of
several TLVs from the RsaOaepCtx. The AEADData, KeyId,
KeyLink, HashAlg TLVs are from the RsaOaepWrapper field. The label is
hashed via the HashAlg, so the length of the label does not affect the size of
the encryption. To tightly bind the encryption to the manifest, the publisher
SHOULD choose a unique KeyNum and KDFInfo pair.¶
AdditionalInfo = "FLIC RSA-OAEP" ||
KeyNum || AeadMode || [KDFData] ||
KeyID || HashAlg ||
KeyLink (if present in RsaOaepWrapper)
To create the wrapped key using a Key Encryption Key:¶
WrappedKey value using the KEK public key with OAEP padding
and the OAEP label (additional information), following [NIST-800-131Ar2]. The encryption is not signed or authenticated because
the root Manifest must have been signed by the publisher already. Or the encapsulating
Content Object (Data Object) is signed via ICN mechanisms.¶
To decrypt the wrapped key using a Key Encryption Key:¶
WrappedKey value using the KEK private key with OAEP
padding and OAEP label, following [NIST-800-131Ar2].¶
To encrypt a Manifest, the publisher:¶
SecurityCtx and adds it to the Manifest. The SecurityCtx
includes an AEADNonce and AEADMode, as per AEAD mode.¶
AEADData
.¶
To decrypt a Manifest, the consumer:¶
KeyId via the KeyLink
or whatever means the publisher and consumers use to distribute keys.¶
WrappedKey to get the CEK and salt. If the consumer has
already decrypted the same exact WrappedKey TLV block, it may use that cached CEK and
salt. The same wrapping key is determined by the publisher's signing KeyId, the
wrapping key KeyId, and the AEADData.¶
CEK and AEADData, decrypt the Manifest as per AEAD Mode.¶
The CCNx type values are defined in Section 5. The section Section 3.9.1.5 goes over every TLV structure.¶
In CCNx, application data content objects use a PayloadType of T_PAYLOADTYPE_DATA. In order to clearly distinguish FLIC Manifests from application data, a different payload type is required. Therefore this specification defines a new payload type of T_PAYLOADTYPE_MANIFEST.¶
ManifestContentObject = TYPE LENGTH [Name] [ExpiryTime]
PayloadType Payload
Name = TYPE LENGTH *OCTET ; As per RFC8569
ExpiryTime = TYPE LENGTH *OCTET ; As per RFC8569
PayloadType = TYPE LENGTH T_PAYLOADTYPE_MANIFEST ; Value TBD
Payload : TYPE LENGTH *OCTET ; the serialized Manifest object
The Hash Naming Strategy uses CCNx nameless content objects and the HashSchema name constructor. This means that only the Root Manifest should have a name embedded in the Content object. All other are CCNx nameless objects. The Manifest should provide a set of Locators that the client may use to form the Interests.¶
It proceeds as follows:¶
The Single Prefix strategy uses a named Root manifest and then all other data and sub-manifest objects use the same Name. They are differentiated only by their hash. The single prefix name should be different than the root manifest name, to not confuse them, as one may wish to use a discovery mechanism on the root manifest and fetch it without a hash restriction.¶
It proceeds as follows:¶
It proceeds as follows:¶
A manifest may use multiple schemas. For example, the application payload in data content objects might use SegmentedPrefix while the manifest content objects might use HashNaming.¶
The Root Manifest should specify an NsDef with a first NsId (say 1) as the HashNaming schema and a second NsDef with a second NsId (say 2) as the SegmentedPrefix schema along with the SegmentedPrefixName.¶
Each manifest (Top, Internal, Leaf) uses two or more HashGroups, where each HashGroup has only Direct (with the second NsId) or Indirect (with the first NsId). The number of hash groups will depend on how the publisher wishes to interleave direct and indirect pointers.¶
Manifests and data objects derive their names according to the application's naming schema.¶
This section defines each CCNx TLV encoding and the format of the TLV values.¶
FLIC uses variable length integer encodings in several places. We use the term
varint to be a network byte order unsigned integer of length 1 - 8 octets. This
applies to all fields defined as "INTEGER" in the grammar: T_SUBTREE_SIZE,
T_LEAF_SIZE, T_NCID, T_KEYNUM.¶
FLIC encodes hash values as per Section 3.3.3 of [RFC8609]. That is,
as a hash algorithm type, the length, and the hash output in the value. This applies
to any field in the grammar defined as "HashValue": T_SUBTREE_DIGEST,
T_LEAF_DIGEST, T_PTRS (an array of HashValue), T_PTR, T_KEYID.¶
The CCNx encoding allows for vendor extensions (T_ORG) in several places, as
per Section 3.3.2 of [RFC8609]. A parser may skip over any T_ORG
it does not implement. Where appropriate, we show an optional T_ORG tlv where
allowed.¶
The CCNx encoding allows for experimental type identifiers (0x1000-0x1FFF) in most TLV contexts. A parser may skip over any experimental TLV it does not implement. We do not show experimental TLVs in the artwork below.¶
There is no required order of TLV blocks within a TLV context. We show the RECOMMENDED ordering of TLV blocks. TLV blocks MUST NOT repeat unless specifically allowed in the grammar (Section 3.6).¶
A Manifest has an outer TLV type that identifies type kind of manifest inside a
Content Object with a payload type of T_PAYLOADTYPE_MANIFEST. FLIC is
defined as type T_FLIC_MANIFEST.¶
A FLIC Manifest may be plaintext or encrypted. A plaintext manifest usually only
has a Node. But it may also have a Security Context, Node, and Authentication Tag.
This can happen when a manifest is in-place decrypted. In place decryption operates
on the body of the EncryptedNode TLV and then changes the type from
T_ENCRYPTED_NODE to T_NODE.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_FLIC_MANIFEST | Length |
+---------------+---------------+---------------+---------------+
/ [Security Context] /
+---------------+---------------+---------------+---------------+
/ Node or EncryptedNode /
+---------------+---------------+---------------+---------------+
/ [Authentication Tag] /
+---------------+---------------+---------------+---------------+
The SecurityCtx TLV wraps an AlgroithmCtx, which may be either a
symmetric key encryption context AEADCtx or an asymmetric key wrapping of
the decryption key, RsaWrapCtx.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_SECURITY_CTX | Length |
+---------------+---------------+---------------+---------------+
/ AEADCtx or RsaWrapCtx /
+---------------+---------------+---------------+---------------+
The AEADCtx identifies a symmetric key shared by the publisher and
consumer. It is identified by a KeyNum, which may be an small integer (e.g.
within a TLS-like session) or a longer integer. CCNx uses up to a 64-bit integer.¶
The AEADNonce is used to generate the encryption IV, as described in Section 3.8.1. It is an octet string.¶
The AEADMode is an integer that identifies the encryption algorithm. All
defined values fit within 1 octet. The IANA registry "AEAD Algorithms" allows for up
to 2 octets.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_AEAD_CTX | Length |
+---------------+---------------+---------------+---------------+
| T_KEY_NUM | Length |
+---------------+---------------+---------------+---------------+
/ <varint> /
+---------------+---------------+---------------+---------------+
| T_NONCE | Length |
+---------------+---------------+---------------+---------------+
/ 1*OCTET /
+---------------+---------------+---------------+---------------+
| T_AEAD_MODE | Length |
+---------------+---------------+---------------+---------------+
/ <varint> /
+---------------+---------------+---------------+---------------+
/ [KDFData] /
+---------------+---------------+---------------+---------------+
The RsaOaepData has a mandatory AEADData section plus optional
RsaOaepData. Note that in the grammar, those are not TLV containers, but simply
data records. The figure below shows an RsaOaepCtx with all parameters.¶
The HashAlg value is an unsigned 16-bit integer in network byte order.¶
The wrapped key value is the RSA-OAEP ciphertext of the WrappedKey record.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_RSAOAEP_CTX | Length |
+---------------+---------------+---------------+---------------+
| T_KEY_NUM | Length |
+---------------+---------------+---------------+---------------+
/ <varint> /
+---------------+---------------+---------------+---------------+
| T_NONCE | Length |
+---------------+---------------+---------------+---------------+
/ 1*OCTET /
+---------------+---------------+---------------+---------------+
| T_AEAD_MODE | Length |
+---------------+---------------+---------------+---------------+
/ <varint> /
+---------------+---------------+---------------+---------------+
| T_KDF_DATA | Length |
+---------------+---------------+---------------+---------------+
/ <kdf structure> /
+---------------+---------------+---------------+---------------+
| T_KEYID | Length |
+---------------+---------------+---------------+---------------+
/ 1*OCTET /
+---------------+---------------+---------------+---------------+
| T_KEYLINK | Length |
+---------------+---------------+---------------+---------------+
/ <ccnx link> /
+---------------+---------------+---------------+---------------+
| T_HASH_ALG | 2 |
+---------------+---------------+---------------+---------------+
| 16-bit int |
+---------------+---------------+---------------+---------------+
| T_WRAPPED_KEY | Length |
+---------------+---------------+---------------+---------------+
/ <RSA-OAEP encrypted octets> /
+---------------+---------------+---------------+---------------+
The Node contains the manifest information. It has an optional NodeData,
plus one or more hash groups.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_NODE | Length |
+---------------+---------------+---------------+---------------+
/ [NodeData] /
+---------------+---------------+---------------+---------------+
/ 1*HashGroup /
+---------------+---------------+---------------+---------------+
NodeData has no mandatory fields, but several optional fields. If no
fields are present, a publisher should omit the entire NodeData TLV
container.¶
SubtreeSize, SubtreeDigest, and Vendor are encoded as previously specified (
INTEGER, HashValue, and T_ORG, respectively).¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_NODE_DATA | Length |
+---------------+---------------+---------------+---------------+
/ [SubtreeSize] /
+---------------+---------------+---------------+---------------+
/ [SubtreeDigest] /
+---------------+---------------+---------------+---------------+
/ [Locators] /
+---------------+---------------+---------------+---------------+
/ 0*NcDef /
+---------------+---------------+---------------+---------------+
/ 0*Vendor /
+---------------+---------------+---------------+---------------+
Locators is a TLV container around a list s Locator entries. Each
Locator wraps a CCN x Link Section 3.3.4 of [RFC8609]. In the
CCNx draft, "Link" does not have its own TLV type, but rather is embedded inside a
type with specific meaning, such as KeyLink or PublicKeyLocator.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_LOCATORS | Length |
+---------------+---------------+---------------+---------------+
/ 1*Locator /
+---------------+---------------+---------------+---------------+
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_LOCATOR | Length |
+---------------+---------------+---------------+---------------+
/ LINK /
+---------------+---------------+---------------+---------------+
NcDef provides the information needed for a consumer to construct an
Interest from a manifest pointer. The information is in a Name Constructor Schema.¶
NcId is encoded as an INTEGER, as previously defined.¶
NcSchema may include ProtocolFlags, which are TLVs intended to be
included in an Interest. These may control discovery or response freshness. The
value of protocol flags is ICN specific.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_NCDEF | Length |
+---------------+---------------+---------------+---------------+
/ NcId /
+---------------+---------------+---------------+---------------+
/ NcSchema /
+---------------+---------------+---------------+---------------+
The HashSchema uses CCNx nameless objects. It must have one or more
locators.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_HASH_SCHEMA | Length |
+---------------+---------------+---------------+---------------+
| T_LOCATORS | Length |
+---------------+---------------+---------------+---------------+
/ 1*LOCATOR /
+---------------+---------------+---------------+---------------+
/ [ProtocolFlags] /
+---------------+---------------+---------------+---------------+
The PrefixSchema uses named content objects. CCNx uses the provided name
and does not use locators.¶
The Name is encoded as Section 3.6.1 of [RFC8609].¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_PREFIX_SCHEMA | Length |
+---------------+---------------+---------------+---------------+
/ Name /
+---------------+---------------+---------------+---------------+
/ [ProtocolFlags] /
+---------------+---------------+---------------+---------------+
The SegmentedSchema uses named content objects. Each object has a name
prefix plus a unique suffix. The suffix is encoded with NameComponent type
SuffixComponentType. CCNx uses the provided name and does not use locators.¶
The Name is encoded as Section 3.6.1 of [RFC8609].¶
In CCNx, the SuffixComponentType must be 2 octets, as per the CCNx TLV
type size.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_SEGMENTED_SCHEMA | Length |
+---------------+---------------+---------------+---------------+
/ Name /
+---------------+---------------+---------------+---------------+
| T_SUFFIX_TYPE | 2 |
+---------------+---------------+---------------+---------------+
| Name Component Type |
+---------------+---------------+---------------+---------------+
/ [ProtocolFlags] /
+---------------+---------------+---------------+---------------+
A HashGroup encloses a series of hash values. It has an optional
GroupData that applies to all the pointers in the group.¶
The pointers are bundled in either a Ptrs list or an AnnotatedPtrs
list.¶
Ptrs is an array of raw CCNx hash values entries (i.e. SHA256 TLVs), as
per Section 3.3.3 of [RFC8609]. Each entry MAY be a
different hash type and different TLV length, so a parser must use the hash TLV type
and TLV length fields of each entry.¶
AnotatedPtrs is a list of annotations for each pointer.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_HASH_GROUP | Length |
+---------------+---------------+---------------+---------------+
/ [GroupData] /
+---------------+---------------+---------------+---------------+
/ Ptrs or AnnotatedPtrs /
+---------------+---------------+---------------+---------------+
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_PTRS | Length |
+---------------+---------------+---------------+---------------+
/ 1*HashValue /
+---------------+---------------+---------------+---------------+
The GroupData is a set of optional fields. The encoding of these fields
has been previously described (NcId, INTEGER, HashValue, T_ORG).¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_GROUP_DATA | Length |
+---------------+---------------+---------------+---------------+
/ [NcId] /
+---------------+---------------+---------------+---------------+
/ [LeafSize] /
+---------------+---------------+---------------+---------------+
/ [LeafDigest] /
+---------------+---------------+---------------+---------------+
/ [SubtreeSize] /
+---------------+---------------+---------------+---------------+
/ [SubtreeDigest] /
+---------------+---------------+---------------+---------------+
/ [StartSegmentId] /
+---------------+---------------+---------------+---------------+
/ 0*Vendor /
+---------------+---------------+---------------+---------------+
AnnotatedPtrs is a list of one or more PointerBlocks. Each
pointer block is one pointer plus zero or more annotations.¶
Annotations should not repeat in the same pointer block, unless specifically allowed by the annotation.¶
The defined annotations (SizeAnnotation, SegmentIdAnnotation, and LinkAnnotation) all use previously defined encodings (INTEGER or Name) and are not shown here.¶
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_ANNOTATED_PTRS | Length |
+---------------+---------------+---------------+---------------+
/ 1*PointerBlock /
+---------------+---------------+---------------+---------------+
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+---------------+---------------+---------------+---------------+
| T_PTR_BLOCK | Length |
+---------------+---------------+---------------+---------------+
| T_PTR | Length |
+---------------+---------------+---------------+---------------+
/ HashValue /
+---------------+---------------+---------------+---------------+
/ *Annotation /
+---------------+---------------+---------------+---------------+
In NDN, all Manifest Data objects use a ContentType of FLIC (1024), while all application data content objects use a PayloadType of Blob.¶
In NDN Hash Naming, a Data Object has a 0-length name. This means that an Interest will only have an ImplicitDigest name component in it. This method relies on using NDN Forwarding Hints.¶
It proceeds as follows:¶
In Single Prefix, the Data name is a common prefix used between all objects in that namespace, without a Segment or other counter. They are distinguished via the Implicit Digest name component. The FLIC Locators go in the ForwardingHints.¶
It proceeds as follows:¶
In Segmented Prefix, the Data name is a common prefix plus a segment number, so each manifest or application data object has a unique full name before the implicit digest. This means the consumer must maintain a counter for each SegmentedPrefix namespace.¶
It proceeds as follows:¶
A manifest may use multiple schemas. For example, the application payload in data content objects might use SegmentedPrefix while the manifest content objects might use HashNaming.¶
The Root Manifest should specify an NsDef with a first NsId (say 1) as the HashNaming schema and a second NsDef with a second NsId (say 2) as the SegmentedPrefix schema along with the SegmentedPrefixName.¶
Each manifest (Top, Internal, Leaf) uses two or more HashGroups, where each HashGroup has only Direct (with the second NsId) or Indirect (with the first NsId). The number of hash groups will depend on how the publisher wishes to interleave direct and indirect pointers.¶
Manifests and data objects derive their names according to the application's naming schema.¶
Of special interest are "skewed trees" where a pointer to a manifest may only appear as last pointer of (sub-) manifests. Such a tree becomes a sequential list of manifests with a maximum of data pointers per manifest packet. Beside the tree shape we also show this data structure in form of packet content where D stands for a data pointer and M is the hash of a manifest packet.¶
Root -> M0 ----> M1 ----> ... |->DDDD |->DDDD |- ...¶
FLIC is expected to enable a number of salient experiments in the use of ICN protocols by applications. These experiments will help not only to inform the desirable structure of ICN applications but reflect back to the features included in FLIC to evaluate their usefulness to those applications. While many interesting design aspects of FLIC remain to be discovered through experience, a number of important questions to be answered through experimentation include:¶
FLIC adds two values to existing registries and defines two new registry in the "Content-Centric Networking (CCNx)" group.¶
The FLIC registries follow the CCNx convention of reserving the namespace 0x1000 - 0x1FFF
for experimental use. It also uses the T_ORG (0x0FFF) definition for organizational (vendor)
extensions in the NodeData and GroupData fields.¶
IANA will assign value "0x0004" to "T_MANIFEST_ID" in the "CCNx Name Segment Types" registry.¶
IANA will assign value "0x0003" to "T_PAYLOADTYPE_MANIFEST" in the "CCNx Payload Types" registry.¶
IANA will add the following new registry to the "Content-Centric Networking (CCNx)" registry group at https://www.iana.org/assignments/ccnx):¶
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_FLIC_MANIFEST | |
| 0x0001-0x0FFF | Unassigned | |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
IANA will add the following new registry and sub-registries to the "Content-Centric Networking (CCNx)" registry group at https://www.iana.org/assignments/ccnx):¶
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_SECURITY_CTX | |
| 0x0001 | T_NODE | |
| 0x0002 | T_ENCRYPTED_NODE | |
| 0x0003 | T_AUTH_TAG | |
| 0x0004-0x0FFF | Unassigned | |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_AEAD_CTX | |
| 0x0001 | T_RSAOAEP_CTX | |
| 0x0002-0x0FFF | Unassigned | |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_NODE_DATA | |
| 0x0001 | T_HASH_GROUP | |
| 0x0002 | T_SUBTREE_SIZE | |
| 0x0003 | T_SUBTREE_DIGEST | Value is in CCNx Hash Format Section 3.3.3 of [RFC8609] |
| 0x0004 | T_NCDEF | |
| 0x0005 | T_NCID | |
| 0x0006 | T_LOCATORS | |
| 0x0007 | T_PTRS | Value is array of CCNx Hash Format Section 3.3.3 of [RFC8609] |
| 0x0008 | T_ANNOTATED_PTRS | |
| 0x0009 | T_PTR_BLOCK | |
| 0x000A | T_PTR | Value is in CCNx Hash Format Section 3.3.3 of [RFC8609] |
| 0x000B | T_GROUP_DATA | |
| 0x000C-0x000F | Unassigned | |
| 0x0010 | T_HashSchema | |
| 0x0011 | T_PrefixSchema | |
| 0x0012 | T_SegmentedSchema | |
| 0x0013-0x0FFD | Unassigned | |
| 0x0FFE | T_PAD | Section 3.3.1 of [RFC8609] |
| 0x0FFF | T_ORG | Section 3.3.2 of [RFC8609] |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_NAME | [RFC8609] |
| 0x0001 | T_PROTOCOL_FLAGS | |
| 0x0002 | T_SUFFIX_TYPE | |
| 0x0003-0x0005 | Unassigned | |
| 0x0006 | T_LOCATORS | |
| 0x0007-0x000C | Unassigned | |
| 0x000D | T_LINK | Value is a Link Section 3.3.4 of [RFC8609] |
| 0x000E-0x0FFF | Unassigned | |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_LEAF_SIZE | |
| 0x0001 | T_LEAF_DIGEST | Value is a CCNx Hash Format Section 3.3.3 of [RFC8609] |
| 0x0002 | T_SUBTREE_SIZE | |
| 0x0003 | T_SUBTREE_DIGEST | Value is in CCNx Hash Format Section 3.3.3 of [RFC8609] |
| 0x0004 | T_START_SEGMENT_ID | |
| 0x0005-0x0FFE | Unassigned | |
| 0x0FFF | T_ORG | Section 3.3.2 of [RFC8609] |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_KEYNUM | |
| 0x0001 | T_NONCE | |
| 0x0002 | T_AEADMode | Value a per IANA "AEAD Algorithms" [RFC5116] |
| 0x0003 | T_HASH_ALG | |
| 0x0004 | T_WRAPPED_KEY | |
| 0x0005 | T_KDF_DATA | |
| 0x0006 | T_KDF_ALG | Value as per IANA "HPKE KDF Identifiers" [RFC9180] |
| 0x0007 | T_KDF_INFO | |
| 0x0008 | Unassigned | |
| 0x0009 | T_KEYID | As per Section 3.6.4.1.4 of [RFC8609] |
| 0x000A-0x000D | Unassigned | |
| 0x000E | T_KEYLINK | As per Section 3.6.4.1.4 of [RFC8609] |
| 0x000F-0x0FFF | Unassigned | |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
| Type | Name | Reference |
|---|---|---|
| 0x0000 | T_ANN_SIZE | |
| 0x0001 | T_ANN_SEGMENT_ID | |
| 0x0003-0x000C | Unassigned | |
| 0x000D | T_LINK | Value is a Link Section 3.3.4 of [RFC8609] |
| 0x000E-0x0FFE | Unassigned | |
| 0x0FFF | T_ORG | Section 3.3.2 of [RFC8609] |
| 0x1000-0x1FFF | Reserved for experimental use | |
| 0x2000-0xFFFF | Unassigned |
A FLIC manifest has it's own security and privacy apart from the underlying application data that the manifest describes. The trust and privacy of the application data is not considered by FLIC, only the trust, security, and privacy of the manifest itself. The trust of a consumer on a manifest is based on the root manifest name, it's publisher's key, the signature on the root manifest, and the consumers belief that the given key is trusted to publish the name.¶
The security and privacy of a FLIC manifest is for the hash pointers and name
constructors it contains. FLIC does not provide privacy for: the name of the root manifest
or any named ICN packet in the tree, the publisher's public key ID in any manifest or
application data object, the key identifiers used to encrypt a FLIC manifest. The first
two items are part of the Content Object and thus outside the FLIC security envelope
(though they are authenticated by the root manifest signature). The FLIC SecurityCtx
information is outside the encryption envelope, so elements like the symmetric
KeyNumber or the RSA-OAEP wrapping KeyId are exposed.¶
An observer may be able to track, for example, all manifests from a publisher that use
the same preshared symmetric key by the pair (publisher public key id, key number) in the
Content Object and FLIC security context. With RSA-OAEP encapsulation, the wrapping key id
and the wrapped key number are public information and could be used to correlate manifest
objects. One could use a unique wrapped key (and thus key number) for each manifest. If
using a KDF, the KDFInfo field is public and could be used to correlate manifests
if kept constant for a single manifest tree or a sequential counter is used.¶
A FLIC Manifest is used to describe how to form Interests to access CCNx or NDN application data. The Manifest is itself either an individual content object, or a tree of content objects linked together via the corresponding content hashes. The NDN and CCnx protocol architectures directly provide both individual object integrity (using cryptographic strong hashes) and data origin authentication (using signatures). The protocol specifications, [NDN] and CCNx [RFC8609] respectively, provide the protocol machinery and keying to support strong integrity and authentication. Therefore, FLIC utilizes the existing protocol specifications for these functions, rather than providing its own. There are a few subtle differences in the handling of signatures and keys in NDN and CCNx worth recapitulating here:¶
A FLIC Manifest therefore gets integrity of its individual pieces through the existing secure hashing procedures of the underlying protocols. Origin authentication of the entire Manifest is achieved through hash chaining and applying a signature only to the root Manifest of a manifest tree. It is important to note that the Name of the Manifest, which is what the signature is bound to, need not bear any particular relationship to the names of the application objects pointed to in the Manifest via Name Constructors. This has a number of important benefits described in Section 3.3.¶
ICN protocol architectures like CCNx and NDN, while providing integrity and origin authentication as described above, leaves confidentiality issues entirely in the domain of the ICN application. Therefore, since FLIC is an application-level construct in both NDN and CCNx, it is incumbent on this specification for FLIC to provide the desired confidentiality properties using encryption. One could leave the specification of Manifest encryption entirely in the hands of the individual application utilizing FLIC, but this would be undesirable for a number of reasons:¶
Therefore, this specification directly specifies two encryption encapsulations and associated links to key management, as described in Section 3.8. As more experience is gained with various use cases, additional encryption capabilities may be needed and hence we expect the encryption aspects of this specification to evolve over time.¶
The RSA-OAEP encryption mechanism follows the recommendations of [NIST-800-56Br2], when not used for group keying. FLIC RSA-OAEP does not use integral key confirmation (MacKey), but rather signs the root manifest with the sender's private key. The RSA-OAEP encryption is of both the transported key, K, but also an AES salt, S.¶
RSA key generation is assumed to comply with [NIST-800-56Br2] Sec 6., but that is outside the control of FLIC.¶
The belief of the sender that it is using the correct wrapping public key for the receiver, and the sender's belief that the receiver has possession of the private key are functions of the key distribution system beyond the scope of FLIC. One possible mechanism to bring these beliefs closer to FLIC is to require that the manifest requester sign the Interest, such as using the CCNx mechanisms for signing an Interest, and the sender (publisher) check that the signature time is recent. This mechanism requires that the sender already have the public key and trust the owner of the private key to consume the manifest. This mechanism should not be used to distribute the public key.¶
The RSA-OAEP mechanism uses approved NIST hash functions (SHA256 or SHA512, as per the IANA CCNx hash function registry). It also uses additional information for the OAEP label, as recommended by [NIST-800-56Br2] Sec 9.1.¶
The lifespan and scope of symmetric keys, as identified by a KeyNum, is
different between an AeadCtx and a RsaOaepCtx. In the AeadCtx
case, the lifespan and scope is agreed to by the publisher and consumer out of band. In
the RsaOaepCtx the lifespan and scope is implicitly the current manifest. We will
discuss the RsaOaepCtx case first, as it is the simpler of the two.¶
For RsaOaepCtx, the first manifest in the tree to use RSA-OAEP must include the
wrapped key. The KeyNum is purely local within the manifest. The only requirement
is that the KeyNum have a one-to-one association with a specific wrapped key
within the manifest. That is, a publisher MUST NOT reuse a KeyNum
within a single manifest tree for two different AES key and salt combinations. The key
lifespan is strictly the ExpiryTime of the manifest and the scope is that single
manifest.¶
A publisher should use new symmetric keys for each manifest encrypted with RSA-OAEP.¶
For AeadCtx, a publisher and one or more consumers agree on a shared symmetric
key out-of-band and share it via some means. The publisher and consumer must agree on both
the lifespan of the key and its scope. The lifespan of such a key should be no shorter
than the greatest ExpiryTime of a manifest published with the key. The scope of
use should be, at minimum, manifests signed by the publisher's KeyId. The
publisher and consumer may also add name prefix limitations to a symmetric key's scope.¶
Because there is no requirement that an AeadCtx KeyNum be globally
unique, one should store them based on their scopes, such as (Publisher KeyId, KeyNum)
or (Publisher KeyId, Name Prefix, KeyNum).¶
If a publisher will use a single AES key across multiple manifests, it MUST use unique KDF derived keys or ensure that it never re-uses the same nonce.¶
A publisher MAY include a Pad element in the Node
element to hide the true length of a manifest. It is RECOMMENDED that a
publisher pad all encrypted Node to a multiple of 128 bytes, or up to the maximum
that will fit in the MTU target, to reduce the number of possible manifest sizes. It is
important that the sequence of manifest sizes within a manifest tree not have an
identifying sequence of sizes. A publisher of an encrypted manifest SHOULD
pad all manifests in a tree out to the same largest size.¶
The names of manifest and data objects are often missing or not unique, unless using specific naming conventions. In this example, we show how using manifest locators is used to generate Interests. Take for example the figure below where the root manifest is named by hash h0. It has nameless children with hashes with hashes h1 ... hN.¶
Objects: manifest(name=/a/b/c, ptr=h1, ptr=hN) - has hash h0 nameless(data1) - has hash h1 ... nameless(dataN) - has hash hN Query for the manifest: interest(name=/a/b/c, implicitDigest=h0)
After obtaining the manifest, the client fetches the contents. In this first instance, the manifest does not provide any Locators data structure, so the client must continue using the name it used for the manifest.¶
interest(name=/a/b/c, implicitDigest=h1) ... interest(name=/a/b/c, implicitDigest=hN)
Using the locator metadata entry, this behavior can be changed:¶
Objects: manifest(name=/a/b/c, hashgroup(loc=/x/y/z, ptr=h1) hashgroup(ptr=h2) - has hash h0 nameless(data1) - has hash h1 nameless(data2) - has hash h2 Queries: interest(name=/a/b/c, implicitDigest=h0) interest(name=/x/y/z, implicitDigest=h1) interest(name=/a/b/c, implicitDigest=h2)
Fast seeking (without having to sequentially fetch all content) works by skipping over
entries for which we know their size. The following expression shows how to compute the
byte offset of the data pointed at by pointer P_i, call it offset_i. In
this formula, let P_i.size represent the Size value of the i-th pointer.¶
offset_i = \sum_{k=1}^{i-1} > P_k.size¶
With this offset, seeking is done as follows:¶
Input: seek_pos P, a FLIC manifest with a hash group having N entries
Output: pointer index i and byte offset o, or out-of-range error
Algorithm:
offset = 0
for i in 1..N do
if (P > offset + P_i.size)
return (i, P - offset)
offset += P_i.size
return out-of-range
Seeking in a BlockHashGroup is different since offsets can be quickly computed. This is because the size of each pointer P_i except the last is equal to the SizePerPtr value. For a BlockHashGroup with N pointers, OverallByteCount D, and SizePerPointer L, the size of P_N is equal to the following:¶
D - ((N - 1) * L)¶
In a BlockHashGroup with k pointers, the size of P_k is equal to:¶
D - L * (k - 1)¶
Using these, the seeking algorithm can be thus simplified to the following:¶
Input: seek_pos P, a FLIC manifest with a hash group having
OverallByteCount S and SizePerPointer L.
Output: pointer index i and byte offset o, or out-of-range error
Algorithm:
if (P > S)
return out-of-range
i = floor(P / L)
if (i > N)
return out-of-range # bad FLIC encoding
o = P mod L
return (i, o)
Consider a huge file, e.g. an ISO image of a DVD or program in binary be patched. In this case, all existing encoded ICN chunks can remain in the repository while only the chunks for the patch itself is added to a new manifest data structure, as is shown in the diagram below. For example, the venti archival file system of Plan9 [venti] uses this technique.¶
A log file, for example, grows over time. Instead of having to re-FLIC the grown file it suffices to construct a new manifest with a manifest pointer to the old root manifest plus the sequence of data hash pointers for the new data (or additional sub-manifests if necessary).¶
In the example shown in Figure 32, there is a first root
manifest, Root 1, that has a name /logfile/v1 with an RsaOaepCtx
encryption context #1 and a CCNx content object RSA signature #2. In this example,
there is only room for 4 pointers per manifest (for the sake of a simple drawing),
the manifest Top 1 has two direct pointers and one indirect pointer. Manifest M2
has four direct pointers. Thus, the original log file is the concatendation
of D0 ... D5 payloads.¶
At a later time, the log files is extended with root manifest Root 2. This has its own name, /logfile/v2, with a new encryption content RsaOaepCtx #2. It has its own Content Object signature, Signature #2. Root 2 has one pointer to the previous root manifest, Root 1, and one pointer to the new FLIC tree, Top 2. The previous manifest stays encrypted with the RsaOaepCtx #1 key and the new manifest is encrypted with the new key in RsaOaepCtx #2.¶
If the same encryption key were used, Root 2 could point to Top 1 instead of Root 1.¶
┌───────────────┐ ┌───────────────┐
│ Root 1 │ │ Root 2 │
│ /logfile/v1 │ │ /logfile/v2 │
│ RsaOaepCtx #1 │◀──────────┐ │ RsaOaepCtx #2 │
│ Signature #1 │ │ │ Signature #2 │
└───────────────┘ │ └───────────────┘
│ └──────────┤
▼ ▼
┌────────────┐ ┌────────────┐
│ Top 1 │ │ Top 2 │
└────────────┘ └────────────┘
┌──────┼───────┐ ┌──────┼───────┐
▼ ▼ ▼ ▼ ▼ ▼
┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐
│ D0 │ │ D1 │ │ M2 │ │ D6 │ │ D7 │ │ D8 │
└────┘ └────┘ └────┘ └────┘ └────┘ └────┘
┌──────┬──┴───┬──────┐
▼ ▼ ▼ ▼
┌────┐ ┌────┐ ┌────┐ ┌────┐
│ D2 │ │ D3 │ │ D4 │ │ D5 │
└────┘ └────┘ └────┘ └────┘
¶
Note that the grown manifest does not need to specifically continue the previous naming. The old manifest (Root 1) might use one set of name constructors for the old manifests and data, and the new manifest (Root 2) might use different name constructors. If the manifests used HashedSchema, then naming is not an issue except for the root manfiests.¶
There are several use cases for republishing a collection under a new namespace, or having one collection exist under several namespaces:¶
This can easily be achieved with a single nameless root manifest for the large FLIC plus arbitrarily many per-name manifests (which are signed by whomever wants to publish this data):¶
data < - nameless_mfst() <-- h < - mfst(/com/example/east/the/flic)
< - mfst(/com/example/west/old/the/flic)
< - mfst(/internet/archive/flic234)
This example points out the problem of HashGroups having their own locator metadata elements: A retriever would be urged to follow these hints which are "hardcoded" deep inside the FLIC but might have become outdated. We therefore recommend to name FLIC manifests only at the highest level (where these names have no locator function). Child nodes in a FLIC manifest should not be named as these names serve no purpose except retrieving a sub-tree's manifest by name, if would be required.¶
This appendix describes one method to build FLIC graphs. We will use the term "tree" here, as all the construction and traversal mechanisms work as for trees, even if there are duplicate pointers in the graph that cause a node to have multiple parents.¶
We constructs a pre-order tree in a single pass of the application data, going from the tail to the beginning. This allows us to work up the right side of the tree in a single pass, then work down each left branch until we exhaust the data. Using the reverse-order traversal, we create the right-most-child manifest, then its parent, then the indirect pointers of that parent, then the parent's direct pointers,then the parent of the parent (repeating). This process uses recursion, as it is the clearest way to show the code. A more optimized approach could do it in a true single pass.¶
Because we build from the bottom up, we use the term 'level' to be the distance from the right-most child up. Level 0 is the bottom-most level of the tree, such as where node 7 is:¶
1
2 3
4 5 6 7
preorder: 1 2 4 5 3 6 7
reverse: 7 6 3 5 4 2 1
¶
The [ccnpy] Python code has more complex algorithms to build a FLIC graph is one pass while optimizing the tree structure. Its default is to minimize the tree height while fitting within a given packet MTU. It will use m-indirect and k-direct pointers for interior manifest nodes and n-direct pointers (n=m+k) for leaf manifest noides.¶
The Python-like pseudocode build_tree(data, n, k, m) algorithm creates a tree of n data objects. The data[] array is an array of Content Objects that hold application payload; the application data has already been packetized into n Content Object packets.An interior manifest node has k direct pointers and m indirect pointers.¶
build_tree(data[0..n-1], n, k, m):
# data is an array of Content Objects (Data in NDN) with app data.
# n is the number of data items
# k is the number of direct pointers per internal node
# m is the number of indirect pointers per internal node
segment = namedtuple('Segment', 'head tail')(0, n)
level = 0
# This bootstraps the process by creating the right most child
# manifest. A leaf manifest has no indirect pointers, so k+m
# are direct pointers
root = leaf_manifest(data, segment, k + m)
# Keep building subtrees until we're out of direct pointers
while not segment.empty():
level += 1
root = bottom_up_preorder(data, segment, level, k, m, root)
return root
¶
bottom_up_preorder(data, segment, level, k, m, right_most_child=None):
manifest = None
if level == 0:
assert right_most_child is None
# build a leaf manifest with only direct pointers
manifest = leaf_manifest(data, segment, k + m)
else:
# If the number of remaining direct pointers will fit
# in a leaf node, make one of those. Otherwise, we need to be
# an interior node
if right_most_child is None and segment.length() <= k + m:
manifest = leaf_manifest(data, segment, k+m)
else:
manifest = interior_manifest(data, segment, level,
k, m, right_most_child)
return manifest
¶
leaf_manifest(data, segment, count): # At most count items, but never go before the head start = max(segment.head(), segment.tail() - count) manifest = Manifest(data[start:segment.tail]) segment.tail -= segment.tail() - start return manifest¶
interior_manifest(data, segment, level, k, m, right_most_child)
children = []
if right_most_child is not None:
children.append(right_most_child)
interior_indirect(data, segment, level, k, m, children)
interior_direct(data, segment, level, k, m, children)
manifest = Manifest(children)
return manifest, tail
¶
interior_indirect(data, segment, level, k, m, children):
# Reserve space at the head of the segment for this node's
# direct pointers before descending to children. We want
# the top of the tree packed.
reserve_count = min(k, segment.tail - segment.head)
segment.head += reserve_count
while len(children) < m and not segment.head == segment.tail:
child = bottom_up_preorder(data, segment, level - 1, k, m)
# prepend
children.insert(0, child)
# Pull back our reservation and put those pointers in
# our direct children
segment.head -= reserve_count
¶
interior_direct(data, segment, level, k, m, children):
while len(children) < k+m and not segment.head == segment.tail:
pointer = data[segment.tail() - 1]
children.insert(0, pointer)
segment.tail -= 1
¶