Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 3F28BB09 for ; 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 ; Thu, 7 Sep 2017 00:39:23 +0000 (UTC) Received: by mail-pg0-f50.google.com with SMTP id q68so2197731pgq.1 for ; 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 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 06 Sep 2017 17:39:22 -0700 (PDT) From: Mark Friedenbach 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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