Problem: Inefficient binary encoding of Merkle tree path (CRO-149) by yihuang · Pull Request #558 · crypto-com/thaler

yihuang · 2019-11-06T18:47:59Z

I've refactored the Path representation with Vec, which makes it both more correct and more compact serialization (Old representation allows some illegal path state).
With the current implementation, the gain of further optimizing the serialization with BitVec is small, I guess it doesn't worth the trouble anymore.

tomtau

@yihuang thanks and congrats on your first PR!
I forgot to point to this document (did you go through the PR checklist?): https://github.com/crypto-com/chain/blob/master/CONTRIBUTING.md#working-on-issues (and https://rfc.zeromq.org/spec:42/C4/#23-patch-requirements )

Looks OK -- I guess flattening out the path representation is the biggest win in terms of efficiency and simplicity (in common cases with short paths, as the tree depth is limited / bounded); for our own reference, could you do a simple example byte size comparison (e.g. a path with 4 nodes -- old_representation.encode().len() vs new_representation.encode().len())?

A couple of small things:

the patch fails to compile: https://travis-ci.org/crypto-com/chain/jobs/608353067#L3540

   --> chain-core/src/common/merkle_tree.rs:102:21
3542    |
3543102 |                     path
3544    |                     ^^^^ expected enum `std::option::Option`, found struct `common::merkle_tree::Path`
3545    |
3546    = note: expected type `std::option::Option<common::merkle_tree::Path>`
3547               found type `common::merkle_tree::Path`
3548
3549error: aborting due to previous error
3550
3551

the patch isn't formatted with the default style convention we use (cargo fmt should fix it): https://travis-ci.org/crypto-com/chain/jobs/608353067#L3593

Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 76:
3594     {
3595         match self {
3596             Tree::Empty => None,
3597-            Tree::Leaf { hash: node_hash, .. } => {
3598+            Tree::Leaf {
3599+                hash: node_hash, ..
3600+            } => {
3601                 if &hash(value, NodeType::Leaf) == node_hash {
3602-                    Some(Path{leaf_hash: node_hash.clone(), nodes: vec![]})
3603+                    Some(Path {
3604+                        leaf_hash: node_hash.clone(),
3605+                        nodes: vec![],
3606+                    })
3607                 } else {
3608                     None
3609                 }
3610Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 85:
3611             }
3612-            Tree::Node { hash: node_hash, left, right } => {
3613-                left.generate_path(value).map_or_else(|| {
3614+            Tree::Node {
3615+                hash: node_hash,
3616+                left,
3617+                right,
3618+            } => left.generate_path(value).map_or_else(
3619+                || {
3620                     right.generate_path(value).map(|mut path| {
3621-                        path.nodes.push(PathNode{
3622+                        path.nodes.push(PathNode {
3623                             node_hash: node_hash.clone(),
3624                             child_hash: left.hash(),
3625-                            hash_side: Side::Left
3626+                            hash_side: Side::Left,
3627                         });
3628                         path
3629                     })
3630Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 96:
3631-                }, |mut path| {
3632-                    path.nodes.push(PathNode{
3633+                },
3634+                |mut path| {
3635+                    path.nodes.push(PathNode {
3636                         node_hash: node_hash.clone(),
3637                         child_hash: right.hash(),
3638-                        hash_side: Side::Right
3639+                        hash_side: Side::Right,
3640                     });
3641                     path
3642-                })
3643-            }
3644+                },
3645+            ),
3646         }
3647     }
3648 }
3649Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 111:
3650 #[derive(Debug, PartialEq, Eq, Clone, Encode, Decode)]
3651 pub enum Side {
3652     Left,
3653-    Right
3654+    Right,
3655 }
3656 
3657 #[derive(Debug, PartialEq, Eq, Clone, Encode, Decode)]
3658Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 118:
3659 pub struct PathNode {
3660     node_hash: H256,
3661-    child_hash: H256,  // hash of left child unless reversed
3662+    child_hash: H256, // hash of left child unless reversed
3663     hash_side: Side,  // the side of hash child
3664 }
3665 
3666Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 124:
3667 #[derive(Debug, PartialEq, Eq, Clone, Encode, Decode)]
3668 pub struct Path {
3669     leaf_hash: H256,
3670-    nodes: Vec<PathNode>,  // order from inner node to outer node
3671+    nodes: Vec<PathNode>, // order from inner node to outer node
3672 }
3673 
3674 impl Path {
3675Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 142:
3676             let ref_hash = if i == 0 {
3677                 self.leaf_hash
3678             } else {
3679-                self.nodes[i-1].node_hash
3680+                self.nodes[i - 1].node_hash
3681             };
3682 
3683             let calced_hash = if Side::Left == node.hash_side {
3684Diff in /home/travis/build/crypto-com/chain/chain-core/src/common/merkle_tree.rs at line 300:
3685     {
3686         self.generate_path(&value).map(|path| {
3687             assert_eq!(&self.root_hash(), path.hash());
3688-            Proof {
3689-                path,
3690-                value,
3691-            }
3692+            Proof { path, value }
3693         })
3694     }

the patch commit message doesn't follow point 7: https://rfc.zeromq.org/spec:42/C4/#23-patch-requirements

A patch commit message MUST consist of a single short (less than 50 characters) line stating the problem ("Problem: ...") being solved, followed by a blank line and then the proposed solution ("Solution: ...").

yihuang · 2019-11-07T01:58:44Z

Sorry about the compile error and format, just fixed them, and made a force push to keep it clean.

codecov · 2019-11-07T02:49:43Z

Codecov Report

Merging #558 into master will decrease coverage by <.01%.
The diff coverage is 98.11%.

@@            Coverage Diff             @@
##           master     #558      +/-   ##
==========================================
- Coverage   67.53%   67.53%   -0.01%     
==========================================
  Files         124      124              
  Lines       14319    14321       +2     
==========================================
+ Hits         9671     9672       +1     
- Misses       4648     4649       +1

Impacted Files	Coverage Δ
chain-core/src/common/merkle_tree.rs	`98.79% <98.11%> (-0.24%)`	⬇️
chain-core/src/tx/fee/mod.rs	`87.68% <0%> (-0.5%)`	⬇️
...transaction_builder/default_transaction_builder.rs	`88.06% <0%> (+0.41%)`	⬆️

yihuang · 2019-11-07T02:54:23Z

I've compared the serialization length between new and old representation, the numbers are below:

Path length	Old	New	Hashes
3	168	163	5*32 = 160
9	570	553	17 * 32 = 544

With the new representation, the extra bytes without the hashes is 553 - 544 = 9 bytes, 8 bytes for the side field of each node, 1 byte for the length of Vec.

The test code:

use chain_core::common::merkle_tree::{MerkleTree};
use parity_scale_codec::{Encode};

fn main() {
    let values = vec![
        "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
        // "10", "11", "12", "13", "14", "15", "16", "17", "18", "19",
        // "110", "111", "112", "113", "114", "115", "116", "117", "118", "119",
        // "1110", "1111", "1112", "1113", "1114", "1115", "1116", "1117", "1118", "1119",
        // "11110", "11111", "11112", "11113", "11114", "11115", "11116", "11117", "11118", "11119",
        // "111110", "111111", "111112", "111113", "111114", "111115", "111116", "111117", "111118", "111119",
        // "1111110", "1111111", "1111112", "1111113", "1111114", "1111115", "1111116", "1111117", "1111118", "1111119",
        // "11111110", "11111111", "11111112", "11111113", "11111114", "11111115", "11111116", "11111117", "11111118", "11111119",
        // "111111110", "111111111", "111111112", "111111113", "111111114", "111111115", "111111116", "111111117", "111111118", "111111119",
        // "1111111110", "1111111111", "1111111112", "1111111113", "1111111114", "1111111115", "1111111116", "1111111117", "1111111118", "1111111119",
        // "11111111110", "11111111111", "11111111112", "11111111113", "11111111114", "11111111115", "11111111116", "11111111117", "11111111118", "11111111119",
        // "111111111110", "111111111111", "111111111112", "111111111113", "111111111114", "111111111115", "111111111116", "111111111117", "111111111118", "111111111119",
        // "1111111111110", "1111111111111", "1111111111112", "1111111111113", "1111111111114", "1111111111115", "1111111111116", "1111111111117", "1111111111118", "1111111111119",
    ];
    let tree = MerkleTree::new(values);
    let path = tree.generate_path(&"9").unwrap();
    println!("{}", path.encode().len());
}

tomtau · 2019-11-07T03:03:18Z

bors r+

538: Problem:(CRO-521) unbonded from custom time is ignored in genesis initconfig r=tomtau a=linfeng-crypto Solution: change the parameters of `new_init`: change `genesis_time` from `Timespec` into `Option<Timespec>`, remove the `bool` type parameter `bonded`, add a `&StakedStateDestination` type parameter. 558: Problem: Inefficient binary encoding of Merkle tree path (CRO-149) r=tomtau a=yihuang I've refactored the ``Path`` representation with ``Vec``, which makes it both more correct and more compact serialization (Old representation allows some illegal path state). With the current implementation, the gain of further optimizing the serialization with ``BitVec`` is small, I guess it doesn't worth the trouble anymore. Co-authored-by: linfeng <linfeng@crypto.com> Co-authored-by: yihuang <huang@crypto.com>

bors · 2019-11-07T05:33:52Z

Timed out (retrying...)

chain-core/src/common/merkle_tree.rs

leejw51crypto · 2019-11-07T06:34:43Z

lgtm,
does this work with the same result of previous one?

tomtau · 2019-11-07T07:04:19Z

lgtm,
does this work with the same result of previous one?

yeah, there are a bunch of tests from the old implementation: https://github.com/crypto-com/chain/blob/master/chain-core/src/common/merkle_tree.rs#L381 -- one different thing is that the previous representation could have represented some invalid states, e.g. no Sibling but with subpath or something like that

tomtau · 2019-11-07T07:22:47Z

bors r+

leejw51crypto

good job

538: Problem:(CRO-521) unbonded from custom time is ignored in genesis initconfig r=tomtau a=linfeng-crypto Solution: change the parameters of `new_init`: change `genesis_time` from `Timespec` into `Option<Timespec>`, remove the `bool` type parameter `bonded`, add a `&StakedStateDestination` type parameter. 556: Problem: (CRO-494) not possible to create unjail transaction in client-cli r=tomtau a=leejw51 Solution: call unjail in cli increase coverage fix sync fix save public, private key 558: Problem: Inefficient binary encoding of Merkle tree path (CRO-149) r=tomtau a=yihuang I've refactored the ``Path`` representation with ``Vec``, which makes it both more correct and more compact serialization (Old representation allows some illegal path state). With the current implementation, the gain of further optimizing the serialization with ``BitVec`` is small, I guess it doesn't worth the trouble anymore. Co-authored-by: linfeng <linfeng@crypto.com> Co-authored-by: Jongwhan Lee <jonghwan@crypto.com> Co-authored-by: yihuang <huang@crypto.com>

bors · 2019-11-07T09:02:07Z

Canceled

tomtau

nice comment art 👍 -- @yihuang could you squash the commits (rebase it on the latest master)?

yihuang · 2019-11-07T10:29:31Z

done @tomtau

tomtau

a few clippy suggestions:

error: using `clone` on a `Copy` type
1596  --> chain-core/src/common/merkle_tree.rs:84:36
1597   |
159884 |                         leaf_hash: node_hash.clone(),
1599   |                                    ^^^^^^^^^^^^^^^^^ help: try dereferencing it: `*node_hash`
1600   |
1601   = note: `-D clippy::clone-on-copy` implied by `-D warnings`
1602   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#clone_on_copy
1603
1604error: using `clone` on a `Copy` type
1605  --> chain-core/src/common/merkle_tree.rs:99:40
1606   |
160799 |                             node_hash: node_hash.clone(),
1608   |                                        ^^^^^^^^^^^^^^^^^ help: try dereferencing it: `*node_hash`
1609   |
1610   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#clone_on_copy
1611
1612error: using `clone` on a `Copy` type
1613   --> chain-core/src/common/merkle_tree.rs:108:36
1614    |
1615108 |                         node_hash: node_hash.clone(),
1616    |                                    ^^^^^^^^^^^^^^^^^ help: try dereferencing it: `*node_hash`
1617    |
1618    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#clone_on_copy
1619
1620error: aborting due to 3 previous errors

tomtau · 2019-11-07T13:18:01Z

and test compilation fails: https://travis-ci.org/crypto-com/chain/jobs/608661250#L1426

failures:
1425
1426---- src/common/merkle_tree.rs - common::merkle_tree::Side (line 121) stdout ----
1427error: expected one of `!`, `.`, `::`, `;`, `?`, `{`, `}`, or an operator, found `,`
1428 --> src/common/merkle_tree.rs:122:11
1429  |
14303 | node_hash1, Left
1431  |           ^ expected one of 8 possible tokens here
1432
1433error: aborting due to previous error
1434
1435Couldn't compile the test.
1436---- src/common/merkle_tree.rs - common::merkle_tree::Side (line 135) stdout ----
1437error[E0422]: cannot find struct, variant or union type `Path` in this scope
1438 --> src/common/merkle_tree.rs:136:1
1439  |
14403 | Path {
1441  | ^^^^ not found in this scope
1442  |
1443help: possible candidate is found in another module, you can import it into scope
1444  |
14452 | use std::path::Path;
1446  |
1447
1448error[E0425]: cannot find value `leaf_hash` in this scope
1449 --> src/common/merkle_tree.rs:137:14
1450  |
14514 |   leaf_hash: leaf_hash,
1452  |              ^^^^^^^^^ not found in this scope
1453
1454error[E0422]: cannot find struct, variant or union type `PathNode` in this scope
1455 --> src/common/merkle_tree.rs:138:12
1456  |
14575 |   nodes: [ PathNode {
1458  |            ^^^^^^^^ not found in this scope
1459
1460error[E0425]: cannot find value `node_hash0` in this scope
1461 --> src/common/merkle_tree.rs:139:16
1462  |
14636 |     node_hash: node_hash0,
1464  |                ^^^^^^^^^^ not found in this scope
1465
1466error[E0425]: cannot find value `child_hash0` in this scope
1467 --> src/common/merkle_tree.rs:140:17
1468  |
14697 |     child_hash: child_hash0,
1470  |                 ^^^^^^^^^^^ not found in this scope
1471
1472error[E0425]: cannot find value `Right` in this scope
1473 --> src/common/merkle_tree.rs:141:16
1474  |
14758 |     hash_side: Right
1476  |                ^^^^^ not found in this scope
1477  |
1478help: possible candidates are found in other modules, you can import them into scope
1479  |
14802 | use core::fmt::Alignment::Right;
1481  |
14822 | use core::fmt::rt::v1::Alignment::Right;
1483  |
14842 | use serde::export::fmt::Alignment::Right;
1485  |
14862 | use serde::export::fmt::rt::v1::Alignment::Right;
1487  |
1488    and 2 other candidates
1489
1490error[E0422]: cannot find struct, variant or union type `PathNode` in this scope
1491 --> src/common/merkle_tree.rs:142:6
1492  |
14939 |   }, PathNode {
1494  |      ^^^^^^^^ not found in this scope
1495
1496error[E0425]: cannot find value `node_hash1` in this scope
1497  --> src/common/merkle_tree.rs:143:16
1498   |
149910 |     node_hash: node_hash1,
1500   |                ^^^^^^^^^^ not found in this scope
1501
1502error[E0425]: cannot find value `child_hash1` in this scope
1503  --> src/common/merkle_tree.rs:144:17
1504   |
150511 |     child_hash: child_hash1,
1506   |                 ^^^^^^^^^^^ not found in this scope
1507
1508error[E0425]: cannot find value `Left` in this scope
1509  --> src/common/merkle_tree.rs:145:16
1510   |
151112 |     hash_side: Left
1512   |                ^^^^ not found in this scope
1513   |
1514help: possible candidates are found in other modules, you can import them into scope
1515   |
15162  | use core::fmt::Alignment::Left;
1517   |
15182  | use core::fmt::rt::v1::Alignment::Left;
1519   |
15202  | use serde::export::fmt::Alignment::Left;
1521   |
15222  | use serde::export::fmt::rt::v1::Alignment::Left;
1523   |
1524     and 2 other candidates
1525
1526error: aborting due to 10 previous errors
1527
1528Some errors have detailed explanations: E0422, E0425.
1529For more information about an error, try `rustc --explain E0422`.
1530Couldn't compile the test.
1531
1532failures:
1533    src/common/merkle_tree.rs - common::merkle_tree::Side (line 121)
1534    src/common/merkle_tree.rs - common::merkle_tree::Side (line 135)

yihuang · 2019-11-07T15:51:53Z

Clippy and doctest problem fixed.

represent merkle tree path using Vec, more efficient, more correct and simpler. ascii art to explain merkle path fix clippy and doctest errors fix doctest

tomtau

bors r+

558: Problem: Inefficient binary encoding of Merkle tree path (CRO-149) r=tomtau a=yihuang I've refactored the ``Path`` representation with ``Vec``, which makes it both more correct and more compact serialization (Old representation allows some illegal path state). With the current implementation, the gain of further optimizing the serialization with ``BitVec`` is small, I guess it doesn't worth the trouble anymore. Co-authored-by: yihuang <huang@crypto.com>

bors · 2019-11-08T04:36:26Z

Build failed

continuous-integration/drone/push

tomtau · 2019-11-08T05:52:41Z

bors retry

558: Problem: Inefficient binary encoding of Merkle tree path (CRO-149) r=tomtau a=yihuang I've refactored the ``Path`` representation with ``Vec``, which makes it both more correct and more compact serialization (Old representation allows some illegal path state). With the current implementation, the gain of further optimizing the serialization with ``BitVec`` is small, I guess it doesn't worth the trouble anymore. Co-authored-by: yihuang <huang@crypto.com>

bors · 2019-11-08T06:37:27Z

Build succeeded

yihuang force-pushed the cro-149 branch from 7a796d8 to 1c81a37 Compare November 6, 2019 18:49

tomtau requested review from calvinaco, devashishdxt, leejw51crypto, lezzokafka, linfeng-crypto and tomtau November 7, 2019 01:10

tomtau suggested changes Nov 7, 2019

View reviewed changes

tomtau changed the title ~~Problem (CRO 149): Compact the serialization of merkle tree path~~ Problem: Inefficient binary encoding of Merkle tree path (CRO 149) Nov 7, 2019

tomtau changed the title ~~Problem: Inefficient binary encoding of Merkle tree path (CRO 149)~~ Problem: Inefficient binary encoding of Merkle tree path (CRO-149) Nov 7, 2019

yihuang force-pushed the cro-149 branch from 1c81a37 to 4991a13 Compare November 7, 2019 01:57

yihuang force-pushed the cro-149 branch from 4991a13 to 8df1cdf Compare November 7, 2019 02:04

leejw51crypto reviewed Nov 7, 2019

View reviewed changes

chain-core/src/common/merkle_tree.rs Show resolved Hide resolved

leejw51crypto approved these changes Nov 7, 2019

View reviewed changes

tomtau suggested changes Nov 7, 2019

View reviewed changes

yihuang force-pushed the cro-149 branch from ab63bbc to fc312cb Compare November 7, 2019 10:29

tomtau self-requested a review November 7, 2019 13:16

tomtau suggested changes Nov 7, 2019

View reviewed changes

yihuang force-pushed the cro-149 branch from fc312cb to 63ae1bd Compare November 7, 2019 15:51

Problem: (CRO-149) inefficient Merkle proof binary serialisation

a3bfc9d

represent merkle tree path using Vec, more efficient, more correct and simpler. ascii art to explain merkle path fix clippy and doctest errors fix doctest

yihuang force-pushed the cro-149 branch from 63ae1bd to a3bfc9d Compare November 7, 2019 16:01

tomtau approved these changes Nov 8, 2019

View reviewed changes

bors bot merged commit a3bfc9d into crypto-com:master Nov 8, 2019

yihuang deleted the cro-149 branch December 19, 2019 08:22

Conversation

yihuang commented Nov 6, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tomtau left a comment

Choose a reason for hiding this comment

Uh oh!

yihuang commented Nov 7, 2019

Uh oh!

codecov bot commented Nov 7, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

yihuang commented Nov 7, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tomtau commented Nov 7, 2019

Uh oh!

bors bot commented Nov 7, 2019

Timed out (retrying...)

Uh oh!

Uh oh!

leejw51crypto commented Nov 7, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tomtau commented Nov 7, 2019

Uh oh!

tomtau commented Nov 7, 2019

Uh oh!

leejw51crypto left a comment

Choose a reason for hiding this comment

Uh oh!

bors bot commented Nov 7, 2019

Canceled

Uh oh!

tomtau 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!

yihuang commented Nov 7, 2019

Uh oh!

tomtau left a comment

Choose a reason for hiding this comment

Uh oh!

tomtau commented Nov 7, 2019

Uh oh!

yihuang commented Nov 7, 2019

Uh oh!

tomtau left a comment

Choose a reason for hiding this comment

Uh oh!

bors bot commented Nov 8, 2019

Build failed

Uh oh!

tomtau commented Nov 8, 2019

Uh oh!

bors bot commented Nov 8, 2019

Build succeeded

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

yihuang commented Nov 6, 2019 •

edited

Loading

codecov bot commented Nov 7, 2019 •

edited

Loading

yihuang commented Nov 7, 2019 •

edited

Loading

leejw51crypto commented Nov 7, 2019 •

edited

Loading

tomtau left a comment •

edited

Loading