Skip to content

Latest commit

Β 

History

History
709 lines (571 loc) Β· 67.5 KB

PLAN-Proof-of-Correctness.md

File metadata and controls

709 lines (571 loc) Β· 67.5 KB
Raw

PLAN Security Model & Proof of Correctness

         P.rivacy
         L.ogistics
         A.ccessibility
P  L  A  N.etworks

What is this?

This document is a proof of correctness for the PLAN security model, an IRC-inspired virtual channel system that serves as a canvas for community content organization, access controls, real-world security features. The purpose of this system is to host PLAN-compatible clients, playback requested channel entries, process and propagate newly authored entries, and maintain a consistent and secure state.

In computer science, a "proof of correctness" refers to a formal walk-through and demonstration that a proposed method and/or design rigorously satisfies a given set of specifications or claims. The intention is to remove all doubt that there exists a set of conditions such that the proposed method would not meet all the specifications.

Below, we express a scenario, list a set of specifications, and propose a system of operation intended to address the scenario and specifications. We then proceed to demonstrate correctness for each specification, citing how the system and its prescribed operation satisfies that specification.

This document, although labeled "proof", is not perfect and has areas needing deeper analysis. It is intended to be a blueprint and serve as an ongoing open analysis of a pluggable, distributed, and extensible system. The data structures listed here are intended to convey understanding and model correctness more than they are intended to be performant.

Table of Contents

Scenario

A founding set of community organizers ("admins") wish to form C, a secure distributed storage network comprised of computers with varying capabilities, each running a common peer-to-peer software daemon ("node"). C is characterized by a set of individual members for any given point in time, with one or more members charged with administering member status, member permissions, and community-global rules/policies.

On their nodes, the members of C agree to employ 𝓛, an append-only CRDT. Data entries appended to 𝓛 ("transactions") are characterized by an arbitrary payload buffer, a signing public key, and a signature authenticating the transaction. Transactions on any given 𝓛 are considered to be "in the clear" (i.e. neither "wire" privacy nor storage privacy is assumed).

Let 𝓛C be a CRDT whose genesis is under exclusive control of the admins of C. 𝓛C is assumed to either contain (or have access to) a verification system such that a transaction submitted to 𝓛C is acceptable only if the transaction's author (signer) has explicit 𝓛-append permission ("postage"). At first this may appear to be a strong requirement, but it reflects the transference of security liability of the key(s) specified during the genesis of 𝓛C to an external set of authorities.

For example, a customized "private distro" of the Ethereum blockchain ("⧫") could be used to implement 𝓛 since:

  • The admins of C, on creating ⧫C, would issue themselves some large bulk amount C-Ether (postage)
  • The admins of C would periodically distribute portions of C-Ether to members of C (a postage quota).
  • On C's nodes, ⧫C:
    • Large payload buffers would be split into 32k segments (Ethereum's transaction size limit) and then committed.
    • Any transaction that does not "burn" an amount of postage commensurate with the byte size of the payload would be dropped/rejected.
    • Any transaction that attempts to transfer postage from a non-designated identities would be dropped/rejected.

For context, consider watching the distinguished George Glider in this video clip speak on the empowering nature of distributed information technology.

On Digital Security

We acknowledge that even the most advanced and secure systems are vulnerable to private key loss or theft, socially engineered deception, and physical coercion. That is, an adversary in possession of another's private keys without their knowledge, or an adversary manipulating or coercing others is difficult (or impossible) to prevent. Biometric authentication systems can mitigate some of these threats, but they also introduce additional surfaces that could be exploited (e.g. spoofing a biometric device or exploiting an engineering oversight).

Security frameworks often don't analyze or provision for the loss of private keys since the implications are typically catastrophic, effectively making the issue someone else's intractable problem. Any system lacking such analysis and provisioning can only be considered incomplete for every-day use. The system of operation presented here features swift countermeasures and recovery once it becomes known that private keys have been compromised (or suspect activity has been witnessed).

Specifications & Requirements

The members of C wish to assert...

Signal Opacity

  • For all actors not in C, all transactions sent to, read from, and residing on 𝓛C are informationally opaque to the maximum extent possible.

Access Exclusivity

  • Only members of C effectively have read and append access to 𝓛C.
  • Alternatively, parts of C can be set up for "public access" where non-members of C have read access to select community content.

Permissions Assurance

  • There is a hierarchy of member admin policies and permissions that asserts itself in order to arrive at successive states (and cannot be circumvented).
  • Even if multiple members are (or become) covert adversaries of C or are otherwise coerced, it must still be impossible to:
    • impersonate other members,
    • insert unauthorized permission or privilege changes,
    • gain access to others' private keys or information, or
    • alter 𝓛C in any way that poisons or destroys community content.

Accountability Assurance

  • The members of C are confident and can rest assured that every member is:
    • accountable, in that any exercise of their authority is community-public information and cannot be altered or concealed, and
    • bound, in that they cannot circumvent C's established rules and governance.
  • Even members in the highest positions of authority within C are both accountable and bound.

Membership Fluidity

  • New members can be invited to and join C at any time (given that C policies and permissions are met).
  • A member can be deactivated from C such that they become equivalent to an actor that has never been a member of C (aside that deactivated members can retain their copies of 𝓑 before the community entered this new security "epoch").

Strong Eventual Consistency

  • For each node ni in C, it's local replica state ("𝓑i"), converges to a stable/monotonic state as 𝓛C message traffic eventually "catches up", for any set of network traffic delivery conditions (natural or adversarial). That is, 𝓑1...𝓑N mutate such that strong eventual consistency ("SEC") is guaranteed.

Practical Security Provisioning

  • If/When it is discovered that a member's private keys are known to be either lost or possibly comprised, a "Member Halt" can be immediately initiated such that any actor in possession of said keys will have no further read or write access to C.
  • Actors that can initiate a Member Halt include:
    • the afflicted member, or
    • a member peer (depending on community-global settings), or even
    • an automated watchdog system on C (responding to abnormal or malicious activity)
  • Following a Member Halt, the afflicted member's security state enters new "epoch" and incurs no additional security liability. That is, there are no potential "gotchas" sometime down the road if an adversary gains access to previously compromised keys.

Independence Assurance

  • In the event that:
    • an adversary gains access to admin/root private keys and hijacks C, or
    • one or more admins becomes adversarial towards C, or
    • 𝓛C is otherwise corrupted or vandalized,
  • ...then C can elect to "hard fork" 𝓛C to an earlier time state, where specified members are struck from the member registry and others are granted admin permission.

Storage Portability

  • C, led by a coordinated admin effort, retains the ability to switch-out 𝓛 technologies.
  • For example, suppose 𝓛C has the safety feature such that it automatically halts under suspicious network conditions or insufficient peer connectivity (but requires central connectivity). However, earlier in C's history, they used a CRDT that favored liveness over safety, allowing partitions of C to still be able to collaborate without central connectivity.
  • Or for example, suppose a member of C inadvertently adds data to the community record that is inappropriate or legally unacceptable (even if it is no longer accessible at the client level). In such case, the community would want to "rebase" the community's persistent store so that the offending content entries are not carried over.

Proposed System of Operation

The members of C present the following system of operation...

System Synopsis

  • This system embraces a multi-tier security model, where each community member possesses a community-common keys as well as private keys. In effect, this places the entire system's infrastructure and transaction traffic inside a cryptographic bubble.
  • The system's data model is IRC-inspired in that member interaction takes the form of data entries posted serially to channels within a virtual channel address space. However, instead of channel entries just being rebroadcast to other connected clients (as on an IRC server), entries persist as transactions replicated across 𝓛C.
  • When a channel is created, it is assigned a protocol descriptor string, specifying the kind of entries that are expected to appear that channel and how UI clients should interpret them (functionally comparable to MIME types). This, plus the ability for any channel entry to include arbitrary HTTP-style headers, creates many possibilities for visually-oriented client interfaces.
  • Also inspired from IRC, each channel has its own permissions settings. Each channel designates an access control channel ("ACC") to be used as an oracle for channel permissions. An ACC is a special channel type that additionally conforms to a protocol designed to specify channel permissions. Like other channels, each ACC also designates a parent ACC, and so on, all the way up to C's root-level ACC.
  • Member, channel, and community security and key distribution uses "epochs" to demarcate security events, in effect furnishing permissions assurance.
  • In a flow known as Channel Entry Validation, each community node ("ni") iteratively mutates its local replica ("𝓑i") by attempting to merge newly arriving entries from 𝓛C into 𝓑i. During validation, if 𝓑i is not yet in a state to fully validate an incoming entry e, then e is said to be "deferred" for later processing.
  • This system, in effect, forms a secure and operational core outside C's channel data space, comparable to how a traditional OS maintains internal pipelines and hierarchies of operations and permissions, designed to serve and protect user processes.

System Security

  • Let UUID represent a constant-length independently generated identifier that ensures no reasonable chance of peer collision. Although it is difficult to express collision odds in meaningful human terms (even for "modest" probability spaces such as 1 in 2160), 20 to 32 pseudo-randomly generated bytes is more than sufficient.
  • Each member m in C securely maintains custody of two "keyrings":
    1. []km: m's personal keyring, which:
      • decrypts/encrypts information "sent" to/from m, and
      • creates signatures that authenticate information authored by m.
    2. []kC: the community keyring, which ensures C's "community-public" data is only readable by members of C.
      • Each entry authored by m is encrypted by m's local client using the latest community key on []kC.
      • That is, []kC encrypts/decrypts EntryCrypt traffic to/from 𝓛C and 𝓑i
      • Newly issued community keys are securely distributed to members via the Community Epoch Channel.

Channel Entries

  • Transactions residing in 𝓛C are storage containers for EntryCrypt: 
    type EntryCrypt struct {
    CommunityKeyID    UUID     // The community key used to encrypt .InfoCrypt
    InfoCrypt         []byte   // EntryInfo encrypted with .CommunityKeyID
    ContentCrypt      []byte   // Channel content, encrypted with EntryInfo.ContentKeyID
    Sig               []byte   // Authenticates this entry; signed by EntryInfo.AuthorMemberID
}
  • Given entry e arriving from 𝓛C and access to []kC, node ni decrypts e.InfoCrypt into an EntryInfo ("einfo"): 
    type EntryInfo struct {
    EntryOp           int32    // Entry opcode. Typically, POST_CONTENT
    TimeAuthored      int64    // When this struct was sealed/signed
    ChannelID         UUID     // Channel that this entry is posted to (or operates on)
    ChannelEpochID    UUID     // Epoch of the channel in effect when entry was authored
    AuthorMemberID    UUID     // Creator of this entry (and signer of EntryCrypt.Sig)
    AuthorMemberEpoch UUID     // Epoch of the author's identity when entry was authored
    ContentKeyID      UUID     // Identifies the key used to encrypt EntryCrypt.ContentCrypt
}
  • Every entry specifies a destination ChannelID within C's channel space to be merged into.
  • During Channel Entry Validation, newly arriving entries from 𝓛C are validated and merged into node ni's locally stored CommunityRepo ("𝓑i").
  • 𝓑i consists of:
    • a datastore for each channel UUID that makes an appearance in C
    • bookkeeping needed to resume sessions with 𝓛C
    • a queue of entries to be merged in accordance with Channel Entry Validation.
    • a mechanism for "deferred" entries to be retried periodically
    // CommunityRepo is a node's replica/repo/𝓑i
type CommunityRepo struct {
    ChannelsByID      map[UUID]ChannelStore
}

// ChannelStore stores entries for a given channel and provides rapid access to them
type ChannelStore struct {
    ChannelID         UUID
    ChannelProtocol   string          // "/chType/ACC" or "/chType/desc/<protocol-desc>"
    EpochHistory      []ChannelEpoch  // Record of all past channel epochs
    EntryTable        []EntryIndex    // Entry info indexed by TimeAuthored and hashname
    ContentTome       ContentTome     // Entry content store/db for channel
}

// EntryIndex packages the the essential parts of an entry, plus status information.
type EntryIndex struct {
    EntryInfo        EntryInfo
    EntryStatus      EntryStatus      // Status of entry (e.g. LIVE, DEFERRED)
    ContentPos       uint64           // Byte offset into ..ContentTome
    ContentLen       uint32           // Byte length at .ContentPos in ..ContentTome
}

Channel Epochs

Under an append-only storage model, the mechanism that gives rise to mutable permissions and access controls is centered around ChannelEpoch.

  • In a procedure known as issuing a new channel epoch, an owner of channel π˜Ύπ’‰ posts a new revision to π˜Ύπ’‰'s current ChannelEpoch to:
    • edit properties specific to π˜Ύπ’‰, or
    • designate a different parent ACC for π˜Ύπ’‰.
  • Naturally, part of Channel Entry Validation is to reject entries from members that lack the appropriate permissions to issue a new ChannelEpoch for a given channel. 
    // Specifies general epoch parameters and info
type EpochInfo struct {
    TimeStarted       timestamp
    TimeClosed        timestamp
    EpochID           UUID
    ParentEpochID     UUID            // 0 if this is the first epoch.
    TransitionSecs    int             // How long before previous epochs "expire"
    ...                               // Other epoch transition parameters
}

// ChannelEpoch represents a "rev" to a channel's security properties.
type ChannelEpoch struct {
    EpochInfo         EpochInfo
    AccessChannelID   UUID            // This is channel's parent ACC; cannot form circuit
    MemberGrants      AccessGrants    // Permissions for explicitly specified members   
    DefaultGrants     AccessGrants    // Permissions for members not otherwise specified  
}

Channels

Channels are intended as general-purpose containers for channel entries of all forms. This system uses channels internally for administration and permissions controls.

  1. General purpose channels, alas, are this system's primary deliverable and raison d'Γͺtre.
    • Most channels are this type and a general purpose channel is somewhat analogous to a file on a traditional operating system.
    • When a new channel is created, the creator (and hence owner) specifies a "protocol descriptor", a string directing client UIs to consistently interpret, handle, and present channel entries in accordance with the expectations associated with the channel's protocol.
    • Each channel also names a governing access control channel ("parent ACC"). A channel's parent ACC is charged with returning a permission level for any given member UUID, allowing nodes in C to independently carry out Channel Entry Validation.
    • General purpose channels are either:
      • community-public, where channel entry content is encrypted with the latest community key, or
      • private, where entry content is encrypted with the key identified by einfo.ContentKeyID.
        • Key mechanics for private channels are similar to starting a new community epoch, except the channel owner updating the ChannelEpoch performs key generation and distribution.
        • Only members that have at least read-access are "sent" the keys needed in order to decrypt private channel entries.
          • By default, community admins do not have the authority/means to gain access to a private channel's key.
          • This ensures that only the members that have been explicitly given channel access could possibly have access to the channel's key.
  2. Access Control Channels (ACCs) are specialized channels used to express permissions for all other channels, including other ACCs.
    • An ACC serves as an access authority that specifies:
      • channel permissions for a given member UUID, and
      • default permissions for members not otherwise specified.
    • Like general purpose channels, each ACC must designate a parent ACC, and so on, all the way up to the reserved root ACC.
    • Multiple channels can name the same ACC as their parent ACC, allowing a single ACC to conveniently manage permissions for any number of channels.
    • ACCs also are the vehicle for key distribution, where a channel owner "sends" a newly issued private channel to each member with access, using their public key.
  3. Reserved channels are specialized channels used by the system to internally carry out community governance and member administration.
    • Reserved channels specify root-level information and permissions, namely admin and member records.
    • Entries in these channels must meet additional security/signing requirements and serve prescribed purposes.
    • Because reserved channels have nuanced specifications, they do not solely rely on ACCs for access controls.
    • The number, purpose, and use of these channels can be expanded to meet future needs.

Reserved Channels

Root Access Control Channel

  • This is C's root access channel, specifying which members are community authorities ("admins").
  • All community-public channels, including ACCs, are implicitly under authority of this channel.
  • When a new community is formed ("community genesis"), the initial entries this channel are auto-generated in accordance with the parameters and policies provided by the founding members.
  • Automated machinery in C can optionally be geared to use smart contracts on 𝓛C to manage, monitor, or validate entries in this channel.
    • E.g. a majority vote of existing admins could be required in order to add a new admin to the root access channel.

Member Epoch Channel

  • This is a special channel where members post revisions to their currently published MemberEpoch, also known as the Community Member Registry channel.
    • MemberEpoch contains essential information about a specific member, such as their most recently published public keys and their "home" channel UUID 
      // MemberEpoch contains a member's community-public info
type MemberEpoch struct {
    MemberID          UUID
    EpochInfo         EpochInfo
    PubSigningKey     []byte
    PubEncryptKey     []byte
    HomeChannel       UUID
}
  • Each entry is this channel embeds a MemberEpoch, 𝓔, and is only considered valid if:
    • the member who signed the entry matches the MemberID that appears in 𝓔 (or is an authorized member delegated to do so), and
    • the predecessor ("parent") epoch of 𝓔 is eligible to be superseded.
  • MemberEpoch importantly publishes a member's public keys to the rest of the community, allowing each node in C to maintain a database used to:
    • authenticate signatures on each EntryCrypt
    • encrypt entry content exclusively for a given member (used for key distribution)
  • Only a community admin (or certified delegate) is permitted to post a MemberEpoch for members other than themselves. This provides the means for:
  • When a Member Halt has been issued on m, an special MemberEpoch entry ("𝓔halt") is posted to this channel.
    • The authorizing signature of 𝓔halt must be:
      • one of m's personal signatures, or
      • a member previously designated by m.
    • 𝓔halt is permitted to be signed by m's recently superseded keys, otherwise an adversary in possession of []km could "lock out" m by issuing a new member epoch.
    • Once 𝓔halt goes live, Channel Entry Validation will defer all further entries bearing m's signature.
    • If/When the cause for concern is addressed, a community authority would issue a new member epoch for m, superseding 𝓔halt.

Community Epoch Channel

  • This channel is where a community admin (or authorized agent) posts an entry that, in effect, replaces the current community key with a newly issued key.
  • This channel contains a succession of entries that embed:
    • an EpochInfo containing parameters associated with the new community epoch, and
    • a newly generated symmetric key for each member m in C, encrypted using m's latest public key published in C's Member Epoch Channel: 
      // KeyIssue is the vessel used to securely pass a ski.KeyEntry to another member
type KeyIssue struct {
    MemberID          UUID      // Specifies the recipient 
    MemberEpochID     UUID      // Implies which key was used to encrypt .KeyEntryCrypt
    KeyEntryCrypt     []byte    // Encrypted ski.KeyEntry
}

Standard Procedures

Issuing a New Member Epoch

  • Given: member m wishes to replace their currently published MemberEpoch with a new revision:
    • m generates new encryption and signing key pairs and places the private keys into their personal keyring, []km.
    • m prepares a replacement MemberEpoch, 𝓔′, placing the newly generated public keys into 𝓔′.
    • m packages 𝓔′ into a new entry ("e𝓔′"), signs it, and posts it to C's Member Epoch Channel.
    • As e𝓔′ propagates across 𝓛C (and goes live on 𝓑i):
      • Channel Entry Validation now requires that entries authored by m must use the newly published signing key.
      • Other member clients intending to securely pass keys or content to m would use m's updated public encryption key.
  • If a Member Halt has been ordered on m, then admin (or community authority) intervention is required before m is permitted to post a new MemberEpoch.

Issuing a New Community Epoch

  • Given: an admin, delegated member, or an automated agent wants to issue a new/replacement community key and deprecate the previously issued community key.
  • The purpose of starting this new "community epoch" is so that an actor in possession of the community keyring ("[]kC") will no longer be able to decrypt community-public data on C unless they are currently a member of C. This typically applies after a Member Halt or after deactivating a member since it's important that the currently active community key (and an actor in possession of it) is longer used to encrypted community traffic.
  • As the newly posted community key epoch goes live across the nodes of C, all new EntryCrypt on 𝓛C are encrypted using it.
  • A community authority or agent does the following:
    1. Generates a new symmetrical key to serve as the next community key ("kC").
    2. Prepares a new entry containing an EpochInfo ("𝓔C").
    3. For each open/active MemberEpoch ("𝓔m") in the Member Epoch Channel (for each member m in C):
      • Creates a new KeyIssue (intended for m), encrypting kC using 𝓔m.PubEncryptKey,
      • Appends the KeyIssue key to 𝓔C's content body.
    4. Posts 𝓔C to the Community Epoch Channel.
  • Member m's client, upon seeing 𝓔C go live:
    1. Searches the content body of 𝓔C for a KeyIssue matching m's member ID.
    2. Recovers kC from the KeyIssue using the member's private keyring.
    3. Adds kC to m's own community keyring.
    4. Uses kC to encrypt all subsequent authored entries bound for 𝓛C
  • Within Ξ”C, newly authored transactions are strictly only readable by the current members of C.
    • An actor in possession of a halted keyring or any keys past member epochs will not have any of the keys needed to extract kC.
    • If 𝓛C favors safety, then C could additionally be configured to reject entries encrypted with a community key older than Ξ”C since offline nodes effectively remain in a halted state until they regain access to a critical threshold of central validators.

Issuing a New Channel Epoch

  • Given: an owner of channel π˜Ύπ’‰ decides to alter permissions on π˜Ύπ’‰, such as:
    • editing π˜Ύπ’‰'s default access permissions to be more restrictive, or
    • removing access permissions for explicitly named members, or
    • making π˜Ύπ’‰ private and granting access to only specifically listed members of C.
  • Similar to issuing a new member epoch, π˜Ύπ’‰'s owner posts an entry to π˜Ύπ’‰ to revise the current ChannelEpoch.
  • If π˜Ύπ’‰ is private, a procedure similar to issuing a new community epoch distributes π˜Ύπ’‰'s latest access key to members that have at least read-only access to π˜Ύπ’‰.

Member Halt

  • Given: member m (or their private keyring) is potentially under the control or influence of an another.
  • A "Member Halt" refers to an automated sequence of actions performed on m's behalf once it's believed that their personal keyring ("[]km") is under the influence of another.
  • The conditions/requisites needed in order to initiate a Member Halt on another's behalf can be arbitrarily based on security needs and situational circumstances.
  • A Member Halt on m could be initiated by:
    • m, upon discovering that another actor has gained access to []km, or
    • a peer of m (previously designated by m), upon receiving a message or signal of duress from m, or
    • a community automated agent, noticing damning/malicious activity originating from a holder of []km.
  • Once a Member Halt is initiated on m:
    1. A special entry is posted to the Member Epoch Channel, signaling to all nodes in C to defer all further entries signed by []km
      • β‡’ this prevents any actor in possession of []km from posting any entries as m.
    2. A special transaction is submitted to 𝓛C, immediately "burning" the ability of m (or any actor in possession of []km) to post further transactions.
      • As this propagates across 𝓛C, subsequent transactions signed by []km will be rejected because post permission on 𝓛C will no longer exist for []km.
      • This removes an adversary's ability to vandalize 𝓛C (e.g filling it with junk data).
      • For example, for ⧫C, the transaction would send all m's C-Ether to address x0.
    3. An admin, automated agent, or delegated member(s) would issue a new community epoch for C.
      • Since newly issued community keys aren't posted for halted members, any agent(s) in possession of []km would lose all further read access to 𝓛C since they would not have a key to extract the newly issued community key for C.

Member Halt Recovery

  • Given: a Member Halt was issued on m.
  • Some time later, admin(s) or delegated members can review the situation:
    • When appropriate, m's access is restored and new keys issued using a variant of adding a new member.
    • In the case that an adversary in possession of []km transfers their postage (their privileges on 𝓛C) to another identity before a Member Halt is issued on m, entries using postage from the illicit postage could be identified and rejected.
    • In the case that an a adversary in possession of []km issued a new member epoch (impersonating m), then an admin in communication with m would issue new entries that rescind the earlier entries as appropriate. As normal Channel Entry Validation proceeds, this will automatically result in any dependent (adversary-authored) entries to be removed from "live" status.

Adding A New Member

  • Given: the permissions/prerequisites on C are met to bestow member status to actor Ξ±:
    1. A designated authority of C generates and posts a special MemberEpoch, 𝓔α0, in the Member Epoch Channel, containing:
      • a newly generated MemberID for Ξ±.
      • newly generated public keys.
      • information on Ξ±'s invitation, such as:
        • documentation of which authorities in C were connected to Ξ±'s invitation.
        • proof that Ξ±'s invitation was granted by the collective authority of C.
    2. Also created is token Ο„, containing:
      • a copy of 𝓔a0, and
      • a copy of the community keyring, []kC, and
      • the private half of public keys in 𝓔a0, and
      • network addresses and other bootstrapping information needed in order to connect to 𝓛C, and
      • a token that bestows its bearer postage on 𝓛C.
    3. Ο„ is encrypted with a passphrase, and is passed to Ξ± via USB device, email, file sharing, etc.
    4. Using face-to-face communication, direct contact, or other secure means, Ξ± is passed the passphrase to Ο„.
    5. On a newly created "blank" node, nΞ± (or an existing node of C in a logged-out state):
      1. Ξ± passes Ο„ to the client
      2. the client prompts for the passphrase that decrypts Ο„
      3. the client opens Ο„ and now has what it needs to:
        • connect and write to 𝓛C
        • decrypt entries from C and rebuild 𝓑α normally
      4. Once that 𝓑α is up to date (i.e. once 𝓔α0 is live in the Member Epoch Channel), Ξ± posts a successor MemberEpoch as they would when starting a new member epoch.

Deactivating A Member

  • Given: the admins and/or collective authority of C decide that member m is to be "deactivated", meaning that m's access C is to be immediately rescinded.
  • The designated authority of C performs a procedure identical to the Member Halt procedure. In effect:
    1. Any subsequent entries authored by m will be rejected, and
    2. m will be unable to post any transactions to 𝓛C, and
    3. All new entries on 𝓛C will be unreadable to m within Ξ”C

Channel Entry Validation

  • Given node ni in C, let 𝓑i denote the local replica state of 𝓛C on node ni at a given time.
  • Channel Entry Validation is the process of merging incoming entries arriving from 𝓛C such that entries placed into "live" status (on 𝓑i) comply and are in integrity with all relevant author and channel permissions and intent.
  • Since entries can arrive at ni in arbitrary order from 𝓛C, entries will arrive whose validation will depend on other entries that have not yet been processed β€” or entries yet to even arrive.
  • As node ni processes an incoming entry e to be merged with 𝓑i:
    • If e satisfies all channel properties and parent ACC permissions, then e is placed into "live" status.
    • Otherwise, if for whatever reason e cannot complete validation, then e is placed into "deferred" status.
      • Node ni periodically reattempts to validate e as other entries go live on 𝓑i.
      • Unless e was crafted with malicious intent, it would be unexpected for e to remain indefinitely deferred.
  • For each new entry e arriving from 𝓛C (or is locally authored and also submitted to 𝓛C):
    1. Authenticate e:
      1. edigest ⇐ ComputeDigest(e.CommunityKeyID, e.InfoCrypt, e.ContentCrypt)
      2. einfo ⇐ EntryInfo ⇐ Decrypt(e.InfoCrypt, []kC.LookupKey(e.CommunityKeyID)
        • if the community key is not found, then e is deferred.
      3. 𝓔author ⇐ 𝓑i.LookupMemberEpoch(einfo.AuthorMemberID, einfo.AuthorMemberEpoch)
        • if 𝓔author = nil, then e is deferred.
        • if einfo.TimeAuthored falls outside the scope of 𝓔author, then e is deferred.
      4. kpub ⇐ 𝓑i.LookupPublicKey(einfo.AuthorMemberID, einfo.AuthorMemberEpoch)
        • if kpub = nil, then e is deferred.
      5. ValidateSig(edigest, e.Sig, kpub)
        • if e.Sig is invalid, then e is deferred.
    2. Validate e in its destination channel:
      1. π˜Ύπ’‰dst ⇐ 𝓑i.GetChannelStore(einfo.ChannelID)
        • if π˜Ύπ’‰dst = nil, then e is deferred.
      2. Check that e cites an agreeable ChannelEpoch:
        • 𝓔cited ⇐ π˜Ύπ’‰dst.LookupEpoch(einfo.ChannelEpochID)
          • if 𝓔cited = nil, then e is deferred.
        • if einfo.TimeAuthored falls outside the scope of 𝓔cited, then e is deferred.
        • if 𝓔cited.CanAccept(einfo), then proceed, otherwise e is deferred.
      3. Check that π˜Ύπ’‰dst's parent ACC permits e:
        • π˜Ύπ’‰AC ⇐ 𝓑i.GetChannelStore(𝓔cited.AccessChannelID)
        • 𝓅author ⇐ π˜Ύπ’‰AC.LookupPermissions(einfo.AuthorMemberID)
        • if 𝓅author does not allow einfo.EntryOp, then e is deferred.
      4. If e inserts a permissions change but does not issue a new channel epoch as required, then e is deferred.
    3. Merge e into 𝓑i:
      • π˜Ύπ’‰dst.InsertEntry(e)
    4. Propagate the mutation of π˜Ύπ’‰dst as required ("revalidation"):
      • if π˜Ύπ’‰dst is now equally or less restrictive, then return since dependencies that are live will be unaffected.
      • if π˜Ύπ’‰dst is now more restrictive, then revalidate dependent channels:
        • trev ⇐ einfo.TimeAuthored
        • []π˜Ύπ’‰dep ⇐ π˜Ύπ’‰dst.GetDependentChannels(trev)
        • for each π˜Ύπ’‰j in []π˜Ύπ’‰dep:
          • Scanning forward from trev in π˜Ύπ’‰j, for each entry ek:
            • (re)validate ek (4 validate steps above)
            • if ek is now deferred:
              • π˜Ύπ’‰j.RemoveEntry(ek)
              • Defer ek normally
              • Sub-propagate the mutation of π˜Ύπ’‰j as applicable
      • Although there are edge cases where change propagation could result in a cascading workload, the amount of work is generally either n/a or negligible. This is because:
        • Most entries are content-related, not access-control related.
          • Revalidation only needs to proceed if an entry makes a channel more restrictive.
          • For example, compare the number of ACL-related files stored on a conventional workstation to the total number of files.
          • Only ACCs tend to have dependent channels.
        • Mutations to a channel occur close to the present time, so only O(1) of all entry history typically needs to be revalidated.
        • If 𝓛C favors safety over liveness, then there a highly limiting trailing time boundary for how "late" an entry can arrive (e.g. 10 seconds).
      • Revalidation can also be strategically managed, where multiple ACC mutations are scheduled such that only a single revalidation pass is needed.

Liveness vs Safety

"Liveness versus safety" refers to canonical tradeoffs made during the design of a blockchain or distributed ledger. This discussion is variant of the CAP theorem applied to distributed ledgers, where "liveness" corresponds to availability and "safety" corresponds to consistency. Here, we weigh the tradeoffs made by a given 𝓛C implementation:

  • If 𝓛C favors liveness over safety (such as Ethereum or Holochain), then partitions of 𝓛C will operate independently and will synchronize when rejoined. This implies:
    1. Ξ”C will reflect network latency and topology.
    2. Channel Entry Validation could potentially encounter an important but late-arriving entry, triggering a cascade of entry revalidation.
    3. The nodes of C are conveniently "offline-first" and will operate in independent cells if network connectivity is limited.
      • As partitions rejoin after some time and synchronize, each 𝓑i will receive new batches of old transactions (from other partitions).
  • If 𝓛C favors safety over liveness (such as a central server, EOS, DFINITY, Hashgraph), then 𝓛C by definition integrates a consensus mechanism that enforces a trailing timestamp boundary ("tb") for transactions. This implies:
    1. Ξ”C is helpfully fast (1-10 seconds)
    2. Channel Entry Validation has the luxury to finalize entries older than tb since later-arriving entries are not possible.
    3. However, the nodes of C require central network connectivity in order to operate. If nodes partition from the central network:
      • the 𝓛C nodes will halt, even though the nodes still have connectivity with each other, and
      • the 𝓛C nodes will only resume if/when the partition regains central network connectivity.

Proof of Specifications

Each item below corresponds to each item in the Specifications & Requirements section.

Proof of Signal Opacity

Signal Opacity asserts that outside actors can't infer material information by analyzing community wire traffic.

  • Given that (a) all community channel entries reside within transactions stored on 𝓛C, and (b) transactions are considered to be "in the clear":
    • What information is discernible to actors outside of C?
  • Let Ξ± be an actor that is not a member of C, implying that Ξ± does not possess the latest community keys.
    • β‡’ the only information directly available to Ξ± is the UUID of the encryption key used for each EntryCrypt on 𝓛C.
      1. β‡’ information opacity is maximized since all information resides within InfoCrypt and ContentCrypt.
        • Adversaries snooping 𝓛C can only discern when a new community security epoch began (by noting the appearance of a new community key UUID). However, this is weak information since such an event could correspond to any number of circumstances.
      2. β‡’ only members of C effectively have read-access to C's content and member activity.
    • If Ξ± is a former member of C, then Ξ±'s access is limited to read-only up to when Ξ± was deactivated (when the new community epoch was issued as part of deactivating a member).

Proof of Access Exclusivity

Access Exclusivity asserts that only members of C can read and write to the shared data store.

  • Read-Access Exclusivity
    • Only an actor is possession of the community keyring ("[]kC") has the ability to read community-public content residing on 𝓛C. See Proof of Signal Opacity.
  • Write-Access Exclusivity
    • There are three layers that prevent the unauthorized mutation of 𝓛C or a community replica/repo ("𝓑i"):
      1. 𝓛C Postage, the mechanism ensuring that 𝓛C will only accept storage transaction txnj if:
        • txnj bears an author that 𝓛C recognizes as having permission to post a transaction of that size, and
        • txnj bears a valid signature that proves the contents and author borne by txnj is authentic.
      2. Community Keyring Access, referring to that only community members are issued []kC.
        • So even if actor Ξ± is able procure postage on 𝓛C, they must also submit an EntryCrypt containing an EntryInfo encrypted using a recent community key β€” otherwise 𝓑i will reject it.
      3. Channel Entry Validation, referring to "deep" validation of entries arriving from 𝓛C. Part of this flow is verifying that:
        • the signature contained in a given EntryCrypt is a valid signature from the member UUID borne by its EntryInfo, and
        • the member is a valid/current member of C (based on 𝓑i's Member Epoch Channel).
    • Given that the members of C maintain exclusive possession of their private keys, only they can mutate 𝓛C or 𝓑i.
    • In the case where m's private keys are possibly compromised, m would immediately initiate a Member Halt, leaving any actor in possession of m's keys challenged or unable to move past the above layers.

Proof of Permissions Assurance

Permissions Assurance asserts the access controls on C remain in effect and cannot be circumvented.

  • In order for a channel entry to be "live" in a node's repo ("𝓑i"), it must repeatedly survive Channel Entry Validation.
    • β‡’ each successive state of 𝓑i is, exclusively, an authorized mutation from its previous state.
  • However, if an important entry is withheld from node ni, it is easy to imagine dependent entries piling up and 𝓑i being at a standstill.
  • In addition to transactions arriving out of order from 𝓛C naturally, we must consider if entries are altered, reordered, or withheld by adversaries manipulating communications signals or infrastructure.
  • We can rule out corruption or alteration of entries since each EntryCrypt bears a signature dependent on its contents, so altered entries would be immediately rejected.
  • So then, could the reordering, blocking, or withholding ("withholding") of entries from 𝓛C cause 𝓑i to pass through a state such that access controls or grants established by members of C could be circumvented or exploited? We separate the possibilities into two categories:
    1. Unauthorized key, channel, or content access
      • These scenarios are characterized by gaining unauthorized access to a privileged key that in turn allows read access to restricted content within 𝓑i.
      • Since any withholding of entries can't result in the additional generation/grant of permissions, the remaining possibility is that withholding entries somehow result in 𝓑i not mutating such that privileged data somehow remains accessible. This is a legitimate concern, however, Channel Entry Validation requires that any mutation that is access-restrictive in nature must also issue a new channel security epoch. In this process flow, only members with access privileges are (securely) issued the newly generated private channel key. Similarly, this is why a new community epoch is issued when a member is deactivated or a Member Halt is issued (but not when a new member is added).
      • β‡’ In the case where entries are withheld from ni, there is no possibility that subsequent entries could reveal restricted material since new peer entries would be encrypted with a newly issued member, channel or community key (after Ξ”C) .
    2. Circumventing access controls
      • These scenarios are characterized by posting maliciously crafted channel entries on C intended to circumvent access controls.
      • Given Proof of Access Exclusivity, we know that in order for 𝓑i to be mutated (or maliciously manipulated), the perpetrating actor must possess both an active member and community keyring.
        • β‡’ this would start with m (or an adversary covertly in possession of m's keys) authoring and submitting said entries in an attempt to somehow sidestep an aspect of the system's channel permissions enforcement. How could an entry go live across C whose parent ACC denies access? Channel Entry Validation's primary purpose is to ensure that only entries that validate under the parent channel's ACC are placed into "live" status.
      • What if m (or an adversary in possession of m's keys) "hot-wires" their node or manually crafts an entry to perform an operation not allowed by m?
        • Although m would be able to submit doctored entries to 𝓛C, Channel Entry Validation running on every other community node would see that m does not have the required privileges and would indefinitely defer (reject) the entry.
        • This is analogous to submitting a transaction on the global Bitcoin or Ethereum blockchain that transfers coinage from an ID that does not have sufficient funds β€” the transaction will never validate.

Proof of Accountability Assurance

Accountability Assurance asserts that members who exercise authority are accountable and remain bound to community policies and expectations.

  • Every member action (mutation) on C is manifested as a channel entry, whether that is a routine content entry or a specially-signed entry in the Member Epoch Channel.
    • β‡’ every member interaction (channel entry) is replicated across 𝓛C, an append-only storage layer, and available for review to all other members of C.
    • β‡’ entries are immutable on 𝓛C and any attempt to conceal or rescind an entry will not alter the original entry.
    • β‡’ all actions in community-public channels, which includes all community administrative reserved channels, are always openly visible for peer review and scrutiny.
  • In private channels, entry content is encrypted and only members granted access by the channel's owner can read the channel's content.
    • By default, not even community admins or authorities can gain access to private channel content unless they have been granted access.
    • Through private channel content is cryptographically secure, some metadata is community-public information β€” namely, who is generating activity, with whom, and how often.
    • Although the actions of a member in private channel π˜Ύπ’‰p cannot be witnessed or reviewed by members outside of that channel, any participant of π˜Ύπ’‰p could be pressured by community authorities to turn over the channel's keyring (or face deactivation or social/legal repercussions).
    • Community authorities are free to make use of private channels (just like other community members), but any action affecting reserved or community-public channels would be publicly available information and would be part of the permanent record that is 𝓛C.
  • Important channels, such as reserved channels or channels used to conduct community governance, could harness the dependable and predictable nature of "smart contracts" on 𝓛C. For example:
    • C has a special community admin account capable of executing community propositions. This virtual agent (and its private keys) are wired into a smart contract on 𝓛C such that β…” of C's "council" members are needed to sign a proposition before the contract's "threshold" signature triggers the proposition to be executed with admin permissions.
    • C makes use of a channel UI extension that in effect recreates a voting booth, allowing the members of C to vote on community propositions. Corresponding smart contracts on 𝓛C would be wired into these channels such that community members would have full assurance that voted propositions are executed reliably and predictably.

Proof of Membership Fluidity

Membership Fluidity asserts that members can be added and deactivated at any time.

Proof of Strong Eventual Consistency

Strong Eventual Consistency asserts that community replicas eventually arrive at the same state and are independent of network delivery.

  • For each node ni in C, it's local replica state ("𝓑i") at a given time is dependent on:
    • The set and order of entries that have arrived from 𝓛C and have been authored locally.
    • Channel Entry Validation reviewing newly arrived entries and entries previously deferred.
  • Given that natural or adversarial network conditions could cause entries to and from 𝓛C to be delayed or withheld:
    • Once all entries replicated across 𝓛C eventually arrive at n1...nN, are 𝓑1...𝓑N each in an equivalent ("consistent") state?
  • This system's Proof of Permissions Assurance implies that the eventual state of 𝓑i is independent of the order of arrival of entries from 𝓛C.

Proof of Practical Security Provisioning

Practical Security Provisioning refers a system's inherent ability to address real-world security incidents. Although this section is intended to convincingly analyze how this system provisions for severe security scenarios, we acknowledge that the more severe and multifaceted the scenario, the more complex and divergent a complete analysis becomes. Given member m in C, this system provisions for:

  1. A scenario where... m loses/erases all copies of their private keyring ("[]klost").
    • A community admin (or delegated member) would use a procedure similar to adding a new member, resulting in a successor MemberEpoch to be issued for m.
    • β‡’ m would fully retain and resume their identity in C, however m would lack the private keys needed to access their private channels.
      • Fortunately, for each private channel π˜Ύπ’‰p that m had access to, m could regain access if at least one other member has at least read-access to π˜Ύπ’‰p (allowing m to successfully petition for the channel's keyring).
      • This could be automated and implemented in various ways, but m would not regain keys to private channels if the members are no longer active (since their client would need to be active to package keys into an entry in response to m's petition).
    • If m were to someday recover []klost, access to past data would be fully restored at no disadvantage.
    • If an adversary were to somehow recover []klost in an unlocked state, they would, at most, have read-access up to the time when m's new MemberEpoch was published.
      • Entries signed by []klost and processed by 𝓑i would be rejected since the MemberEpoch associated with the latest private key in []klost would be superseded.
  2. A scenario where... an adversary ("O") gains access to m's private keys ("[]km") through deception, coercion, or covert access to m's client device.
    • as expected, O would be able to:
      • read all community-public data on C
      • author entries impersonating m
      • read content intended to be private for m
    • When m, a peer of m, an admin, or an automated notices something is amiss, they would initiate a Member Halt on m. As part of the Member Halt:
      1. O would lose append/post access to C (twofold: no postage and m's MemberEpoch suspended), and
      2. O would lose further read access to 𝓛C once a new community epoch is issued.
    • In the case that O issues a new member epoch (impersonating m) before a Member Halt is issued:
      • m would still be able to issue a Member Halt, and
      • an authority within C, in communication with m, would later rescind any entries in the Member Epoch Channel authored by O.
  3. A scenario where... a dishonest community authority ("O") within C covertly wishes to snoop on m.
    • At no point would O have had access to []km since m's private keys never leave m's client process space by design.
      • β‡’ O has no ability to gain access to content encrypted for m, including content in m's private channels.
    • In the event that O posts a new MemberEpoch for m without permission, m would immediately become aware once m's client sees the epoch issued.
      • Hijacking another's identity as in this case would not allow the perpetrator to gain access to any of m's private data since only m has possession of []km.
      • β‡’ O would only gain the ability to impersonate m only as long as m remains offline.
  4. A scenario where... multiple adversaries covertly infiltrate C.
    • Plan A: Surgical Member Halt Attack
      • Since a member halt only suspends a member's access to C, its utility as an attack vector is limited to a one-time DoS for the targeted member.
      • This attack can be quickly be undone by an admin, and the offending member's integrity would immediately move under a spotlight.
      • Limitations could be added that would guard against adversarial behavior. Examples:
        • a member could be limited to ordering one Member Halt per day
        • members could limit whom could order a halt on them, limiting anonymous misuse
    • Plan B: Vandalization of C
      • The authorities of C could:
        1. manually rescind the offending entries.
        2. retroactively deactivate the MemberEpoch of the offending members, resulting in a revalidation cascade as Channel Entry Validation propagates the change.
          • Each dependent entry would automatically be placed into rejected status on each community node during propagation.
        3. hard fork 𝓛C to an earlier state if the vandalism was pervasive (e.g. though postage guards against this, gigabytes of junk appended to 𝓛C).

Proof of Independence Assurance

Independence Assurance asserts that any member subset of C can independently fork C with a replacement governance or leadership structure.

  • Suppose some members of C decide, for whatever reason, that they are better off in their own community ("Cβ€²"), with their own pact of governance or leadership.
  • They desire Cβ€² to be the equivalent of C but only up to a given time ("tCβ€²") β€” at which time the authority structure or membership is arbitrarily altered.
    • Let g be the genesis authority of C at time of its creation.
    • Let []a be the admins of C at time tCβ€²
    • Let []aβ€² be the founders (and admins-to-be) of Cβ€²
  • Given that 𝓛C is append-only CRDT, each transaction is assumed to have a timestamp and identifying ID.
    • β‡’ 𝓛C is characterized as a set of sealed data transactions and can be partitioned at any given time index.
  • The founders of Cβ€² do the following:
    1. Instantiate a new CRDT ("𝓛Cβ€²") and allocate bulk postage identically to 𝓛C's genesis in addition to allocating bulk postage to []aβ€².
    2. Copy the parameters from C's genesis in addition to grant admin status to []aβ€².
    3. Transfer entries from 𝓛C to 𝓛Cβ€² up to time tCβ€² (omitting entries as desired).
      • Allocations from step (1) ensure that transactions copied from 𝓛C and posted to 𝓛Cβ€² will clear.
    4. Once is 𝓛Cβ€² updated up to desired time, []aβ€² can effectively assert control:
      1. They demote or deactivate []a (and any other desired members), and
      2. For each member demoted/deactivated, reduce/burn their postage allocation on 𝓛Cβ€² as appropriate.
  • β‡’ Cβ€² is free to operate independently of C and under the authority of []aβ€².
    • Although Cβ€² is now operating under altered governance or leadership, the privacy of all legacy encrypted entry content is preserved. Otherwise, members from C would have had to disclose their private keys.

Proof of Storage Portability

Storage Portability asserts that C is not permanently bound to its storage layer implementation.

  • Suppose C wishes to switch to an alternative CRDT technology.
  • Using a simplified form of the steps listed in Proof of Independence Assurance, C can coordinate a switch to a new CRDT medium almost transparently.
  • This is to say that 𝓛 is to C as a hard drive is to an operating system. C's "hard drive" can be replaced:
    • with the an updated model, or
    • with a different "brand", or
    • with a different storage technology all together.

On Network Latency

In any system, replicated data transactions and messages take non-trivial periods of time to traverse and propagate across the network. Also, any number of nodes could be offline for indefinite periods of time. No assumptions are made about network connectivity or reachability in this proof, and propagation times are expressed as "Ξ”C":

  • Let Ξ”C be the time period needed for there to be at least a 99.7% chance that all reachable nodes in C have received a given replicated transaction across 𝓛C.
  • Ξ”C serves as a "rule-of-thumb" for characterizing information latency within C. It allows us to more fully express aggregate performance, decision making calculus, and case-study analysis.
  • Although Ξ”C depends on how aggressively 𝓛C trades off redundancy with bandwidth conservation, Ξ”C generally tracks with log(N), given N "well-connected" nodes.
  • β‡’ Even a "dumb" peer-based network has attractive latency characteristics as N increases at human scales. For example:
    • Consider a collection of N=1000 well-connected nodes, having:
      1. a standard distribution of node neighbor latency centered at .2 sec (with Οƒ = .1 sec)
      2. a standard distribution of "swarm diameter" centered at 10 hops (with Οƒ = 5 hops).
    • β‡’ Ξ”C is in the neighborhood of (.2 + 6 * .1) * (10 + 6 * 5) secs (about 1 minute).
    • If N is doubled, then Ξ”C only increases a couple seconds since the limiting swarm diameter increases by 2-3 hops.

Like the way an operating system is only as swift as its host storage system, the latency and "liveness" (availability) of the system presented below is solely dependent on 𝓛. This means that the design tradeoffs that 𝓛C makes will determine C's overall network properties and behavior. Liveness vs Safety discusses tradeoffs for various choices of 𝓛.

Back to README