From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id CA270C0177 for ; Thu, 26 Mar 2020 04:07:13 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id B505A8625C for ; Thu, 26 Mar 2020 04:07:13 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xpIQT+Vgmh2c for ; Thu, 26 Mar 2020 04:06:36 +0000 (UTC) X-Greylist: delayed 00:09:07 by SQLgrey-1.7.6 Received: from out3-smtp.messagingengine.com (out3-smtp.messagingengine.com [66.111.4.27]) by hemlock.osuosl.org (Postfix) with ESMTPS id 09B5F888C5 for ; Thu, 26 Mar 2020 04:06:28 +0000 (UTC) Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id 4EFD15C01AD for ; Wed, 25 Mar 2020 23:57:20 -0400 (EDT) Received: from imap2 ([10.202.2.52]) by compute2.internal (MEProxy); Wed, 25 Mar 2020 23:57:20 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=albert.sh; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type; s=fm2; bh=LBu7ImeHa9o8k9mKLWwBYS+nst5tn01 EoDtJr7JfCYw=; b=EFBiL5OmL50/c+E5maj3F0Qrx1UPUpQJOBM6dFmDW+VBWqH SkWYUh5d1e7nZHYR9Gl6WSJ6eH1wZMi6AmeEmTs0tpSCPgqK73isco8/L2PBcVgT 9OoQ5s4HmTdN9SCZcRIyM7bircYww2cl+80Urh61M0hM1qMbPULxRSNzvFQ4etZX zN0PwJOtvO/IUCNkSVmi0KYM57mBSE9mfx5MoeGImuWUcSelFXrSNTmtAw5rgEsK KNWZyb63XBRjkxK9FofFHZIhfWqo98sK53pCcopaxpdiabUntMZxEvc/5QKaoJpt jiDinc/QrRF5nbR7gAqF5XP7aglLFQ+n4h+ZOrA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=LBu7Im eHa9o8k9mKLWwBYS+nst5tn01EoDtJr7JfCYw=; b=u3RXbBpyB+W+FrjUaDmXbi qTqPcewpaM+rD3alwwQX11PSeMyJwnwHefHGx3DCPBE4wZUj0UA0loOsavUPUiEP dgp4kpAY4IOFbhMOL+8c3pOI1ESKpEm1FZoU6KeqYlTltwz2w2Uz+mbbWj8jZTur EsJQfe2jZ6bS9fenVgGYfDFIe7iyA4Zr2JHeUpgqrWXDNMVVfEgnsrOzI54NSRxN mgMohqzrGSulveg31lNutYjVBgY9MAQMS2mP+ogoD0HPzGYCJZkCKdweRkj/LywR kUij1Rc5unkIZP7wm8fRE6HuWwUM3qoXXsvJL82/5S7oeKeEGb6XyTbiaglYqpFQ == X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedugedrudehhedgieduucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtsegrtd erreerreejnecuhfhrohhmpeetlhgsvghrthcuoegsihhttghoihhnqdguvghvsegrlhgs vghrthdrshhhqeenucffohhmrghinhepfihikhhiphgvughirgdrohhrghdpmhgvughiuh hmrdgtohhmpdhlihhnuhigfhhouhhnuggrthhiohhnrdhorhhgnecuvehluhhsthgvrhfu ihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepsghithgtohhinhdquggvvhesrg hlsggvrhhtrdhshh X-ME-Proxy: Received: by mailuser.nyi.internal (Postfix, from userid 501) id BB203E00BA; Wed, 25 Mar 2020 23:57:19 -0400 (EDT) X-Mailer: MessagingEngine.com Webmail Interface 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: References: Date: Thu, 26 Mar 2020 11:55:50 +0800 From: Albert To: bitcoin-dev@lists.linuxfoundation.org Content-Type: multipart/alternative; boundary=188243bb2a48488180073fd76b6346e7 X-Mailman-Approved-At: Thu, 26 Mar 2020 04:20:34 +0000 Subject: Re: [bitcoin-dev] Statechain implementations X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 26 Mar 2020 04:07:13 -0000 --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
Hi,

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

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 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 x1*s1 and 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).
Now, because of the central limit theorem, the distribution of x1+x2 s= hould approximate a normal one, concretely an 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.

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.

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.
<= div>
Albert

On Wed, Mar 25, 2020, at 9:52 PM, Tom Trevethan via bitcoin= -dev wrote:
Hi all,

We are starting to work on a= n implementation of the statechains concept (https://medium.com/@RubenSomsen/statechains-non-custodial-off= -chain-bitcoin-transfer-1ae4845a4a39), 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.

There are two main modifica= tions we are looking at:
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.

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):

KeyGen:

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 Owne= r 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 (which corresponds to a shared private key of p= =3D o1*s1): P =3D o1.(s1.G) =3D s1.(o1.G)
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).
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. Own= er 2 generates two private keys: o2 (the new owner UTXO private key shar= e) and b2 (the new owner refund private key).
b. The SE g= enerates a temporary blinding nonce x and calculates the value x*s1 and = sends this securely to Owner 2.
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.
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.
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.
= 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.
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).
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 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).
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 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.

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.

Any comments on the above would be greatly appreciated. =

Tom
__________________= _____________________________
bitcoin-dev mailing list
=
bitcoin-dev@lists.linuxfoundation.org
https://l= ists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

=

--188243bb2a48488180073fd76b6346e7--