Encoding for Robust Immutable Storage (ERIS)

1.3. Previous Work

ERIS is inspired and based on the encoding used in the file-sharing application of GNUNet - Encoding for Censorship-Resistant Sharing (ECRS) [ECRS].¶

ERIS differs from ECRS in following points:¶

Cryptographic primitives

ECRS itself does not specify any cryptographic primitives. The GNUNet implementation uses the SHA-512 hash and AES cipher. ERIS uses the Blake2b-256 cryptographic hash [RFC7693] and the ChaCha20 stream cipher [RFC8439]. This improves performance, storage efficiency (as hash references are smaller) and allows a convergence secret to be used (via Blake2b keyed hashing; see Section 2.3).¶

Block size

ECRS uses a fixed block size of 32 KiB. This can be very inefficient when encoding many small pieces of content. ERIS allows a block size of 1 KiB or 32 KiB, allowing efficient encoding of small and large content (see Section 2.2).¶

URN

ECRS does not specify an URN for referring to encoded content (this is specified as part of the GNUNet file-sharing application). ERIS specifies an URN for encoded content regardless of encoding application or storage and transport layer (see Section 2.7).¶

Namespaces

ECRS defines two mechanisms for grouping and discovering encoded content (SBlock and KBlock). ERIS does not specify any such mechanisms (see Section 3.3).¶

Other related projects include Tahoe-LAFS, Freenet and Datashards. The reader is referred to the ECRS paper [ECRS] for an in-depth explanation and comparison of related projects.¶

2.2. Block Size

ERIS uses two block sizes: 1KiB (1024 bytes) and 32KiB (32768 bytes). The block size must be specified when encoding content.¶

Both block sizes can be used to encode content of arbitrary size. The block size of 1KiB is an optimization towards smaller content.¶

The block size is encoded in the read capability and the decoding process is capable of handling both block sizes.¶

Implementations MUST support encoding and decoding content with both block sizes (1KiB and 32KiB).¶

2.3. Convergence Secret

Using the hash of the content as key is called convergent encryption.¶

Because the hash of the content is deterministically computed from the content, the key will be the same when the same content is encoded twice. This results in de-duplication of content, as well as deterministic identifiers. Both are useful properties for certain applications.¶

However, convergent encryption suffers from two known attacks that allow adversaries to either confirm the presence of some encoded content or even learn the content when parts are predictable (see Section 4.6 for details). A solution to both attacks is to use a convergence secret.¶

ERIS requires a 32 byte convergence secret to be specified when encoding some content. Using different convergence secrets to encode the same content will result in different blocks and different read capabilities. This prevents deterministic identifiers and de-duplication, but allows a slightly stronger form of censorship resistance (see Section 4.5).¶

The convergence secret only needs to be provided during encoding. The content can be decoded from blocks without access to the convergence secret (see Section 2.5).¶

Users who do not want to be vulnerable to the known attacks against convergent encryption and are ready to give up determistic identifiers and de-duplication SHOULD use a random (cryptographically secure) and unique convergent secret for every encoded content. Note that even while using random and unique convergent secrets ERIS SHOULD NOT be used to ensure confidentiality.¶

A group using a shared convergence secret can benefit from the advantages of convergent encryption (de-duplication and deterministic identifiers) while being safe against certain attacks from adversaries that do not know the convergence secret.¶

If the known attacks against convergent encryption are well understood and the advantages of deterministic identifiers and de-duplication outweigh, then the null convergence secret (32 bytes of zeroes) MAY be used.¶

The convergence secret is implemented as the keying feature of the Blake2 cryptographic hash [RFC7693].¶

2.4. Encoding

Inputs to the encoding process are:¶

content

An arbitrary length byte sequence of content to be encoded.¶

convergence-secret

A 256 bit (32 byte) byte sequence (see Section 2.3).¶

block-size

The block size used for encoding in bytes can be either 1024 (1KiB) or 32768 (32KiB) (see Section 2.2).¶

The output of the encoding process is a set of uniformly sized blocks and a read capability.¶

The encoding process constructs a tree of uniformly sized nodes. Leaf nodes at the bottom of the tree (level 0) correspond to the input content. Internal nodes (not leaf nodes) consist of references to nodes at lower levels .¶

The maximum number of references to nodes of a lower level in a node is called the arity of the tree and depends on the block size. For block size 1KiB the arity of the tree is 16, for block size 32KiB the arity is 512.¶

A simplified view of a tree constructed by encoding some content that is split into four leaf nodes is given in Figure 3. For illustration purposes the tree is of arity 2 (instead of 16 or 512).¶

Nodes are unencrypted elements of the tree . The encoding process output blocks which are encrypted nodes .¶

Internal nodes of the encoding tree (i.e. not leaf nodes) are concatenations of reference-key pairs (see Section 2.4.3).¶

The steps of the encoding process are:¶

1. Split content into leaf nodes (see Section 2.4.1).¶
2. Encrypt leaf nodes into blocks and reference-key pairs (see Section 2.4.2).¶
3. Recursively construct tree by making nodes from reference-key pairs to nodes at lower level (see Section 2.4.3) and encrypting nodes to blocks and reference-key pairs (see Section 2.4.2) until there is a single root node.¶
4. Construct the read capability from the tree level, used block size and reference-key pair to the root node.¶

A pseudocode implementation of the encoding process:¶

ERIS-Encode(content, convergence-secret, block-size):
    # initialize empty set of blocks to be output
    blocks := {}

    # split content into leaf nodes
    leaf-nodes := Split-Content(content, block-size)

    # initialize a list of reference-key pairs
    reference-key-pairs := []

    # initialize level to 0
    level := 0

    # encrypt leaf nodes to blocks and reference-key pairs
    for leaf-node in leaf-nodes:
        block, reference, key := Encrypt-Node(leaf-node, level, convergence-secret)

        # add block to set of blocks to output
        blocks := blocks ∪ { block }

        # add reference-key pair to list of reference-key pairs
        reference-key-pairs := reference-key-pairs ++ [ (reference, key) ]

    # we can be sure that there is at least a single reference-key pair
    assert Length(reference-key-pairs) >= 1

    # Construct higher levels until there is a single reference-key pair
    while Length(reference-key-pairs) > 1:

        # increment level
        level := level + 1

        # construct list of nodes at current level
        nodes := Construct-Internal-Nodes(reference-key-pairs, level, convergence-secret)

        # clear the reference-key pairs
        reference-key-pairs := []

        # encrypt nodes to blocks and reference-key pairs
        for node in nodes:
            block, reference, key := Encrypt-Node(node, level, convergence-secret)

            # add block to set of blocks to output
            blocks := blocks ∪ { block }

            # add reference-key pair to list of reference-key pairs
            reference-key-pairs := reference-key-pairs ++ [ (reference, key) ]


    # after constructing tree there is a single reference key pair
    assert Length(reference-key-pairs) = 1

    # get the root reference-key pair (pointing to the root node)
    root-reference, root-key := reference-key-pairs[0]

    # construct the read capability
    read-capability := block-size, level, root-reference, root-key

    return read-capability, blocks

The sub-processes Split-Content, Encrypt-Leaf-Node, Encrypt-Internal-Node and Construct-Internal-Nodes are explained in the following sections.¶

Note that the pseudocode implementation is provided for illustration purposes. Implementers are RECOMMENDED to implement a more efficient streaming encoder (see Section 2.8.2).¶

Split-Content(content, block-size):
    # pad content
    padded := Pad(content, block-size)

    # length of padded content is a multiple of block size
    assert Length(padded) mod block-size = 0

    # split padded content
    leaf-nodes := split padded into pieces of size exactly block-size

    return leaf-nodes

Encrypt-Leaf-Node(node, convergence-secret):
    # use the keyed Blake2b hash to compute the encryption key
    key := Blake2b-256-Keyed(node, convergence-secret)

    # nonce is 12 bytes of 0
    nonce := [0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]

    # encrypt node to block
    block := ChaCha20(node, key, nonce)

    # compute reference to encrypted block using unkeyed Blake2b
    reference := Blake2b-256(block)

    return block, reference, key

Encrypt-Internal-Node(node, level):
    # level is always larger than 0
    assert level > 0

    # use the unkeyed Blake2b hash to compute the encryption key
    key := Blake2b-256(node)

    # first byte of nonce is level of the node followed by 11 bytes of zero
    nonce := [level; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]

    # encrypt node to block
    block := ChaCha20(node, key, nonce)

    # compute reference to encrypted block using unkeyed Blake2b
    reference := Blake2b-256(block)

    return block, reference, key

Construct-Internal-Nodes(reference-key-pairs, block-size):
    # input is always non-empty
    assert Length(reference-key-pairs) > 0

    # compute arity
    arity := block-size / 64

    # initialize empty list of nodes to return
    nodes := []

    while Length(reference-key-pairs) > 0:
        # take at most arity reference-key pairs from the left of reference-key-pairs
        node-reference-key-pairs, rest :=
            Take-At-Most-N-From-Left(reference-key-pairs, arity)

        # concatenate all reference-key pairs to a node
        node := Concat(node-reference-key-pairs)

        # make sure node has size block-size by filling up with zeroes
        if Length(node) < block-size:
            node := Fill-with-zeroes(node, block-size)

        # add node to list of nodes to return
        nodes := nodes ++ [ node ]

        # set reference-key-pairs to rest
        reference-key-pairs := rest

    return nodes

2.5. Decoding

Given a read capability and access to blocks via a block storage the content can be decoded as shown in the procedure ERIS-Decode:¶

ERIS-Decode-Recurse(block-size, level, reference, key):

    # dereference the node
    node := Dereference-Node(reference, key, level, block-size)

    if level = 0:
        # node is a leaf node
        return node
    else:
       # node is an internal node

       # initialize an output
       output := []

       # iterate over all the reference-key-pairs in the node
       for reference-key-pair in node:
           # decode sub-tree and append to output
           output := output ++ Eris-Decode-Recurse(level - 1, reference-key-pair)

       return output

ERIS-Decode(block-size, level, root-reference, root-key):

    # verify integrity of read capability key if level is larger than 0
    if level > 0:
        Verify-Key(level, root-reference, root-key)

    padded := ERIS-Decode-Recurse(block-size, level, root-reference, root-key)

    return Unpad(padded, block-size)

The procedures Dereference-Node and Verify-Key are provided in the next section.¶

Note that the pseudocode implementation is provided for illustration purposes. Implementers are RECOMMENDED to implement a more efficient streaming or random-access decoder (see Section 2.8.3 and Section 2.8.4).¶

Dereference-Node(reference-key-pair, level, block-size):
    # unpack reference-key pair
    reference, key := reference-key-pair

    # get block
    block := Block-Storage-Get(reference)

    # ensure that block has correct size
    if not Length(block) = block-size:
        throw "block has invalid size"

    # ensure that block is valid for reference
    if not Blake2b-256(block) = reference:
        throw "block is invalid"

    # first byte of nonce is level of the node followed by 11 bytes of zero
    nonce := [level; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0]

    node := ChaCha20(block, key, nonce)

    return node

Verify-Key(level, reference, key):
    # ensure that reference-key pair is to an internal node
    assert level > 0

    # dereference the node
    node := Dereference-Node(reference, key, level)

    # verify integrity of key
    if not Blake2b-256(node) = key:
        throw "key in read capability is invalid"

2.6. Binary Encoding of Read Capability

The read capability consisting of the block-size, level of root reference-key pair as well as the root reference-key pair form the necessary pieces of information required to decode content.¶

We specify an binary encoding of the read capability to 66 bytes:¶

2.7. URN

A read capability can be encoded as an URN [RFC8141] using the namespace identifier eris and the unpadded Base32 [RFC4648] encoding of the read capability as namespace specific string, i.e:¶

urn:eris:BASE32-READ-CAPABILITY¶

For example the ERIS URN of the UTF-8 encoded string "Hello world!" (with block size 1KiB and null convergence secret):¶

urn:urn:eris:BIAD77QDJMFAKZYH2DXBUZYAP3MXZ3DJZVFYQ5DFWC6T65WSFCU5S2IT4YZGJ7AC4SYQMP2DM2ANS2ZTCP3DJJIRV733CRAAHOSWIYZM3M¶

3.1. Storage and Transport Layers

ERIS is defined independent of any storage and transport layer for blocks. The only requirement is that blocks can be accessed by their reference - the hash of the block content.¶

Possible storage layers include:¶

• in-memory hash-map¶
• key-value store and other databases¶
• files on a file system¶

Transport mechanisms include:¶

• HTTP: A simple HTTP endpoint can be used to de-reference blocks (see ERIS over HTTP).¶
• Sneakernet: Blocks can be transported on a physical medium such as a USB stick.¶

More interesting transport and storage layers use the fact that blocks are content-addressed. For example the peer-to-peer network IPFS can be used to store and transport blocks. The major advantages over using IPFS directly are that blocks are encrypted and not readable to IPFS peers without the read capability and that identifier of blocks and encoded content are not tied to the IPFS network. Applications can transparently use IPFS or any other storage/transport mechanism.¶

Other protocols we are investigating for usage as ERIS transport layer include Named Data Networking, BitTorrent and GNUNet.¶

We are also researching transport protocols based on CoAP [RFC7252].¶

3.3. Mutability and Namespaces

Encoded content is immutable in the sense that changing the encoded content results in a new identifier. Existing references to the old content need to be updated. This is a property that allows robust availabilty of content.¶

Nevertheless, there are applications where one wants to reference mutable content. Examples include user profiles or dynamic collections of content. Making small changes to a user profile or adding a piece of content to a collection should preserve the identifiers.¶

There are many ways of implementing such mutability or namespaces. ERIS does not specify any particular mechanism. Possible mechanisms include:¶

• Centralized servers that returns a mutable list of reference to (immutable) content. This is how most HTTP services work.¶
• Append-only logs where changes are securely appended with cryptographic signatures. The state is computed from the log of changes. This is how peer-to-peer systems such as hypercore or Secure ScuttleButt work. See also ERIS Canons for appendable logs optimized for usage with ERIS.¶
• Petname system: A system where a dynamic local name can be mapped to a reference. Sophisticated systems that allow delegation of naming authority include the GNU Name System [LSD0001] (see Section 2.6.2).¶
• Commutative Replicated Data Types (CRDTs) are distributed data structures similar to append-only logs with the advantage that the state of a mutable container can diverge and converge to consistent state eventually. Such structures seem especially suitable when control over a mutable container is shared by multiple parties. For an example see Distributed Mutable Containers.¶

We believe that the best suited mechanism for handling mutability depends on concrete applications and use-cases. A key value of ERIS is that it is agnostic of such mechanisms and can be used from any of them.¶

6.1. CBOR Tags Registry

This specification requires the assignment of a CBOR tag for a binary ERIS read capability. The tag is added to the CBOR Tags Registry as defined in RFC 8949 [RFC8949].¶

7.1. GNU Name System record types registry

GANA [GANA] is requested to add an entry into the "GNU Name System record types" registry as follows:¶