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)