[WIP] General Merkle Proof by mossid · Pull Request #2298 · tendermint/tendermint

mossid · 2018-08-30T13:52:54Z

Closes: #2502

Updated all relevant documentation in docs
Updated all code comments where relevant
Wrote tests
Updated CHANGELOG_PENDING.md

ValarDragon · 2018-09-03T22:01:42Z

Should we close #2296 then?

mossid · 2018-09-04T13:48:06Z

@ValarDragon That PR is for making reference squashed branch, so I think it is good to close that.

codecov-io · 2018-09-04T13:59:46Z

Codecov Report

❗ No coverage uploaded for pull request base (develop@4c4a95c). Click here to learn what that means.
The diff coverage is 24.21%.

@@            Coverage Diff             @@
##             develop    #2298   +/-   ##
==========================================
  Coverage           ?   61.16%           
==========================================
  Files              ?      202           
  Lines              ?    16658           
  Branches           ?        0           
==========================================
  Hits               ?    10189           
  Misses             ?     5600           
  Partials           ?      869

Impacted Files	Coverage Δ
rpc/core/abci.go	`0% <0%> (ø)`
lite/proxy/wrapper.go	`0% <0%> (ø)`
lite/proxy/query.go	`9.8% <0%> (ø)`
crypto/merkle/proof_simple_value.go	`0% <0%> (ø)`
lite/proxy/proof.go	`0% <0%> (ø)`
crypto/merkle/proof.go	`0% <0%> (ø)`
abci/example/kvstore/kvstore.go	`80.95% <100%> (ø)`
crypto/merkle/wire.go	`100% <100%> (ø)`
crypto/merkle/proof_key_path.go	`74.19% <74.19%> (ø)`
crypto/merkle/simple_proof.go	`67.3% <81.81%> (ø)`

mossid · 2018-09-04T14:11:52Z

Ready for review.

liamsi

I left a few comments. Mostly about documentation and few. But I also still think, we might split this up into two PRs: the general merkle stuff and the examples? It will make this slightly easier to review, too.

There are a bunch of TODOs and XXXs in the PR. If they won't be addressed in this PR, can we open an issue that summarizes what is letft to be done?

A brief description in an issue what the overall goal is, would be beneficial too.

liamsi · 2018-09-11T14:04:14Z

consensus/common_test.go

 // genesis, chain_id, priv_val
 var config *cfg.Config              // NOTE: must be reset for each _test.go file
-var ensureTimeout = time.Second * 1 // must be in seconds because CreateEmptyBlocksInterval is
+var ensureTimeout = time.Second * 5 // must be in seconds because CreateEmptyBlocksInterval is


why do need to increase the timeout here?

crypto/merkle/merkle.proto

crypto/merkle/proof.go

crypto/merkle/proof_simple_value.go

liamsi · 2018-09-11T14:27:59Z

crypto/merkle/simple_proof.go

+	"errors"
 	"fmt"
+
+	cmn "github.com/tendermint/tmlibs/common"


use common package in tendermint

liamsi · 2018-09-11T14:30:14Z

crypto/merkle/simple_tree_test.go

-			if ok {
-				t.Errorf("Expected verification to fail for wrong trail length.")
+			err = proof.Verify(rootHash, itemHash)
+			if err == nil {


For consistency: can we use require.Error here? And everywhere else?

liamsi · 2018-09-11T14:36:51Z

lite/proxy/query_test.go

+	require.NoError(err, "%#v", err)
+	// require.NotNil(proof)
+	// TODO: Ensure that *some* keys will be there, ensuring that proof is nil,
+	// (currently there's a race condition)


Is there still a race condition?

liamsi · 2018-09-11T14:38:50Z

rpc/core/abci.go

 		Data:   data,
 		Height: height,
-		Prove:  !trusted,
+		Prove:  prove,


Everywhere else prove is just a renaming of trusted. Why is it different here?

I think that is because this was the place where the trusted finally converted into prove which abci.RequestQuery wants.

crypto/merkle/proof_key_path.go

ebuchman · 2018-09-13T00:05:50Z

Would be really great if we could get an ADR here that explains what we're trying to do, why, and how. Would also help orient folks looking at cosmos/iavl#105

finalize rebase add protoc_merkle to Makefile

fix test_apps

ebuchman · 2018-09-28T17:27:44Z

@mossid thanks for updating - is this still a WIP or want to remove that?

ebuchman

This looks good, other than some deficiencies in documentation, both in code and the docs/spec/abci/ dir (since we're updating ABCI). We also need an ADR. There's also a few TODO/XXX that we should probably track in new issues.

We also need to update CHANGELOG. This is a breaking change to:

[abci] ResponseQuery
[rpc] /abci_query takes prove instead of trusted and switches the default behaviour to prove=false

ebuchman · 2018-09-26T17:59:12Z

crypto/merkle/proof_simple_value.go

+	cmn "github.com/tendermint/tendermint/libs/common"
+)
+
+const ProofOpSimpleValue = "simple:v"


We should include the encoding scheme in here? eg. amino ? or maybe use IPFS multicodec: https://github.com/multiformats/multicodec

crypto/merkle/proof.go

ebuchman · 2018-09-28T17:38:42Z

crypto/merkle/proof.go

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


What is the meaning of an op with an empty key, and should it still be represented in the keypath? Should we have len(poz) == len(keys)?

crypto/merkle/proof.go

crypto/merkle/proof_key_path.go

ebuchman · 2018-09-28T18:14:11Z

lite/proxy/query.go

-// GetWithProofOptions is useful if you want full access to the ABCIQueryOptions
-func GetWithProofOptions(path string, key []byte, opts rpcclient.ABCIQueryOptions,
+// GetWithProofOptions is useful if you want full access to the ABCIQueryOptions.
+// XXX Usage of path?  It's not used, and sometimes it's /, sometimes /key, sometimes /store.


Was noted in #2090. Added a small comment to docs (d8d268f#diff-69fe72a9f14b8f1a14776025eb902ed3R239) to address this but maybe issue should be re-opened?

lite/proxy/query.go

ebuchman · 2018-09-28T18:19:38Z

rpc/client/localclient.go


 func (Local) ABCIQueryWithOptions(path string, data cmn.HexBytes, opts ABCIQueryOptions) (*ctypes.ResultABCIQuery, error) {
-	return core.ABCIQuery(path, data, opts.Height, opts.Trusted)
+	return core.ABCIQuery(path, data, opts.Height, opts.Prove)


Oh, was this wrong before? Trusted should mean don't Prove.

ebuchman · 2018-09-28T18:20:17Z

rpc/client/mock/abci.go

 		return &res, nil
 	}
 	res.DeliverTx = a.App.DeliverTx(tx)
+	res.Height = -1 // TODO


ebuchman · 2018-09-28T18:20:58Z

rpc/client/mock/abci_test.go

 	assert.Nil(err, "expected no err on info")

-	_, err = r.ABCIQueryWithOptions("path", cmn.HexBytes("data"), client.ABCIQueryOptions{Trusted: false})
+	_, err = r.ABCIQueryWithOptions("path", cmn.HexBytes("data"), client.ABCIQueryOptions{Prove: false})


ebuchman · 2018-09-28T23:26:56Z

I'll address some of my comments and open an issue for the rest. Thanks.

* tmlibs -> libs * update changelog * address some comments from review of #2298

melekes · 2018-10-01T08:25:17Z

rpc/core/abci.go

-	}
-
+// | height    | int64  | 0       | false    | Height (0 means latest)                        |
+// | prove     | bool   | false   | false    | Includes proof if true                         |


Don't we want proofs by default?

melekes · 2018-10-01T08:26:58Z

rpc/client/mock/abci_test.go

 	assert.True(res.DeliverTx.IsOK())

+	// commit
+	// TODO: This may not be necessary in the future


in what future? under what conditions?

melekes · 2018-10-01T08:32:05Z

lite/proxy/query_test.go

+	cert := lite.NewBaseVerifier(chainID, seed.Height(), seed.Validators)
+
+	// Wait for tx confirmation.
+	done := make(chan int64)


txConfirmedCh

melekes · 2018-10-01T08:35:31Z

crypto/merkle/wire.go

+
+func init() {
+	cdc = amino.NewCodec()
+	cdc.Seal()


what Seal() does? prevents future modifications?

melekes · 2018-10-01T08:36:50Z

crypto/merkle/simple_proof.go

+// Check sp.Index/sp.Total manually if needed
+func (sp *SimpleProof) Verify(rootHash []byte, leafHash []byte) error {
+	if sp.Total < 0 {
+		return errors.New("Proof total must be positive")


cannot be negative

melekes · 2018-10-01T08:42:28Z

crypto/merkle/proof_key_path_test.go

+
+		for i := range keys {
+			enc := keyEncoding(rand.Intn(int(KeyEncodingMax)))
+			keys[i] = make([]byte, rand.Uint32()%20)


20 magic const

melekes · 2018-10-01T08:45:41Z

crypto/merkle/proof_key_path.go

+	cmn "github.com/tendermint/tendermint/libs/common"
+)
+
+/*


non-standard comment style https://blog.golang.org/godoc-documenting-go-code

melekes · 2018-10-01T08:48:48Z

crypto/merkle/proof.go

+func (prt *ProofRuntime) Decode(pop ProofOp) (ProofOperator, error) {
+	decoder := prt.decoders[pop.Type]
+	if decoder == nil {
+		return nil, cmn.NewError("unrecognized proof type %v", pop.Type)


no decoder for proof type %v

melekes · 2018-10-01T08:49:27Z

crypto/merkle/proof.go

+
+type OpDecoder func(ProofOp) (ProofOperator, error)
+
+type ProofRuntime struct {


godoc is missing

melekes · 2018-10-01T08:50:19Z

crypto/merkle/proof.go

+		key := op.GetKey()
+		if len(key) != 0 {
+			if !bytes.Equal(keys[0], key) {
+				return cmn.NewError("Key mismatch on operation #%d: expected %+v but %+v", i, []byte(keys[0]), []byte(key))


, but got

mossid requested review from ebuchman, melekes, xla and zramsay as code owners August 30, 2018 13:52

This was referenced Aug 30, 2018

General Merkle Proof cosmos/iavl#105

Merged

Generalized Merkle Proof Issue Visiting #2256

Closed

mossid force-pushed the joon/generalmerkle_squashed branch from 25fc69e to aacba15 Compare September 2, 2018 13:46

mossid force-pushed the joon/generalmerkle_squashed branch from 6b253b0 to 8eac3bc Compare September 4, 2018 11:49

ValarDragon mentioned this pull request Sep 4, 2018

WIP: General Merkle Proofs #2296

Closed

liamsi suggested changes Sep 11, 2018

View reviewed changes

liamsi reviewed Sep 11, 2018

View reviewed changes

crypto/merkle/proof_key_path.go Outdated Show resolved Hide resolved

ebuchman mentioned this pull request Sep 12, 2018

[WIP] generalized merkle proofs #1912

Closed

mossid changed the title ~~General Merkle Proof~~ [WIP] General Merkle Proof Sep 14, 2018

jaekwon and others added 12 commits September 27, 2018 01:32

first commit

84dc2b5

finalize rebase add protoc_merkle to Makefile

in progress

9c99b0e

fix kvstore

13696da

fix tests

8e35fbc

remove iavl dependency

fcba43d

fix tx_test

4f947a8

fix test_abci_cli

e9b1672

fix test_apps

fix test_apps

2e16296

fix test_cover

63680a4

rm rebase residue

b6333e0

address comment in progress

5af0c87

finalize rebase

02eb642

mossid force-pushed the joon/generalmerkle_squashed branch from 9bc4bd6 to 02eb642 Compare September 26, 2018 17:22

ebuchman approved these changes Sep 28, 2018

View reviewed changes

ebuchman mentioned this pull request Sep 28, 2018

Change ResponseQuery to return an array of proofs cosmos/cosmos-sdk#1146

Closed

ebuchman merged commit 71a34ad into tendermint:develop Sep 29, 2018

ebuchman mentioned this pull request Sep 29, 2018

General Merkle Follow Up #2509

Closed

8 tasks

ebuchman added a commit that referenced this pull request Sep 29, 2018

address some comments from review of #2298

0664d8e

ebuchman added a commit that referenced this pull request Sep 29, 2018

address some comments from review of #2298

40cef2d

ebuchman added a commit that referenced this pull request Sep 29, 2018

General Merkle Follow Up (#2510)

f36ed7e

* tmlibs -> libs * update changelog * address some comments from review of #2298

ethanfrey mentioned this pull request Sep 29, 2018

Define proofs for query iov-one/weave#5

Open

melekes reviewed Oct 1, 2018

View reviewed changes

liamsi mentioned this pull request Feb 12, 2019

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

Merged


		type OpDecoder func(ProofOp) (ProofOperator, error)

		type ProofRuntime struct {

Conversation

mossid commented Aug 30, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ValarDragon commented Sep 3, 2018

Uh oh!

mossid commented Sep 4, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

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

Uh oh!

Codecov Report

Uh oh!

mossid commented Sep 4, 2018

Uh oh!

liamsi left a comment • 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!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

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!

ebuchman commented Sep 13, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ebuchman commented Sep 28, 2018

Uh oh!

ebuchman left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ebuchman Sep 28, 2018 • 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!

ebuchman commented Sep 28, 2018

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

mossid commented Aug 30, 2018 •

edited

Loading

mossid commented Sep 4, 2018 •

edited

Loading

codecov-io commented Sep 4, 2018 •

edited

Loading

liamsi left a comment •

edited

Loading

ebuchman commented Sep 13, 2018 •

edited

Loading

ebuchman Sep 28, 2018 •

edited

Loading

melekes Oct 1, 2018 •

edited

Loading