Clarification of messages in blocks, headers, and network vs implementation structures

anorth commented 5 years ago

I'm seeking an understanding of the motivation behind proposal #94 (and spec detail #250), to reference messages in blocks by CID in a merkle-tree-like structure. The corresponding issue in go-filecoin is https://github.com/filecoin-project/go-filecoin/issues/1324 and there are other mentions of the idea. Without understanding the goals, it's hard to judge concrete technical proposals or ensure that other parts of the system work in concert.

It's quite likely that I'm missing some key piece of context like a use case, desired capability, or philosophical foundation that motivates this. In that case, resolution probably involves documenting that context. It's also possible that the existing proposals are missing some key pieces that would make it all make sense.

I'll try to lay out my understanding and make some guesses at motivations, to which I can then respond. I'm also going to ask some questions – I have a good answer to some of them already, but would like to be sure. I appreciate your responses and send apologies for anywhere I'm way off base.

Background

At present, the Block datastructure includes an array of messages and parallel array of receipts. The messages are thus necessarily propagated and available whenever the block is. #94 indirects these through a CID to another structure.

fetching the blockchain involves starting with head block CIDs, fetching those blocks (with messages), and repeating with the parent CIDs of those blocks.
the whole chain is currently held in memory, which is causing nodes to OOM after the chain is a few weeks old some discussion. Separating messages from blocks so that only the block "headers" (without messages") are in RAM would significantly ease this (but isn't the only solution).
network/data-propagation in the spec describes propagation of new blocks and messages, assuming the messages were already broken out from blocks, but not exchange of existing ones. It doesn't describe how already-mined blocks/messages are fetched by a node fetching its initial chain.
Ethereum and other blockchains store messages and receipts in merkle tries, for some explanation and justification see https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

Questions

What is the motivation for referencing messages in a merkle-trie-like structure? I think the answer is to enable future light clients and other processes to determine properties of the blockchain and state without requiring a full chain state, i.e. like Ethereum. This is good but should be documented as such so that something like #250 can be judged against it.

Another motivation posited in https://github.com/filecoin-project/go-filecoin/issues/1324 is to keep block headers small since they are expected to be inserted into some on-chain messages. Is this unique to Filecoin? Is this definitely a thing?

Are there other similar unique-to-filecoin requirements that designers and implementers should be aware of?

Another possible motivation is to address the chain memory pressure problems noted above. If this were the sole motivation I would push back: the network protocol and node implementation need not be so tightly coupled. There are many ways to make better use of node memory and these improvements could be made independent of the network protocol, if inlining messages in blocks was simpler for the protocol.

So where do the actual messages go? Other blockchains identify the block header as one part of a complete block. Block headers may be exchanged for light clients without the accompanying block data (messages, receipts), but as I understand it, the full block is the unit of transfer for full nodes. #250 breaks the messages out of the "block" but doesn't put them anywhere.

Is there some implicit protocol by which messages are to be fetched (like blocks are fetched by bitswap)? If fetched individually, this seems like it will greatly add to the network overhead of fetching a full chain.

Is there instead a missing Block/BlockHeader distinction that should come with #94? I can imagine chain sync etc protocols continuing to receive a block's full messages and receipts alongside the header, leaving room for future light client protocols to fetch just the header?

Thoughts

In case it enters thinking while drafting spec items, I have a reasonable expectation that many of the concrete details of, e.g., the block structure will be abstracted from some of the bits of code that see them now. Especially as we implement a model for protocol upgrades, we'll likely attempt to hide heterogeneous block structures behind some interfaces in order to simplify and remove unnecessary coupling. I don't think the spec should worry too much about implementation efficiency, so long as there is clearly room for efficient implementations given the network protocol requirements (in many cases they are necessarily coupled).

Since the spec makes such concrete implementation recommendations, pre-empting a tech design process, I think significant proposals like #94 would benefit from more structured text, particularly including the goals and background of the proposal, as an implementation design doc would. #94 did not include enough information for me to know what the right questions to ask were.

anorth commented 5 years ago

Assigned @whyrusleeping who did a great job pushing me to ask here rather than in a chat.

cc @frrist @ZenGround0 @acruikshank

ZenGround0 commented 5 years ago

+1 on performance of implementation being a poor motivator of this work

There is a proposed explicit protocol for fetching messages of a blockchain: https://github.com/filecoin-project/specs/blob/master/sync.md. While your concern about fetching blocks then fetching messages is valid and will need to be addressed I think there is also potential to reduce syncing traffic by rejecting invalid block headers before fetching messages that this model introduces.

Passing block headers into slashing messages is NOT unique to filecoin AFAIK. The state machine needs to validate that a violator signed two things that fit block headers, and I think there are significant (potentially unworkable) disadvantages to just passing a signature in a message and requiring that the processing node fetch the block from the network for validation.

whyrusleeping commented 5 years ago

What is the motivation for referencing messages in a merkle-trie-like structure?

To make block headers as small as possible

So where do the actual messages go?

In a merkle tree that is linked to by the block. See [ every other blockchain ].

Is there instead a missing Block/BlockHeader distinction that should come with #94?

Maybe, we could rename our current 'Block' datastructure to 'BlockHeader'. I don't have strong opinions on this, and to me any data structure claiming to be the block will just be the linky bits at the top of the structure.

anorth commented 5 years ago

What is the motivation for referencing messages in a merkle-trie-like structure?

To make block headers as small as possible

They could be extracted to a flat array, then hashed, and still achieve that. I assume there is more to the picture, such as succinct existence proofs. It would be helpful for those motivations to be apparent to implementers so that we may make other decisions in line with the same goals, and meaningfully analyse and critique the spec. Especially in the current environment where the implementation is ahead of the spec in some areas, but we are working towards a common goal.

So where do the actual messages go?

In a merkle tree that is linked to by the block. See [ every other blockchain ].

I may have been imprecise. By go I meant to ask how the messages are serialised and communicated to other nodes. To take Ethereum as an example, types/block.go identifies distinct Header and Body structures, the body containing the transactions as a flat list. There's also a Block structure for purely internal use: a header, transaction list, and some cached values. The extblock and storageblock are distinct, for encoding to those channels. The spec and go-filecoin have no analogues at present.

The spec describes GetBlockHeaders and GetBlockBodies requests, which return essentially flattened arrays (of RLP'd extblock?). When I asked this question, there was no equivalent in the Filecoin spec; #261 has since added something to the interim blocksync protocol. It's not clear to me that this will answer the need when we use graphsync (later), without a Block structure comprising the header and messages/receipts.

The Ethereum merkle tree is not part of the exchange protocol except for defining the method by which the transactions hash is computed. It's never necessary serialised: NewBlock discards the Trie immediately after computing the root hash. (I was also imprecise with store messages and receipts in merkle tries in the OP; they're not persisted).

Elsewhere you noted that your IPLD experience leads you to identify "hash" with "pointer to an object in memory". This helps me understand what you are saying, but can lead to confusion when defining serialised data, especially in reference to [ every other blockchain ]. Walking IPLD trees directly would seem to require many more network messages than desirable.

Is there instead a missing Block/BlockHeader distinction that should come with #94?

Maybe, we could rename our current 'Block' datastructure to 'BlockHeader'. I don't have strong opinions on this, and to me any data structure claiming to be the block will just be the linky bits at the top of the structure.

We can choose terminology different from prior projects, but we should be very clear and precise about it if so. Since this distinction is new, the spec will be confusing until we do that.

anorth commented 5 years ago

A piece of context that has just clicked for me is an implicit anticipation of using graphsync for exchange. This isn't really clear in the spec at present, but answers some of the questions about how to obtain a full block (header + body) in a single round trip, without defining additional serialisation structures. That may be the implicit protocol by which messages are to be fetched I was seeking.

This would differ from most other blockchains, where the serialized structures are somewhat distinct from the logical ones (e.g. flat transaction list vs merkle tree).

whyrusleeping commented 5 years ago

By go I meant to ask how the messages are serialised and communicated to other nodes.

Oh, right. For initial synchronization, the block sync protocol includes the messages as a deduplicated array per tipset. For 'caught up' synchronization, the block propagation pubsub will need to change to include a set of message Cids (you don't want to send all of the messages themselves, as a full node that has been online for some time will likely already have most if not all of the messages already due to message gossip). It currently sends the whole blocks due to the messages being embedded into the block structure. I'll be sending a PR with this change shortly (as mentioned in the linked slack thread).

Another understated goal of all the data structures created here is that the entire filecoin blockchain will be viewable and traversable in ipld. This means that any IPFS node can fetch and exchange filecoin data, can view it, 'fully decentralized' chain explorers can be written using common interfaces, and anything in the ipld ecosystem can link to anything in filecoin.

Also, as mentioned elsewhere, the main reason that trees are used for message hashing is for merkle proofs. Given a block that they trust to be the latest head, a light client may request proof that their message made it into a block from some node on the network. (In the future, we will have better ways to be able to determine the latest head of the chain with minimal trust, right now this process requires trusting some node to tell them the right chain). Not planning properly for light clients is part of the reason ethereum's light client ecosystem is so scattered, there are at least three different light client protocols that I know of ( likely more ), including some that are only supported by parity, and some only by geth.

anorth commented 5 years ago

Thanks. I think that more or less answers my questions. I'll leave the issue open as a prompt to reflect these things in the spec to answer similar questions from others

[x] high level goal of IPLD traversibility of the chain, messages, state tree
[ ] anticipation of graphsync selector-based queries replacing custom exchange protocols
[ ] planning for light clients w/ merkle proofs
[x] block pubsub envelope message including message CIDs

For the structures that are intended to be IPLD-traversible, I think it would help to explicitly identify this, to distinguish them from those that are more implementation suggestions. Perhaps they could be expressed in a different language, closer to the IPLD schemas (which I think are WIP)?

Finally, for the pre-graphsync interim (if we are to implement it), is it worth adding a protocol for a node that has most but not all of the messages referenced by a block from pubsub to fetch the delta, rather than falling back to fetching the full tipset with blocksync?

pooja commented 5 years ago

We have a light clients issue that is tracking planning for light clients here: https://github.com/filecoin-project/specs/issues/68

We're closing this issue, but @anorth feel free to open if you feel your questions weren't answered/addressed!

filecoin-project / specs