spinresearch / merkle.rs Goto Github PK

We should have a Contributing.md in the repo describing the workflow for contributions.

We're using merkle's Proofs in messages that need to be serialized, and want to support Serde in addition to protobuf, so I added a very crude serialization-serde feature in my fork: afck@dd41698

Unfortunately Proof can't just be deserialized, so we added a ProofData that doesn't contain the algorithm field, and conversion functions.

Would you be interested in merging something like that into master? Is there a better way to handle proof deserialization?

archlinux ships protobuf 3.6.0.1, since the crate explicitly requires 3.5.1, the crate fails to build when executing:

cargo check --features=serialization-protobuf

Somewhat related to SpinResearch/RustySecrets#70

Pros and cons?

Sorry for the newbie question.
I want to maintain a global merkle tree to be accessed by all functions. I want to add new values to the already existing Merkle tree at irregular intervals.

Please help.

Obviously they're not too keen on proper use of semver. I think we should use Tilde requirements for rust-protobuf because even after merging #38 we should expect to continue dealing with this problem.

For example:

#![deny(
    missing_docs,
    missing_debug_implementations, missing_copy_implementations,
    trivial_casts, trivial_numeric_casts,
    unsafe_code, unstable_features,
    unused_import_braces, unused_qualifications
)]

https://pascalhertleif.de/artikel/good-practices-for-writing-rust-libraries/

ring only supports a small set of cryptographically secure Hash function. Rely on ring makes it hard to use SHA3 or other hash functions before ring implements them.

Since we're choosing to have the same domain separation as CT, we can add a suite of test vectors from a CT library to make sure we're compatible and that Merkle can be a dependency for a CT library.

Protobuf made a backwards-incompatible change without incrementing the major version number, breaking the build.

(A short-term solution would be using "~1.4.5" in Cargo.toml.)

Since for some use cases (see #36 and https://github.com/poanetwork/hbbft) knowing the index of a leaf inclusion proof is useful, it might be useful to add an index field to the Proof struct, instead of doing a separate expensive computation to find it. It should be very little additional computation to determine the index as well when already traversing a tree to create an inclusion proof.

When receiving a Proof over the wire from a 3rd party, you should not trust the index is correct, even if the Proof validates. Changing validate to check the index matches in addition to its current purpose, however, should be possible with little overhead.

#36 adds a panic if Lemma::index is called on a malformed Lemma, i.e. one where any of its sublemmas or itself violates the requirement that sibling_hash.is_some() == sub_lemma.is_some(). A malformed lemma currently can't be constructed, but it could certainly be deserialized, and calling validate is expensive because it does a lot of hashing. Should we:

• Always do full validation anyway, so that you can't even deserialize a lemma whose hashes don't match?

• Validate only the structure (i.e. the above requirement) on deserialization?

• Change the struct definition into one of the following?

pub struct Lemma {
    pub node_hash: Vec<u8>,
    pub sub_lemma: Option<(Positioned<Vec<u8>>, Box<Lemma>)>,
}

pub struct Lemma {
    pub node_hash: Vec<u8>,
    pub sub_lemma: Option<Box<SubLemma>>, // where `SubLemma` contains the sibling hash and position
}

pub struct Lemma {
    pub count: usize,
    // The positions can be computed from the lemma's index.
    pub index: usize,
    pub node_hash: Vec<u8>,
    pub sub_lemma: Option<(Vec<u8>, Box<Lemma>)>,
}

It appears from

While the repeated hashing of nodes looks very correct, I cannot see anywhere that the client can verify what the actual value that was included in the proof.

The last Lemma will have the node_hash of the LeafNode. However, there is no check in Proof.verify to check that proof.Value has any relationship to the Lemma that was Valid.

I don't see a reason I cannot construct a valid proof for some data in the tree, then change the Value and present it to you as a valid proof of some fake data.

MerkleTree::gen_proof takes a leaf value and returns a proof for it, but if the value occurs more than once, the user can't specify which proof they want. It would be useful to have a method that returns the proof for the n-th leaf, by index. I'd be happy to try and write code for that, if you are okay with it.

We are using it in hbbft and are currently working around the limitation by making the leafs unique (prepending an index byte), which is wasteful. Conversely, we compute the index from the proof here, which might also make sense as a method of Lemma:
https://github.com/poanetwork/hbbft/blob/71fa32c18f977c45e7869d47e50b4eccfd61d898/src/broadcast.rs#L493

Reference

I think this idea applies not only to serde, but to protobuf, too: #30 (comment)

Serializing the hash algorithm as a string like "SHA256", and on deserialization picking the appropriate constant from ring would be convenient.