CAP autistic.space/merkle-tree
==============================

Copyright (c) 2018, 2020 Soni L. \<fakedme plus irkv3 at gmail dot com>

This capability provides a mechanism for connecting IRC messages together using
merkle trees, and sharing those with clients.

The benefit of merkle trees over conventional logging is that merkle trees are
inherently distributed. This is the reason many developers have moved from SVN,
etc to Git, etc. IRC networks also tend to be distributed, with some networks
having upwards of 10 servers; merkle trees can provide merging logs after a
netsplit, efficient negotiation with the client for which ranges of logs to
send, eventual consistency, among other benefits.

Cap Syntax
----------

The capability shall be specified as

    autistic.space/merkle-tree=hash_type,hash_type/tag,tag,tag

Example:

    autistic.space/merkle-tree=sha-512_256,sha3-256/time,autistic.space/merkle-tree

`time` and `autistic.space/merkle-tree` are always implicitly specified, and
should be omitted. Note that the `autistic.space/merkle-tree` capability
*requires* the `time` capability.

Valid Values for `hash_type`
----------------------------

This specification defines the following valid values for `hash_type`. Future
versions of this specification may update this list. A compliant implementation
MUST only use values defined on this list.

- `sha-224`: SHA-224, part of the SHA-2 family.
- `sha-256`: SHA-256, part of the SHA-2 family.
- `sha-384`: SHA-384, part of the SHA-2 family.
- `sha-512`: SHA-512, part of the SHA-2 family.
- `sha-512_224`: SHA-512/224, part of the SHA-2 family.
- `sha-512_256`: SHA-512/256, part of the SHA-2 family.

These have been chosen because they're not broken yet and can often be
hardware-accelerated. Additionally, althought SHA-512/224 and SHA-512/256 are
on this list, they don't provide any useful advantage, as length extension
attacks do not apply to this specification; they're only here to set precedent
for how to name such algorithms in future versions of this specification.

The `HASH` S2C Command
----------------------

The `HASH` server-to-client command SHOULD be sent from server to client when
a channel has associated hashes and the capability is enabled. In particular,
the `HASH` command MAY be omitted for privacy reasons, e.g. if a user is not
logged in.

Syntax:

    HASH #channel :hash_type=counter/hash,hash_type=counter/hash,...

Example:

    >>> JOIN #channel
    <<< JOIN #channel
    <<< NAMES etc
    <<< HASH #channel :sha-256=20/5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8
    <<< HASH #channel :sha-256=60/305d7abb3a8e806f3806e85f7702d51e2f58269a4e4759fa8f7be7facd8e0fd9,sha-224=70/5a9ea281bc1aa96750edbd2b3d0a462372275c182e01498f54dc8355

Optionally, the server may include a server name with the HASH command:

    <<< :server1.example.com HASH #channel :sha-384=86c736076dfa3b0b1fc0db39074bf0891240d00caeeecdb3457ce71d47d704e82c8a50608f8f9e4f3ea452ec07a11b0e
    <<< :server2.example.com HASH #channel :sha-512=3cb8e3271f9b482781de09cf1d4830f9514fd4315bfb760f8ffe2ee778b16eb0c4b42ef779c653687a8bd568452d345c874ef5ad0ece03799f0638dcc84aa401

The counter MUST be able to store numbers in the `0..2^62-1` range.

These hashes specify the current "heads" of the merkle trees.

The `HASH` C2S Command
----------------------

The `HASH` client-to-server command MAY be sent from client to server to view
and manipulate a channel's hash list.

To view a channel's hash list:

    HASH #channel

To manipulate a channel's hash list:

    HASH #channel :+hash_type=counter/hash,hash_type=counter/hash,...
    HASH #channel :-hash_type=counter/hash,hash_type=counter/hash,...

(To add and remove hashes, respectively)

Viewing a channel's hash list SHOULD be restricted to anyone capable of
joining the channel. This means banned users SHOULD NOT have access to this
command.

Manipulating a channel's hash list SHOULD be restricted to channel operators
only.

The `autistic.space/hash` Message Tag
-------------------------------------

The `autistic.space/hash` message tag is a server-to-client tag that specifies
the parent message(s) of the current message.

The `autistic.space/hash` message tag SHOULD be sent with every `PRIVMSG`,
`TOPIC` (for changes) and `NOTICE`, except where the sender has opted-out or
the receiver is not allowed to see the hashes (such as not being logged in).

The `autistic.space/hash` message tag MAY be sent with `JOIN`, `PART`, `QUIT`
and `KICK`, with the added requirement that the server send separate `QUIT`s
corresponding to each logged channel common between the quitting user and the
receiving user. (FIXME this seems really inefficient, but not sure if there's
a better way...)

Syntax:

    autistic.space/hash=hash_type=counter/short_hash,hash_type=counter/short_hash,...

The `short_hash` is the (optionally shortened) hash of the parent message. The
client MUST be able to reconstruct the full hashes from these. Shortening and
reconstructing the hashes MUST be done with care, and the shortened hashes MUST
be no less than 64 bits in length.

The hash encompasses the message tags specified by the capability (e.g. `time`
and `autistic.space/hash`), sorted according to UTF-8 byte order, and the
contents of the IRC message, as seen in the following format:

    @autistic.space/hash=hash_type=counter/full_hash,hash_type=counter/full_hash,...;time=... :nick!user@host PRIVMSG #channel :message

(This line is what gets hashed)

Note the use of `full_hash` instead of `short_hash`.

Examples:

    TODO

Additional User and Channel Modes
---------------------------------

Logging of user messages MUST be controlled by the use of a user mode, set to
enable logging. Network admins MAY choose whether to set or unset it by
default. Additionally, channels where logging is enabled MUST also have a mode
set. Again network admins MAY choose whether to set or unset this mode by
default.

Security Considerations
-----------------------

Merkle trees are meant for channels that want public logging. As such, anything
in a merkle tree SHOULD be considered public.

If the merkle trees proposed here get used in a peer-to-peer scheme, it becomes
possible to recover deleted merkle trees by setting up a separate IRC network
and sending the right hashes on the right channel. However, you'd still need to
know the hashes. Thus, this isn't a vulnerability, because if you had the
hashes, you could just request the logs directly, without going through the
process of setting up an IRC network. It also requires the use of a scheme not
specified here.

The server can and should be able to "undo" hashes. This is useful if, for
example, someone links to illegal content or content that is against the
network or channel rules - users likely don't want that permanently recorded in
a channel's history. This is provided by allowing channel operators to use the
HASH command to set a channel's hashes.

Users and channel operators MUST be able to opt-out of logging. Opt-out is
provided by this specification through the use of user and channel modes.

[FIXME there may be more]