Add extmod for secp256k1-zkp

[real-or-random]

This includes the https://github.com/ElementsProject/secp256k1-zkp library (which is a fork from sipa/secp256k1 used in Bitcoin Core) and uses it for signing transactions and signing and verifying messages for ECDSA on the secp256k1 curve.

The Ethereum app is left untouched. I assume because they use Keccak-256 as a message digest and not SHA256. @apoelstra

This is the first step towards solving #282.

Some background to understand the open issues below: secp256k1-zkp (and in fact sipa/secp256k1) relies on two precomputation tables to speed up signing and for verification. secp256k1(-zkp) supports that the precomputed table values for the signing table are stored in the executable (by defining USE_ECMULT_STATIC_PRECOMPUTATION) and thus do not need to be created at running time.

It's WIP because the following is still open (and maybe more):

• [x] secp256k1-zkp uses two "error callbacks". These are called when some bad error occurs and we don't know how to continue except for shutting down the execution properly, see https://github.com/bitcoin-core/secp256k1/blob/77668c09da756190e188521d87aaaa08736fa196/include/secp256k1.h#L218 and the function below for details. The default callbacks use abort() and fprintf(), so we need to replace them. I replaced them by functions which throw Python exceptions. Is this the right thing to do on trezor?
• [x] The size of the verification table is configurable. A larger table makes verification possibly faster. We set it to 4096 bytes (of RAM). Is this is fine for you as memory footprint? I guess even smaller is okay because verification speed is not so crucial. We need to see if we want to move that to CCMRAM too as mentioned in https://github.com/trezor/trezor-core/issues/282#issuecomment-467508352 .
• [x] The table(s) are stored in a secp256k1_context which is currently created when it's first used. Is that okay or do we want to create at program startup?
• [ ] This currently relies on a dev branch of secp256k1-zkp. We'll merge this into master once we know that we're on the right track.
  • [x] We wanted to enable USE_ECMULT_STATIC_PRECOMPUTATION but it increases the executable by 64 KiB, which is about 17 KiB too much after we rebased on master. To make the build work I've added a HACK commit that disables `USE_ECMULT_STATIC_PRECOMPUTATION in the firmware build again. But that means calling into secp256k1-zkp functions will fail at runtime because we don't give it enough memory to create the table. Note that it's probably really better to build this in the executable because otherwise we need 64 KiB of RAM instead of flash. Also, we need to keep in mind that currently no rangeproof functions are used, so those will be removed from the executable. If we really call these, the size will increase further.
  • [x] There is naming collision between with the header secp256k1.h. For some reason the build currently works (at least on my machine) but this is probably fragile. Our goal is to make all of this work without the need to vendor specific secp256k1-zkp changes, and we'd rather not want to rename our header. I think it's easiest to rename your currently used secp256k1.h? Is that fine for you? Otherwise we can also use #includes with directories.

We opened this mostly to get some feedback on the build system. We can also decide to use this PR just for the build system and handle the other stuff in a different PR if that works better for you.

cc @romanz @apoelstra

[real-or-random]

Note to self: We should also call secp256k1_context_randomize (https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L641) after creating the context

[prusnak]

1) I would prefer not changing import secp256k1 to import secp256k1_zkp in our Python code via this pull request. It simplifies reviewing and I am not sure whether we are going to switch immediately. It makes sense to use secp256k1_zkp for Liquid, but I am not in favor of using it everywhere unless there are benchmarks done which prove the zkp implementation is faster and/or has other big advantages. 2) I agree we should use directories in #include to avoid clashes. I will address this in another pull request.

[real-or-random]

I would prefer not changing import secp256k1 to import secp256k1_zkp in our Python code via this pull request. It simplifies reviewing and I am not sure whether we are going to switch immediately. It makes sense to use secp256k1_zkp for Liquid, but I am not in favor of using it everywhere unless there are benchmarks done which prove the zkp implementation is faster and/or has other big advantages.

No problem, then we should first focus on just getting zkp imported and included in the build. I'll update this PR then. Anyway, it was still good to have these other commits to demonstrate that the build worked and can actually be used, and for the future.

I agree we should use directories in #include to avoid clashes. I will address this in another pull request.

Okay, I can also just do it when I update this.

[prusnak]

Anyway, it was still good to have these other commits to demonstrate that the build worked and can actually be used, and for the future.

Sure, I 100% agree. To be clear, I am not opposed to using secp256k1_zkp globally for ECDSA/ECDH operations. But let's test that first.

[prusnak]

Maybe we can leverage the fact the tests for secp256k1 and secp256k1_zkp ar the same. Something like this comes to mind:

from trezor.crypto.curve import secp256k1, secp256k1_zkp

class Secp256k1Common(unittest.TestCase):
   # all existing unit tests go here

   def test_foo(self):
       # use impl.method instead of secp256k1.method

class TestCryptoSecp256k1(Secp256k1Common): 
    def __init__(self):
         self.impl = secp256k1

class TestCryptoSecp256k1Zkp(Secp256k1Common): 
    def __init__(self):
         self.impl = secp256k1_zkp

[romanz]

A small update to the PR (following a discussion with @real-or-random): I have replaced https://github.com/trezor/trezor-core/commit/f8b5bbc17f70be4333666fd8421b47c0dfa3cc97 by https://github.com/trezor/trezor-core/commit/55a39486ce9a06a0251c329aa036d34a551f77ba (moving the read-only precomputed tables from the .flash to .flash2 section, which AFAIU is not used for storing executable code). The resulting binary should compile and run successfully on TREZOR model T.

[prusnak]

moving the read-only precomputed tables from the .flash to .flash2 section, which AFAIU is not used for storing executable code

Good!

[real-or-random]

I added two commits to address the file name issues and the size of the context. (I'm leaving the replacement of the internal secp256k1 in at the moment for testing, we can remove that if everything looks good.)

@prusnak Do the callbacks look right to you?

[prusnak]

@real-or-random offtopic: How hard is to add NIST P-256 curve to secp256k1 library? Is this even possible or desired?

[apoelstra]

@prusnak it would basically mean rewriting the library. It is neither possible nor desired :)

[prusnak]

Got it :)

[real-or-random]

We have now https://github.com/ElementsProject/secp256k1-zkp/pull/53 which (when merged) removes the need to use a modified branch/version of secp256k-zkp.

The remaining issues are the top three items in the list in first comment here in this PR @prusnak Can you comment on these? :)

[prusnak]

I replaced them by functions which throw Python exceptions. Is this the right thing to do on trezor?

Yes

4096 bytes (of RAM). Is this is fine for you as memory footprint?

Yes

The table(s) are stored in a secp256k1_context which is currently created when it's first used. Is that okay or do we want to create at program startup?

I think that's fine as a PoC.

[prusnak]

Can you please squash the changes into a single commit and resolve conflicts (rebase on top of the current master)? We have reformatted our code using clang-format. Config is in the .clang-format file but it should be picked up automatically, just use clang-format -i on newly added C files. This should help with the resolution.

[real-or-random]

Okay, I squashed and changed it to remove the commits that change the apps. Two issues open left:

• Your TODO where we don't raise an exception, see above.
• We need to wait until https://github.com/ElementsProject/secp256k1-zkp/pull/53 is merged and change the submodule according.

[real-or-random]

The table(s) are stored in a secp256k1_context which is currently created when it's first used. Is that okay or do we want to create at program startup?

I think that's fine as a PoC.

Yes, indeed. I think in a PR that actually changes apps to use secp256k1-zkp, it's best to change this to a model where the verification table is only created when it's necessary (which is rare). Currently, we would create the verification table even when we would call into secp256k1-zkp for signing, which is kind of silly because signing is much more common and we don't need to build a table for signing (because the signing table it's statically built).

[real-or-random]

I added two commits (will squash again if you approve):

• I changed my mind about one the callbacks, namely the error_callback. This is only triggered when some internal check fails and we really just want to crash the entire device, because continuing execution could mean undefined behavior or leaking secrets etc, see https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/include/secp256k1.h#L247 for an explanation. So this is a last resort thing, and I changed it to call __fatal_error() instead.
• I removed your comment about returning None as explained here https://github.com/trezor/trezor-core/pull/500#discussion_r271510331.

With these two commits, this PR is ready to be merged except that we need to wait for https://github.com/ElementsProject/secp256k1-zkp/pull/53 to be merged and adjust the submodule.

[prusnak]

(will squash again if you approve):

Agreed. Please squash.

this PR is ready to be merged except that we need to wait for #53 to be merged and adjust the submodule.

Ack. we'll review it in the meantime. @jpochyla can you have a look, please?

[real-or-random]

Squashed.

[real-or-random]

Okay, sorry, I pushed again because I additionally enabled some ASM optimizations for ASM in secp256k1-zkp.

[prusnak]

Okay @real-or-random, great job! We are ready to merge. We'll wait until you merge https://github.com/ElementsProject/secp256k1-zkp/pull/53 and adjust the submodule in this PR.

[real-or-random]

Okay force-pushed, I touched only .gitmodules. The other PR is not merged yet but should be today.

[apoelstra]

Merged the other PR.

[prusnak]

@real-or-random do you want to change the revision of the included submodule to reflect the last change from @apoelstra or should we merge as is?

[real-or-random]

Oh yes I should have done this. I'll update it later. :)

[real-or-random]

fixed

[prusnak]

Great work @real-or-random, thanks for the contribution!