Fix generating wrong e value when the message bytes start with "00" byte

[rantan]

This PR fixes issue #35

The sha256 hash function which is used in schnorr signature generation receives inputs as BigInt value. But the BigInt value eliminate head bytes if it is zero. So that, the output of hash function was wrong. This commit changes the message into BigInt array for each byte of the message.

It also include changing zilliqa part. But i don't know much about zilliqa, so I wonder if it is ok.🤔

P.S.

BIP-340 computes e from x coordinate of R and P at present. I think that this change should be applied to not only message but also R and P when updating this library to latest bitcoin schnorr specification.

I'm wondering if there are something i don't know... but I thought current create_hash signature such as receiving reference of BigInt slice is not good so much because it leads kind of this issue.

Thank you for your support 😄 @omershlo .

[omershlo]

awesome work, I have some concrete review (sha2 should be a dev dependency, compute_e should be done once in mod.rs and so on) but after seeing your code I think we should go with the other option of using sha2 directly. In fact I think we should add this interface to curv: https://github.com/KZen-networks/curv/blob/master/src/cryptographic_primitives/hashing/hash_sha256.rs#L20 The new function will accept vectors (or a matrix, or a vector) and output a bigint (and will use sha2 internally). Afterwards we can use this function here.

I am ok with doing it myself, but please let me know what you think and if you still into doing it yourself?

[rantan]

Thank you for your consideration!

I want to suggest one more addition for the signature. I think it is better to make it returns Vec<u8> not BigInt. Because it is easier for when a user want to get byte vector. If it returns BigInt, the user need to pad by 0. For example, someone want to compute bitcoin block hash. As you know, It always starts with a lot of "00".

I want to leave it to you. Thank you for asking.

[rantan]

@omershlo Hi, I updated this PR. Could you check the changes, please?

[omershlo]

Can you use the same new primitive that is used here: https://github.com/KZen-networks/multi-party-schnorr/commit/8a3e0a11ff9d4e06dbf42d28fac20df8b50bfa71

[rantan]

You mean it should use below way which using BigInt to create slice for the hash function?

        let message_len_bits = message.len() * 8;
        let R = local_ephemeral_key.y.bytes_compressed_to_big_int();
        let X = local_private_key.y.bytes_compressed_to_big_int();
        let X_vec = BigInt::to_vec(&X);
        let X_vec_len_bits = X_vec.len() * 8;
        let e_bn = HSha256::create_hash_from_slice(
            &BigInt::to_vec(
                &((((R << X_vec_len_bits) + X) << message_len_bits) + BigInt::from(message)),
            )[..],
        );

I don't know what is better point of this approach than current PR's way. Would you tell me the good points?

[omershlo]

sure, the main reason I prefer my method is because it fixes the problem at its root. - at the lower level library. Your code create a function compute_e that should be created each time differently for different argument - so I cannot take it and use it elsewhere without defining it again. This is a source for a lot of trouble in my opinion.

[rantan]

Thanks, you wonder about extracting compute_e function, right?

Your code create a function compute_e that should be created each time differently for different argument - so I cannot take it and use it elsewhere without defining it again.

I agree this. I prefer code for computation of e should be in each protocol file like bitcoin_schnorr.rs and zilliqa_schnorr.rs. The reason of putting it in new util module is you said "compute_e should be done once in mod.rs" above comment.

However I think that parts of compute e in same protocol can share the code because it should be same way to compute e.

So that, how about getting compute_e function back into each protocol file?

--

The most important point for me is never use BigInt for to create input data into hash function, because if some value starts with "00" bytes, it will get eliminated and the final input will be wrong. If use BigInt, it needs to treat original length of each value such a way as 8a3e0a1 and this way is a bit complicated.

p.s. I'm little wandering if my understanding for your comment is correct..if not, tell me please.

[omershlo]

This is not exactly what I meant, I apologise for the confusion. What I meant was that as a rule we should try and make much as possible code re-use. This is why I suggested moving compute_e to mod.rs and this is why I prefer the solution of https://github.com/KZen-networks/multi-party-schnorr/commit/8a3e0a11ff9d4e06dbf42d28fac20df8b50bfa71 because you can use the same low level function anywhere you want

[rantan]

No problem. Thank you for explanation of your policy. I understand.

So that, how about getting compute_e function back into each protocol file?

So, what do you think about this suggestion? Can i go ahead? or do you prefer never create compute_e() function?

[omershlo]

I prefer to never create the compute_e function. But I acknowledge that this is a good and valid solution. I have no strong objection and it might be that in the future we will use it so good think that you created this

[rantan]

Ok, i will go ahead.

By this changes, there are two same implementation for computing e. But it is temporary. I think bitcoin_schnorr.rs's one should be changed for to adapt BIP-340 sometime in future.

[omershlo]

Adapting to bip340 is really important. Can you elaborate what changes must be done to support it?

[rantan]

I can show 2 points which should be adapted.

1. Compute e from only x coordinate of two public key. current implementation includes prefix which represents y coordinate.
2. Decide k such a way as y coordinate of R to be a quadratic residue modulo p.

These might not exhaustive. It's just on my current understanding.