Confidential Assets tracking issue

[apoelstra]

It would be great to have support for Confidental Assets (CA), which is used in the Elements blockchain platform and in Liquid, the commercial sidechain based on Elements. I'm happy to help move this forward, and am available by email at apoelstra at blockstream.com for any clarification or guidance.

CA is described in this blog post: https://blockstream.com/2017/04/03/blockstream-releases-elements-confidential-assets.html
It is essentially the same as Confidential Transactions, which involves the use of Pedersen commitments in place of amounts, alongside rangeproofs, which I believe is already supported as part of Trezor's Monero support. CA mades one of the two EC generators variable and adds a new "asset surjection proof" which is described here: https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/src/modules/surjection/surjection.md

We've implemented CA in full as part of libsecp256k1-zkp, our fork of the Bitcoin Core libsecp256k1 library.

For referenc, the API for making surjection proofs is here: https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/include/secp256k1_surjectionproof.h
and the core crypto functionality is here:
https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/src/modules/surjection/main_impl.h
https://github.com/ElementsProject/secp256k1-zkp/blob/secp256k1-zkp/src/modules/surjection/surjection_impl.h

Cheers

[prusnak]

Hello Andrew! Thanks for contacting us and creating this tracking issue.

We use our trezor-crypto library for both Trezor One and the new Model T.

Monero support is being added in this pull request: trezor/trezor-crypto#162

Monero uses a different curve (Curve25519), so I don't think there's any way we could reuse Pedersen commitments and/or range proofs from this code.

In order to get Confidential Assets working on Trezor, there are two different approaches:

1. add CA primitives to trezor-crypto (built on top of our ecdsa primitives)
2. port secp256k1-zkp to Trezor

I think option 1) is probably easier, although I am not sure how much of the new code would that need.

Option 2) might be complicated, because we don't use malloc/free in our crypto environment and as far as I can tell secp256k1 uses these OS features.

[apoelstra]

Hi @prusnak ,

Our current use of malloc is well-encapsulated in only one place: secp256k1_context_create and secp256k1_context_free. These functions need to be called only during system init/deinit and is designed to be easily replaceable on embedded systems that do not support malloc.

We also use malloc in our unit tests and benchmarks, which I assume doesn't matter.

So I think option (2) is actually likely to be the simpler one.

[prusnak]

Is secp256k1-zkp a superset of libsecp256k1? If yes, I think it's worth the effort integrating secp256k1 into our stack.

[apoelstra]

Yes, secp256k1-zkp is a superset of libsecp256k1 - all the new code is in the src/modules/ tree (and Makefile.am and configure.ac are correspondingly modified).

The current use of malloc in secp256k1_context_create is used to build two precomputation tables - one for signing (which uses a constant-time scalar-point multiply) and one for verification (ditto, but not constant-time). We already have code that allows static compilation of the signing context, but rangeproofs will require both contexts.

I'll work with upstream libsecp to figure out the cleanest way to avoid malloc entirely.

[apoelstra]

@prusnak because only one context is needed for the entire device, it's sufficient to replace checked_malloc in util.h with a function that returns a pointer into a fixed memory space (and increments it for subsequent calls). Would that integrate well with Trezor?

[prusnak]

Would that integrate well with Trezor?

Yes, that would work. I created a branch zkp which copies trezor.crypto.curve.secp256k1 into trezor.crypto.curve.secp256k1_zkp. All you need is to replace stuff inside embed/extmod/modtrezorcrypto/modtrezorcrypto-secp256k1_zkp.h so it doesn't use secp256k1.h from trezor-crypto, but rather your implementation you add as a submodule to vendor/. I guess we can even use gc_alloc and gc_free from Micropython in this code as a proof-of-concept.

[prusnak]

Ping?

[apoelstra]

Hi, sorry for the delay. I had meant to work on this every day for the last 2 weeks but I didn't find the time.

My plan today is to make a PR upstream to allow creating a context object from a user-provided byte array (and a utility function to determine how large the array needs). I'll pull that into secp256k1-zkp and then I'll work on integrating that.

[prusnak]

Sure, let me know if you need help with anything.

[apoelstra]

Sorry for the continued delay, this was a bit harder than I expected because the precomputation requires not only memory for the context, but also extra scratch space memory that it only uses during the computation. So I need to think more carefully about how to make a comprehensible API -- questions like, how can signing precomp and verification precomp use the same scratch space; how can I make context cloning require enough memory for the new context but not enough for scratch; etc.

I also got ratholed trying to redo some of the precomp algorithms to not use so much aux space..

[prusnak]

No worries, take your time. I just wanted to make sure we are not blocking you in the development.

[apoelstra]

With a bit of algebra I found a way to eliminate all of the scratch memory, so this API wart can be avoided entirely.

bitcoin-core/secp256k1#557

[prusnak]

With a bit of algebra I found a way to eliminate all of the scratch memory, so this API wart can be avoided entirely.

Awesome!

[real-or-random]

Just a small update: We have a PR now that makes secp256k1 work with a block of caller-allocated memory: bitcoin-core/secp256k1#566

[prusnak]

@real-or-random great news!

[apoelstra]

I'm getting started working on the libsecp port but I think I'm doing something wrong. I have two unrelated build issues.

1. When I try to build the simulator it seems that there are no limits on memory usage or libc calls; I can stick malloc(100000) into the signing code and everything compiles fine and the tests in tests/test_apps.wallet.signtx.py still run successfully. (And I checked that I'm running the right code by re-running it and raising an error.) How can I ensure that I'm writing code without sneaking in system malloc() calls or using piles of memory?
2. If I try to build the firmware by following the pipenv instructions in docs/build.md I get the following compilation error

vendor/micropython/lib/stm32lib/STM32F4xx_HAL_Driver/Src/stm32f4xx_ll_usb.c: In function 'USB_WritePacket':
vendor/micropython/lib/stm32lib/STM32F4xx_HAL_Driver/Src/stm32f4xx_ll_usb.c:888:7: error: 'packed' attribute ignored for type 'uint32_t *' {aka 'long unsigned int *'} [-Werror=attributes]
       USBx_DFIFO(ch_ep_num) = *((__packed uint32_t *)src);
       ^~~~~~~~~~
vendor/micropython/lib/stm32lib/STM32F4xx_HAL_Driver/Src/stm32f4xx_ll_usb.c: In function 'USB_ReadPacket':
vendor/micropython/lib/stm32lib/STM32F4xx_HAL_Driver/Src/stm32f4xx_ll_usb.c:914:5: error: 'packed' attribute ignored for type 'uint32_t *' {aka 'long unsigned int *'} [-Werror=attributes]
     *(__packed uint32_t *)dest = USBx_DFIFO(0U);
     ^

[prusnak]

1. emulator is emulator, there are no limits. it also don't make sense to introduce them as memory layout is quite different for x86_64 (64-bit pointer size) than on arm (32bit) and objects take much more space in emulator.
2. architecure? gcc-version? does build using docker (./build-docker.sh) work

[apoelstra]

I'm am an an x86_64 system with the following gcc

Using built-in specs.
COLLECT_GCC=arm-none-eabi-gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/arm-none-eabi/8.2.0/lto-wrapper
Target: arm-none-eabi
Configured with: /build/arm-none-eabi-gcc/src/gcc-8.2.0/configure --target=arm-none-eabi --prefix=/usr --with-sysroot=/usr/arm-none-eabi --with-native-system-header-dir=/include --libexecdir=/usr/lib --enable-languages=c,c++ --enable-plugins --disable-decimal-float --disable-libffi --disable-libgomp --disable-libmudflap --disable-libquadmath --disable-libssp --disable-libstdcxx-pch --disable-nls --disable-shared --disable-threads --disable-tls --with-gnu-as --with-gnu-ld --with-system-zlib --with-newlib --with-headers=/usr/arm-none-eabi/include --with-python-dir=share/gcc-arm-none-eabi --with-gmp --with-mpfr --with-mpc --with-isl --with-libelf --enable-gnu-indirect-function --with-host-libstdcxx='-static-libgcc -Wl,-Bstatic,-lstdc++,-Bdynamic -lm' --with-pkgversion='Arch Repository' --with-bugurl=https://bugs.archlinux.org/ --with-multilib-list=rmprofile
Thread model: single
gcc version 8.2.0 (Arch Repository) 

./build-docker.sh fails for me with a Python exception

Sending build context to Docker daemon  509.7MB
Step 1/13 : FROM debian:9
 ---> be2868bebaba
Step 2/13 : RUN apt-get update && apt-get install -y     build-essential wget git python3-pip gcc-multilib
 ---> Using cache
 ---> db16b8548d9c
Step 3/13 : ENV TOOLCHAIN_SHORTVER=7-2018q2
 ---> Using cache
 ---> e81d2510e207
Step 4/13 : ENV TOOLCHAIN_LONGVER=gcc-arm-none-eabi-7-2018-q2-update
 ---> Using cache
 ---> 44039a22c632
Step 5/13 : ENV TOOLCHAIN_FLAVOR=linux
 ---> Using cache
 ---> c5161bc4eb1a
Step 6/13 : ENV TOOLCHAIN_URL=https://developer.arm.com/-/media/Files/downloads/gnu-rm/$TOOLCHAIN_SHORTVER/$TOOLCHAIN_LONGVER-$TOOLCHAIN_FLAVOR.tar.bz2
 ---> Using cache
 ---> 10ea91fd2e4b
Step 7/13 : RUN cd /opt && wget $TOOLCHAIN_URL && tar xfj $TOOLCHAIN_LONGVER-$TOOLCHAIN_FLAVOR.tar.bz2
 ---> Using cache
 ---> 93cd6a551e7f
Step 8/13 : ENV PATH=/opt/$TOOLCHAIN_LONGVER/bin:$PATH
 ---> Using cache
 ---> 05c926049e19
Step 9/13 : RUN pip3 install click pyblake2 scons
 ---> Using cache
 ---> 7162774f4226
Step 10/13 : RUN pip3 install --no-deps git+https://github.com/trezor/python-trezor.git@master
 ---> Running in 5607fb26382e
Collecting git+https://github.com/trezor/python-trezor.git@master
  Cloning https://github.com/trezor/python-trezor.git (to master) to /tmp/pip-zbqsaizf-build
Installing collected packages: trezor
  Running setup.py install for trezor: started
    Running setup.py install for trezor: finished with status 'error'
    Complete output from command /usr/bin/python3 -u -c "import setuptools, tokenize;__file__='/tmp/pip-zbqsaizf-build/setup.py';f=getattr(tokenize, 'open', open)(__file__);code=f.read().replace('\r\n', '\n');f.close();exec(compile(code, __file__, 'exec'))" install --record /tmp/pip-vfsilqhl-record/install-record.txt --single-version-externally-managed --compile:
    /usr/lib/python3.5/distutils/dist.py:261: UserWarning: Unknown distribution option: 'long_description_content_type'
      warnings.warn(msg)
    running install
    running build
    running build_py
    running prebuild
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/tmp/pip-zbqsaizf-build/setup.py", line 146, in <module>
        cmdclass={"prebuild": PrebuildCommand},
      File "/usr/lib/python3.5/distutils/core.py", line 148, in setup
        dist.run_commands()
      File "/usr/lib/python3.5/distutils/dist.py", line 955, in run_commands
        self.run_command(cmd)
      File "/usr/lib/python3.5/distutils/dist.py", line 974, in run_command
        cmd_obj.run()
      File "/usr/lib/python3/dist-packages/setuptools/command/install.py", line 61, in run
        return orig.install.run(self)
      File "/usr/lib/python3.5/distutils/command/install.py", line 583, in run
        self.run_command('build')
      File "/usr/lib/python3.5/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/lib/python3.5/distutils/dist.py", line 974, in run_command
        cmd_obj.run()
      File "/usr/lib/python3.5/distutils/command/build.py", line 135, in run
        self.run_command(cmd_name)
      File "/usr/lib/python3.5/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/lib/python3.5/distutils/dist.py", line 974, in run_command
        cmd_obj.run()
      File "/tmp/pip-zbqsaizf-build/setup.py", line 108, in new_run
        self.run_command("prebuild")
      File "/usr/lib/python3.5/distutils/cmd.py", line 313, in run_command
        self.distribution.run_command(command)
      File "/usr/lib/python3.5/distutils/dist.py", line 974, in run_command
        cmd_obj.run()
      File "/tmp/pip-zbqsaizf-build/setup.py", line 81, in run
        build_coins_json(coins_json)
      File "/tmp/pip-zbqsaizf-build/setup.py", line 49, in build_coins_json
        coins = coin_info.coin_info().bitcoin
      File "/tmp/pip-zbqsaizf-build/vendor/trezor-common/tools/coin_info.py", line 492, in coin_info
        all_coins, _ = coin_info_with_duplicates()
      File "/tmp/pip-zbqsaizf-build/vendor/trezor-common/tools/coin_info.py", line 483, in coin_info_with_duplicates
        all_coins = collect_coin_info()
      File "/tmp/pip-zbqsaizf-build/vendor/trezor-common/tools/coin_info.py", line 456, in collect_coin_info
        erc20=_load_erc20_tokens(),
      File "/tmp/pip-zbqsaizf-build/vendor/trezor-common/tools/coin_info.py", line 229, in _load_erc20_tokens
        token = load_json(filename)
      File "/tmp/pip-zbqsaizf-build/vendor/trezor-common/tools/coin_info.py", line 29, in load_json
        return json.load(f, object_pairs_hook=OrderedDict)
      File "/usr/lib/python3.5/json/__init__.py", line 265, in load
        return loads(fp.read(),
      File "/usr/lib/python3.5/encodings/ascii.py", line 26, in decode
        return codecs.ascii_decode(input, self.errors)[0]
    UnicodeDecodeError: 'ascii' codec can't decode byte 0xd1 in position 19: ordinal not in range(128)

[prusnak]

@apoelstra I just removed all cached docker images, restarted the docker build and everything works for me. Try running docker rmi $(docker images -q) first.

We are using gcc-7 as can be seen from the Dockerfile. Most probably gcc-8 has more aggressive checks. You can either use gcc-7 or add -Wno-attributes to CFLAGS in SConscript files.

[apoelstra]

Quick update on this because I realize we've been working somewhat in the background here.

With the help of @romanz we've got the basic secp256k1 library working on the Trezor 1 and T. With some hacky stack measurement we've confirmed that we're far away from any resource limits. We're uncertain about our build commands or use of the micropython allocator but we think we're close.

From here @real-or-random and I have been working on getting the rangeproof and surjection proof code. Our initial measurements indicate that we're using roughly 30Kb of 15Kb available stack space :) so over the next couple days I'm rewriting the core functions that implement rangeproof proving and verification to eliminate this overuse of stack space. We both have obtained physical devices that we can test on, since the simulator does not simulate memory limits.

These functions are self-contained and I think the scope of this rewrite is very narrow and straightforward. I met with Greg Maxwell, who wrote the original code, a couple of days ago and he had a similar intuition.

[prusnak]

@apoelstra These are great news! Looking forward to working with you on merging the functionality into our tree.

[real-or-random]

From here @real-or-random and I have been working on getting the rangeproof and surjection proof code. Our initial measurements indicate that we're using roughly 30Kb of 15Kb available stack space :) so over the next couple days I'm rewriting the core functions that implement rangeproof proving and verification to eliminate this overuse of stack space. We both have obtained physical devices that we can test on, since the simulator does not simulate memory limits.

Okay, so we had a closer look at the code. It's possible to rewrite it to use less stack memory, we're not convinced that this is the best idea because it will probably almost double the (already noticeable) running time of the rangeproof creation. In our experiments, we overused the stack by about 15 KB, but the code worked fine (on the physical device). What exactly happens is that we use more stack than reserved by the firmware within micropython. But since this is FFI code, micropython does not check that we're using more stack and just let us run. But since the code actually works (so the memory is in fact available) and is the fastest way to create rangeproofs, we wonder what the best forward is. Specifically,

• is it okay to just increase the stack reservation? If yes, that's the simplest solution, because the memory is really only need during the function call. (Unlike the secp256k1 context that we changed to caller-provided memory; this contains precomputations used for multiple calls.)
• if increasing the stack reservation not okay, is it maybe possible to use some other 15 KB of memory of available memory? (statically allocated / caller provided like we did for the bare secp256k1?)

As I said it's possible to use less stack memory but we really would like to avoid it due to the performance hit.

[prusnak]

@jpochyla can you shed some light on stack limitations?

[real-or-random]

@prusnak @jpochyla Could you figure this out?

[jpochyla]

Hi! Sorry about the delay.

Seems like the best way to solve this would be to move the C stack into CCMRAM, that should give us 64KB space in total, instead of 16KB soft-limit. You can find the code here: https://github.com/trezor/trezor-core/tree/ccmram_stack

64KB should be enough, right?

[real-or-random]

Thanks!

64KB ought to be enough for anybody.

If none of our math was wrong, we'll need 32 KB altogether (current stack of 16KB plus ~15KB use over the current limit. We'll try our patches on top of your branch.

[romanz]

Unfortunately, it seems that using the CCMRAM for the stack causes USB disconnection after running a get-features command:

$ git lg -1 
* 22bf491a firmware: move the c stack into ccmram

$ trezorctl list 
webusb:003:2 
$ trezorctl get-features 
Features (90 bytes) { device_id: '9BC70FAD4E718F8C8944B712', flags: 0, initialized: True, language: 'english', major_version: 2, minor_version: 1, model: 'T', needs_backup: False, no_backup: False, passphrase_cached: False, passphrase_protection: False, patch_version: 0, pin_cached: False, pin_protection: False, revision: 8 bytes b'22bf491a', unfinished_backup: False, vendor: 'trezor.io', } 

$ trezorctl list 
Failed to enumerate WebUsbTransport. USBErrorIO: LIBUSB_ERROR_IO [-1] 
$ trezorctl get-features 
Failed to enumerate WebUsbTransport. USBErrorIO: LIBUSB_ERROR_IO [-1] 
Failed to enumerate WebUsbTransport. USBErrorIO: LIBUSB_ERROR_IO [-1] 
Failed to find a TREZOR device.

@jpochyla Could you please take a look?

[prusnak]

@romanz What do you see on the display? It seems the device stopped responding.

[romanz]

@prusnak
It shows the default background image (nothing seems to change after the device stops responding).

[romanz]

BTW, moving .bss section to CCMRAM seems to be working well for our case (by allowing us using larger .stack section in RAM) - see romanz/trezor-core@1dfe780.
May I submit this change as a PR to this repository?