javascript creates sometimes invalid signatures

[VzxPLnHqr]

This is a weird one. For some reason this exception is thrown from javascript whereas it is fine for native/jvm. https://github.com/fiatjaf/scoin/blob/master/shared/src/main/scala/Script.scala#L531

I do not have a trimmed down program to reproduce, but it can be done via these steps with my toy "sig-pow" program:

1. clone the repo here https://github.com/VzxPLnHqr/sig-pow
2. switch to the add-scalajs-target branch
3. ./mill -i sigpow.jvm[3.1.3].run (press enter at each prompt to accept the defaults)
4. terminates without throwing an exception which means that the transaction which was generated/signed was valid (at least according to the acinq/scoin verification code).

Now do it again but for javascript:

1. ./mill -i sigpow.js[3.1.3,1.10.1].runNode (after it builds and runs, just press enter at each prompt to accept the defaults)
2. exception might be thrown at the end, but might not be either. Sometimes the sigs it generates are valid, apparently, and sometimes not.

Maybe the underlying javascript library (noble/secp256k1) is not enforcing some bitcoin consensus rules on ecdsa signatures (low s value?) that the jvm/native underlying library (libsecp256k1) does?

[fiatjaf]

Thank you for this report.

[fiatjaf]

I think this commit should fix it, but I am not entirely sure. If you can test it for me and report back that will be amazing.

[VzxPLnHqr]

It may have, but then a exception was thrown pertaining to CryptoPlatform.sign It looks like you are currently requiring CryptoPlatform.sign to return a ByteVector64 but this is problematic for ECDSA sigs since they are not typically 64 bytes in length.

[fiatjaf]

OK, I understand it now. The idea is that the signature returned from .sign() is 64 bytes, in compact format. That is the original API. But to use it in a Bitcoin script you must convert it using compact2der.

I will revert that commit (by which I mean I will remove it and force-push).

[VzxPLnHqr]

Thanks. It is still somewhat strange though because my code was calling scoin.Transaction.signInput which lookcs like it does in fact call Crypto.compact2der.

[fiatjaf]

Then I don't know. If you don't fix this yourself I may try it myself in the near future.

[VzxPLnHqr]

I have been working on it. It seems to, oddly, have to do with the number of signatures generated by the javascript library. The bitcoin transactions that my program generates/signs/verifies can vary from requiring, say, 4 signatures to requiring 16 signatures. It is not a op_checkmultisig transaction but instead is a large transaction that has many individual op_checksig calls.

When the number of signatures is less than 15, the javascript program at least seems to generate valid signatures. However, as soon as I am above 16 signatures, the javascript program somehow ends up creating at least one invalid signature and it fails verification.

The bizarre thing though is that this same issue does not happen on the jvm/native, so it definitely has something to do with how the javascript library generates its signatures.

[VzxPLnHqr]

The jvm, using libsecp256k1, generated the following signatures for the following public keys.

0313fd0f57a343c28b830eccab1dea6bb0a7fd44ed26e63e3c184b2e08bdc0db09 --sig--> 30450221009df0130583b7492f10f82f7816d72e377661a85978ffcab396e3416bb6666495022068f61ee549d43dff548f0626535c661545755d5f7e75f4f32247e8eb4da1ead301
02f7a2d32d03dd521dee02c62c84898932a33812f50c68b62eca880497ccc7747d --sig--> 3045022100bc8d764369929c6aa4c578eac04eb826dab232de297a7aa260780411ab12e70802206e61f021fccebe8c4b7566df62730bdd10c8c77f4d665d5a41fa39976f22d1c701
03ccb895aae25472a03b6989e8958c6f1a64d16df7d8634b129b1b5d2df75e2a41 --sig--> 3045022100aa1a2c1f77e7f5e9f7d9a067ad4c3412d73fab0fcdf72eba10a54d8a7a74121d02203c63fbdbc0d146d39f389eae682ed6bc7c1d9dcd13145c9768712af3d800ce2f01
02ef4b7c8174e5f1e20647d53ac18de0880fd4736976dbbf4d98736eec5bbeed3d --sig--> 3045022100f3908de2448517cc7bb78403116d319335e80f76eeef27b931e74cdb8a0383f702204aee3d152177bd396a24e7850563ddb5ea17273ec946cc3e320c74113358194201
02699710b3cc42db9a5fe2a589565fdc1fd710d7d568cffde6cbb5a1546452129e --sig--> 304402203d4910c64e410c6b1265a9bfafc9c8733bd266ad6ccc174bb807a91a0ca6f12c0220560fd0c53a969b6808152dd3640eecb96a4d4061ab0e221e257a98179fde131001
03cb9686b0cd6e0a2e5e4bbd3204cec54a5eb74887934aa4353556820f8329e52e --sig--> 304402200449e71b3ecc68bbcd8f3f49cee24844ccf721fe16b4b2edf0a8eddc988bf3de02205d880f23e9217b656401d2372fc1204c858cd6debe7fc3dfe79a830c615a36a801
03c2972024e3dd80134f5169b395b84d7a0f65223a18d967b171475667c5af67c5 --sig--> 304502210092d7756b2e472c400d4f1bbde78fe3b663f090ee83977218e839e6a0adbf682f02203916eea61936d952cfaf00b87f8d4b80ebe16a8c5cd5043cebb651cb7356c67101
0214aa8f243bcf6111b157a443b30ba99d65591660d5b34f47de2163d93fa6fe9e --sig--> 3044022041c9d745f08b8829632378f2c9ee9f73abc31750ffb6b0a0c246c4408dcb49c5022034f670501f16d950c7c5776eea79a585d5861d52576aac9c01515f7b8eaa1f2201
021398c1fd987e97669469f66491ecd6d6f8de1a020cc7b029b0757031475f71e2 --sig--> 3045022100c11aae78e3a9601bd6ed6d909cbeb1416e8ce1aee275e981b8a8940e37619ae002202b94cbf8dd9da1aef1850ade5c6ae45dd3ada4b2a8db6aa7792c21f2421531a101
02c06abce22db77d3f4bfc20350db60dc182f68a44d7079666056c84dd3c99dbe1 --sig--> 3045022100fe6e36768e95b8cc0cd307afc228480884969311bdd42ce41f96e902a77358a50220535360d8a4b0f957afe2e15f710a90c2ed3369ac4f9bb59adc73e51822e96e7401
0200f9a57d9ad292143121e66fb98a77b1f595f8ecf0c6d3f553067c0d413a97cb --sig--> 3045022100c647ce439be05fe6c504f0e385a5c0a0e529df3d7af93153ee2e345d5a2f0acc0220732ff89f2f2a4054360f3a008f90d0fd4091a749dc72d8592ab15bfd19a8afe301
031c1cbeb2a14b2723a9581d8808dde768bbd576e689189f64f4af96c53e435e7e --sig--> 304502210096f7c83403009f0695eba9eda6df0002af45721d85d92445cf508fcb8a65fda3022026ff9cc100c43c8cbbc72fc791c0bdd359a6ad421cd80ab47efe64a955db938c01
02d96745b4f023b7a83802b74e640432ed9c5328c796be29d3a63d6d94c1ecf67f --sig--> 304402204936a3e80c7316af0d8c3f25558e0886ccc0d31ef02273531e9c0916441712e902200fffc14bd54cea6da579b0d8d2d139281897621a3096ae66eec720c31dcda1bc01
03e20845a0b9405cb5736ab62d0b530904c7e994b5171f6c19f37ee14aee9907ea --sig--> 3045022100fc536853140f6065974dbaede4e91857a5df51ad707216691ecb41836ec824360220550a871ffd8c8daa96bf47b6543b5d4f643668c9135682e20c6cd7229e3214a701
02f642103ea91b1bd39fe5190828e43af965151207988adcbb631a540b7c14d698 --sig--> 304402204a56443c3291409641dc94024f37983384f9a451f35e53098c41c747f56874ce022066982d4ba48ca0d53bccb832d83918b6033c5a87f81a80fd0f7243d5c9cbad0a01
027ffaae6043e994b57ce7e0e42b52ba5893fb6595e9eb9cc0995cbdeef678296b --sig--> 3045022100e0709e558fb59383d1fc56ed3b07ce7c93e57d8eb33bfb5e6854e54ceb69736002201ec6073a595e81b3e9f48e7cd422509bf443296a100e001d3bff60f7630cf76901

Whereas the javascript run of the same program generated the following:

0313fd0f57a343c28b830eccab1dea6bb0a7fd44ed26e63e3c184b2e08bdc0db09 --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab10022053b8129f7958f3d9f1b576f3e379cd744bffe852936247d23ebcb94e23f250f001
02f7a2d32d03dd521dee02c62c84898932a33812f50c68b62eca880497ccc7747d --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab100220747ff719087870d87f818acb11becdc13ad6de58e2dd7859b45277787207c3d601
03ccb895aae25472a03b6989e8958c6f1a64d16df7d8634b129b1b5d2df75e2a41 --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab1002201c97004c6463595536700d159b8a6ff5705f209063c88abde9aabcde61a221a101
02ef4b7c8174e5f1e20647d53ac18de0880fd4736976dbbf4d98736eec5bbeed3d --sig--> 03044022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab10021f45ea5071719a2599644fb6b7a976a053aa3142b0603d2cc98152af4f1a8f6f201
02699710b3cc42db9a5fe2a589565fdc1fd710d7d568cffde6cbb5a1546452129e --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab1002202fcef7d2a0819629185dd3ff9dd3baf2baa588d4a642df52cef41ae2679435d401
03cb9686b0cd6e0a2e5e4bbd3204cec54a5eb74887934aa4353556820f8329e52e --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab100220116593cafbfcf6b0445326d706a46037c2fc068b73547bcfccc6a02b8761bbda01
03c2972024e3dd80134f5169b395b84d7a0f65223a18d967b171475667c5af67c5 --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab10022026e344ff032b0675b79ade5f6acaf67a4c1bff5485a2c58276e00982c65c6f2d01
0214aa8f243bcf6111b157a443b30ba99d65591660d5b34f47de2163d93fa6fe9e --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab1002201b5563696941150abe3478ad1f28f64b5ea94c012ade56267dbb1217b7c4b46a01
021398c1fd987e97669469f66491ecd6d6f8de1a020cc7b029b0757031475f71e2 --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab100220607945a3b17b83bd8f4a61fb59dfaf58bf52ca82e6593bf6bfd73ff15381b51001
02c06abce22db77d3f4bfc20350db60dc182f68a44d7079666056c84dd3c99dbe1 --sig--> 03045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab100220008e2ec562a43957f90eaed8e403aebbbdcbe3911adb5e17f35555936c0ef76ee01
0200f9a57d9ad292143121e66fb98a77b1f595f8ecf0c6d3f553067c0d413a97cb --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab1002201fcae65e13c4c56df044d8d38682409e4e708b849e67254db8ed185ccdfb1c9a01
031c1cbeb2a14b2723a9581d8808dde768bbd576e689189f64f4af96c53e435e7e --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab100220598eae5d566fd8c30fa4a0140b6d635d37984e1f38888d1249f042d345abeba201
02d96745b4f023b7a83802b74e640432ed9c5328c796be29d3a63d6d94c1ecf67f --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab100220735602d3445181d3228700e123a8826be7cad1f064f115b02937a5632f6d3d6e01
03e20845a0b9405cb5736ab62d0b530904c7e994b5171f6c19f37ee14aee9907ea --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab1002202a2c145befd7e7db27244bcdd62cd161881ecc07d7b4c8e697500b5803e3e7f301
02f642103ea91b1bd39fe5190828e43af965151207988adcbb631a540b7c14d698 --sig--> 03044022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab10021f25efe8868215c1c3446ce30a6108516cf0ead3f1884553c067c8ffdbe4062bd01
027ffaae6043e994b57ce7e0e42b52ba5893fb6595e9eb9cc0995cbdeef678296b --sig--> 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab10022000a5adb254534551e326eb685080d3ae2f96b90415f8ccf53ba2c5ed2d30c7d001

Notice how the first bytes of the javascript signatures are the same. Only a couple of them are different. Whereas (rightly so) the jvm signatures are in fact all quite different from one another.

[VzxPLnHqr]

I wonder if it has to do with how this sha256Sync and hmacSha256Sync are working in javascript. The output above makes me think that maybe the hmac is somehow caching something that we do not want cached.

[fiatjaf]

Interesting.

[VzxPLnHqr]

The monkeypatch code which exposes hmacSha256Sync to javascript is currently:

def hmacSha256Sync(key: Uint8Array, msg: Uint8Array): Uint8Array =
    ByteVector
      .fromValidHex(
        HashJS
          .hmac(HashJS.sha256, ByteVector.view(key).toHex, "hex")
          .update(ByteVector.view(msg).toHex, "hex")
          .digest("hex")
      )
      .toUint8Array

But the docs from https://www.npmjs.com/package/@noble/secp256k1#signmsghash-privatekey seem to indicate it should be like this (javascript):

// signSync counterpart could also be used, you need to set utils.hmacSha256Sync to a function with signature key: Uint8Array, ...messages: Uint8Array[]) => Uint8Array. Example with noble-hashes package:

import { hmac } = from '@noble/hashes/hmac';
import { sha256 } from '@noble/hashes/sha256';
secp256k1.utils.hmacSha256Sync = (key: Uint8Array, ...msgs: Uint8Array[]) => {
  const h = hmac.create(sha256, key);
  msgs.forEach(msg => h.update(msg));
  return h.digest();
};

So, I tried to update the monkeypatch code to be:

  def hmacSha256Sync(key: Uint8Array, msgs: Uint8Array): Uint8Array = {
    val h = HashJS.hmac(HashJS.sha256, ByteVector.view(key).toHex, "hex")
    msgs.foreach(msg => h.update(ByteVector(msg).toHex,"hex"))
    ByteVector.fromValidHex(h.digest("hex")).toUint8Array
  }

It still did not work (in the sense that it still generated the same invalid signatures as before). I wonder if somehow it should return the result of a msgs.fold(..) instead of a msgs.foreach? But what to use as the zero value in the fold?

[VzxPLnHqr]

Ok, after some more investigation. I changed the monkeypatch code to:

  def hmacSha256Sync(key: Uint8Array, msgs: Uint8Array): Uint8Array = {
    val h = HashJS.hmac(HashJS.sha256, ByteVector.view(key).toHex, "hex")
    val result = msgs.foldLeft(h){
      case (accum, msg) => h.update(ByteVector(msg).toHex,"hex")
    }
    ByteVector.fromValidHex(result.digest("hex")).toUint8Array
  }

That at least seems to, most of the time, generate valid signatures. Furthermore, the signatures it generates which are deemed "invalid" by scoin.Script$Runner.checkSignature which is usually called at somepoint by Transaction.correctlySpends(...) all seem to start with a 03 whereas the valid signatures start with 3. For example:

invalid signature: 03044022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab10021f699910e4c0793b95336d5aefa880ac3f3442a04db99f26680bf8b5b0263ba2801
valid signature: 3045022100bf169e19c6cc1762ddeb0c8fbcd46d9e7b3131b8e277bc1e55aa841c6d81ab1002201cf8452d8c280a0e6cc9824a8992d58f6879d2f9f4bccffd6763db7bce8e96d001

So there are at least two things happening here:

1. if these signatures are der encoded (r,s) values, then the r values are somehow being calculated to be the same despite being generated by different private keys. This problem does not happen when the same code runs on jvm.
2. sometimes, for an unknown reason, it is putting an an extra 0 at the beginning. This also does not happen when the same code runs on the jvm.

[fiatjaf]

Now it will work. There are tests, even, and they are passing (wow!) after a little fight against the ScalaJS compiler which ended with this: https://discord.com/channels/632150470000902164/635668814956068864/1011715303056609332

[fiatjaf]

Let me know if it worked for you.

[VzxPLnHqr]

Nice work! I wondered if there was going to be some nuance with scalajs and the hmac function signature needed for the secp256k1 javascript library. The commit you pushed seemed to fix the repeated r value you problem. However, we still have this strange "sometimes a leading 0" in javascript issue.

for same key and message
signature from javascript:
03043021f449e71b3ecc68bbcd8f3f49cee24844ccf721fe16b4b2edf0a8eddc988bf3de02205d880f23e9217b656401d2372fc1204c858cd6debe7fc3dfe79a830c615a36a801
signature
signature from jvm:
304402200449e71b3ecc68bbcd8f3f49cee24844ccf721fe16b4b2edf0a8eddc988bf3de02205d880f23e9217b656401d2372fc1204c858cd6debe7fc3dfe79a830c615a36a801

Notice that the only thing different is the leading zero, and all the other data is the same. Guessing that ByteVector is the culprit here in that it is somehow behaving differently on jvm/js when encoding/decoding hex?

[VzxPLnHqr]

Crypto.signatureToDER ultimately returns a ByteVector which it gets from ByteVector.fromValidHex(hex) and we can see here that val hex = s"30{$length}..." (point being that hex itself obviously starts with 30 as it is supposed to, yet somehow when toHex is called on the resulting signature (a ByteVector), the returned hexstring has a 0 prepended to it (sometimes, not all the time, and only seems to be in javascript, not jvm or native).

https://github.com/fiatjaf/scoin/blob/master/shared/src/main/scala/Crypto.scala#L404

[VzxPLnHqr]

Yes, I think this is an issue with ByteVector. Just confirmed on javascript the following:

raw hex: 3043021f449e71b3ecc68bbcd8f3f49cee24844ccf721fe16b4b2edf0a8eddc988bf3de02205d880f23e9217b656401d2372fc1204c858cd6debe7fc3dfe79a830c615a36a8
ByteVector.fromValidHex(hex).toHex: 03043021f449e71b3ecc68bbcd8f3f49cee24844ccf721fe16b4b2edf0a8eddc988bf3de02205d880f23e9217b656401d2372fc1204c858cd6debe7fc3dfe79a830c615a36a8

The above output was made via a simple cats-effect IOApp:

    val weirdJSissueDemo = for {
         hex <- IO("3043021f449e71b3ecc68bbcd8f3f49cee24844ccf721fe16b4b2edf0a8eddc988bf3de02205d880f23e9217b656401d2372fc1204c858cd6debe7fc3dfe79a830c615a36a8")
         _ <- IO.println(s"raw hex: $hex")
         bv <- IO(ByteVector.fromValidHex(hex))
         _ <- IO.println(s"ByteVector.fromValidHex(hex).toHex: ${bv.toHex}")
    } yield ()

[VzxPLnHqr]

Not sure if this would work, but for signature-related code in scoin on javascript, it looks like the js library expects input as a hex string. So when we have a ByteVector and need to get it to the js library, it looks like right now we are sending such hextring over by calling _.toHex on the ByteVector. I will see what happens if it is changed to _.toHex.dropWhile(_ == '0'). Maybe that will fix it?

[VzxPLnHqr]

I do not know much about DER, but I wonder if the issue is that in Crypto.signatureToDER the value val hex = s"30${length}02${rLen}${rHex}02${sLen}${sHex}" seems to, sometimes, be of a size which is not even. So I think that is actually the problem because it is fed into ByteVector.fromValidHex (but it is not actually valid hex).

[fiatjaf]

OK, now this is an error elsewhere, on the DER encoding specifically, right? Let me take a look.

[fiatjaf]

Nice, my code for signatureToDER is what is broken, very likely, it was ported from @noble/secp256k1 to Scala by my own hands and never tested.

[VzxPLnHqr]

OK, now this is an error elsewhere, on the DER encoding specifically, right? Let me take a look.

Yes, if you put something like:

def signatureToDER(...) {
... 
 require(hex.size % 2 == 0, "INVALID HEXSTRING of odd length")
ByteVector.fromValidHex(hex)
}

and then feed it the following, it will fail the require and throw an exception.

      val r = BigInt("1939826268000007359143909510553084398066457921122334221326722093796335285214")
      val s = BigInt("42305490613398507257462290570133199576497244294403847577481978090143620937384")
      val sig = Crypto.signatureToDER(r,s)

but if you feed it:

      val r = BigInt("27720179373560178646241075848627520324989088086870667600053818420475967500588")
      val s = BigInt("38926848564652280097082943871331288670328626516021751159001707213882054808336")
      val sig = Crypto.signatureToDER(r,s)

it will pass.

[VzxPLnHqr]

Nice, my code for signatureToDER is what is broken, very likely, it was ported from @noble/secp256k1 to Scala by my own hands and never tested.

Ok, glad we got to the bottom of it then!

[fiatjaf]

We didn't get to the bottom of anything, my code seems to be correct!

[VzxPLnHqr]

It looks like the DER encoding has to start with 30 always, so is libsecp256k1 wrong here? This makes no sense.

Agreed. I am so confused!

We didn't get to the bottom of anything, my code seems to be correct!

But val hex = ... sometimes is of odd length, so it cannot be correct, right?

[fiatjaf]

I took a long time to understand what you were saying.

[VzxPLnHqr]

Just tested it....success! Nice work! Now I think we can safely say that we got to the bottom of it.

[fiatjaf]

Awesome, thank you!

That is great to hear because I had a dream in which I had forgotten to replace the toPaddedHex function name in one place and everything was breaking because of that but I couldn't find because I only had access to the GitHub interface and not my editor.