Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 27181AB8 for ; Tue, 4 Jul 2017 15:06:12 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from so254-16.mailgun.net (so254-16.mailgun.net [198.61.254.16]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 67E87CF for ; Tue, 4 Jul 2017 15:06:10 +0000 (UTC) DKIM-Signature: a=rsa-sha256; v=1; c=relaxed/relaxed; d=suredbits.com; q=dns/txt; s=mailo; t=1499180769; h=Content-Type: Cc: To: Subject: Message-ID: Date: From: References: In-Reply-To: MIME-Version: Sender; bh=HK7Rb2G+A5Aiu1tmLcqfWvvk81z7B+f29VMeTiVrCyc=; b=kIoMO6wGF5z/0C7AbPB9pHnJRrAstI3cqtWyCA+iS5PiqIGJ3eSSGTNJptyIxU1Azpg6geIE TpAJQ5Gy1SKcMjUucMzUhr5Z3bTGDmEhQAocyVTbC6JhsCX9aej94XyACWqexueRQlp484vH Ag7wOAXFZqZ44j18i/w/jUO4qgk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=suredbits.com; s=mailo; q=dns; h=Sender: MIME-Version: In-Reply-To: References: From: Date: Message-ID: Subject: To: Cc: Content-Type; b=oBpnwdOOiYVJAl6RJJWoSg7YXdB31BsC0juLHvdF/FJKyAWNrneIyzfbI2qzWJu9oaypMA pDPBbWX0XvyOfWEwSPK68aWNmFf9+6oDtwI9SOauWPDQ1OyRnqej25NS3Yov12EP7v7Hai2G quO6GCz9mQCnRl4Qi3unQSWtIsxi4= Sender: chris@suredbits.com X-Mailgun-Sending-Ip: 198.61.254.16 X-Mailgun-Sid: WyI5MGYzNyIsICJiaXRjb2luLWRldkBsaXN0cy5saW51eGZvdW5kYXRpb24ub3JnIiwgIjJjMTQxIl0= Received: from mail-it0-f50.google.com (mail-it0-f50.google.com [209.85.214.50]) by mxa.mailgun.org with ESMTP id 595baee0.7fc7d067c0b0-smtp-out-n01; Tue, 04 Jul 2017 15:06:08 -0000 (UTC) Received: by mail-it0-f50.google.com with SMTP id v202so101979026itb.0 for ; Tue, 04 Jul 2017 08:06:08 -0700 (PDT) X-Gm-Message-State: AKS2vOxZIuhhffvILlfhV+woXdLjcHbkJ8w6rndjZGKYYGpTlN5xRxMS 1nkk1d71s6LHvFsyV/fKWvF5kn0eNw== X-Received: by 10.36.147.2 with SMTP id y2mr34354350itd.43.1499180767619; Tue, 04 Jul 2017 08:06:07 -0700 (PDT) MIME-Version: 1.0 Received: by 10.107.185.3 with HTTP; Tue, 4 Jul 2017 08:06:06 -0700 (PDT) In-Reply-To: References: <2f2e6b7c-2d47-518a-5a8f-0b5333607aac@gmail.com> <98d35291-5948-cb06-c46a-9d209276cee2@gmail.com> From: Chris Stewart Date: Tue, 4 Jul 2017 10:06:06 -0500 X-Gmail-Original-Message-ID: Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="94eb2c089e1c1bb2fe05537f3963" X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Tue, 04 Jul 2017 15:12:32 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] BIP: OP_BRIBVERIFY - the op code needed for Blind Merge Mined drivechains X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 04 Jul 2017 15:06:12 -0000 --94eb2c089e1c1bb2fe05537f3963 Content-Type: text/plain; charset="UTF-8" Hi ZmnSCPxj, In my scheme, if you read carefully through the pseudocode, a block list > node is valid only if its block is valid. > It seems this is a contradiction against the "blind" part of blind merge mining. How can a bitcoin blockchain node enforce this without tracking the sidechain? Basically, in my scheme, the OP_RETURN data *is* the sidechain block > headers stored on the mainchain. To save space, the sidechain block > headers are reduced to only the previous-block-header commitment and the > current-block-data commitment. All of the other data you would want to put > in the block header (e.g. UTXO set commitment, signalling bits, > time-of-day...) would be part of the current-block-data instead of the > block header. Thus if the current-block-data is invalid the sidechain > block header is invalid and another sidechain block header based on the > previous block header will be searched for. It seems both of our schemes need to include 2 32 bit hashes in the blockchain. Your scheme needs a previous block header hash and the current block header hash, while mine includes the current block header hash twice. We can just commit to all that information via the block header hash and if a sidechain node lies to us will we are doing IBD the hashes won't match with what was included in the bitcoin blockchain. I'll follow your discussion with Paul about sidechain reorgs, but I think his proposal is more desirable -- it follows what actually happens in the bitcoin mining process where we *can* have chain splits when miners simultaneously find a block. Other miners will pick one of the two blocks to mine on top of and eventually one chain will become longer than the other. Therefore that chain will have it's block's orphaned and the miners/nodes following the dead chain will reorg on top of the longest chain. In Paul's scheme, we replace PoW with a bribe. At the conceptual level these are somewhat similar. In PoW a miner is willing to pay a certain amount of money (on electricity) to try to find a bitcoin block. With OP_BRIBEVERIFY a sidechain miner is willing pay a certain amount of money to find a block. In PoW, there is nothing at the software level that says a miner cannot just decide to build on a old block. I could decide to build on the genesis block if I wanted to. Obviously this is a stupid idea as I'll never overtake the bitcoin blockchain with 8 years of PoW behind it -- but it doesn't mean I couldn't try if I wanted too. Your scheme from what I understand prevents this from happening -- and I don't think that is desirable. You might be able to make an argument that a rich attacker can *stall* mining progress on the drivechain, but I think the same argument can be made with a rich miner on the bitcoin blockchain as well. I think miners have threatened to do that if BIP148 caused a chain split. Can you link to the aforementioned pseudocode? I must have missed it on the mailing list. -Chris On Tue, Jul 4, 2017 at 2:21 AM, ZmnSCPxj wrote: > Good morning Paul, Chris, and CryptAxe, > > @Paul > > >> >Your way is actually very similar to mine. Mine _forces_ the bribe to > be > >> >in the earliest txn (the coinbase) and to only occur once. Yours > doesn"t > >> >do anything to refund the briber, if the sidechain (but not the > >> >mainchain) reorganizes (as it can easily do, if an older sidechain > >> >parent is extended while the mainchain proceeds normally). This creates > >> >additional risk. > >> > >> I don"t understand this part. In my scheme, a sidechain cannot > >> reorganize unless the mainchain reorganizes, since the consensus loop > >> only cares about matching the current block; it ignores splits and > >> does not consider them valid. > > > >If I"ve understood you correctly, you have said that each OP Return > >links the (ex)-latest block to a brand new block, and that whichever > >message of this kind comes first (in the mainchain) wins and the rest > >are discarded. > > > >So what if I had a sidechain represented by a jumble of capital letters, > >discarded entries as lowercase letters. > > > >Mainchain Block #200001: [0 --> Q], [0 -->v], [0 -->s], [0 -->b], > >Mainchain Block #200002: [Q --> H], [Q --> z], > >Mainchain Block #200003: [H --> F] > >Mainchain Block #200004: [F --> J], [F -->w] > >Mainchain Block #200005: [H --> P], [J -->x] > >Mainchain Block #200006: [P --> D] > > > >Isn"t the chain {{ Q --> H --> F --> J }} now starting to reorg, with a > >competing chain {{ Q --> H --> P --> D }} ? > > No, because at block #20005, the topmost sidechain block is J, not H, and > the H->P will not be considered as valid -- only the J->x is valid, even > though H->P comes first. > > Please see the pseudocode I sent before in detail and consider how it will > work with your given mainchain blocks example. > > > >> But I suppose you are considering something like the Ethereum > >> mutability feature, which I do not think is something you would want > >> in a sidechain. > > > >What I do want to do, is retain the existing model to some extent. > >Specifically, to the degree where sidechains could salvage some bad > >situations (eg value overflow incident, or March 2013 incident). > > I suppose some kinds of mutability are desirable. In my model, a > sidechain reorg can be forced if the sidechain code is forked to > specifically force some previously-valid block to become invalid, by > developer fiat. In the example you gave, basically, if you want to reorg > from Q->H->F->J to Q->H->P->D then you would fork the sidechain consensus > code to declare that block F is invalid. > > I am hesitant to make mutability something that is easy to force, however. > > >> >I think mine is also much more space-efficient. Even if ours each had > >> >exactly one h* per sidechain per block, it seems that I only require > one > >> >hash to be communicated (plus an indicator byte, and a ~2 byte counter > >> >for the ratchet), whereas you require two. Since its overhead per > >> >sidechain per block, it actually might really add up. > >> > >> Do you not provide a single sidechain"s h* twice in the block? Once > >> in the coinbase and once in the briber"s separate transaction? > > > >That is a good point. Technically, we do include it twice, but the > >second instance (briber-transaction) can be "shuffled" out if the > >counterparties are part of the same Lightning Network (which I expect to > >the be the case, in equilibrium). > > Payments on LN are finalized when the payee provides a preimage for a > hashlock, whether by chain or by LN. Although I suppose you can use a > bribelocked timelocked contract instead of a hashlocked timelocked > contract. I suppose it would be almost the same, except the bribelock is > provided off-chain as a proof of existence in a mainblock coinbase. > > In addition, it may be possible to create a payment channel specifically > between a sidechain operator and a mainchain miner. > > >> In my scheme at least there is no indicator byte -- the "previous > >> block" hash is the indicator of which sidechain it is extending. From > >> your other emails on this list, it seems the ratchet is for > >> withdrawals from sidechain to mainchain? If so, should it not only > >> appear in only some of the sidechains (the ones which are currently > >> doing some withdrawal?)? > > > >No, sorry. There are many tangled issues (Drivechain (total system); > >side-to-main withdrawals (OP CountACKs); individual Drivechains > >themselves; Blind Merged Mining (OP BribeVerify)). The ratchet is not > >about withdrawals, it is exclusively about Blind Merged Mining, and > >making a better OP BribeVerify that offers better guarantees to both > sides. > > Can you describe the ratchet better? I am sorry but when I first heard of > "blind" merge mining, the first thing that came to mind was the use of > OP_RETURN. This is truly blind as the mainchain miner is given what is > effectively a blob of data, and the mainchain miner cannot expect any kind > of format from OP_RETURN. This has the tremendous advantage of not even > requiring a softfork. > > > @Chris > > >What if a attacker pays a large fee to have his *invalid* block hash > included in the bitcoin mainchain? Would this block *have* to be included > in the sidechain's blockchain forever since *it was* included in bitcoin > blockchain? > > In my scheme, if you read carefully through the pseudocode, a block list > node is valid only if its block is valid. > > Basically, in my scheme, the OP_RETURN data *is* the sidechain block > headers stored on the mainchain. To save space, the sidechain block > headers are reduced to only the previous-block-header commitment and the > current-block-data commitment. All of the other data you would want to put > in the block header (e.g. UTXO set commitment, signalling bits, > time-of-day...) would be part of the current-block-data instead of the > block header. Thus if the current-block-data is invalid the sidechain > block header is invalid and another sidechain block header based on the > previous block header will be searched for. > > My understanding is that your attack scenario is not helped by > OP_BRIBEVERIFY alone, as a rich sidechain attacker can provide a bigger > bribe to an invalid h* especially since the mainchain miner will not even > check the h*, just insert it into the coinbase. > > >Maybe I am missing something here, but why we do *explicitly* commit to > the previous block hash? Isn't it implicitly committed to via > SHA256(SHA256())? > > In order to eliminate having to specify a sidechain index, and to remove > sidechain indexes altogether. Instead the sidechain is identified by its > topmost block header hash. > > > @CryptAxe > > >The ratchet system is actually what links the h* data from bribes to > sidechain blocks. h*'s (which are sidechain block hashes) are added to the > ratchet system if they move the sidechain forward or start a split like I > mentioned before. Then a sidechain can request of their local mainchain > node to verify the headers they have downloaded from sidechain peers and > form the side chain. > > I see. However, then, I propose that my OP_RETURN scheme is superior as > the sidechain block headers are indeed visible directly on the mainchain, > and the mainchain node does not even need to be "local", but can be sourced > anywhere, without requiring a ratchet structure (whose purpose I still have > not managed to grok). > > Regards, > ZmnSCPxj > > --94eb2c089e1c1bb2fe05537f3963 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi ZmnSCPxj,


In my scheme, if= you read carefully through the pseudocode, a block list node is valid only= if its block is valid.

It seems this is a contradiction against the "blind" part of blind = merge=20 mining. How can a bitcoin blockchain node enforce this without tracking=20 the sidechain?

Ba= sically, in my scheme, the OP_RETURN data *is* the sidechain block=20 headers stored on the mainchain.=C2=A0 To save space, the sidechain block= =20 headers are reduced to only the previous-block-header commitment and the current-block-data commitment.=C2=A0 All of the other data you would want = to put in the block header (e.g. UTXO set commitment, signalling bits,=20 time-of-day...) would be part of the current-block-data instead of the=20 block header.=C2=A0 Thus if the current-block-data is invalid the sidechain= =20 block header is invalid and another sidechain block header based on the=20 previous block header will be searched for.

It seems both of our schemes need to include 2 32 bit hashes in the blockc= hain. Your scheme needs a previous block header hash and the current block = header hash, while mine includes the current block header hash twice.=C2=A0= We can just commit to all that information via the block header hash and i= f a sidechain node lies to us will we are doing IBD the hashes won't ma= tch with what was included in the bitcoin blockchain.

I'll foll= ow your discussion with Paul about sidechain reorgs, but I think his propos= al is more desirable -- it follows what actually happens in the bitcoin min= ing process where we *can* have chain splits when miners simultaneously fin= d a block. Other miners will pick one of the two blocks to mine on top of a= nd eventually one chain will become longer than the other. Therefore that c= hain will have it's block's orphaned and the miners/nodes following= the dead chain will reorg on top of the longest chain.

I= n Paul's scheme, we replace PoW with a bribe. At the conceptual level t= hese are somewhat similar. In PoW a miner is willing to pay a certain amoun= t of money (on electricity) to try to find a bitcoin block. With OP_BRIBEVE= RIFY a sidechain miner is willing pay a certain amount of money to find a b= lock.

In PoW, there is nothing at the software level tha= t says a miner cannot just decide to build on a old block. I could decide t= o build on the genesis block if I wanted to. Obviously this is a stupid ide= a as I'll never overtake the bitcoin blockchain with 8 years of PoW beh= ind it -- but it doesn't mean I couldn't try if I wanted too. Your = scheme from what I understand prevents this from happening -- and I don'= ;t think that is desirable. You might be able to make an argument that a ri= ch attacker can *stall* mining progress on the drivechain, but I think the = same argument can be made with a rich miner on the bitcoin blockchain as we= ll. I think miners have threatened to do that if BIP148 caused a chain spli= t.

Can you link to the aforementioned pseudocode? I must = have missed it on the mailing list.

-Chris

On = Tue, Jul 4, 2017 at 2:21 AM, ZmnSCPxj <ZmnSCPxj@protonmail.com&g= t; wrote:
Good morning Paul, = Chris, and CryptAxe,

@Paul

>> >Your way is actually very similar t= o mine. Mine _forces_ the bribe to be
>> >in the ear= liest txn (the coinbase) and to only occur once. Yours doesn"t
>> >do anything to refund the briber, if the sidechain (but= not the
>> >mainchain) reorganizes (as it can easil= y do, if an older sidechain
>> >parent is extended w= hile the mainchain proceeds normally). This creates
>> = >additional risk.
>>
>> I don&qu= ot;t understand this part. In my scheme, a sidechain cannot
= >> reorganize unless the mainchain reorganizes, since the consensus l= oop
>> only cares about matching the current block; it = ignores splits and
>> does not consider them valid.
=
>
>If I"ve understood you correctly, yo= u have said that each OP Return
>links the (ex)-latest blo= ck to a brand new block, and that whichever
>message of th= is kind comes first (in the mainchain) wins and the rest
>= are discarded.
>
>So what if I had a side= chain represented by a jumble of capital letters,
>discard= ed entries as lowercase letters.
>
>Mainc= hain Block #200001: [0 --> Q], [0 -->v], [0 -->s], [0 -->b],
>Mainchain Block #200002: [Q --> H], [Q --> z],
<= /div>
>Mainchain Block #200003: [H --> F]
>Main= chain Block #200004: [F --> J], [F -->w]
>Mainchain= Block #200005: [H --> P], [J -->x]
>Mainchain Bloc= k #200006: [P --> D]
>
>Isn"t th= e chain {{ Q --> H --> F --> J }} now starting to reorg, with a
>competing chain {{ Q --> H --> P --> D }} ?
<= /div>

No, because at block #20005, the topmost si= dechain block is J, not H, and the H->P will not be considered as valid = -- only the J->x is valid, even though H->P comes first.

Please see the pseudocode I sent before in detail and cons= ider how it will work with your given mainchain blocks example.


>> But I suppose yo= u are considering something like the Ethereum
>> mutabi= lity feature, which I do not think is something you would want
>> in a sidechain.
>
>What I do w= ant to do, is retain the existing model to some extent.
>S= pecifically, to the degree where sidechains could salvage some bad
>situations (eg value overflow incident, or March 2013 incident).<= br>

I suppose some kinds of mutability are = desirable.=C2=A0 In my model, a sidechain reorg can be forced if the sidech= ain code is forked to specifically force some previously-valid block to bec= ome invalid, by developer fiat.=C2=A0 In the example you gave, basically, i= f you want to reorg from Q->H->F->J to Q->H->P->D then yo= u would fork the sidechain consensus code to declare that block F is invali= d.

I am hesitant to make mutability something = that is easy to force, however.

>> >I think mine is also much more space-efficient. Even if our= s each had
>> >exactly one h* per sidechain per bloc= k, it seems that I only require one
>> >hash to be c= ommunicated (plus an indicator byte, and a ~2 byte counter
&g= t;> >for the ratchet), whereas you require two. Since its overhead pe= r
>> >sidechain per block, it actually might really = add up.
>>
>> Do you not provide a = single sidechain"s h* twice in the block? Once
>>= in the coinbase and once in the briber"s separate transaction?
>
>That is a good point. Technically, we do inc= lude it twice, but the
>second instance (briber-transactio= n) can be "shuffled" out if the
>counterparties = are part of the same Lightning Network (which I expect to
>= ;the be the case, in equilibrium).

Paym= ents on LN are finalized when the payee provides a preimage for a hashlock,= whether by chain or by LN.=C2=A0 Although I suppose you can use a bribeloc= ked timelocked contract instead of a hashlocked timelocked contract.=C2=A0 = I suppose it would be almost the same, except the bribelock is provided off= -chain as a proof of existence in a mainblock coinbase.

<= /div>
In addition, it may be possible to create a payment channel speci= fically between a sidechain operator and a mainchain miner.

>> In my scheme at least there is no i= ndicator byte -- the "previous
>> block" hash= is the indicator of which sidechain it is extending. From
&= gt;> your other emails on this list, it seems the ratchet is for
>> withdrawals from sidechain to mainchain? If so, should it = not only
>> appear in only some of the sidechains (the = ones which are currently
>> doing some withdrawal?)?
>
>No, sorry. There are many tangled issues= (Drivechain (total system);
>side-to-main withdrawals (OP= CountACKs); individual Drivechains
>themselves; Blind Mer= ged Mining (OP BribeVerify)). The ratchet is not
>about wi= thdrawals, it is exclusively about Blind Merged Mining, and
&= gt;making a better OP BribeVerify that offers better guarantees to both sid= es.

Can you describe the ratchet better= ?=C2=A0 I am sorry but when I first heard of "blind" merge mining= , the first thing that came to mind was the use of OP_RETURN.=C2=A0 This is= truly blind as the mainchain miner is given what is effectively a blob of = data, and the mainchain miner cannot expect any kind of format from OP_RETU= RN.=C2=A0 This has the tremendous advantage of not even requiring a softfor= k.


@Chris

>What if a attacker pays a=20 large fee to have his *invalid* block hash included in the bitcoin=20 mainchain? Would this block *have* to be included in the sidechain's=20 blockchain forever since *it was* included in bitcoin blockchain?
=

In my scheme, if you read carefully through the = pseudocode, a block list node is valid only if its block is valid.

Basically, in my scheme, the OP_RETURN data *is* the s= idechain block headers stored on the mainchain.=C2=A0 To save space, the si= dechain block headers are reduced to only the previous-block-header commitm= ent and the current-block-data commitment.=C2=A0 All of the other data you = would want to put in the block header (e.g. UTXO set commitment, signalling= bits, time-of-day...) would be part of the current-block-data instead of t= he block header.=C2=A0 Thus if the current-block-data is invalid the sidech= ain block header is invalid and another sidechain block header based on the= previous block header will be searched for.

M= y understanding is that your attack scenario is not helped by OP_BRIBEVERIF= Y alone, as a rich sidechain attacker can provide a bigger bribe to an inva= lid h* especially since the mainchain miner will not even check the h*, jus= t insert it into the coinbase.

>Maybe I am missing something here, but why we do *explicitly* commit to the=20 previous block hash? Isn't it implicitly committed to via=20 SHA256(SHA256())?

In order to eliminate= having to specify a sidechain index, and to remove sidechain indexes altog= ether.=C2=A0 Instead the sidechain is identified by its topmost block heade= r hash.


@CryptAxe

>The ratchet system is actually what li= nks the h* data from bribes to=20 sidechain blocks. h*'s (which are sidechain block hashes) are added to= =20 the ratchet system if they move the sidechain forward or start a split=20 like I mentioned before. Then a sidechain can request of their local=20 mainchain node to verify the headers they have downloaded from sidechain peers and form the side chain.=C2=A0

I= see.=C2=A0 However, then, I propose that my OP_RETURN scheme is superior a= s the sidechain block headers are indeed visible directly on the mainchain,= and the mainchain node does not even need to be "local", but can= be sourced anywhere, without requiring a ratchet structure (whose purpose = I still have not managed to grok).

Regards,
ZmnSCPxj


--94eb2c089e1c1bb2fe05537f3963--