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://bt.irlbtc.com/view/106373.0), because their algorithms needs to keep track of the color state of individual outputs.

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.

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.


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.



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.

@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.

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)

That sounds like duplicating operating systems existing support for disk encryption.