Re: [bitcoin-dev] Statechain implementations

From: Tom Trevethan <tom@commerceblock•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Statechain implementations
Date: Thu, 7 May 2020 15:54:53 +0100	[thread overview]
Message-ID: <CAJvkSsek2Z3a1tPHrfS4ebViNB0nCikm0mM6mXNbidtcZ86gGQ@mail.gmail.com> (raw)
In-Reply-To: <CAJvkSsf2UxDAkxMC4MuedP2xcgM4_aDQNQfofeW7MBh2oK73rw@mail.gmail.com>

[-- 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 --]