EDIT: This question is not specific to Bitcoin. It's applicable to any other crypto currency that is interested in using a different signature scheme than Bitcoin or the QT reference client. One reason for this is to reduce complexity (and bugs) in the protocol.

My understanding of malleable transactions in Bitcoin is that two different values are supported for "S" when a signature is validated.

The solution for this is to ensure that S is less than the following

  X9ECParameters ecParams = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");

  HALF_CURVE_ORDER = ecParams.N.ShiftRight(1);

Given the plethora of signature mechanisms available to crypto-currency, what algorithms or signature approaches are not vulnerable to Malleable Transactions?

e.g. What if...

  • A different curve was selected instead of secp256k1?
  • A different signature mechanism was chosen?
  • A different approach entirely, such as a blind HMAC was used to sign transactions?

I'm interested in answers that describe both solutions that are broken, and those that would prevent malleable transactions from ever occurring.

My goal is to flush out an algorithm that produces consistent results with minimal complexity for implementors. (in other words, even Mt Gox would get it right)

  • possible duplicate of Is this "transaction malleability" really an issue? – John T Feb 11 '14 at 23:56
  • @JacobTorba Not a duplicate, I'm asking if a signature format exists that doesn't have this issue. I'm aware of all the answers of that question, and none relate. Perhaps you can help me clarify? – halfbit Feb 12 '14 at 0:32
  • you're right! This is a legitimate question with a tricky title, my bad. – John T Feb 12 '14 at 0:35
  • I think you are having trouble with the way hashing works, it's not so that sha256 hashing causes the multiple values, it's all about what is fed into the hash function. Could you be talking about avoiding collisions? Theres an extremely small chance for those. – John T Feb 12 '14 at 0:38
  • My focus is specifically on two public keys that can generate the same signature. The change in signature results in a different sha256 hash (of course). I'm focused primarily on the S value of the signature being less than half of the curve order as defined by this e.g. HALF_CURVE_ORDER = ecParams.N.ShiftRight(1); – halfbit Feb 12 '14 at 0:57

The solution is the same regardless of curve or signature algorithm -- reject non-canonical signatures. This is precisely what Bitcoin has decided to do.

  • This answer doesn't apply to my question. Is there a signature format, or encryption type that makes it impossible to have multiple values for a signature. Can you help me rephrase...? – halfbit Feb 12 '14 at 0:31
  • I think the answer is "yes, a canonical signature format makes it impossible to have multiple values for a signature". The software just needs to reject non-canonical signatures. – Greg Hewgill Feb 12 '14 at 1:29
  • 1
    @makerofthings7 Any scheme, provided non-canonical signatures are rejected. – David Schwartz Feb 12 '14 at 4:59
  • understood, but I'm looking at cryptocurrencies in general, not specific to Bitcoin, that may allow or promote signature schemes that don't require the implementation detail of ensuring canonical signatures. (hence the comment "even Mt Gox would get it right). What crypto approach would eliminate this need (outside of Bitcoin and QT reference client) – halfbit Feb 12 '14 at 5:03
  • 4
    That has nothing to do with the algorithm, that has to do with how you choose to represent the signatures. For example, say a signature algorithm produced a signature of seventeen. Regardless of the algorithm if you treat "017" as equivalent to "17", then you have more than one way to represent the signature. It has nothing to do with the crypto algorithm but with the rules you use for validating the representations of signatures. If the representation validity rules provide one and only one way to represent any given signature, you are good. If not, not. – David Schwartz Feb 12 '14 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.