1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
Return-Path: <mark@friedenbach.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 6F1DFA55
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 19 Sep 2017 00:46:35 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pg0-f48.google.com (mail-pg0-f48.google.com [74.125.83.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id E0283E4
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 19 Sep 2017 00:46:33 +0000 (UTC)
Received: by mail-pg0-f48.google.com with SMTP id 7so1087257pgd.13
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 18 Sep 2017 17:46:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=friedenbach-org.20150623.gappssmtp.com; s=20150623;
h=from:content-transfer-encoding:mime-version:subject:date:references
:to:in-reply-to:message-id;
bh=f1YlyBA4IbixvbMIdGD//X+PJwtotDkfdLGlkXat9o4=;
b=jCgcUklTLELhC98NFDjWVi3WLjx79VfmIf/riJYKRYQekkBEIPZVPwm0UG9NNbpn/Q
u+Hr2OJ0VKpsIpWvIGWr/cl/ir4ZWhCqEUWYaFCQuFdQCbVV19Uj12gz0pTegpsIchA5
xtWG8bnQIGFbZaOzhOFmgbiBYX1LUG5lWlWKBtAijGcIuJsE+fDIgpfTlkPVJr6UNUkv
ipvBSwMOCFJMRTxw2UJsdo7dQZ19hJZe1deeg4QIk1kkGJoCqqLHMusukRgJ9VO0oUXn
fqpSZYDEPzxw5uzmDWR2ipjjS+P83XYxgi/hKdHX3jPyOlTUwDzGBdY17X3RM33nDyd3
patw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:from:content-transfer-encoding:mime-version
:subject:date:references:to:in-reply-to:message-id;
bh=f1YlyBA4IbixvbMIdGD//X+PJwtotDkfdLGlkXat9o4=;
b=PsMESLs5pTjk4aacygELLZpv2mRo3S/H8msaFXtRQ5DzwuUVwJgnbhzSWky8ER/5Nz
SQ2jj02D52X+0WPa8gp7QDolu8jclO6BVoBESVhTDI/FPHaZOEcuMNNEEClXT8DJQX9Z
AHdYVDmMYfXPhh96twnwXYRxOMwhvPkIWxLoqW2tH/moIdvJHIldqbjSC0SBRDemFZ/K
g1J6njC1j/t/kPejUdZNJ58iw/I5zjVsxmbxQ6QWOwOUtzSfczXelSxaNIQ9TjeTcXsM
XP7KbaVeFyUG0+4ue757OjXzyFcDqRagzw/vlfkgl82QRshNWQEgWoCkRN5QQCGG2hRq
+hUA==
X-Gm-Message-State: AHPjjUgFB1ohl2CVcLcDFAZXObBo3SGFw3eEv9cnUZvY14EIMupSo/36
vjaW2TRmFkw8L0BtSaeyhw==
X-Google-Smtp-Source: AOwi7QAQqIMkj+EJ7dcvyLkFWcd73sPLq3La0mZAurkI6rMF/Qw9r2B2ubWFZBC7iewgbV8nb0JKBA==
X-Received: by 10.84.235.203 with SMTP id m11mr365741plt.28.1505781992898;
Mon, 18 Sep 2017 17:46:32 -0700 (PDT)
Received: from ?IPv6:2601:647:4600:9c66:21bf:a584:6afe:a92a?
([2601:647:4600:9c66:21bf:a584:6afe:a92a])
by smtp.gmail.com with ESMTPSA id
q13sm750166pfd.100.2017.09.18.17.46.31
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Mon, 18 Sep 2017 17:46:31 -0700 (PDT)
From: Mark Friedenbach <mark@friedenbach.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Mon, 18 Sep 2017 17:46:30 -0700
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
Message-Id: <C623794E-F061-4C7A-B05D-378798ED2BF7@friedenbach.org>
X-Mailer: Apple Mail (2.3273)
X-Spam-Status: No, score=0.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=disabled 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, 19 Sep 2017 00:50:45 +0000
Subject: Re: [bitcoin-dev] Merkle branch verification & tail-call semantics
for generalized MAST
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 19 Sep 2017 00:46:35 -0000
As some of you may know, the MAST proposal I sent to the mailing list
on September 6th was discussed that the in-person CoreDev meetup in
San Francisco. In this email I hope to summarize the outcome of that
discussion. As chatham house rules were in effect, I will refrain from
attributing names to this summary..
* An introductory overview of the BIPs was presented, for the purpose
of familiarizing the audience with what they are attempting to
accomplish and how they do so.
* There was a discussion of a single vs multi-element MBV opcode. It
was put forward that there should perhaps be different opcodes for
the sake of script analysis, since a multi-element MBV will
necessarily consume a variable number of inputs. However it was
countered that if the script encodes the number of elements as an
integer push to the top of the stack immediately before the opcode,
then static analyzability is maintained in such instances. I took
the action item to investigate what an ideal serialization format
would be for a multi-element proof, which is the only thing holding
back a multi-element MBV proposal.
* It was pointed out that the non-clean-stack tail-call semantics is
not compatible with segwit's consensus-enforcement of the clean
stack rule. Some alternatives were suggested, such as changing
deployment mechanisms. After the main discussion session it was
observed that tail-call semantics could still be maintained if the
alt stack is used for transferring arguments to the policy script. I
will be updating the BIP and example implementation accordingly.
* The observation was made that single-layer tail-call semantics can
be thought of as really being P2SH with user-specified hashing. If
the P2SH script template had been constructed slightly differently
such as to not consume the script, it would even have been fully
compatible with tail-call semantics.
* It was mentioned that using script versioning to deploy a MAST
template allows for saving 32 bytes of witness per input, as the
root hash is contained directly in the output being spent. The
downside however is losing the permissionless innovation that comes
with a programmable hashing mechanism.
* The discussion generally drifted into a wider discussion about
script version upgrades and related issues, such as whether script
versions should exist in the witness as well, and the difference in
meaning between the two. This is an important subject, but only of
relevance in far as using a script version upgrade to deploy MAST
would add significant delay from having to sort through these issues
first.
This feedback led to some minor tweaks to the proposal, which I will
be making, as well as the major feature request of a multi-element
MERKLE-BLOCK-VERIFY opcode which requires a little bit more effort to
accomplish. I will report back to this list again when that work is
done.
Sincerely,
Mark Friedenbach
|
