[TEASER] Multi-Sig Lockboxes! (Now with Simulfunding!)

[etotheipi]

Introducing Multi-key Lockboxes by Armory Technologies, Inc.

Armory Technologies, Inc. has come a long way since we incorporated 9 months ago.  We now have 5 full-time developers, and for the first time since I started Armory I was able to take my hands off the steering wheel, and focus on innovating, instead of just bug fixes and testing.  This gave me the opportunity to do something I've been wanting to do for a very long time... Multi-signature transactions!.  

I've been busy getting a form of multi-sig implemented before the conference this week (Apr 7-8), but without the new wallet format, yet.  This isn't a waste of time, because this kind of interface should be available for one-time escrow situations where you won't need a full wallet, anyway.  And in the short-term, it can used for low-volume, secure savings (when it's ready in a few weeks).

In the end, it turned out to be more than just a demo: it's actually quite usable!   See screenshots below.  If you can compile from github, you can play with it on the "multihacker" "devel" branch.  More details below.

Keep in mind the multi-key lockbox interface is an advanced tool.  All manual data exchange, multiple steps, multiple wallets, etc.  But just like offline transactions, I think we've taken something that is inherently quite complex, and made it about as simple as it can be without centralization.  We will be providing a server-assisted mode in the future which will make this far easier, but it will always be usable without a 3rd party service.

UPDATE: lockboxes are now being updated on the "devel" branch


Multi-key lockboxes:

WARNING: This is not ready for real money!  I have powered through the design process to get it demo-ready for the conference under time constraints.  Over the next couple weeks, we will be fixing all of it's limitations, reduce bugs, add simulfunding, and test it!  Until then, only use this with testnet!

A "lockbox" is created from a list of public keys (and some meta-data), and then anyone can put money into the lockbox.  To spend from the lockbox, one party initiates a transaction, and then circulates it to collect signatures.  Whoever adds the last signature can then broadcast it.





All data exchanged looks like the following example lockbox (go ahead and import it, see what happens):

Code:

=====LOCKBOX-kYzv3hKH===========================================================
AAAAAAsRCQc45UFTAAAAAMlTQQR0MnqhjDUOtCC9w72FXiWrsSVloX2Iu7uRJwbWxXoUXQtT2MrBd3wf
QwzZfEgkqMmqspb7zpfz9U/bPPFqVkdpQQRoaAc3x22ruAHLIgT1fb5ORXnk9xDNZ9wbQidZLIHptc8C
tayei0yfSb5SUQVram0BHkw39rbRft5rVfqiNRniQQR3uYP11MOuJ5kKfWBiRnEaIbaCDLKJplw5ymLH
e2H3Su4m9fPy3L1gOxKkrv5z7v5+R1PgCW3bFtmXRUhOFdf9U64TU3BvdXNlIEpvaW50IFdhbGxldAAD
AAAAEkRlc2t0b3AgSG90IFdhbGxldBVTYWxseSdzIE1vYmlsZSBXYWxsZXQSQmFja3VwIFNpZ25pbmcg
S2V5
================================================================================

Some great things about the current state of "Multi-key lockboxes":

• No central points of failure.  Private keys never exposed to any other device, and only used at time of signing much like offline transactions.  Armory lets you collect all public keys from all devices/parties, and creates a multi-signature address to deposit money in the lockbox.  
• Totally online/offline agnostic!  All circulated transaction data is treated as "offline" transactions, and thus includes data needed for secure offline review and signing!  You can mix any kinds of wallets you want, even do a 5-of-5 spread out between cold laptops kept in bank vaults in 5 different countries! (please don't do this yet, but it technically will be possible soon)
• Uses ASCII (base64) text blocks for easy exchange inline via email.   Armory used to use BIP 10, but that had some serious limitations.  A new format was created that accommodates all the quirks and security issues of exchanging data and offline signing (especially lots of complexities if P2SH is involved).
• Change is handled automatically:  It's handled by sending the change back to the exact same lockbox, which all remains transparent to the user, as always.  This is certainly "address reuse", but until we have multi-sig/linked wallets, we have no other choice unless you require the user to spend all or nothing.
• Completely decentralized:  We will add a server-assisted mode in the future, but we wanted to guarantee that it's theoretically usable if no servers exist.

Some current limitations of what's there:

• Plain multi-sig only -- limited to 3-of-3 on mainnet:  P2SH is theoretically supported, and I have designed all the data formats, and blockchain code to be able to accomodate P2SH.  But none of it has been tested, and requires a bit more complexity under the hood to make it work.  However, supporting P2SH will be required to go above 3-of-3 on mainnet, so it will be done. Eventually
• No simulfunding yet:  Certain types of contracts require both/all parties to send coins to the lockbox simultaneously (in the same transaction).  Again, I have designed the data formats to accommodate simulfunding, and even created a "Promissory Note" structure that can be exchanged like LOCKBOX and TXSIGCOLLECT blocks, but it's not complete yet.  Until then, these lockboxes are best suited when either (1) All devices are your own [you can't scam yourself], (2) All other parties are trusted, such as family members, (3)  Only one person is funding the lockbox.
• Expert tool!  All manual exchange of data: These are building blocks of multi-signature transactions.  Once we have all the mechanics in place, Armory will start hosting servers that will facilitate the exchange of this data (privately, of course!).  Until then, all data must be exchanged via email or shared folders.
• No signature merging yet:  Right now you must literally circulate the transaction to all parties, in any order.  Each party must sign it before passing it to the next party.  In the future, you will be able to send all parties the proposed transaction, they can each sign it and send it back, and the organizer can merge and broadcast
• All devices must be upgraded:  None of the data exchange formats are compatible with older versions

Using Lockboxes
You must be in Expert usermode on Testnet to use lockboxes!

• (1) One party/device is elected to make and organize the lockbox.  All other parties send them their public keys and contact info, etc (there's a new right-click menu in the wallet address table, to copy the hex public key).  If you are setting up a lockbox between multiple devices, you can simply use the addressbook buttons to pull the keys from watching-only wallets.
• (2) When the organizer is done creating the lockbox, and decorating it with contact info, lockbox description, etc, he will be given a "=====LOCKBOX" block of data to send to all the other parties.
• (3) Each other party will go into the lockbox manager and import the lockbox.  They will then be able to see its balance and transaction history only within the lockbox manage (from the the multisig menu)  There are no notifications.
• (4) Any party may send money to the lockbox by selecting it in the manager and clicking "Deposit Funds".  Or you can copy the ID into the regular "Send Bitcoins" window (from a regular wallet) in the following format "Lockbox[ID:z87Qnm42]".
• (5) To spend funds, one party is elected to create the spending transaction.  They click "Spend Funds" from the lockbox manager, which will open a regular dialog, but will only show UTXOs and balance of the selected lockbox.
• (6) Armory will open a "Signature Collector" window.   At any time, you can export the tx with all available signatures, to an ASCII block and email it inline to other participants, or put it on USB key or shared folder to get it to the other devices that need to sign
• (7) Once a sufficient number of signatures are present, the "Broadcast" button will appear.  Simply broadcast it and wait!

Final note:  No compiled versions will be available for a while.  If you can compile from the github repo, you are welcome to play with it and provide feedback, but we don't even want to give any hint that it might be usable for real money.  Check back in a couple weeks for updates!

Simulfunding is Implemented!

The simulfunding options menu.  Create notes, merge into a single tx, then sign and broadcast:


Each user selects a source wallet and destination lockbox to create a promissory note.  Then the organizer merges them into a funding transaction to be signed by all funders (right now no labels are passed through, so you only see how many participants there are and how much they are contributing, but not who is who...)


Once the promissory notes are collected, the parties have to sign.  This works identically to spend-from-lockbox (it's the same dialog).  Note that it only shows you the net value difference for each wallet, even though each "funder" is providing both inputs and change.  Armory figures it out.


As you can see, the final transaction has three different input wallets, and change back to those wallets as well.  

[Carlton Banks]

Looking forward to full rollout of this. Multi-sig keychains, where multiple private keys co-sign for a specific BIP32 Child Public Keychain, would be a real achievement (with change sent to a new address in the chain).

[etotheipi]

Looking forward to full rollout of this. Multi-sig keychains, where multiple private keys co-sign for a specific BIP32 Child Public Keychain, would be a real achievement (with change sent to a new address in the chain).

Yup.  That's where we're going next.  But we need a new wallet format to do that, and I wanted to get some usable multisig tools released before we go down that path.  Most of this will remain useful or at least can be recycled to support the full linked wallet solution.

[vinboy]

This feature may actually be very useful to the business world where multiple partners sig are required to access the wallet.
Very nice.
 

[killinitsoftly]

Damn guys.  This looks fantastic.
Love your work, keep it up. 

[etotheipi]

FYI, this was a big hit at the conference.  There's a lot of pent-up demand for this feature!  Even though it doesn't have all the privacy properties of a properly-implemented linked-wallet solution, the security achievable with it for low-volume transactions is awesome.

Since the conference, we have tweaked it quite a bit, and it's a lot more usable and stable.  We will be working on it over the next couple weeks and probably breaking it.  If you want to play with it and multihacker branch doesn't work, you can checkout this commit which is a very stable snapshot of the new functionality:

https://github.com/etotheipi/BitcoinArmory/commit/d8811a1c8892e373d6ff4de779ab2c75b5a21dc1

Seriously, try it out on testnet according the instructions in the top-post.  You really can setup multisig lockboxes with multiple offline computers,  review them, sign them, broadcast them, etc.  

[TierNolan]

Are you considering things like p2p messaging to support the transfer of the packets?

That goes against not exposing Armory to the internet though, except via bitcoind.

I see you know about the P2SH 'feature' where it doesn't properly check the size of multisig transactions, so you can bypass the 3 of 3 limit .

Does the public key effectively act as a root seed for a whole new branch of keys?  I guess the chaincode is computed from the root public key?

[etotheipi]

Are you considering things like p2p messaging to support the transfer of the packets?

That goes against not exposing Armory to the internet though, except via bitcoind.

I see you know about the P2SH 'feature' where it doesn't properly check the size of multisig transactions, so you can bypass the 3 of 3 limit .

Does the public key effectively act as a root seed for a whole new branch of keys?  I guess the chaincode is computed from the root public key?

For now, this is minimal.

-- At the time of the top post, P2SH wasn't implemented.  But now it is.  Should be able to go up to 7-of-7 on mainnet, unless I botched the calculation (can only use uncompressed keys, currently).  Unfortunately, the interface is capped to M-of-5, so you can't really help me test that yet unless you modify the source (it's really just one line to modify maxM and maxN)

-- This does not do any kind of parallel generation of keys.  It is used with a single public key for each party/device, and sends all change back to the same multisig with those original keys.  It was envisioned mostly for escrow transactions, though it can be used for savings (eventually) as long as you don't mind the privacy implications.  Or you can manually adjust the change. However, given the lack of multi-sig on the network, even if we sent to a new P2SH/multisig it would probably still be pretty obvious which is change and recipient.  At least until multisig is more widely-embraced.

By the time this matters, we'll have a proper linked-wallet solution that generates parallel address chains and produces a new address for every receive and change output.

[TierNolan]

For now, this is minimal.

-- At the time of the top post, P2SH wasn't implemented.  But now it is.  Should be able to go up to 7-of-7 on mainnet, unless I botched the calculation (can only use uncompressed keys, currently).

Yeah, I saw the calculation at 20 or something, but compressed vs uncompressed could explain that.

-- This does not do any kind of parallel generation of keys.  It is used with a single public key for each party/device, and sends all change back to the same multisig with those original keys.  It was envisioned mostly for escrow transactions, though it can be used for savings (eventually) as long as you don't mind the privacy implications.  Or you can manually adjust the change. However, given the lack of multi-sig on the network, even if we sent to a new P2SH/multisig it would probably still be pretty obvious which is change and recipient.  At least until multisig is more widely-embraced.

Cold wallets with a board of directors is a potential use.  It lets them remain completely separate.

Each director can see all incoming payments, but can only sign one of them.

[etotheipi]

For now, this is minimal.

-- At the time of the top post, P2SH wasn't implemented.  But now it is.  Should be able to go up to 7-of-7 on mainnet, unless I botched the calculation (can only use uncompressed keys, currently).

Yeah, I saw the calculation at 20 or something, but compressed vs uncompressed could explain that.

-- This does not do any kind of parallel generation of keys.  It is used with a single public key for each party/device, and sends all change back to the same multisig with those original keys.  It was envisioned mostly for escrow transactions, though it can be used for savings (eventually) as long as you don't mind the privacy implications.  Or you can manually adjust the change. However, given the lack of multi-sig on the network, even if we sent to a new P2SH/multisig it would probably still be pretty obvious which is change and recipient.  At least until multisig is more widely-embraced.

Cold wallets with a board of directors is a potential use.  It lets them remain completely separate.

Each director can see all incoming payments, but can only sign one of them.

Just posted it here:  https://bitcointalk.org/index.php?topic=587895.msg6443351#msg6443351

The protocol considers M-of-20 to be valid, but their's a standardness limit at M-of-3 for plain multisig, and a 520-byte total-script-size limit on redemption of P2SH multisig -- that corresponds to M-of-15 if all keys are compressed, or M-of-7 if uncompressed.

[dexX7]

The protocol considers M-of-20 to be valid, but their's a standardness limit at M-of-3 for plain multisig, and a 520-byte total-script-size limit on redemption of P2SH multisig -- that corresponds to M-of-15 if all keys are compressed, or M-of-7 if uncompressed.

Ah, so the 520 byte limit only applies to the redeem script, but not to the full scriptSig? I assumed it's slightly less due to the signature(s) and script itself, to be more specific:

[1 byte, null] ([1 byte, signature length] [71-73 byte, signature]) x m [1-2 byte, redeem script length] [1 byte, m] ([1 byte, public key length] [33 or 65 byte, public key]) x n [1 byte, n] [1 byte, OP_CHECKMULTISIG]

Which would lead to: 1-of-13, 2-of-10, 3-of-8 or 4-of-6 with compressed keys and a bit luck.


(I have no idea, if this is correct, thus the question.)

[etotheipi]

The protocol considers M-of-20 to be valid, but their's a standardness limit at M-of-3 for plain multisig, and a 520-byte total-script-size limit on redemption of P2SH multisig -- that corresponds to M-of-15 if all keys are compressed, or M-of-7 if uncompressed.

Ah, so the 520 byte limit only applies to the redeem script, but not to the full scriptSig? I assumed it's slightly less due to the signature(s) and script itself, to be more specific:

[1 byte, null] ([1 byte, signature length] [71-73 byte, signature]) x m [1-2 byte, redeem script length] [1 byte, m] ([1 byte, public key length] [33 or 65 byte, public key]) x n [1 byte, n] [1 byte, OP_CHECKMULTISIG]

Which would lead to: 1-of-13, 2-of-10, 3-of-8 or 4-of-6 with compressed keys and a bit luck.


(I have no idea, if this is correct, thus the question.)

At least the way it's described on the wiki, there's a 520-byte limit on any PUSHDATA operation... each sig is ~ 70 bytes (with DER encoding bytes) so no problem there.  But the last PUSHDATA pushes the multisig script onto the stack -- so the multisig script must be no bigger than 520 bytes.  it's indepdendent of the number of signatures -- there's a separate limit for the total script size.

[etotheipi]

And one more feature before the Amsterdam conference!  Simulfunding!  This one will probably need some documentation, though.  This is actually very similar to manual CoinJoin, but right now limited to sending to a single lockbox.  The idea is that certain contracts/escrow will require multiple people to fund a lockbox at the same time, and there was no clean way to do it before I implemented this.

• Create the Lockbox:  Pick an organizer.  All parties send a public key to the organizer.  He merges them into a lockbox, and sends the LOCKBOX block out to everyone to import into their lockbox manager
• Simulfunding:  All parties that are funding the lockbox will create a "promissory note".  This is a list of inputs, a change address, along with how much you are committing to funding and fee.  The organizer collects and merges all PROMISSORY blocks into a single transaction.  Its SIGCOLLECT block is passed around for signing, just like a regular lockbox-spend
• Spend from Lockbox:  One party creates the proposed spend from the lockbox, and sends the SIGCOLLET block to everyone for signing.  

Btw, on the latest devel branch, merging of signatures works, so you don't have to exactly circulate it anymore:  just send it out to everyone and you can "Import/Merge" them into the "Review & Sign" window -- it will recognize you loaded the same tx and merge the signatures into the one already loaded (before, you had to sign it and pass it to the next person to accumulate sigs)

There's still some quirks with simulfunding, but it does work!

P.S. -- And of course everything works with offline computers  All the messages/blocks that are passed between devices assume everything is offline.  You can do simulfunding between N offline devices, and spend from a lockbox between N offline devices.  I'm sure there are some services claiming to do multisig, but they don't have that kind of flexibility!


The simulfunding options menu.  All users create promissory notes.  One person merges them into a tx.  Then all funders sign it.


Each user selects a source wallet and destination lockbox to create a promissory note.  Then the organizer merges them into a funding transaction to be signed by all funders (right now no labels are passed through, so you only see how many participants there are and how much they are contributing, but not who is who...)


Once the promissory notes are collected, the parties have to sign.  This works identically to spend-from-lockbox (it's the same dialog).  Note that it only shows you the net value difference for each wallet, even though each "funder" is providing both inputs and change.  Armory figures it out.


As you can see, the final transaction has three different input wallets, and change back to those wallets as well.  

[teste]

Question: Only who created Multi-key Lockbox can propose a spend? or any of the participants?

[etotheipi]

Question: Only who created Multi-key Lockbox can propose a spend? or any of the participants?

Each step is independent.  Once the lockbox is created, anyone can create a proposed spend and distribute for signing

[omegaflare]

Basically a lockbox is where you can pool in fundings? Or is it like no one can access that lockbox until it has two out of three (yourself included) public keys to access that lockbox?

Let me know!

[etotheipi]

Basically a lockbox is where you can pool in fundings? Or is it like no one can access that lockbox until it has two out of three (yourself included) public keys to access that lockbox?

• Collect N public keys from the wallets of N parties or devices
• The organizer creates the M-of-N lockbox.  
• Anyone and everyone can send money to it.  You can distribute the P2SH address for receiving.
• To move the money, one person creates a spending transaction, sends it to each party/device for signing
• When it has M signatures, it can be broadcast.

For instance, you could have three laptops.  One at home (hot or cold), one in safe-deposit box A (cold SDB A) and one in safe-deposit box B (cold SDB B).  Set up each SDB laptop in the privacy room at the bank.  Take the watching only copies with you.  Use all three watch-only wallets to create a 2-of-3 lockbox.  Put money in it.  Now, in order for an attacker to take your money, they need to break into your house and one safe-deposit box to fetch signatures, or they need to get to both safe-deposit boxes.   When you want to move that money, you simply create the tx at home, sign it, take it to one of the SDB's, get a second signature.  Take it home and broadcast.

For a company, this is perfect.  Each director creates a wallet, merges public keys into, say, 3-of-5 lockbox.  Company funds are held in there.  Even if each/most of the director's used hot wallets, the security model is much stronger than most of the alternatives (because you've eliminated central points of failure).  You could even keep like 5% in a 2-of-5 wallet with the same keys.  If that disappears, you know that the 3-of-5 is close to being compromised and can regenerate a new 3-of-5 with different wallets and move the funds there.

[plethora]

I have a question about Simulfunding.

What exactly is being transmitted when a user sends the signed TXSIGCOLLECT back to the organizer? I guess it's my signature to allow sending my specified amount from my specified wallet. But what's to prevent the organizer to use my signed transaction twice?
What if the organizer doesn't sign and broadcast their part of the transaction until, let's say, 2018? Perhaps there should be a time limit. Do we currently have to manually empty the wallet if the transaction isn't made or you could get the funds sent sometime in the future when it might come as a surprise?

[etotheipi]

I have a question about Simulfunding.

What exactly is being transmitted when a user sends the signed TXSIGCOLLECT back to the organizer? I guess it's my signature to allow sending my specified amount from my specified wallet. But what's to prevent the organizer to use my signed transaction twice?
What if the organizer doesn't sign and broadcast their part of the transaction until, let's say, 2018? Perhaps there should be a time limit. Do we currently have to manually empty the wallet if the transaction isn't made or you could get the funds sent sometime in the future when it might come as a surprise?

The easiest way to describe simulfunding is that it is a contract:

You both put the terms into the contract ("I will send 10 BTC if you send 10 BTC"), then you both sign it.  Just like a regular legal contract, one person signing the contract doesn't mean half the contract is executed.  You are signing all parts of the contract (in this case, the transaction), and it's either executed fully, or not at all.

The TXSIGCOLLECT is simply the transaction proposing sending money from both parties to a single target.   When you sign it, you're not just signing your part, you're signing the entire transaction, including their contribution.  If they never sign it, the transaction is never valid and money never moves.   

The whole point of simulfunding is that there is exactly zero risk of one party getting screwed. 

[plethora]

It seems the last signer (or organizer) has the advantage of choosing when the transaction takes place and the money is withdrawn from all others' wallets. What if this person waits one week, one month or one year? Well, you could just send the money to some other wallet I guess so that it's impossible for the organizer to complete the transaction a long time later if you wish to "cancel" the transaction.

If they never sign it, the transaction is never valid and money never moves.   

My point is, how do you know if they never sign it? They might just be very, very slow