Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: etotheipi on November 28, 2012, 04:00:19 AM



Title: New wallet file ideas
Post by: etotheipi on November 28, 2012, 04:00:19 AM
I am in-process of doing a full rewrite of Armory wallets; not just to improve the design, but to enable tons of new features.   However, I think this time I want to collect input from others before I go ahead and just do it my own way.  I'd like some feedback before I'm too committed to it my way.  

There are two major features I want to implement in the wallet that are "forward-thinking."  There's a lot of other stuff going in, but these are the two that warrant a real discussion.   Some quick background:  the new wallets will be based on BIP 0032 (https://en.bitcoin.it/wiki/BIP_0032) so that they will be compatible with future Satoshi wallets, and get all the nice features of hierarchical deterministic wallets.  There will have the ability to store multiple wallets/chains/accounts per file.  There will also be a way to merge wallets.  And, I want the wallet to handle P2SH scripts elegantly.  

However, P2SH engenders some complications in the wallet design.  P2SH was designed to hide scripts, thus you cannot just search the blockchain for multi-sig tx involving you -- you must actually save the (TxID, p2shScript) pair somewhere so you can recognize and find it later.  This is really annoying from the wallet-backup perspective:  all P2SH scripts must be backed up immediately to avoid potential of losing coins, but you also don't want your primary wallet to be copied around everywhere.  For instance, I think Dropbox is ideal for backing up P2SH scripts and tx/address comments, but should the user should never backup his entire wallet to Dropbox.  And I don't trust users to manually&responsibly set up reliable backups.   With that in mind:

  • (1) Paired-wallet support (two-factor auth):  Each wallet/chain/account will have a field to specify another wallet/chain/account.  If that field is present, it signifies this is a "paired" wallet -- Armory will expect to have a watching-only copy of the second wallet in the same file.  It will never generate single-sig addresses -- it will only generate P2SH scripts requiring a signature from both wallets (design will also accommodate 2-of-3 and 3-of-3 wallet combos).  All multi-sig scripts will have public keys added to them in the order of the wallet IDs -- the wallet with the lower binary fingerprint/ID will always have its address first, etc.  By doing this, devices with complimentary wallet combinations (A'B and AB') will generate the same, completely deterministic chain of 2-of-2 payment addresses.    This means that in either wallet, I can say "get me address index 37", and it will fetch PubKeyA[37] and PubKeyB[37], and put them into a P2SH 2-of-2 script and return the associated payment address.  This makes P2SH for two-factor-authentication schemes completely deterministic, and will look almost identical to a regular wallet.  (for two-factor auth, you don't need ((A and B) or C) transactions, you just use (A and B) and backup both wallets to where you would otherwise backup wallet C)
  • (2) "Lightly encrypted" P2SH and Comments files:  There are still situations where you need to backup your scripts:  escrow transactions with strangers on the internet, or various other contracts, etc.  Also, it would be nice to backup your comments/labels too, but not worth risking your whole wallet to do it.  So the user will be able to enable an external "wallet" file containing only these scripts & comments ("wallet" in quotes because it stores no keys).  Whenever you save a comment or P2SH script, it will save it to both files. Most importantly, these scripts and comments will be encrypted with AES256 using HMAC(walletRootPubKey, walletRootChainCode) as the encryption key.  Therefore, this external file can be backed up just about anywhere, even Dropbox, because the holder needs [at least] the watching-only wallet to decrypt it.  Someone who compromises only your Dropbox account will not have that wallet, and thus your privacy is maintained.  If your HDD crashes, you can restore your deterministic wallets/chains/accounts from your backup, and merge the Dropbox'd file into it and you're back to where you were before the HDD crash.  This not only saves your P2SH scripts from failure, but gives you a way to preserve all your address comments/labels, too (i.e. -- it's useful even for non-P2SH wallets).  The default behavior will be to not have an external file, but to allow the user to specify a location to create it that will be backed up regularly.

Edit:  Some might suggest you could always get the P2SH script from the other party if you lose your wallet.  My response is:  what if you stored their contact information as a comment in your wallet file?  This system would preserve both comments and P2SH scripts on an insecure channel without compromising privacy.

Number 2 is a bit crazy, but I think it solves a unique problem introduced by P2SH, as well as providing extra options for users deciding how to keep their P2SH/comments file backed up.




Title: Re: New wallet files -- recommendations invited
Post by: justusranvier on November 28, 2012, 04:11:17 AM
For instance, I think Dropbox is ideal for backing up P2SH scripts and tx/address comments, but should the user should never backup his entire wallet to Dropbox.  And I don't trust users to manually&responsibly set up reliable backups.
This won't work for everyone, but for those people who have it installed Freenet is ideal for storing data like this. For that matter you could securely backup the entire wallet in Freenet.


Title: Re: New wallet files -- recommendations invited
Post by: etotheipi on November 28, 2012, 04:46:35 AM
For instance, I think Dropbox is ideal for backing up P2SH scripts and tx/address comments, but should the user should never backup his entire wallet to Dropbox.  And I don't trust users to manually&responsibly set up reliable backups.
This won't work for everyone, but for those people who have it installed Freenet is ideal for storing data like this. For that matter you could securely backup the entire wallet in Freenet.

Sure, I was using Dropbox as a common example of a reliable backup system someone would want to use, but hesitate because of the security concerns.   But there's lot of other systems people could use to do this backup -- but with this method, it doesn't have to be a secure channel to maintain your privacy.


Title: Re: New wallet file ideas
Post by: casascius on November 28, 2012, 05:27:43 AM
As I look through BIP 0032 and see the suggestion for serializing extended public and private keys in Base58, I'm sort of turned off by the fact that the resulting strings have no useful visible prefix.  Any way we can change this before getting serious about implementations involving BIP 0032?

The BIP calls for 74 or 75 bytes starting with a "version" byte of 0x06.  This results in strings in the following ranges: CHp9i78Gq2z9cmoCwmasob3nLUfDMfhQPmRGAF12dARaUfsEi33j6UbWSe3SdRnfBbtqQmGZEFP5qvrD9amMVcbUuxZA znDwP1hKDNTKYb thru EAx1Vd9V8hz1PQGEwEMBwMPaZPbv5n9UHtpe27fhZXL1PcgGzYPWn4CG1utBZqFbt33UUiypGTSmKRA5WM4QuiXZZnUs L5Rm7M9N2fPpqe for 74 bytes, and rqD7SS36s1mF2tiwijnXEdHH6y5fYDoLFV45uno8AcbUm8YjW832oAoJxAVn7nQXXo1nftPfFUUUNxgCct2mTJ7CCkD1 82c72A4vu1oa9UR thru 218uoBLYTB1tchsgGWMv7Gtzf7xm7J6GPTZjGPvRp2YrtipUMayYNRs6hH2QuduySxG1vHNHmdDiicHd4tXY4XgHtjhk1 9CYHh1uvD9aCV8b for 75 bytes.  That means these strings could start with any character within "CDErstuvwxyz12".  Yikes!  How does one know by looking that such gibberish serves any specific purpose?

I'd like it much better if instead of worrying about conserving the "Version byte space", we considered the visual prefix space as seen by humans.

If instead of 0x06 and 0x0C, we used 0x0488B21E and 0x0488ADE4 plus 74 payload bytes, the resulting prefixes would be "xpub" and "xprv" respectively.  0x043587CF and 0x04358394 yield tpub and tprv (for testnet).  If instead of specifying "use 32 bytes for a private key and 33 bytes for a public key", we specified "use 0x00 + 32 bytes for a private key" (knowing public keys always start with 0x02 or 0x03), then the payload beyond the prefix would always be 74 bytes, and we wouldn't have base58 prefixes that change drastically because the message length changed.  One could know by looking just what they are looking at.

As for the original question (how to safely persist P2SH scripts), I have input on that as well but am still contemplating whether it's sensible.


Title: Re: New wallet file ideas
Post by: casascius on November 28, 2012, 05:44:45 AM
Here is what I think on P2SH persistence: I think the paired wallet idea is a great way to go.

Perhaps there should be such thing as a "relationship object": an object that exists for each party to the relationship, which includes that party's private objects, the pattern of keys that can be created in the relationship, and the public keys/objects of the other parties.  A "paired wallet" would be one type of relationship, but despite a pair sounding like a couple, a relationship could have many more parties than just two.

The first party proposes the relationship as a text record and decides how many vacancies are in it, and that record is transferred to other parties/devices, who in turn generate text records offering to fill those vacancies, much like creating a certificate signing request to acquire an SSL certificate.  When all parties/devices have all the records, they should all produce a single "relationship hash" acknowledging mutual understanding of the terms, at which point, the user(s) of the P2SH system can reconcile and confirm amongst each other that they have backed up the private goodies for each role in the relationship with hash H, and finally, address generation can occur by the parties/devices who have been authorized to do so.

P2SH addresses would be generated deterministically from the relationship object which must be backed up by each party to the relationship when the relationship is created, but no backup is ever necessary for the keys it produces.

Sample exchange in forming a relationship

1. Party/Device A creates a record that says: "I propose an (A AND B)" relationship.  I want to be A, here is my public chain code.  I'm looking for a B to offer a chain code."

The record could go on to say "In this relationship, new addresses should be issued by parties in this list: [A,B]".  One party could be responsible for all the issuing (e.g. if party A is a computer and party B is merely a smartphone app for confirming transactions).  Or, if multiple parties are authorized to issue addresses, then (for example) A issues addresses having sequence mod 2 == 0, and party B issues sequence mod 2 == 1. (replace 2 with the number of parties able to issue addresses).

2. Party/Device B is fed that record and agrees.  It creates a record saying "I agree to be the B for proposal whose hash is X. Here is my public chain code."

3. That record is transferred back to party/device A.  They each agree that a relationship H has been formed, where H is 32 bits of the hash of all the public keys etc going into the relationship record.  When all parties/devices acknowledge being parties to relationship H, and the user(s) have safely backed everything up, then they can start issuing addresses.

Defined this way, a "relationship" becomes a supertype of a wallet... a normal wallet can then be defined as merely a "relationship" with one party (self) who has the only private chain code and who itself issues all addresses.


Title: Re: New wallet file ideas
Post by: Pieter Wuille on November 28, 2012, 08:01:53 AM
As I look through BIP 0032 and see the suggestion for serializing extended public and private keys in Base58, I'm sort of turned off by the fact that the resulting strings have no useful visible prefix.  Any way we can change this before getting serious about implementations involving BIP 0032?

Well, I have little problem with changing the serialization of the extended public/private keys if it's worth it. Whatever preliminary implementations exist, I doubt they have more than the internal key derivation mechanism.

I've generally given up on the human recognizability aspect of Base58 - if we wanted that, base64 or base32 would be far better choices, as they allow prefixing/suffixing with bit/byte arrays without affecting every single encoded character.

Quote
The BIP calls for 74 or 75 bytes starting with a "version" byte of 0x06.  This results in strings in the following ranges: CHp9i78Gq2z9cmoCwmasob3nLUfDMfhQPmRGAF12dARaUfsEi33j6UbWSe3SdRnfBbtqQmGZEFP5qvrD9amMVcbUuxZA znDwP1hKDNTKYb thru EAx1Vd9V8hz1PQGEwEMBwMPaZPbv5n9UHtpe27fhZXL1PcgGzYPWn4CG1utBZqFbt33UUiypGTSmKRA5WM4QuiXZZnUs L5Rm7M9N2fPpqe for 74 bytes, and rqD7SS36s1mF2tiwijnXEdHH6y5fYDoLFV45uno8AcbUm8YjW832oAoJxAVn7nQXXo1nftPfFUUUNxgCct2mTJ7CCkD1 82c72A4vu1oa9UR thru 218uoBLYTB1tchsgGWMv7Gtzf7xm7J6GPTZjGPvRp2YrtipUMayYNRs6hH2QuduySxG1vHNHmdDiicHd4tXY4XgHtjhk1 9CYHh1uvD9aCV8b for 75 bytes.  That means these strings could start with any character within "CDErstuvwxyz12".  Yikes!  How does one know by looking that such gibberish serves any specific purpose?

I don't consider this a priority anymore. A human will need to know what type of data it encodes anyway before using it.

Quote
I'd like it much better if instead of worrying about conserving the "Version byte space", we considered the visual prefix space as seen by humans.

If instead of 0x06 and 0x0C, we used 0x0488B21E and 0x0488ADE4 plus 74 payload bytes, the resulting prefixes would be "xpub" and "xprv" respectively.  0x043587CF and 0x04358394 yield tpub and tprv (for testnet).  If instead of specifying "use 32 bytes for a private key and 33 bytes for a public key", we specified "use 0x00 + 32 bytes for a private key" (knowing public keys always start with 0x02 or 0x03), then the payload beyond the prefix would always be 74 bytes, and we wouldn't have base58 prefixes that change drastically because the message length changed.  One could know by looking just what they are looking at.

Ok, I admit I like that. I'll ask around whether anyone objects. Instead of 0x00 + privkey, I'll use privkey + 0x01, so that it matches the serialized private key format exactly (which has a 0x01 at the because the corresponding public key is compressed).


Title: Re: New wallet file ideas
Post by: casascius on November 28, 2012, 02:11:14 PM
I'll use privkey + 0x01, so that it matches the serialized private key format exactly (which has a 0x01 at the because the corresponding public key is compressed).

I don't believe this will work, because you won't be able to disambiguate when you have 33 bytes that begin with 0x02/0x03 and ends with 0x01, how do you know whether that's a public or private key?  You won't.

Besides, I have this cunning plan to start canvassing, writing a BIP to propose consensus seeking on base58 visual prefixes, and asking us to deprecate the "serialized private key format" you mention, and let the world rid itself of Bitcoin private keys that start with "L", which force users to ask "wtf is the difference between a '5' and a 'L' private key?  how about 'K' and 'L'?" and forcing TMUI(too-much-useless-information) down their throats just to understand Bitcoin.  It will most likely be to use 0x82 instead of 0x80 as a prefix byte (so the keys are still visually distinct in the 2nd character for those interested in compressed status at a glance), and then continue to accept the existing K/L format on a basis where it is universally acceptable as input (for compatibility) but propose that new keys in the old format never be emitted.


Title: Re: New wallet file ideas
Post by: Pieter Wuille on November 28, 2012, 02:23:51 PM
I don't believe this will work, because you won't be able to disambiguate when you have 33 bytes that begin with 0x02/0x03 and ends with 0x01, how do you know whether that's a public or private key?  You won't.

Because you yourself proposed putting "xpub" or "xprv" at the beginning. There is never a question of which one you are working on.


Title: Re: New wallet file ideas
Post by: casascius on November 28, 2012, 02:27:06 PM
I don't believe this will work, because you won't be able to disambiguate when you have 33 bytes that begin with 0x02/0x03 and ends with 0x01, how do you know whether that's a public or private key?  You won't.

Because you yourself proposed putting "xpub" or "xprv" at the beginning. There is never a question of which one you are working on.

Yes, you are right, that makes sense.  Count me up for one missing the obvious! :)


Title: Re: New wallet file ideas
Post by: etotheipi on November 28, 2012, 10:48:10 PM
Re: "Relationship Objects"

I like the idea of defining "relationships" and having that be defined somewhere. However, where would it be stored?  I really think that however it is done, it must be coded into the wallet:  the user should never be in the position that they recover this wallet and think it's a single-sig wallet.  I want wallets to be dedicated to multi-sig or not.  If a user doesn't want multi-sig, create a regular wallet.  (easy for me to say, Armory is a multi-wallet app)

To me, it would be ideal if two-factor auth wallets were always generated by an offline computer.  It would create both wallets and generate 3 things to print:   paper backup of AB, A'B and AB' (where A is full wallet and A' is watching-only wallet).  AB goes into a safe-deposit box, A'B is entered into one device (desktop), AB' entered into the other device (smartphone).  Those could be backed up, too, in separate locations, with less security each than the AB backup.  A physical burglar would have to find both to compromise the funds.   I don't want to see A backed up separately from B. I really want the user to be backing up the wallet after the linkage has been defined in the wallet, so it's obvious from the backup that it is a multi-sig wallet and to which other wallet it is linked.  

The problem is, not all users want to do this with an offline system.  The desktop could make both and then just delete B (after it's backed up).  But some users want the keys to never be on the same device, ever.  There will probably have to be an interface to convert a regular wallet to a paired wallet, and allow users to merge them at a later time.  Perhaps, it is as simple as popping up a warning, suggesting they make a new backup when a link is created.

For escrow transactions and contracts, etc, I think you have to allow a regular, single-sig wallet to generate a private key intended to be used for this purpose.  This would be signified by the stored P2SH script in the wallet file, which would contain both public keys (and your own will be easily identifiable).  When the wallet is loaded, it will search all stored P2SH scripts and identify how they relate to your wallet.  But that will need to be backed up the moment you generate it.  I just don't see another way to be totally safe about this without using something as persistent as Dropbox (what other backup options are there for this, besides keeping this extra file on a network drive on another system, or external device?)




Title: Re: New wallet file ideas
Post by: casascius on November 29, 2012, 01:06:08 AM
Re: "Relationship Objects"

I like the idea of defining "relationships" and having that be defined somewhere. However, where would it be stored?  I really think that however it is done, it must be coded into the wallet:  the user should never be in the position that they recover this wallet and think it's a single-sig wallet.  I want wallets to be dedicated to multi-sig or not.  If a user doesn't want multi-sig, create a regular wallet.  (easy for me to say, Armory is a multi-wallet app)

In my view, the wallet IS the relationship, or at least a file representing one party's participation in a relationship.  Multiple relationships means multiple files, one file per party per relationship.  The data defining the relationship would be in the root structure of the wallet file, along with the party's own private keys and the other parties' public keys.  This would be consistent with the view that a regular wallet file was simply a "relationship" file where number of parties is 1 and that party has the one and only private key.


To me, it would be ideal if two-factor auth wallets were always generated by an offline computer.  It would create both wallets and generate 3 things to print:   paper backup of AB, A'B and AB' (where A is full wallet and A' is watching-only wallet).  AB goes into a safe-deposit box, A'B is entered into one device (desktop), AB' entered into the other device (smartphone).

The proposal I speak of would preserve this ability.  Although I proposed that party A issue some record proposing a relationship and party B issued a record accepting the proposal, nothing stops A and B from being a single program running in a trusted environments and producing both records and printing them to separate pieces of paper.

Given that offline computers are something that come easy for you and me, and the popularity of smartphones among everybody else, I envision the most popular use case scenario being where party A is a computer, B is the same person's smartphone.  In this case, the "relationship record" goes from A to B in the form of a camera scanning an on-screen QR code, and where the returned record travels from the smartphone back to the computer via E-mail, or removable flash media, or the user just bearing it and hand-typing the response record off their phone's display onto their computer via keyboard.  Private key material for A is backed up by printing it, and private key material for B is backed up by the user writing down a wordlist-encoded record they see on their phone's screen.

Once such a relationship is set up, users would initiate transactions on their computer (A), and their on-computer client would show QR code (or a series of them if the transaction was large) containing the proposed transaction and the party A signature.  The smartphone would display the transaction details on screen, get the user's consent, provide the party B signature, and send it all directly to the bitcoin network itself.


Title: Re: New wallet file ideas
Post by: casascius on November 29, 2012, 01:18:28 AM
For escrow transactions and contracts, etc, I think you have to allow a regular, single-sig wallet to generate a private key intended to be used for this purpose.  This would be signified by the stored P2SH script in the wallet file, which would contain both public keys (and your own will be easily identifiable).  When the wallet is loaded, it will search all stored P2SH scripts and identify how they relate to your wallet.  But that will need to be backed up the moment you generate it.  I just don't see another way to be totally safe about this without using something as persistent as Dropbox (what other backup options are there for this, besides keeping this extra file on a network drive on another system, or external device?)

For escrow transactions and one-offs where creating and backing up a relationship would be a burden, I see P2SH as the wrong tool for the job.  This might be more suited for a simple regular multisig transaction where the redemption script goes into the block chain and is based on normal keys in a normal wallet.  The purpose of P2SH as I understand it is to push the multisig burden off the sender and onto the receiver and to make sure that users and websites not interested in using multisig can always send coins to people who are, with a normal-looking and normal-sized destination address.  This burden shifting doesn't make much sense if three consenting individuals want to deliberately participate in a complicated transaction.

Such a transaction could be formed much like a relationship (in the sense that there's a "proposal" and "acceptance"), but would be far simpler.  If Alice wants to send coins to Bob and use escrow agent Eddie, then Alice and Bob could each send a fresh bitcoin address of their own to Eddie, and then Eddie could formulate a large and cumbersome "address" that contained the entire multisig script serialized within, and then Alice would just send the coins to it.  Both Alice and Bob's clients would automatically recognize an incoming but "encumbered" transaction, and both Alice and Bob would have the option to create a transaction proposal that would have to be sent to Eddie, signed, and released by him for the funds to go anywhere.


Title: Re: New wallet file ideas
Post by: etotheipi on November 29, 2012, 01:46:41 AM
For escrow transactions and contracts, etc, I think you have to allow a regular, single-sig wallet to generate a private key intended to be used for this purpose.  This would be signified by the stored P2SH script in the wallet file, which would contain both public keys (and your own will be easily identifiable).  When the wallet is loaded, it will search all stored P2SH scripts and identify how they relate to your wallet.  But that will need to be backed up the moment you generate it.  I just don't see another way to be totally safe about this without using something as persistent as Dropbox (what other backup options are there for this, besides keeping this extra file on a network drive on another system, or external device?)

For escrow transactions and one-offs where creating and backing up a relationship would be a burden, I see P2SH as the wrong tool for the job.  This might be more suited for a simple regular multisig transaction where the redemption script goes into the block chain and is based on normal keys in a normal wallet.  The purpose of P2SH as I understand it is to push the multisig burden off the sender and onto the receiver and to make sure that users and websites not interested in using multisig can always send coins to people who are.  This burden shifting doesn't make much sense if three consenting individuals want to deliberately participate in a complicated transaction.

I was under the impression that P2SH was intended for all multi-sig transactions, though you are right there is no reason plain-text multi-sig can't be used (is there? they were probably never added to isStandard...).  One reason for desiring P2SH, in general, is that very long scripts become part of the TxIns instead of the TxOuts.  This means that they will never bloat a pruned version of the blockchain.  If everyone only used P2SH, then no TxOut script would ever be longer than 22 bytes.


Title: Re: New wallet file ideas
Post by: casascius on November 29, 2012, 01:54:11 AM
I was under the impression that P2SH was intended for all multi-sig transactions, though you are right there is no reason plain-text multi-sig can't be used (is there? are they yet considered isStandard?).  One reason for desiring P2SH, in general, is that very long scripts become part of the TxIns instead of the TxOuts.  This means that they will never bloat a pruned version of the blockchain.  If everyone only used P2SH, then no TxOut script would ever be longer than 22 bytes.

If plain multi-sig transactions became the de facto standard for contracts and one offs, it's unlikely they'd accumulate on the block chain.  An unspent transaction of that sort represents unspendable money that somebody somewhere would like to have unencumbered, so they're unlikely to leave it sitting in a state like that for a long time.  The moment Eddie releasing the transaction that commits to Bob getting the money, the fat transaction becomes ripe for pruning.

The IsStandard could be resolved simply by offering an option that says "make sure my transaction gets sent to this/these miner(s)" and getting somebody somewhere to agree to mine them into a block.  That of course ignores the overwhelming likelihood that the whole Bitcoin community will immediately realize the value and will accept defining such a transaction as worth relaying.


Title: Re: New wallet file ideas
Post by: etotheipi on November 29, 2012, 02:03:06 AM
I was under the impression that P2SH was intended for all multi-sig transactions, though you are right there is no reason plain-text multi-sig can't be used (is there? are they yet considered isStandard?).  One reason for desiring P2SH, in general, is that very long scripts become part of the TxIns instead of the TxOuts.  This means that they will never bloat a pruned version of the blockchain.  If everyone only used P2SH, then no TxOut script would ever be longer than 22 bytes.

If plain multi-sig transactions became the de facto standard for contracts and one offs, it's unlikely they'd accumulate on the block chain.  An unspent transaction of that sort represents unspendable money that somebody somewhere would like to have unencumbered, so they're unlikely to leave it sitting in a state like that for a long time.  The moment Eddie releasing the transaction that commits to Bob getting the money, the fat transaction becomes ripe for pruning.

The IsStandard could be resolved simply by offering an option that says "make sure my transaction gets sent to this/these miner(s)" and getting somebody somewhere to agree to mine them into a block.  That of course ignores the overwhelming likelihood that the whole Bitcoin community will immediately realize the value and will accept defining such a transaction as worth relaying.

I don't want to get side-tracked on the philosophy and use-cases of P2SH (though, I do agree, I much prefer plain multi-sig for escrow/contracts).  Even if users agreed to use plain multi-sig and avoid necessitating such backups, there's probably plenty of information in their wallet that is nearly-critical to have backed up -- perhaps contact information stored with the wallet, order numbers of various transactions, identities associated with non-wallet addresses, etc.  A lot of this isn't widely used now, but I expect it will be with the URI spec -- I've been pushing for contact information and order numbers to be included in URI strings so that when a merchant requests payment for something, they can auto-document the transaction for the buyer by pre-filling those fields which will end up in the user's wallet.  Even without P2SH, the user has a strong interest in securing that data (and users always fail if effort expenditure is required for a seemingly-non-essential operation).



Title: Re: New wallet file ideas
Post by: casascius on November 29, 2012, 02:23:52 AM
I don't want to get side-tracked on the philosophy and use-cases of P2SH (though, I do agree, I much prefer plain multi-sig for escrow/contracts).  Even if users agreed to use plain multi-sig and avoid necessitating such backups, there's probably plenty of information in their wallet that is nearly-critical to have backed up -- perhaps contact information stored with the wallet, order numbers of various transactions, identities associated with non-wallet addresses, etc.  A lot of this isn't widely used now, but I expect it will be with the URI spec -- I've been pushing for contact information and order numbers to be included in URI strings so that when a merchant requests payment for something, they can auto-document the transaction for the buyer by pre-filling those fields which will end up in the user's wallet.  Even without P2SH, the user has a strong interest in securing that data (and user's always fail if effort expenditure is required for a seemingly-non-essential operation).

Agreed - I don't mean the user shouldn't have to do backups, I just mean we should reduce the number of transaction types that require the user to make an immediate backup or else risk a financial loss in the event of a data loss... the whole purpose of having the deterministic key chains in the first place, and what I understood a core element of the original problem to be as described in the OP.

Another thing that occurred to me, is if Eddie is in the professional escrow business, P2SH could still be used, with Eddie having primary responsibility for backing up the script (given that he already has agreed to accept primary responsibility for releasing the transaction in the first place).  Eddie could still propose a multi sig transaction, but instead of Alice sending coins to a huge string, instead, Alice would receive a record allowing her to confirm that P2SH destination X is really what she thinks it is (which could be done on a public website instead of being built into any given client), and then she just pay the P2SH address.  We could leave the backup responsibility to Eddie, and relieve Alice and Bob of the burden.

Let's assume for a moment that Eddie only has backed up his deterministic wallet chain code and not the individual P2SH script belonging to Alice and Bob, and suffers a data loss.  While not trivial, it would still be possible for Eddie to recover that P2SH script from the hash just by taking Alice and Bob's submitted bitcoin addresses, and combining them with all of the keys coming from Eddie's chain code until the result is a match.  Even that potential burden could be completely eliminated simply by e-mailing the P2SH "destination verification" data to Alice and Bob, as in the event of Eddie's hard drive crash, Alice and Bob could recover the script from their e-mail.

Seems to me the ideal escrow transaction is (A AND E) or (B AND E) or (A AND B).  This way, in the event of disappearance of the escrow agent, Alice and/or Bob can release the coins to one another by submitting a transaction paying the other, requiring that other person's signature.


Title: Re: New wallet file ideas
Post by: Mike Hearn on November 29, 2012, 01:12:02 PM
Alan, did you look at the payment protocol discussions happening on bitcoin-development? Some of it may be relevant to this work.

Re: P2SH/normal, I agree with Mike that P2SH is not always the right tool for the job. It was designed on the assumption that people will want to use short addresses and that may well turn out to be true, but if we successfully move most payments to use a payment protocol (as we're going to try) then addresses will start to fade away as a user-visible part of Bitcoin and that rationale goes away. It leaves P2SH being purely a UTXO set size optimization, which like any optimization must be weighed against the additional complexity it introduces. If it's going to make the user experience worse, it's better to just use regular scripts.

Mike, escrow is indeed meant to work as you describe but using 2-of-3 multisig which boils down to (A AND E) or (B AND E) or (A AND B):

  https://en.bitcoin.it/wiki/Contracts#Example_2:_Escrow_and_dispute_mediation

A think a lot of these things become easier to reason about when you assume a payment protocol.


Title: Re: New wallet file ideas
Post by: Gavin Andresen on November 29, 2012, 01:35:41 PM

I was under the impression that P2SH was intended for all multi-sig transactions, though you are right there is no reason plain-text multi-sig can't be used (is there? they were probably never added to isStandard...).  One reason for desiring P2SH, in general, is that very long scripts become part of the TxIns instead of the TxOuts.  This means that they will never bloat a pruned version of the blockchain.  If everyone only used P2SH, then no TxOut script would ever be longer than 22 bytes.
You can use plain multisig if you like, they WERE added to IsStandard.


Title: Re: New wallet file ideas
Post by: etotheipi on November 29, 2012, 05:08:50 PM

I was under the impression that P2SH was intended for all multi-sig transactions, though you are right there is no reason plain-text multi-sig can't be used (is there? they were probably never added to isStandard...).  One reason for desiring P2SH, in general, is that very long scripts become part of the TxIns instead of the TxOuts.  This means that they will never bloat a pruned version of the blockchain.  If everyone only used P2SH, then no TxOut script would ever be longer than 22 bytes.
You can use plain multisig if you like, they WERE added to IsStandard.

Ahh, so it does make sense to use P2SH for paired/linked wallets, and regular multi-sig for escrow tx, etc.  For some reason, I was under the impression that P2SH was intended for everything.  I do prefer plain multi-sig for those escrow tx.

@Mike,

I'm not sure the payment protocol changes this much.  It means that the decision about which form to use will be irrelevant to those using the payment protocol, but there will still be users who will do it the "old" way, which should still be accommodated.  Though it sounds like we already have a consensus ... it makes sense to use P2SH for linked wallets, and regular multi-sig for isolated escrows and contracts.





@Casascius:  I was just about to post an expanded idea for linked wallets, but I think you already did it.  I'll restate it, though, for clarity, and maybe add a little.

Let's say I make wallet A/j, and my spouse creates wallet B/j.  We exchange the root of the external/internal chains.  Meaning, we exchange the data needed to not just generate one chain of addresses, but both the primary chain and change chain.  

So, I give her A'/j and she gives me B'/j.  All addresses generated by my wallet will be of the form 2of2([A'/j/0/x, B'/j/0/x]) and all change will go to 2of2([A'/j/1/y, B'/j/1/y]) -- external chain is 0, internal chain is 1.  The order will be switched for her wallet:  she will create addresses of the form 2of2([B'/j/0/x, A'/j/0/x]) and change will go to 2of2([B'/j/1/y, A'/j/1/y]).  So each wallet will only generate addresses from its own two chains, but watching for addresses on all four chains.  

I'm pretty sure that's very similar to what you suggested.  


EDIT: to avoid ordering issues for 3+ wallets, the addresses should be ordered by wallet fingerprint order, and each wallet always generates addresses starting with their own in that list, wrapping around.  So if the wallet fingerprints end up ordering the wallets  B, A, C,  then all 2-of-3 addresses generated by wallet B will be {B,A,C}, wallet A will be {A,C,B} and wallet C will be {C,B,A}.  That makes sure there are only N possible address orderings (one per party), instead of N-factorial


Title: Re: New wallet file ideas
Post by: casascius on November 29, 2012, 05:45:59 PM
With regard to ordering of wallets I never imagined this to be a problem. Mainly because in my mind, somebody would be proposing the relationship with a specific number of vacancies which may or may not be equivalent in purpose. If A were to propose (A AND B) OR C, someone entering that relationship needs to explicitly be choosing slot B or slot C, there would be no ambiguity as to what party is in what slot and they cannot just simply take the first available slot.  Further, I imagine that when the relationship was defined, each of the roles would either be allowed or not allowed to generate addresses. (If B is just a smartphone validating A's transactions, then it would be a waste of resources to assign a chain for B it will never use, but which A will have to walk up and down that chain looking for transactions at great CPU expense just in case it somehow did).

If I use those assumptions, then the field containing the list of parties able to generate addresses would dictate a fixed order and also dictate how to manage the chains so that all parties know where they generate from, assuming they are set to be able to.

I have more reading to do on the contracts and chains and how they work, so it is probable that my assumptions reflect a deficient understanding of those.


Title: Re: New wallet file ideas
Post by: etotheipi on November 29, 2012, 06:07:26 PM
With regard to ordering of wallets I never imagined this to be a problem. Mainly because in my mind, somebody would be proposing the relationship with a specific number of vacancies which may or may not be equivalent in purpose. If A were to propose (A AND B) OR C, someone entering that relationship needs to explicitly be choosing slot B or slot C, there would be no ambiguity as to what party is in what slot and they cannot just simply take the first available slot.  Further, I imagine that when the relationship was defined, each of the roles would either be allowed or not allowed to generate addresses. (If B is just a smartphone validating A's transactions, then it would be a waste of resources to assign a chain for B it will never use, but which A will have to walk up and down that chain looking for transactions at great CPU expense just in case it somehow did).

If I use those assumptions, then the field containing the list of parties able to generate addresses would dictate a fixed order and also dictate how to manage the chains so that all parties know where they generate from, assuming they are set to be able to.

I have more reading to do on the contracts and chains and how they work, so it is probable that my assumptions reflect a deficient understanding of those.

My understanding is that we don't have real capability to do ((A and B) or C) yet (or at least, it's not standard), and that only M-of-N multisig is really enabled.  I know you could execute any arbitrary script if you find a miner to do it for you, but that's not in scope for me -- I'm sticking with transactions that will be accepted by the network without special actions.  (I just confirmed with Gavin that non-M-of-N transactions are not standard; redeeming such a P2SH script would require a miner's help)

However, I agree that the design here should be extensible to these cases, when they become available in the future.  But it also seems unnecessary to require extra user-interaction for regular M-of-N transactions where the specific ordering is actually irrelevant to the users, as long as it is deterministic and accessible to all participants.    As a user entering a 2-of-3 wallet with two other parties, I don't actually care what order they go in, and asking the user to specify a totally arbitrary ordering is not only confusing, but ripe for people to do it wrong -- i.e. user A chooses {A,B,C}, but user B accidentally sets up their wallet with {B,A,C}, and then things get all out of whack...

Also, I don't see a reason why there should be a special case for desktop+second-factor (smartphone) vs shared-spouse-wallets.  Just have all 2-of-2 wallets pretend that both chains could be used, because the resource usage of watching for a few extra addresses is trivial.  If it's really a concern, there can be an option in "Expert" usermode to disable the second device chain if you know it won't be used.  



Title: Re: New wallet file ideas
Post by: Jutarul on November 29, 2012, 06:18:40 PM
While you're doing a rewrite, you may consider adding support for output "attributes".
E.g. projects like the colored bitcoins would vastly benefit from code like that (https://bitcointalk.org/index.php?topic=106373.0), because their algorithms needs to keep track of the color state of individual outputs.


Title: Re: New wallet file ideas
Post by: etotheipi on November 29, 2012, 06:25:28 PM
While you're doing a rewrite, you may consider adding support for output "attributes".
E.g. projects like the colored bitcoins would vastly benefit from code like that (https://bitcointalk.org/index.php?topic=106373.0), because their algorithms needs to keep track of the color state of individual outputs.

I already have an "extraAttributes" field which is intended to accommodate non-Armory addresses and address chains.  I don't know who else would be leveraging the code base, but at least it gives me room to, say, import and maintain an Electrum-deterministic wallet chain and store any necessary extra information in that field that doesn't fit into the Armory-specific structure.   I'm not sure of exact implementation details, yet, but I do want to try to leave room for things I haven't thought about, yet.  I suppose colored-coin attributes could go there, too.



Title: Re: New wallet file ideas
Post by: casascius on November 29, 2012, 06:48:47 PM
My understanding is that we don't have real capability to do ((A and B) or C) yet (or at least, it's not standard), and that only M-of-N multisig is really enabled.  I know you could execute any arbitrary script if you find a miner to do it for you, but that's not in scope for me -- I'm sticking with transactions that will be accepted by the network without special actions.

With what I had in mind, you wouldn't be restricted to any specific pattern of multisig transactions, the data structure could support any kind of multisig relationship imaginable.  You would still restrict users' ability to create such relationships to the ones you consider in scope of course, but the file format itself would accept any.

Here is how I imagine a "relationship" data structure, let's do something weird: (A AND B) OR (C AND D AND E) OR (F AND A) OR ANY5OF (A,B,C,D,E,F), and C,D,E are the ones who can issue addresses.
Code:
Relationship
  Number_Of_Parties = 6
  I_Am_Party = A
  Multisig_Script = OP_WHATEVER pubA OP_WHATEVER pubB OP_WHATEVER pubC etc...
  Address_Issuing_Parties = C,D,E

  Party
    Position=A
    Description=Captain
    PrivateChain = xprvxxxxxx
    PublicChain = xpubxxxxxx

  Party
    Position=B
    Description=First Officer
    PrivateChain = unknown
    PublicChain = xpubxxxx

  Party
    Position=C
    Description=Flight Attendant
    PrivateChain = unknown
    PublicChain = xpubxxxx

  Party
    Position=D
    Description=Flight Attendant
    PrivateChain = unknown
    PublicChain = xpubxxxx

  Party
    Position=E
    Description=Flight Attendant
    PrivateChain = unknown
    PublicChain = xpubxxxx

  Party
    Position=F
    Description=Air Marshal
    PrivateChain = unknown
    PublicChain = xpubxxxx


This structure would originally be created by A, but with "unknowns" for the public keys for B,C,D,E,F, and serialized into a block of text.  That block of text would be sent to the five other parties, who would recognize "OK, this is a multisig proposal with vacancies, which one should I join? First Officer, Flight Crew, or Air Marshal?".  The clients of those parties would emit a record proposing to join the position they chose.

When all six parties have their own record, plus the five of the other parties, they should all recognize the group relationship and be able to start participating in it.

However, I agree that the design here should be extensible to these cases, when they become available in the future.  But it also seems unnecessary to require extra user-interaction for regular M-of-N transactions where the specific ordering is actually irrelevant to the users, as long as it is deterministic and accessible to all participants.    As a user entering a 2-of-3 wallet with two other parties, I don't actually care what order they go in, and asking the user to specify a totally arbitrary ordering is not only confusing, but ripe for people to do it wrong -- i.e. user A chooses {A,B,C}, but user B accidentally sets up their wallet with {B,A,C}, and then things get all out of whack...

At some point, one of the parties must take the initiative and decide "I'm creating a multisig wallet relationship, and the style will be 2-of-3".  I am imagining the process similar to the CSR request for SSL certificates.  At some point, when setting up SSL on a website, one party (web site operator) initiates the deal generating a CSR that says "I'm so-and-so, here is my public key, and I propose the creation of a certificate that looks like x".  The other parties to the deal accept the proposal and respond with "Here is the certificate you asked for".  Someone always has to go first, and there is nothing wrong with tying special responsibilities - like defining the proposed relationship - to the party who does.

At some point, all three parties must exchange some record so that they learn the public chain codes of the other parties.  If they didn't do this, they would never be able to recognize incoming transactions belonging to the relationship.  I see this step as unavoidable.

However, I do see a possibility that several of the roles could be equivalent.  My example above has three "Flight Attendants".  It could be defined that these positions are equivalent in purpose, and that which specific relationship member gets spot C, D, or E, is dictated by numerical order of a hash, rather than forcing the user to pick a spot deliberately hoping another member didn't pick the same one.

At some point, all three parties software must have the ability to express to the human user that they in fact all have the same parameters and keys in mind.  I propose they do this by emitting a hash of the serialized relationship record containing all the public keys in the relationship.  When the clients of all parties to the relationship say "Relationship Successfully Formed: Relationship ID F1175A23", the users can know that all parties are on the same page, and that (for example) party C didn't accidentally use a key that came from somewhere else.


Also, I don't see a reason why there should be a special case for desktop+second-factor (smartphone) vs shared-spouse-wallets.  Just have all 2-of-2 wallets pretend that both chains could be used, because the resource usage of watching for a few extra addresses is trivial.  If it's really a concern, there can be an option in "Expert" usermode to disable the second device chain if you know it won't be used.  

I am not sure I understand how the resource usage is small.  I understand a chain can be used to generate unlimited addresses.  How should the software come to know that of all the addresses generated by party B (for example), the one with sequence number 10,000 has a transaction that needs to be checked for, even if all addresses 0 thru 9999 don't?  I see no way other than actually generating all those addresses just in case and checking them all, and then there is no guarantee that 10000 or any other number is enough if you can't assume how the other party will be using addresses they generate.  While such sparse utilization seems counterintuitive on the surface, it's not all that unusual if you consider that someone setting up an e-commerce web server might pre-generate a huge number of addresses assuming most will be wasted, and then give them out in an arbitrary order (e.g. alphabetical sort instead of the order in which they were actually generated).  If my assumption that the only way for party A to truly know if party B has never received funds at addresses he has issue is to perform an operation that is unbounded in resource usage, it seems prudent to clip it from the start if the use case makes it clearly unlikely to be used.  This of course discounts your assertion that "the resource usage of watching for a few addresses is trivial" - if I have overlooked something and this assertion is guaranteed to always be true for a reason I haven't considered, then yes I agree that it would be a waste to bother with an option that disables address generation roles for parties.


Title: Re: New wallet file ideas
Post by: kjj on November 29, 2012, 09:41:21 PM
I am not sure I understand how the resource usage is small.  I understand a chain can be used to generate unlimited addresses.  How should the software come to know that of all the addresses generated by party B (for example), the one with sequence number 10,000 has a transaction that needs to be checked for, even if all addresses 0 thru 9999 don't?  I see no way other than actually generating all those addresses just in case and checking them all, and then there is no guarantee that 10000 or any other number is enough if you can't assume how the other party will be using addresses they generate.

This.

For occasional interactions, I think that each party should just accept the burden of keeping track of everything they need.  For p2sh, it means keeping a copy of the completed redeemScript (which generally means having all of the pubkeys).  The whole point of using pubkeys is that they can be public, so the service that collects keys can also distribute them when done.

For regular interactions, and particularly when you want to define a stream, each party should generate a new set (seed and chain secrets), and then the problem is reduced a bit to merely passing around names and indexes.  If ABCDEFGHIJK are keys in some complicated scheme, they can be taken to mean AiBiCiDiEiFiGiHiJiKi, when given i, so everyone knows how to generate their part of it.

By the way, for regular X-of-Y multisig, I find it VERY useful to sort the pubkeys before assembly.  In fact, I wish that the default behaviors of createmultisig and addmultisigaddress in the stock client were to sort, possibly with an option to not-sort.


Title: Re: New wallet file ideas
Post by: etotheipi on November 29, 2012, 11:39:37 PM
@Casascius,

I recognize that you are proposing something of ultimate flexibility and versatility.  And I actually really like the idea for arbitrarily complex transaction types.  But M-of-N transactions are a degenerate case of that large space of possible transaction types.  Combined with the fact it will be spectacularly more-common than those other cases, I think it's not unreasonable to have a separate "shortcut" method for setting them up.  

However, I do like where your idea is going, and worth some further discussion.  I'd really like to have a way to document and execute these crazy transaction types, I just think a fully developed solution for that is out-of-scope for now.  I think I will leave room in my design to accommodate "relationship" entries in the wallet.  When it is fully developed, I can switch all multi-sig tx over to that...

Though, why can't such relationships be developed by a central organizer?  Rather than distributing the relationship object and letting each person pick a place... there is at least one person that already knows how it should be setup.  Have everyone send that person a public key/wallet, and he will set it all up.  Perhaps the final result can be signed by the private keys of all included public keys, or something like that.

But for now, I think it makes sense to shortcut the couple degenerate cases of 1-of-2, 2-of-2, 2-of-3, 3-of-3, and handle all the details automatically for the user.  A user simply wants the transaction to require 2 of 3 signatures, and has his own private chain and the other two public chains.  He doesn't care about the internal ordering of keys, but he does require everyone to use the same ordering.  He also wants to avoid address collisions in the event that multiple parties try to create transactions at the same time with the same ordering.  I think this technique resolves all of that, and can be represented quite simply to the user.



The issue with look-ahead in deterministic wallets is an annoying problem.  Most regular users, really don't need more than 10 addresses lookahead, 100 to be safe.  However, e-commerce users/merchants might need significantly more lookahead than that.  For that reason, I defaulted to 100 address lookahead with Armory, and added a button to let users extend the lookahead as far as they want.  I expect that any business users interested in this application, will have the knowledge to know which knobs to tweak -- i.e: set lookahead to 10,000 addresses & disable second chain.  

Therefore, Armory users using two-factor auth as I have described, only have 100 extra addresses in their wallet.  One time.  If the second chain is never used, then it never increases.  The way Armory scans the blockchain, search time is O(log N) in the number of addresses in the wallet (because they're stored in a BST in RAM, so that's how long it takes to check if an address is in your wallet).  As such, 100 extra addresses is trivial, both in HDD space, and extra computation time.  If the user needs more than 100 lookahead, they are also likely knowledgeable enough to know what options to change for their application.


Title: Re: New wallet file ideas
Post by: casascius on November 30, 2012, 12:48:30 AM
That works for me and am satisfied just by that you understand what I propose well enough to decide whether it's appropriate for inclusion in your client, even if the answer is no.


Title: Re: New wallet file ideas
Post by: etotheipi on November 30, 2012, 01:02:48 AM
That works for me and am satisfied just by that you understand what I propose well enough to decide whether it's appropriate for inclusion in your client, even if the answer is no.

The answer is:  you just seeded an excellent discussion about the far future of Bitcoin escrow/contracts, but I think that future hasn't arrived yet.  And when it does arrive, I'd love to see that discussed and developed into an inter-client standard.  Until then, the M-of-N cases are dramatically simpler, and can actually be used right now, thus it warrants a separate [simpler] treatment :)  (plus, there will probably be some lessons learned from M-of-N execution to be applied to the more-general case)



Title: Re: New wallet file ideas
Post by: etotheipi on December 02, 2012, 08:22:34 PM
Another idea was just proposed to me, which I really like.  Out of scope for the first two ideas I presented, but completely relevant for a new wallet design:

Encrypted watching-only wallets

Some users have expressed concern that, although their BTC is safe if their online laptop is stolen because they keep their coins offline, the person that stole their laptop now knows their identity and the fact that they own $50k in BTC.  It would be best if the thief had no information at all...

As such, I'm thinking I could add an extra layer of encryption, to encrypt the public keys, addresses and transaction IDs stored in the wallet.  This "outer" encryption would use the same encryption scheme as the one used for private keys, but it would only have to be entered once when the app is started and would have no timeout .  This means that the data is always stored on disk encrypted, and the decrypted version only exists in RAM.

It would also be nice if all such wallets (per-computer?) had the same encryption.  So if you have multiple wallets, you still only type your passphrase once.  I can see it getting out of hand when you have multiple devices with different addresses, and then start juggling wallets around.  But there's only so much I can do about that...


Title: Re: New wallet file ideas
Post by: Mike Hearn on December 03, 2012, 12:06:32 AM
That sounds like duplicating operating systems existing support for disk encryption.


Title: Re: New wallet file ideas
Post by: etotheipi on December 03, 2012, 12:20:54 AM
That sounds like duplicating operating systems existing support for disk encryption.

Is it?  What if you want your watching-only wallet encrypted but you don't have disk encryption setup?  What if you don't know how to setup disk encryption?  Wouldn't the same argument apply to the private keys, too?

Tell me if I'm wrong, but I think there's another key advantage (but I don't know much about the way these things are implemented).  If you use FS encryption, then once you've booted and your OS has requested and unlocked the filesystem encryption, then anyone who gains access to your system while it is running will be able to read that file, even if they got access to your system remotely (the OS will decrypt for them).  But if it's done at the application level, then the file will always be encrypted, and the only way for them to get the info will be to pull it out of your memory space.  I'm pretty sure that is "difficult."  But I don't know for sure...