Rename to merkle-tree, add rationale, and rewriteHEADdefault

3 files changed, 179 insertions, 124 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..321db3b
--- /dev/null
+++ b/README.md
@@ -0,0 +1,4 @@
+`merkle-tree` Capability
+========================
+
+This is the specification for the `merkle-tree` IRC capability.
diff --git a/clog.md b/clog.md
deleted file mode 100644
index 8466e27..0000000
--- a/clog.md
+++ /dev/null
@@ -1,124 +0,0 @@
-CAP soniex2.github.io/clog
-===============
-
-Copyright (c) 2018 Soni L. \<fakedme plus irkv3 at gmail dot com>  
-
-This capability provides a mechanism for identifying and conveying a cryptographically secured list of messages to IRC clients.
-
-This specification also suggests a mechanism by which IRC clients can sync logs, using the information provided by this capability.
-
-Cap syntax
-----------
-
-The capability shall be specified as
-
-    soniex2.github.io/clog=hash_type,hash_type/tag,tag,tag
-
-Example:
-
-    soniex2.github.io/clog=sha1,sha256/time,soniex2.github.io/clog
-
-`time` and `soniex2.github.io/clog` are always implicitly specified, and should be omitted.
-
-The `HASH` S2C command
-----------------------
-
-The `HASH` server-to-client command shall be sent from server to client for hashes associated with a channel.
-
-Each hash must be a cryptographic hash. Non-cryptographic hashes must be ignored. Broken hash algorithms should be avoided. MD5 is explicitly disallowed and must not be used.
-
-The counter must be able to store numbers in the `0..2^62-1` range.
-
-These hashes specify the current "heads" of the clog. This is similar to git heads, if you're familiar with them.
-
-Syntax:
-
-    HASH #channel :hash_type=counter/hash,type=counter/hash,...
-
-Example:
-
-    >>> JOIN #channel
-    <<< JOIN #channel
-    <<< NAMES etc
-    <<< HASH #channel :sha1=20/something_long
-    <<< HASH #channel :sha1=60/something_else,sha256=70/another
-
-Optionally, the server may include a server name with the HASH command:
-
-    <<< :server1.example.com HASH #channel :etc
-    <<< :server2.example.com HASH #channel :other
-
-The `HASH` C2S command
-----------------------
-
-The `HASH` client-to-server command shall 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,type=counter/hash,...
-    HASH #channel :-hash_type=counter/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 shouldn't have access to this command.
-
-Manipulating a channel's hash list should be restricted to channel operators only.
-
-The `clog` message tag
-----------------------
-
-The `clog` message tag shall be sent with every `PRIVMSG`, `TOPIC` and `NOTICE`.
-
-Syntax:
-
-    soniex2.github.io/clog=type=counter/short_hash,type=counter/short_hash,...
-
-The use of `short_hash` lowers bandwidth requirements. Consult your cryptography expert for best practices on using cryptography.
-
-These hashes specify the previous "head(s)" of the clog. "Merges" are just messages with hashes from different sources.
-
-The hash encompasses the message tags specified by the capability (e.g. `time` and `clog`), sorted according to UTF-8 byte order, and the contents of the IRC message, as seen in the following format:
-
-    @soniex2.github.io/clog=type=counter/full_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
-
-Security Considerations
------------------------
-
-Clogs are meant for channels that want public logging. An example is the Rust IRC channel. As such, anything in a clog should be assumed public.
-
-It's possible to recover deleted clogs 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.
-
-The network could be made to sign all hashes, but you'd need to share the signing key across all servers for it to work correctly. This still doesn't prevent someone
-from getting access to an intercepted, correctly-signed hash, and by sharing the signing key you increase the attack surface.
-
-The server can and should be able to "undo" hashes. This is useful if, for example, someone posts child pornography - you likely don't want that permanently recorded in a channel's history.
-
-[FIXME there may be more]
-
-The `SYNC` CTCP (informative)
------------------------------
-
-*This section is informative.*
-
-The `SYNC` CTCP is a hypothetical CTCP for syncing logs.
-
-Syntax:
-
-    SYNC <tox-compatible public key> <port> <host> <host> <...> -[nospam+checksum]
-
-This is a highly flexible command supporting ipv4, ipv6, hostname, tor, i2p and tox ID.
-
-Messages sent over non-tox channels must be encrypted with the tox-compatible public key.
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]