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’m 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,……... If I have to choose among OP_CODESEPARATOR and “flow operator counting”, I’d rather choose OP_CODESEPARATOR. At least we don’t 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 <[email protected]> wrote: > > 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. > > 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. > > On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau <[email protected]> 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. > > >> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev >> <[email protected]> wrote: >> >> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev >> <[email protected]> wrote: >> So my question is whether anyone can see ways in which this introduces >> redundant flexibility, or misses obvious use cases? >> >> Hopefully my comment is on-topic for this thread: >> >> 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. >> >> 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). >> >> 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. >> >> 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 >> [email protected] >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > _______________________________________________ bitcoin-dev mailing list [email protected] https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
