[WIP] generalized merkle proofs by jaekwon · Pull Request #1912 · tendermint/tendermint

jaekwon · 2018-07-05T08:25:25Z

Related: ~~cosmos/iavl#84~~ edit(@liamsi): cosmos/iavl#85

mossid

Few modifications requested, LGTM.

mossid · 2018-07-05T21:16:26Z

crypto/merkle/proof.go

+// Extension of ProofOp (defined in merkle.proto)
+
+func (po ProofOp) Bytes() []byte {
+	bz, err := amino.MarshalBinary(po)


MustMarshalBinary?

Also, we maybe don't need this function if ProofOpis a member of abci.ResponseQuery because proto will handle marshaling.

mossid · 2018-07-05T21:24:27Z

crypto/merkle/proof.go

+	if !bytes.Equal(root, args[0]) {
+		return cmn.NewError("Calculated root hash is invalid: expected %+v but %+v", root, args[0])
+	}
+	return nil


We have to check len(keys) == 0 before returning nil

mossid · 2018-07-05T21:40:21Z

crypto/merkle/proof.go

+	}
+}
+
+func (prt *ProofRuntime) RegisterAminoOpDecoder(typ string, opType reflect.Type) {


Maybe better to have generator function instead of reflect.Type?

I think this is fine, esp for something called AminoOpDecoder.

mossid · 2018-07-05T22:00:40Z

crypto/merkle/simple_proof.go

-	computedHash := computeHashFromAunts(index, total, leafHash, sp.Aunts)
-	return computedHash != nil && bytes.Equal(computedHash, rootHash)
+// Verify that the SimpleProof proves the root hash.
+func (sp *SimpleProof) Verify(rootHash []byte, index int, total int, leafHash []byte) error {


Can we exclude index int, total int, leafHash []byte from the argument list? The fields are exported, the user can check it manually when they need to. Or we can make a new method like Validate to check the fields' validity.

I think we can exclude index/total, but we should leave rootHash and leafHash. The other two we can expose GetIndex() and GetTotal(). We should add a comment that the user should check these if they need to verify this info.

codecov-io · 2018-07-08T05:11:49Z

Codecov Report

Merging #1912 into jae/literefactor4 will decrease coverage by 1.18%.
The diff coverage is 21.42%.

@@                  Coverage Diff                  @@
##           jae/literefactor4    #1912      +/-   ##
=====================================================
- Coverage              61.24%   60.06%   -1.19%     
=====================================================
  Files                    191      162      -29     
  Lines                  15421    13527    -1894     
=====================================================
- Hits                    9445     8125    -1320     
+ Misses                  5128     4649     -479     
+ Partials                 848      753      -95

Impacted Files	Coverage Δ
abci/example/kvstore/kvstore.go	`80.64% <ø> (ø)`	⬆️
crypto/merkle/proof.go	`0% <0%> (ø)`
crypto/merkle/proof_simple_value.go	`0% <0%> (ø)`
rpc/client/mock/client.go	`20% <0%> (ø)`	⬆️
crypto/merkle/wire.go	`100% <100%> (ø)`
rpc/client/mock/abci.go	`80.76% <100%> (ø)`	⬆️
types/block.go	`29.84% <100%> (ø)`
abci/example/kvstore/persistent_kvstore.go	`64.04% <100%> (ø)`	⬆️
crypto/merkle/merkle.pb.go	`14.28% <14.28%> (ø)`
crypto/merkle/simple_proof.go	`69.23% <90.9%> (+4.11%)`	⬆️
... and 117 more

mossid · 2018-07-11T01:07:31Z

Gopkg.toml

  version = "~0.10.1"

+[[constraint]]
+  name = "github.com/tendermint/iavl"


Can we exclude IAVL dependency from tendermint? IAVL repo will be moved into the SDK, making dependency cycle. The only part in this code that uses IAVL directly is abci example, which can be reverted or moved into the SDK. @liamsi @ebuchman

Talked to bucky recently and figured we'll move it into tendermint/tendermint because it's useful to have them for the abci/example/kvstore app.

Truth is that it will still be much more convenient to have it in the SDK as that is where it is primarily used and thus putting it there will maximally reduce developer overhead when changes need to be made. So I'd still advocate for putting it in the SDK and not requiring it in Tendermint if possible

mossid · 2018-07-11T01:08:06Z

abci/example/kvstore/kvstore.go

 type State struct {
-	db      dbm.DB
+	db   dbm.DB
+	tree *iavl.VersionedTree


See comment above

jaekwon · 2018-07-16T22:08:05Z

crypto/merkle/proof_key_path_test.go

+	var path KeyPath
+	keys := make([][]byte, 10)
+
+	for d := 0; d < 20; d++ {


Maybe 1e4 or 1e5?

liamsi

1st pass while going through the changes. Will follow up with a more detailed review shortly.

liamsi · 2018-07-18T09:43:32Z

abci/types/types.proto

  bytes key = 6;
  bytes value = 7;
-  bytes proof = 8;
+  merkle.Proof proof = 8;


Note: This will be breaking.

liamsi · 2018-07-18T09:45:22Z

crypto/merkle/compile.sh

+protoc --gogo_out=. -I $GOPATH/src/ -I . -I $GOPATH/src/github.com/gogo/protobuf/protobuf merkle.proto
+echo "--> adding nolint declarations to protobuf generated files"
+awk '/package merkle/ { print "//nolint: gas"; print; next }1' merkle.pb.go > merkle.pb.go.new
+mv merkle.pb.go.new merkle.pb.go


Nit: proto files often are compiled using a gen.go file. See here for example: https://github.com/google/trillian/blob/e856bae55959e54d2e480790d7c881aced7a4b5c/gen.go#L15-L24

Not sure if this works with gogoproto though.

liamsi · 2018-07-18T09:51:03Z

crypto/merkle/wire.go

+
+func RegisterWire(cdc *amino.Codec) {
+	// Nothing to do.
+}


As far as I see, this file's only intention is to provide a global variable which does not hold any state. Should we remove RegisterWire and Seal the codec instead?

liamsi · 2018-07-18T10:01:29Z

crypto/merkle/proof_key_path.go

+
+	NOTE: Punycode will never be supported here, because not all values can be
+	decoded.  For example, no string decodes to the string "xn--blah" in
+	Punycode.


Maybe I should continue reading first but if it is unsupported / disallowed, it would be great to have a test-case showing what happens if punycode is used.

liamsi · 2018-07-18T10:03:23Z

crypto/merkle/proof.go

+// ProofOp gets converted to an instance of ProofOperator:
+
+type ProofOperator interface {
+	Run([][]byte) ([][]byte, error)


As someone not involved in the reasoning / design of these changes, it is unclear what Run will do (and what it will return) in this context.

liamsi · 2018-07-18T10:24:30Z

rpc/client/types.go

-// (which will result in a proof being returned).
-var DefaultABCIQueryOptions = ABCIQueryOptions{Height: 0, Trusted: false}
+// DefaultABCIQueryOptions are latest height (0) and prove false.
+var DefaultABCIQueryOptions = ABCIQueryOptions{Height: 0, Prove: false}


Wouldn't the equivalent of Trusted: false be Prove: true instead?

liamsi · 2018-07-30T18:51:38Z

Also linking #2052 as both PRs have jae/literefactor4 as a base branch.

liamsi · 2018-07-31T16:33:04Z

@mossid I'll submit a PR to resolve above merge conflicts (I'm not if I can push here directly). I'll do so without changing above base branch jae/literefactor4 (for now). After that and when all issues are resolved, we can change the base branch to develop. (Still need to confirm with @jaekwon if this should go into develop or into jae/literefactor4).

@mossid: I think the easiest way to unblock yourself on the outdated protofiles / merge conflicts would be to cherrypick the latest two commits from: https://github.com/tendermint/tendermint/compare/jae/literefactor4...Liamsi:jae/generalmerkle?expand=1
(namely 58fb372 and e9fc2c1)

These changes resolve the merge conflicts, regenerate all relevant protos. They also contain some changes to gogoproto params (and consequential changes).

Let me know if this works for you.

mossid · 2018-07-30T17:20:16Z

crypto/merkle/proof.go

+
+	for i, op := range poz {
+		key := op.GetKey()
+		if len(key) != 0 {


Can we add the code for checking the length of the remaining keys for preventing panic if the keypath is too short?

ebuchman · 2018-09-12T23:40:43Z

Closing for #2298

first commit

4f7565b

jaekwon requested review from ebuchman, melekes and xla as code owners July 5, 2018 08:25

jaekwon mentioned this pull request Jul 5, 2018

WIP generalized merkle proofs cosmos/iavl#84

Closed

mossid suggested changes Jul 5, 2018

View reviewed changes

Fix tests

c039b61

xla assigned liamsi Jul 9, 2018

Trusted -> \!Prove

ad873c7

mossid mentioned this pull request Jul 9, 2018

WIP: Multi Layer Proof cosmos/cosmos-sdk#1062

Closed

jaekwon mentioned this pull request Jul 10, 2018

WIP generalized merkle proofs cosmos/iavl#85

Closed

Fixing tests...

77a51e7

mossid reviewed Jul 11, 2018

View reviewed changes

jaekwon and others added 3 commits July 12, 2018 00:27

fixed all tests

3a5a7a7

Commit KeyPath

7495528

in progress

b16ce7e

jaekwon commented Jul 16, 2018

View reviewed changes

add test

f31a6f0

mossid approved these changes Jul 17, 2018

View reviewed changes

liamsi reviewed Jul 18, 2018

View reviewed changes

xla changed the title ~~WIP generalized merkle proofs~~ [WIP] generalized merkle proofs Jul 18, 2018

liamsi mentioned this pull request Jul 25, 2018

dep: Change the tendermint import cosmos/iavl#90

Closed

liamsi added the C:light Component: Light label Jul 30, 2018

mossid suggested changes Aug 9, 2018

View reviewed changes

xla added this to the launch milestone Aug 27, 2018

liamsi changed the base branch from jae/literefactor4 to develop August 29, 2018 23:44

jaekwon mentioned this pull request Aug 29, 2018

WIP: General Merkle Proofs #2296

Closed

ebuchman closed this Sep 12, 2018

liamsi mentioned this pull request Feb 12, 2019

update tendermint dependency to v0.30 cosmos/iavl#125

Merged

mircea-c deleted the jae/generalmerkle branch October 10, 2019 15:28

mircea-c restored the jae/generalmerkle branch October 10, 2019 15:28

Conversation

jaekwon commented Jul 5, 2018 • edited by liamsi Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mossid left a comment

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!

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!

codecov-io commented Jul 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

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!

liamsi left a comment

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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

liamsi commented Jul 30, 2018

Uh oh!

liamsi commented Jul 31, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ebuchman commented Sep 12, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

jaekwon commented Jul 5, 2018 •

edited by liamsi

Loading

codecov-io commented Jul 8, 2018 •

edited

Loading

liamsi commented Jul 31, 2018 •

edited

Loading