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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
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 ECD378D7
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Oct 2017 04:40:05 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pf0-f177.google.com (mail-pf0-f177.google.com
[209.85.192.177])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 24F20433
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 28 Oct 2017 04:40:04 +0000 (UTC)
Received: by mail-pf0-f177.google.com with SMTP id 17so6296155pfn.12
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 27 Oct 2017 21:40:04 -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=ze36fyENd9O8ZSo518mPwUfIvjL+WnSOYlCiWNzkv1U=;
b=Xht2K8GMnHoejNBrubZ2kqboNbxJRbccgO8Sr1wgZUuuWEi1fYSMkaLZjv8aoo18uD
gEKxs18wUzSQ7iF2epNJpm8V+yQtWd05b2PPS4VTtV7b1hZww3RVpYqKqBzBVGr0MVO0
RYRTC2QjlOt4E2AhbD0h3qpv7p/XBi4yHncVynj0zO8VPJoylGvLdTOFJX38heX0Lfbe
x7+7FWZAnkVGz8bRT0GWcwKR+EKskoA6M+jVRTaTh/EZTBeFjeuTEsp5voMbJISPGDlX
iUSpMATIm48X3jXAqQdwgBaB7qM/9NNwX8rOUZNa/k88noQDPb+jHu4Lez68F9QXfg0n
pDJQ==
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=ze36fyENd9O8ZSo518mPwUfIvjL+WnSOYlCiWNzkv1U=;
b=tb3PoWFVgbZCJogz2rzaaI4QJ+7+wkPD6a+17nPF1NsX9ZdPXPwr4BxpI6Xe+1EqrR
fHpaJkZs7+mjG7FCbHpvgnaVWtR91ubP1msVvLk7jt0VEamvlZP6QW4Uwh8tKH7Hg71B
/hty7Nl7AeC5Qcosq1ZkyDdHbvjigJbkZzH0ObbHC3A7cjLUhGqGfNen8N79cLmHyb8I
QhqAZanIbcJ680XLvHg2CLt58hK9MO9TRDj6xWpXf9jFviSqI5NeG+OxWGxC6IMvs8lR
IrkAdXmOFUteLM4vv9PG74soCLMY03NoyTo0zs/JmY0Qu2fHpNPEXE0MC5DBFjGZNazT
vJDw==
X-Gm-Message-State: AMCzsaXgTNF6Fs6pwfbDFFGY1qiyJLOzdrBZjdC043HBFYfuIEQTMH8f
JWFECj0XyVuVimU09L/m95tQzvMl7Vw=
X-Google-Smtp-Source: ABhQp+SLnpd/2KPjkT89IwO67yCDiWPx7YIoPPcQw/+0SGWHrs+i0cz431M6Br5Et2k0/5DexHuCwQ==
X-Received: by 10.84.238.136 with SMTP id v8mr2001720plk.37.1509165604136;
Fri, 27 Oct 2017 21:40:04 -0700 (PDT)
Received: from ?IPv6:2601:646:8080:4dbb:d494:f85:ff93:d5f1?
([2601:646:8080:4dbb:d494:f85:ff93:d5f1])
by smtp.gmail.com with ESMTPSA id
x27sm18803783pfe.172.2017.10.27.21.40.02
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Fri, 27 Oct 2017 21:40:02 -0700 (PDT)
From: Mark Friedenbach <mark@friedenbach.org>
Content-Type: text/plain;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 11.0 \(3445.1.7\))
Date: Fri, 27 Oct 2017 21:40:01 -0700
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
Luke Dashjr <luke@dashjr.org>
In-Reply-To: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
Message-Id: <3FE16880-868C-40BA-BCC5-954B15478FB2@friedenbach.org>
X-Mailer: Apple Mail (2.3445.1.7)
X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
RCVD_IN_DNSWL_NONE autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
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: Sat, 28 Oct 2017 04:40:06 -0000
I have completed updating the three BIPs with all the feedback that I =
have received so far. In short summary, here is an incomplete list of =
the changes that were made:
* Modified the hashing function fast-SHA256 so that an internal node =
cannot be interpreted simultaneously as a leaf.
* Changed MERKLEBRANCHVERIFY to verify a configurable number of elements =
from the tree, instead of just one.
* Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs are =
assumed to be hashes, and one where they are run through double-SHA256 =
first.
* Made tail-call eval compatible with BIP141=E2=80=99s CLEANSTACK =
consensus rule by allowing parameters to be passed on the alt-stack.
* Restricted tail-call eval to segwit scripts only, so that checking =
sigop and opcode limits of the policy script would not be necessary.
There were a bunch of other small modifications, typo fixes, and =
optimizations that were made as well.
I am now ready to submit these BIPs as a PR against the bitcoin/bips =
repo, and I request that the BIP editor assign numbers.
Thank you,
Mark Friedenbach
> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark@friedenbach.org> =
wrote:
>=20
> I would like to propose two new script features to be added to the
> bitcoin protocol by means of soft-fork activation. These features are
> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
> semantics.
>=20
> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
> redemption to use values selected from a pre-determined set committed
> to in the scriptPubKey, but without requiring revelation of unused
> elements in the set for both enhanced privacy and smaller script
> sizes. Tail-call execution semantics allows a single level of
> recursion into a subscript, providing properties similar to P2SH while
> at the same time more flexible.
>=20
> These two features together are enough to enable a range of
> applications such as tree signatures (minus Schnorr aggregation) as
> described by Pieter Wuille [1], and a generalized MAST useful for
> constructing private smart contracts. It also brings privacy and
> fungibility improvements to users of counter-signing wallet/vault
> services as unique redemption policies need only be revealed if/when
> exceptional circumstances demand it, leaving most transactions looking
> the same as any other MAST-enabled multi-sig script.
>=20
> I believe that the implementation of these features is simple enough,
> and the use cases compelling enough that we could BIP 8/9 rollout of
> these features in relatively short order, perhaps before the end of
> the year.
>=20
> I have written three BIPs to describe these features, and their
> associated implementation, for which I now invite public review and
> discussion:
>=20
> Fast Merkle Trees
> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
>=20
> MERKLEBRANCHVERIFY
> BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
> Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
>=20
> Tail-call execution semantics
> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
>=20
> Note: I have circulated this idea privately among a few people, and I
> will note that there is one piece of feedback which I agree with but
> is not incorporated yet: there should be a multi-element MBV opcode
> that allows verifying multiple items are extracted from a single
> tree. It is not obvious how MBV could be modified to support this
> without sacrificing important properties, or whether should be a
> separate multi-MBV opcode instead.
>=20
> Kind regards,
> Mark Friedenbach
|
