Sipa's secp256k1 for .NET!

[joshlang]

https://github.com/joshlang/Secp256k1.NET - A managed (.NET) wrapper around Sipa's secp256k1 implementation.

I only threw it together a bit more than an hour ago, so obviously I haven't thoroughly tested it  But so far I've verified blocks up to 77700 with it and its working just fine.  78100 now.  78200!  ...Geez it's fast  SIPA = INCREDIBLE.

If anyone finds any issues or has questions, feel free to get in touch.


EDIT:  HOLY MOLY.  100,000 VERIFICATIONS in 9.8 SECONDS!
EDIT AGAIN:  ...ON A SINGLE PROCESSOR!(@!1(&!(!(@!$(&#@!%
EDIT ONCE MORE: ...Doh, I think it caches results.  That test was verifying the same signature over and over again.  On the blockchain, signature verifications are taking about 10ms on average.  Still 100x faster than Bouncy.
EDIT FOR LIFE LIBERTY AND HAPPINESS:  Without a debugger attached, I'm easily getting <1ms per verification with Sipa

[TierNolan]

Still 100x faster than Bouncy.

Bouncy castle is taking 1 second per signature?

[joshlang]

Yeah - ...Sorta   To be fair, it ranged from 200-1100ms on bouncy. 

[TierNolan]

Yeah - ...Sorta   To be fair, it ranged from 200-1100ms on bouncy. 

Wow, that is pretty slow. 

[Remember remember the 5th of November]

Well what did you expect? Bouncy castle is written in Java, which is compiled to bytecode and interpreted by the JVM or Dalvik VM. Sipa's implementation is in C, with hand-tuned assembly for speed it is executed directly on the CPU.

[joshlang]

Pssh.  It was .NET bouncy not Java

PS there's no "interpreting" going on after being compiled.  Don't bash on JIT compilers   C# = Savior of the uniprogrammiverse!

But true, there's definitely no beating a hand-tuned optimized C/assembly implementation of anything!

[etotheipi]

But true, there's definitely no beating a hand-tuned optimized C/assembly implementation of anything!

I should add, this isn't just a hand-tuned, optimized implementation of general ECDSA signature verification:  it's hand-tuned and optimized for the specific elliptic curve that Bitcoin uses (secp256k1).  The curve is actually one of the simpler ones blessed by NIST, and sipa is an optimization ninja  

[joshlang]

But true, there's definitely no beating a hand-tuned optimized C/assembly implementation of anything!

I should add, this isn't just a hand-tuned, optimized implementation of general ECDSA signature verification:  it's hand-tuned and optimized for the specific elliptic curve that Bitcoin uses (secp256k1).  The curve is actually one of the simpler ones blessed by NIST, and sipa is an optimization ninja  

People who actually understand cryptology are like the evil chess grandmaster james bond villains.

[Remember remember the 5th of November]

But true, there's definitely no beating a hand-tuned optimized C/assembly implementation of anything!

I should add, this isn't just a hand-tuned, optimized implementation of general ECDSA signature verification:  it's hand-tuned and optimized for the specific elliptic curve that Bitcoin uses (secp256k1).  The curve is actually one of the simpler ones blessed by NIST, and sipa is an optimization ninja  

People who actually understand cryptology are like the evil chess grandmaster james bond villains.

Isn't cryptology different than cryptography?

[joshlang]

Isn't cryptology different than cryptography?

Only when you take the SHA256 hash of it.

[MatthewLM]

Has anyone attempted a GPU implementation of signature verification?

[TierNolan]

Has anyone attempted a GPU implementation of signature verification?

That is interesting. 

GPUs require everything to run in lock step, so maybe it wouldn't work.

You would probably need to generate a large number of signatures to verify and then send them all to the kernel.

hash of message (32 bytes)
signature (64 bytes)
public key (33 bytes)

These could then be put in large arrays and each processed in parallel.

The vanity pool GPU code should have an elliptic curve engine, I assume.  It has the advantage that the curve calculations can be computed.

However, I doubt that memory bandwidth to the GPU would be the limiting factor.

[riplin]

Should anyone care, I use the following. Saves you from needing a managed C++ project:

Code:

public static class ECDSA
{

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_start", CallingConvention = CallingConvention.Cdecl)]
        private static extern void StartCrypto();

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_stop", CallingConvention = CallingConvention.Cdecl)]
        private static extern void StopCrypto();

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_verify", CallingConvention = CallingConvention.Cdecl)]
        public static extern int VerifySignature(byte[] msg, int msglen, byte[] sig, int siglen, byte[] pubkey, int pubkeylen);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_sign", CallingConvention = CallingConvention.Cdecl)]
        public static extern int SignMessage(byte[] msg, int msglen, byte[] sig, ref int siglen, byte[] seckey, ref int nonce);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_sign_compact", CallingConvention = CallingConvention.Cdecl)]
        public static extern int SignCompact(byte[] msg, int msglen, byte[] sig64, byte[] seckey, ref int nonce, ref int recid);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_recover_compact", CallingConvention = CallingConvention.Cdecl)]
        public static extern int RecoverCompact(byte[] msg, int msglen, byte[] sig64, byte[] pubkey, ref int pubkeylen, int compressed, int recid);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_seckey_verify", CallingConvention = CallingConvention.Cdecl)]
        public static extern int VerifySecretKey(byte[] seckey);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_pubkey_verify", CallingConvention = CallingConvention.Cdecl)]
        public static extern int VerifyPublicKey(byte[] pubkey, int pubkeylen);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_pubkey_create", CallingConvention = CallingConvention.Cdecl)]
        public static extern int PublicKeyFromSecretKey(byte[] pubkey, ref int pubkeylen, byte[] seckey, int compressed);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_pubkey_decompress", CallingConvention = CallingConvention.Cdecl)]
        public static extern int DecompressPublicKey(byte[] pubkey, ref int pubkeylen);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_pubkey_compress", CallingConvention = CallingConvention.Cdecl)]
        public static extern int CompressPublicKey(byte[] pubkey, ref int pubkeylen);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_privkey_export", CallingConvention = CallingConvention.Cdecl)]
        public static extern int ExportPrivateKey(byte[] seckey, byte[] privkey, ref int privkeylen, int compressed);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_privkey_import", CallingConvention = CallingConvention.Cdecl)]
        public static extern int ImportPrivateKey(byte[] seckey, byte[] privkey, int privkeylen);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_privkey_tweak_add", CallingConvention = CallingConvention.Cdecl)]
        public static extern int PrivateKeyTweakAdd(byte[] seckey, byte[] tweak);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_pubkey_tweak_add", CallingConvention = CallingConvention.Cdecl)]
        public static extern int PublicKeyTweakAdd(byte[] pubkey, int pubkeylen, byte[] tweak);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_privkey_tweak_mul", CallingConvention = CallingConvention.Cdecl)]
        public static extern int PrivateKeyTweakMul(byte[] seckey, byte[] tweak);

        [DllImport("secp256k1.dll", EntryPoint = "secp256k1_ecdsa_pubkey_tweak_mul", CallingConvention = CallingConvention.Cdecl)]
        public static extern int PublicKeyTweakMul(byte[] pubkey, int pubkeylen, byte[] tweak);

}

It's probably a little bit slower when signing a transaction because of the pinvokes when looping to find a correct nonce, but other than that, it's pure C# instead of managed C++.


Edit: actually, now that I looked at the code a bit closer, this is just as fast, if not faster than the managed C++ version, since it's calling managed and unmanaged code in the loop, so it needs to do a pinvoke in the loop too.

Managed C++ is a fickle beast, you never know where it goes managed or native (those transitions are murder). At least with the code above, you know for certain when it happens.

[DeathAndTaxes]

Nice one. 

[joshlang]

Should anyone care, I use the following. Saves you from needing a managed C++ project:

Code:

...

It's probably a little bit slower when signing a transaction because of the pinvokes when looping to find a correct nonce, but other than that, it's pure C# instead of managed C++.


Edit: actually, now that I looked at the code a bit closer, this is just as fast, if not faster than the managed C++ version, since it's calling managed and unmanaged code in the loop, so it needs to do a pinvoke in the loop too.

Managed C++ is a fickle beast, you never know where it goes managed or native (those transitions are murder). At least with the code above, you know for certain when it happens.

Every call into one of the C++ methods I provided does 1 native call, so there's 1 transition per call.... unless you count a call into the RNG.  Same with the p/invoke code you posted. 

Your p/invoke is awesome   It'll work just as good as my library.  Just be careful.  I made the C++ library so that I could write "guard" code around the calls.  ie: make sure keys/signatures/messages are the right length (if not, they cause access violations), handle the nonce so I don't screw it up elsewhere, etc. If you don't need all that junk, then cool

[riplin]

Every call into one of the C++ methods I provided does 1 native call, so there's 1 transition per call.... unless you count a call into the RNG.  Same with the p/invoke code you posted. 

Your p/invoke is awesome   It'll work just as good as my library.  Just be careful.  I made the C++ library so that I could write "guard" code around the calls.  ie: make sure keys/signatures/messages are the right length (if not, they cause access violations), handle the nonce so I don't screw it up elsewhere, etc. If you don't need all that junk, then cool

No guards, no nothing, that's correct. but you could write a nice little C# wrapper for it.

Just for the fun of it, would you mind running your .dll through reflector to get a peek at the generated code?

[joshlang]

No guards, no nothing, that's correct. but you could write a nice little C# wrapper for it.

Just for the fun of it, would you mind running your .dll through reflector to get a peek at the generated code?

Sure, but why me?

Ok, I used ILSpy.

Here's Sign(..)

Code:

/// <summary>Signs a message and returns the signature.  Returns null on failure.</summary>
/// <param name="message">The message to sign.  This data is not hashed.  For use with bitcoins, you probably want to double-SHA256 hash this before calling this method.</param>
/// <param name="privateKey">The private key to use to sign the message.</param>
public unsafe static byte[] Sign(byte[] message, byte[] privateKey)
{
	if (message == null || privateKey == null)
	{
		throw new ArgumentNullException();
	}
	if (privateKey.Length != 32)
	{
		throw new ArgumentOutOfRangeException(Signatures.PrivateKeyLengthError);
	}
	if (message.Length != 32)
	{
		throw new ArgumentOutOfRangeException(Signatures.MessageLengthError);
	}
	int messageptr_3D_cp_1 = 0;
	int keyptr_46_cp_1 = 0;
	byte[] nonce = new byte[32];
	byte[] nonceptr_59_cp_0 = nonce;
	int nonceptr_59_cp_1 = 0;
	byte[] signature = new byte[72];
	byte[] signatureptr_6A_cp_0 = signature;
	int signatureptr_6A_cp_1 = 0;
	int signaturelen = signature.Length;
	byte[] privateKey2;
	for (int x = 0; x < 1000; x++)
	{
		Signatures.Randoms.Value.GetBytes(nonce);
		int result = <Module>.secp256k1_ecdsa_sign((byte*)(&message[messageptr_3D_cp_1]), message.Length, ref signatureptr_6A_cp_0[signatureptr_6A_cp_1], &signaturelen, (byte*)(&privateKey[keyptr_46_cp_1]), ref nonceptr_59_cp_0[nonceptr_59_cp_1]);
		if (result == 1)
		{
			if (signaturelen == signature.Length)
			{
				privateKey2 = signature;
			}
			else
			{
				byte[] smallsignature = new byte[signaturelen];
				Array.Copy(signature, 0, smallsignature, 0, signaturelen);
				privateKey2 = smallsignature;
			}
			return privateKey2;
		}
	}
	privateKey2 = null;
	return privateKey2;
}

And here's Verify

Code:

/// <summary>Verifies that a signature is valid.</summary>
/// <param name="message">The message to verify.  This data is not hashed.  For use with bitcoins, you probably want to double-SHA256 hash this before calling this method.</param>
/// <param name="signature">The signature to test for validity. This must not be a compact key (Use RecoverKeyFromCompact instead).</param>
/// <param name="publicKey">The public key used to create the signature.</param>
public unsafe static Signatures.VerifyResult Verify(byte[] message, byte[] signature, byte[] publicKey)
{
	if (message == null || signature == null || publicKey == null)
	{
		throw new ArgumentNullException();
	}
	if (message.Length != 32)
	{
		throw new ArgumentOutOfRangeException(Signatures.MessageLengthError);
	}
	int messageptr_27_cp_1 = 0;
	int signatureptr_30_cp_1 = 0;
	int keyptr_39_cp_1 = 0;
	int result = <Module>.secp256k1_ecdsa_verify((byte*)(&message[messageptr_27_cp_1]), message.Length, (byte*)(&signature[signatureptr_30_cp_1]), signature.Length, (byte*)(&publicKey[keyptr_39_cp_1]), publicKey.Length);
	int signature2 = result;
	Signatures.VerifyResult message2;
	if (signature2 != -2)
	{
		if (signature2 != -1)
		{
			if (signature2 != 0)
			{
				if (signature2 != 1)
				{
					message2 = Signatures.VerifyResult.Error;
				}
				else
				{
					message2 = Signatures.VerifyResult.Verified;
				}
			}
			else
			{
				message2 = Signatures.VerifyResult.SignatureFailed;
			}
		}
		else
		{
			message2 = Signatures.VerifyResult.InvalidPublicKey;
		}
	}
	else
	{
		message2 = Signatures.VerifyResult.InvalidSignature;
	}
	return message2;
}

[riplin]

No guards, no nothing, that's correct. but you could write a nice little C# wrapper for it.

Just for the fun of it, would you mind running your .dll through reflector to get a peek at the generated code?

Sure, but why me?

Ok, I used ILSpy.

I didn't have your code compiled and I'm on vacation, so don't have all my tools handy. But looks like single pinvokes per call. So it's all good.