Introduce a new DAG element kind
Stream is a list containing stream elements. A stream element is a union of:
NonceValue is a list of two elements
[nonce, data]. The
data values may have any type; however, for a stream to be valid all nonce elements in the stream must have the same type, and that type must be ordered according to the nonce ordering rules (to be defined). In many cases a nonce will be simple integer, and might represent a timestamp, a block height (in a blockchain application), or a byte offset, depending on the application.
All elements in the
Stream must be a
NonceValue, with the exception of the last element, which must be either a
Link, or null. We refer to this as the terminating link.
Link element of a stream must reference a block in which the root element is a
Stream. The nonce values in the referenced precursor must have the same type as the referencing stream (aka the subsequent block).
So far, there is no particular reason why a
Stream could not be represented as a struct. However, we now specify the following hard constraints:
- The CID of a block which has a
Streamas its root element should always be constructed with the same hash algorithm, codec, and base as the terminating link.
- The Hash algorithm chosen will always have a Merkle-Damgard construction.
- The hash value of the terminating link will be used as the initialization value for calculating the hash of the block. The terminating link does not otherwise contribute to the hash of the block.
- The hash of a
Streamblock is calculated by hashing the stream elements in nonce order
- Nonce values in a subsequent block must be greater than any nonce value its precursor block.
Validating these constraints will be significantly easier if the Stream has a distinct node type.
The interface of an IPFS node will be enhanced with the following methods:
Rewind (cid, nonce) -> [ Stream, cid ]
Listen (cid, timeout) -> [ [ Stream, … ], cid ]
Rewind method implements an optimized search for the first stream block in the sequence of precursors which has a nonce value less than the specified nonce. If no such block exists, the last block in the sequence (the block containing a null precursor) will be returned. Both the matched block and its CID are returned.
Listen method returns all known blocks subsequent to the specified block in nonce order (the block with the greatest nonce will be returned last). If no subsequent blocks are available, the call will wait for the specified timeout period. If the node discovers any new subsequent blocks before the timeout expires, those blocks will be returned. The CID of the most recent block is returned at the end of the list.
The construction has some useful properties:
- The CID of the most recent block in the chain is independent of the way that data is distributed amongst is precursor blocks; a single block containing all the stream elements will have the same hash as the head of a large chain of blocks containing the same stream elements.
- The sequence of blocks returned by the
Listenmethod is incrementally verifiable; the terminating link in each subsequent
Streamblock can be used to verify the data in the precursor block.
- Consequent to these first two properties, a call to
Rewindcan either walk an existing static chain of stream blocks, or dynamically create a sequence of stream blocks optimized for the nature of the request; for example, thin clients might set a low limit on the maximum block size.
- Nonce information encoded in the stream enables IPFS nodes to create caches of stream data that are known to be complete for a given nonce range. Thus some searches within the stream which are also bound by a given nonce range may be conclusively answered from cached data.