Delegated Distributed Mappings
draft-watson-dinrg-delmap-00

Network Working Group                                              S. Li
Internet-Draft                                                       EFF
Intended status: Experimental                                     C. Man
Expires: January 3, 2019                                       J. Watson
                                                     Stanford University
                                                           July 02, 2018

                     Delegated Distributed Mappings
                      draft-watson-dinrg-delmap-00

Abstract

   Delegated namespaces (domain names, IP address allocation, etc.)
   underpin almost every Internet entity but are centrally managed,
   unilaterally revokable, and lack a common interface.  This draft
   specifies a generalized scheme for delegation with a structure that
   supports explicit delegation guarantees.  The resulting data may be
   secured by any general purpose distributed consensus protocol;
   clients can query the local state of any number of participants and
   receive the correct result barring a compromise at the consensus
   layer.

Status of This Memo

   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 January 3, 2019.

Copyright Notice

   Copyright (c) 2018 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

Li, et al.               Expires January 3, 2019                [Page 1]
Internet-Draft             Delegated Mappings                  July 2018

   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Structure . . . . . . . . . . . . . . . . . . . . . . . . . .   3
     2.1.  Cells . . . . . . . . . . . . . . . . . . . . . . . . . .   4
     2.2.  Tables  . . . . . . . . . . . . . . . . . . . . . . . . .   5
     2.3.  Root Key Listing  . . . . . . . . . . . . . . . . . . . .   6
     2.4.  Data Structure  . . . . . . . . . . . . . . . . . . . . .   7
   3.  Consensus . . . . . . . . . . . . . . . . . . . . . . . . . .   8
     3.1.  Validation  . . . . . . . . . . . . . . . . . . . . . . .   8
     3.2.  SCP . . . . . . . . . . . . . . . . . . . . . . . . . . .   9
   4.  Security Considerations . . . . . . . . . . . . . . . . . . .   9
   5.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  10
     5.1.  Normative References  . . . . . . . . . . . . . . . . . .  10
     5.2.  Informative References  . . . . . . . . . . . . . . . . .  10
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  10
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  10

1.  Introduction

   Internet entities rely heavily on delegated namespaces to function
   properly.  Typical web services might have been delegated a domain
   name under which they host the entirety of their public-facing
   content, or obtain a public IP range from their ISP, acquiring a
   portion of a namespace originally assigned by an Internet Numbers
   Registry [RFC7249].  An enormous amount of economic value is
   therefore placed in these assignments, or mappings, yet they are
   dangerously ephemeral.  Delgating authorities can unilateraly revoke
   and replace the assignments they've made (maliciously or
   accidentally), compromising infrastructure security.

   Presented in this draft is a generalized mechanism for delegating and
   managing such mappings.  Specifically, we describe the structure for
   a distributed directory with support for delegation "commitments"
   that have an explicit duration.  Certain known entities are assigned
   namespaces, loosely associated with a service provided by that entity
   (i.e domain prefixes for DNS Authorities).  Under that namespace, are
   authorized to create mapping records, or _cells_, a unit of ownership
   in the service.  A namespace's cells are grouped into a logical unit
   we term a _table_.

Li, et al.               Expires January 3, 2019                [Page 2]
Internet-Draft             Delegated Mappings                  July 2018

   Table cells may also explicitly document the delegation of a portion
   of the authority's namespace to another entity with a given public
   key, along with a guarantee on that delegation's lifetime.  Each
   delegation forms a new table, for which the delegee is the sole
   authority.  Thus, the delegating entity may not make modifications to
   a delegated table and need not be trusted by the delegee.  The
   namespace segment may be further delegated to others.

   The delegation tables maintain security and consistency through a
   distributed consensus algorithm.  When a participant receives an
   update, they verify and submit it to the consensus layer, after
   which, if successful, the change is applied to its associated table.
   Clients may query any number of trusted servers and expect the result
   to be correct barring widespread collusion.

   The risk of successful attacks on this system vary based on the
   consensus scheme used.  Detailed descriptions of specific protocol
   implementations are out of scope for this draft, but at a minimum,
   the consensus algorithm must apply mapping updates in a consistent
   order, prevent equivocation or unauthorized modification, and enforce
   the semantic rules associated with each table.  We find that
   federated protocols such as the Stellar Consensus Protocol
   [I-D.mazieres-dinrg-scp] are promising given their capability for
   open participation, broad diversity of interests among consensus
   participants, and a measure of accountability for submitting
   deceptive updates.

   This document specifies the structure for authenticated mapping
   management and its interface with a consensus protocol
   implementation.

2.  Structure

   Trust within the delegation structure is solely based on public key
   signatures.  Namespace authorities must sign any mapping additions,
   modifications, delegations, and revocations as proof to the other
   consensus participants that such changes are legitimate.  For the
   sake of completeness, the public key and signature types are detailed
   below.  All types in this draft are described in XDR [RFC4506].

    typedef publickey opaque<>; /* Typically a 256 byte RSA signature */

    struct signature {
        publickey pk;
        opaque data<>;
    };

Li, et al.               Expires January 3, 2019                [Page 3]
Internet-Draft             Delegated Mappings                  July 2018

2.1.  Cells

   Cells are the basic unit of the delegation structure.  In general,
   they define an authenticated mapping record that may be queried by
   clients.  We describe two types of cells:

       enum celltype {
           VALUE = 0,
           DELEGATE = 1
       };

   Value cells store individual mapping entries.  They resolve a lookup
   key to an arbitrary value, for example, an encryption key associated
   with an email address or a the address of an authoritative nameserver
   for a given DNS zone.  The public key of the cell's owner (e.g. the
   email account holder, the zone manager) is also included, as well as
   a signature authenticating the current version of the cell.  The cell
   must be signed either by the "owner_key", or in some cases, the
   authority of the table containing the cell, as is described below.
   The cell owner may rotate their public key at any time by signing the
   transition with the old key.

       struct valuecell {
           opaque value<>;
           publickey owner_key;
           signature transition_sig; /* Owner or table authority */
       };

   Delegate cells have a similar structure but different semantics.
   Rather than resolving an individual mapping, they authorize the
   delegee to create arbitrary value cells within an assigned namespace.
   This namespace must be a subset of the _delegator_'s own namespace
   range.  The delegee is identified by their public key.  Finally, each
   delegate cell and subsequent updates to the cell are signed by the
   delegator - this ensures that the delegee cannot unilaterally modify
   its namespace, which limits the range of mappings they can
   legitimately create.

       struct delegatecell {
           opaque namespace<>;
           publickey delegee;
           signature authority_sig;  /* Delegator only */
       };

   Both cell types share a set of common data members, namely a set of
   UNIX timestamps recording the creation time and, if applicable, the
   time of last modification.  They are useful indicators and will
   likely be useful in updating consensus nodes that have fallen behind.

Li, et al.               Expires January 3, 2019                [Page 4]
Internet-Draft             Delegated Mappings                  July 2018

   An additional "commitment" timestamp must be present in every
   mapping.  It is an explicit guarantee on behalf of the authority
   creating the cell that the mapping will remain valid until at least
   the specified time.  Therefore, while value cell owners may modify
   their cell at any moment, the authority cannot successfully change
   (or remove) the cell until its commitment expires.  Similarly,
   delegated namespaces are guaranteed to be valid until the commitment
   timestamp.  This creates a tradeoff between protecting delegees from
   arbitrary delegator action and allowing simple reconfiguration that
   can be customized for the use case.

       union innercell switch (celltype type) {
       case VALUE:
           valuecell vcell;
       case DELEGATE:
           delegatecell dcell;
       };

       struct cell {
           unsigned hyper create_time;     /* 64-bit UNIX timestamps */
           unsigned hyper *revision_time;
           unsigned hyper commitment_time;
           innercell c;
       }

2.2.  Tables

   Every cell is stored in a table, which groups all the mappings
   created by a single authority public key for a specific namespace.
   Individual cells are referenced by an application-specific label in a
   lookup table.  Below, we allow for a single lookup key to reference a
   list of cells, for the sake of generality.  The combination of a
   lookup key and a referenced cell value forms a mapping.

       struct tableentry {
           opaque lookup_key<>;
           cell cells<>;
       }

   Delegating the whole or part of a namespace requires adding a new
   lookup key for the namespace in question and a matching delegate
   cell.  Each delegation must be validated in the context of the other
   table entries and the table itself.  For example, it should not be
   possible for the owner of a /8 IPv4 block to delegate the same /16
   block to two different delegees.  In addition to a collection of
   entries, each table incorporates a "type" that informs each
   participating node of the particular delegation rules to apply to
   table entries.

Li, et al.               Expires January 3, 2019                [Page 5]
Internet-Draft             Delegated Mappings                  July 2018

       struct table {
           tabletype type;
           tableentry entries<>;
       };

   While there exist more delegation mechanisms than we could reasonably
   discuss in this draft, we initially propose three general-purpose
   schemes that cover the majority of use cases:

       enum tabletype {
           PREFIX = 0,
           SUFFIX = 1,
           FLAT = 2
       };

   The table type informs the validation procedure when performing
   consensus; all new or updated delegated namespaces must follow the
   proper format for their table.  Prefix-based delegation, such as in
   an IP delegation use case, requires every table cell value to be
   prefixed by the table namespace, and no cell value be a prefix of
   another cell value.  Similar rules apply to suffix-based delegation.
   In cases where arbitrary values may be mapped (e.g. account names for
   an email service provider), "flat" delegation rules are used.

   The delegation rule for a table also determine valid lookup behavior.
   Given a particular lookup key, "PREFIX"-type tables should have at
   most one entry whose key is a prefix of the query.  Likewise,
   "SUFFIX" tables have at most one entry whose key is a suffix of the
   query.  As an example, lookup on "irtf.org" in a table of domain
   names with suffix-based delegation rules may return entries with keys
   "irtf.org", "tf.org", ".org", etc., but the presence of more than one
   of these indicates two faulty delegations that control the same
   namespace.

2.3.  Root Key Listing

   Each linked group of delegation tables for a particular namespace is
   rooted by a public key stored in a flat root key listing, which is
   the entry point for lookup operations.  Well-known application
   identifier strings denote the namespace they control.  We describe
   below how lookups can be accomplished on the mappings.

Li, et al.               Expires January 3, 2019                [Page 6]
Internet-Draft             Delegated Mappings                  July 2018

       struct rootentry {
           publickey namespace_root_key;
           string application_identifier<>;
           signature listing_sig;
       }

       struct rootlisting {
           rootentry roots<>;
       }

   A significant open question is how to properly administer entries in
   this listing, since a strong authority, such as a single root key,
   can easily protect the listing from spam and malicious changes, but
   raises important concerns about censorship resilience and potential
   compromise.  A federated approach to management is more in line with
   the spirit of this draft but opens the door for counter-productive
   participation.  In the "rootentry" description above, we allow for
   either a root signing key to authenticate mappings, or first-come-
   first-served self-signed entries.  In either case, no more than one
   key may control the namespace for a specific application identifier.

2.4.  Data Structure

   Delegation tables are stored in a Merkle hash tree, described in
   detail in [RFC6962].  In particular, it enables efficient lookups and
   logarithmic proofs of existence in the tree, and prevents
   equivocation between different participants.  Specifically, we can
   leverage Google's [Trillian] Merkle tree implementation which
   generalizes the datastructures used in Certificate Transparency.  In
   map mode, the tree can manages arbitrary key-value pairs at scale.
   This requires flattening the delegation links such that each table
   may be queried, while ensuring that a full lookup from the
   application root be made for each mapping.  Given a "rootentry", the
   corresponding table in the Merkle tree can be found with this
   concatenation:

    root_table_name = app_id || namespace_root_key

   Similarly, tables for delegated namespaces are found at:

    root_table_name || delegee_key_1 || ... || delegee_key_n

   Consensus is performed on the Merkle tree containing the flattened
   collection of tables.  While it is possible to reach consensus on
   entire tables when a cell is modified, this approach does not scale
   well with the size of the table.  Therefore, each table should
   maintain its entries in its own internal Merkle tree and perform
   consensus on Merkle proofs for the modified cell.

Li, et al.               Expires January 3, 2019                [Page 7]
Internet-Draft             Delegated Mappings                  July 2018

3.  Consensus

   Safety is ensured by reaching distributed consensus on the state of
   the tree.  The general nature of a Merkle tree as discussed in the
   previous section enables almost any consensus protocol to support
   delegated mappings, with varying guarantees on the conditions under
   which safety is maintained and different trust implications.  For
   example, a deployment on a cluster of nodes running a classic
   Byzantine Fault Tolerant consensus protocol such as [PBFT] requires a
   limited, static membership and can tolerate compromises in up to a
   third of its nodes.  In comparison, proof-of-work schemes including
   many cryptocurrencies have open membership but rely on economic
   incentives and distributed control of hashing power to provide
   safety, and federated consensus algorithms like the Stellar Consensus
   Protocol (SCP) [I-D.mazieres-dinrg-scp] combine dynamic members with
   real-world trust relationships but require careful configuration.
   Determining which scheme, if any, is the "correct" protocol to
   support authenticated delegation is an open question.

3.1.  Validation

   Incorrect (potentially malicious) updates to the Merkle tree should
   be rejected by nodes participating in consensus.  Given the limited
   set of delegation schemes presented in the previous section, each
   node can apply the same validation procedure without requiring
   application-specific knowledge.  Upon any modification to the tree -
   addition of a new root entry, table or cell, or modification of an
   existing cell - the submitted change to the consensus layer should
   contain:

   (1) the updated or newly-created table, and

   (2) a Merkle proof containing all the hashes necessary to validate
   the new root tree hash.

   Finally, each node participating in consensus must confirm before
   voting for the update that:

   (1) the Merkle proof is correct, and

   (2) an addition to the root key listing is correctly signed by an
   authorized party, or

   (3) for delegate cells:

   (3a) a new delegation is correctly authenticated, (3b) the cell
   contains a valid namespace owned by the delegator, (3c) the

Li, et al.               Expires January 3, 2019                [Page 8]
Internet-Draft             Delegated Mappings                  July 2018

   delegation follows the table-specified delegation rules, and (3d) the
   delegated table is mapped in the Merkle map by the proper key

   (4) for value cells:

   (4a) a new mapping is correctly authenticated, (4b) the value belongs
   to the signing authority's namespace, and (4c) does not conflict with
   other cells in its table

   (5) and for all updates, if proposed by the table authority, the cell
   contains an expired commitment timestamp.

   Only after a round of the consensus protocol is successful are the
   changes exposed to client lookups.

3.2.  SCP

   While consensus can be reached with many protocols, this section
   describes how the delegation tables can interface with an SCP
   implementation.

   As discussed above, updates to the delegation tables take the form of
   Merkle proofs along with the table change itself.  Since SCP does not
   need specific knowledge of the format of these proofs, they directly
   form the opaque values submitted to the consensus layer.  Once a
   combination of proofs are agreed to as outputs for a given slot, they
   are applied to the local tables state.

   Finally, [I-D.mazieres-dinrg-scp] requires the delegation layer to
   provide a _validity_ function that is applied to each input value,
   and a _combining function_ to compose multiple candidate values.  For
   this application, the validity function must implement the logic
   contained in the previous section.  The combining function can simply
   take the union of the valid proofs proposed by the consensus nodes,
   rejecting valid, duplicate updates to the same cell in favor of the
   most up-to-date timestamp.

4.  Security Considerations

   The security of the delegation tables is primarily tied to the safety
   properties of the underlying consensus layer.  Further, incorrect use
   of the public key infrastructure authenticating each mapping or
   compromise of a namespace root key can endanger mappings delegated by
   the key after their commitments expire.

Li, et al.               Expires January 3, 2019                [Page 9]
Internet-Draft             Delegated Mappings                  July 2018

5.  References

5.1.  Normative References

   [RFC4506]  Eisler, M., Ed., "XDR: External Data Representation
              Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May
              2006, <https://www.rfc-editor.org/info/rfc4506>.

   [Trillian]
              Google, "Trillian: General Transparency", n.d.,
              <https://github.com/google/trillian>.

5.2.  Informative References

   [I-D.mazieres-dinrg-scp]
              Barry, N., Losa, G., Mazieres, D., McCaleb, J., and S.
              Polu, "The Stellar Consensus Protocol (SCP)", draft-
              mazieres-dinrg-scp-04 (work in progress), June 2018.

   [PBFT]     Castro, M. and B. Liskov, "Practical Byzantine Fault
              Tolerance", 1999,
              <http://pmg.csail.mit.edu/papers/osdi99.pdf>.

   [RFC6962]  Laurie, B., Langley, A., and E. Kasper, "Certificate
              Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013,
              <https://www.rfc-editor.org/info/rfc6962>.

   [RFC7249]  Housley, R., "Internet Numbers Registries", RFC 7249,
              DOI 10.17487/RFC7249, May 2014,
              <https://www.rfc-editor.org/info/rfc7249>.

Acknowledgments

   We are grateful for the contributions and feedback on design and
   applicability by David Mazieres, as well as help and feedback from
   the IRTF DIN research group, including Dirk Kutscher and Melinda
   Shore.

   This work was supported by The Stanford Center For Blockchain
   Research.

Authors' Addresses

Li, et al.               Expires January 3, 2019               [Page 10]
Internet-Draft             Delegated Mappings                  July 2018

   Sydney Li
   Electronic Frontier Foundation
   815 Eddy Street
   San Francisco, CA 94109
   US

   Email: sydney@eff.org

   Colin Man
   Stanford University
   353 Serra Mall
   Stanford, CA 94305
   US

   Email: colinman@cs.stanford.edu

   Jean-Luc Watson
   Stanford University
   353 Serra Mall
   Stanford, CA 94305
   US

   Email: jlwatson@cs.stanford.edu

Li, et al.               Expires January 3, 2019               [Page 11]