Add extmod for secp256k1-zkp #500

real-or-random · 2019-03-14T23:33:37Z

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):

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?
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 .
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.
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.
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

embed/extmod/modtrezorcrypto/modtrezorcrypto-secp256k1_zkp.h

real-or-random · 2019-03-14T23:35:39Z

embed/extmod/modtrezorcrypto/modtrezorcrypto-secp256k1_zkp.h

+    secp256k1_pubkey pk;
+    if (!secp256k1_ecdsa_recover(ctx, &pk, &ec_sig, (const uint8_t *)dig.buf)) {
+        // Copying "return None" behaviour from secp256k1 module; but why do
+        // we do this rather than raising an exception?


Looks like a TODO.

Yes, this is still open. We raise an exception for every other failure mode, so I see no reason why we should not raise an exception here. Any ideas?

Well, so the documentation of the function says that it should return None if the signature is invalid, so None makes sense. However, the actual behavior of the function is that either returns None or raises ValueError if the signature is invalid.

This inconsistency lead to a bug (#422), which was fixed in d5fb2a4 by handling both None and an exceptions equally in the caller code. (The Ethereum app is the only caller.)

I think this can be improved by making the function consistently return None no matter what the failure is, but in a different PR. I will remove your comment then at least here. If you agree with this conclusion, I'm volunteering to create that other PR, it should just take a few minutes.

embed/extmod/modtrezorcrypto/modtrezorcrypto-secp256k1_zkp.h

real-or-random · 2019-03-15T09:49:46Z

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 · 2019-03-15T10:54:40Z

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.
I agree we should use directories in #include to avoid clashes. I will address this in another pull request.

real-or-random · 2019-03-15T11:29:59Z

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 · 2019-03-15T11:38:03Z

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.

SConscript.firmware

prusnak · 2019-03-15T12:23:49Z

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 · 2019-03-17T13:28:49Z

A small update to the PR (following a discussion with @real-or-random):
I have replaced f8b5bbc by 55a3948 (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 · 2019-03-17T22:24:52Z

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 · 2019-03-20T15:58:16Z

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 · 2019-03-25T14:25:25Z

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

apoelstra · 2019-03-25T16:13:18Z

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

prusnak · 2019-03-25T19:19:54Z

Got it :)

real-or-random · 2019-04-02T13:02:16Z

We have now BlockstreamResearch/secp256k1-zkp#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 · 2019-04-02T13:08:34Z

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 · 2019-04-02T13:09:57Z

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 · 2019-04-02T15:52:59Z

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 Changes necessary for usage on Trezor BlockstreamResearch/secp256k1-zkp#53 is merged and change the submodule according.

real-or-random · 2019-04-02T15:56:14Z

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 · 2019-04-02T22:41:35Z

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 Add extmod for secp256k1-zkp #500 (comment).

With these two commits, this PR is ready to be merged except that we need to wait for BlockstreamResearch/secp256k1-zkp#53 to be merged and adjust the submodule.

prusnak · 2019-04-03T11:12:18Z

(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 · 2019-04-04T10:39:15Z

Squashed.

real-or-random · 2019-04-04T16:27:53Z

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

prusnak · 2019-04-11T10:05:31Z

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

real-or-random · 2019-04-12T15:50:05Z

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

apoelstra · 2019-04-12T16:43:18Z

Merged the other PR.

prusnak · 2019-04-12T20:18:59Z

@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 · 2019-04-12T21:28:59Z

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

This includes the https://github.com/ElementsProject/secp256k1-zkp library (which is a fork from sipa/secp256k1 used in Bitcoin Core) as a module. It is currently not used in any app. This commit the first step towards integrating Liquid (tracking issue #282). Note that this creates a new 64 kiB read-only data section in .flash2 for pre-computed tables (secp256k1_ecmult_static_context) which speed up signature creation and related private key operations. Co-authored-by: Roman Zeyde <me@romanzey.de> Co-authored-by: Andrew Poelstra <apoelstra@wpsoftware.net> Co-authored-by: Pavol Rusnak <pavol@rusnak.io>

real-or-random · 2019-04-13T00:03:51Z

fixed

prusnak · 2019-04-15T15:58:14Z

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

d4d270a Allow field_10x26_arm.s to compile for ARMv7 architecture (Roman Zeyde) Pull request description: It would allow using optimized field operations on the TREZOR device, which is using ARMv7 Cortex-M4. Following trezor/trezor-core#500 and part of trezor/trezor-firmware#66. Tree-SHA512: 73c0f03503feff01c6f4efd884e916ae1f43f55d525e8c3ea9372cf777aef6901585b74774c316dd7937abfff5e86be5b1acb569f9eeee9b73ae088f0f6b589d

real-or-random commented Mar 14, 2019

View reviewed changes

prusnak reviewed Mar 15, 2019

View reviewed changes

SConscript.firmware Outdated Show resolved Hide resolved

romanz force-pushed the wip-secp256k1-zkp branch from f8b5bbc to 55a3948 Compare March 17, 2019 13:23

real-or-random force-pushed the wip-secp256k1-zkp branch from 5e42337 to 4c8fb0c Compare March 20, 2019 15:57

prusnak added this to the v2.1.1 milestone Mar 20, 2019

real-or-random force-pushed the wip-secp256k1-zkp branch from 98acb08 to 1ab15b0 Compare March 23, 2019 23:32

real-or-random force-pushed the wip-secp256k1-zkp branch from 1ab15b0 to 59eea86 Compare April 2, 2019 15:39

real-or-random changed the title ~~WIP: Replace internal secp256k1 by secp256k1-zkp library~~ Add extmod for secp256k1-zkp Apr 2, 2019

real-or-random force-pushed the wip-secp256k1-zkp branch 3 times, most recently from d6d2299 to f1934b9 Compare April 2, 2019 15:47

prusnak self-requested a review April 3, 2019 11:12

prusnak requested a review from jpochyla April 3, 2019 11:12

tsusanka assigned jpochyla Apr 3, 2019

real-or-random force-pushed the wip-secp256k1-zkp branch from 82996bf to 809c2e3 Compare April 4, 2019 10:38

real-or-random mentioned this pull request Apr 4, 2019

extmod/modtrezorcrypto: return False or None consistently when a signature verification fails #535

Closed

real-or-random force-pushed the wip-secp256k1-zkp branch from 809c2e3 to bd53fb2 Compare April 4, 2019 15:06

jpochyla approved these changes Apr 11, 2019

View reviewed changes

prusnak approved these changes Apr 11, 2019

View reviewed changes

real-or-random force-pushed the wip-secp256k1-zkp branch from bd53fb2 to 65bb972 Compare April 12, 2019 15:49

real-or-random force-pushed the wip-secp256k1-zkp branch from 65bb972 to c542cb3 Compare April 13, 2019 00:03

jpochyla merged commit 52d3495 into trezor:master Apr 15, 2019

romanz mentioned this pull request Apr 21, 2019

Allow field_10x26_arm.s to compile for ARMv7 architecture bitcoin-core/secp256k1#612

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add extmod for secp256k1-zkp #500

Add extmod for secp256k1-zkp #500

real-or-random commented Mar 14, 2019 •

edited

Loading

real-or-random Mar 14, 2019

real-or-random Apr 2, 2019

real-or-random Apr 2, 2019

real-or-random commented Mar 15, 2019

prusnak commented Mar 15, 2019 •

edited

Loading

real-or-random commented Mar 15, 2019

prusnak commented Mar 15, 2019

prusnak commented Mar 15, 2019 •

edited

Loading

romanz commented Mar 17, 2019

prusnak commented Mar 17, 2019

real-or-random commented Mar 20, 2019 •

edited

Loading

prusnak commented Mar 25, 2019

apoelstra commented Mar 25, 2019

prusnak commented Mar 25, 2019

real-or-random commented Apr 2, 2019

prusnak commented Apr 2, 2019

prusnak commented Apr 2, 2019 •

edited

Loading

real-or-random commented Apr 2, 2019

real-or-random commented Apr 2, 2019

real-or-random commented Apr 2, 2019 •

edited

Loading

prusnak commented Apr 3, 2019

real-or-random commented Apr 4, 2019

real-or-random commented Apr 4, 2019

prusnak commented Apr 11, 2019 •

edited

Loading

real-or-random commented Apr 12, 2019

apoelstra commented Apr 12, 2019

prusnak commented Apr 12, 2019 •

edited

Loading

real-or-random commented Apr 12, 2019

real-or-random commented Apr 13, 2019

prusnak commented Apr 15, 2019

Add extmod for secp256k1-zkp #500

Add extmod for secp256k1-zkp #500

Conversation

real-or-random commented Mar 14, 2019 • edited Loading

real-or-random Mar 14, 2019

Choose a reason for hiding this comment

real-or-random Apr 2, 2019

Choose a reason for hiding this comment

real-or-random Apr 2, 2019

Choose a reason for hiding this comment

real-or-random commented Mar 15, 2019

prusnak commented Mar 15, 2019 • edited Loading

real-or-random commented Mar 15, 2019

prusnak commented Mar 15, 2019

prusnak commented Mar 15, 2019 • edited Loading

romanz commented Mar 17, 2019

prusnak commented Mar 17, 2019

real-or-random commented Mar 20, 2019 • edited Loading

prusnak commented Mar 25, 2019

apoelstra commented Mar 25, 2019

prusnak commented Mar 25, 2019

real-or-random commented Apr 2, 2019

prusnak commented Apr 2, 2019

prusnak commented Apr 2, 2019 • edited Loading

real-or-random commented Apr 2, 2019

real-or-random commented Apr 2, 2019

real-or-random commented Apr 2, 2019 • edited Loading

prusnak commented Apr 3, 2019

real-or-random commented Apr 4, 2019

real-or-random commented Apr 4, 2019

prusnak commented Apr 11, 2019 • edited Loading

real-or-random commented Apr 12, 2019

apoelstra commented Apr 12, 2019

prusnak commented Apr 12, 2019 • edited Loading

real-or-random commented Apr 12, 2019

real-or-random commented Apr 13, 2019

prusnak commented Apr 15, 2019

real-or-random commented Mar 14, 2019 •

edited

Loading

prusnak commented Mar 15, 2019 •

edited

Loading

prusnak commented Mar 15, 2019 •

edited

Loading

real-or-random commented Mar 20, 2019 •

edited

Loading

prusnak commented Apr 2, 2019 •

edited

Loading

real-or-random commented Apr 2, 2019 •

edited

Loading

prusnak commented Apr 11, 2019 •

edited

Loading

prusnak commented Apr 12, 2019 •

edited

Loading