Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

ECTipset Format Redux #166

Closed
Tracked by #5
Stebalien opened this issue Apr 17, 2024 · 0 comments · Fixed by #216
Closed
Tracked by #5

ECTipset Format Redux #166

Stebalien opened this issue Apr 17, 2024 · 0 comments · Fixed by #216
Assignees
@Stebalien
Milestone
Milestone 0: F3 A...

Comments

@Stebalien
Copy link
Member

@masih, @Kubuxu, and I were discussing the eventual upgrade path to cross-chain bridging and ran into an issue. Even with a 100 tipset limit:

  1. We can still easily reach 26KiB+ of data in a single finality certificate.
  2. This data is CBOR, so it's hard to make it a private input to a SNARK (requires parsing CBOR in a snark). I think we're going to be very unhappy if we have to start proving facts about CBOR-encoded data inside a snark.
  3. Even without snarks, parsing CBOR is non-trivial and not well supported on most chains.

We initially claimed that this was fine because we don't yet support cross-chain bridging but... we still want an upgrade path towards cross-chain bridging (hence the commitment tree). I hate to re-open this can of worms, but I think we need to commit to a sequence of commitment hashes instead of CBOR values. That is:

type Value = [32]byte // root hash of a merkle tree
type ECChain = []Value // concatenated hashes, we could also make a tree here, but I don't think that's necessary.

That way, any future SNARKs can:

  1. Given a snark friendly commitment to the power-table from the last instance.
  2. Validate the signature over the root commitment (32 bytes).
  3. Validate a simple merkle-proof down to facts we're trying to prove.
  4. Use those facts (e.g., in a new SNARK).

The one objection we envision is observability. But we can handle that by treating this commitment scheme as a part of the signature scheme (suggested by @Kubuxu). Basically:

  1. The GossiPBFT protocols still transmit full tipset information.
  2. The signature also includes the merkle-proof proving that the signed commitment commits to the transmitted tipste.
  3. The v1 finality certificate format can also include the tipsets/power table directly. It's just that the signature will only cover the root hash.

Importantly, this would let us create small finality certificates that don't require parsing CBOR to understand.
@Kubuxu Kubuxu mentioned this issue Apr 22, 2024
Closed
@ranchalp ranchalp mentioned this issue Apr 24, 2024
Closed
@Stebalien Stebalien mentioned this issue Apr 30, 2024
Closed
@anorth anorth mentioned this issue May 9, 2024
Merged
Stebalien added a commit that referenced this issue May 14, 2024
@Stebalien
EVM-friendly TipSet and ECChain formats
a15375b 
This patch implements the changes described in
filecoin-project/FIPs#1004.

Unfortunately, go-f3 now needs to be aware of the internal structure of
`TipSet` objects as it sends them over the wire in one format, but signs
another. This effectively reverts #149.

Specific changes:

1. On the wire (and in finality certificates), `TipSet` objects are now
   directly cbor-marshaled within the payload instead of first being
   marshaled to byte strings.
2. Instead of directly covering the entire tipset list with the payload
   signature:
  1. `TipSet` objects are "marshaled for signing" per the FIP change
      proposed above.
  2. These marshaled tipset objects are stuffed into a merkle tree.
  3. The merkle tree root is signed (along with the payload's other
     fields), again according the proposed changes.

fixes #166
@Stebalien Stebalien mentioned this issue May 14, 2024
Merged
Stebalien added a commit that referenced this issue May 14, 2024
@Stebalien
EVM-friendly TipSet and ECChain formats
6d72d02 
This patch implements the changes described in
filecoin-project/FIPs#1004.

Unfortunately, go-f3 now needs to be aware of the internal structure of
`TipSet` objects as it sends them over the wire in one format, but signs
another. This effectively reverts #149.

Specific changes:

1. On the wire (and in finality certificates), `TipSet` objects are now
   directly cbor-marshaled within the payload instead of first being
   marshaled to byte strings.
2. Instead of directly covering the entire tipset list with the payload
   signature:
  1. `TipSet` objects are "marshaled for signing" per the FIP change
      proposed above.
  2. These marshaled tipset objects are stuffed into a merkle tree.
  3. The merkle tree root is signed (along with the payload's other
     fields), again according the proposed changes.

fixes #166
Stebalien added a commit that referenced this issue May 14, 2024
@Stebalien
EVM-friendly TipSet and ECChain formats
efdd9e8 
This patch implements the changes described in
filecoin-project/FIPs#1004.

Unfortunately, go-f3 now needs to be aware of the internal structure of
`TipSet` objects as it sends them over the wire in one format, but signs
another. This effectively reverts #149.

Specific changes:

1. On the wire (and in finality certificates), `TipSet` objects are now
   directly cbor-marshaled within the payload instead of first being
   marshaled to byte strings.
2. Instead of directly covering the entire tipset list with the payload
   signature:
  1. `TipSet` objects are "marshaled for signing" per the FIP change
      proposed above.
  2. These marshaled tipset objects are stuffed into a merkle tree.
  3. The merkle tree root is signed (along with the payload's other
     fields), again according the proposed changes.

fixes #166
Stebalien added a commit that referenced this issue May 14, 2024
@Stebalien
EVM-friendly TipSet and ECChain formats
a12ab48 
This patch implements the changes described in
filecoin-project/FIPs#1004.

Unfortunately, go-f3 now needs to be aware of the internal structure of
`TipSet` objects as it sends them over the wire in one format, but signs
another. This effectively reverts #149.

Specific changes:

1. On the wire (and in finality certificates), `TipSet` objects are now
   directly cbor-marshaled within the payload instead of first being
   marshaled to byte strings.
2. Instead of directly covering the entire tipset list with the payload
   signature:
  1. `TipSet` objects are "marshaled for signing" per the FIP change
      proposed above.
  2. These marshaled tipset objects are stuffed into a merkle tree.
  3. The merkle tree root is signed (along with the payload's other
     fields), again according the proposed changes.

fixes #166
Stebalien added a commit that referenced this issue May 14, 2024
@Stebalien
EVM-friendly TipSet and ECChain formats
d5c87aa 
This patch implements the changes described in
filecoin-project/FIPs#1004.

Unfortunately, go-f3 now needs to be aware of the internal structure of
`TipSet` objects as it sends them over the wire in one format, but signs
another. This effectively reverts #149.

Specific changes:

1. On the wire (and in finality certificates), `TipSet` objects are now
   directly cbor-marshaled within the payload instead of first being
   marshaled to byte strings.
2. Instead of directly covering the entire tipset list with the payload
   signature:
  1. `TipSet` objects are "marshaled for signing" per the FIP change
      proposed above.
  2. These marshaled tipset objects are stuffed into a merkle tree.
  3. The merkle tree root is signed (along with the payload's other
     fields), again according the proposed changes.

fixes #166
@jennijuju jennijuju added this to F3 May 15, 2024
@Kubuxu Kubuxu mentioned this issue May 15, 2024
Closed
@Kubuxu Kubuxu moved this to In progress in F3 May 16, 2024
@Stebalien Stebalien moved this from In progress to In review in F3 May 17, 2024
github-merge-queue bot pushed a commit that referenced this issue May 17, 2024
@Stebalien
EVM-friendly TipSet and ECChain formats (#216)
837ffde 
* EVM-friendly TipSet and ECChain formats

This patch implements the changes described in
filecoin-project/FIPs#1004.

Unfortunately, go-f3 now needs to be aware of the internal structure of
`TipSet` objects as it sends them over the wire in one format, but signs
another. This effectively reverts #149.

Specific changes:

1. On the wire (and in finality certificates), `TipSet` objects are now
   directly cbor-marshaled within the payload instead of first being
   marshaled to byte strings.
2. Instead of directly covering the entire tipset list with the payload
   signature:
  1. `TipSet` objects are "marshaled for signing" per the FIP change
      proposed above.
  2. These marshaled tipset objects are stuffed into a merkle tree.
  3. The merkle tree root is signed (along with the payload's other
     fields), again according the proposed changes.

fixes #166

* test marshal payload for signing

* slightly optimize hashing

* add a worst-case benchmark for marshalling payloads

* address feedback

* Fake marshaling for testing

* pre-allocate when marshaling tipsets

* combine signer/verifier and MarshalPayloadForSignature

Into a single Signatures interface.

* tipset marshal for signing test

* Test bad merkle-tree paths
@github-project-automation github-project-automation bot moved this from In review to Done in F3 May 17, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Stebalien Stebalien

Labels
None yet
Projects
F3
Status: Done
Milestone
Milestone 0: F3 Alpha Code Freeze
Development

Successfully merging a pull request may close this issue.

EVM-friendly TipSet and ECChain formats filecoin-project/go-f3
2 participants
@Stebalien @Kubuxu