search

filecoin-project / FIPs

The Filecoin Improvement Proposal repository
313 stars 165 forks source link

FIP-0086: Merklize The Tipset List #1004

Closed Stebalien closed 5 months ago

Stebalien commented 5 months ago

This PR turns the tipset list into a merkle-tree to shrink the size of the root "decision" message to something more friendly to zkSNARKs and bandwidth-limited blockchains. I've also re-arranged the signature format a bit to align the fields on 32-byte word boundaries to make it a little more EVM friendly.

Second, this PR reformats the ECTipset structs themselves to be more EVM friendly. Specifically:

  1. We sign the CID of the tipset key, not the tipset key itself, so we can omit the full tipset keys from bridge messages.
  2. We encode the ECTIpset by concatenating the four fields (epoch, commitments, tipset cid, powertable cid) instead of CBOR-encoding.
  3. We put the fixed-sized fields (epoch and commitments) first when encoding the ECTipset for signing, so we can avoid parsing. We likely don't care about the tipset CID and/or the power table CID in bridge smart contracts anyways.

See the rational for details.

Stebalien commented 5 months ago

I would also somewhat prefer the FIP document itself stuck to pseudocode. But since merkle trees are a fairly widely understood concept, how about pulling this code out into a supporting file under resources and pointing to it there?

Can do. Although it's surprisingly easy to mess up the implementation (or design...).

Regarding decision about ECTipset, I think the conclusions stated in https://github.com/filecoin-project/go-f3/issues/166 are strong and we should probably go with that.

This change so-far handles point's 1 & 2 (small finality certificate, no need to parse CBOR in a snark) but it doesn't handle point 3. IMO, that was the weakest point... but it's also not particularly hard to address it (it just adds a small bit of complexity).

jennijuju commented 5 months ago

editor review ✅ .

@Kubuxu can you confirm this https://github.com/filecoin-project/FIPs/pull/1004#discussion_r1596889874v and see if the flag is resolved? will block merging the PR until then

Kubuxu commented 5 months ago

@Kubuxu can you confirm this https://github.com/filecoin-project/FIPs/pull/1004#discussion_r1596889874v and see if the flag is resolved? will block merging the PR until then

It should not block, as it is only a note in the FIP.

Kubuxu commented 5 months ago

@jennijuju we will discuss it but it should not block merge of this PR