BIP 124: Hierarchical Deterministic Script Templates #246

Defines a generalized script template format for wallet interoperability.

http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011795.html

I really don't like the lexicographic sorting of keys. Why not assuming that when m's are chosen, the order is important.

Instead of defining a particular key by using Sort_i(K_k) it is way easier to use K_k,i.

Worse than that. Normally a key derivation m_i should define a particular function for all the k derived keys (for example, "temp keys" in HTLC). If you use lexicographic order, Sort_i(K_k) will not refer to a key which has the same function as Sort_i(K_k+1)

So for example in multi sig take

K/k = {m₁/k,m₂/k,m₃/k}

Where m is derivation respectively of Alice,Bob,Satoshi.

Sort₁(K₁) may define Alice but Sort₁(K₂) will define Bob. This is odd... It might not matter for multi sig because the order of keys does not matter as long as everybody agrees the same. But this is a special case.

Better say K_1,1 define first key of Alice, K_2,1 second one etc...

@NicolasDorier Ordering of keys is really important, see BIP67 - https://github.com/bitcoin/bips/blob/master/bip-0067.mediawiki

@NicolasDorier

What use-cases does sorting prevent? It's just as stateful a process as "sort in the order of [Alice, Bob, Satoshi] always", but sorting addresses a privacy leak, and is a bit more universal (and if everyone sorts, there's one less barrier to wallet interoperability)

I would think software advanced enough to perform signing should be able to tell which public key is it's own, and add the signature irrespective of the actual ordering scheme?

@btcdrak I know this bip and never enforced it in what I develop because there is stricly no utility into doing that. @afk11 , except if I don't understand the goal of what is called "group key" here is an example (but if I understand correctly, the concept of group is only useful in multi sig scenario thus hurting the generic aspect of this BIP):

Let's take this contract sample (don't need to understand, this is only for my point)

OP_IF
        OP_DUP OP_HASH160 <Alice pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
        <TIMEOUT> OP_CHECKLOCKTIMEVERIFY OP_DROP
        OP_DUP OP_HASH160 <Bob pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

If I wanted to represent this contract as in this bip I would define the following group.

K/k = { m₁/k, m₂/k }

m₁ is Alice choice m₂ is Bob choice

If I rewrite this script according to this BIP you may be tempted to define a template as

OP_IF
        OP_DUP OP_HASH160 Sort1(Kk) OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
        <TIMEOUT> OP_CHECKLOCKTIMEVERIFY OP_DROP
        OP_DUP OP_HASH160 Sort2(Kk)  OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

Except that Sort1(K1) may represent Alice key for the first transaction, but for the second transaction Sort1(K2) may represent Bob's key in the following way

1st transaction based on the template

OP_IF
        OP_DUP OP_HASH160 Sort1(K1)==m1/1==Alice OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
        <TIMEOUT> OP_CHECKLOCKTIMEVERIFY OP_DROP
        OP_DUP OP_HASH160 Sort2(K1)==m2/1==Bob  OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

2nd transaction based on the template

OP_IF
        OP_DUP OP_HASH160 Sort1(K2)==m2/2==Bob OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
        <TIMEOUT> OP_CHECKLOCKTIMEVERIFY OP_DROP
        OP_DUP OP_HASH160 Sort2(K2)==m1/2==Alice  OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

Because the sorting is done on the actual public keys derived with k as currently specified.

I don't see why ordering should be done at all. When one define a group of key, you can define any order at this moment.

if you want to define a multi sig contract by using this template language, with address reuse you have no need of lexical ordering:

Define K/k and number of signature required. K/k's order being significant no lexical ordering is needed.

@NicolasDorier you can define multiple key groups for a script template - and using key groups is optional. This preserves full generality but also affords key sorting, which is important for certain use cases (i.e. m-of-n with full key symmetry, since the p2sh depends on the ordering and the number of permutations increases factorially in n making p2sh lookups impratical...and sorting also improves privacy).

@NicolasDorier Specifically, for the example you gave key groups wouldn't provide any real benefit. Might as well define Ak for Alice and Bk for Bob:

OP_IF
        OP_DUP OP_HASH160 [Ak] OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
        <TIMEOUT> OP_CHECKLOCKTIMEVERIFY OP_DROP
        OP_DUP OP_HASH160 [Bk] OP_EQUALVERIFY OP_CHECKSIG
OP_ENDIF

Not having alphabetical ordering would not make permutation increases factorially, because I expected the m's in the K group to be sorted. (so for example in 2-2 Alice key is always the first and Bob always second, because it is the order in which they appear in the K group) I did not thought about sorting for increasing privacy though.

I admit I have lots of difficulty to think about another use case expect multi sig for the key group structure.

Anyway, I think it is easy to at least simplify the notation:

Define group B: B_k = { m₁/k, m₂/k, m₃/k }

Then, in a script template [Bk] would mean [Sort₁(B_k)] [Sort₂(B_k)] [Sort₃(B_k)]

OP_IF
        OP_DUP OP_HASH160 [Ak] OP_EQUALVERIFY OP_CHECKSIG
OP_ELSE
        <TIMEOUT> OP_CHECKLOCKTIMEVERIFY OP_DROP
        2 [Bk] 3 OP_CHECKMULTISIGVERIFY
OP_ENDIF

I see a group as a way to express : "The order of the keys is not important but should be deterministic..so let's decide it is lexical".

@NicolasDorier yes, a group essentially means that permutations of the set don't affect the authorization policy...the key set is fully symmetric.

There could potentially be other use cases we have not considered, so although the simplified notation is useful, we might still want to support interspersing opcodes between the keys.

Ok I understand, waiting the next commits. :)

I'll probably do a script template parser for NBitcoin in the future, the problem with using the [Sort1(Bk)] notation is that you can't use it during template design, because you don't know the number of keys in the group.

If you want to concatenate, then maybe notation [Bk | <script> ] might do the deal. [Bk | OP_CHECKSIG ] meaning [Sort1(Bk)] OP_CHECKSIG [Sort2(Bk)]

@NicolasDorier I've incorporated your simplified notation idea and your example.Just one caveat: I think we should make the distinction between a sorted key group and an individual key, so I suggest we use [{Bk}] to denote a sorted key group as opposed to [Bk] which is just a single key.

We can still improve upon the notation, perhaps, by making the distinction between a key group and an individual key more explicit as well. Perhaps something like:

Single key: Bk Key group: {Bk} Sorted key group: S{Bk} or {Bk}_s

Or perhaps {Bk} can be used to denote both the key group itself and the sorted expansion. Sorting would always be implied when used in a template.

Yes I think Bk and {Bk} is clear enough, I don't think there will be any need of saying "sorted key group", it is implied. There is no reason to make a keygroup if they can't be sorted by lexical order without changing the semantic of the script.

Needs Copyright section.

@luke-jr copyright section added.