I would like to get community feedback on whether the following idea would be reasonable to write as an informational BIP proposal:


Boolean Addresses: Standardized p2sh addresses combining public keys, multisigs and time locks with arbitrary and/or-operations


Abstract
========
It is currently straightforward to create Bitcoin addresses which can be redeemed by a single key or an m-of-n multi signature. It is not as straight forward to create addresses that can be redeemed by, for example, key A or (key B and key C).

This proposal describes a consistent way to create s type of p2sh addresses (“Boolean addresses”) which can be redeemed by an arbitrary set of keys and multi signatures combined with logical and/or operations.


Examples

========
In the examples below, Alice has key A, Bob key B, Charles key C, etc).

Example 1:

A corporation has an account that can be spent by the CEO Alice or two board members (of Bob, Charles, David or Eric) in union. The account should allow signatures by "A or (2 of 4 of B, C, D, E)"


Example 2:


Alice wants a bitcoin address that she normally signs herself. However, if she has a fatal accident, she sets up a key "B" to be automatically mailed from a cloud service after a given time of inactivity to close relatives Charles, David and Eric. These relatives are also given keys written on paper.


Alice's address can be redeemed by "A or (B and 1-of-3 of C, D, E)". This way, if the cloud wallet key B is compromised or paper wallets C, D or E are stolen, it is not sufficient to redeem the address. If Alice’s key is lost, she can ask C, D, or E for their key and use key B to spend the address to a new one with a new key for Alice.


Motivation

==========
Standardisation of these addresses would allow interoperability for wallet software to create, sign and share signature requests for such addresses.


Implementation
==============
A Boolean address is described as a tree starting at a root node, where a node can be:

* An “and” operation, with a list of sub-nodes
* An “or” operation, with a list of sub-nodes
* A public key
* A Multisig operation n-of-m with a list of public keys
* A CHECKLOCKTIMEVERIFY operation

The implementation will describe a single well-defined way to generate a P2SH script from a given boolean address tree.

It will also define the ordering of sub-nodes for and and or operations.

The implementation will further detail how spending transactions are to be signed. A signature will consist of keys required for a given path through the tree. Signing an “or”- branch of the tree, will consist of a value specifying which or-subnode is signed, followed by the signatures for that node. That way, only one or-case has to be evaluated in the script.

For example, in the case of an account that can be redeemed by the example "A or (B and 1-of-3 of C, D, E)" from above, could be signed by something like:

0 (meaning evaluate the first sub-node of the or condition)
A

or

1 (evaluate the second sub-node of the top level or condition)
B
1 (One key for the multisig)
D (one of the 1-of-3 signatures)
0 (padding required for multisig opcode)