MIME-Version: 1.0
References: <CAJvkSseW9OZ50yQiS7e0zt9tQt4v9aoikgGs_54_kMN-ORkQgw@mail.gmail.com>
 <79753214-9d5e-40c7-97ac-1d4e9ea3c64e@www.fastmail.com>
In-Reply-To: <79753214-9d5e-40c7-97ac-1d4e9ea3c64e@www.fastmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Thu, 26 Mar 2020 13:36:20 +0100
Message-ID: <CAPv7TjZ45VD_5sGSFiQxmt981uDodq28mHOW=2LYLofXams43w@mail.gmail.com>
To: tom@commerceblock.com, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000001d148805a1c13ca1"
Subject: Re: [bitcoin-dev] Statechain implementations
Precedence: list

--0000000000001d148805a1c13ca1
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Tom,

Nice to see you working on this.

Regarding modification 1, I agree with ZmnSCPxj that Decker-Wattenhofer is
your next best option, given that eltoo is not yet available. But if you
are going to use a kickoff transaction, keep in mind that every previous
owner will have a copy of it. Because of this, you can't include a fee, and
will instead need to have a second output for CPFP. This way a previous
owner will at least have to pay the fee if they want to publish it. Note
that it's still an improvement, because even if the kickoff transaction
gets posted, it basically becomes no different than what it would have
been, had you not used a kickoff transaction at all.

Regarding modification 2, I like it a lot conceptually. It hadn't occurred
to me before, and it's a clear security improvement. The only question is
something Greg Sanders mentioned: whether it's enough to justify the added
complexity of using 2P ECDSA. The alternative would be to simply use a
regular 2-of-2 multisig (until Schnorr arrives, possibly).

I'm looking forward to seeing statechains become a reality.

Cheers,
Ruben

On Thu, Mar 26, 2020 at 5:20 AM Albert via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi,
>
> Great to see some work in this direction, here's some thoughts on your
> keygen scheme:
>
> In the scenario where Owner1=3DOwner2, that is, one of the owners sends s=
ome
> coins to itself, that owner would get to know both x1*s1 and
> x2*s2=3Dx2*s1*o2_inv*o1, and, because he already knows o1 and o2, that
> implies knowledge of both x1*s1 and x2*s1 where x1 and x2 are random
> numbers sampled from an uniform distribution. Once the owner has these tw=
o
> numbers, he can just sum these together to obtain s1*(x1+x2).
> Now, because of the central limit theorem, the distribution of x1+x2
> should approximate a normal one, concretely an Irwin=E2=80=93Hall distrib=
ution,
> with that approximation getting better when more numbers are collected
> through iterations of the protocol. Once you've collected enough numbers =
to
> approximate a normal well enough (looking at Irwin Hall distribution
> graphs^[1] you can observe that with less than 10 samples the distributio=
n
> is already pretty similar to a normal one), it should be possible to
> drastically reduce the search space and apply brute force to guess the
> value of \sum x and, consequently, s1.
>
> Practically, it's possible that the search space is still too large for
> brute-force to be fruitful, so this attack might not work, but it shows
> that there is information leakage in every protocol iteration.
>
> On another note, if you are not already aware of, something which might b=
e
> worth looking into is the possibility of further trust-minimising the SE
> role by forcing it's code to be run inside an AWS oracle or a hardware
> isolated processor such as SGX.
>
> Albert
>
> [1] https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution
>
> On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin-dev wrote:
>
> Hi all,
>
> We are starting to work on an implementation of the statechains concept (
> https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitco=
in-transfer-1ae4845a4a39),
> with particular interest in using the protocol enable the change of
> ownership (novation) of an individual position in an active discreet log
> contract (DLC) without an on-chain transaction, and without needing the
> cooperation of the counterparty. The protocol as outlined by Ruben requir=
es
> features not currently available in Bitcoin (like SIGHASH_NOINPUT), and i=
t
> is uncertain when (or even if) this will be added. So we are looking at
> variants that would work with current Bitcoin functionality, and it would
> be good to get some feedback on them.
>
> There are two main modifications we are looking at:
> 1. Instead of an eltoo-based backup/refund transaction (enabling the
> current owner to claim the UTXO in case the statechain entity disappears)
> we propose using a decrementing nLocktime for backup transactions as the
> output changes hands. Here, the first owner gets a backup transaction wit=
h
> an nLocktime at some future height (h0), then the next owner gets a backu=
p
> transaction with nLocktime (h0-c) where c is a confirmation window. This
> approach has the downside of limiting the lifetime of the UTXO, but it al=
so
> doesn't require the current owner to be always online.
>
> 2. Replacing the 2-of-2 multisig output (paying to statechain entity SE
> key and transitory key) with a single P2(W)PKH output where the public ke=
y
> shared between the SE and the current owner. The SE and the current owner
> can then sign with a 2-of-2 ECDSA MPC. This enables each owner to generat=
e
> their own private key share, and the SE changes their key share at each
> change of ownership (with the shared public key remaining the same). This
> works as follows (.G is EC point multiplication, * is scalar
> multiplication):
>
> KeyGen:
>
> a. Owner 1 generates private key share o1 then calculates the
> corresponding public key of the share O1 and sends it to the SE: O1 =3D o=
1.G
> b. The SE then generates a private key: s1 (the SE private key share),
> calculates the corresponding public key and sends it to Owner 1: S1 =3D s=
1.G
> c. Both SE and Owner 1 then multiply the public keys they receive by thei=
r
> own private key shares to obtain the same shared public key P (which
> corresponds to a shared private key of p =3D o1*s1): P =3D o1.(s1.G) =3D =
s1.(o1.G)
> d. Owner 1 creates a funding transaction (Tx0) to pay an amount A to the
> address corresponding to P (but doesn't sign it).
> e. Once Owner 1 and SE cooperatively sign the first backup transaction,
> Owner 1 then signs and broadcasts the deposit transaction Tx0.
>
> Transfer from Owner 1 to Owner 2:
>
> a. Owner 2 generates two private keys: o2 (the new owner UTXO private key
> share) and b2 (the new owner refund private key).
> b. The SE generates a temporary blinding nonce x and calculates the value
> x*s1 and sends this securely to Owner 2.
> c. Owner 2 then multiplies this received value by the modular inverse of
> o2 (o2_inv) and then sends this value (x*s1*o2_inv), to Owner 1.
> d. Owner 1 then multiplies this received value by the key share o1 and
> sends the resulting value (x*s1*o2_inv*o1) to the SE.
> e. The SE then multiplies this received value by the modular inverse of
> the temporary nonce (x_inv) to obtain x*s1*o2_inv*o1*x_inv. This cancels
> the blinding nonce x to give s1*o2_inv*o1. This value, when multiplied by
> the new owner key share o2 equals the original shared private key s1*o1.
> f. The SE then sets this value equal to s2 =3D s1*o2_inv*o1 and deletes s=
1.
> s2 and o2 are now the key shares of `P` and can be used to colaboritively
> sign (with 2P ECDSA). So long as the SE delets s1, the old owner key shar=
e
> (o1) is of no use in deriving or co-signing with the full shared private
> key, and is invalidated.
> g. The shared public key P remains unchanged, but the corresponding
> private key (which no individual party ever has knowledge of or can deriv=
e)
> can only be determined from the key shares of the SE and Owner 2 (i.e. P =
=3D
> s2*o2.G).
> h. Owner 2 then calculates their backup public key (B2 =3D b2.G) and send=
s
> it to the SE.
> i. The SE creates a backup transaction (Tx2) that pays the output of Tx0
> to the address corresponding to B2 , with `nLockTime` set to a block heig=
ht
> h0 - c0, where c0, is a confirmation time sufficient to guarantee that Tx=
2
> can be confirmed in the blockchain before Tx1 (therefore making Tx1
> invalid).
> j. Owner 2 and the SE then cooperate to sign Tx2 with shared key (P) usin=
g
> the 2P ECDSA protocol, which Owner 2 then saves.
>
> The principle of the logic of the key transfer is that the two separate
> key shares are updated, but the full shared private key (which no-one
> knows) remains the same. The new owner chooses a new secret value for the=
ir
> private key share, and this (along with the private key share of the
> previous owner) is utilized by the SE to update their share. The use of t=
he
> nonce (x) prevents any of the participants from determining any informati=
on
> about each others secret keys. In this way Owner 2 cannot determine s1 fr=
om
> x*s1, Owner 1 cannot determine s1 or o2 from x*s1*o2_inv and the SE canno=
t
> determine o1 or o2 from x*s1*o2_inv*o1.
>
> This transfer protocol can be repeated to transfer the ownership to new
> owners. Each time the SE key share sX is updated, the previous key shares
> become invalid and are of no use even if the current key share is
> subsequently revealed. The SE still needs to be trusted to delete the old
> key share, but this protocol removes the risk the the SE can be hacked by=
 a
> previous owner to steal the funds.
>
> Any comments on the above would be greatly appreciated.
>
> Tom
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--0000000000001d148805a1c13ca1
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Tom,<div><br></div><div>Nice to see you working on this=
.<br><div><br></div><div>Regarding modification=C2=A01, I agree with ZmnSCP=
xj that Decker-Wattenhofer is your next best option, given that eltoo is no=
t yet available. But if you are going to use a kickoff transaction, keep in=
 mind that every previous owner will have a copy of it. Because of this, yo=
u can&#39;t include a fee, and will instead need to have a second output fo=
r CPFP. This way a previous owner will at least have to pay the fee if they=
 want to publish it. Note that it&#39;s still an improvement, because even =
if the kickoff transaction gets posted, it basically becomes no different t=
han what it would have been, had you not used a kickoff transaction at all.=
</div><div><br>Regarding modification 2, I like it a lot conceptually. It h=
adn&#39;t occurred to me before, and it&#39;s a clear security improvement.=
 The only question is something Greg Sanders mentioned: whether it&#39;s en=
ough to justify the added complexity of using 2P ECDSA. The alternative wou=
ld be to simply use a regular 2-of-2 multisig (until Schnorr arrives, possi=
bly).</div><div><br></div><div>I&#39;m looking forward to seeing statechain=
s become a reality.</div><div><br></div><div>Cheers,</div><div>Ruben</div><=
/div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_a=
ttr">On Thu, Mar 26, 2020 at 5:20 AM Albert via bitcoin-dev &lt;<a href=3D"=
mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfounda=
tion.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D=
"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-le=
ft:1ex"><u></u><div><div>Hi,<br></div><div><br></div><div>Great to see some=
 work in this direction, here&#39;s some thoughts on your keygen scheme:<br=
></div><div><br></div><div>In the scenario where Owner1=3DOwner2, that is, =
one of the owners sends some coins to itself, that owner would get to know =
both=C2=A0x1*s1 and x2*s2=3Dx2*s1*o2_inv*o1, and, because he already knows =
o1 and o2, that implies knowledge of both=C2=A0x1*s1 and=C2=A0x2*s1 where x=
1 and x2 are random numbers sampled from an uniform distribution. Once the =
owner has these two numbers, he can just sum these together to obtain s1*(x=
1+x2). <br></div><div>Now, because of the central limit theorem, the distri=
bution of x1+x2 should approximate a normal one, concretely an=C2=A0Irwin=
=E2=80=93Hall distribution, with that approximation getting better when mor=
e numbers are collected through iterations of the protocol. Once you&#39;ve=
 collected enough numbers to approximate a normal well enough (looking at I=
rwin Hall distribution graphs^[1] you can observe that with less than 10 sa=
mples the distribution is already pretty similar to a normal one), it shoul=
d be possible to drastically reduce the search space and apply brute force =
to guess the value of \sum x and, consequently, s1.<br></div><div><br></div=
><div>Practically, it&#39;s possible that the search space is still too lar=
ge for brute-force to be fruitful, so this attack might not work, but it sh=
ows that there is information leakage in every protocol iteration.<br></div=
><div><br></div><div>On another note, if you are not already aware of, some=
thing which might be worth looking into is the possibility of further trust=
-minimising the SE role by forcing it&#39;s code to be run inside an AWS or=
acle or a hardware isolated processor such as SGX.<br></div><div><br></div>=
<div>Albert</div><div><br></div><div>[1]=C2=A0<a href=3D"https://en.wikiped=
ia.org/wiki/Irwin%E2%80%93Hall_distribution" target=3D"_blank">https://en.w=
ikipedia.org/wiki/Irwin%E2%80%93Hall_distribution</a><br></div><div><br></d=
iv><div>On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin-dev wro=
te:<br></div><blockquote type=3D"cite" id=3D"gmail-m_-1151363685022229184qt=
"><div dir=3D"ltr"><div>Hi all,<br></div><div><br></div><div>We are startin=
g to work on an implementation of the statechains concept (<a href=3D"https=
://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-tran=
sfer-1ae4845a4a39" target=3D"_blank">https://medium.com/@RubenSomsen/statec=
hains-non-custodial-off-chain-bitcoin-transfer-1ae4845a4a39</a>), with part=
icular interest in using the protocol enable the change of ownership (novat=
ion) of an individual position in an active discreet log contract (DLC) wit=
hout an on-chain transaction, and without needing the cooperation of the co=
unterparty. The protocol as outlined by Ruben requires features not current=
ly available in Bitcoin (like SIGHASH_NOINPUT), and it is uncertain when (o=
r even if) this will be added. So we are looking at variants that would wor=
k with current Bitcoin functionality, and it would be good to get some feed=
back on them. <br></div><div><br></div><div>There are two main modification=
s we are looking at: <br></div><div>1. Instead of an eltoo-based backup/ref=
und transaction (enabling the current owner to claim the UTXO in case the s=
tatechain entity disappears) we propose using a decrementing nLocktime for =
backup transactions as the output changes hands. Here, the first owner gets=
 a backup transaction with an nLocktime at some future height (h0), then th=
e next owner gets a backup transaction with nLocktime (h0-c) where c is a c=
onfirmation window. This approach has the downside of limiting the lifetime=
 of the UTXO, but it also doesn&#39;t require the current owner to be alway=
s online. <br></div><div><br></div><div>2. Replacing the 2-of-2 multisig ou=
tput (paying to statechain entity SE key and transitory key) with a single =
P2(W)PKH output where the public key shared between the SE and the current =
owner. The SE and the current owner can then sign with a 2-of-2 ECDSA MPC. =
This enables each owner to generate their own private key share, and the SE=
 changes their key share at each change of ownership (with the shared publi=
c key remaining the same). This works as follows (.G is EC point multiplica=
tion, * is scalar multiplication):<br></div><div><br></div><div>KeyGen:<br>=
</div><div><br></div><div> a. Owner 1 generates private key share o1 then c=
alculates the corresponding public key of the share O1 and sends it to the =
SE: O1 =3D o1.G<br></div><div> b. The SE then generates a private key: s1 (=
the SE private key share), calculates the corresponding public key and send=
s it to Owner 1: S1 =3D s1.G<br></div><div> c. Both SE and Owner 1 then mul=
tiply the public keys they receive by their own private key shares to obtai=
n the same shared public key P (which corresponds to a shared private key o=
f p =3D o1*s1): P =3D o1.(s1.G) =3D s1.(o1.G)<br></div><div> d. Owner 1 cre=
ates a funding transaction (Tx0) to pay an amount A to the address correspo=
nding to P (but doesn&#39;t sign it). <br></div><div> e. Once Owner 1 and S=
E cooperatively sign the first backup transaction, Owner 1 then signs and b=
roadcasts the deposit transaction Tx0. <br></div><div><br></div><div>Transf=
er from Owner 1 to Owner 2:<br></div><div><br></div><div> a. Owner 2 genera=
tes two private keys: o2 (the new owner UTXO private key share) and b2 (the=
 new owner refund private key).<br></div><div> b. The SE generates a tempor=
ary blinding nonce x and calculates the value x*s1 and sends this securely =
to Owner 2. <br></div><div> c. Owner 2 then multiplies this received value =
by the modular inverse of o2 (o2_inv) and then sends this value (x*s1*o2_in=
v), to Owner 1.<br></div><div> d. Owner 1 then multiplies this received val=
ue by the key share o1 and sends the resulting value (x*s1*o2_inv*o1) to th=
e SE.<br></div><div> e. The SE then multiplies this received value by the m=
odular inverse of the temporary nonce (x_inv) to obtain x*s1*o2_inv*o1*x_in=
v. This cancels the blinding nonce x to give s1*o2_inv*o1. This value, when=
 multiplied by the new owner key share o2 equals the original shared privat=
e key s1*o1. <br></div><div> f. The SE then sets this value equal to s2 =3D=
 s1*o2_inv*o1 and deletes s1. s2 and o2 are now the key shares of `P` and c=
an be used to colaboritively sign (with 2P ECDSA). So long as the SE delets=
 s1, the old owner key share (o1) is of no use in deriving or co-signing wi=
th the full shared private key, and is invalidated. <br></div><div> g. The =
shared public key P remains unchanged, but the corresponding private key (w=
hich no individual party ever has knowledge of or can derive) can only be d=
etermined from the key shares of the SE and Owner 2 (i.e. P =3D s2*o2.G).<b=
r></div><div> h. Owner 2 then calculates their backup public key (B2 =3D b2=
.G) and sends it to the SE.<br></div><div> i. The SE creates a backup trans=
action (Tx2) that pays the output of Tx0 to the address corresponding to B2=
 , with `nLockTime` set to a block height h0 - c0, where c0, is a confirmat=
ion time sufficient to guarantee that Tx2 can be confirmed in the blockchai=
n before Tx1 (therefore making Tx1 invalid).<br></div><div> j. Owner 2 and =
the SE then cooperate to sign Tx2 with shared key (P) using the 2P ECDSA pr=
otocol, which Owner 2 then saves. <br></div><div><br></div><div>The princip=
le of the logic of the key transfer is that the two separate key shares are=
 updated, but the full shared private key (which no-one knows) remains the =
same. The new owner chooses a new secret value for their private key share,=
 and this (along with the private key share of the previous owner) is utili=
zed by the SE to update their share. The use of the nonce (x) prevents any =
of the participants from determining any information about each others secr=
et keys. In this way Owner 2 cannot determine s1 from x*s1, Owner 1 cannot =
determine s1 or o2 from x*s1*o2_inv and the SE cannot determine o1 or o2 fr=
om x*s1*o2_inv*o1. <br></div><div><br></div><div>This transfer protocol can=
 be repeated to transfer the ownership to new owners. Each time the SE key =
share sX is updated, the previous key shares become invalid and are of no u=
se even if the current key share is subsequently revealed. The SE still nee=
ds to be trusted to delete the old key share, but this protocol removes the=
 risk the the SE can be hacked by a previous owner to steal the funds. <br>=
</div><div><br></div><div>Any comments on the above would be greatly apprec=
iated. <br></div><div><br></div><div>Tom<br></div></div><div>______________=
_________________________________<br></div><div>bitcoin-dev mailing list<br=
></div><div><a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=
=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br></div><div><a href=
=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" target=
=3D"_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<=
/a><br></div><div><br></div></blockquote><div><br></div></div>_____________=
__________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000001d148805a1c13ca1--