ARTree

Asynchronous Ratcheting Tree implementation in Typescript

Asyncronous Ratcheting Tree (see ART paper) is PKE and key derivation protocol which allows group of users to agree on using one common key while keeping forward secrecy and asynchronous nature of group communcation.

TLDR: a binary tree of Diffie Hellman keys. Each node is HKDF(DH(A, B)) where A & B are keys of 2 of its children.

The reasons why ART is preferred over over plain ratchets, double ratchets and alike, include:

1. In order to calculate stage (top level) key you need a secret key of one of the leaves and public keys of other nodes. Single secret key is required and is enough.
2. Parent node keys can be calculated by either of its children with all of them ending up with the same top level key.
3. Any leaf can change its key asynchronously. While some members are offline, for example.
4. One key! No need to send N - 1 messages for any message in group of N members.

This implementation is largely based on ART paper, yet it adds several extra features (use with caution, not verified or scientifically proven!) necessary for real world application:

• Ability to split tree leaves and add new users.
• Ability to redistribute up to date tree to users who were offline while other memebers updated their keys. Useful when you don't store messages.

[!WARNING] Note that ARTree does not encrypt messages it produces. It's implied that package user will encrypt messages between ART members with art.stage key. Both synchronous & asynchronous encryption is supported as art.stage is a keypair. That being said, ARTree actually uses encryption in one place: it encrypts stage key transferred to new tree member on split; it does that because encryption key would be tricky to calculate outside of the library.

Getting started

Install

npm install artree

Add your crypto implementaion

ARTree is BYOCrypto, abstracted from crypto implementation, but tested with awesome paulmillr's @noble set of packages:

npm install @noble/curves @noble/hashes @noble/ciphers

import { gcm } from '@noble/ciphers/aes';
import { secp256k1 } from '@noble/curves/secp256k1';
import { hkdf } from '@noble/hashes/hkdf';
import { sha256 } from '@noble/hashes/sha256';
import { randomBytes } from 'crypto';
import { setCrypto, SK, SI, PK, concat } from 'artree';

setCrypto({
  generateSecretKey: secp256k1.utils.randomPrivateKey,
  derivePublicKey: secp256k1.getPublicKey,
  getSharedSecret: secp256k1.getSharedSecret,
  hash_256: sha256,
  sign: function (data: Uint8Array, sk: SK) {
    return secp256k1.sign(data, sk, { prehash: true }).toCompactRawBytes();
  },
  verify: function (si: SI, data: Uint8Array, pk: PK) {
    return secp256k1.verify(si, data, pk, { prehash: true });
  },
  hkdf: hkdf.bind(null, sha256),
  encrypt: function (data: Uint8Array, key: SK) {
    const nonce = randomBytes(this.ENCRYPTION_PREFIX_LENGTH);
    return concat(nonce, gcm(key, nonce).encrypt(data));
  },
  decrypt: function (data: Uint8Array, key: SK) {
    const nonce = data.subarray(0, this.ENCRYPTION_PREFIX_LENGTH);
    return gcm(key, nonce).decrypt(data.subarray(this.ENCRYPTION_PREFIX_LENGTH));
  },
  PK_LENGTH: 33,
  SK_LENGTH: 32,
  SI_LENGTH: 64,
  ENCRYPTION_PREFIX_LENGTH: 12,
  ENCRYPTION_SUFFIX_LENGTH: 16,
});

Start turning!

In order to create ART you'd need identity & ephemeral private keys for initiator and identity & ephemeral public keys for each participant. Also ephemeral keys must be signed with corresponding identity key to prove it belongs to identity secret key owner:

import { ART, Me, Peer, keypair } from 'artree';

const keys = new Array(2).fill(0).map(() => {
  const identity = keypair(); // {sk: Uint8Array, pk: Uint8Array}, Secret Key & Public Key
  const ephemeral = keypair();
  const ephemeral_signature = secp256k1.sign(sha256(ephemeral.pk), identity.sk).toCompactRawBytes();
  return { identity, ephemeral, ephemeral_signature };
});

// Alice initiates ART
const alice = ART.initiate(
  keys.map(({ identity, ephemeral, ephemeral_signature }, i) => {
    if (i === 0) {
      // initiator knows own secret keys
      return new Me(identity, ephemeral);
    } else {
      // initiator knows only public keys & signature of other members
      return new Peer(identity.pk, ephemeral.pk, ephemeral_signature);
    }
  })
);

// Alice also generated setup message which she needs to send to other members
// The message should be encrypted when transferring to them
const setupMessage = alice.setupMessage;

// Bob receives setup message and joins the tree
// He only needs setup message and his identity & ephemeral keys to start turning the tree
const bob = ART.fromSetupMessage(new Me(keys[1]!.identity, keys[1]!.ephemeral), setupMessage);

expect(bob.stage.sk).toEqual(alice.stage.sk); // look Ma, same keys!

// Once set up, members can turn the ratchet at their will
const bobUpdateMessage = bob.updateKey();
alice.processKeyUpdate(bobUpdateMessage);

expect(alice.stage.sk).toEqual(bob.stage.sk); // look Ma, same keys!

See full example in tests.

Tree modifications after initialization

ARTree allows new tree members to join the tree after its initialization:

• Any tree member can replace its tree leaf with a node consisting of 2 leaves: old leaf and new leaf with the same identity key as the old one. Think of one user having multiple devices.
• Tree initiator can add new leaves at arbitrary position.

[!CAUTION] Using this feature (art.split()) is not required and in fact not advised if security is your main concern.

The problem comes from the fact that the very top level (stage) key is an HKDF which uses previous key as one of its inputs. Therefore adding a tree member requires sharing current stage key with this member in order for newcomer to be able to calculate next stage key.

Alternative to current implementation would be not using HKDF for stage key calculation, but that would come at a cost of forward secrecy.

Bottomline: if you don't need to add new tree members after its initialization, better don't.

API

Intro

Peer - a class with public identity & ephemeral keys + signature of ephemeral key by identity key.

Me - a class with identity & ephemeral keypair, generates signature automatically.

SK, sk - secret (private) key.

PK, pk - public key.

ART - main package class.

ART.initiate(peers: Peer[]): ART

Create new tree for given peers. Called by tree initiator. One of Peer objects must be initiator's Me instance. Returns ready to use tree with setupMessage property set to a message to be sent to other members.

ART.fromSetupMessage(me: Me, message: Uint8Array): ART

Recreate tree at non-initiator side from setup message.

ART.fromSplitMessage(me: Me, snapshot: Uint8Array, splitMessage: Uint8Array): ART

USE WITH CAUTION Recreate tree at non-initiator side from split snapshot & message. Used to add new members to the tree after its initiation. snapshot & splitMessage are results of art.split() call.

art.updateKey(key = keypair()): Uint8Array

Replace ephemeral key of a tree member with new one. Returns a message which should be sent to every other tree member. Failure to do so will make them unable to process next messages as their stage key will be outdated. By default key is randomly generated.

art.processKeyUpdate(message: Uint8Array): void

Process key update message from another peer.

art.split(peer: Peer, at?: Uint8Array): {message: Uint8Array, snapshot: Uint8Array}

USE WITH CAUTION Splits one of the leaves into two, adding new member to the tree. Initiator can add members at arbitrary positions (by setting at parameter to leaf's pk), while other members can only add new members with the same identity key right next to their own node (at === undefined). See Tree modifications after initialization for details.

art.processSplit(message: Uint8Array)

USE WITH CAUTION Updates tree with new Peer. See Tree modifications after initialization for details.