Fixpoint

2019-11-19

Gales Bitcoin Wallet: status, preliminary work plan and code dump

Filed under: Bitcoin, Software — Jacob Welsh @ 21:01

The item in question is the software component of a combination of hardware, software and operational practices with the goal of sending and receiving Bitcoin while excluding the possibility of remote compromise of keys (so long as underlying cryptographic assumptions hold). Proper airgapping is the foundation, but it's easier said than done when it comes to Bitcoin because of the dependency on data from the outside world for the inputs of a transaction. Popular "cold storage" solutions may involve storing keys offline, but have windows of vulnerability when the keys are generated and funds are swept using an online (i.e. insecure) machine.

Our approach is to allow data to jump the gap as selectively as possible, using a simple and low-speed channel (serial port) with optical isolation and manually switched simplex operation (one way at a time). The system is intended for manual, low-frequency usage; thus we're not especially concerned with performance or timing side channels.(i) At the same time, we're very concerned with correctness, which informs a preference for straightforward "textbook" implementations when possible, minimizing external dependencies and overall system complexity, maximizing auditability (e.g. avoiding any sort of processor-specific "crypto acceleration"), and publishing code.(ii)

Design points include:

  • An offline machine, running the offline component of the wallet. The machine is to have no swap, be operated on battery power during key operations, and powered off after use.
  • A set of private keys, generated offline by explicit request and associated with names of the operator's choice, stored in a tmpfs during operation and GPG-encrypted on disk using a strong password when at rest.
  • A true (i.e. hardware) random number generator, used for all key generation including the ephemeral keys used in ECDSA signing.
  • Transactions constructed offline (potentially reducing round trips through the airgap).
  • An online machine running a TRB node and the online component of the wallet, which pushes outbound transactions, scans for sufficiently-confirmed new transactions affecting the set of watched addresses, and produces minimal data structures for updating state of the offline component.

Status

I've used my own Scheme system for implementation of the offline component so far, after an earlier prototype in the much larger (albeit more battle-tested) Python. Much of the code falls into one of two categories: math, or shuffling data from one format to another.

On the first category, I've implemented the following algorithms, with reference primarily to Menezes, van Oorschot and Vanstone and the SECG standards.

  • Bignum arithmetic: addition/subtraction, multiplication, division/remainder. My first pass here was intended more as an exercise, a "userspace" (pure Scheme) implementation supporting only unsigned values. I subsequently redid this, with signed integers and plugging into the generic arithmetic operators, still mostly in Scheme. The wallet code is presently still using the former. This is a conventional arbitrary-precision framework and thus does not support constant-time operations.
  • Modular inversion (extended Euclidean GCD).
  • Unbiased random integer in a given range.
  • Elliptic curve point addition and scalar multiplication, for the secp256k1 curve required by Bitcoin. Scalar multiplication is the most intensive operation, done once for key generation and several times for signing, and comes out noticeably slow; one optimization was to precompute iterated doublings of the generator point.
  • ECDSA signing.
  • SHA256 and RIPEMD160 hash functions.

On the second, the following, with reference primarily to the TRB and OpenSSL code (and sometimes the Bitcoin Wiki which was almost always a mistake):

  • Base58 and Base58Check
  • Little-endian hex and octet encoding
  • Fixed and variable-length integer byte encodings as seen in Bitcoin
  • The OpenSSL EC point (public key) encoding
  • The subset of ASN.1 DER as used by OpenSSL for ECDSA signatures
  • Bitcoin script, with code to construct p2pkh and p2sh outputs(iii)

These are presently wrapped up into commands by which one can generate private key files, the associated addresses, and (in case of emergency) export private keys to the "WIF" format for import to other wallet software.

The aforementioned Python prototype also implements the somewhat convoluted Bitcoin transaction signing algorithm, and I have Python code for deserializing blocks and transactions.

Remaining tasks

This list will surely need some revision upon contact with reality. The practical deadline so as not to wreck my own holiday is December 13.

For the offline component:

  • Porting transaction signing to Scheme
  • External representation of transaction data (S-expression or maybe JSON)
  • Switching to the now-builtin bignum support
  • Unspent output accounting; import of inbound or previously unknown outbound payments
  • Transaction input selection (menu-based?)
  • ECDSA S-value normalization?
  • Frontend commands
  • Shell scripts for "opening/closing" the wallet (GPG operations)
  • More tests

The online component, for which I'll probably stick to Python and make use of available libraries:

  • Fetching blocks from TRB (new RPC? Bitcoin protocol?)
  • Pushing raw transactions to TRB (likewise)
  • Tracking watched addresses and synchronization state (SQL?)
  • Export of new payment data for transfer offline
  • Alert for unexpected outbound payments

Partial code dump

Python prototype:

Offline component, Scheme code:

  • pkg.scm - basic import/export mechanism used by the remaining
  • bignum.scm - Unsigned "userspace" bignum library
  • ecdsa.scm
  • bit-ops.scm - some rather sad complexity for implementing fixed-width arithmetic and bitwise operations, which in hindsight would have been better done as interpreter extensions
  • hashes.scm - the RIPEMD and SHA families, based on the above
  • wallet.scm
  1. Certainly it would be preferable to eliminate these. [^]
  2. At least when it comes to cryptography, you don't gain much from obscuring your algorithms or implementation, because chances are you're not as clever as you think: all the ways to mess it up are already known to someone and will eventually be probed. [^]
  3. The latter might be a contentious point; it does not involve any support for "multisig", "segwit" or similar on my side, but enables one to transact with those who insist on these Gavinistic 3-addresses. [^]

4 Comments »

  1. [...] planning in my last article left a fair amount to the imagination, and in particular several pending decisions without [...]

    Pingback by Next steps in wallet planning « Fixpoint — 2019-11-20 @ 18:40

  2. I discovered the draft code as posted here doesn't all quite fit together, in particular wallet.scm doesn't reflect changes to the bit-ops and hashes interfaces. I've fixed locally.

    From logs:

    diana_coman: jfw: over what interval have you been developing that wallet? if I read correctly it has already had a few iterations.
    diana_coman: Sept 2016 in crypto.py, huh.
    jfw: right, then and oct 2017 mainly; then redid/expanded the hashes in May 2018 based on the comment.

    diana_coman: jfw: was that footnote 3 required by your clients or what?
    jfw: Support for sending to 3-addresses: some fiat exchanges we were looking at used them

    diana_coman: re footnote 1 , preferable is one thing but required atm and given the tight timeframe you have there anyway, certainly not.
    jfw: agreed

    diana_coman: jfw: is that the minimum you can get away with currently (ie to actually have a working wallet)?
    jfw: hmm, the switching to builtin bignum could be skipped, or I could instead build on the Python though at this point I'm not sure that would save much
    diana_coman: doesn't sound likely to save much, no.

    diana_coman: jfw: what's the way you normally decide on those ? in there?
    jfw: looks like there's some different cases: for S-value, I'd check whether it's done already by TRB with -lows flag (don't believe it is though)
    jfw: otherwise: I'd take a guess which way is best, give it a try and see how it's going

    diana_coman: at this point and given the little time I'd say it's more likely faster whichever way you usually go about it; ie ~any outside mix in there is more likely to slow you down than make it faster.

    diana_coman: huh, that give it a try...how exactly do you "see how it's going" anyway?
    jfw: seeing what unexpected difficulties come up
    diana_coman: uhm, so you try A and if you run into ...too hard difficulties then you backtrack and try B and if that runs (later on) into harder difficulties you go back to A or search for C?
    jfw: (I'm getting the idea I should instead spend more effort on anticipating the difficulties)
    jfw: something like that
    diana_coman: I don't know if I envy you all the time you had or shudder at the idea there, lol.
    diana_coman: a big problem with that sort of approach in general is also that some difficulties are really way better to have than others, *even if they are harder*.
    jfw: because they lead to more growth?
    jfw: on the envy vs. shudder, I can imagine. How do you go about such decisions?
    diana_coman: at times simply because they don't kill the whole thing in the medium/long term; you can say lead to more growth (if you are talking of the whole business indeed) but that is in itself already quite optimistic.

    diana_coman: jfw: this sort of choices (to the extent it's about something rather important eg new rpc/btc protocol?) are normally management's decision really; precisely because that's the role of management - to be able to make the correct choice *for the business* not based on "technical difficulties encountered on the route" as such; tech supports aka provides as much relevant info from the tech perspective as required/available.
    jfw: ahh. And I'll note that "don't get lost in FFA right now, finish on what we've got" was advised by dorion.
    diana_coman: you clearly owe him a cerveza for that at least, lol.
    diana_coman: I do gather that dorion is more at ease first of all with marketing in fact; but he's clearly working on growing up the management skills too because yes, crucial.
    jfw: might get to buy that cerveza tonight.
    dorion will collect on the cerveza tonight.

    diana_coman: jfw: what's your current plan there on tackling those and fitting them within your 13th Dec deadline?
    dorion: diana_coman agreed on the working on mgmt and how crucial it is.
    jfw: First I need to give them time estimates and deadlines and schedule the whole period
    diana_coman: jfw: well yes but ...priorities first; hence my first question earlier re what is absolutely crucial.
    diana_coman: jfw: I don't really know how fast you work in general and on this in particular (and esp since you haven't touched it in a while if I understand correctly) but as the list stands vs the 2-3 weeks available, it still seems quite a lot & esp a lot of unknowns to me.
    jfw: ah ok, transaction signing is first I think, then, hm...
    jfw: possibly some parts could be done more manually at first

    diana_coman: dorion: part of that is also to lean on the tech to support you, not to end up supporting the tech; not saying this is what happened/is happening here but just making sure it's said in clear, just in case.
    diana_coman: jfw: you see, that's part of the question you should ask dorion really - can some parts be done more manually at first? ie is that acceptable/better than ending up moving the whole thing later/crucial etc?
    dorion: diana_coman thanks. part of it was dereliction of duty as a manager. By knowing the difficulty for myself the correctly evaluate the tech aspects I left it to him to decide, since that's his expertise/domain. A big problem though was not having in 2017 the current pleasure of reading something like the article just published.

    diana_coman: jfw: basically you should provide dorion with some options that are realistic & then ask/discuss on the decision.
    jfw: I consider & spell out the options then ask, makes sense
    jfw: well "consider" as in consider what they'd look like rather than whether "best" or something

    diana_coman: dorion: yes, you are not to ask him the impossible, certainly; but you should have certainly asked for something like this article, way sooner; and jfw should have provided one even unasked, yes; but at least one of you there to have taken some steps.
    diana_coman: jfw: yes, you can and should provide as much relevant information as you can; including "what I think it's best from tech pov" but note that it's always with *that* mention: from tech pov;
    diana_coman: and you can - if needed - give justification also ie why you'd rather this than that
    dorion: diana_coman agreed.
    diana_coman: but just as jfw, you wrestle with the tech to find a working way, note that dorion has to wrestle with a much less clearly defined beast - namely the market and the future - to figure out something that works
    diana_coman: so you know, you both want to help the other with their task, certainly but part of this is *also* letting and enabling the other to actually do their part.

    dorion: and that can't happen without proper reporting on both ends.
    diana_coman: dorion: well yes; you need to tell him what the business needs and to communicate as clearly as possible what the priorities are + ask for information/details when/as you require them (and preferably with reasonable time in advance too, obv); he needs to provide you with clear, useful and timely updates on the work and with notice (preferably with enough time in advance) of forks int the road/the need for decisions.

    diana_coman: jfw: dorion you know, those s.mg board discussions in public in #t were not just for MP's and my convenience or something.
    jfw: aha, could make good reading for illustration of putting this theory in practice
    diana_coman: when I say I claim no management expertise I mean it in a very practical term: I have much more experience with (and frankly, preference for) the tech role; it doesn't mean though that I have no idea whatsoever of anything that management does (though I am sure I don't know *all* there is to do there, either).

    dorion: diana_coman thanks for spelling it out. I read the s.mg meetings as instructional ; there's a big gap between reading and doing and the doing must be done.

    diana_coman: jfw: you know, that summary I linked only the other day for a different reason & all the graphics in eulora series and so on.
    jfw: the spelling out of the theory should also be helpful in seeing better what's going on in the reading
    diana_coman: yes, not all of the S.MG board meetings are public and not all documents can be public either; that's fine; but look at the pile that is anyway public and realise that there is even more behind it all.

    diana_coman: dorion: do you have some clear(er) idea as to what would be absolutely crucial from his tasks there? ie can you give him any help prioritizing stuff in there?
    diana_coman: even if you need to discuss further between the two of you, not necessarily right now.
    dorion: diana_coman still digesting and also wrapping up for travel. I'ma give it my closest read and ask questions as needed.
    jfw: I could perhaps help with that by spelling out the ?'s better as noted here
    diana_coman: timing is not the best for sure, yes; as mentioned earlier, I'd rather think it's fastest if you coordinate on this between the two of you and get it done but if there's any help you think I can provide, just ask/speak up.
    jfw: will do, thank you

    diana_coman: jfw: if you can spell them better, do it at least directly when talking to him, certainly.
    dorion: likewise, thank you diana_coman
    diana_coman: you're both welcome.

    jfw: who would be the best at this point to ask TRB questions? mod6 or trinque perhaps?
    diana_coman: jfw: trinque, if he is available.
    diana_coman: I'll ask him in his chan too.

    jfw: I have some familiarity with the source, and have previously implemented a 'getrawtransaction' RPC; a way to get raw block shouldn't be too different. But good to know when to escalate.
    diana_coman: jfw: so join #trinque anyway, I asked him in chan there and see.

    Comment by Jacob Welsh — 2019-11-21 @ 03:28

  3. Remaining tasks

    This list will surely need some revision upon contact with reality.

    What revisions, if any, are needed given subsequent conversations and where the plan stands today ?

    Comment by Robinson Dorion — 2019-11-26 @ 18:44

  4. [...] proposal will detail the software part of my wallet under development,(i) consisting of a security critical offline part and less sensitive online [...]

    Pingback by Gales Bitcoin Wallet spec and battle plan « Fixpoint — 2019-11-28 @ 04:51

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by MP-WP. Copyright Jacob Welsh.