public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Mark Friedenbach <mark@friedenbach.org>
To: Johnson Lau <jl2012@xbt.hk>
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Version 1 witness programs (first draft)
Date: Sun, 1 Oct 2017 17:35:38 -0700	[thread overview]
Message-ID: <50CA8523-3D1A-409E-9B7D-51EA5FC4B898@friedenbach.org> (raw)
In-Reply-To: <30B31B43-B603-4793-BDFB-B7E25FD96D1B@xbt.hk>


> On Oct 1, 2017, at 2:32 PM, Johnson Lau <jl2012@xbt.hk> wrote:
> 
> So there are 3 proposals with similar goal but different designs. I try to summarise some questions below:
> 
> 1. How do we allow further upgrade within v1 witness? Here are some options:
> a. Minor version in witness. (Johnson / Luke) I prefer this way, but we may end up with many minor versions.

I'm not sure I agree with the "minor version" nomenclature, or that we would necessarily end up with any consensus-visible fields beyond 2.  There are two separate soft-fork version fields that were, I think it is fair to say now, inappropriately merged in the "script version” feature of segregated witness as described in BIP141.

First there is the witness type, which combined with the length of the commitment that follows specifies how data from the witness stack is used to calculate/verify the witness commitment in the scriptPubKey of the output being spent.  For v0 with a 20-byte hash, it says that those 20 bytes are the HASH160 of the top element of the stack.  For v0 with a 32-byte hash, it says that those 32 bytes are the HASH256 of the top element of the stack.

Second there is the script version, which is not present as a separate field for witness type v0.  Implicitly though, the script version for v0,20-byte is that the witness consists of two elements, and these are interpreted as a pubkey and a signature.  For v0,32-byte the script version is that the witness consists of 1 or more elements; with max 520 byte size constraints for all but the top element, which has a higher limit of 10,000 bytes; and the top-most element is interpreted as a script and executed with the modified CHECKSIG behavior defined by BIP141 and the CLEANSTACK rule enforced.

These are separate roles, one not being derivative of the other.  In an ideal world the witness type (of which there are only 16 remaining without obsoleting BIP141) is used only to specify a new function for transforming the witness stack into a commitment for verification purposes.  Merklized script would be one example: v2,32-byte could be defined to require a witness stack of at least two elements, the top most of which is a Merkle inclusion proof of the second item in a tree whose root is given in the 32-byte payload of the output.  Maybe v3 would prove inclusion by means of some sort of RSA accumulator or something.

Such a specification says nothing about the features of the subscript drawn from the Merkle tree, or even whether it is bitcoin script at all vs something else (Simplicity, DEX, RISC-V, Joy, whatever).  All that is necessary is that a convention be adopted about where to find the script version from whatever data is left on the stack after doing the witness type check (hashing the script, calculating a Merkle root, checking inclusion in an RSA accumulator, whatever).  A simple rule is that it is serialized and prefixed to the beginning of the string that was checked against the commitment in the output.

So v0,32-byte says that the top item is hashed and that hash must match the 32-byte value in the output.  This new v1,32-byte witness type being talked about in this thread would have exactly the same hashing rules, but will execute the resulting string based on its prefix, the script version, which is first removed before execution.

Sure first script version used could be a cleaned up script with a bunch of the weirdness removed (CHECKMULTISIG, I'm looking at you!); CLTV, CSV, and MBV drop arguments; disabled opcodes and unassigned NOPs become "return true"; etc.  Maybe v2 adds new opcodes.  But we can imagine script version that do something totally different, like introduce a new script based on a strongly-typed Merklized lambda calculus, or a RISC-V executable format, or whatever.

This has pragmatic implications with the separation of witness type and script version: we could then define a "MAST" output that proves the script used is drawn from a set represented by the Merkle tree.  However different scripts in that tree can use different versions.  It would be useful if the most common script is the key aggregated everyone-signs outcome, which looks like a regular bitcoin payment, and then contingency cases can be handled by means of a complicated script written in some newly added general computation language or a whole emulated RISC-V virtual machine.

> b. OP_RETURNTRUE (Luke). I proposed this in an earlier version of BIP114 but now I think it doesn’t interact well with signature aggregation, and I worry that it would have some other unexpected effects.
> c. Generalised NOP method: user has to provide the returned value, so even VERIFY-type code could do anything

I see no reason to do either. Gate new behavior based on script execution flags, which are set based on the script version.  Script versions not understood are treated as "return true" to begin with.  The interpreter isn't even going to try to decode the script according to the old rules, let alone try to execute it, so there's no reason for the old soft-fork compatability tricks.

The new soft-fork trick is that you increment the script version number.  That is all.

> 2. Do we want to allow signature-time commitment of extra scripts?
> I think all proposals allow this, just with different way
> a. Tail-call semantics with CHECKSIGFROMSTACK (Mark). I think this is too rigid as it works only with specially designed scriptPubKey

This is not signature-time commitment of extra script. Not without CHECKSIGFROMSTACK or something like it.

> b. scriptWitCode: extra scripts are put in some fixed location in witness (Johnson). This makes sure static analysability.
> c. Extra-data as script in OP_CHECKSIG (Luke)

Propose these as their own script updates.  Script versioning makes such new features cheap.  There's no reason to create some sort of complex omnibus overhaul that does everything.

> 3. Do we want to allow static analysis of sigop?
> BIP114 and the related proposals are specifically designed to allow static analysis of sigop. I think this was one of the main reason of OP_EVAL not being accepted. This was also the main reason of Ethereum failing to do a DAO hacker softfork, leading to the ETH/ETC split. I’m not sure if we really want to give up this property. Once we do it, we have to support it forever.

Again, this is off-topic for this thread.  I don't think a v1 witness type upgrade should do any of these things.  The v1 witness type should add a proper script version in the witness, and remove or simplify limits or unnecessary verification rules that are no longer necessary and/or hindering progress.  That’s it.

For example, I don't think a v1 witness version should be coupled with my tail-call semantics or the introduction of MERKLEBRANCHVERIFY (but if MBV was released already we could have it drop its arguments, which would be nice).  However it should drop the CLEANSTACK rule in favor of something else (like signatures committing to the witness depth and/or weight) since the tail-call BIP demonstrates it to be an impediment to extensibility and alternatives are not.  And it should drop the 520 byte push limitation, as the MBV BIP demonstrates use cases that have serialized proofs larger than that, like a k-of-N threshold with N=16.

  reply	other threads:[~2017-10-02  0:35 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-10-01  1:13 [bitcoin-dev] Version 1 witness programs (first draft) Luke Dashjr
2017-10-01  2:23 ` Mark Friedenbach
2017-10-01  2:47   ` Luke Dashjr
2017-10-01  5:04     ` Mark Friedenbach
2017-10-01 11:22       ` Felix Weis
2017-10-01 17:36         ` Luke Dashjr
2017-10-01 19:05       ` Russell O'Connor
2017-10-01 19:27         ` Mark Friedenbach
2017-10-01 19:41           ` Russell O'Connor
2017-10-01 20:39             ` Mark Friedenbach
2017-10-01 20:43               ` Luke Dashjr
2017-10-02 20:38               ` Russell O'Connor
2017-10-01 18:34 ` Mark Friedenbach
2017-10-01 21:32 ` Johnson Lau
2017-10-02  0:35   ` Mark Friedenbach [this message]
2017-10-02  2:56     ` Luke Dashjr
2017-10-02  9:09       ` Sjors Provoost
2017-10-02  0:45   ` Luke Dashjr
2017-10-05 20:33 ` Mark Friedenbach
2017-10-05 21:28   ` Russell O'Connor

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=50CA8523-3D1A-409E-9B7D-51EA5FC4B898@friedenbach.org \
    --to=mark@friedenbach.org \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=jl2012@xbt.hk \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox