ADC Extensions

These are the official extensions to ADC. This document is based on the information contained in the ADC wiki - spefications from there are moved here when they are mature and stable enough.

The latest draft of the next version of this document as well as intermediate and older versions can be downloaded from $URL: https://adc.svn.sourceforge.net/svnroot/adc/trunk/ADC-EXT.txt $.

This version corresponds to $Revision: 13 $.

This extension adds Tiger tree hash support to the base protocol. It is intended to be used both for identifying files and for purposes such as CID generation and password negotiation

All files shared by TIGR supporting clients must have been hashed using Merkle Hash trees, as defined by http://www.open-content.net/specs/draft-jchapweske-thex-02.html. The Tiger algorithm, as specified by http://www.cs.technion.ac.il/~biham/Reports/Tiger/, functions as the hash algorithm. A base segment size of 1024 bytes must be used when generating the tree, but clients may then discard parts of the tree as long as at least 7 levels are kept or a block granularity of 64 KiB is achieved.

Generally, the root of the tree (TTH) serves to identify a file uniquely. Searches use it and it must be present in the file list. Further, the root of the file list must also be available and discoverable via GFI. A client may also request the rest of the tree using the normal client-client transfer procedure. The root must be encoded using base32 encoding when converted to text.

In the file list, each File element carries an additional attribute "TTH" containing the base32-encoded value of the Tiger tree root.

In the GET/GFI type, the full tree may be accessed using the "tthl" type.

"tthl" transfers send the largest set of leaves available) as a binary stream of leaf data, right-to-left, with no spacing in between them. <start_pos> must be set to 0 and <bytes> to -1 when requesting the data. <bytes> must contain the total binary size of the leaf stream in SND; by dividing this length by the individual hash length, the number of leaves, and thus the leaf level, can be deducted. The received leaves can then be used to reconstruct the entire tree, and the resulting root must match the root of the file (this verifies the integrity of the tree itself). Identifier must be a TTH root value from the "TTH/" root.

In the GET/GFI namespace, files are identified by "TTH/<base32-encoded tree root>".

In SCH and GFI, the following attributes are added:

This extension adds a special file "files.xml.bz2" in the unnamed root of the share which contains "files.xml" compressed with bzip2 1.0.3+ (www.bzip.org).

There are two variants of zlib support, FULL and GET, and only one should be used on a each communications channel set up.

If, during SUP negotiation, a peer sends "ZLIF" in its support string, it must accept two additional commands, ZON and ZOF. Upon reception of ZON the peer must start decompressing the incoming stream of data with zlib before interpreting it, and stop doing so after ZOF is received (in the compressed stream). The compressing end must partially flush the zlib buffer after each chunk of data to allow for decompression by the peer.

The alternative is to send "ZLIG" to indicate that zlib is supported for binary transfers using the GET command, but not otherwise. A flag "ZL1" is added to the to the SND command to indicate that the data will come compressed, and the client receiving requests it by adding the same flag to GET (the sending client may ignore a request for a compressed transfer, but may also use it even when not requested by the receiver). The <bytes> parameter of the GET and SND commands is to be interpreted as the number of uncompressed bytes to be transferred.

Added 2008-03-14, based on ADC 1.0

This extension can be supported by both clients and hubs, and when present, if hub supports it, it must send additional information to the client ( otherwise normal base client).

It’s purpose is to send to hublist pingers additional information about the hub that otherwise it would be impossible to get as a normal user (eg. minimum share, maximum user count, etc).

Contexts : F

When the client supporting the PING extension connects, the hub must send its normal INF along with the following added fields ( none mandatory, if not present, it means hub has no restrictions in that matter, or non existent):

The hub must continue to send the user list as for a normal user (move to NORMAL state). The pinger may decide to go through or disconnect (eg. if it doesn’t require additional information about the users).

The same extension goes for hub- hublist communication. This way, the hub takes the role of the client and the hublist of the server.

The hublist may send INF about itself with NI field which would become hublist name and WS hublist web address.

Timestamp of the moment when the message was sent, expressed in seconds since the Unix Epoch (January 1 1970 00:00:00 GMT).

The idea behind this extension is to generate a public hublist from the users favorite hublist. Implementations should separate between public and private hubs in the favorite hublist of an user, in order not to distribute private hubs where one can not connect to anyway.

Contexts: T, C

Asks all users within the same hub with the correct feature to send all publicly available hubs, in their favorite hub list to the requesting client.

Contexts: C

Response of a client.

HA | Hub address

LG | Last succesfull login time ( number of seconds since the epoch (1970), (UTC) )

All INF fields from BASE are inherited. All INF fields from PING extension are inherited.

Contexts: F

States: NORMAL

User commands are used to send hub-specific commands to the client which provide useful shortcuts for the user. These commands contain strings which must be sent back to the hub and keyword substitutions in the strings. Each user command has a display name, a string to be sent to the hub, and one or more categories where it may appear. The strings passed to the hub must first be passed through a dictionary replacement that replaces all keywords in the string and then through the equivalent of the C standard function "strftime", with the current time.

Name uniquely (per hub) identifies a particular user command. The name may contain "/" to indicate a logical structure on the viewing client, where each "/" introduces a new submenu level. Other than name, the command also has a number of flags that further detail what to do with it.

Keywords are specified using "%[keyword]". Unknown keywords must be replaced by the empty string. Additionally, all %-substitutions of the C function "strftime" must be supported.

The following tables specify the keywords that must be supported.

Client parameters

User parameters

File parameters

Hub parameters

Bloom filters allow the hub to filter certain searches using bitmap that represents the hashes of the files in the users share. BLOM is an extension that allows hub software to create a map (bloom filter) of the shared files on the hub, but with minimal effort, e.g. the hub doesn’t keep a list of files, but a filter that never produces false negatives but only possible false positives. This can potentially save bandwidth and effort on the client side. When the user updates the share, the client must send an INF containing the flag SF. The hub may at any time request that the client sends an updated version of its bloom filter by sending a GET command to the client. The client will then respond using SND and send the bloom filter binary data.

The hub chooses k, h and m.

Signal BLOM in SUP.

For the SND type, adds H as message type.

For the GET type, adds I as message type.

For the GET type, adds "blom" as type.

For the GET type, "/" shall be used as namespace.

For the GET type, 0 (zero) shall be used as start position.

For the GET type, m / 8 shall be used as byte amount.

Updates GET with the following flags;

The client constructs the bloom filter by creating a bit array of m bits set to 0 (zero). For each file it then sets to "1" k positions constructed from the file hash. Seeing the file hash as a stream of bits (starting from the lowest bit of the first byte, ending at the highest bit of the last byte), the client should use h bits starting at the first bit of the first byte to create an integer and apply modulo m to get the position in the bit array, then redo the process k times advancing the starting position by h each time.

Once the hub has received the bloom filter bit array, for each search command it processes, if it contains a hash search term, it can skip broadcasting the search to a particular client if at least one of the k bits in that clients bit array is "0", calculating positions as the client does when setting bits to "1". The hub has to evaluate the filter for each client that it has a bloom filter for, for each search.

p = (1 - (1 - 1 / m)^(k * n))^k, thus p becomes smaller as m grows and larger as n grows. Larger m means more bits to transfer but also fewer false positives. The optimum value for k given m and n is (m / n) * ln 2. The largest k supported by a hash of a certain size is b / h, so if the hub wants the smallest p possible, it should choose the smallest possible h which gives the largest k, and then calculate m = k * n/ln 2, checking that the resulting m < 2^h. 2^h should much be larger than m (at least 3-4 times), because of how the modulo operator works. Also, with m grows the required bandwidth to transfer the bloom filter, so the hub may wish to cap m. In that case, it should still choose k according to m / n * ln 2, but send an h as big as possible to alleviate biasing problems.

For TTH roots, b is 192 and a reasonable value for h is 24, giving a maximum k = 8 which means that m = 8 * n / ln 2 ≈ 11.5 * n. The required bandwidth then becomes 11.5 * n / 8 bytes, so approximately 1.44 bytes per file in the users share. For 20000 files, m should then be 230016 (taking into account the modulo 64 requirement), giving a p = 0.004, in other words ~99.6% of all searches that don’t match a users share would not be sent, saving valuable upload bandwidth for the hub. The client calculates i valid positions, if x is an array of bytes containing the hash of the file, on a little-endian machine, by doing pos = x[0+i*h/8] | (x[1+i*h/8] << 8) | (x[2+i*h/8] << 16) for i = [0;k). This is of course a special case where h % 8 = 0, the actual algorithm has to take into consideration values for h where the integer crosses byte boundaries.

For test vectors, see the ADC wiki talk page; http://www.adcportal.com/wiki/index.php/Talk:BLOM