User-Agent: Cyrus-JMAP/3.1.7-1021-g152deaf-fmstable-20200319v1
Mime-Version: 1.0
Message-Id: <79753214-9d5e-40c7-97ac-1d4e9ea3c64e@www.fastmail.com>
In-Reply-To: <CAJvkSseW9OZ50yQiS7e0zt9tQt4v9aoikgGs_54_kMN-ORkQgw@mail.gmail.com>
References: <CAJvkSseW9OZ50yQiS7e0zt9tQt4v9aoikgGs_54_kMN-ORkQgw@mail.gmail.com>
Date: Thu, 26 Mar 2020 11:55:50 +0800
From: Albert <bitcoin-dev@albert.sh>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=188243bb2a48488180073fd76b6346e7
Subject: Re: [bitcoin-dev] Statechain implementations
Precedence: list

--188243bb2a48488180073fd76b6346e7
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable

Hi,

Great to see some work in this direction, here's some thoughts on your k=
eygen scheme:

In the scenario where Owner1=3DOwner2, that is, one of the owners sends =
some coins to itself, that owner would get to know both x1*s1 and x2*s2=3D=
x2*s1*o2_inv*o1, and, because he already knows o1 and o2, that implies k=
nowledge of both x1*s1 and x2*s1 where x1 and x2 are random numbers samp=
led from an uniform distribution. Once the owner has these two numbers, =
he can just sum these together to obtain s1*(x1+x2).=20
Now, because of the central limit theorem, the distribution of x1+x2 sho=
uld approximate a normal one, concretely an Irwin=E2=80=93Hall distribut=
ion, with that approximation getting better when more numbers are collec=
ted through iterations of the protocol. Once you've collected enough num=
bers to approximate a normal well enough (looking at Irwin Hall distribu=
tion graphs^[1] you can observe that with less than 10 samples the distr=
ibution is already pretty similar to a normal one), it should be possibl=
e 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 =
be 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 hardwa=
re 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,
>=20
> We are starting to work on an implementation of the statechains concep=
t (https://medium.com/@RubenSomsen/statechains-non-custodial-off-chain-b=
itcoin-transfer-1ae4845a4a39), with particular interest in using the pro=
tocol enable the change of ownership (novation) of an individual positio=
n in an active discreet log contract (DLC) without an on-chain transacti=
on, and without needing the cooperation of the counterparty. The protoco=
l as outlined by Ruben requires features not currently available in Bitc=
oin (like SIGHASH_NOINPUT), and it is uncertain when (or even if) this w=
ill 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 the=
m.=20
>=20
> There are two main modifications we are looking at:=20
> 1. Instead of an eltoo-based backup/refund transaction (enabling the c=
urrent owner to claim the UTXO in case the statechain entity disappears)=
 we propose using a decrementing nLocktime for backup transactions as th=
e output changes hands. Here, the first owner gets a backup transaction =
with an nLocktime at some future height (h0), then the next owner gets a=
 backup transaction with nLocktime (h0-c) where c is a confirmation wind=
ow. This approach has the downside of limiting the lifetime of the UTXO,=
 but it also doesn't require the current owner to be always online.=20
>=20
> 2. Replacing the 2-of-2 multisig output (paying to statechain entity S=
E 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 shar=
e 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):
>=20
> KeyGen:
>=20
>  a. Owner 1 generates private key share o1 then calculates the corresp=
onding public key of the share O1 and sends it to the SE: O1 =3D o1.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=
 s1.G
>  c. Both SE and Owner 1 then multiply the public keys they receive by =
their own private key shares to obtain the same shared public key P (whi=
ch 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).=20
>  e. Once Owner 1 and SE cooperatively sign the first backup transactio=
n, Owner 1 then signs and broadcasts the deposit transaction Tx0.=20
>=20
> Transfer from Owner 1 to Owner 2:
>=20
>  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 v=
alue x*s1 and sends this securely to Owner 2.=20
>  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 an=
d 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 canc=
els the blinding nonce x to give s1*o2_inv*o1. This value, when multipli=
ed by the new owner key share o2 equals the original shared private key =
s1*o1.=20
>  f. The SE then sets this value equal to s2 =3D s1*o2_inv*o1 and delet=
es s1. s2 and o2 are now the key shares of `P` and can be used to colabo=
ritively sign (with 2P ECDSA). So long as the SE delets s1, the old owne=
r key share (o1) is of no use in deriving or co-signing with the full sh=
ared private key, and is invalidated.=20
>  g. The shared public key P remains unchanged, but the corresponding p=
rivate 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 =
sends 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=
 height h0 - c0, where c0, is a confirmation time sufficient to guarante=
e that Tx2 can be confirmed in the blockchain before Tx1 (therefore maki=
ng Tx1 invalid).
>  j. Owner 2 and the SE then cooperate to sign Tx2 with shared key (P) =
using the 2P ECDSA protocol, which Owner 2 then saves.=20
>=20
> The principle of the logic of the key transfer is that the two separat=
e 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 th=
eir 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=
 the nonce (x) prevents any of the participants from determining any inf=
ormation about each others secret keys. In this way Owner 2 cannot deter=
mine s1 from x*s1, Owner 1 cannot determine s1 or o2 from x*s1*o2_inv an=
d the SE cannot determine o1 or o2 from x*s1*o2_inv*o1.=20
>=20
> This transfer protocol can be repeated to transfer the ownership to ne=
w owners. Each time the SE key share sX is updated, the previous key sha=
res become invalid and are of no use even if the current key share is su=
bsequently 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 b=
y a previous owner to steal the funds.=20
>=20
> Any comments on the above would be greatly appreciated.=20
>=20
> Tom
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20

--188243bb2a48488180073fd76b6346e7
Content-Type: text/html;charset=utf-8
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE html><html><head><title></title><style type=3D"text/css">p.Mso=
Normal,p.MsoNoSpacing{margin:0}</style></head><body><div>Hi,<br></div><d=
iv><br></div><div>Great to see some work in this direction, here's some =
thoughts on your keygen scheme:<br></div><div><br></div><div>In the scen=
ario where Owner1=3DOwner2, that is, one of the owners sends some coins =
to itself, that owner would get to know both&nbsp;x1*s1 and x2*s2=3Dx2*s=
1*o2_inv*o1, and, because he already knows o1 and o2, that implies knowl=
edge of both&nbsp;x1*s1 and&nbsp;x2*s1 where x1 and x2 are random number=
s sampled from an uniform distribution. Once the owner has these two num=
bers, he can just sum these together to obtain s1*(x1+x2). <br></div><di=
v>Now, because of the central limit theorem, the distribution of x1+x2 s=
hould approximate a normal one, concretely an&nbsp;Irwin=E2=80=93Hall di=
stribution, with that approximation getting better when more numbers are=
 collected through iterations of the protocol. Once you've collected eno=
ugh numbers to approximate a normal well enough (looking at Irwin Hall d=
istribution graphs^[1] you can observe that with less than 10 samples th=
e distribution 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.<br></div><div><br></di=
v><div>Practically, it'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=
 shows 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, something which might be worth looking into is the possibility of f=
urther trust-minimising the SE role by forcing it's code to be run insid=
e an AWS oracle or a hardware isolated processor such as SGX.<br></div><=
div><br></div><div>Albert</div><div><br></div><div>[1]&nbsp;<a href=3D"h=
ttps://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution">https://en=
.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution</a><br></div><div><b=
r></div><div>On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin=
-dev wrote:<br></div><blockquote type=3D"cite" id=3D"qt"><div dir=3D"ltr=
"><div>Hi all,<br></div><div><br></div><div>We are starting to work on a=
n implementation of the statechains concept (<a href=3D"https://medium.c=
om/@RubenSomsen/statechains-non-custodial-off-chain-bitcoin-transfer-1ae=
4845a4a39">https://medium.com/@RubenSomsen/statechains-non-custodial-off=
-chain-bitcoin-transfer-1ae4845a4a39</a>), with particular interest in u=
sing the protocol enable the change of ownership (novation) of an indivi=
dual position in an active discreet log contract (DLC) without an on-cha=
in transaction, and without needing the cooperation of the counterparty.=
 The protocol as outlined by Ruben requires features not currently avail=
able in Bitcoin (like SIGHASH_NOINPUT), and it is uncertain when (or eve=
n 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 fee=
dback on them. <br></div><div><br></div><div>There are two main modifica=
tions we are looking at: <br></div><div>1. Instead of an eltoo-based bac=
kup/refund transaction (enabling the current owner to claim the UTXO in =
case the statechain entity disappears) we propose using a decrementing n=
Locktime for backup transactions as the output changes hands. Here, the =
first owner gets a backup transaction with an nLocktime at some future h=
eight (h0), then the next owner gets a backup 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 also doesn't require the c=
urrent owner to be always online. <br></div><div><br></div><div>2. Repla=
cing 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 key share=
d 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 public key remaining the same). Thi=
s works as follows (.G is EC point multiplication, * is scalar multiplic=
ation):<br></div><div><br></div><div>KeyGen:<br></div><div><br></div><di=
v> a. Owner 1 generates private key share o1 then calculates the corresp=
onding 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 sends it to Owne=
r 1: S1 =3D s1.G<br></div><div> c. Both SE and Owner 1 then multiply the=
 public keys they receive by their 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)<br></div><div> d. Owner 1 cre=
ates a funding transaction (Tx0) to pay an amount A to the address corre=
sponding to P (but doesn't sign it). <br></div><div> e. Once Owner 1 and=
 SE cooperatively sign the first backup transaction, Owner 1 then signs =
and broadcasts the deposit transaction Tx0. <br></div><div><br></div><di=
v>Transfer from Owner 1 to Owner 2:<br></div><div><br></div><div> a. Own=
er 2 generates two private keys: o2 (the new owner UTXO private key shar=
e) and b2 (the new owner refund private key).<br></div><div> b. The SE g=
enerates a temporary blinding nonce x and calculates the value x*s1 and =
sends this securely to Owner 2. <br></div><div> c. Owner 2 then multipli=
es this received value by the modular inverse of o2 (o2_inv) and then se=
nds this value (x*s1*o2_inv), to Owner 1.<br></div><div> d. Owner 1 then=
 multiplies this received value by the key share o1 and sends the result=
ing value (x*s1*o2_inv*o1) to the SE.<br></div><div> e. The SE then mult=
iplies 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 ke=
y share o2 equals the original shared private 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 can be used to colabori=
tively 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 with the full shar=
ed private key, and is invalidated. <br></div><div> g. The shared public=
 key P remains unchanged, but the corresponding private key (which no in=
dividual party ever has knowledge of or can derive) can only be determin=
ed from the key shares of the SE and Owner 2 (i.e. P =3D s2*o2.G).<br></=
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 tra=
nsaction (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 c=
onfirmation time sufficient to guarantee that Tx2 can be confirmed in th=
e blockchain before Tx1 (therefore making Tx1 invalid).<br></div><div> 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. <br></div><div><br></=
div><div>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 their 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 the nonce (x) prevents any of the participants from determining =
any information about each others secret keys. In this way Owner 2 canno=
t 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 from 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, t=
he previous key shares become invalid and are of no use even if the curr=
ent 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. <br></div><div=
><br></div><div>Any comments on the above would be greatly appreciated. =
<br></div><div><br></div><div>Tom<br></div></div><div>__________________=
_____________________________<br></div><div>bitcoin-dev mailing list<br>=
</div><div>bitcoin-dev@lists.linuxfoundation.org<br></div><div>https://l=
ists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<br></div><div><br>=
</div></blockquote><div><br></div></body></html>
--188243bb2a48488180073fd76b6346e7--