Fix #66 `reverse_k` signature digest

[blocksurf]

• Adds DigestAction enum to handle the byte order of the k_digest and msg_scalar during ECDSA sign/verify
• SighashSignature::from_der_impl now checks the sig length before attempting to remove the sighash byte
• checksig and multisig will verify the reverse digest if verify_tx_signature fails the first time. This guarantees that the interpreter can validate signatures regardless of the byte order used for the digest

[blocksurf]

The most recent commit adds reverse_k flags where necessary. It also updates the signatures in tests/sighash.rs

All of the tests pass again but there are still two outstanding issues

Signature verification

Signatures produced with a reversed digest still can't be verified by their signer because the function called by ECDSA::verify_digest_impl here assumes our scalars will always be big endian

Interpreter

The multisig tests in tests/interpreter_signatures.rs failed unless I switched the order of the private keys. I'm not sure what broke. Still debugging this

[blocksurf]

Fixed the outstanding issues in ecdsa/verify.rs & interpreter/script_matching.rs

[Firaenix]

I do like this PR, while I do have some concerns about the changes to the API for backwards compatibility's sake, I dont mind adding another flag to the already low level ECDSA functions.

What about instead of adding a reverse_k boolean to the function signature, you create a new enum and do something like

Option where DigestOptions is an enum such as

DigestOptions::ReverseK DigestOptions::ReverseDigest DigestOptions::ReverseKAndDigest

This way you can tweak the ECDSA method as you need but if you pass None to the function call, it acts as it does currently and is thus at least functionally backwards compatible?

[blocksurf]

I do like this PR, while I do have some concerns about the changes to the API for backwards compatibility's sake, I dont mind adding another flag to the already low level ECDSA functions.

Totally agree this should all be opt-in. I added a DigestAction enum for the underlying impls and restored most of the functions back to their current form

These two function will still need flags though since their impls are pub(crate)

• Transaction::sign
• ECDSA::verify_digest

I went ahead & implemented them as you suggested

if you pass None to the function call, it acts as it does currently

ECDSA::verify_digest

reverse_digest: Option<bool>

Default value for None:

reverse_digest.unwrap_or(false)

Transaction::sign

digest_action: Option<DigestAction>

Default value for None:

digest_action.unwrap_or(DigestAction::ReverseK)

But if you want to avoid making changes to the existing function signatures we could do this instead:

• Create a separate Transaction::sign_legacy method that accepts Option<DigestAction>
• Make ECDSA::verify_digest_impl public

What do you think?

[Firaenix]

Hmm that's an interesting option to add new functions. If we do go that route, I do have a request that kind of adds some scope but @deanmlittle brought up with me during some quick discussions.

He mentioned instead of the library reversing anything, you should be passing digests in already formatted how you need them to be. Do you think it would be worth adding a new function to handle that case?

@deanmlittle did I explain what you had in mind accurately enough?

[blocksurf]

I like the idea of handling digests outside the library. Would you like to keep the existing functions unchanged & add new functions that accept the digest directly?

How would we handle functions that call pub(crate) methods internally? Transaction::sign needs to generate the preimage before signing, the return type SighashSignature has private fields, etc.

As for the digests I think a good option would be to implement them as an associated trait type of vecs & slices. Something like this

pub trait ToDigest {
    type HashDigest: digest::FixedOutput<OutputSize = digest::consts::U32>
        + digest::BlockInput
        + Clone
        + Default
        + digest::Reset
        + digest::Update
        + FixedOutput
        + ReversibleDigest;

    fn to_digest(&self, hash_algo: SigningHash, reverse: bool) -> Self::HashDigest;
}

impl<T> ToDigest for T
where
    T: AsRef<[u8]>,
{
    type HashDigest = Sha256r;

    fn to_digest(&self, hash_algo: SigningHash, reverse: bool) -> Self::HashDigest {
        let d = match hash_algo {
            SigningHash::Sha256 => Digest::chain(Self::HashDigest::default(), self.as_ref()),
            SigningHash::Sha256d => Digest::chain(Self::HashDigest::default(), Self::HashDigest::digest(self.as_ref())),
        };

        match reverse {
            true => d.reverse(),
            false => d,
        }
    }
}

Then you could just go

let message = b"Hello";
let digest = message.to_digest(SigningHash::Sha256d, true);

[Firaenix]

I do really like your trait idea. Not sure how that would work in Javascript but worth playing around with.

I think lets go with a fresh function call for externally created digests, we can figure out what to do with the other functions later based on usage.

Thanks again for your input!