Topic: 2-of-3 Paper Wallets - page 2. (Read 7679 times)

That's awesome and offers tons of flexibility. I can't wait to play around with this feature.


Exactly, the only thing you can do is preach about practice!  I didn't put any large amount in cold storage until I had reconstructed my wallet 3-4 times, I even did a fresh OS install and reconstructed again.

The problem with this is that "putting it in your will" is essentially equivalent to "giving it to your attorney".   Someone else has access to it in some capacity, since they obviously need to access it in the event that you die. 

Just like the bank employee snooping thing, it might be far-fetched, but some people are too paranoid.  I think it makes sense that your will would contain a significant portion  (say 2 of the 5 required pieces), making it considerably easier for your family to recover your funds once they see the will but not allowing your attorney full access to it if he "turns" on you.

There's a lot of permutations, and I fear that this could be "too complicated" for many folks.  I think I'll limit it to "require 2 or 3 fragments" below Expert usermode, and you can make any number of fragments.   By the way, the algorithm that I have implemented uses deterministic fragment generation.  i.e.  You require any 3 pieces to reconstruct the wallet.  You print out 5 such pieces.  Now lets say you decide too much risk is involved in losing a couple of the pieces, so you can print out fragments #6 and #7 and know that they will compliment the other pieces.  Or if one of your fragments is destroyed, you can reprint #2 and know it will be the same as before.

As for peace of mind that the fragments will reconstruct properly... I'm not sure how to do that "right".  I can show the user the result of recombining fragments (as I did in my first post in this thread, showing that I did the calculations and got the same answer, but that's not necessarily comforting to the user.  They won't be satisfied until they manually enter each fragment into a fresh version of Armory that's never seen the wallet, and they get the correct answer.  There's nothign I can really do about that.

This M-of-N system is a great feature and it will help many people, including myself sleep better at night. But . . . .
Since the subject of super paranoid people has already come up here, If I were that paranoid person, I would prefer a backup system like X+ M-of-N. Where X is the piece that is in my will.
I want to die before any of the pieces can be used. Is that something that could be possible with the current system that you're working on?

As I typed that out, I answered my own question. I think it is possible, if you split it into enough pieces and keep > 51% of the pieces required to recover your wallet for the will.

Example: Require 7-of-10 and put 4 pieces in your will.

Thanks for the explanation. This is exactly what I am waiting for to create the best fail-safe cold wallet backup. Also didn't know about the M-of-3 multisig restriction.

Talking of paranoia (I think it is legitimate when large sums of money are at stake) can you think of an easy way to validate if the backup is good? I mean 100% certainty.

The only way to be really sure imo would be to restore the cold wallet from the backup and see if you can spend the BTC - very time-consuming if you are of the mental paranoid type and want to try all combinations of a Shamir's Secret Sharing 3-of-6 backup. Plus as far as I know that compromises some of the security of the cold wallet, because the public key is broadcasted to the network if you use an address for the first time. Is there another less time-consuming way possibly without the need to publish the public key to check if all backups are working?

I've already described a similar use-case in one of the above posts, but I am considering doing this right now, so I thought it was appropriate to post here what I'm doing, and what the alternatives are.  I want a simple offline computer to conduct trade, and I want to back it up...

A quick note:  One of the benefits of Shamir's Secret Sharing is that if N pieces are needed to reconstruct the secret, having N-1 pieces is as good as having 0 pieces:  you have nothing.  Compare this to some scheme where by you simply split the private key into four 8-byte fragments... if you accumulate 3 of them, you only have to brute force 8 more bytes to get the fourth piece, which is completely feasible.  With this scheme, the last piece could be any N-bit (x,y) pair on the finite field plan, and no one point is any more likely than the others.

I emphasize this, because I don't want anyone reading to believe that somehow an attacker with 7 of 8 required pieces is a threat (outside of the fact that he has less remaining pieces to find than someone without any).  Those seven pieces are 100% useless without an eighth one.  It's one of the beauties of the SSS.

So onto the use case:

Right now, I have a wallet, backed up onto a single sheet of paper.  That sheet of paper by itself allows anyone who finds it, to recover all the coins in my wallet.  I have put a copy of this piece of paper in a safe-deposit box at the bank, for safe-keeping.  If a fire at my house destroys everything, I can still get my coins back with a visit to the bank.

Of course, the paranoids out there are concerned about bank employees snooping.  I would say it's being too paranoid, but to some extent you can't be too paranoid with BTC, since all security failures are completely untraceable and unrecoverable.  It would be impossible to prove that the employee did this.  And declaring that life is unfair does not get me my coins back.  Similarly, someone who breaks into my house finds one of my two sheets of paper will get all my coins.  

This is my point of comparison:  the fragility of the single-backup system.  You want to backup, but you don't want the vulnerabilities associated with it. I would propose a or 3-of-5 fragmented backup.  You put 2 pieces in the safe-deposit box at the bank.  You keep two at your house in different locations, as protection against losing one, and you give the 5th piece to a friend, family member, or your attorney (who should be good at keeping stuff).  Make it 3-of-6 if you are extra concerned about your house burning down, and give one to another friend.

A lot of things have to go wrong for this to fail.  The 2 pieces at the bank are useless without a third one, so no problem with snooping bank employees.  Someone breaking into your house, even if they find both pieces, will get nothing unless they also infiltrate the bank or break into your friend's house, too.  If your house burns down (and somehow both pieces are completely destroyed), you still have a friend/lawyer with a copy which compliments the third available at the bank.  If the banks disappears, you still have three pieces between you and your friend.

And even if somehow these things happen, they will usually not happen at exactly the same time that your offline computer dies.  Bank goes out of business?  Well open your offline computer, decrypt your wallet, and print the two pieces again and put them in another bank.  

And why would we do this instead of multisig?  Well, I don't want multisig.  I am still a single person using an offline computer to operate my business, and it's quite simple to use single-sig offline transactions without any extra complexities (plus, you can only go up to M-of-3 using multi-sig).  I just want a way to mitigate common side-channel compromises that are associated with my backups.

It's true that that's the use case, however I believe there's one other important use case: testing the system in order to feel comfortable with the process. If someone puts their savings into their armory wallet and prints out three pieces of paper, the first thing they're going to want to do is try to restore the wallet from the pieces of paper. The QR code makes that much easier. To be fair, I did that test by typing in the words, and it wasn't that bad.

It's also important to keep in mind the most likely failure mode. For instance, you could have a fantastic cryptographic system, an unhackable password, and a netbook that's completely isolated from the internet. And then the cable guy could slip a keylogger in your usb port, copy your encrypted wallet file, and come back a few days later to fix your router and take your password. That may be highly unlikely at this point, but infinitely more likely than somebody breaking a 160 bit password.

It appears I reinvented a bitcoin wheel:

https://bitcointalksearch.org/topic/pybtcsplit-m-of-n-private-key-splitting-made-easy-in-one-simple-python-utility-104086

I mean, it's a "standard" crypto trick, but it also looks like Vitalek created exactly the same thing 6 months.  And I probably could've used his code.  My solution uses a stupidly-inefficient version of matrix-inverse, but that's because it was ridiculously compact, and I thought 8-of-N would be overkill, anyway.   He says his could support up to 15-of-N and wanted to go up to 255-of-N.   Meh...



Yes, there will be QR codes everywhere.  But I don't have plans to implement a QR reader in Armory unless someone basically does it for me... it's annoying to type in paper-backup stuff, but it should be a once-every-3-years kinda thing for most users.

I like the idea of putting one in your will (that's essentially giving it to an attorney, though, isn't it?).   You could also have fun nesting these, if you weren't afraid of mind-blowing complexity -- split the secret into M-of-N, and then fragment some of the pieces further.  It would allow you to create asymmetrically-important fragments, so that each piece really just represents some fraction of the secret, some pieces worth more than others.

I guess you'd get the same thing from simply producing 100-of-N fragmenting, and distributing multiple pieces to each person/place.  Then you can keep 10% in your bookshelf, 30% in a safe-deposit box, etc.  That would be a ton of data, and QR codes probably wouldn't be very convenient either.  This really isn't all that useful, just kinda fun to think about ... It's late, maybe I should sleep instead...

That is the plan, correct, to have a QR code for each split paper backup that could scanned in easily?

With this feature you could keep a brain wallet by memorizing a passphrase but also backup the generated private key by splitting it N-ways among family, attorney, etc., in case of death, and put recombination instructions (and may one of the split QR codes) in your will.

@ Meni,

Sorry, I didn't mean to get defensive.  Just a misunderstanding.  Really the important part of what I was saying was: "This feature has no effect on my intention to finish and promote multi-sig wallets and all their wonderful features/benefits, and I totally agree with you that a proper multi-signature solution is still needed."   Perhaps I misunderstood the intention of the original post.

I think the misunderstanding (and the answer to deeplink) is that what I posted about doesn't have anything to do with spending your coins.  It's purely a backup thing so you can recover your single-signature wallet in 10 years when your offline computer finally bites the dust.  This is a terrible idea for spending coins -- if you want to require 2-of-3 things every time you spend coins, don't use this.  Use multi-sig wallets (which aren't available yet, but I'm working on it).

Context:  Right now Armory has a one-time-only paper-backup that will backup your single-sig wallet for ever.  I recommend you use it and keep a copy in a safe-deposit box and you'll never lose your coins.  You may not need it for 10 years, but then your HDD crashes and you can make one trip back to the bank to get it and recover your wallet.    Some people, though, are concerned about the physical safety of their paper backup (bank employees snooping, someone breaking into your house and finding it).  They would prefer that someone touching your paper backup doesn't get to clean you out instantly.

For actually protecting your day-to-day purchases from theft, you can increase your security (over Bitcoin-Qt) by using (1) Offline wallets, or (2) Multi-sig wallets.  Armory has #1 right now, and should have #2, soon.  And this split-backup thing has nothing to do with that.

I get that splitting the wallet and multi-sig are technically not the same, but isn't the end result exactly the same?

For example, if I want to backup a wallet on paper in different locations, but each one of those prints alone shouldn't be able to spend my coins, I can do either of the following:

1) use your split-wallet approach and if I want to spend the coins, rebuild the wallet with x-of-y prints

2) use multi-sig and if I want to spend the coins, collect x-of-y printed signatures

Alan, I'm not sure why you keep misunderstanding my comment, despite my effort to clarify it. Actually, I think my mistake is that I didn't notice we're in the Armory subforum, and my comments were more general.

From the OP:
To sleep better, the OP wants to have 3 pieces of paper where any 2 of them are needed to access his funds.

One way for this arrangement is to have a single-sig address where the private key is split into 2-of-3 secret-sharing pieces, and printing each piece on a different piece of paper.

A second way for this arrangement is to have a 2-of-3 multisig address, and print each of the associated private keys on a different piece of paper.

As you said, the first method is now available in Armory. That has its use cases (and is what the OP had in mind) and as I said, it's cool.

The second method is not yet supported by Armory or the larger Bitcoin ecosystem. It is a more secure way to use 3 pieces of paper than the first method, and because of this, it will be even cooler when this method is available. That's all I'm saying.

Of course there are many more use cases for multisig and all sorts of crazy combinations you can do. I am not implying one feature is supposed to be at the expense of the other. But using a 2-of-3 address for long-term bitcoin savings is the most important use case for multisig IMO, and I'm looking forward to its availability.

@Meni,

I think you're getting stuck on the idea that I have in some way proposed this idea as a replacement for multi-sig wallets.  This is not intended to replace multi-sig.  I'm not comparing it to multi-sig.  It's nothing to do with multi-sig, at all.  0% related.   It's simply an alternative for backing up your regular single-sig wallet.  Your single-sig paper-backup has all the security risks you describe, but it's still an important use-case that many users (and maybe even organizations) will use even when multi-sig is available.

Multi-sig is completely unrelated to this, and is still my number one goal for the new wallets.   Though, I guess you could technically create a 2-of-3 multi-sig wallet between multiple devices or parties, and each party could back up their own wallet using a M-of-N split-backup... sounds complicated.  In fact, I might try to discourage fragmenting multi-sig-wallet backups because of it being complicated (but there's no reason it couldn't still be done)...



Use-case 1:  simple user wants to use Bitcoin, and wants to have it backed up, but doesn't want any one user to have control of it.  He may create a 3-of-6 split-backup of his single-sig wallet, keep one, and give the others to five friends who don't know each other (and don't know who they'd even contact to find the other pieces).  

Use-case 2: These super-paranoid folks who think that someone at the bank will snoop in their safe-deposit box.  Okay, so use two safe-deposit boxes at different banks, distributing 2-of-3 pieces (keep one, put the other two in two different banks).  The likelihood of snooping is ridiculously low, but apparently still enough for the paranoids.  However, that stupidly-low probability is squared when it's two unrelated banks so even most tin-foil hatters would be satisfied.

Use-case 3: Simply hide a few pieces around your house.  As ben-abuya said, finding a single one won't be sufficient, but in 10 years from now when you need it, you'll surely be able to remember at least 3 of the 10 places you split it   (hell, hide one at your grandmother's house in one the 10,000 books she has on her bookshelves -- she doesn't even have to know or care that it's there)

That's amazing! Actually, one of the reasons it would be great to have this in the GUI is that you can create a QR code for each sheet of paper. That way it doesn't matter as much how much data there is. Netbooks have built in cameras and can easily scan the codes.

Meni, you're right about m-of-n transactions, they are certainly much more flexible and powerful. However, it's going to take a while for them to be properly implemented and managed by the Bitcoin community, and I see this as a great temporary solution.

Btw, etotheipi, I had the pleasure of meeting you at the Bitcoin Summit in Philly -- we were on the panel together at the end.

I understood this. What I mean is that if you store your private key exclusively on paper, storing it with 2-of-3 secret sharing still leaves a vulnerability when the shares are imported and combined (mitigated by combining in an offline clean computer, but still). If you have a 2-of-3 multisig address, and store the keys for that on 3 distinct pieces of paper, you get more security.

This is not a replacement for multi-sig.  It is to provide an alternative, flexible way to create and store paper backups.   Multi-factor auth wallets (linked wallets) are still coming... with the new wallet files... if I ever finish them...



EDIT: I see what I wasn't clear about -- this is for paper backups, not multi-sig wallet chains.  You will be able to print a single paper backup, or if you are in advanced/expert mode, you can choose M and N to print off an M-of-N paper backup.  Then it would print off a single piece of paper that can be cut with scissors into N strips, requiring any combination of M strips in order to recover your secret (or check a box to print N separate pages).

I just didn't want to do this with the current wallets, because each strip contains data that is 2x the size of the secret to be split, and the current paper backups already store 512 bits.  Thus, if you split your paper backup into 3-of-5 like my example above, in order to recover the secret you'll be typing 3 kB into Armory by hand!   That's a lot!  Originally, I was just planning to wait for the new wallets which will only require backing up 160 bits, which is a lot better (and about the best I can do).

Since someone explicitly asked about it just after I finished it, I decided to share that it's available already if you are willing to do some work.

@etotheipi: That's cool. Eventually though, multi-sig would be much cooler and safer than just secret-sharing a single private key.

---

Request:  This isn't exactly secret, but I didn't plan to release it yet.  So don't go telling all your friends, yet... let people stumble on this thread on their own

---

You're ridiculous!  I was going to keep this a secret until I released the new wallets, but that may still be a while, and the feature is technically already done.  If you hadn't specifically requested exactly what I just finished a few days ago, I was going to leave it to be part of mega-release with the new wallets

However, it's not integrated into the GUI, because the current wallets use a ton of data to represent a wallet, and splitting them results in each part being even 2x bigger.   The new wallets will use 160 bits instead of 512, making it a lot more "friendly" to apply this technique.   However, if you don't mind that it will be a ridiculous amount of data and you have some patience with the command line, you can do this right now! (It's so fresh though, you have to switch to the "armoryd" branch which is where I've been doing my latest development)

If you're into math, you might enjoy the description of how this works, at the bottom of this post.  For now,  here's some sample output from my unit-test:



The code that generated what is above is in unittest.py:



I'm not sure I can cram it into the GUI and subject users to typing in 1kB/fragment.  That's a lot of data!  I think I'll skip that for now, and just focus on finishing the new wallets and release it with that...

Enjoy!

---

The Math:  It's a super-elegant solution:  encode your secret into the coefficients of a polynomial, and then distribute points on that polynomial.  If it's a first-degree polynomial (line), two points are needed to solve the coefficients (and thus recover the secret).  If you want to require 3 points, use a second-degree poly (parabola).  Use higher order if you want to require more pieces.

The cooler part about this is that you have to use finite fields if you want any chance of this working with 256-bit numbers:  pick a large prime number, N, and do all operations modulo N.  This creates a cyclic group of size N.  Things like division are simply A/B = A*(B^(N-1)).  You can't do it with floats or doubles, because there's not enough precision to track all the significant digits in the variables and you'd die from the rounding errors.

And the coolest part is how little code was required to implement all the finite-field matrix operations in python!  There's nothing efficient about it, but it doesn't need to be efficient to be useful here.  It is still usable up to 8-of-N secret splitting -- it takes a couple seconds to reconstruct, but who cares!

+1

I've been playing around a lot with Armory as an offline wallet, and the one thing that would make me sleep better would be a 2-of-3 series of paper wallets. Right now you can only print a single wallet page, so if somebody breaks in to your house and gets it, they have all your coins. If Armory used something like ssss-split to print out three pages, where any two of them were needed, you'd be able to put them in three different places, making it very unlikely any thief would get to two of them. At the same time, you could lose one of three and still be able to reconstruct your wallet.

Does anybody else feel this would be a cool feature?