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"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Hash function requirements for Taproot
Precedence: list

--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>&gt; I am uncertain what you mean here by &quot;coin-tossing&quot;.<br>=
&gt; From the comparison to MuSig, I imagine it is an interactive key gener=
ation protocol like this:<br><br>&gt; * Everybody generates fresh keypairs.=
<br>&gt; * 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>&gt; * They add all their pubkeys to gener=
ate the aggregate key (and if using Taproot, use it as the internal key).<b=
r><br>&gt; 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&#39;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>&gt; 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&#39;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&#39;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>&gt; 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>&gt; So in general reducing the latency by reduc=
ing communication rounds is better in general.<br>&gt; 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>&gt; 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 &quot;master&quot; a=
ggregate key they generated by coin tossing at the channel&#39;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&#39;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&#39;t due to the fact that it doesn&#39;t make signing anymore non-intera=
ctive, then coin tossing might be the answer.</div><div><br></div><div>LL</=
div></div></div>

--0000000000001e8c8705a0189062--