[WIP] General Merkle Proof #2298

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

@@ -39,7 +39,7 @@ const (

 // 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

 	"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

 	resQuery, err := proxyAppQuery.QuerySync(abci.RequestQuery{
 		Path:   path,
 		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

@@ -61,7 +61,7 @@ func (c *Local) ABCIQuery(path string, data cmn.HexBytes) (*ctypes.ResultABCIQue
 }

 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

 func (a ABCIApp) BroadcastTxCommit(tx types.Tx) (*ctypes.ResultBroadcastTxCommit, error) {
 	res := ctypes.ResultBroadcastTxCommit{}
 	res.CheckTx = a.App.CheckTx(tx)
 	if res.CheckTx.IsErr() {
 		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

@@ -98,7 +98,7 @@ func TestABCIRecorder(t *testing.T) {
 	_, err := r.ABCIInfo()
 	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

@@ -173,9 +173,17 @@ func TestABCIApp(t *testing.T) {
 	require.NotNil(res.DeliverTx)
 	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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[WIP] General Merkle Proof #2298

[WIP] General Merkle Proof #2298

mossid commented Aug 30, 2018 •

edited

ValarDragon commented Sep 3, 2018

mossid commented Sep 4, 2018 •

edited

codecov-io commented Sep 4, 2018 •

edited

mossid commented Sep 4, 2018

liamsi left a comment •

edited

liamsi Sep 11, 2018

liamsi Sep 11, 2018

liamsi Sep 11, 2018

liamsi Sep 11, 2018

liamsi Sep 11, 2018

mossid Sep 26, 2018

ebuchman commented Sep 13, 2018 •

edited

ebuchman commented Sep 28, 2018

ebuchman left a comment

ebuchman Sep 26, 2018

ebuchman Sep 28, 2018

ebuchman Sep 28, 2018

ebuchman Sep 28, 2018 •

edited

ebuchman Sep 28, 2018

ebuchman Sep 28, 2018

ebuchman commented Sep 28, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018

melekes Oct 1, 2018 •

edited


		type OpDecoder func(ProofOp) (ProofOperator, error)

		type ProofRuntime struct {

[WIP] General Merkle Proof #2298

[WIP] General Merkle Proof #2298

Conversation

mossid commented Aug 30, 2018 • edited

ValarDragon commented Sep 3, 2018

mossid commented Sep 4, 2018 • edited

codecov-io commented Sep 4, 2018 • edited

Codecov Report

mossid commented Sep 4, 2018

liamsi left a comment • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ebuchman commented Sep 13, 2018 • edited

ebuchman commented Sep 28, 2018

ebuchman left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ebuchman Sep 28, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ebuchman commented Sep 28, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

melekes Oct 1, 2018 • edited

Choose a reason for hiding this comment

mossid commented Aug 30, 2018 •

edited

mossid commented Sep 4, 2018 •

edited

codecov-io commented Sep 4, 2018 •

edited

liamsi left a comment •

edited

ebuchman commented Sep 13, 2018 •

edited

ebuchman Sep 28, 2018 •

edited

melekes Oct 1, 2018 •

edited