[bitcoin-dev] Statechain implementations

[bitcoin-dev] Statechain implementations

[Tom Trevethan]

[-- Attachment #1: Type: text/plain, Size: 5631 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 5911 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Tom,

>
> 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.

I believe I suggested this to Ruben Somsen as well in the past, but you can replace the state update mechanism with, for example, Decker-Wattenhofer decrementing-`nSequence`, which while it has a limit on the number of updates, does not have a limit on the time that a UTXO is locked in this mechanism.

You can even use the Decker-Wattenhofer trick of having a chain of decrementing-`nSequence` mechanisms to effectively multiply the number of updates that the overall mechanism can have.

The drawback is that in a unilateral close condition, the time to completely resolve the unilateral close is very large.

For a quick reference for this technique:

* The funding transaction is anchored onchain, but all succeeding transactions are offchain.
  * This funding transaction has a particular funding transaction output.
* There is a kickoff transaction, which is a 1-input 1-output transaction without any `nLockTime` or `nSequence` limits.
  * This spends the funding tx out.
  * The signer set of the output is the same as the signer set of the funding transaction output.
    * You could tweak keys or script to give a modicum of privacy.
* There is one or more decrementing-`nSequence` transactions, which are 1-input 1-output transactions.
  * Each one has a particular `nSequence` with a relative-locktime constraint.
  * This spends the kickoff transaction output.
  * The signer set of the output is the same as the signer set of the funding transaction output.
* There is one or more decrementing-`nSequence` transactions, which are 1-input 1-output transactions.
  * Each one has a particular `nSequence` with a relative-locktime constraint.
  * This spends the previous stage decrementing-`nSequence` transaction output.
  * The signer set of the output is the same as the signer set of the funding transaction output.
* Repeat the above stage a few times.
* There is one or more decrementing-`nSequence` transactions, which are 1-input multi-output transactions.
  * Each one has a particular `nSequence` with a relative-locktime constraint.
  * This spends the previous stage decrementing-`nSequence` transaction output.
  * The outputs of this transaction represent the current state inside the statechain.

The `nSequence` use means there is no time-based lifetime limit.
The decrementing-`nSequence` stages mean that earlier states have higher `nSequence` limits, and newer states have lower `nSequence` limits.
Chaining multiple such mechanisms allows you to "reset" a stage by making a single update of the higher stage, which resets all further stages.

So for example, we could have a multi-stage mechanism as below:

    ***blockchain***
       [funding tx] -+
         _ _ _ _ _ _ | _ _ _ _ _ _ _
     offchain        |
                     +->[kickoff tx]->[[14] stage]->[[14] stage]->[[14] stage]-> state outputs

The number in the brackets is the relative-locktime `nSequence` constraint in that stage transaction.
Let us suppose that we agree to decrement `nSequence` by 7 blocks at each update.

Then the first update will have:

    ***blockchain***
       [funding tx] -+
         _ _ _ _ _ _ | _ _ _ _ _ _ _
     offchain        |
                     +->[kickoff tx]->[[14] stage]->[[14] stage]->[[ 7] stage]-> state outputs

The the second update:

    ***blockchain***
       [funding tx] -+
         _ _ _ _ _ _ | _ _ _ _ _ _ _
     offchain        |
                     +->[kickoff tx]->[[14] stage]->[[14] stage]->[[ 0] stage]-> state outputs

After this update, for the next update, we would also sign the second-to-the-last stage, and reset the last stage:

    ***blockchain***
       [funding tx] -+
         _ _ _ _ _ _ | _ _ _ _ _ _ _
     offchain        |
                     +->[kickoff tx]->[[14] stage]->[[ 7] stage]->[[14] stage]-> state outputs

And so on.
Effectively it becomes a large counter, with the "least significant digit" being the last stage.
This multiplies the total number of updates your statechain can have, so for example the above uses a total unilateral close delay of 42 blocks to allow creation of 27 updates, whereas if it were a single stage those 42 blocks would only allow 7 updates.

As the first stage decrements, you can actually add more stages dependent on it, keeping a total maximum time that a unilateral close will resolve, but increasing the number of transactions that would need to be published onchain in a unilateral close.
This allows you to further extend the number of updates, possibly allowing an indefinite number of updates (at the cost of greatly increased blockchain usage in the unilateral close, which might not be feasible).

The original Decker-Wattenhofer paper "Duplex Micropayment Channels" has prettier graphics.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Statechain implementations

[Albert]

[-- Attachment #1: Type: text/plain, Size: 7698 bytes --]

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
> 

[-- Attachment #2: Type: text/html, Size: 8794 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 9367 bytes --]

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=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
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 10948 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Christian Decker]

Ruben Somsen via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
writes:
> 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.

It might be worth adopting the late fee binding we have in eltoo by
having the kickoff transaction input spending the funding tx signed with
sighash_single. This works because we only have 1 input and 1 output
that we really care about, and can allow others to attach fees at
will. That'd at least remove the need to guess the feerate days or
months in advance and thus having to overestimate.  

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

Wouldn't that result in a changing pubkey at each update, and thus
require an onchain move to be committed?

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

That'd indeed be great :-)

Cheers,
Christian

Re: [bitcoin-dev] Statechain implementations

[Greg Sanders]

[-- Attachment #1: Type: text/plain, Size: 2313 bytes --]

> Wouldn't that result in a changing pubkey at each update, and thus
require an onchain move to be committed?

Suggestion was in line with original proposal where no keys are changing
ever, just not presupposing existence of MuSig.

On Thu, Mar 26, 2020 at 1:15 PM Christian Decker via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Ruben Somsen via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
> writes:
> > 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.
>
> It might be worth adopting the late fee binding we have in eltoo by
> having the kickoff transaction input spending the funding tx signed with
> sighash_single. This works because we only have 1 input and 1 output
> that we really care about, and can allow others to attach fees at
> will. That'd at least remove the need to guess the feerate days or
> months in advance and thus having to overestimate.
>
> > 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).
>
> Wouldn't that result in a changing pubkey at each update, and thus
> require an onchain move to be committed?
>
> > I'm looking forward to seeing statechains become a reality.
>
> That'd indeed be great :-)
>
> Cheers,
> Christian
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 3123 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 3517 bytes --]

Hey Christian,

Thanks for chiming in :)

>It might be worth adopting the late fee binding we have in eltoo

That is where my thinking originally went as well, but then I remembered
that this alters the txid, causing the settlement tx to become invalid.
What I am suggesting should be functionally the same (albeit less
space-efficient): a secondary output that can be spent by anyone, which can
be used to fee bump the kickoff tx with CPFP. I believe this same idea was
considered for Lightning as well at some point. Do you happen to recall if
there was some kind of non-standardness issue with it?

>Wouldn't that result in a changing pubkey at each update, and thus require
an onchain move to be committed?

I have yet to take a closer look at the math, but my understanding is that
the same key (x) gets redistributed. First x = s1 + o1 and after the
transfer x = s2 + o2 (not the actual math, but it demonstrates how the
transitory key can change from o1 to o2). Assuming s1 is then thrown away
(trust assumption), o1 becomes harmless information.

Cheers,
Ruben

On Thu, Mar 26, 2020 at 6:17 PM Greg Sanders <gsanders87@gmail.com> wrote:

> > Wouldn't that result in a changing pubkey at each update, and thus
> require an onchain move to be committed?
>
> Suggestion was in line with original proposal where no keys are changing
> ever, just not presupposing existence of MuSig.
>
> On Thu, Mar 26, 2020 at 1:15 PM Christian Decker via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Ruben Somsen via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
>> writes:
>> > 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.
>>
>> It might be worth adopting the late fee binding we have in eltoo by
>> having the kickoff transaction input spending the funding tx signed with
>> sighash_single. This works because we only have 1 input and 1 output
>> that we really care about, and can allow others to attach fees at
>> will. That'd at least remove the need to guess the feerate days or
>> months in advance and thus having to overestimate.
>>
>> > 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).
>>
>> Wouldn't that result in a changing pubkey at each update, and thus
>> require an onchain move to be committed?
>>
>> > I'm looking forward to seeing statechains become a reality.
>>
>> That'd indeed be great :-)
>>
>> Cheers,
>> Christian
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 4739 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Ruben,

> Hey Christian,
>
> Thanks for chiming in :)
>
> >It might be worth adopting the late fee binding we have in eltoo
>
> That is where my thinking originally went as well, but then I remembered that this alters the txid, causing the settlement tx to become invalid. What I am suggesting should be functionally the same (albeit less space-efficient): a secondary output that can be spent by anyone, which can be used to fee bump the kickoff tx with CPFP. I believe this same idea was considered for Lightning as well at some point. Do you happen to recall if there was some kind of non-standardness issue with it?

Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you can use an `OP_TRUE` `redeemScript`, for instance.

Using an `OP_TRUE` `redeemScript` would allow any third party to make you cry by opportunistically spending such an output.
For example your Bitcoin-network peer could notice you broadcasting such a transaction with an `OP_TRUE` output, see you spend that output with a CPFP-RBF-ed child transaction, then instead of further broadcasting the child transaction, instead broadcast a non-RBF child transaction with tiny fee, so that it and its parent transaction will be accepted into mempools but would not be replaceable with a higher-feerate child transaction (because not RBF-flagged).
Thus, some portion of mempools will contain this poisoned low-fee child transaction and prevent the parent from being confirmed (because the parent+child fees are not enough to justify being put in a block).
Which I suppose is an argument for Full RBF aka ignore-the-RBF-flag-and-always-RBF.

The solution that I remember being proposed for this in Lightning was to give each participant its own attach-your-fees output that only that participant can spend, which works for Lightning because the set of participants in a channel is permanently fixed, but probably not for statechains.

--

The broadcasting of the kickoff simply means that the first stage cannot be easily changed, and you might still be able to make further updates by updating only the later stages, until the last stage is confirmable, so the kickoff being broadcast simply creates a "dead man walking" statechain.
However, the implementation complexity would probably increase tremendously.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Statechain implementations

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 3816 bytes --]

Hi ZmnSCPxj,

I appreciate the input.

>Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you
can use an `OP_TRUE` `redeemScript`, for instance.

Good point. I guess the conversation I recall reading must have been about
avoiding p2sh in order to lower the tx size.

>broadcast a non-RBF child transaction with tiny fee, so that it and its
parent transaction will be accepted into mempools but would not be
replaceable

I believe this is solved by inherited signalling. As long as the kickoff tx
is RBF enabled (and unconfirmed), any transaction spending it automatically
inherits its RBF status. See:
https://github.com/bitcoin/bips/blob/master/bip-0125.mediawiki#Summary

>The broadcasting of the kickoff simply means that the first stage cannot
be easily changed

I see what you're saying. Yeah, it does ruin the stages. If the kickoff tx
hits the chain, you'd probably just want to "refresh" the UTXO by agreeing
with the statechain entity to spend it to a new statechain 2-of-2 UTXO
on-chain, thus removing all prior owners. Ideally you'd want it to be more
costly to CPFP the kickoff tx than it is to refresh the UTXO, so the
defender is at an advantage. The statechain entity should probably pay for
every refresh ("insurance"), since the actual owner isn't at fault.

Cheers,
Ruben


On Fri, Mar 27, 2020 at 2:46 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Ruben,
>
> > Hey Christian,
> >
> > Thanks for chiming in :)
> >
> > >It might be worth adopting the late fee binding we have in eltoo
> >
> > That is where my thinking originally went as well, but then I remembered
> that this alters the txid, causing the settlement tx to become invalid.
> What I am suggesting should be functionally the same (albeit less
> space-efficient): a secondary output that can be spent by anyone, which can
> be used to fee bump the kickoff tx with CPFP. I believe this same idea was
> considered for Lightning as well at some point. Do you happen to recall if
> there was some kind of non-standardness issue with it?
>
> Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you
> can use an `OP_TRUE` `redeemScript`, for instance.
>
> Using an `OP_TRUE` `redeemScript` would allow any third party to make you
> cry by opportunistically spending such an output.
> For example your Bitcoin-network peer could notice you broadcasting such a
> transaction with an `OP_TRUE` output, see you spend that output with a
> CPFP-RBF-ed child transaction, then instead of further broadcasting the
> child transaction, instead broadcast a non-RBF child transaction with tiny
> fee, so that it and its parent transaction will be accepted into mempools
> but would not be replaceable with a higher-feerate child transaction
> (because not RBF-flagged).
> Thus, some portion of mempools will contain this poisoned low-fee child
> transaction and prevent the parent from being confirmed (because the
> parent+child fees are not enough to justify being put in a block).
> Which I suppose is an argument for Full RBF aka
> ignore-the-RBF-flag-and-always-RBF.
>
> The solution that I remember being proposed for this in Lightning was to
> give each participant its own attach-your-fees output that only that
> participant can spend, which works for Lightning because the set of
> participants in a channel is permanently fixed, but probably not for
> statechains.
>
> --
>
> The broadcasting of the kickoff simply means that the first stage cannot
> be easily changed, and you might still be able to make further updates by
> updating only the later stages, until the last stage is confirmable, so the
> kickoff being broadcast simply creates a "dead man walking" statechain.
> However, the implementation complexity would probably increase
> tremendously.
>
>
> Regards,
> ZmnSCPxj
>

[-- Attachment #2: Type: text/html, Size: 4481 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Ruben,


> >The broadcasting of the kickoff simply means that the first stage cannot be easily changed
>
> I see what you're saying. Yeah, it does ruin the stages. If the kickoff tx hits the chain, you'd probably just want to "refresh" the UTXO by agreeing with the statechain entity to spend it to a new statechain 2-of-2 UTXO on-chain, thus removing all prior owners. Ideally you'd want it to be more costly to CPFP the kickoff tx than it is to refresh the UTXO, so the defender is at an advantage. The statechain entity should probably pay for every refresh ("insurance"), since the actual owner isn't at fault.

Actually, thinking a little more, it seems that you can try to ensure that the first stage never drops to 0 relative locktime.
Then if somebody broadcasts the kick-off, the current owner can ask the statechain entity to sign an alternative to the first stage, with 0 relative locktime, that can now be a new funding transaction to anchor a (actually new, but logically a continuation) statechain.

Regards,
ZmnSCPxj

>
> Cheers,
> Ruben
>
> On Fri, Mar 27, 2020 at 2:46 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> > Good morning Ruben,
> >
> > > Hey Christian,
> > >
> > > Thanks for chiming in :)
> > >
> > > >It might be worth adopting the late fee binding we have in eltoo
> > >
> > > That is where my thinking originally went as well, but then I remembered that this alters the txid, causing the settlement tx to become invalid. What I am suggesting should be functionally the same (albeit less space-efficient): a secondary output that can be spent by anyone, which can be used to fee bump the kickoff tx with CPFP. I believe this same idea was considered for Lightning as well at some point. Do you happen to recall if there was some kind of non-standardness issue with it?
> >
> > Any standardness issue can be fixed by embedding it in a P2WSH / P2SH, you can use an `OP_TRUE` `redeemScript`, for instance.
> >
> > Using an `OP_TRUE` `redeemScript` would allow any third party to make you cry by opportunistically spending such an output.
> > For example your Bitcoin-network peer could notice you broadcasting such a transaction with an `OP_TRUE` output, see you spend that output with a CPFP-RBF-ed child transaction, then instead of further broadcasting the child transaction, instead broadcast a non-RBF child transaction with tiny fee, so that it and its parent transaction will be accepted into mempools but would not be replaceable with a higher-feerate child transaction (because not RBF-flagged).
> > Thus, some portion of mempools will contain this poisoned low-fee child transaction and prevent the parent from being confirmed (because the parent+child fees are not enough to justify being put in a block).
> > Which I suppose is an argument for Full RBF aka ignore-the-RBF-flag-and-always-RBF.
> >
> > The solution that I remember being proposed for this in Lightning was to give each participant its own attach-your-fees output that only that participant can spend, which works for Lightning because the set of participants in a channel is permanently fixed, but probably not for statechains.
> >
> > --
> >
> > The broadcasting of the kickoff simply means that the first stage cannot be easily changed, and you might still be able to make further updates by updating only the later stages, until the last stage is confirmable, so the kickoff being broadcast simply creates a "dead man walking" statechain.
> > However, the implementation complexity would probably increase tremendously.
> >
> > Regards,
> > ZmnSCPxj

Re: [bitcoin-dev] Statechain implementations

[Bob McElrath]

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 

Re: [bitcoin-dev] Statechain implementations

[Bob McElrath]

[-- Attachment #1: Type: text/plain, Size: 10474 bytes --]

Big picture, it seems to me this idea is workable and very interesting. I see
three likely enhancements that will be necessary or desirable:
    1. Atomic swap of multiple UTXOs, and binary decomposition of value in lots
    2. Key exchange ("addresses") to facilitate a secure comms path from 
        sender -> receiver
    3. (Optional) single-use seals to close old state

(1) It's unlikely that a party sending a UTXO to another party will have a UTXO
of exactly the right size that's needed, already locked into the statechain. If
he has to create the UTXO first and then lock it into the statechain, the
statechain solution is no better than an on-chain send. And once the receiver
has the UTXO, it's unlikely that he will want to send exactly that same amount
to another receiver later. This isn't a problem in Lightning where amounts can
be arbitrarily updated. As a consequence, I think Lightning is more valuable for
small-value payments, and statechains will be more valuable for larger values.

The natural solution is to decompose your outputs in a binary decomposition,
having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis, and so
on. Then when I want to send, I select the appropriate UTXOs as a binary
decomposition of the value I want to send, with a "lot size" of 1048576
satoshis, or the dust limit. The notion of "lots" like this is common in
traditional markets...many stocks are bought and sold in lots of 100, and forex
is traded in lots of $100,000. Users of a statechain therefore need log(V)
available UTXOs locked into the statechain, where V is their value in BTC.
Having fixed lot sizes like this also makes coinjoin-type uses more viable. The
statechain could also assist in dividing a UTXO into two utxos of the next lot
size down, so that I have the right UTXOs to hit the value I want to send.

This means that the statechain now has to *atomically* swap multiple UTXOs. In
principle, it should be possible for a statechain to circumvent the
Pagnia-Gärtner theorem[1] as it is a trusted third party, but guaranteed output
delivery will still be a problem. If a statechain can do this, it is also
capable of performing such swaps across two blockchains, creating the
execution/clearing element (but not order book) for a DEX. This same mechanism
can also be used to pay the SE for its service through a different UTXO than the
one being transferred.

Second (2), the steps in Tom's protocol presuppose a secure communications path
from the sender's wallet to the receiver's. This is probably not practical for a
myriad of reasons, but this data can be relayed through the SE if it is
encrypted for the target. This implies a new kind of "address" or "payment
request" that identifies the IP of the SE in use, pubkey of the
sender/recipient, and amount. If sender and receiver have each other's pubkeys
through another channel, as addresses/lightning payment requests are used today,
they can perform a Diffie-Hellman round mediated by the SE to establish a secure
communications path for the rounds of the protocol. Piggybacking on the
Lightning p2p network might be another option.

Third (3), a logical enhancement would be to use some kind of single-use seal,
which is "opened" when the UTXO is created or transferred, and "closed" when it
is transferred again. Thus a receiver can ensure that the sender is the holder
of current state and not some old state.  It's a good idea from Peter Todd, and
Tom's Mainstay[2] may be a way to do it. The SE itself can maintain a rolling
single-use seal Merkle root, periodically timestamped into Bitcoin for faster
time resolution than Bitcoin, if you trust the SE but not your counterparty
(which is the trust assumption present in the first place). Getting Bitcoin
itself to reject backout transactions from closed seals is another problem...but
having a single-use seal implementation involved is a start.

.. [1] https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.7863

.. [2] https://mainstay.xyz

Tom Trevethan via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] 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
> !DSPAM:5e7b7203210751402398759!

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

--
Cheers, Bob McElrath

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


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Bob,

> Big picture, it seems to me this idea is workable and very interesting. I see
> three likely enhancements that will be necessary or desirable:
> 1. Atomic swap of multiple UTXOs, and binary decomposition of value in lots
> 2. Key exchange ("addresses") to facilitate a secure comms path from
> sender -> receiver
>
>     3. (Optional) single-use seals to close old state
>
>
> (1) It's unlikely that a party sending a UTXO to another party will have a UTXO
> of exactly the right size that's needed, already locked into the statechain. If
> he has to create the UTXO first and then lock it into the statechain, the
> statechain solution is no better than an on-chain send. And once the receiver
> has the UTXO, it's unlikely that he will want to send exactly that same amount
> to another receiver later. This isn't a problem in Lightning where amounts can
> be arbitrarily updated. As a consequence, I think Lightning is more valuable for
> small-value payments, and statechains will be more valuable for larger values.
>
> The natural solution is to decompose your outputs in a binary decomposition,
> having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis, and so
> on. Then when I want to send, I select the appropriate UTXOs as a binary
> decomposition of the value I want to send, with a "lot size" of 1048576
> satoshis, or the dust limit. The notion of "lots" like this is common in
> traditional markets...many stocks are bought and sold in lots of 100, and forex
> is traded in lots of $100,000. Users of a statechain therefore need log(V)
> available UTXOs locked into the statechain, where V is their value in BTC.
> Having fixed lot sizes like this also makes coinjoin-type uses more viable. The
> statechain could also assist in dividing a UTXO into two utxos of the next lot
> size down, so that I have the right UTXOs to hit the value I want to send.

My understanding of statechains is that nothing prevents the statechain from internally having multiple UTXOs divided from a single large onchain UTXO.

Indeed, a statechain can act much like a federated blockchain, and the interface to the statechain could be for its clients to send a Bitcoin transaction to it spending 1 or more of the UTXOs currently instantiated inside the statechain.
Then the statechain validates the client Bitcoin transaction, updates its state and republishes it to its clients, removing the (internal-to-statechain-only) UTXOs spent, and inserting the new UTXOs of the incoming transaction.

For example, suppose I have a 1BTC onchain UTXO that I use to create a new statechain:

    [funding tx]->1BTC(SE)-+  (onchain)
    _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
              (statechain) |
                           +->[update mechanism]->1BTC(ZmnSCPxj)

Then I send to the statechain a transaction spending my 1BTC-on-statechain, giving you 0.11568768 BTC:

    [funding tx]->1BTC(SE)-+  (onchain)
    _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
              (statechain) |
                           +->[update mechanism]->1BTC(ZmnSCPxj)->[tx]-+->0.11568768BTC(bsm117532)
                                                                       +->0.88431232BTC(ZmnSCPxj)

The statechain verifies that the tx I sent is valid, then outputs the next state as below:

    [funding tx]->1BTC(SE)-+  (onchain)
    _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
              (statechain) |
                           +->[update mechanism]-+->0.11568768BTC(bsm117532)
                                                 +->0.88431232BTC(ZmnSCPxj)

In short, statechains can be implemented as a sort of super-transaction-cutthrough system.

This prevents the onchain UTXO from having a single logical owner, of course, so onchain it is the statechain entity that owns the entire fund, but if you are trusting the statechain entity anyway, the update mechanism is sufficient to ensure that nobody (other than the trusted statechain) can prevent the publication of the latest accepted state.

This is probably significantly more efficient than splitting up the 1BTC value to multiple lots.

I think this framework will work for all offchain mechanisms (CoinSwap, Lightning, statechains), by the way --- you can always view the offchain update mechanism as logically implementing a "new" cryptocurrency system that maintains UTXO sets and allows removal and insertion of UTXO sets according to the same rules (sans relative-locktime) as the hosting cryptocurrency system (i.e. the blockchain).
The same realization is what underlies channel factories as well --- the hosting cryptocurrency system need not be a blockchain, it can be just another cryptocurrency system (of which a blockchain is just one kind).

My understanding is that the original description, which describes transferring the entire value inside the statechain to a new owner, was only for exposition and that it was an exercise for the reader to consider how a statechain can internally split the total value among multiple UTXOs.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Statechain implementations

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 7694 bytes --]

Hi Bob,

Looks like we're largely thinking along the same lines.

It's unlikely that a party sending a UTXO to another party will have a UTXO
> of exactly the right size that's needed


My original proposal uses adaptor signatures to ensure swapping UTXOs is
atomic. All parties choose a secret, then they all make adaptor signatures,
then they reveal their secret to the statechain entity. The SE then
publishes the signatures, causing everyone to learn the secret. And if the
SE doesn't publish, it simply means the transfer didn't occur.

But taking a step back and thinking about an MVP, it may be easier to make
it more like a fully audited transparent blockchain where multiple users
create a combined transaction of all the UTXOs they want to swap, which is
published together with all the corresponding Bitcoin transactions. Then
adaptor signatures aren't needed.

The downside of that method is that you lose the ability to only validate
the history of the coins you hold (scalability win). For this to be
possible, you need to keep the history of every individual UTXO completely
separate. I still think that is where we eventually want to end up (as well
as having blind signatures), but it adds a lot of complexity (adaptor
signatures, sparse merkle trees with non-inclusion proofs...).

The natural solution is to decompose your outputs in a binary decomposition


I fully agree, but on top of that I think we also need Lightning,
because....

This same mechanism can also be used to pay the SE for its service through
> a different UTXO than the one being transferred.


My conclusion was that opening a Lightning channel on top of a statechain
makes more sense for this (as ZmnSCPxj explained in his reply to you). If
we expect BTC fees to go up, we can't expect the statechain to hold UTXOs
that are small enough to be used to pay for statechain fees.

More on this in my Breaking Bitcoin 2019 talk (timestamped link):
https://youtu.be/09HcYRjDkMA?t=850

a logical enhancement would be to use some kind of single-use seal


Any kind of system where users transfer ownership through signatures will
resemble single-use seals, so I'd say that's inevitable! :)

Cheers,
Ruben


On Sat, Mar 28, 2020 at 3:42 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Bob,
>
> > Big picture, it seems to me this idea is workable and very interesting.
> I see
> > three likely enhancements that will be necessary or desirable:
> > 1. Atomic swap of multiple UTXOs, and binary decomposition of value in
> lots
> > 2. Key exchange ("addresses") to facilitate a secure comms path from
> > sender -> receiver
> >
> >     3. (Optional) single-use seals to close old state
> >
> >
> > (1) It's unlikely that a party sending a UTXO to another party will have
> a UTXO
> > of exactly the right size that's needed, already locked into the
> statechain. If
> > he has to create the UTXO first and then lock it into the statechain, the
> > statechain solution is no better than an on-chain send. And once the
> receiver
> > has the UTXO, it's unlikely that he will want to send exactly that same
> amount
> > to another receiver later. This isn't a problem in Lightning where
> amounts can
> > be arbitrarily updated. As a consequence, I think Lightning is more
> valuable for
> > small-value payments, and statechains will be more valuable for larger
> values.
> >
> > The natural solution is to decompose your outputs in a binary
> decomposition,
> > having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis,
> and so
> > on. Then when I want to send, I select the appropriate UTXOs as a binary
> > decomposition of the value I want to send, with a "lot size" of 1048576
> > satoshis, or the dust limit. The notion of "lots" like this is common in
> > traditional markets...many stocks are bought and sold in lots of 100,
> and forex
> > is traded in lots of $100,000. Users of a statechain therefore need
> log(V)
> > available UTXOs locked into the statechain, where V is their value in
> BTC.
> > Having fixed lot sizes like this also makes coinjoin-type uses more
> viable. The
> > statechain could also assist in dividing a UTXO into two utxos of the
> next lot
> > size down, so that I have the right UTXOs to hit the value I want to
> send.
>
> My understanding of statechains is that nothing prevents the statechain
> from internally having multiple UTXOs divided from a single large onchain
> UTXO.
>
> Indeed, a statechain can act much like a federated blockchain, and the
> interface to the statechain could be for its clients to send a Bitcoin
> transaction to it spending 1 or more of the UTXOs currently instantiated
> inside the statechain.
> Then the statechain validates the client Bitcoin transaction, updates its
> state and republishes it to its clients, removing the
> (internal-to-statechain-only) UTXOs spent, and inserting the new UTXOs of
> the incoming transaction.
>
> For example, suppose I have a 1BTC onchain UTXO that I use to create a new
> statechain:
>
>     [funding tx]->1BTC(SE)-+  (onchain)
>     _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
>               (statechain) |
>                            +->[update mechanism]->1BTC(ZmnSCPxj)
>
> Then I send to the statechain a transaction spending my
> 1BTC-on-statechain, giving you 0.11568768 BTC:
>
>     [funding tx]->1BTC(SE)-+  (onchain)
>     _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
>               (statechain) |
>                            +->[update
> mechanism]->1BTC(ZmnSCPxj)->[tx]-+->0.11568768BTC(bsm117532)
>
>  +->0.88431232BTC(ZmnSCPxj)
>
> The statechain verifies that the tx I sent is valid, then outputs the next
> state as below:
>
>     [funding tx]->1BTC(SE)-+  (onchain)
>     _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
>               (statechain) |
>                            +->[update
> mechanism]-+->0.11568768BTC(bsm117532)
>                                                  +->0.88431232BTC(ZmnSCPxj)
>
> In short, statechains can be implemented as a sort of
> super-transaction-cutthrough system.
>
> This prevents the onchain UTXO from having a single logical owner, of
> course, so onchain it is the statechain entity that owns the entire fund,
> but if you are trusting the statechain entity anyway, the update mechanism
> is sufficient to ensure that nobody (other than the trusted statechain) can
> prevent the publication of the latest accepted state.
>
> This is probably significantly more efficient than splitting up the 1BTC
> value to multiple lots.
>
> I think this framework will work for all offchain mechanisms (CoinSwap,
> Lightning, statechains), by the way --- you can always view the offchain
> update mechanism as logically implementing a "new" cryptocurrency system
> that maintains UTXO sets and allows removal and insertion of UTXO sets
> according to the same rules (sans relative-locktime) as the hosting
> cryptocurrency system (i.e. the blockchain).
> The same realization is what underlies channel factories as well --- the
> hosting cryptocurrency system need not be a blockchain, it can be just
> another cryptocurrency system (of which a blockchain is just one kind).
>
> My understanding is that the original description, which describes
> transferring the entire value inside the statechain to a new owner, was
> only for exposition and that it was an exercise for the reader to consider
> how a statechain can internally split the total value among multiple UTXOs.
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 9644 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Ruben Somsen]

[-- Attachment #1: Type: text/plain, Size: 8525 bytes --]

Hi ZmnSCPxj,

the current owner can ask the statechain entity to sign an alternative to
> the first stage, with 0 relative locktime


Unless I am misunderstanding something, this seems to run into the problem
that the original first stage transaction is already out there (and its
relative timelock started ticking). There is no mechanism ensuring that the
new tx will have precedence. And even if it did work, I doubt it's cleaner
than doing a cooperative peg-out that simultaneously happens to peg back
in, creating a brand new statechain UTXO with no history.

Cheers,
Ruben

On Sat, Mar 28, 2020 at 6:38 PM Ruben Somsen <rsomsen@gmail.com> wrote:

> Hi Bob,
>
> Looks like we're largely thinking along the same lines.
>
> It's unlikely that a party sending a UTXO to another party will have a
>> UTXO of exactly the right size that's needed
>
>
> My original proposal uses adaptor signatures to ensure swapping UTXOs is
> atomic. All parties choose a secret, then they all make adaptor signatures,
> then they reveal their secret to the statechain entity. The SE then
> publishes the signatures, causing everyone to learn the secret. And if the
> SE doesn't publish, it simply means the transfer didn't occur.
>
> But taking a step back and thinking about an MVP, it may be easier to make
> it more like a fully audited transparent blockchain where multiple users
> create a combined transaction of all the UTXOs they want to swap, which is
> published together with all the corresponding Bitcoin transactions. Then
> adaptor signatures aren't needed.
>
> The downside of that method is that you lose the ability to only validate
> the history of the coins you hold (scalability win). For this to be
> possible, you need to keep the history of every individual UTXO completely
> separate. I still think that is where we eventually want to end up (as well
> as having blind signatures), but it adds a lot of complexity (adaptor
> signatures, sparse merkle trees with non-inclusion proofs...).
>
> The natural solution is to decompose your outputs in a binary decomposition
>
>
> I fully agree, but on top of that I think we also need Lightning,
> because....
>
> This same mechanism can also be used to pay the SE for its service through
>> a different UTXO than the one being transferred.
>
>
> My conclusion was that opening a Lightning channel on top of a statechain
> makes more sense for this (as ZmnSCPxj explained in his reply to you). If
> we expect BTC fees to go up, we can't expect the statechain to hold UTXOs
> that are small enough to be used to pay for statechain fees.
>
> More on this in my Breaking Bitcoin 2019 talk (timestamped link):
> https://youtu.be/09HcYRjDkMA?t=850
>
> a logical enhancement would be to use some kind of single-use seal
>
>
> Any kind of system where users transfer ownership through signatures will
> resemble single-use seals, so I'd say that's inevitable! :)
>
> Cheers,
> Ruben
>
>
> On Sat, Mar 28, 2020 at 3:42 AM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Good morning Bob,
>>
>> > Big picture, it seems to me this idea is workable and very interesting.
>> I see
>> > three likely enhancements that will be necessary or desirable:
>> > 1. Atomic swap of multiple UTXOs, and binary decomposition of value in
>> lots
>> > 2. Key exchange ("addresses") to facilitate a secure comms path from
>> > sender -> receiver
>> >
>> >     3. (Optional) single-use seals to close old state
>> >
>> >
>> > (1) It's unlikely that a party sending a UTXO to another party will
>> have a UTXO
>> > of exactly the right size that's needed, already locked into the
>> statechain. If
>> > he has to create the UTXO first and then lock it into the statechain,
>> the
>> > statechain solution is no better than an on-chain send. And once the
>> receiver
>> > has the UTXO, it's unlikely that he will want to send exactly that same
>> amount
>> > to another receiver later. This isn't a problem in Lightning where
>> amounts can
>> > be arbitrarily updated. As a consequence, I think Lightning is more
>> valuable for
>> > small-value payments, and statechains will be more valuable for larger
>> values.
>> >
>> > The natural solution is to decompose your outputs in a binary
>> decomposition,
>> > having e.g. UTXOs with 1048576 satoshis, another with 2097152 satoshis,
>> and so
>> > on. Then when I want to send, I select the appropriate UTXOs as a binary
>> > decomposition of the value I want to send, with a "lot size" of 1048576
>> > satoshis, or the dust limit. The notion of "lots" like this is common in
>> > traditional markets...many stocks are bought and sold in lots of 100,
>> and forex
>> > is traded in lots of $100,000. Users of a statechain therefore need
>> log(V)
>> > available UTXOs locked into the statechain, where V is their value in
>> BTC.
>> > Having fixed lot sizes like this also makes coinjoin-type uses more
>> viable. The
>> > statechain could also assist in dividing a UTXO into two utxos of the
>> next lot
>> > size down, so that I have the right UTXOs to hit the value I want to
>> send.
>>
>> My understanding of statechains is that nothing prevents the statechain
>> from internally having multiple UTXOs divided from a single large onchain
>> UTXO.
>>
>> Indeed, a statechain can act much like a federated blockchain, and the
>> interface to the statechain could be for its clients to send a Bitcoin
>> transaction to it spending 1 or more of the UTXOs currently instantiated
>> inside the statechain.
>> Then the statechain validates the client Bitcoin transaction, updates its
>> state and republishes it to its clients, removing the
>> (internal-to-statechain-only) UTXOs spent, and inserting the new UTXOs of
>> the incoming transaction.
>>
>> For example, suppose I have a 1BTC onchain UTXO that I use to create a
>> new statechain:
>>
>>     [funding tx]->1BTC(SE)-+  (onchain)
>>     _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
>>               (statechain) |
>>                            +->[update mechanism]->1BTC(ZmnSCPxj)
>>
>> Then I send to the statechain a transaction spending my
>> 1BTC-on-statechain, giving you 0.11568768 BTC:
>>
>>     [funding tx]->1BTC(SE)-+  (onchain)
>>     _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
>>               (statechain) |
>>                            +->[update
>> mechanism]->1BTC(ZmnSCPxj)->[tx]-+->0.11568768BTC(bsm117532)
>>
>>  +->0.88431232BTC(ZmnSCPxj)
>>
>> The statechain verifies that the tx I sent is valid, then outputs the
>> next state as below:
>>
>>     [funding tx]->1BTC(SE)-+  (onchain)
>>     _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _
>>               (statechain) |
>>                            +->[update
>> mechanism]-+->0.11568768BTC(bsm117532)
>>
>>  +->0.88431232BTC(ZmnSCPxj)
>>
>> In short, statechains can be implemented as a sort of
>> super-transaction-cutthrough system.
>>
>> This prevents the onchain UTXO from having a single logical owner, of
>> course, so onchain it is the statechain entity that owns the entire fund,
>> but if you are trusting the statechain entity anyway, the update mechanism
>> is sufficient to ensure that nobody (other than the trusted statechain) can
>> prevent the publication of the latest accepted state.
>>
>> This is probably significantly more efficient than splitting up the 1BTC
>> value to multiple lots.
>>
>> I think this framework will work for all offchain mechanisms (CoinSwap,
>> Lightning, statechains), by the way --- you can always view the offchain
>> update mechanism as logically implementing a "new" cryptocurrency system
>> that maintains UTXO sets and allows removal and insertion of UTXO sets
>> according to the same rules (sans relative-locktime) as the hosting
>> cryptocurrency system (i.e. the blockchain).
>> The same realization is what underlies channel factories as well --- the
>> hosting cryptocurrency system need not be a blockchain, it can be just
>> another cryptocurrency system (of which a blockchain is just one kind).
>>
>> My understanding is that the original description, which describes
>> transferring the entire value inside the statechain to a new owner, was
>> only for exposition and that it was an exercise for the reader to consider
>> how a statechain can internally split the total value among multiple UTXOs.
>>
>> Regards,
>> ZmnSCPxj
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 10822 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Ruben,

> Hi ZmnSCPxj,
>
> > the current owner can ask the statechain entity to sign an alternative to the first stage, with 0 relative locktime
>
> Unless I am misunderstanding something, this seems to run into the problem that the original first stage transaction is already out there (and its relative timelock started ticking). There is no mechanism ensuring that the new tx will have precedence. And even if it did work, I doubt it's cleaner than doing a cooperative peg-out that simultaneously happens to peg back in, creating a brand new statechain UTXO with no history.


If:

* You are sure the old first stage tx has > 0 relative locktime.
* The replacement tx (which replaces the old first stage) has a 0 relative locktime.
  * The replacement tx redirects the funds to a new funding output for a (logically continuous, onchain new) statechain.

Then the replacement tx, having a smaller relative locktime than the old first stage, has precedence.
Indeed, having a *smaller* relative locktime is exactly the mechanism Decker-Wattenhofer uses.

So this is the state, with the kickoff having just been confirmed onchain:


    ***blockchain***
       [funding tx]->[kickoff tx]-+
         _ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _
     offchain                     |
                                  +->[[ 7] stage]->[[ 0] stage]->[[14] stage]-> state outputs

Since the first stage is still "ticking" it is not yet confirmable onchain.

You ask the statechain to create an alternative, 0-relative-locktime, re-funding tx, and create a new mechanism:

    ***blockchain***
       [funding tx]->[kickoff tx]-+
         _ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _
     offchain                     |
                                  +->[[ 7] stage]->[[ 0] stage]->[[14] stage]-> state outputs
                                 (OR)
                                  |
                                  +->[[ 0] funding tx]->[kickoff tx]->[[14] stage]->[[14] stage]->[[14] stage]->state outputs

Because it has a time advantage, this new re-funding tx has higher priority (and is the same mechanism Decker-Wattenhofer has anyway).

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Statechain implementations

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 2384 bytes --]

On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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),
>
> [...]
> There are two main modifications we are looking at:
> [...]
> 
> 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. 

Dr. Trevethan,

Would you be able to explain how your proposal to use statechains with
2P-ECDSA relates to your patent assigned to nChain Holdings for "Secure
off-chain blockchain transactions"?[1]  

    [1] https://patents.google.com/patent/US20200074464A1

Here are some excerpts from the application that caught my attention in
the context of statechains in general and your proposal to this list in
particular:

> an exchange platform that is trusted to implement and operate the
> transaction protocol, without requiring an on-chain transaction. The
> off-chain transactions enable one computer system to generate multiple
> transactions that are recordable to a blockchain in different
> circumstances
>
> [...]
>
> at least some of the off-chain transactions are valid for recording on
> the blockchain even in the event of a catastrophic failure of the
> exchange (e.g., exchange going permanently off-line or loosing key
> shares).
>
> [...]
>
> there may be provided a computer readable storage medium including a
> two-party elliptic curve digital signature algorithm (two-party ECDSA)
> script comprising computer executable instructions which, when
> executed, configure a processor to perform functions of a two-party
> elliptic curve digital signature algorithm described herein.
>
> [...]
>
> In this instance the malicious actor would then also have to collude
> with a previous owner of the funds to recreate the full key. Because
> an attack requires either the simultaneous theft of both exchange and
> depositor keys or collusion with previous legitimate owners of funds,
> the opportunities for a malicious attacker to compromise the exchange
> platform are limited.

Thank you,

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Tom Trevethan]

[-- Attachment #1: Type: text/plain, Size: 3931 bytes --]

Hi David,

Just for clarity, I left nChain over 2 years ago (having worked there since
2016). While there, I (along with other researchers) were given free rein
to work on any ideas we wanted to. I had been interested in the scaling of
Bitcoin off-chain, and this was one of several things I spent time on
(including things like sidechains, pegs and threshold signatures). This
patent application came out of an idea I had to transfer ownership of UTXOs
off-chain that has some similarities to the statechains proposal, which has
shown there is interest and demand for this type of system.

Although I think the existence of this application is something to be
mindful of, there are several important things to note:

1. Although there are similarities, the current ideas are significantly
different to those in the application.
2. The key transfer protocol as described in the application is not secure
(for several reasons, including as discussed above, by Albert and Bob etc.)
- and a different mechanism is required.
3. Decrementing timelocks (as suggested in the application) are prior art
(Decker-Wattenhofer 2015), and in any case any implementation will most
likely use an 'invalidation tree' relative locktime backup mechanism for
open-ended UTXOs.
4. The patent application has not been granted (it was made in May 2017)
and the international search report rejected it on the grounds of prior
art.

Tom

On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave@dtrt.org> wrote:

> On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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
> ),
> >
> > [...]
> > There are two main modifications we are looking at:
> > [...]
> >
> > 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.
>
> Dr. Trevethan,
>
> Would you be able to explain how your proposal to use statechains with
> 2P-ECDSA relates to your patent assigned to nChain Holdings for "Secure
> off-chain blockchain transactions"?[1]
>
>     [1] https://patents.google.com/patent/US20200074464A1
>
> Here are some excerpts from the application that caught my attention in
> the context of statechains in general and your proposal to this list in
> particular:
>
> > an exchange platform that is trusted to implement and operate the
> > transaction protocol, without requiring an on-chain transaction. The
> > off-chain transactions enable one computer system to generate multiple
> > transactions that are recordable to a blockchain in different
> > circumstances
> >
> > [...]
> >
> > at least some of the off-chain transactions are valid for recording on
> > the blockchain even in the event of a catastrophic failure of the
> > exchange (e.g., exchange going permanently off-line or loosing key
> > shares).
> >
> > [...]
> >
> > there may be provided a computer readable storage medium including a
> > two-party elliptic curve digital signature algorithm (two-party ECDSA)
> > script comprising computer executable instructions which, when
> > executed, configure a processor to perform functions of a two-party
> > elliptic curve digital signature algorithm described herein.
> >
> > [...]
> >
> > In this instance the malicious actor would then also have to collude
> > with a previous owner of the funds to recreate the full key. Because
> > an attack requires either the simultaneous theft of both exchange and
> > depositor keys or collusion with previous legitimate owners of funds,
> > the opportunities for a malicious attacker to compromise the exchange
> > platform are limited.
>
> Thank you,
>
> -Dave
>

[-- Attachment #2: Type: text/html, Size: 4911 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Tom Trevethan]

[-- Attachment #1: Type: text/plain, Size: 4717 bytes --]

Thanks for all of the input and comments - I do now think that the
decrementing nSequence relative locktime backup system with kick-off
transaction is the way to go, including a fee penalty via CPFP to
disincentivise DoS, as suggested.
I have started a more detailed document specifying the proposed protocol in
more detail:
https://github.com/commerceblock/mercury/blob/master/statechains.md which
includes improvements to the transfer mechanism (and an explanation of how
this can be used to transfer/novate positions in DLCs). Always happy to get
more feedback or PRs.

Tom

On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <tom@commerceblock.com>
wrote:

> Hi David,
>
> Just for clarity, I left nChain over 2 years ago (having worked there
> since 2016). While there, I (along with other researchers) were given free
> rein to work on any ideas we wanted to. I had been interested in the
> scaling of Bitcoin off-chain, and this was one of several things I spent
> time on (including things like sidechains, pegs and threshold signatures).
> This patent application came out of an idea I had to transfer ownership of
> UTXOs off-chain that has some similarities to the statechains proposal,
> which has shown there is interest and demand for this type of system.
>
> Although I think the existence of this application is something to be
> mindful of, there are several important things to note:
>
> 1. Although there are similarities, the current ideas are significantly
> different to those in the application.
> 2. The key transfer protocol as described in the application is not secure
> (for several reasons, including as discussed above, by Albert and Bob etc.)
> - and a different mechanism is required.
> 3. Decrementing timelocks (as suggested in the application) are prior art
> (Decker-Wattenhofer 2015), and in any case any implementation will most
> likely use an 'invalidation tree' relative locktime backup mechanism for
> open-ended UTXOs.
> 4. The patent application has not been granted (it was made in May 2017)
> and the international search report rejected it on the grounds of prior
> art.
>
> Tom
>
> On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave@dtrt.org> wrote:
>
>> On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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
>> ),
>> >
>> > [...]
>> > There are two main modifications we are looking at:
>> > [...]
>> >
>> > 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.
>>
>> Dr. Trevethan,
>>
>> Would you be able to explain how your proposal to use statechains with
>> 2P-ECDSA relates to your patent assigned to nChain Holdings for "Secure
>> off-chain blockchain transactions"?[1]
>>
>>     [1] https://patents.google.com/patent/US20200074464A1
>>
>> Here are some excerpts from the application that caught my attention in
>> the context of statechains in general and your proposal to this list in
>> particular:
>>
>> > an exchange platform that is trusted to implement and operate the
>> > transaction protocol, without requiring an on-chain transaction. The
>> > off-chain transactions enable one computer system to generate multiple
>> > transactions that are recordable to a blockchain in different
>> > circumstances
>> >
>> > [...]
>> >
>> > at least some of the off-chain transactions are valid for recording on
>> > the blockchain even in the event of a catastrophic failure of the
>> > exchange (e.g., exchange going permanently off-line or loosing key
>> > shares).
>> >
>> > [...]
>> >
>> > there may be provided a computer readable storage medium including a
>> > two-party elliptic curve digital signature algorithm (two-party ECDSA)
>> > script comprising computer executable instructions which, when
>> > executed, configure a processor to perform functions of a two-party
>> > elliptic curve digital signature algorithm described herein.
>> >
>> > [...]
>> >
>> > In this instance the malicious actor would then also have to collude
>> > with a previous owner of the funds to recreate the full key. Because
>> > an attack requires either the simultaneous theft of both exchange and
>> > depositor keys or collusion with previous legitimate owners of funds,
>> > the opportunities for a malicious attacker to compromise the exchange
>> > platform are limited.
>>
>> Thank you,
>>
>> -Dave
>>
>

[-- Attachment #2: Type: text/html, Size: 5989 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Nadav Kohen]

[-- Attachment #1: Type: text/plain, Size: 6382 bytes --]

Hey all,

So my main concern with the proposal as written is that the Statechain
Entity (SE) can untraceably scam its users with the following attack:

1) Buy the utxo (have it transferred to a key it knows), this first step
can be skipped if the utxo was created by the SE.
2) Transfer the UTXO to someone else, let it be for however long
3) When it wishes to steal the UTXO, the SE now knows its own shard s_n and
it  knows the full private key, x, from when it owned the UTXO (and had
both shards), and so it can compute x/s_n = the current users shard. It can
then sign for the current user, and forge a state transition to a key it
owns before spending the UTXO on chain.

The main problem here is that the user who had their funds stolen cannot
prove to anyone that this has happened since the attack compromises their
key.
That said, I think this problem is easily fixed by adding a new user key to
the protocol with which they must sign in order for the transfer to be
considered valid on the state chain. This way, if the SE wishes to steal
the funds (which they still can), at least it is traceable/provable that
this SE is not trustworthy as there is no evidence of a valid transfer for
the funds that have been stolen.

Best,
Nadav

On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Thanks for all of the input and comments - I do now think that the
> decrementing nSequence relative locktime backup system with kick-off
> transaction is the way to go, including a fee penalty via CPFP to
> disincentivise DoS, as suggested.
> I have started a more detailed document specifying the proposed protocol
> in more detail:
> https://github.com/commerceblock/mercury/blob/master/statechains.md which
> includes improvements to the transfer mechanism (and an explanation of how
> this can be used to transfer/novate positions in DLCs). Always happy to get
> more feedback or PRs.
>
> Tom
>
> On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <tom@commerceblock.com>
> wrote:
>
>> Hi David,
>>
>> Just for clarity, I left nChain over 2 years ago (having worked there
>> since 2016). While there, I (along with other researchers) were given free
>> rein to work on any ideas we wanted to. I had been interested in the
>> scaling of Bitcoin off-chain, and this was one of several things I spent
>> time on (including things like sidechains, pegs and threshold signatures).
>> This patent application came out of an idea I had to transfer ownership of
>> UTXOs off-chain that has some similarities to the statechains proposal,
>> which has shown there is interest and demand for this type of system.
>>
>> Although I think the existence of this application is something to be
>> mindful of, there are several important things to note:
>>
>> 1. Although there are similarities, the current ideas are significantly
>> different to those in the application.
>> 2. The key transfer protocol as described in the application is not
>> secure (for several reasons, including as discussed above, by Albert and
>> Bob etc.) - and a different mechanism is required.
>> 3. Decrementing timelocks (as suggested in the application) are prior art
>> (Decker-Wattenhofer 2015), and in any case any implementation will most
>> likely use an 'invalidation tree' relative locktime backup mechanism for
>> open-ended UTXOs.
>> 4. The patent application has not been granted (it was made in May 2017)
>> and the international search report rejected it on the grounds of prior
>> art.
>>
>> Tom
>>
>> On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave@dtrt.org> wrote:
>>
>>> On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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
>>> ),
>>> >
>>> > [...]
>>> > There are two main modifications we are looking at:
>>> > [...]
>>> >
>>> > 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.
>>>
>>> Dr. Trevethan,
>>>
>>> Would you be able to explain how your proposal to use statechains with
>>> 2P-ECDSA relates to your patent assigned to nChain Holdings for "Secure
>>> off-chain blockchain transactions"?[1]
>>>
>>>     [1] https://patents.google.com/patent/US20200074464A1
>>>
>>> Here are some excerpts from the application that caught my attention in
>>> the context of statechains in general and your proposal to this list in
>>> particular:
>>>
>>> > an exchange platform that is trusted to implement and operate the
>>> > transaction protocol, without requiring an on-chain transaction. The
>>> > off-chain transactions enable one computer system to generate multiple
>>> > transactions that are recordable to a blockchain in different
>>> > circumstances
>>> >
>>> > [...]
>>> >
>>> > at least some of the off-chain transactions are valid for recording on
>>> > the blockchain even in the event of a catastrophic failure of the
>>> > exchange (e.g., exchange going permanently off-line or loosing key
>>> > shares).
>>> >
>>> > [...]
>>> >
>>> > there may be provided a computer readable storage medium including a
>>> > two-party elliptic curve digital signature algorithm (two-party ECDSA)
>>> > script comprising computer executable instructions which, when
>>> > executed, configure a processor to perform functions of a two-party
>>> > elliptic curve digital signature algorithm described herein.
>>> >
>>> > [...]
>>> >
>>> > In this instance the malicious actor would then also have to collude
>>> > with a previous owner of the funds to recreate the full key. Because
>>> > an attack requires either the simultaneous theft of both exchange and
>>> > depositor keys or collusion with previous legitimate owners of funds,
>>> > the opportunities for a malicious attacker to compromise the exchange
>>> > platform are limited.
>>>
>>> Thank you,
>>>
>>> -Dave
>>>
>> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 8182 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Nadav,

Indeed.

It seems to me that practical deployments of statechains requires the statechain operator to be a trusted federation, possibly a k-of-n.
This is slightly better than a federated sidechain because the money can always be reclaimed on the blockchain layer very quickly in case of a loss of trust in the federation.
If the k-of-n is arranged in such a way that the signers can be identified (such as by use of old `OP_CHECKMULTISIG` or some combination of the proposed `OP_CHECKSIGADD`) then it has the same "auditability", i.e. you can identify the pseudonyms of the members who cheated (which is not worth much, as getting a new pseudonym is trivial).

It is helpful to remember that a k-of-n federation can only be trusted if you have full trust in at least (n - k + 1) members of the federation.

Regards,
ZmnSCPxj

> Hey all,
>
> So my main concern with the proposal as written is that the Statechain Entity (SE) can untraceably scam its users with the following attack:
> 1) Buy the utxo (have it transferred to a key it knows), this first step can be skipped if the utxo was created by the SE.
> 2) Transfer the UTXO to someone else, let it be for however long
> 3) When it wishes to steal the UTXO, the SE now knows its own shard s_n and it  knows the full private key, x, from when it owned the UTXO (and had both shards), and so it can compute x/s_n = the current users shard. It can then sign for the current user, and forge a state transition to a key it owns before spending the UTXO on chain.
>
> The main problem here is that the user who had their funds stolen cannot prove to anyone that this has happened since the attack compromises their key.
> That said, I think this problem is easily fixed by adding a new user key to the protocol with which they must sign in order for the transfer to be considered valid on the state chain. This way, if the SE wishes to steal the funds (which they still can), at least it is traceable/provable that this SE is not trustworthy as there is no evidence of a valid transfer for the funds that have been stolen.
>
> Best,
> Nadav
>
> On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > Thanks for all of the input and comments - I do now think that the decrementing nSequence relative locktime backup system with kick-off transaction is the way to go, including a fee penalty via CPFP to disincentivise DoS, as suggested. 
> > I have started a more detailed document specifying the proposed protocol in more detail: https://github.com/commerceblock/mercury/blob/master/statechains.md which includes improvements to the transfer mechanism (and an explanation of how this can be used to transfer/novate positions in DLCs). Always happy to get more feedback or PRs. 
> >
> > Tom
> >
> > On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <tom@commerceblock.com> wrote:
> >
> > > Hi David,
> > >
> > > Just for clarity, I left nChain over 2 years ago (having worked there since 2016). While there, I (along with other researchers) were given free rein to work on any ideas we wanted to. I had been interested in the scaling of Bitcoin off-chain, and this was one of several things I spent time on (including things like sidechains, pegs and threshold signatures). This patent application came out of an idea I had to transfer ownership of UTXOs off-chain that has some similarities to the statechains proposal, which has shown there is interest and demand for this type of system. 
> > >
> > > Although I think the existence of this application is something to be mindful of, there are several important things to note:
> > >
> > > 1. Although there are similarities, the current ideas are significantly different to those in the application. 
> > > 2. The key transfer protocol as described in the application is not secure (for several reasons, including as discussed above, by Albert and Bob etc.) - and a different mechanism is required. 
> > > 3. Decrementing timelocks (as suggested in the application) are prior art (Decker-Wattenhofer 2015), and in any case any implementation will most likely use an 'invalidation tree' relative locktime backup mechanism for open-ended UTXOs. 
> > > 4. The patent application has not been granted (it was made in May 2017) and the international search report rejected it on the grounds of prior art. 
> > >
> > > Tom
> > >
> > > On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave@dtrt.org> wrote:
> > >
> > > > On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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),
> > > > >
> > > > > [...]
> > > > > There are two main modifications we are looking at:
> > > > > [...]
> > > > >
> > > > > 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.
> > > >
> > > > Dr. Trevethan,
> > > >
> > > > Would you be able to explain how your proposal to use statechains with
> > > > 2P-ECDSA relates to your patent assigned to nChain Holdings for "Secure
> > > > off-chain blockchain transactions"?[1] 
> > > >
> > > >     [1] https://patents.google.com/patent/US20200074464A1
> > > >
> > > > Here are some excerpts from the application that caught my attention in
> > > > the context of statechains in general and your proposal to this list in
> > > > particular:
> > > >
> > > > > an exchange platform that is trusted to implement and operate the
> > > > > transaction protocol, without requiring an on-chain transaction. The
> > > > > off-chain transactions enable one computer system to generate multiple
> > > > > transactions that are recordable to a blockchain in different
> > > > > circumstances
> > > > >
> > > > > [...]
> > > > >
> > > > > at least some of the off-chain transactions are valid for recording on
> > > > > the blockchain even in the event of a catastrophic failure of the
> > > > > exchange (e.g., exchange going permanently off-line or loosing key
> > > > > shares).
> > > > >
> > > > > [...]
> > > > >
> > > > > there may be provided a computer readable storage medium including a
> > > > > two-party elliptic curve digital signature algorithm (two-party ECDSA)
> > > > > script comprising computer executable instructions which, when
> > > > > executed, configure a processor to perform functions of a two-party
> > > > > elliptic curve digital signature algorithm described herein.
> > > > >
> > > > > [...]
> > > > >
> > > > > In this instance the malicious actor would then also have to collude
> > > > > with a previous owner of the funds to recreate the full key. Because
> > > > > an attack requires either the simultaneous theft of both exchange and
> > > > > depositor keys or collusion with previous legitimate owners of funds,
> > > > > the opportunities for a malicious attacker to compromise the exchange
> > > > > platform are limited.
> > > >
> > > > Thank you,
> > > >
> > > > -Dave
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Statechain implementations

[Bob McElrath]

[-- Attachment #1: Type: text/plain, Size: 10445 bytes --]

Note that this attack requires collaboration with the current UTXO owner.
Generally if there's some form of address/payment request, the current holder is
trying to transfer the UXTO to some other (non-statechain) entity, and he knows
the target of the transfer, and participates in the protocol to authorize it.
The current holder must obtain the target pubkey for the transfer out-of-band
with respect to the SE, or the SE can MITM that.

It's a stated security assumption that the sender or receiver do not collude
with the SE. If either do, then your attack is generally possible and all bets
are off. So what you've described is simply the SE colluding with the receiver.
The receiver will *already* receive the UTXO, so the receiver here is assisting
the SE in stealing his (the receiver's) funds, or the SE has done a MITM on the
transfer.  Various improvements including blind signing, a SE-federation, etc
are valuable to consider to mitigate this. But the SE must be prevented, one way
or another, from "buying the UTXO". The SE cannot be allowed to be both operator
of the SE and a customer of it, as this clearly violates the no-receiver
collusion principle.

"Adding a new user key" doesn't change the situation. There's already a user key
involved, and the user has already acquiesced to the transfer. Acquiescing with
two keys doesn't change anything.

As far as proving and tracing the fraud, this is where "single use seals" come
in. Each SE transfer can involve an "opening" of a seal, followed by a "close"
when it is transferred, creating a linear history of ownership. If the SE
obtains the full private key x, one way or another, the spend of that UTXO will
fall outside this seal-based history, and proof of fraud will be evident. It
won't be possible to determine *which* of the old owners collaborated with the
SE, but it gives clear proof that the SE is not to be trusted. A customer might
demand that a seal-based system be in use as an independent entity from the SE,
to audit the honesty of the SE. The seal system does not require any of the keys
required for transfer. See https://mainstay.xyz as a potential implementation.
There are lots of reasons this might required as an AML solution for some
businesses anyway.

Nadav Kohen via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote:
> Hey all,
> 
> So my main concern with the proposal as written is that the Statechain Entity
> (SE) can untraceably scam its users with the following attack:
> 
> 1) Buy the utxo (have it transferred to a key it knows), this first step can be
> skipped if the utxo was created by the SE.
> 2) Transfer the UTXO to someone else, let it be for however long
> 3) When it wishes to steal the UTXO, the SE now knows its own shard s_n and it 
> knows the full private key, x, from when it owned the UTXO (and had both
> shards), and so it can compute x/s_n = the current users shard. It can then
> sign for the current user, and forge a state transition to a key it owns before
> spending the UTXO on chain.
> 
> The main problem here is that the user who had their funds stolen cannot prove
> to anyone that this has happened since the attack compromises their key.
> That said, I think this problem is easily fixed by adding a new user key to the
> protocol with which they must sign in order for the transfer to be considered
> valid on the state chain. This way, if the SE wishes to steal the funds (which
> they still can), at least it is traceable/provable that this SE is not
> trustworthy as there is no evidence of a valid transfer for the funds that have
> been stolen.
> 
> Best,
> Nadav
> 
> On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
>     Thanks for all of the input and comments - I do now think that the
>     decrementing nSequence relative locktime backup system with kick-off
>     transaction is the way to go, including a fee penalty via CPFP to
>     disincentivise DoS, as suggested. 
>     I have started a more detailed document specifying the proposed protocol in
>     more detail: https://github.com/commerceblock/mercury/blob/master/
>     statechains.md which includes improvements to the transfer mechanism (and
>     an explanation of how this can be used to transfer/novate positions in
>     DLCs). Always happy to get more feedback or PRs. 
> 
>     Tom
> 
>     On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <tom@commerceblock.com>
>     wrote:
> 
>         Hi David,
> 
>         Just for clarity, I left nChain over 2 years ago (having worked there
>         since 2016). While there, I (along with other researchers) were given
>         free rein to work on any ideas we wanted to. I had been interested in
>         the scaling of Bitcoin off-chain, and this was one of several things I
>         spent time on (including things like sidechains, pegs and threshold
>         signatures). This patent application came out of an idea I had to
>         transfer ownership of UTXOs off-chain that has some similarities to the
>         statechains proposal, which has shown there is interest and demand for
>         this type of system. 
> 
>         Although I think the existence of this application is something to be
>         mindful of, there are several important things to note:
> 
>         1. Although there are similarities, the current ideas are significantly
>         different to those in the application. 
>         2. The key transfer protocol as described in the application is not
>         secure (for several reasons, including as discussed above, by Albert
>         and Bob etc.) - and a different mechanism is required. 
>         3. Decrementing timelocks (as suggested in the application) are prior
>         art (Decker-Wattenhofer 2015), and in any case any implementation will
>         most likely use an 'invalidation tree' relative locktime backup
>         mechanism for open-ended UTXOs. 
>         4. The patent application has not been granted (it was made in May
>         2017) and the international search report rejected it on the grounds of
>         prior art. 
> 
>         Tom
> 
>         On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave@dtrt.org>
>         wrote:
> 
>             On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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),
>             >
>             > [...]
>             > There are two main modifications we are looking at:
>             > [...]
>             >
>             > 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.
> 
>             Dr. Trevethan,
> 
>             Would you be able to explain how your proposal to use statechains
>             with
>             2P-ECDSA relates to your patent assigned to nChain Holdings for
>             "Secure
>             off-chain blockchain transactions"?[1] 
> 
>                 [1] https://patents.google.com/patent/US20200074464A1
> 
>             Here are some excerpts from the application that caught my
>             attention in
>             the context of statechains in general and your proposal to this
>             list in
>             particular:
> 
>             > an exchange platform that is trusted to implement and operate the
>             > transaction protocol, without requiring an on-chain transaction.
>             The
>             > off-chain transactions enable one computer system to generate
>             multiple
>             > transactions that are recordable to a blockchain in different
>             > circumstances
>             >
>             > [...]
>             >
>             > at least some of the off-chain transactions are valid for
>             recording on
>             > the blockchain even in the event of a catastrophic failure of the
>             > exchange (e.g., exchange going permanently off-line or loosing
>             key
>             > shares).
>             >
>             > [...]
>             >
>             > there may be provided a computer readable storage medium
>             including a
>             > two-party elliptic curve digital signature algorithm (two-party
>             ECDSA)
>             > script comprising computer executable instructions which, when
>             > executed, configure a processor to perform functions of a
>             two-party
>             > elliptic curve digital signature algorithm described herein.
>             >
>             > [...]
>             >
>             > In this instance the malicious actor would then also have to
>             collude
>             > with a previous owner of the funds to recreate the full key.
>             Because
>             > an attack requires either the simultaneous theft of both exchange
>             and
>             > depositor keys or collusion with previous legitimate owners of
>             funds,
>             > the opportunities for a malicious attacker to compromise the
>             exchange
>             > platform are limited.
> 
>             Thank you,
> 
>             -Dave
> 
>     _______________________________________________
>     bitcoin-dev mailing list
>     bitcoin-dev@lists.linuxfoundation.org
>     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> !DSPAM:5e87670a231323960034969!

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

--
Cheers, Bob McElrath

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


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

Re: [bitcoin-dev] Statechain implementations

[ZmnSCPxj]

Good morning Bob,


> Note that this attack requires collaboration with the current UTXO owner.
> Generally if there's some form of address/payment request, the current holder is
> trying to transfer the UXTO to some other (non-statechain) entity, and he knows
> the target of the transfer, and participates in the protocol to authorize it.
> The current holder must obtain the target pubkey for the transfer out-of-band
> with respect to the SE, or the SE can MITM that.
>
> It's a stated security assumption that the sender or receiver do not collude
> with the SE. If either do, then your attack is generally possible and all bets
> are off. So what you've described is simply the SE colluding with the receiver.
> The receiver will already receive the UTXO, so the receiver here is assisting
> the SE in stealing his (the receiver's) funds, or the SE has done a MITM on the
> transfer. Various improvements including blind signing, a SE-federation, etc
> are valuable to consider to mitigate this. But the SE must be prevented, one way
> or another, from "buying the UTXO". The SE cannot be allowed to be both operator
> of the SE and a customer of it, as this clearly violates the no-receiver
> collusion principle.
>
> "Adding a new user key" doesn't change the situation. There's already a user key
> involved, and the user has already acquiesced to the transfer. Acquiescing with
> two keys doesn't change anything.

The point is not that acquiescing with two keys is possible.
Instead, the point is that any past owner of the coin can collude with the statechain authority (who, in the new scheme, must be trusted to delete old keys), or anyone who manages to get backups of the statechain authority keys (such as by digging for backups in a landfill), in order to steal the onchain funds, regardless of who the current owner is, within the statechain.

Thus an amount of trust must still be put in the statechain authority.

So I think the security assumptions should be that:

* The statechain authority really does delete keys and does not make backups.
* No *past* or *current* owner of the coin colludes with the statechain authority.
  * I think saying merely "sender" is not sufficient to capture the actual security assumption here.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Statechain implementations

[Tom Trevethan]

[-- Attachment #1: Type: text/plain, Size: 12204 bytes --]

Hi Bob and Nadav,

There seems to be no way to prevent a malicious SE from stealing an
output from the current owner by either colluding with (or being) a
previous owner. But with a proof-of-publication (i.e. the statechain) it is
possible for the current owner to have a proof that the SE has stolen from
them. It seems to me that the statechain itself provides two functions: 1.
Proof that an output has only a single owner at any time (preventing the SE
from double-spending) and 2. a way for the current owner to prove their
ownership, and require their permission to change ownership. 1. can just be
a publication by the SE, but 2. requires that the output is transferred to
a public key of the owner, and only via a signature of the previous owner
(in this way the SE cannot re-assign ownership unilaterally). Therefore I
think Nadav is right, and this needs to be a key that the SE can never know
(even if they are malicious), but which can be used to prove ownership, and
in turn prove fraud on the part of the SE.

I don't think that this should be too much of an issue: any wallet will
have to use new keys for each output and transfer anyway. The statechain
key (used for the ownership proof) and the output key share can be on
different hardened HD paths (following on from a path derived from the
outpoint of the UTXO, similar to the method in BIP175).

Tom



On Sun, Apr 5, 2020 at 3:17 PM Bob McElrath <bob@mcelrath.org> wrote:

> Note that this attack requires collaboration with the current UTXO owner.
> Generally if there's some form of address/payment request, the current
> holder is
> trying to transfer the UXTO to some other (non-statechain) entity, and he
> knows
> the target of the transfer, and participates in the protocol to authorize
> it.
> The current holder must obtain the target pubkey for the transfer
> out-of-band
> with respect to the SE, or the SE can MITM that.
>
> It's a stated security assumption that the sender or receiver do not
> collude
> with the SE. If either do, then your attack is generally possible and all
> bets
> are off. So what you've described is simply the SE colluding with the
> receiver.
> The receiver will *already* receive the UTXO, so the receiver here is
> assisting
> the SE in stealing his (the receiver's) funds, or the SE has done a MITM
> on the
> transfer.  Various improvements including blind signing, a SE-federation,
> etc
> are valuable to consider to mitigate this. But the SE must be prevented,
> one way
> or another, from "buying the UTXO". The SE cannot be allowed to be both
> operator
> of the SE and a customer of it, as this clearly violates the no-receiver
> collusion principle.
>
> "Adding a new user key" doesn't change the situation. There's already a
> user key
> involved, and the user has already acquiesced to the transfer. Acquiescing
> with
> two keys doesn't change anything.
>
> As far as proving and tracing the fraud, this is where "single use seals"
> come
> in. Each SE transfer can involve an "opening" of a seal, followed by a
> "close"
> when it is transferred, creating a linear history of ownership. If the SE
> obtains the full private key x, one way or another, the spend of that UTXO
> will
> fall outside this seal-based history, and proof of fraud will be evident.
> It
> won't be possible to determine *which* of the old owners collaborated with
> the
> SE, but it gives clear proof that the SE is not to be trusted. A customer
> might
> demand that a seal-based system be in use as an independent entity from
> the SE,
> to audit the honesty of the SE. The seal system does not require any of
> the keys
> required for transfer. See https://mainstay.xyz as a potential
> implementation.
> There are lots of reasons this might required as an AML solution for some
> businesses anyway.
>
> Nadav Kohen via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org] wrote:
> > Hey all,
> >
> > So my main concern with the proposal as written is that the Statechain
> Entity
> > (SE) can untraceably scam its users with the following attack:
> >
> > 1) Buy the utxo (have it transferred to a key it knows), this first step
> can be
> > skipped if the utxo was created by the SE.
> > 2) Transfer the UTXO to someone else, let it be for however long
> > 3) When it wishes to steal the UTXO, the SE now knows its own shard s_n
> and it
> > knows the full private key, x, from when it owned the UTXO (and had both
> > shards), and so it can compute x/s_n = the current users shard. It can
> then
> > sign for the current user, and forge a state transition to a key it owns
> before
> > spending the UTXO on chain.
> >
> > The main problem here is that the user who had their funds stolen cannot
> prove
> > to anyone that this has happened since the attack compromises their key.
> > That said, I think this problem is easily fixed by adding a new user key
> to the
> > protocol with which they must sign in order for the transfer to be
> considered
> > valid on the state chain. This way, if the SE wishes to steal the funds
> (which
> > they still can), at least it is traceable/provable that this SE is not
> > trustworthy as there is no evidence of a valid transfer for the funds
> that have
> > been stolen.
> >
> > Best,
> > Nadav
> >
> > On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> >     Thanks for all of the input and comments - I do now think that the
> >     decrementing nSequence relative locktime backup system with kick-off
> >     transaction is the way to go, including a fee penalty via CPFP to
> >     disincentivise DoS, as suggested.
> >     I have started a more detailed document specifying the proposed
> protocol in
> >     more detail: https://github.com/commerceblock/mercury/blob/master/
> >     statechains.md which includes improvements to the transfer mechanism
> (and
> >     an explanation of how this can be used to transfer/novate positions
> in
> >     DLCs). Always happy to get more feedback or PRs.
> >
> >     Tom
> >
> >     On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <
> tom@commerceblock.com>
> >     wrote:
> >
> >         Hi David,
> >
> >         Just for clarity, I left nChain over 2 years ago (having worked
> there
> >         since 2016). While there, I (along with other researchers) were
> given
> >         free rein to work on any ideas we wanted to. I had been
> interested in
> >         the scaling of Bitcoin off-chain, and this was one of several
> things I
> >         spent time on (including things like sidechains, pegs and
> threshold
> >         signatures). This patent application came out of an idea I had to
> >         transfer ownership of UTXOs off-chain that has some similarities
> to the
> >         statechains proposal, which has shown there is interest and
> demand for
> >         this type of system.
> >
> >         Although I think the existence of this application is something
> to be
> >         mindful of, there are several important things to note:
> >
> >         1. Although there are similarities, the current ideas are
> significantly
> >         different to those in the application.
> >         2. The key transfer protocol as described in the application is
> not
> >         secure (for several reasons, including as discussed above, by
> Albert
> >         and Bob etc.) - and a different mechanism is required.
> >         3. Decrementing timelocks (as suggested in the application) are
> prior
> >         art (Decker-Wattenhofer 2015), and in any case any
> implementation will
> >         most likely use an 'invalidation tree' relative locktime backup
> >         mechanism for open-ended UTXOs.
> >         4. The patent application has not been granted (it was made in
> May
> >         2017) and the international search report rejected it on the
> grounds of
> >         prior art.
> >
> >         Tom
> >
> >         On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <dave@dtrt.org
> >
> >         wrote:
> >
> >             On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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),
> >             >
> >             > [...]
> >             > There are two main modifications we are looking at:
> >             > [...]
> >             >
> >             > 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.
> >
> >             Dr. Trevethan,
> >
> >             Would you be able to explain how your proposal to use
> statechains
> >             with
> >             2P-ECDSA relates to your patent assigned to nChain Holdings
> for
> >             "Secure
> >             off-chain blockchain transactions"?[1]
> >
> >                 [1] https://patents.google.com/patent/US20200074464A1
> >
> >             Here are some excerpts from the application that caught my
> >             attention in
> >             the context of statechains in general and your proposal to
> this
> >             list in
> >             particular:
> >
> >             > an exchange platform that is trusted to implement and
> operate the
> >             > transaction protocol, without requiring an on-chain
> transaction.
> >             The
> >             > off-chain transactions enable one computer system to
> generate
> >             multiple
> >             > transactions that are recordable to a blockchain in
> different
> >             > circumstances
> >             >
> >             > [...]
> >             >
> >             > at least some of the off-chain transactions are valid for
> >             recording on
> >             > the blockchain even in the event of a catastrophic failure
> of the
> >             > exchange (e.g., exchange going permanently off-line or
> loosing
> >             key
> >             > shares).
> >             >
> >             > [...]
> >             >
> >             > there may be provided a computer readable storage medium
> >             including a
> >             > two-party elliptic curve digital signature algorithm
> (two-party
> >             ECDSA)
> >             > script comprising computer executable instructions which,
> when
> >             > executed, configure a processor to perform functions of a
> >             two-party
> >             > elliptic curve digital signature algorithm described
> herein.
> >             >
> >             > [...]
> >             >
> >             > In this instance the malicious actor would then also have
> to
> >             collude
> >             > with a previous owner of the funds to recreate the full
> key.
> >             Because
> >             > an attack requires either the simultaneous theft of both
> exchange
> >             and
> >             > depositor keys or collusion with previous legitimate
> owners of
> >             funds,
> >             > the opportunities for a malicious attacker to compromise
> the
> >             exchange
> >             > platform are limited.
> >
> >             Thank you,
> >
> >             -Dave
> >
> >     _______________________________________________
> >     bitcoin-dev mailing list
> >     bitcoin-dev@lists.linuxfoundation.org
> >     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > !DSPAM:5e87670a231323960034969!
>
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
> > !DSPAM:5e87670a231323960034969!
>
> --
> Cheers, Bob McElrath
>
> "For every complex problem, there is a solution that is simple, neat, and
> wrong."
>     -- H. L. Mencken
>
>

[-- Attachment #2: Type: text/html, Size: 15640 bytes --]

Re: [bitcoin-dev] Statechain implementations

[Tom Trevethan]

[-- Attachment #1: Type: text/plain, Size: 13439 bytes --]

Hi,

An quick update on progress with our statechain implementation which we are
pressing ahead with - we have started work on a version in Rust (
https://github.com/commerceblock/mercury) that is based on the 2P ECDSA
gotham-city wallet from KZen (https://github.com/KZen-networks/gotham-city),
and using their implementation of Lindel's 2P ECDSA protocol, which is very
fast (we can always swap to a different protocol later). Also, we are
planning on using a sparse Merkle tree attested to a Mainstay slot (
mainstay.xyz) for the proof-of-publication/proof-of-ownership - using the
protocol described here:
https://github.com/commerceblock/mercury/blob/master/doc/statechains.md and
https://github.com/thyeem/monotree. Any comments on these choices or on
anything else are highly appreciated.

Tom

On Sun, Apr 5, 2020 at 10:25 PM Tom Trevethan <tom@commerceblock.com> wrote:

> Hi Bob and Nadav,
>
> There seems to be no way to prevent a malicious SE from stealing an
> output from the current owner by either colluding with (or being) a
> previous owner. But with a proof-of-publication (i.e. the statechain) it is
> possible for the current owner to have a proof that the SE has stolen from
> them. It seems to me that the statechain itself provides two functions: 1.
> Proof that an output has only a single owner at any time (preventing the SE
> from double-spending) and 2. a way for the current owner to prove their
> ownership, and require their permission to change ownership. 1. can just be
> a publication by the SE, but 2. requires that the output is transferred to
> a public key of the owner, and only via a signature of the previous owner
> (in this way the SE cannot re-assign ownership unilaterally). Therefore I
> think Nadav is right, and this needs to be a key that the SE can never know
> (even if they are malicious), but which can be used to prove ownership, and
> in turn prove fraud on the part of the SE.
>
> I don't think that this should be too much of an issue: any wallet will
> have to use new keys for each output and transfer anyway. The statechain
> key (used for the ownership proof) and the output key share can be on
> different hardened HD paths (following on from a path derived from the
> outpoint of the UTXO, similar to the method in BIP175).
>
> Tom
>
>
>
> On Sun, Apr 5, 2020 at 3:17 PM Bob McElrath <bob@mcelrath.org> wrote:
>
>> Note that this attack requires collaboration with the current UTXO owner.
>> Generally if there's some form of address/payment request, the current
>> holder is
>> trying to transfer the UXTO to some other (non-statechain) entity, and he
>> knows
>> the target of the transfer, and participates in the protocol to authorize
>> it.
>> The current holder must obtain the target pubkey for the transfer
>> out-of-band
>> with respect to the SE, or the SE can MITM that.
>>
>> It's a stated security assumption that the sender or receiver do not
>> collude
>> with the SE. If either do, then your attack is generally possible and all
>> bets
>> are off. So what you've described is simply the SE colluding with the
>> receiver.
>> The receiver will *already* receive the UTXO, so the receiver here is
>> assisting
>> the SE in stealing his (the receiver's) funds, or the SE has done a MITM
>> on the
>> transfer.  Various improvements including blind signing, a SE-federation,
>> etc
>> are valuable to consider to mitigate this. But the SE must be prevented,
>> one way
>> or another, from "buying the UTXO". The SE cannot be allowed to be both
>> operator
>> of the SE and a customer of it, as this clearly violates the no-receiver
>> collusion principle.
>>
>> "Adding a new user key" doesn't change the situation. There's already a
>> user key
>> involved, and the user has already acquiesced to the transfer.
>> Acquiescing with
>> two keys doesn't change anything.
>>
>> As far as proving and tracing the fraud, this is where "single use seals"
>> come
>> in. Each SE transfer can involve an "opening" of a seal, followed by a
>> "close"
>> when it is transferred, creating a linear history of ownership. If the SE
>> obtains the full private key x, one way or another, the spend of that
>> UTXO will
>> fall outside this seal-based history, and proof of fraud will be evident.
>> It
>> won't be possible to determine *which* of the old owners collaborated
>> with the
>> SE, but it gives clear proof that the SE is not to be trusted. A customer
>> might
>> demand that a seal-based system be in use as an independent entity from
>> the SE,
>> to audit the honesty of the SE. The seal system does not require any of
>> the keys
>> required for transfer. See https://mainstay.xyz as a potential
>> implementation.
>> There are lots of reasons this might required as an AML solution for some
>> businesses anyway.
>>
>> Nadav Kohen via bitcoin-dev [bitcoin-dev@lists.linuxfoundation.org]
>> wrote:
>> > Hey all,
>> >
>> > So my main concern with the proposal as written is that the Statechain
>> Entity
>> > (SE) can untraceably scam its users with the following attack:
>> >
>> > 1) Buy the utxo (have it transferred to a key it knows), this first
>> step can be
>> > skipped if the utxo was created by the SE.
>> > 2) Transfer the UTXO to someone else, let it be for however long
>> > 3) When it wishes to steal the UTXO, the SE now knows its own shard s_n
>> and it
>> > knows the full private key, x, from when it owned the UTXO (and had both
>> > shards), and so it can compute x/s_n = the current users shard. It can
>> then
>> > sign for the current user, and forge a state transition to a key it
>> owns before
>> > spending the UTXO on chain.
>> >
>> > The main problem here is that the user who had their funds stolen
>> cannot prove
>> > to anyone that this has happened since the attack compromises their key.
>> > That said, I think this problem is easily fixed by adding a new user
>> key to the
>> > protocol with which they must sign in order for the transfer to be
>> considered
>> > valid on the state chain. This way, if the SE wishes to steal the funds
>> (which
>> > they still can), at least it is traceable/provable that this SE is not
>> > trustworthy as there is no evidence of a valid transfer for the funds
>> that have
>> > been stolen.
>> >
>> > Best,
>> > Nadav
>> >
>> > On Thu, Apr 2, 2020 at 7:22 PM Tom Trevethan via bitcoin-dev <
>> > bitcoin-dev@lists.linuxfoundation.org> wrote:
>> >
>> >     Thanks for all of the input and comments - I do now think that the
>> >     decrementing nSequence relative locktime backup system with kick-off
>> >     transaction is the way to go, including a fee penalty via CPFP to
>> >     disincentivise DoS, as suggested.
>> >     I have started a more detailed document specifying the proposed
>> protocol in
>> >     more detail: https://github.com/commerceblock/mercury/blob/master/
>> >     statechains.md which includes improvements to the
>> transfer mechanism (and
>> >     an explanation of how this can be used to transfer/novate positions
>> in
>> >     DLCs). Always happy to get more feedback or PRs.
>> >
>> >     Tom
>> >
>> >     On Tue, Mar 31, 2020 at 12:41 PM Tom Trevethan <
>> tom@commerceblock.com>
>> >     wrote:
>> >
>> >         Hi David,
>> >
>> >         Just for clarity, I left nChain over 2 years ago (having worked
>> there
>> >         since 2016). While there, I (along with other researchers) were
>> given
>> >         free rein to work on any ideas we wanted to. I had been
>> interested in
>> >         the scaling of Bitcoin off-chain, and this was one of several
>> things I
>> >         spent time on (including things like sidechains, pegs and
>> threshold
>> >         signatures). This patent application came out of an idea I had
>> to
>> >         transfer ownership of UTXOs off-chain that has some
>> similarities to the
>> >         statechains proposal, which has shown there is interest and
>> demand for
>> >         this type of system.
>> >
>> >         Although I think the existence of this application is something
>> to be
>> >         mindful of, there are several important things to note:
>> >
>> >         1. Although there are similarities, the current ideas are
>> significantly
>> >         different to those in the application.
>> >         2. The key transfer protocol as described in the application is
>> not
>> >         secure (for several reasons, including as discussed above, by
>> Albert
>> >         and Bob etc.) - and a different mechanism is required.
>> >         3. Decrementing timelocks (as suggested in the application) are
>> prior
>> >         art (Decker-Wattenhofer 2015), and in any case any
>> implementation will
>> >         most likely use an 'invalidation tree' relative locktime backup
>> >         mechanism for open-ended UTXOs.
>> >         4. The patent application has not been granted (it was made in
>> May
>> >         2017) and the international search report rejected it on the
>> grounds of
>> >         prior art.
>> >
>> >         Tom
>> >
>> >         On Tue, Mar 31, 2020 at 11:36 AM David A. Harding <
>> dave@dtrt.org>
>> >         wrote:
>> >
>> >             On Wed, Mar 25, 2020 at 01:52:10PM +0000, 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),
>> >             >
>> >             > [...]
>> >             > There are two main modifications we are looking at:
>> >             > [...]
>> >             >
>> >             > 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.
>> >
>> >             Dr. Trevethan,
>> >
>> >             Would you be able to explain how your proposal to use
>> statechains
>> >             with
>> >             2P-ECDSA relates to your patent assigned to nChain Holdings
>> for
>> >             "Secure
>> >             off-chain blockchain transactions"?[1]
>> >
>> >                 [1] https://patents.google.com/patent/US20200074464A1
>> >
>> >             Here are some excerpts from the application that caught my
>> >             attention in
>> >             the context of statechains in general and your proposal to
>> this
>> >             list in
>> >             particular:
>> >
>> >             > an exchange platform that is trusted to implement and
>> operate the
>> >             > transaction protocol, without requiring an on-chain
>> transaction.
>> >             The
>> >             > off-chain transactions enable one computer system to
>> generate
>> >             multiple
>> >             > transactions that are recordable to a blockchain in
>> different
>> >             > circumstances
>> >             >
>> >             > [...]
>> >             >
>> >             > at least some of the off-chain transactions are valid for
>> >             recording on
>> >             > the blockchain even in the event of a catastrophic
>> failure of the
>> >             > exchange (e.g., exchange going permanently off-line or
>> loosing
>> >             key
>> >             > shares).
>> >             >
>> >             > [...]
>> >             >
>> >             > there may be provided a computer readable storage medium
>> >             including a
>> >             > two-party elliptic curve digital signature algorithm
>> (two-party
>> >             ECDSA)
>> >             > script comprising computer executable instructions which,
>> when
>> >             > executed, configure a processor to perform functions of a
>> >             two-party
>> >             > elliptic curve digital signature algorithm described
>> herein.
>> >             >
>> >             > [...]
>> >             >
>> >             > In this instance the malicious actor would then also have
>> to
>> >             collude
>> >             > with a previous owner of the funds to recreate the full
>> key.
>> >             Because
>> >             > an attack requires either the simultaneous theft of both
>> exchange
>> >             and
>> >             > depositor keys or collusion with previous legitimate
>> owners of
>> >             funds,
>> >             > the opportunities for a malicious attacker to compromise
>> the
>> >             exchange
>> >             > platform are limited.
>> >
>> >             Thank you,
>> >
>> >             -Dave
>> >
>> >     _______________________________________________
>> >     bitcoin-dev mailing list
>> >     bitcoin-dev@lists.linuxfoundation.org
>> >     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> >
>> > !DSPAM:5e87670a231323960034969!
>>
>> > _______________________________________________
>> > bitcoin-dev mailing list
>> > bitcoin-dev@lists.linuxfoundation.org
>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> >
>> >
>> > !DSPAM:5e87670a231323960034969!
>>
>> --
>> Cheers, Bob McElrath
>>
>> "For every complex problem, there is a solution that is simple, neat, and
>> wrong."
>>     -- H. L. Mencken
>>
>>

[-- Attachment #2: Type: text/html, Size: 17141 bytes --]