A description of the inner working of Entropy

This is largerly outdated or incorrect - update to follow

Entropy is designed to meet several goals at once:

1. Distribute documents in the network in a wide-spread manner, so that it is not practically possible to locate it (i.e. make censorship impossible).
2. Keep documents retrievable even if a part of the nodes keeping copies of them is offline
3. Hide from users, admins or authorities, what node on the network actually keeps parts (fragments, bit-chunks) of what documents (key encryption).
4. Optimize data retrieval for the most common user base with ADSL, where the downstream bandwidth is several times the upstream bandwidth (e.g. 768kbit/s vs. 128kbit/s with many German ISPs).
5. Hide from network operators, what kind of communication happens between nodes of the network (transport encryption).

Entropy is divided into several modules, which are run as separate processes (forked) that use shared memory to communicate with each other. These modules are:

• Peer management with bandwidth limiter
• Peer outgoing connections launcher
• Peer incoming connections listener
• File or Document fragmentation and chunking
• Data store management
• Queues and the routing
• Freenet Client Protocol (FCP) server
• HTTP gateway, aka proxy

Peer management with bandwidth limiter

This module and its process are rather simple. You can configure a maximum bandwidth to use for incoming and outgoing connections. You configure a total number of bytes per second in entropy.conf. The limiter now runs with 10 ticks per second (in file include/config.h there's a line #define TICKS 10) and adds to two shared memory variables 1/10th of the bandwidth per second in either direction. The socket I/O functions use these variables to grab their required bandwidth from. If e.g. a send buffer is 10K bytes and there's currently only 1000 byte/s available, the sock_writeall() function will sleep and later try to get more bandwidth until it is finished writing all the data out. The various processes of the connections are concurrently trying to lock the bandwidth variables down and get a fraction (80%, hard-coded in src/sock.c) of the rquired bandwidth until they're done.

This method is perhaps far from perfect and some operating systems may have much better ways to limit a socket or network bandwidth. However, Entropy runs on systems where such things are not available and there is no general standard anyway. Entropy at least allows you to keep some spare bandwidth for your other jobs and this is all of what the bandwidth limiter is intended to do.

Peer outgoing connections launcher

Entropy has its very own way of finding out about possible peer nodes it can contact. Besides the initial list, which is defined by listing some hostname:port or ipaddr:port lines in your seed.txt file (or whatever you want to call it in your entropy.conf), a node tells its outgoing connections about other connections it has evey now and then.

These so-called node announcements are made inside the network. For this purpose, a node creates a file with zero contents but meta-data only. In this meta-data there is an XML text specifying some information about a node:

• node's IP address
• node's contact port (world accessible port)
• node's preferred encryption module

  <?xml version="1.0" standalone='yes'?>
  <p2p>
    <peer hostname='aaa.bbb.ccc.ddd' port='nnnn' />
    <crypto module='something' />
  </p2p>

These announcements are now kept in documents (with zero length) in the meta-data part. The documents have known names. The current names are:

1. entropy:KSK@utc-timeslice-ipaddr:port
2. entropy:KSK@utc-timeslice-2-digit-hex-value

A node's outgoing connections launcher does look up all 256 possible keys of the current timeslice until it finds an entry that is:

• not yet connected
• not blocked (due to errors or permanently)
• resolvable (if it is a hostname)

If a connection fails, the peer's IP address and port are entered into a failure list (in shared memory). If this happens for the second time within some time (currently 1 hour) the peer's IP address and port is blocked for 10 minutes. It is therefore put into the blocked list with a timestamp of now + 10 minutes, which means the peer_node_search() function in src/peer.c will skip this ip/port for some time.

You might wonder if two nodes could produce the same 2-digit-hex value for a specific time slice? Yes, they could and they sometimes will do. It just isn't much of a problem, since one of the keys will be somewhere on the network. The next time slice changes the resulting numbers and the possibility, that two nodes constantly collide in their announcement keys, is very low (except they had the same ipaddr/port -- which cannot happen if you think about it :). Should the net ever become so big that 256 slots are not sufficient for every node to find enough outgoing connections after some time, I might as well add another digit of the hash and then search for 4096 slots. I don't believe that this will ever be needed, though.

Peer incoming connections listener

This module and process is rather simple. It sets up a socket, binds it to the special IP address 0.0.0.0 (IPADDRANY) with the specified port number for Entropy (nodeport= from entropy.conf), so that anyone can contact it and then listens for incoming connections. Whenever the listen() call returns, a new connection is accept()ed and a new child process is started to handle the incoming connection.

This child process first checks that there is a free slot for incoming connections. If a node has 32 incoming connections, it won't accept any more. This did not yet happen, since the network is just too small, but it is supposed to happen.

Whenever a new inbound connection arrives, our forked process first generates a new McEliece private and public key pair. It then sends the public key to the connecting peer. This public key is a string of 1024 * 654 bits = 83'712 bytes.

The peer node receives this public key, retrieves a 4096 bytes session key or seed from its PRNG (pseudo random number generator) and encrypts the data with our public key. The encrypted session key is then written into an initial message, which is then compressed (using LZW) and is now send to our node.

Our child process reads this first, initial message from the peer node that contains a XML text block of the form:

  <?xml version="1.0" standalone='yes'?>
  <p2p>
    <peer hostname='node.somewhere.net' port='nnnn' />
    <node type='entropy' major='0' minor='0.30' build='xyz' />
    <store fingerprint='[32 hex digits]' />
    <crypto module='something' size='xxx' initial='[2 * size hex digits]' />
  </p2p>

The node tag and the attributes there should be obvious. This is purely informational for now but might be used to e.g. block certain implementations or (broken) builds from polluting the network. Of course, someone with malicious intent could fake these fields, as they are not verified in any way.

The fingerprint attribute of the store tag does serve an important purpose. A node's fingerprint determines its place in the routing inside the network. Such a fingerprint consists of 16 byte-sized values, i.e. unsigned numbers between 0 and 255. The node derives its own fingerprint by weighing the number of keys of certain kinds in its data store. For routing purposes and the fingerprint, Entropy simply uses the last digit of the SHA1 hashes of the keys. So if a node has a maximum of 1000 keys ending in 9, 500 ending in 3 and 100 ending in f, and some more keys in unimportant amounts (say below 10) its fingerprint will look like this:

01 03 00 7f 00 02 00 00 01 ff 00 00 02 00 00 19

Fingerprints are updated from time to time (currently every five minutes) when a node sends its current fingerprint as message to all contacted peers. This happens in the set of functions that is announced in the log files as node maintenance. A noticeable difference of the MSG_FPR message from other messages is that this special message contains a hops to live value of zero. Messages with hops to live zero wouldn't normally leave a node and this is to indicated that a fingerprint will only reach the next hop, our direct contacts. So if a node's fingerprint changes -- slightly or dramatically, e.g. becuase it collected a lot of data from local or from other peers -- its peer nodes will be informed about what to expect from it or what to send to it. The whole story with fingerprints is nothing more -- and nothing less -- than a way to load-balance the network and to diverge keys, so that they are kept in different places in the network.

In the final tag of the initial message (crypto) a node tells its peer about what crypto module it intends to use and what initial data, seed or session key it will use. The crypto module= names are simple placeholders for the implemented methods. I am experimenting with some stream-cipher number generators and Entropy currently prefers a module 'crypt3', which is an implementation of an S-box algorithm. Other modules do nothing (crypt0 is a null-layer which you might want to disable by adding it to crypto_reject= line in entropy.conf) or experimental. Except for crypt0 they all do their job to produce a difficult to guess stream of pseudo random bytes, though.

Our node, and only our node, can now decrypt the initial='001122...' part of the first message using its McEliece private key. It does this and then initializes the selected crypto module with the 4K bytes of pseudo random data that came from the peer which just connected to our node. From then on, all messages on this channel will be encrypted using the selected stream cipher and session key or seed.

File or Document fragmentation and chunking

The first thing that Entropy does to any document or file that is to be inserted into the network is to chop it into fragments.

Fig. 1 - Fragmentation

Each fragment of a file is then hashed using two algorithms: EK5 (which is a modified MD5 hash for Entropy's encryption key purposes) and SHA1 after encryption. But let's first look at the encryption of a fragment:

Fig. 2 - Fragment encryption

The Lili2 algorithm's LFSRs are 128 bit (clock) and 127 bit (data). I used the 128 bit EK5 hash digest to seed the clock, and in word reversed order to seed the data LFSR. Then the resulting stream of bits is XORed with the plain text of a fragment, one byte at a time, to produce the encrypted fragment.

After the fragments are encrypted, they are now chunked and at the same time FEC encoded (Forward Error Correction). I called the FEC scheme that is used in Entropy FEC84, because it produces 4 chunks of check bits for every 8 chunks of data bits. At the same time -- and by pure coincidence(?) -- this can be seen as a relation to George Orwell's horror scenario of a total surveillance state in his book "1984". Entropy does really split up the data into bits, so for each 128K byte fragment of data you get 8 times 128K bits chunks, which makes 16K bytes again, after the bits are grouped back into octets.

Fig. 3 - Chunking

So as you can see, the FEC84 encoding process produces 50% of redundancy for any fragment that is inserted into the network. This means that any file of a size of e.g. 100K actually needs twelve chunks, or 12 times 16K of data store. Why is this? The FEC code makes it possible to reconstruct the 128K of data from any 8 out of the 12 chunks of a fragment. This is a essential part of the ability of Entropy to heal data while retrieving it on your node. If any eight of the twelve chunks of a fragment could be found, your node will reconstruct the missing four chunks and (sometimes) spread the reconstructed chunks further. This also means that not necessarily all of the 50% of redundancy has to be sent through network connections. In fact, this approach of chunked fragments makes it even harder to tell what a node was doing: it receives some (up to eight) chunks of data and then emits some (up to 4) new chunks of data. Did this node insert the data or just recreate the chunks? This is impossible to tell without looking what the node's program code was doing.

So the final shape of the data comprising a document or file is the chunk of at most 16K bytes, plus a XML document describing its construction:

Fig. 4 - Keyroute

The XML document that was mentioned several times now, and that is the key to the otherwise unusable data in any data store, looks like this:

  <?xml version="1.0" standalone='yes'?>
  <content size='xxx' key='abcdef...,...vwxyz'>
    <fragment number='x' mode='fec84' size='xxx' key='ABCDEF...,...VWXYZ'>
      <chunk number='0' hash='000000...000' />
      <chunk number='1' hash='111111...111' />
      ...
      <chunk number='b' hash='bbbbbb...bbb' />
    </fragment>
    <fragment number='y' mode='fec84' size='yyy' key='012345...,...6789~'>
      <chunk number='0' hash='000000...000' />
      <chunk number='1' hash='111111...111' />
      ...
      <chunk number='b' hash='bbbbbb...bbb' />
    </fragment>
    ...
    <metadata size='xxx'>001122334455...ff</metadata>
  </content>

The list of fragment elements can contain zero (sic!) or more entries. If a document does not contain any data at all, but only meta data, or if the data fits into a second format (see below), there are no fragments listed in the XML document.

In the fragment number='x' x is a zero based hex digit string, so the first fragment has number='0', the second number='1' etc. For now the encoding mode of a fragment is always mode='fec84'. This might change in the future and is why each fragment has its own mode associated with it. The fragment's key='xxx...,...yyy' string is constructed similiar to a top level CHK@. In the entropy log files you can see this type of keys denoted as BIT@ keys if you turn up the loglevel. It consists of the base64 encoded SHA1 hash of the encrypted fragment's data and the decryption key, which is at the same time the EK5 hash of the decrypted fragment's data.

For mode='fec84' every fragment contains a list of twelve chunk elements, and each chunk has as its attributes a number (again a zero based hex digit string) and a hash. The hash is the SHA1 hash of the chunk as it was described below the last picture above. The size attribute of the fragment is 128K (131072 decimal, stored in the XML as hexadecimal number, i.e. size='20000') in most cases, except for the last fragment, which will often be shorter than 128K.

The metadata element of a document contains what was attached from the FCP protocol when a document was inserted. This is usually the Freenet compatable description of a document, including a Revision=1 number (which is unused in both, Freenet and Entropy :) and things like the Info.Format=mime/type format description. It could be any kind of data you want to assign, if Freenet (and proxy) compatibility is not an issue for your client application.

Each such XML document is now squeezed using the LZW compression that is part of Entropy. This usually reduces the size to something between 50% and 90% of the pure text. Should the resulting LZW squeezed buffer become smaller than CHUNKSIZE (which is 16K), then the data is encrypted just as a fragment, using its EK5 hash and Lili2. The resulting CHK@ key is then a combination of the SHA1 hash of the encrypted XML chunk and the EK5 hash of the unencrypted chunk. A CHK@ chunk is not discernable from one of the BIT chunks. It is also routed just the same, according to its keyroute for the SHA1 part.

Whenever Entropy tries to access a CHK@ key, it actually looks for the chunk with the SHA1 hash specified in the frst part of the CHK@ (the SHA1 part). Together with the second part of a CHK@, the EK5 hash, this piece of data is then decrypted using the EK5 seeded Lili2 algorithm (which is, of course, symmetric). The resulting decrypted buffer can be LZW expanded and then be parsed by the expat XML parser.

At this stage, Entropy has a complete list of the parts that make up a file in memory. It can try to reconstruct fragments by looking for the chunks of each fragment. As was said before, it is sufficient to have any eight of the twelve chunks available to reconstruct the fragment. Any of the chunks that are not locally available can now be requested from the contacted peer nodes. This is done quasi-parallel for the twelve chunks of each fragment, so that ideally the eight quickest replies from eight out of sixteen (or more) peers with optimum routes/fingeprints for the chunks fly in. The first eight chunks of (up to) 16K are sufficient to reconstruct a 128K fragment. Some routes for certain chunks may be (currently) not available, the peers with optimum routes may be overloaded or slow, and this is why it might take some retries to get at least eight chunks for each fragment. This is done in various ways, also by asking not-so-optimal peer nodes for a chunk during the retries and by asking the same nodes again after a certain timeout for a key, which depends on the HTL (hops to live) value with that this key was requested from a neighbour node.

If, however, eight of the chunks listed for a fragment make it into your node's data store, this fragment is complete. Fortunately this is what happens quite often, as long as content is kept alive by some nodes requesting it or inserting it again. Entropy verifies that the hash for the fragment matches the SHA1 from the XML document and, if it does, then writes out the decrypted fragment to the temporary file storage. Should any of the twelve chunks still be missing, they are now reconstructed and sometimes advertized to your peers. Then the next fragment is tried, and this continues until all fragments of a file are collected in your data store. Note that this still does not mean that the file you just requested is in your data store in any plain format. It is, however, in the temporary file storage and from there it is on the way to either your browser, the news entry tables or some of your FCP client applications.

Finally, when the document is complete, and its validity was verified by comparing the overall SHA1 hash (the hash of the entire document's encrypted data) with that from the original key, the temporary file is sent to the requesting program.

One sentence above mentioned the constraint that a LZW squeezed XML document fits in CHUNKSIZE. What happens if it does not fit? In this case the document itself is stored as a temporary file and inserted as if it was a user's file. This is an indirection which could even be required several times for very large files, and which is resolved whenever the document is requested. If a file resulting from collecting and decrypting a CHK@ key has an internal key type, it is not immediately send to the frontend application requesting the key, but instead parsed as the next, larger layer of an XML document. This document then describes a longer list of fragments with more chunks. The whole process continues until the outermost XML document, the one that really describes a user's document, was collected and reconstructed.

Another exception mentioned above was for XML documents without fragments. If a document or file can be LZW squeezed entirely into a 16K buffer, it will be stored as a short key. This type of keys avoids the necessity to handle the XML chunk and twelve data and check bit chunks for small files. The XML document that is stored under the CHK@ of this type of keys looks like this:

  <?xml version="1.0" standalone='yes'?>
  <content size='xxx' key='abcdef...,...vwxyz'>
    <data size='xxx'>001122334455...ff</data>
    <metadata size='xxx'>001122334455...ff</metadata>
  </content>

Data store management

The basic (and maximum size) element of data inside the Entropy network is a chunk, which is at most 16KB in size. See section File or Document fragmentation and chunking for a description of the fragmentation and chunking that entropy does on any data. The data store must thus be capable of holding a large number of quickly identifiable, rather small files or pieces of data: the chunks.

The probably most efficient type of data store to use for this type of data is a monolithic store, which happens to be the default configured in Entropy's Makefile. This data store is set up as a set of few, big files. Each file will be of a fixed size of up to slightly more than 1GB in size. The position of a chunk in this store is derived from its SHA1 hash. Only a few bits of the hash are used and so collisions are possible (and happen). Therefore keys are also stored in not-so-ideal places in the store: up to 16 positions after an ideal place are scanned for an empty slot (when inserting) or for the key (when retrieving).

This data store type seems to have the least impact on the overall system performance on operating systems that have far-from-perfect handling for huge amounts of small files (namely Windows).

Entropy's second type of data store, the store_tree type data store, is kept in a tree of directories below a configurable base path; storepath=store is the default in entropy.conf. Depending on the setting of storedepth=x in the configuration, there is a zero, one, two or three level tree of directories. Every directory's name is just one lower case hex digit, that is a number between 0-9 or a-f.

The best storedepth to choose depends on the abilities of your filesystem. For most Unix filesystems and also NTFS, a storedepth of 1 seems to be a good choice. Whenever Entropy is looking for a key or looking for a place to store a key, your system has to traverse the directory contents to see if a given filename already exists. If you intend to have a huge store, it will probably be wise to not use a flat directory, that is: all files in one directory (storedepth=0), because then there will be several hundred thousand or even million filenames to be scanned for every action.

On the other hand it is not wise to choose a deep nesting for the directories, if you're going with the default store size or not much more. The reason is that your system will be able to keep some directories in memory. The system will try to do this for some recently accessed directories, but perhaps not for 256 (storedepth=2) or even 4096 (storedepth=3). On FreeBSD on a UFS file system I got the best results with storedepth=1.

Now how does Entropy decide where to look for a file? Each file's name is a 40 hex digit string. It represents the SHA1 hash value for the file (= key). For most files, this is the SHA1 hash of the contents of the file: for the bit chunks. For redirecting keys (CHK@, SSK@ and KSK@) however, the file's name is the SHA1 hash of the contents of the file you would get if you reconstructed the contents from the list of chunks inside the key.

For the details of how a directory for a key is choosen by entropy, take a look into src/store_tree.c. The last four digits of the SHA1 hash are used to pre-select a directory and determine the routing. The fourth digit from the right is used to determine the first directory level, the third digit for the second level (if any), the second digit for the third level (if any). The last digit is not used in the store, but to build fingerprints and to decide on routes.

Queues and the routing

There was much talk about fingerprints, routes (or types of keys) and the keyroute function that calculates the route for a specific key. How does Entropy decide which nodes get what key, or which nodes are asked for a specific key? First, here is a graphics showing how the decision process works:

Fig. 5 - Queues

For very low hops-to-live values, the threshold level is very high (255 or 100%), while for the highest hops-to-live value (usually 25) it is very low (0). The range of thresholds is between 0 to 255, because each fingerprint is comprised of 16 unsigned characters (or bytes), too. If a contacted peer's fingerprint value at position X is greater or equal to the current threshold, Entropy would try to insert a message into this peer's queue. The question marks in the cirles left of a peer contact are a placeholder for the question "Does this contact's fingerprint at position X match the current message's keyroute X well enough?". The answer is a simple yes or no.

In the graphics, the first peer Peer #1 would have a well enough matching fingerprint for our key. The red dots however show that this peer's queue of messages is currently full, so this node won't get a message regarding the current key. In our example the fingerprint for Peer #2 would indicate that this node doesn't probably want (or have) keys of type X, and also Peer #3 would in most cases not accept keys of type X from us (or deliver keys of type X to us). This is sad, because Peer #3 has a currently empty queue. For Peer #4 the fingerprint[X] value would be equal to or above the current threshold and - hooray! - this peer even has some empty places in its queue. And also Peer #5 is good enough to get this message, only that its queue is a little more loaded than that of Peer #4. This usually means that it takes some more time until the message is acutally sent out.

So in our example, the message for a key with route X would be delivered to two of our outbound contacts. This message could e.g. be a request for a key. In the given example Peer #4 would most probably see the request earlier than Peer #5 (though a variety of circumstances could lead to Peer #5 getting the request earlier: Peer #4 could be too busy to accept incoming data, Peer #5 could be on a much faster connection, the local scheduler could for some reason decide to give the process handling Peer #5 more time than the others...).

The queues on each outbound connection are a measure taken to decouple the message handling from the current process' timing. A key is inserted or requested and the messages handling this action are posted into selected peer node's message queues. Then the active process waits some time, depending on the amount of messges to be sent, the available bandwidth at this time and the number of hops-to-live of a message, before it goes on. In case of a key request the process checks the local data store if the key (or keys) already arrived in our node.

As you can see, there is no handshake of any kind on the outbound connections. They just get messages including a key and sometimes a key's data. Our node does not know if the peer node really handles this message, if it ignores it or if it forwards the message to another node.

You may ask how results can be obtained without any handshake going on? Our node has some inbound connections, too. On these inbound connections other nodes send us messages, just as we send messages to them. After sending a request to one or more nodes in the outbound direction, we will eventually see one or more advertizements of any key, or inserts of exactly that one key we requested, on one or more of our inbound connections. Advertizements are sometimes ignored (depending on our own fingerprint and the advertized key's route, as well as a random decision to accept or ignore a key). Inserts are usually accepted, unless we already have a key. Inserts are further "guarded" by a list of previously requested keys, so that no neighbour node can flood our store with data that we didn't want - either on our own or on behalf of another node requesting it from us.

Freenet Client Protocol

The Freenet Client Protocol, as the name suggests, was designed by the developers of Freenet. It is a specification for a set of names and conventions for a client application to talk to a Freenet node. Entropy implements a very similiar interface, except for some minor differences that should not hurt any well designed client (some differences _do_ hurt FCP clients, but that is because they are relying on undocumented details or definitions of Freenet).

A Freenet node usually listens on 127.0.0.1:8481 for FCP clients, that's why I've chosen the default port number (or service) 8482 for Entropy. You can run both, Freenet and Entropy, on the same machine without collisions.

After a client made a socket connection to the FCP port, it will send a request that is plain text for the most part. But prior to any text, it must send a header of four bytes. This header might be used for protocol identification in the future. Right now, the only possible and accepted header is 00 00 00 02 - this is true for Freenet as well as for Entropy and all FCP clients seem to have this hardcoded.

The text part of every Request consists of two or more lines, terminated with CR (\n in C notation). The first line is the type of request that is send. Then there can be from zero to several lines with parameters for a request, and finally there is a message terminating line.

The list of commands or requests that entropy understands is as follows:

• ClientHello ... EndMessage
• ClientGet ... EndMessage
• ClientPut ... Data
• GenerateCHK ... EndMessage
• ClientDelete ... EndMessage
• GenerateSVKPair ... EndMessage
• FECSegmentFile ... EndMessage
• FECEncodeSegment ... Data
• FECDecodeSegment ... EndMessage
• FECMakeMetadata ... Data
• GenerateSHA1 ... Data

ClientHello

[00][00][00][02]
ClientHello
EndMessage

NodeHello
Node=ENTROPY,0,3.0,215
Protocol=1.2
MaxFilesize=1fffff
EndMessage

[00][00][01][02]
ClientHello
EndMessage

NodeHello
Node=ENTROPY,0,3.0,215
Protocol=1.2
MaxFilesize=1fffff
MaxHopsToLive=a
SVKExtension=BCMA
EndMessage

ClientGet

ClientGet
URI=entropy:KSK@gpl.txt
HopsToLive=19
EndMessage

NodeFailed
Reason=Some description of the reason why the request failed
EndMessage

URIError
URI=xxx
EndMessage

RouteNotFound
Reason=No route found
EndMessage

DataNotFound
Reason=No data found
EndMessage

ClientGet
URI=xxx
[HopsToLive=xx]
[MaxFileSize=xxxx]
[Verbose={boolean}]
EndMessage

NodeGet
URI={internal-fragment-key}
Offset=xxx
DataLength=xxx
Percent=dd%
EndMessage

DataFound
DataLength=xxxx
MetadataLength=xxxx
EndMessage

DataChunk
Length=xxxx
Data
{raw binary data}

ClientPut

GenerateCHK

ClientDelete

GenerateSVKPair

FECSegmentFile

FECEncodeSegment

FECDecodeSegment

FECMakeMetadata

GenerateSHA1