AuthChain

Contraction of Authentic or Authored Chains. This is an abstract distributed data structure to represent and store a sequence or sequences of digital messages such that:

1. A chain is permanently connected to a single public identifyer. The public identifyers are connected to asymetric key pairs such that the private key is secured and available to the owner of the identity for signing (authenticating) new messages to be added to the chain, or decrypting private messages. A creation message is authenticated to the identity by generating a signature of the creation message using the private key.
2. All messages are stored in the distributed database indexed by its signature. The identity's public key can be used at any time to validate the authenticity of the message id (storage index) with respect to the message contents.
3. A new message can always be added to a given point in an existing chain. Each new message is chained to the message before by its message id by including it in the new message and then generating the signature for the new message (using the identity's private key to validate the message is authentic). In this way, any message id can be used to authenticate the entire message chain from the new message back to the creation message.
4. The history of every message is a unique chain back to the header, but it is also valid to add new messages again and again to the same point, even to the creation message, of a given chain. Therefore, a nessage id does not uniquely specify the next message, or even whether any next message exists. Applications can use other means to identify the first, or other designated singular next message added to a chain.

An object oriented design will have the following types of object:

• Digital identity: Active identities will have access to both the public and private keys. Ideally the private keys are held in a secure computing device that can sign and encrypt messages using the private key it stores, but never making any copies of that private key (Note 1 ref). This device would generate key pairs and export the public key for storage in the directory service where it will be associated with both a unique ID and other more human centered means of looking up a person's or trusted system's identity and public keys. 
• SecureDevice: Represents a service that will securely store the private key and use that key to encrypt messages or generate digital signatures for them.
• AuthChain: These are created with a creation message and an active identity. This will create a header record that is then signed by the active identity. This signature is the message ID used to index the message in a store. Given an existing AuthChain and an active identity, a new message can be added and signed generating a new message ID for the new state of the AuthChain.
• Message and Message ID: In principle AuthChains are agnostic about message formatting and encoding, however AuthChain applications need to agree. The reference implementation will probable use XML and/or other general data structures that can represent nested externalized data. Objects will need to be serialized into a cannonical format so that all instances of an application will serialize any object in the same way and generate/validate consistently. Stated in terms of invariants, if and only if two objects are the same (equal) they must serialize to the same binary message and 1) compute the same signature (message ID) with the private key or 2) validate that the message and message ID against the public identity (key) of the chain. 

API Summary

Identity:

• Identity.new( secureDevice, message ) -> URL The message will need to identify this user publicly so it needs to include all attributes that will be used by applications to identify and look up public identities. This action will ask the secureDevice to generate a key pair as will as calling the directory service to store a new public identity. The URL will specify the new activeIdentity stored in the secureDevice and can be used with SecureDevice.new( URL )
• Identity.load( URL|Name|FileDescriptor ) -> activeIdentity: Opens an existing identity. Systems settings can select specific secureDevices to try, or it may be specified in a file by name, etc. Alternatively, the secureDevice is contained in the URL.

SecureDevice:

• SecureDevice.new( URL ) -> secDev A URL like: local:path, localdevice:path or FQDNofHost:path. Cases are 1) a local service, 2) A local device (maybe USB or Wifi/Bluetook key fob or 3) a service on the nework. This call opens a connection to the device and returns an object representing the open service or an error if it can't connect.
• secDev.generate( type ) -> localIdentityID  The key pair are stored in the device. The action creates a new localIdentityID in the secure device and it can be openned with new and a URL referencing the secure device and this ID.
• secDev.publicKey( [localIdentity] ) -> publicKey  If the argument is not supplied, the URL must have the ID in it (i.e. you openned an existing identity in the device).
• secDev.sign( message ) -> signature  Computes the signature of a message.
• secDev.encrypt( message ) -> messageEncrypted  Encrypt with private key
• secDev.decrypt( messageEncrypted, [public key] ) -> messageCleartext Decrypt with public key
• secDev.clone( publicKey, [localIdentityID] ) -> cloneMessageEncrypted: Create a clone message containing a private key and encrypt it with the public key of the target secureDevice. For loadClone to work this public key must corespond to the localIdentityID of the secDev you call loadClone on.
• secDev.loadClone( cloneMessageEncrypted ) -> localIdentityID: The secDev object must have the identity of a private key that will decrypt the message (the target) and this method will return a new local ID for the loaded clone.
• secDev.valid?( message, messageID, [ publicKey ] ) Validates the message and ID, returns true when valid.

AuthChain:

• AuthChain.new( activeIdentity, headerMessage ) -> chain: Creates a new AuthChain with no entries (just the header/creation message that will specify what this chain is about, etc. Returns a chain object with no entries.
• AuthChain.get( messageID ) -> chainEntry: Lookup and load a specific chain state. If the ID is a chainID, the chain is empty, it has no messages added to it.
• chain.getID -> messageID: Returns ID of the current (last) entry in the chain.
• chain.getChainID -> chainID: Returns ID of the zero entry (header/creation message) of the chain.
• chain.getMessage -> message: Returns the deserialized message as an object. It will be the header message when the chain is empty
• chain.addEntry( message ) -> newChain: Add message to the chain and returns the resulting chain.

Note 1: Even though these key devices don't normally make copies of a private key, there could be a special case where it is authorized to make a clone of an active identity in a second secure computing device.

Application: Player Chains

Games are both metaphor and example for the general use of authchains. Almost any sort of formal transactions within a community of participants can be characterized as a game in this sense. We can change the language from player to member of even combatant and the formal structure is the same. We like the examples of chess and checkers, two payer games with a small set of formal rules. Without actually writing the rules of each game in some formal system, it is obvious the chess is more complex than checkers, but the complexity of the rules doesn't necessarily reflect the complexity of the game. The rules of go and tick-tac-toe are both simple, but the latter is trivial in play and the former rivals chess.

Although authchains have many other applications, this is the reference use. Distributed games are also an analog of currency exchange in communities. Games and plays in a game are a metaphor for alternative currencies and transactional networks that use them in the course of operations in a gift economy. Here the metaphor is equivalence, just change the labels in the ontology and they are the same thing. Of course, each game (or currency) first creates a set of formal objects that constitute the game space. The objects in the game, the board, the pieces, the payers, etc. A game with two playes woud start with the declaration of the game and associating players with roles in the game. Chess has a black and a white role and a square board, eight squares by eight. Any two player game would start with two chains, one for each player that references the other chain. Bob says: I'm starting this game of chess with Alice. Alice says, I accept, I will be White, and my first move is X, where X is the coding of a legal chess move from the start position. Alice's header references Bob's game header message. Bob can simple echo a reference or make his first move in response. Each new move references the other player's last move and thus the play alternates between the two chains with the current state of the game reflected by the last move. There will always be ambiguity about which chain has moved last. Eac player knows that she has moved, and that move on her chain validates the other player's move that it follows on. I can't prove my last move until I get the other player's next move.

This isn't really a flaw, it is a feature. Bob and Alice can at any time switch to a previous game state and make a different move from there. If the other player finds the switch interesting, they can keep playing it out. Instead of one game, two people can play a whole tree of speculative games. You could play out some standard openings with a learning partner and explore each one and its varients and the system could do counts and statistics for different opening positions.

Or you could put the game in a larger context. Say you want to have a tournament. The tournament hosts could implement the protocols to start games from the tournament schedule. The committee would say Player X is white, Player Y is black, begin. Then each move references the committee's acknowledgement of a move. So, C says begin, X says my move is A, C says X does A, Y says my move is B and C says Y does B, and so on. C can maintain a game clock and put that information in the entries. In fact, C doesn't have to be a personal identity, but rather an avatar of the tournament committee. The messages from C are all automated once the lists of participants are complete and the schedule approved. The avatar might even call for the real committee to make the call for certain situations and exceptions.

AuthChains as a BlockChain Protocol

The use case for chains for flexible community currencies needs more than just the chains themselves, butt a way for distributed particpants to agree on the validity of chains and collective chain states. Most blockchain protocols concentrate on something called a distributed ledger, the state of balances in sets of accounts in various "currencies". In the authchain world, it is the chains of signed transactions added to each chain that are significant. Any participant can calculate  states from sets of validated transactions, but the shared state only need agree on inclusion of transactions on chains, the latest chain states for all chains.

The Universe State Chain

This is the equivalent of the shared ledger of most block chains. Because the protocol is distributed, in theory there can be several universal chains, this is how that works. Any group of chains, represented as a set of IDs and maybe some meta-data, can implement a scalable distributed algorythm to initialize and maintain the shared state of that group.  We will need use cases to merge groups, and maybe to drop chains that are no longer updating (if it is a load issue, they could be recovered in the chain history if they become active again). A universal chain needs to be initialized when there is no previous state, and an initialization record will be created including a set of chains and their initial states. Each node will need to implement the cooperative distributed algorythm to calculate the next entry on the universal chain. This new entry should include by DAG reference the current state of all chains in the universe set. If a chain publishes updates, any groups that it is in should register the change and include that update in the new universe state. The computing nodes for particular chains may go offline and "publish" in a disconnected network and the algorythm should automatically include these updates when they are seen.

An update algorythm with these properties will need to tollerate a lot of asynchrony of updates and many different subsets of updates getting distributed asynchronouly through the network. This can work as long as we 1) add updates iff there are no authchain branching updates, 2) we merge updates by taking the longest chain of two updates for the same chain. In this way, subsets of the network will always agree when they can be in continuous contact, and temporary disconnection results in merging in an effecient and self-correcting manner. So, authchain applications cannot guarantee that all updates that are pending in the network somewhere have been fully integrated into the USC (Universe State Chain) that I participate in, but I can verify that specific chans have updated in my USC as well as what nodes are participants in that group. If I got a transaction from another chain and responded to it, when will I see both of them in the USC? I should see it immediately if the sending node didn't just crash. We would both be part of the same USC and it would add both of our chain updates by the next "tick" of the update clock. If I don't see the transaction in two clock ticks, the sender is probably disconnected, but I still should see the update as soon as the connectivity or time lags straighten out.

Seeing invalid transitions will almost always be a bug or the result of some networking related failure, but it could be the result of bad faith or compromised keys from the sender. The normal operation of application software would routinely check to detect errors and recover from outages, and cases of bad faith and compromise are legal matters that can be at least partly addressed by user agreements. The protocols are designed to be used by trusted teams connected in complex networks and not so much to enforce behaviors as to support good security practices. The applications and tools, when possible, will afford important security related use cases. In general, the private key signed updates are at the core of the trust model,so 1) knowing real aspects of identity and 2) secure handling of private keys will be critical at the team level.

Agorithm Outline

To spread the load and make this scalable, the swarm of active nodes will need to divide up the work and collect the results. It will construct and maintain a data tree as a shared object as in ipfs/ipns. At this point we will note that the network architecture does need to distribute the complete state to all nodes, as well as meet other architectural requirements about resillience and such. In practice, that probably means we re-think some things around "fanouts" as discussed below for scalability.  That said, we want agreement to come quickly even as it has millions, billions or more chains in the full universe. If the "Universe Set" is a somewhat arbitrary nested in a shallow, high branching tree, small subsets of the nodes would each work a particular subset, probably including many of the identities that node subset is responsibile for, the calculation of state updates can proceed something like this.

At each network "tick",  each node iterates through its subset and checks the other nodes updates. There will be several attributes published by each node for agreement: The previous and current state of each chain in its authority, and its value for previous and next universe chain state. When a threshold (majority?) of nodes in the subset have the same previous for UCS value, all should update their previous to that value. Current values are proposed or partial agreements, previous should always be the longest agreed UCS and should be the previous of the next previous value. If a node is not synchronized (has been down, etc.), it may need to skip one or more generations. If it has pending changes not in the current conscensus state, it has to add them on top of those when it re-joins a group. When current values with the same previous are not the same, they are merged. Updates in only one set are just included, updates in both sets are sanity checked for branching and the longest update is included.

The nodes push changes from the fringe subnets to more connected ones and the top of network converges on a single value and pushes that back down to the fringes and everyone updates their current to the synchronized value. Nodes are now free to update previous from current and start the cycle again.

Similar Systems

Doing a little research on alternatives to BitCoin's PoW approach, it seems some are similar to this, from:

C. Ledger

The ledger is the global set of accounts where each account has its own transaction chain (Figure 2). This is a key design component that falls under the category of replacing a run-time agreement with a design-time agreement; everyone agrees via signature checking that only an account owner can modify their own chain. This converts a seemingly shared datastructure, a distributed ledger, in to a set of non-shared ones.

In this system, we don't need the shared ledger to track balances, we make that sort of thing an application level concern. We update the "ledger" with every update to the individual chain, and the only requirement on clients is to publish updates to their chain and verify they get added to the shared resource. As with Nano, we could carry a balance in the transaction blocks, and we definitely want to both send and receive from a chain. Again, that's application level processing. You can implement a Nano-like system by processing the chains and shared state. 1) The sender has to get their "send" message on the global state first, then 2) the receiver can accept it. Once both the send and receive are added to the global chain, we are done. Anyone can validate the "can't spend below zero" rule at the first point of sending and we shouldn't put invalid transfers on our chain. The rules of engagement for the chains and systems involved would decide here, but bad behavior is immediately identifiable and doesn't polute all the chains. You can accept bad transactions, but that would infect your chains and subject your currency to rejections. Or, you can make the transaction rules allow for negative balances as with mutual credit currency systems. Again, transactions might be limited with a max credit or backing currencies but this is a matter internal to the currency application and to how the participants interact within the game as well as external settlement.