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
|
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 3F28BB09
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 00:39:25 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pg0-f50.google.com (mail-pg0-f50.google.com [74.125.83.50])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F11D6140
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 00:39:23 +0000 (UTC)
Received: by mail-pg0-f50.google.com with SMTP id q68so2197731pgq.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 06 Sep 2017 17:39:23 -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:message-id:date
:to; bh=io21+zMesFMSzsVL6HCQDwcGH5emDko4xQRshk65NIE=;
b=ZkDWn5PoJnUfiUMv0Qlciy88DDyDUPkKOshLu48EwBWVvsKVaxxWlnHUeSnOB0NxLe
QXiAg2pqQso4vmk5MlNTGNd9WDx9zWuXuZWhpzRFsxkGuX3GbCbz/5K2pM3cIQ9opGpT
0+YSZ3841EOYtuYSaEbOZwFezr8pJ1cPQa6D5OMq6Guf27Cb6MJQAmFBflIvcMqu6ndf
uzx5a+LnXT+Q8mYfhS5ii4OvrqsMpTqyZHeX8ML8lbqJcjbz4BS7v3zNWB08ZzZSwGeP
/sd1knvnaUdoYsJBSTs7dJeFgp0gzT4zzZg/oO5nWMRlVMaB+Oetzvcwk6w6lfyJjn8j
SfyA==
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:message-id:date:to;
bh=io21+zMesFMSzsVL6HCQDwcGH5emDko4xQRshk65NIE=;
b=Uer/7izWzbUolL3B2OD6BWRClTHXoRMT0NqNezAcjuqk5unFpsFHEMrj1o7wxb5p1p
dT/mN9YUUei94S3XcVkwk2+6fJHu8lxL1js4RO8BjNA5YK/Z1BQ1/HdfQ8XIkK/txsXk
fGQ4hmmbpJTT9ENaItJ/LCz+LPmrpYV6RK7ZXER0jMvgHP2VQzvdaE5D6gCMloqbGNvY
E7VMOETiudTOX8YxFk/Xx8jGYl9TGR8XO3oIzuRSRmuHdVBM+MMuDQfgw8n1M63m5fui
wiclmCzf89cepYtACKRDJNkB563AaTrZ/5STA2khWx6+UlnFiUa5kYEDoeOQY0hBu/1C
ba+A==
X-Gm-Message-State: AHPjjUiRhLI64kYbp4ExGrwodYBObGWnVWZzgriQTST6Q7uEWwtasZ3O
Yf3YrHNI9NbCXgYKYhZ8zg==
X-Google-Smtp-Source: ADKCNb4gntz4MgCgM7HvoqsaYTPauOf/YgLmxCPU+LbOtlFCAoL2640j05rF7xD/2f7TPZEKCoQxWw==
X-Received: by 10.99.116.21 with SMTP id p21mr944840pgc.93.1504744763267;
Wed, 06 Sep 2017 17:39:23 -0700 (PDT)
Received: from ?IPv6:2607:fb90:9c5b:de1f:c478:4191:c770:5c8b?
([2607:fb90:9c5b:de1f:c478:4191:c770:5c8b])
by smtp.gmail.com with ESMTPSA id
c79sm1204429pfb.46.2017.09.06.17.39.12
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Wed, 06 Sep 2017 17:39:22 -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\))
Message-Id: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
Date: Wed, 6 Sep 2017 17:38:55 -0700
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.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: Thu, 07 Sep 2017 01:00:42 +0000
Subject: [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: Thu, 07 Sep 2017 00:39:25 -0000
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.
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.
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.
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.
I have written three BIPs to describe these features, and their
associated implementation, for which I now invite public review and
discussion:
Fast Merkle Trees
BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
MERKLEBRANCHVERIFY
BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
Tail-call execution semantics
BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
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.
Kind regards,
Mark Friedenbach
|
