Chain History Section clarification

[KonradStaniec]

This not an issue per se, but rather a thread to resolve some questions regarding chain history section.

1. Current spec states that When a portal client requests a certain header, the response includes two accumulator proofs, which suggest that at any point portal client can request one header, receive one header in response along with two accumulator proofs, and be sure that received header is part of canonical chain. Unless I am missing something, it would be good to describe in spec that in reality client needs to randomly sample log(n) random blocks from peer to correctly validate that headers are in fact part of canonical chain. We can probably also re-use some of the ideas from https://eprint.iacr.org/2019/226.pdf paper.

2 It would be nice to add some clarifications what changes will be necessary to clients software and protocol to make this feature available and secure:

• should new field be added to block header to make accumulator part of consensus. This is approach used in fly client paper for research purposes but it is probably no-go due to the amount of breakage it would do.
• maybe we can adapt other field from block header for this purposes, like parentHash. This is the way Zcash went, when adapting to fly client protocol - https://zips.z.cash/zip-0221#abstract. Although they adapted other field than parentHash due to troubles with chain reorganisations.
• Fly client paper mention something called velvet forks, when upgraded and not upgraded clients work in parallel.

Maybe there is some other way to do this, either way it would be great to include in in spec.

I just wanted kick start discussion about those things(or get some clarifications to the spec if those problems are already solved and all is fine) , as from usability point of view the state network is probably most important, as it enables user to check their balances and send transactions, but from security point of view chain history is probably more important one as all state inclusion proofs are validated against header which portal client thinks is the part of canonical chain.

[pipermerriam]

https://notes.ethereum.org/KaMqlqxiQLCWyDoXCUCC4Q

[KonradStaniec]

Thanks @pipermerriam, great write up it resolves some of my questions. Some follow up ones:

1. What is exactly proof (as in classic merkle tree it is a path from root to leaf) in this scheme and what would be it size for typical main-net chain or we are yet to determine it ?

2. I am wondering about https://notes.ethereum.org/KaMqlqxiQLCWyDoXCUCC4Q#Build-it-from-scratch, is it really that non-viable ? As for storage, from what I understand the client would not need to store all headers just update its accumulator. As for computation, as I understand we are talking about proof of work validation, we probably would not need to validate every header but every n-th header as it is currently done in fast sync. The one thing that remains is high bandwidth usage, but to be honest this mode would pretty nice for anyone who would like to send transaction from her own laptop with cable connection, without downloading all data.

3. Do we intend to try to to push for hard fork, to include accumulator hash in header or maybe adapt some other field (maybe extraData would be good candidate as for now only validation on it is that it is smaller or equal than 32 bytes, and maybe we could extend it) ?

4. In the initial design, what was intended transport for chain history network ? If it was discovery5.1 over udp, we will probably need to use uTP to stream some larger responses like for example block bodies.

[pipermerriam]

1. What is exactly proof (as in classic merkle tree it is a path from root to leaf) in this scheme and what would be it size for typical main-net chain or we are yet to determine it ?

The accumulator is the composition of two accumulators.

• The "epoch" accumulators store things like the actual header hashes and total difficulties.
• The "master" accumulator is what is directly tracked by the protocol and only contains the roots of the epoch accumulators.

A proof would be two merkle proofs. One for the "master" accumulator leading to leaf node that contains the root of the appropriate epoch accumulator. The second for the "epoch" accumulator leading to the leaf that contains the actual block hash and total difficulty at that height.

[pipermerriam]

2. I am wondering about https://notes.ethereum.org/KaMqlqxiQLCWyDoXCUCC4Q#Build-it-from-scratch, is it really that non-viable ? As for storage, from what I understand the client would not need to store all headers just update its accumulator. As for computation, as I understand we are talking about proof of work validation, we probably would not need to validate every header but every n-th header as it is currently done in fast sync. The one thing that remains is high bandwidth usage, but to be honest this mode would pretty nice for anyone who would like to send transaction from her own laptop with cable connection, without downloading all data.

This really depends on what your tolerance is for making the user "wait". If you want to build it from scratch you will have to acquire al ~12M headers. In the DevP2P model you can request them in batches of 384. In our model these would be individual requests. So a baseline for the wait time can be estimated as either 12_000_000 * average_round_trip_time. If you assume 50ms for round trips, then this operation will take 7 days if you do it synchronously. Obviously you can make some gains on that with concurrency.

What we're really talking about here is the fuzzy realm of subjectivity. There's no right or wrong way for a client to implement tracking of the header chain, only trade-offs. Some clients may want absolute trustless guarantees, and so they may implement full verification of the header chain from genesis.... Some clients may want the absolute best UX out there, and may just use simple heuristics and jump directly to the front of the chain and do basic validation on a copy of someone else's accumulator without every fully verifying it. Neither of these are objectively correct or incorrect. They are just choices that client teams must make with respect to the UX they present to their users.

The reason that I label this as not being viable is that it imposes larger computation and bandwidth requirements on the client than I'm interested in accepting. Other client implementations will have different priorities.

[pipermerriam]

3. Do we intend to try to to push for hard fork, to include accumulator hash in header or maybe adapt some other field (maybe extraData would be good candidate as for now only validation on it is that it is smaller or equal than 32 bytes, and maybe we could extend it) ?

Yes, but it isn't a deal breaker for us one way or the other.

After "The Merge" our network has to transition onto the beacon chain as source of truth, at which point we will have our accumulator because it's already part of the beacon chain protocol.

The only benefit is to get it in before the merge so that we have a thing enshrined in the protocol that gives us the accumulator data from before the merge, and even here this is of limited use because the idea of reaching deep into history gets less and less interesting/necessary when you can no longer sync from genesis as a "trustless" way to find the tip of the chain.

[pipermerriam]

4. In the initial design, what was intended transport for chain history network ? If it was discovery5.1 over udp, we will probably need to use uTP to stream some larger responses like for example block bodies.

I believe the block header is the only data that reliably fits into a UDP packet so yes, uTP would be the intended transport for most or all chain history data. My suggestion for the packet design would be:

• Packet may be one of the following.
  • the full binary payload if it fits
  • a connection_id for a uTP stream over which the data will be sent/received.

This allows the client to just send the data if it fits, or to fall back to uTP when it does not.

[KonradStaniec]

thanks for thorough response!

I think one remaining question I have is what do you think would be best serialization scheme for domain objects in chain history network. What I mean is , that when we ask remote peer for block header by hash, I assume we ask for hash of RLP encoded header (so that portal network and main network have same hashes for same header) so in response I imagine we receive something along the lines ssz_container(header: Rlp_encoded_bytes). So receiver of such message can easily validate that received header bytes have the same hash as requested. (instead of having deserialize whole thing from ssz, and then serialize it again to rlp to check proper hash). Do I understand it correctly ?

[pipermerriam]

I think we want to go with whatever is simplest.

• we should not re-encode things as SSZ. If we are embedding a header it would be as you said: Container[header_rlp: rlp_encoded_header_bytes]
• we should not add additional RLP encoding because we don't like RLP:
  • if we package an accumulator proof with the header then we would do: Container[proof: ProofSedes, header_rlp: ...]

So the rough guideline here is keep RLP encoding at the individual object level for things like Header, BlockBody, Receipt and use SSZ at the envelope/container level for when we need to package additional information along with the payload.

[KonradStaniec]

Another thing Is mechanics of distributing the history data, how peers would know which peers hold what data.

Block headers are the simplest of the three (headers, transactions, receipts) I imagine, as every peer in the network will most likely want to have most recent header. Maybe each peer could broadcast message similar to NewBlockHashes after downloading new header, validating pow, and proof ? I see this message structure as Contrainer(block_number, block_hash, chain_id). (I included chain_id as portal nodes does not go through hadnshake like devp2p nodes, so it would be nice to know which chain remote peer is tracking). Each node would keep such header for some time (lets say 128 or 256 blocks) With such structure, other nodes could request latest known header(and its accumulator) from remote node by hash.

For receipts/transactions, I am not sure what is best solution as https://etherscan.io/txs currrently show that there is over 1 billion transactions. We could probably re use the same mechanics as with state network i.e each node have a radius and store transactions within own radius, but we would need a lot of portal nodes to store them all.

Also in https://ethresear.ch/t/an-updated-roadmap-for-stateless-ethereum/9046, you mentioned that portal nodes should participate in Block Gossip 1 without the other implicit requirements imposed by the DevP2P ETH protocol, did you mean standard rlpx connections to other nodes to be able to process NewBlock and NewBlockHashes messages ?

[pipermerriam]

Important to segregate block gossip from historical data retrieval.

Gossip

For gossip, I believe we just need to implement a simple gossip protocol over DiscV5. This should probably be a separate sub-protocol but might be appropriate to piggy-back it onto the chain-history network. I have ideas for how this would be designed, but it's probably worth someone taking an independent look at existing models for DHT gossip and seeing what they come up with.

The simple design in my head would be a new/separate discv5 subprotocol with its own PING/PONG/FIND/FOUND messages to allow nodes to self organize themselves using the standard Kademlia routing table. Then a new message pair 'NEWBLOCKHEADER/GETNEWBLOCKHEADER` that is used to advertise new blocks being available and to allow retrieval.

Canonical Transaction Index vs Transactions

Transactions and Receipts should probably be stored "bundled" under their block hash. The reason for bundling them is that to validate transactions/receipts you need to reconstruct the trie referenced by Header.transactions_root or Header.receipts_root. This can be done by either having the full set of transactions/receipts or by providing a merkle proof and the individual transaction/receipt. If the network stores transactions/receipts individually, then we end up also needing nodes to store this merkle proof alongside the transaction/receipt so that they can provide it with any response.

A more efficient way to do this is to have nodes store a whole block's worth of transactions/receipts. This allows them to return all of the transactions/receipts for a block in one response as opposed to having to collect all of them from disparate places around the network. The JSON-RPC eth_getBlockByHash contains information about all of the transactions, so serving this for a recent block with 300+ transactions on demand from the portal network would require 300+ network round trips if we store everything separately.

So the above is the justification for how we store transactions and receipts.... what about the canonical transaction index.

I'll suggest that the canonical transaction index should again be its own independent sub-protocol from chain history. The canonical tx index data is way less important than the history data. If they use the same network, then we treat them as if they are of the same level of importance with respect to things like evicting data from the network when it is over-capacity.

[KonradStaniec]

The simple design in my head would be a new/separate discv5 subprotocol with its own PING/PONG/FIND/FOUND messages to allow nodes to self organize themselves using the standard Kademlia routing table. Then a new message pair 'NEWBLOCKHEADER/GETNEWBLOCKHEADER` that is used to advertise new blocks being available and to allow retrieval.

I was also thinking about something along those lines. Imo it makes sense to group header gossip and retrieval into one network (even separating headers from other block data as body with tx and receipts). Then users wanting only to send transaction or interact with smart contract (who I think will be largest consumers of portal client), would need to only participate in two networks - state and headers.

[pipermerriam]

would need to only participate in two networks - state and headers.

This is true in the case where header history and new block gossip are kept in separate networks. The client could use the header history chain to acquire an up-to-date picture of the head of the chain, afterwards they would be able to actually leave the history network and only stay in state+header_gossip+tx_gossip in order to be able to follow the chain and construct and send transactions.

It is unclear to me whether this is a good thing or a bad thing. It is a good thing with respect to compositional functionality and allowing clients to only consume (and conversely contribute) to the parts of the network they use. It might be a bad thing because it might mean that nodes choose to drop out of the header history network once they have synced, not actually contributing back to the overall health of the network and causing the history network to operate at reduced capacity...

[KonradStaniec]

wouldn't keeping header gossip and header retrieval in one network improve the speed of joining up to the network ?

When those are separate then header history network needs to rely on content finding i.e it needs some protocol to effectively say find me best block header in chain history network for some chain (mainnet/testnet/etc).

When those two would be joined, peer can receive gossiped headers from remote peers and know which peer holds (or at least had contact with) which headers, and maybe retrieve historic data without any lookup.

In my view header history and header gossip complete each other nicely to the point that I am not sure if keeping them separate is advantageous or not.

Nevertheless simple design you mentioned earlier sounds goods as something to start building on and improve later if necessary.