From 204b7f13a0cb3d33506a7369e1f131d9f30e98d2 Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Wed, 5 Jun 2019 13:59:09 +0000 Subject: Prescribe that a taproot output key should always have a taproot commitment --- bip-taproot.mediawiki | 18 +++++++++++++++++- 1 file changed, 17 insertions(+), 1 deletion(-) (limited to 'bip-taproot.mediawiki') diff --git a/bip-taproot.mediawiki b/bip-taproot.mediawiki index 7d58b16..bd9de86 100644 --- a/bip-taproot.mediawiki +++ b/bip-taproot.mediawiki @@ -162,6 +162,18 @@ Satisfying any of these conditions is sufficient to spend the output. * When deciding between scripts with conditionals (OP_IF etc.) and splitting them up into multiple scripts (each corresponding to one execution path through the original script), it is generally preferable to pick the latter. * When a single condition requires signatures with multiple keys, key aggregation techniques like MuSig can be used to combine them into a single key. The details are out of scope for this document, but note that this may complicate the signing procedure. * If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = point(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of secp256k1 generator ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key is does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. +* If the spending conditions do not require a script path, the output key should commit to an unspendable script path instead of having no script path. This can be achieved by computing the output key point as ''Q = P + int(hashTapTweak(bytes(P)))G''. '''Why should the output key always have a taproot commitment, even if there is no script path?''' +If the taproot output key is an aggregate of keys, there is the possibility for a malicious party to add a script path without being noticed by the other parties. +This allows to bypass the multiparty policy and to steal the coin. +MuSig key aggregation does not have this issue because it already causes the internal key to be randomized. + +The attack works as follows: Assume Alice and Mallory want to aggregate their keys into a taproot output key without a script path. +In order to prevent key cancellation and related attacks they use [https://eprint.iacr.org/2018/483.pdf MSDL-pop] instead of MuSig. +The MSDL-pop protocol requires all parties to provide a proof of possession of their corresponding private key and the aggregated key is just the sum of the individual keys. +After Mallory receives Alice's key ''A'', Mallory creates ''M = M0 + int(t)G'' where ''M0'' is Mallory's original key and ''t'' allows a script path spend with internal key ''P = A + M0'' and a script that only contains Mallory's key. +Mallory sends a proof of possession of ''M'' to Alice and both parties compute output key ''Q = A + M = P + int(t)G''. +Alice will not be able to notice the script path, but Mallory can unilaterally spend any coin with output key ''Q''. + * The remaining scripts should be organized into the leaves of a binary tree. This can be a balanced tree if each of the conditions these scripts correspond to are equally likely. If probabilities for each condition are known, consider constructing the tree as a Huffman tree. '''Computing the output script''' Once the spending conditions are split into an internal key internal_pubkey and a binary tree whose leaves are (leaf_version, script) tuples, the following Python3 algorithm can be used to compute the output script. In the code below, ser_script prefixes its input with a CCompactSize-encoded length. Public key objects hold 32-byte public keys according to bip-schnorr, have a method get_bytes to get the byte array and a method tweak_add which returns a new public key corresponding to the sum of the public key point and a multiple of the secp256k1 generator (similar to BIP32's derivation). The second return value of tweak_add is a boolean indicating the quadratic residuosity of the Y coordinate of the resulting point. tagged_hash computes the tagged hash according to bip-schnorr. @@ -184,7 +196,11 @@ def taproot_output_script(internal_pubkey, script_tree): script_tree is either: - a (leaf_version, script) tuple (leaf_version is 0xc0 for bip-tapscript scripts) - a list of two elements, each with the same structure as script_tree itself""" - _, h = taproot_tree_helper(script_tree) + - None + if script_tree is None: + h = b'' + else: + _, h = taproot_tree_helper(script_tree) t = tagged_hash("TapTweak", internal_pubkey.get_bytes() + h) assert int.from_bytes(t, 'big') < SECP256K1_ORDER output_pubkey, _ = internal_pubkey.tweak_add(t) -- cgit v1.2.3