Rename to merkle-tree, add rationale, and rewrite HEAD default

1 files changed, 175 insertions, 0 deletions

diff --git a/merkle-tree.md b/merkle-tree.md
new file mode 100644
index 0000000..cc09cc3
--- /dev/null
+++ b/merkle-tree.md
@@ -0,0 +1,175 @@
+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]