Pedersen Hash Improper Configuration

[stechu]

Summary of Bug

Pedersen Hash Improper Configuration

Version

This tutorial's configuration of pedersen hash window (https://github.com/arkworks-rs/r1cs-tutorial/blob/main/merkle_tree_example/src/common.rs#L18):

pub type TwoToOneHash = PedersenCRHCompressor<EdwardsProjective, TECompressor, TwoToOneWindow>;
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct TwoToOneWindow;

// `WINDOW_SIZE * NUM_WINDOWS` = 2 * 256 bits = enough for hashing two outputs.
impl pedersen::Window for TwoToOneWindow {
    const WINDOW_SIZE: usize = 128;
    const NUM_WINDOWS: usize = 4;
}

pub type LeafHash = PedersenCRHCompressor<EdwardsProjective, TECompressor, LeafWindow>;

#[derive(Clone, PartialEq, Eq, Hash)]
pub struct LeafWindow;

// `WINDOW_SIZE * NUM_WINDOWS` = 2 * 256 bits = enough for hashing two outputs.
impl pedersen::Window for LeafWindow {
    const WINDOW_SIZE: usize = 144;
    const NUM_WINDOWS: usize = 4;
}

Which configure the window_size to N, and the num_windows to 4. This is not consistent with the arkworks test: (https://github.com/arkworks-rs/crypto-primitives/blob/main/src/merkle_tree/mod.rs#L463).

From my understanding, this will introduce a potential security vulnerability.

Happy to create a PR if this is confirmed by arkworks devs.

Steps to Reproduce

[weikengchen]

It should be okay, for the following reasons.

• The tutorial uses PedersenCRH along with a compressor "TECompressor", so, the result of hashing is only the x coordinate of the Edwards curve for BLS12-381, which would be about 256 bits.

• The arkworks test uses the pure PedersenCRH without a compressor, type H = pedersen::CRH<JubJub, Window4x256>;, therefore, the hashing result is a point in the affine format (x, y). Converting it to bits, it would be about 512 bits. That is why the window in that test is 2x larger.

In many situations, TECompressor can be used comfortably for twisted Edwards curves. The original PedersenCRH, however, is able to work with non-twisted-Edwards curves (though, in that case, it is not useful in the constraint world).

[stechu]

@weikengchen Thanks for the explanation of how "TECompressor" work. Here what I mean is not the concrete setting of NUM_WINDOWS. From my understanding how does Pedersen work, you always want to set the WINDOWS_SIZE to 4 (or 3 in some situation), since that is the size of chunks the you would break the input into, and then set NUM_WINDOWS to a relative large number, that is the number of multiplication you do. And in above tutorial setting, it is the other way around, it sets NUM_WINDOWS to 4, and variable WINDOWS_SIZE. Seems to be a typo?

[weikengchen]

Got it. You are right.

Yes. The tutorial is using a large window. Likely it is still secure? Because log(field size) is still larger than the window size. What do you think?

The performance overhead would likely be similar, as the Pedersen CRH precomputes the individual generators (https://github.com/arkworks-rs/crypto-primitives/blob/main/src/crh/pedersen/mod.rs#L33), and the hash computation is merely a conditional point addition.

[weikengchen]

Nevertheless, I agree it is better for the tutorial to use a more standard window. I will make a PR.

[stechu]

Honestly, I haven't dived into the details of the security proofs of Pedersen. From the original discussion (https://github.com/zcash/zcash/issues/2234), it appears that chosen 4 bit window is more of a performance consideration.

Somehow I intuitively think relatively large number of multiplication could contribute to the CRH property (really not sure, need more research).

[stechu]

@weikengchen Thanks!

[weikengchen]

By the way, the one I think Zcash eventually uses is a more advanced version here: https://github.com/arkworks-rs/crypto-primitives/tree/main/src/crh/bowe_hopwood

It is faster.