fix overwrite bug by evan-forbes · Pull Request #251 · celestiaorg/celestia-core

evan-forbes · 2021-03-25T19:39:42Z

Description

This PR fixes the overwrite bug described in #250. It also changes appendToShares so that it stops splitting message shares that are equal to MsgShareSize

Closes: #250

evan-forbes · 2021-03-25T19:46:24Z

types/shares.go

 // Used for messages.
 func appendToShares(shares []NamespacedShare, nid namespace.ID, rawData []byte) []NamespacedShare {
-	if len(rawData) < MsgShareSize {
+	if len(rawData) <= MsgShareSize {


I'm fairly certain now that this change is needed.

But why would it need padding in the case len(rawData) == MsgShareSize ?

Can we also have a test that explains that change?

I was wrong as this is change actually doesn't alter any of the end results, so it's not needed. If len(rawData) == MsgShareSize, then split will only return a single share. I do think the change makes sense from a groking perspective though. Why push a share through split if it's not actually split? I'm happy to change it back, if anyone thinks otherwise.

Nah, you are right! No need to change it back.

evan-forbes · 2021-03-25T19:51:18Z

types/shares_test.go

+func Test_appendToSharesOverwrite(t *testing.T) {
+	var shares NamespacedShares
+
+	// generate some arbitrary first share that must be split
+	newShare := generateRandomNamespacedShares(1, MsgShareSize+1)[0]
+
+	// make a copy of the portion of the share to check if it's overwritten later
+	extraCopy := make([]byte, MsgShareSize)
+	copy(extraCopy, newShare.Share[:MsgShareSize])
+
+	// use appendToShares to add our new share
+	appendToShares(shares, newShare.ID, newShare.Share)
+
+	// check if the original share data has been overwritten.
+	assert.Equal(t, extraCopy, []byte(newShare.Share[:MsgShareSize]))
+}


this test fails without the added copy in split

Are you sure it is the copy or simply the fact that previously the nid got prefixed? rawShare := []byte(append(nid, rawData[:shareSizeOrLen]...))? What happens if this is changed to rawShare := rawData[:shareSizeOrLen] instead?

ahh I see, it works!

liamsi · 2021-03-25T19:58:02Z

types/shares.go

 	rawData = rawData[MsgShareSize:]
 	for len(rawData) > 0 {
 		shareSizeOrLen := min(MsgShareSize, len(rawData))
-		rawShare := []byte(append(nid, rawData[:shareSizeOrLen]...))


Trying to understand exactly what is going on here: this append(nid, rawData[:shareSizeOrLen]... is unnecessary as the share gets namespaced below anyways (share := NamespacedShare{paddedShare, nid})?

yep! your other comment is correct, we don't need the copy, only to not use the nid

types/shares_test.go

types/shares.go

Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com>

liamsi

❤️

liamsi

Rejecting this change to prevent merging this in. While the code in isolation looks good, there seems to be some confusion on how the shares actually look like (should they be raw bytes including the nid or should they use the struct NamespacedShare{paddedShare, nid} instead?).

Let's discuss this before we decide on if we want to merge this or not.

…ares

evan-forbes · 2021-03-26T15:30:56Z

The fix has been applied so that it remains consistent with how shares are split and stored. That is, the namespace is stored both in the NamespacedShare fields. Once in NamespaceShare.ID as is, and again as the first NamespaceSize bytes of NamespaceShare.Share. This makes it easy when pushing to the nmt, as we perform the same logic with each push. We simply push append(NamespaceShare.ID, NamespaceShare.Share)

liamsi · 2021-03-26T15:47:02Z

types/shares.go

-		rawShare := []byte(append(nid, rawData[:shareSizeOrLen]...))
+		rawShare := make([]byte, NamespaceSize)
+		copy(rawShare, nid)
+		rawShare = append(rawShare, rawData[:shareSizeOrLen]...)


So this is essentially the same logic (or rather the intended one) as before now but we use copy to make sure that the raw share contains the nid instead of using append 👍🏼

BTW, I guess the append version of this should have looked like this then:

rawShare := append(append( make([]byte, NamespaceSize), nid...), rawData[:shareSizeOrLen]...)

liamsi

👍🏼

liamsi · 2021-03-26T17:23:00Z

go.mod

 	github.com/lazyledger/lazyledger-core/p2p/ipld/plugin v0.0.0-20210219190522-0eccfb24e2aa
 	github.com/lazyledger/nmt v0.2.0
-	github.com/lazyledger/rsmt2d v0.0.0-20201215203123-e5ec7910ddd4
+	github.com/lazyledger/rsmt2d v0.0.0-20210326165230-b6417926360b


Orthogonal to this PR but we should start tagging releases for rsmt2d. I just tagged a pre-release here: https://github.com/lazyledger/rsmt2d/releases/tag/v0.1.0

* fix overwrite bug and stop splitting shares of size MsgShareSize * remove ineffectual code * review feedback: better docs Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * remove uneeded copy and only fix the source of the bug Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug while also being consistent with using NamespacedShares * update to the latest rsmt2d for the nmt wrapper Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com>

) * Basic DA functionality (#83) * move Messages field to the end of Block.Data * Add some constants for share computation and the NMT: - also a bunch of todos regarding shares computation * First (compiling) stab on creating shares * Test with Evidence and fix bug discovered by test * remove resolved todos * introduce split method * Introduce LenDelimitedMarshaler interface and some reformatting * Introduce TxLenDelimitedMarshaler * add some test cases * fix some comments * fix some comments & linter * Add reserved namespaces to params * Move ll-specific consts into a separate file (consts.go) * Add MarshalDelimited to HexBytes * Add tail-padding shares * Add ComputeShares method on Data to compute all shares * Fix compute the next square num and not the next power of two * lints * Unexport MakeShares function: - it's likely to change and it doesn't have to be part of the public API * lints 2 * First stab on computing row/column roots * fix rebase glitches: - move DA related constants out of params.go * refactor MakeBlock to take in interm. state roots and messages * refactor state.MakeBlock too * Add todos LenDelimitedMarshaler and extract appendShares logic * Simplify shares computation: remove LenDelimitedMarshaler abstraction * actually use DA header to compute the DataRoot everywhere (will lead to failing tests for sure) * WIP: Update block related core data structures in protobuf too * WIP: fix zero shares edge-case and get rid of Block.Data.hash (use dataAvailabilityHeader.Hash() instead) * Fixed tests, only 3 failing tests to go: TestReapMaxBytesMaxGas, TestTxFilter, TestMempoolFilters * Fix TestTxFilter: - the size of the wrapping Data{} proto message increased a few bytes * Fix Message proto and `DataFromProto` * Fix last 2 remaining tests related to the increased block/block.Data size * Use infectious lib instead of leopard * proto-lint: snake_case * some lints and minor changes * linter * panic if pushing to tree fails, extend Data.ToProto() * revert renaming in comment * add todo about refactoring as soon as the rsmt2d allows the user to choose the merkle tree * clean up some unused test helper functions * linter * still debugging the exact right number of bytes for max data... * Implement spec-compliant share splitting (#246) * Export block data compute shares. * Refactor to use ShareSize constant directly. * Change message splitting to prefix namespace ID. * Implement chunking for contiguous. * Add termination condition. * Rename append contiguous to split contiguous. * Update test for small tx. * Add test for two contiguous. * Make tx and msg adjusted share sizes exported constants. * Panic on hopefully-unreachable condition instead of silently skipping. * Update hardcoded response for block format. Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug (#251) * fix overwrite bug and stop splitting shares of size MsgShareSize * remove ineffectual code * review feedback: better docs Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * remove uneeded copy and only fix the source of the bug Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug while also being consistent with using NamespacedShares * update to the latest rsmt2d for the nmt wrapper Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * Spec compliant merge shares (#261) * start spec compliant share merging * refactor and finish unit testing * whoops * linter gods * fix initial changes and use constants * use constant * more polish * docs fix* review feedback: docs and out of range panic protection * review feedback: add panic protection from empty input * use constant instead of recalculating `ShareSize`* don't redeclare existing var* be more explicit with returned nil* use constant instead of recalculating `ShareSize`* review feedback: use consistent capitalization * stop accepting reserved namespaces as normal messages * use a descriptive var name for message length * linter and comparison fix * reorg tests, add test for parse delimiter, DataFromBlock and fix evidence marshal bug * catch error for linter * update test MakeShares to include length delimiters for the SHARE_RESERVED_BYTE * minor iteration change * refactor share splitting to fix bug * fix all bugs with third and final refactor * fix conflict * revert unnecessary changes * review feedback: better docs* reivew feedback: add comment for safeLen * review feedback: remove unnecessay comments * review feedback: split up share merging and splitting into their own files * review feedback: more descriptive var names * fix accidental change * add some constant docs * spelling error Co-authored-by: Hlib Kanunnikov <hlibwondertab@gmail.com> Co-authored-by: John Adler <adlerjohn@users.noreply.github.com> Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * refactor to better accomodate real world use cases (celestia node) Co-authored-by: rene <41963722+renaynay@users.noreply.github.com> * thank you linter Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> Co-authored-by: John Adler <adlerjohn@users.noreply.github.com> Co-authored-by: Hlib Kanunnikov <hlibwondertab@gmail.com> Co-authored-by: rene <41963722+renaynay@users.noreply.github.com>

* fix overwrite bug and stop splitting shares of size MsgShareSize * remove ineffectual code * review feedback: better docs Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * remove uneeded copy and only fix the source of the bug Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug while also being consistent with using NamespacedShares * update to the latest rsmt2d for the nmt wrapper Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com>

) * Basic DA functionality (#83) * move Messages field to the end of Block.Data * Add some constants for share computation and the NMT: - also a bunch of todos regarding shares computation * First (compiling) stab on creating shares * Test with Evidence and fix bug discovered by test * remove resolved todos * introduce split method * Introduce LenDelimitedMarshaler interface and some reformatting * Introduce TxLenDelimitedMarshaler * add some test cases * fix some comments * fix some comments & linter * Add reserved namespaces to params * Move ll-specific consts into a separate file (consts.go) * Add MarshalDelimited to HexBytes * Add tail-padding shares * Add ComputeShares method on Data to compute all shares * Fix compute the next square num and not the next power of two * lints * Unexport MakeShares function: - it's likely to change and it doesn't have to be part of the public API * lints 2 * First stab on computing row/column roots * fix rebase glitches: - move DA related constants out of params.go * refactor MakeBlock to take in interm. state roots and messages * refactor state.MakeBlock too * Add todos LenDelimitedMarshaler and extract appendShares logic * Simplify shares computation: remove LenDelimitedMarshaler abstraction * actually use DA header to compute the DataRoot everywhere (will lead to failing tests for sure) * WIP: Update block related core data structures in protobuf too * WIP: fix zero shares edge-case and get rid of Block.Data.hash (use dataAvailabilityHeader.Hash() instead) * Fixed tests, only 3 failing tests to go: TestReapMaxBytesMaxGas, TestTxFilter, TestMempoolFilters * Fix TestTxFilter: - the size of the wrapping Data{} proto message increased a few bytes * Fix Message proto and `DataFromProto` * Fix last 2 remaining tests related to the increased block/block.Data size * Use infectious lib instead of leopard * proto-lint: snake_case * some lints and minor changes * linter * panic if pushing to tree fails, extend Data.ToProto() * revert renaming in comment * add todo about refactoring as soon as the rsmt2d allows the user to choose the merkle tree * clean up some unused test helper functions * linter * still debugging the exact right number of bytes for max data... * Implement spec-compliant share splitting (#246) * Export block data compute shares. * Refactor to use ShareSize constant directly. * Change message splitting to prefix namespace ID. * Implement chunking for contiguous. * Add termination condition. * Rename append contiguous to split contiguous. * Update test for small tx. * Add test for two contiguous. * Make tx and msg adjusted share sizes exported constants. * Panic on hopefully-unreachable condition instead of silently skipping. * Update hardcoded response for block format. Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug (#251) * fix overwrite bug and stop splitting shares of size MsgShareSize * remove ineffectual code * review feedback: better docs Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * remove uneeded copy and only fix the source of the bug Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug while also being consistent with using NamespacedShares * update to the latest rsmt2d for the nmt wrapper Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * Spec compliant merge shares (#261) * start spec compliant share merging * refactor and finish unit testing * whoops * linter gods * fix initial changes and use constants * use constant * more polish * docs fix* review feedback: docs and out of range panic protection * review feedback: add panic protection from empty input * use constant instead of recalculating `ShareSize`* don't redeclare existing var* be more explicit with returned nil* use constant instead of recalculating `ShareSize`* review feedback: use consistent capitalization * stop accepting reserved namespaces as normal messages * use a descriptive var name for message length * linter and comparison fix * reorg tests, add test for parse delimiter, DataFromBlock and fix evidence marshal bug * catch error for linter * update test MakeShares to include length delimiters for the SHARE_RESERVED_BYTE * minor iteration change * refactor share splitting to fix bug * fix all bugs with third and final refactor * fix conflict * revert unnecessary changes * review feedback: better docs* reivew feedback: add comment for safeLen * review feedback: remove unnecessay comments * review feedback: split up share merging and splitting into their own files * review feedback: more descriptive var names * fix accidental change * add some constant docs * spelling error Co-authored-by: Hlib Kanunnikov <hlibwondertab@gmail.com> Co-authored-by: John Adler <adlerjohn@users.noreply.github.com> Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * refactor to better accomodate real world use cases (celestia node) Co-authored-by: rene <41963722+renaynay@users.noreply.github.com> * thank you linter Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> Co-authored-by: John Adler <adlerjohn@users.noreply.github.com> Co-authored-by: Hlib Kanunnikov <hlibwondertab@gmail.com> Co-authored-by: rene <41963722+renaynay@users.noreply.github.com>

* fix overwrite bug and stop splitting shares of size MsgShareSize * remove ineffectual code * review feedback: better docs Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * remove uneeded copy and only fix the source of the bug Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com> * fix overwrite bug while also being consistent with using NamespacedShares * update to the latest rsmt2d for the nmt wrapper Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com>

* Rename Tendermint to CometBFT in /docs (#197) * docs/rename: simple github.com links renaming * docs/rename: old links to spec repo replaced * docs/rename: Go doc links renamed, currently broken * docs/rename: fixing broken links, proper branches * docs/rename: docs.tendermint.com -> docs.cometbft.com * docs/rename: fixing front matter in .md files * docs/rename: renaming in what is tendermint page * Tendermint in a Nutshell image removed * docs/rename: cleaning, renaming docs introduction * docs/rename: renaming in docs/app-dev/ dir * docs/rename: links to main branch in docs/networks * docs/rename: renaming in docs/tools/ dir * docs/rename: renaming in docs/tutorials dir * docs/rename: moving images to docs/imgs/ dir * docs/rename: renaming in docs/tendermint-core/ dir * docs/rename: docs/tendermint-core/ -> docs/core/ * docs/rename: renaming in docs/qa/ sub path * docs/rename: renaming in .vuepress dir, logo removed * docs/rename: renaming in READMEs * docs/rename: removing Tendermint images and content * docs/rename: removing references to removed diagram * docs/rename: renaming in READMEs for RFCs and ADRs * rename: links to docs/tendermint-core -> docs/core * docs/rename: removing unused images from docs/imgs/ * docs/rename: cleaning of docs/imgs/, ADR images moved * Apply suggestions from code review Co-authored-by: Thane Thomson <connect@thanethomson.com> * Apply suggestions from code review Co-authored-by: Thane Thomson <connect@thanethomson.com> * docs/rename: removing outdated Testnets section Co-authored-by: Thane Thomson <connect@thanethomson.com> * docs/rename: removing reference to tendermint/awesome repo Co-authored-by: Thane Thomson <connect@thanethomson.com> * docs/rename: contributing section updated Co-authored-by: Thane Thomson <connect@thanethomson.com> --------- Co-authored-by: Thane Thomson <connect@thanethomson.com> (cherry picked from commit 9883814) # Conflicts: # docs/.vuepress/redirects # docs/DOCS_README.md # docs/README.md # docs/app-dev/abci-cli.md # docs/app-dev/app-architecture.md # docs/app-dev/getting-started.md # docs/app-dev/indexing-transactions.md # docs/architecture/README.md # docs/architecture/adr-047-handling-evidence-from-light-client.md # docs/architecture/adr-056-light-client-amnesia-attacks.md # docs/architecture/adr-059-evidence-composition-and-lifecycle.md # docs/architecture/adr-template.md # docs/core/block-structure.md # docs/core/block-sync.md # docs/core/fast-sync.md # docs/core/how-to-read-logs.md # docs/core/running-in-production.md # docs/core/subscription.md # docs/core/using-cometbft.md # docs/introduction/architecture.md # docs/introduction/what-is-cometbft.md # docs/qa/v037/README.md # docs/rfc/README.md # docs/tendermint-core/block-sync.md # docs/tendermint-core/rpc.md # docs/tools/debugging.md # docs/tutorials/go-built-in.md # docs/tutorials/go.md # spec/consensus/consensus.md # spec/consensus/wal.md * rename: fixing cherry-pick conflicts in docs/core * rename: fixing further cherry-pick conflicts * rename: Inspect section removed from docs/tools/debugging * rename/docs: merging tutorials, from main and v0.34.x * rename/docs: links updated to v0.34.x branch * rename/docs: fixing docs.cometbft.com v0.34 links * docs/rename: updating links to v0.34.x branch * rename: fixing cherry-pick conflicts * Apply suggestions from code review Co-authored-by: Jasmina Malicevic <jasmina.dustinac@gmail.com> * rename/docs: reintroducing time_iota_ms parameter * Apply suggestions from code review Co-authored-by: Jasmina Malicevic <jasmina.dustinac@gmail.com> --------- Co-authored-by: Daniel <daniel.cason@informal.systems> Co-authored-by: Daniel Cason <cason@gandria> Co-authored-by: Jasmina Malicevic <jasmina.dustinac@gmail.com>

fix overwrite bug and stop splitting shares of size MsgShareSize

755c187

evan-forbes added the T:Bug Type: Bug (confirmed) label Mar 25, 2021

evan-forbes self-assigned this Mar 25, 2021

evan-forbes requested review from liamsi and tac0turtle as code owners March 25, 2021 19:39

evan-forbes requested review from adlerjohn and removed request for tac0turtle March 25, 2021 19:39

remove ineffectual code

42a0273

evan-forbes commented Mar 25, 2021

View reviewed changes

liamsi reviewed Mar 25, 2021

View reviewed changes

types/shares_test.go Outdated Show resolved Hide resolved

liamsi reviewed Mar 25, 2021

View reviewed changes

types/shares.go Outdated Show resolved Hide resolved

evan-forbes and others added 2 commits March 25, 2021 15:26

review feedback: better docs

b562b30

Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com>

remove uneeded copy and only fix the source of the bug

1813b73

Co-authored-by: Ismail Khoffi <Ismail.Khoffi@gmail.com>

liamsi approved these changes Mar 25, 2021

View reviewed changes

liamsi requested changes Mar 26, 2021

View reviewed changes

fix overwrite bug while also being consistent with using NamespacedSh…

b89cae7

…ares

liamsi self-requested a review March 26, 2021 15:42

liamsi reviewed Mar 26, 2021

View reviewed changes

liamsi approved these changes Mar 26, 2021

View reviewed changes

adlerjohn approved these changes Mar 26, 2021

View reviewed changes

update to the latest rsmt2d for the nmt wrapper

9d71970

liamsi reviewed Mar 26, 2021

View reviewed changes

evan-forbes merged commit d5371de into master Mar 26, 2021

evan-forbes deleted the evan/fix-appendToShare-overwritebug branch March 26, 2021 17:48

Conversation

evan-forbes commented Mar 25, 2021

Description

Uh oh!

evan-forbes Mar 25, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

evan-forbes Mar 25, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

liamsi Mar 25, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

evan-forbes Mar 25, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

liamsi left a comment

Choose a reason for hiding this comment

Uh oh!

liamsi left a comment

Choose a reason for hiding this comment

Uh oh!

evan-forbes commented Mar 26, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

liamsi Mar 26, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

liamsi Mar 26, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

liamsi left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

evan-forbes Mar 25, 2021 •

edited

Loading

evan-forbes Mar 25, 2021 •

edited

Loading

liamsi Mar 25, 2021 •

edited

Loading

evan-forbes Mar 25, 2021 •

edited

Loading

evan-forbes commented Mar 26, 2021 •

edited

Loading

liamsi Mar 26, 2021 •

edited

Loading

liamsi Mar 26, 2021 •

edited

Loading