feat: expose the recover() function

[motorina0]

Summary

Exposing the recover() function allows other libraries (like bitcoinjs-message and bolt11) to use tiny-secp256k1 (instead of secp256k1).

Details in this issue: https://github.com/bitcoinjs/tiny-secp256k1/issues/68

Test Plan

• [x] unit tests for the valid cases
• [x] unit tests for the invalid cases
  • [x] update README

Screenshots

Further Comments

Benchmark

====================================================================================================
Benchmarking function: recover
----------------------------------------------------------------------------------------------------
tiny-secp256k1 (WASM): 424.34 us/op (2356.61 op/s), ±4.35 %
====================================================================================================

[junderw]

Perhaps create a type alias for recid and export it.

Also, I wonder how this affects WASM binary size.

Needs some more tests, but overall LGTM.

[junderw]

Adds about 2.7kB to the WASM binary size. Pretty reasonable. Deal with the above comments and I'll publish a new minor version.

It might take a couple weeks for me to publish since I have some personal issues I am taking care of.

[junderw]

https://github.com/bitcoin-core/secp256k1/blob/aa5d34a8fe99b1f69306be20819f337dbd3283db/src/modules/recovery/main_impl.h#L87-L121

Looks like 0 is returned for a lot of input errors as well... perhaps we should validate for them and only return null for the infinity case (at the very end)

1. Check R and S of signature are not zero (done)
2. Check that if recid & 2 (second bit) is set, r should be less than p - order (not done)
3. Check that r (or r + order if second bit set) is a valid X value (just add a 0x02 at the beginning and use isPoint())

These should all throw errors.

If 0 comes back from these, it is the infinity point and should be null.

[motorina0]

2. Check that if recid & 2 (second bit) is set, r should be less than p - order (not done)
3. Check that r (or r + order if second bit set) is a valid X value (just add a 0x02 at the beginning and use isPoint())

My monkey-see-monkey-do skills in regards to Rust have reached the limit. Unfortunately I cannot commit to the above two points. Would anyone like to help...?

[junderw]

2 and 3 can be done with JS before calling into WASM.

[junderw]

P-N is

>>> hex(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F - 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
'0x14551231950b75fc4402da1722fc9baee'

> Array.from(Buffer.from('000000000000000000000000000000014551231950b75fc4402da1722fc9baee','hex'))
[
    0,  0,   0,   0,   0,   0,  0,  0,   0,
    0,  0,   0,   0,   0,   0,  1, 69,  81,
   35, 25,  80, 183,  95, 196, 64, 45, 161,
  114, 47, 201, 186, 238
]

So you can just add this to the validate TS file as a const for comparing the r value of the signature when recid & 2 !== 0

[motorina0]

Check R and S of signature are not zero (done)

• [x] it was not throwing an error, added custom validation Check that if recid & 2 (second bit) is set, r should be less than p - order (not done)
• [x] done Check that r (or r + order if second bit set) is a valid X value (just add a 0x02 at the beginning and use isPoint())
• [x] used isXOnlyPoint() instead
• passed a callback to validate. validate is the only place where exceptions are thrown

• [x] add invalid data unit tests
• [x] update README

[junderw]

looks good so far.

r > p-n when recid & 2 seems like it should be a "bad recid" problem...

Since the recid second bit only exists to tell which value r is (r or r+n) when below p-n. But the signature is not... so recid is incorrect most likely.

[junderw]

also, new rust version added a new lint.

just swap with the suggestion in the error.

[motorina0]

it should be a "bad recid" problem...

• [x] done. The error message is succinct (Bad Recovery Id), like for the other errors lint error
• [x] fixed

[junderw]

Needs to update the README

also, we need a method for signing and retrieving the recid. (we need it for signing bolt11 invoices.

LGTM so far.

[motorina0]

• [x] add signRecoverable() function
• [x] updated README
• [x] update unit tests

[junderw]

Adding the signRecoverable method only added about 800B to the wasm binary. I was thinking maybe we could make it more efficient by joining sign and signRecoverable to some helper method, but it looks like the secp256k1 functions already are using the same code.

I'm going to leave this up for a few days before merging.

LGTM

@fanatid If you have any comments I'd appreciate it.

[junderw]

@motorina0 I invited you to the bitcoinjs organization

[junderw]

Validation for private will prevent the only cases where 0 will return from the C function. So all null cases will result in Throws before returning. So it is ok to assume null is impossible.

Your branch wasn't open to fixes, so I will paste a diff:

diff --git a/README.md b/README.md
index f8ad9fd..16e8489 100644
--- a/README.md
+++ b/README.md
@@ -212,6 +212,18 @@ Returns `null` if result is equal to `0`.
 - `Expected Private` if `!isPrivate(d)`
 - `Expected Tweak` if `tweak` is not in `[0...order - 1]`

+### privateNegate (d)
+
+```haskell
+privateNegate :: Buffer -> Buffer
+```
+
+Returns the negation of d on the order n (`n - d`)
+
+##### Throws:
+
+- `Expected Private` if `!isPrivate(d)`
+
 ### xOnlyPointAddTweak (p, tweak)

 ```haskell
diff --git a/src/lib.rs b/src/lib.rs
index 80046f0..5eb9ab6 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -421,14 +421,12 @@ pub extern "C" fn private_sub() -> i32 {
 #[allow(clippy::missing_panics_doc)]
 #[no_mangle]
 #[export_name = "privateNegate"]
-pub extern "C" fn private_key_negate() -> i32 {
+pub extern "C" fn private_negate() {
     unsafe {
-        if secp256k1_ec_seckey_negate(secp256k1_context_no_precomp, PRIVATE_INPUT.as_mut_ptr()) == 1
-        {
+        assert_eq!(
+            secp256k1_ec_seckey_negate(secp256k1_context_no_precomp, PRIVATE_INPUT.as_mut_ptr()),
             1
-        } else {
-            0
-        }
+        );
     }
 }

diff --git a/src_ts/index.ts b/src_ts/index.ts
index 94e1103..1374ba8 100644
--- a/src_ts/index.ts
+++ b/src_ts/index.ts
@@ -244,14 +244,13 @@ export function privateSub(
   }
 }

-export function privateNegate(d: Uint8Array): Uint8Array | null {
+export function privateNegate(d: Uint8Array): Uint8Array {
   validate.validatePrivate(d);

   try {
     PRIVATE_KEY_INPUT.set(d);
-    return wasm.privateNegate() === 1
-      ? PRIVATE_KEY_INPUT.slice(0, validate.PRIVATE_KEY_SIZE)
-      : null;
+    wasm.privateNegate();
+    return PRIVATE_KEY_INPUT.slice(0, validate.PRIVATE_KEY_SIZE);
   } finally {
     PRIVATE_KEY_INPUT.fill(0);
   }
diff --git a/src_ts/wasm_loader.ts b/src_ts/wasm_loader.ts
index e967e31..8706d82 100644
--- a/src_ts/wasm_loader.ts
+++ b/src_ts/wasm_loader.ts
@@ -48,7 +48,7 @@ interface Secp256k1WASM {
   pointMultiply: (p: number, outputlen: number) => number;
   privateAdd: () => number;
   privateSub: () => number;
-  privateNegate: () => number;
+  privateNegate: () => void;
   sign: (e: number) => void;
   signRecoverable: (e: number) => 0 | 1 | 2 | 3;
   signSchnorr: (e: number) => void;

[motorina0]

Your branch wasn't open to fixes, so I will paste a diff

Thanks!

• git apply ...
• changes pushed