diff options
| author | Lloyd Fournier <lloyd.fourn@gmail.com> | 2020-03-05 20:56:54 +1100 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2020-03-05 09:57:23 +0000 |
| commit | 15925abbc6285fd08e75b051eaa11f449ec3409b (patch) | |
| tree | 0e91dc9a7cb93939c19fd1eb33ddf997bbc63878 | |
| parent | b4b6030374217271f3ecca5974ff2da84285aa21 (diff) | |
| download | pi-bitcoindev-15925abbc6285fd08e75b051eaa11f449ec3409b.tar.gz pi-bitcoindev-15925abbc6285fd08e75b051eaa11f449ec3409b.zip | |
Re: [bitcoin-dev] Hash function requirements for Taproot
| -rw-r--r-- | 21/6f7280c1a9dc48fb4c128616c84d55f5953407 | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/21/6f7280c1a9dc48fb4c128616c84d55f5953407 b/21/6f7280c1a9dc48fb4c128616c84d55f5953407 new file mode 100644 index 000000000..aadfc632e --- /dev/null +++ b/21/6f7280c1a9dc48fb4c128616c84d55f5953407 @@ -0,0 +1,214 @@ +Return-Path: <lloyd.fourn@gmail.com> +Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 3103DC013E + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Mar 2020 09:57:23 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by whitealder.osuosl.org (Postfix) with ESMTP id 28A85869BA + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Mar 2020 09:57:23 +0000 (UTC) +X-Virus-Scanned: amavisd-new at osuosl.org +Received: from whitealder.osuosl.org ([127.0.0.1]) + by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id Ti9enpPHtewN + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Mar 2020 09:57:22 +0000 (UTC) +X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 +Received: from mail-io1-f43.google.com (mail-io1-f43.google.com + [209.85.166.43]) + by whitealder.osuosl.org (Postfix) with ESMTPS id 008DD81AD9 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 5 Mar 2020 09:57:21 +0000 (UTC) +Received: by mail-io1-f43.google.com with SMTP id r15so5829082iog.0 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 05 Mar 2020 01:57:21 -0800 (PST) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; + h=mime-version:references:in-reply-to:from:date:message-id:subject:to + :cc; bh=WDubY35pJnl666GOeZARRGKu0TnrUAyBbcXe7IVqybA=; + b=VbkDPJp5iBfoiBHd5XAABq+97cNi1uYoKhKeqqevdMdfaDwMYwpTrWwq1btQSC9l59 + b5Xdbn9Tuz+9yeuakeUWjsPTVuvqbQVokvtDiBcFGCRMyjnfwEd/2V/iJc6lyKuRLpdS + MFpgUnKAXbRWokGpjUf/J5W4sHna1yK1QvRaPwSouwQbSSRz+Zohg3F7aVNR6ladh7Ds + /mNXNxwsxU1EIHaqnC/IXWxUeJEPxkCtmj9f1yo1bPp9+UR1jfyoVXtmttZa6Xl3iFYZ + sI+I4M3c+7h3qSY069JTpP6G6eEF6glFEJn6qOiztkXmq58/OTzmcBGVHSFoac7vgtV+ + f7qw== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20161025; + h=x-gm-message-state:mime-version:references:in-reply-to:from:date + :message-id:subject:to:cc; + bh=WDubY35pJnl666GOeZARRGKu0TnrUAyBbcXe7IVqybA=; + b=h56ZXGRDzhPex9JBdkyvaTGrmu12/kHnnvkIcrlIovbiu/Zw1LgmfoSn5E75cDjNpx + 9F0maPMgbtzp9hjxApEIBr/FaqQbbC1xjVnVoOrfJamg6Lh/4pkLdERkzdl+fZLUl2Nw + EYmX7UTw1bT4T6BkKz0fto9K+KwLoG4Pu9CqT32BNaS5tWYsgRzOWp4IjJ5OZw6UrsfR + 9Olb3v+3gzngiuZ02xTLGogSHxoCmYjZKD7bb5J/u9CeKO1fiARu8GFwSsXHBQhQdHZf + 8YXgKF5JtiNjUxj/r4mx9NwZ9Bi+UHsCJscwg64MM4Nddz+vNG7qT18H/TAtqr2xAA+s + qHjQ== +X-Gm-Message-State: ANhLgQ2iLDywKCv5KdENndoTQ2xr3jw/xDIoaopuXJ9YAJ7RKEKUYtjo + 5MrDBtsyg03fJmyYF1XSNi+SDn6tMStdbmlDSNk= +X-Google-Smtp-Source: ADFU+vtMs6qD7e5iDb6hhXKN0ofjUmZ97C/fTERtmOR3GQM/4lvRvICEe+rXLzp9ZbdPe0WPFMdKcTxrmZyvwyI1nnM= +X-Received: by 2002:a6b:8fd8:: with SMTP id r207mr1011058iod.158.1583402241130; + Thu, 05 Mar 2020 01:57:21 -0800 (PST) +MIME-Version: 1.0 +References: <CAH5Bsr2m3+kN67h0Dd+60-i3WCnCRXr_ywzub5_OV=UxxzN3hQ@mail.gmail.com> + <tXbP-9UVzs4Je3MdjTYAbm0ZWVMctlhY15v6_G8CCRnaWJjo8VU8h2WDfUSiqnWl8rQa0zbrsupNRNtss0gDFjMiqwNil_ahiqSraICAP9Q=@protonmail.com> +In-Reply-To: <tXbP-9UVzs4Je3MdjTYAbm0ZWVMctlhY15v6_G8CCRnaWJjo8VU8h2WDfUSiqnWl8rQa0zbrsupNRNtss0gDFjMiqwNil_ahiqSraICAP9Q=@protonmail.com> +From: Lloyd Fournier <lloyd.fourn@gmail.com> +Date: Thu, 5 Mar 2020 20:56:54 +1100 +Message-ID: <CAH5Bsr0tGFrH5qgUr20fUaceZZvJMY4_RBY6EU769L10KGc3Ng@mail.gmail.com> +To: ZmnSCPxj <ZmnSCPxj@protonmail.com> +Content-Type: multipart/alternative; boundary="0000000000001e8c8705a0189062" +X-Mailman-Approved-At: Thu, 05 Mar 2020 10:25:45 +0000 +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Subject: Re: [bitcoin-dev] Hash function requirements for Taproot +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.15 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Thu, 05 Mar 2020 09:57:23 -0000 + +--0000000000001e8c8705a0189062 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +> I am uncertain what you mean here by "coin-tossing". +> From the comparison to MuSig, I imagine it is an interactive key +generation protocol like this: + +> * Everybody generates fresh keypairs. +> * Everybody sends the hash of their pubkey to everyone else. +> * After receiving a hash of pubkey from everyone else, everybody sends +their pubkey to everyone else. +> * They add all their pubkeys to generate the aggregate key (and if using +Taproot, use it as the internal key). + +> Is that correct? + +Yes exactly. The reason it's called coin tossing is that the resulting key +is guaranteed to be uniformly random (in the random oracle model at least), +so it's like tossing a fair 2^256 sided coin. This is not true in MuSig for +example, where the aggregate key is not guaranteed to be from a uniform +distribution against a malicious party (but still secure as an aggregate +key). + +> However, it can generally be pointed out that, before you put anything +into an n-of-n, you would damn well sure want to have *some* assurance that +you can get it out later. So in general you would need coordination and +interaction anyway to arrange getting into an n-of-n in the first place. + +Right. Taking your example of a lightning channel, when you set it up I +don't *think* there is a way to use the non-interactivity of MuSig to +remove any rounds of communication to get to the starting state where there +is a channel funding on-chain and both parties have a tx that spends from +it which returns their funds. Doing coin tossing for the aggregate key as +well as the aggregate nonce shouldn't lead to any extra rounds of +communication. The downside of coin tossing is that it requires honest +parties to sample their keys non-deterministically (or at least have a +counter to avoid using the same key twice). + +> On the other hand, it would be best to have at least some minimum of +privacy by always interacting over Tor and having a Tor .onion address, +which has absolutely horrid latency because human beings cry when peeling +onions. +> So in general reducing the latency by reducing communication rounds is +better in general. +> Counter to this, assuming you use an n-of-n in an offchain protocol of +some sort, the number of communication rounds to generate the aggregate key +may be dwarfed by the total number of communication rounds to create +signatures to update the offchain protocol. +> Counter counter to this is that one plan for reducing communications +rounds for creating signatures during offchain operation is to (haha) use a +Taproot with an n-of-n internal key and a tapscript that has n +`OP_CHECKSIG` operations, so that for normal operation you just toss +individual signatures at each other but at termination of the offchain +protocol you can do the heavy MuSig-style signing with the n-of-n aggregate +key. + +Counter=C2=B3 to this is that, in the case of lightning, the aggregate key = +for a +PTLC does not need to be chosen at payment time. They channel members +could simply use the "master" aggregate key they generated by coin tossing +at the channel's inception and pseudorandomly randomise it every time they +need a new joint key (so the keys do not look related to everyone else on +the chain but you would effectively just be reusing the same public key). + +Having said that if there is some advantage to using MuSig in some +particular case I wouldn't hesitate to use it in combination with Taproot. +I don't think the new assumption that I think you have to make wrt to the +hash function really weighs up against most design considerations. In +general, it is probably worth considering whether your protocol actually +benefits from the non-interactivity MuSig gives in the key generation +stage. If it doesn't due to the fact that it doesn't make signing anymore +non-interactive, then coin tossing might be the answer. + +LL + +--0000000000001e8c8705a0189062 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><div class=3D"gmail_quote"><div><br></div><div><br></div><= +div>> I am uncertain what you mean here by "coin-tossing".<br>= +> From the comparison to MuSig, I imagine it is an interactive key gener= +ation protocol like this:<br><br>> * Everybody generates fresh keypairs.= +<br>> * Everybody sends the hash of their pubkey to everyone else.<br>&g= +t; * After receiving a hash of pubkey from everyone else, everybody sends t= +heir pubkey to everyone else.<br>> * They add all their pubkeys to gener= +ate the aggregate key (and if using Taproot, use it as the internal key).<b= +r><br>> Is that correct?<br></div><div><br>Yes exactly. The reason it= +9;s called coin tossing is that the resulting key is guaranteed to be unifo= +rmly=C2=A0random (in the random oracle model at least), so it's like to= +ssing a fair 2^256 sided coin. This is not true in MuSig for example, where= + the aggregate key is not guaranteed to be from a uniform distribution agai= +nst=C2=A0a malicious party (but still secure as an aggregate key).</div><di= +v><br></div><div>> However, it can generally be pointed out that, before= + you put anything into an n-of-n, you would damn well sure want to have *so= +me* assurance that you can get it out later. So in general you would need c= +oordination and interaction anyway to arrange getting into an n-of-n in the= + first place.</div><div><br></div><div>Right. Taking your example of a ligh= +tning channel, when you set it up I don't *think* there is a way to use= + the non-interactivity of MuSig to remove any rounds of communication to ge= +t to the starting state where there is a channel funding on-chain and both = +parties have a tx that spends from it which returns their funds. Doing coin= + tossing for the aggregate key as well as the aggregate nonce shouldn't= + lead to any extra rounds of communication. The downside of coin tossing is= + that it requires honest parties to sample their keys non-deterministically= + (or at least have a counter to avoid using the same key twice).=C2=A0</div= +><div><br></div><div>> On the other hand, it would be best to have at le= +ast some minimum of privacy by always interacting over Tor and having a Tor= + .onion address, which has absolutely horrid latency because human beings c= +ry when peeling onions.<br>> So in general reducing the latency by reduc= +ing communication rounds is better in general.<br>> Counter to this, ass= +uming you use an n-of-n in an offchain protocol of some sort, the number of= + communication rounds to generate the aggregate key may be dwarfed by the t= +otal number of communication rounds to create signatures to update the offc= +hain protocol.<br>> Counter counter to this is that one plan for reducin= +g communications rounds for creating signatures during offchain operation i= +s to (haha) use a Taproot with an n-of-n internal key and a tapscript that = +has n `OP_CHECKSIG` operations, so that for normal operation you just toss = +individual signatures at each other but at termination of the offchain prot= +ocol you can do the heavy MuSig-style signing with the n-of-n aggregate key= +.</div><div><br></div><div>Counter=C2=B3 to this is that, in the case of li= +ghtning, the aggregate key for a PTLC does not need to be chosen at payment= + time.=C2=A0 They channel members could simply use the "master" a= +ggregate key they generated by coin tossing at the channel's inception = +and pseudorandomly randomise it every time they need a new joint key (so th= +e keys do not look related to everyone else on the chain but you would effe= +ctively just be reusing the same public key).</div><div><br></div><div>Havi= +ng said that if there is some advantage to using MuSig in some particular c= +ase I wouldn't hesitate to use it in combination with Taproot. I don= +9;t think the new assumption that I think you have to make wrt to the hash = +function really weighs up against most design considerations. In general, i= +t is probably worth considering whether your protocol actually benefits fro= +m the non-interactivity MuSig gives in the key generation stage. If it does= +n't due to the fact that it doesn't make signing anymore non-intera= +ctive, then coin tossing might be the answer.</div><div><br></div><div>LL</= +div></div></div> + +--0000000000001e8c8705a0189062-- + |