Re: [bitcoin-dev] Statechain implementations

From: Bob McElrath <bob@mcelrath•org>
To: Albert <bitcoin-dev@albert•sh>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Statechain implementations
Date: Thu, 26 Mar 2020 14:52:36 +0000	[thread overview]
Message-ID: <20200326145236.GK28113@mcelrath.org> (raw)
In-Reply-To: <79753214-9d5e-40c7-97ac-1d4e9ea3c64e@www.fastmail.com>

Very good point, but I think this is easy to fix.

It's not actually necessary that the quantity in (b) involve the SE's secret key
s1. It can be purely the blinding factor. This quantity gets relayed through the
SE anyway, after a round trip through owner 2, where the SE removes the blinding
nonce. The SE needs to determine the ratio of the two private keys o1*o2_inv.
There's no reason for the SE to send anything about s1 other than the public
keys S1=s1.G and S2=s2.G, keeping the secret keys s1 and s2 hidden behind ECDLP
and not sharing quantities involving them in Z_p.

Thus:
b. (SE) x -> (2)
c. (2) o2_inv*x -> (1) 
d. (1) o1*(o2_inv*x) -> (SE)
e. (SE) s2 = x_inv*(o1*o2_inv*x)*s1 = o1*o2_inv*s1
        s2.G -> (2)
f. (2) o2.s2.G = o1.s1.G = P

Now we could have had a different problem, in step (e) if the SE sends owner 2
the quantity o1*o2_inv*s1, a self-sending owner can determine a similar quantity
to what you described (x1+x2)*s1: (o1*o2_inv + o2*o3_inv)*s1 and we're back to
an Irwin-Hall distribution.

It's not necessary to send a quantity involving s1 in steps (b-e). Owner 2
already has his private key o2 and the SE has his new private key
s2=o1*o2_inv*s1. Since P=o1.s1.G=o2.s2.G we're set up for o2 to transfer the
funds, but it's necessary to prove to (2) that his o2 does in fact control the
UTXO. This can be done by sending (2) the public key S2=s2.G which he can
multiply by o2 to get P=o2.s2.G and verify that the SE does have the correct
private key corresponding to his o2 for the public key P recorded on-chain.

Thus in the self-send situation, the owner no longer has any algebraic relations
he can use as you describe.

Algebraic relations remain in step (d) that a self-sending owner could use, but
they all involve his own private keys, which he knows anyway. He has only one
relation from the previous owner and all subsequent relations do not involve
that owner. However if a pair of entities send funds back and forth, each owner
could collect a sum as you describe, if the counterparty (2) re-uses keys:
    o2_inv*(x1 + x2)
The SE has similar relations in step (e) if there's key reuse.  Therefore it's
important that on each transfer, you generate a new key and do not re-use keys.
A responsible SE could detect a key-reuse situation by e.g.  recording old
pubkeys P1, P2 even though he deleted s1 and s2, and inform the user of the
key-reuse error and abort.

Do you think that works?

P.S. SGX is not "trust minimization", it's "trust transfer" -- specifically to
the keys managing the SGX. If we thought processor manufacturers were better at
key management than the rest of us, we should just hand them the task. I don't
think that's the case, and I don't think anyone else does either. An SGX
attestation as an optional add-on I think is a worthwhile enhancement, as long
as it's not on the critical path of the protocol.

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=Owner2, that is, one of the owners sends some
> coins to itself, that owner would get to know both x1*s1 and x2*s2=
> x2*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 two 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–Hall distribution, 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 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 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 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-bitcoin-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 requires features
>     not currently available in Bitcoin (like SIGHASH_NOINPUT), and it 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 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 window. 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.
> 
>     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 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 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 = 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 = 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 = o1*s1): P = o1.(s1.G) = 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 = s1*o2_inv*o1 and deletes s1.
>     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 share
>     (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 derive) can
>     only be determined from the key shares of the SE and Owner 2 (i.e. P =
>     s2*o2.G).
>     h. Owner 2 then calculates their backup public key (B2 = 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 guarantee that Tx2 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) using
>     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 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 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
> 
> 
> 
> !DSPAM:5e7c2da240641930319229!

> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> !DSPAM:5e7c2da240641930319229!

--
Cheers, Bob McElrath

"For every complex problem, there is a solution that is simple, neat, and wrong."
    -- H. L. Mencken 