diff options
Diffstat (limited to 'merkle-tree.md')
| -rw-r--r-- | merkle-tree.md | 175 |
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] |