Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <CAMZUoKkhrLKOaquP1_M9GwuKT1u7d+GoyW6tcK-t2uv+5VRfyA@mail.gmail.com>
Date: Fri, 23 Nov 2018 04:52:54 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <8CD6C248-9ADF-4324-B4E3-DE41A1ED49A9@xbt.hk>
References: <CAPg+sBhuPG-2GXc+Bp0yv5ywry2fk56LPLT4AY0Kcs+YEoz4FA@mail.gmail.com>
	<CAMZUoK==Bdn73Lc=swgf2F5_mqE84TR1GRBFhrFkn7kab4jBaw@mail.gmail.com>
	<64A86A3A-4633-4BE2-AE09-30BD136BCC2D@xbt.hk>
	<CAMZUoKkhrLKOaquP1_M9GwuKT1u7d+GoyW6tcK-t2uv+5VRfyA@mail.gmail.com>
To: Russell O'Connor <roconnor@blockstream.io>
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT
Precedence: list

Assuming a script size of 128 bytes (including SHA256 padding), 2^20 =
scripts is 134MB. Double it to 268MB for the merkle branch hashes. With =
roughly 100MB/s, this should take 2.5s (or 42min for 30 levels). =
However, memory use is not considered.

>each call to this operation effectively takes O(script-size) time
I=E2=80=99m not sure if this is correct. Actually, =
CTransactionSignatureSerializer() scans every script for =
OP_CODESEPARATOR. Scripts with and without OP_CODESEPARATOR should take =
exactly the same O(script-size) time (see =
https://github.com/bitcoin/bitcoin/pull/14786)
Also, this is no longer a concern under segwit (BIP143), which =
CTransactionSignatureSerializer() is not used. Actually, =
OP_CODESEPARATOR under segwit is way simpler than the proposed OP_MASK. =
If one finds OP_MASK acceptable, there should be no reason to reject =
OP_CODESEPARATOR.

>One suggestion I heard (I think I heard it from Pieter) to achieve the =
above is to add an internal counter that increments on every control =
flow operator,=E2=80=A6=E2=80=A6...
If I have to choose among OP_CODESEPARATOR and =E2=80=9Cflow operator =
counting=E2=80=9D, I=E2=80=99d rather choose OP_CODESEPARATOR. At least =
we don=E2=80=99t need to add more lines to the consensus code, just for =
something that is mostly archivable with MAST.


> On 23 Nov 2018, at 12:23 AM, Russell O'Connor =
<roconnor@blockstream.io> wrote:
>=20
> I see, so your suggestion is that a sequence of OP_IF ... OP_ENDIF can =
be replaced by a Merklized Script tree of that depth in practice.
>=20
> I'm concerned that at script creation time it takes exponential time =
to complete a Merkle root of depth 'n'.  Can anyone provide benchmarks =
or estimates of how long it takes to compute a Merkle root of a full =
tree of various depths on typical consumer hardware?  I would guess =
things stop becoming practical at a depth of 20-30.
>=20
> On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau <jl2012@xbt.hk> wrote:
> With MAST in taproot, OP_IF etc become mostly redundant, with worse =
privacy. To maximise fungibility, we should encourage people to use =
MAST, instead of improve the functionality of OP_IF and further =
complicate the protocol.
>=20
>=20
>> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>>=20
>> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>> So my question is whether anyone can see ways in which this =
introduces
>> redundant flexibility, or misses obvious use cases?
>>=20
>> Hopefully my comment is on-topic for this thread:
>>=20
>> Given that we want to move away from OP_CODESEPARATOR, because each =
call to this operation effectively takes O(script-size) time, we need a =
replacement for the functionality it currently provides.  While perhaps =
the original motivation for OP_CODESEPARTOR is surrounded in mystery, it =
currently can be used (or perhaps abused) for the task of creating =
signature that covers, not only which input is being signed, but which =
specific branch within that input Script code is being signed for.
>>=20
>> For example, one can place an OP_CODESEPARATOR within each branch of =
an IF block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG =
operation.  By doing so, signatures created for one clause cannot be =
used as signatures for another clause.  Since different clauses in =
Bitcoin Script may be enforcing different conditions (such as different =
time-locks, hash-locks, etc), it is useful to be able to sign in such a =
way that your signature is only valid when the conditions for a =
particular branch are satisfied.  In complex Scripts, it may not be =
practical or possible to use different public keys for every different =
clause. (In practice, you will be able to get away with fewer =
OP_CODESEPARATORS than one in every IF block).
>>=20
>> One suggestion I heard (I think I heard it from Pieter) to achieve =
the above is to add an internal counter that increments on every control =
flow operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the =
signature cover the value of this counter.  Equivalently we divide every =
Bitcoin Script program into blocks deliminated by these control flow =
operator and have the signature cover the index of the block that the =
OP_CHECKSIG occurs within.  More specifically, we will want a SigHash =
flag to enables/disable the signature covering this counter.
>>=20
>> There are many different ways one might go about replacing the =
remaining useful behaviour of OP_CODESEPARATOR than the one I gave =
above. I would be happy with any solution.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20