From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id DAAE14679 for ; Thu, 31 Jan 2019 23:44:46 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5035B852 for ; Thu, 31 Jan 2019 23:44:46 +0000 (UTC) Received: by mail-pl1-f170.google.com with SMTP id e11so2202785plt.11 for ; Thu, 31 Jan 2019 15:44:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:content-transfer-encoding:mime-version:subject:message-id:date :to; bh=PveF5o9qRjC8OHwLi/WnVtFUUX1Bj2Yz2m2MFAcm0gE=; b=k5nqQhs97+DxB9krEgKMf+LED17vw9F3XW1qQuobzpExEetbxEHP/PYwqykO8pKY9Z b2pFp/WCy9DxeBlSBmf+++hrjDBH813Bis+IQP7jmTSqpJhFfgP/ErP5laVFt5AsmDh7 lHV0kKY47Nx4z4XeOKTZ4sLmxjgI2QSCeR0HEyqwhR1VvY6++BZBBk+kL63JswcIKFS3 Jh3Jn/eqzOUcjcEstlcWp/lQyW0Mo7PdA6Lx0Fz//ZFq8TrrM8Q+p2j9z6QwURk9WTQu SDi/0mYHZU0hPcJnkseUR0G8ri8dMmjsqnEFiGvTGqYtahzzrQCe5p8ruxx8+WxoYuIh NdiQ== 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=PveF5o9qRjC8OHwLi/WnVtFUUX1Bj2Yz2m2MFAcm0gE=; b=i22742Px8CAuhpCz5Bq39eJ4RqoMAhPq/p/dMi2xpqxaTeRgxVcGa4c+cdhLpumG/D lmJ+My2IAdEbMSup5oHdDTlrIpgGk7kBMC3B2HfIlAi4W9bu5yPW2ernKRR1Aby6YKex axLqw3OWer951pGEo0Tb/zgQUCOu6/HZ/4hrZ7a7bzgR4catY6a2RtvwDAPD/u+XIY/w u3ioKqhz7U2Dw1WDBn5FnNk/VM9aV0J3lSuW7Cfi0FuRI+GbGPWGRwhCWyINVqH2xX/x G+tlg/pyi6rk/6tn2ykSSsmUPcHNz5fj3Ks3xXZpu3MofOxDsjc1el5MhZp9sDgzHJMD y3hA== X-Gm-Message-State: AJcUukfHZDWBCbpl8EPn60SFZBP11jFntVDJB6F0m95ZtHTTXcARGrDi 7zj/yQ+B97M5Y0H7jiZ2coh9HfSd X-Google-Smtp-Source: ALg8bN4e9Vc1GjapcjDIzVQ7B/rPnFlJUt1/15dF/16yFSVjSxNc3g0mI7HUFKgQ5Lcwx7hJzJXQzA== X-Received: by 2002:a17:902:9f93:: with SMTP id g19mr36353816plq.195.1548978285486; Thu, 31 Jan 2019 15:44:45 -0800 (PST) Received: from [10.21.168.80] ([68.65.169.20]) by smtp.gmail.com with ESMTPSA id r76sm8445832pfb.69.2019.01.31.15.44.44 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 31 Jan 2019 15:44:45 -0800 (PST) From: Oleg Andreev Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\)) Message-Id: Date: Thu, 31 Jan 2019 15:44:43 -0800 To: bitcoin-dev X-Mailer: Apple Mail (2.3445.102.3) X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Fri, 01 Feb 2019 14:56:03 +0000 Subject: [bitcoin-dev] Predicate Tree in ZkVM: a variant of Taproot/G'root 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, 31 Jan 2019 23:44:47 -0000 Hi, We've been working for a thing called ZkVM [1] for the last few weeks. = It is a "blockchain virtual machine" in the spirit of Bitcoin, with = multi-asset transfers and zero-knowledge programmable constraints. As a part of its design, there is a "Predicate Tree" =E2=80=94 a variant = of Taproot by Greg Maxwell [2] and G'root by Anthony Towns [3] that I = would like to present here. Hopefully it is useful to the discussion, = and I would appreciate any feedback. ## Background In ZkVM there are linear types Contract and Value (in addition to plain = data types), where Contract also implements "object capabilities" = pattern: Contract "locks" a collection of data and Values under a = "predicate" which is represented by a single group element ("point" in = ECC terms). The predicate can be "satisfied" in a number of allowed ways = which makes the contract unlock its contents, e.g. release the stored = Value which can then be locked in a new unspent output. ## Predicate Tree Predicate is a point that represents one of three things, which allows = composing conditions in an arbitrary tree: 1. Public key 2. Program 3. Disjunction of two other predicates Public key allows representing N-of-N signing conditions (and M-of-N = with proper threshold key setup, although small combinations like 2-of-3 = can be non-interactively represented as a tree of 3 combinations of = 2-of-2 conditions): P =3D x*B (x is a secret, B is a primary generator point) Program commitment is a P2SH-like commitment: P =3D hash2scalar(program)*B2 (B2 is orthogonal to B, so one cannot = sign for P, but must reveal the program) Disjunction (asymmetric to allow happy-path signing with the left = predicate): P =3D L + hash2scalar(L,R)*B ## VM instructions To use the predicate trees, ZkVM provides 4 instructions: 1. `signtx` to verify the signature over the transaction ID treating the = predicate as a pubkey. 2. `call` to reveal the committed program and execute it. 3. `left`/`right` to replace the contract's predicate with one of the = sub-predicates in a disjunction. 4. `delegate` to check a signature over a program and execute that = program (pay-to-signed-program pattern). More details are in the ZkVM spec: = https://github.com/interstellar/zkvm/blob/main/spec/ZkVM.md#signtx `call` and `delegate` differ in that `call` reveals and runs a = pre-arranged program (like in P2SH), while `delegate` allows choosing = the program later which can be signed with a pre-arranged public key. = `delegate` also enables use cases for SIGHASH: if a specific output or = outputs or constraints must be signed, they can be represented by such = program snippet. Likewise, a "revocation token" for the payment channel = (LN) can be implemented with `delegate` instruction. ## Performance For performance, the following rules are built into ZkVM: 1. All point operations are deferred. Signature checks, disjunction = proofs, program commitment proofs - are not executed right away, but = deferred and verified in a batch after the VM execution is complete. = This enables significant savings, especially since half or third of the = terms reuse static points B and B2. 2. `signtx` does not accept individual signatures, but uses a single = aggregated signature for the whole transaction. All the pubkeys are = remembered in a separate set and combined via MuSig-style [4] protocol = to check the single 64-byte signature over txid in the end of the VM = execution. In other words, signature aggregation is not optional for = `signtx` (signatures over txid). Note: the `delegate` instruction = permits arbitrary programs, so it uses one signature per program. ## What is different from Taproot/G'root (1) No pure hash-based MAST: each time one peels off a layer of a tree, = there's an ECC check which is more expensive than pure-hash merkle path = check, but makes the design simpler and all ECC ops are batched = alongside bulletproofs R1CS verification statement, making the = performance difference unimportant. (2) There is no designated blinding factor or a pubkey with the program = commitment like in G'root. This is not something i'm particularly sure = about, but will lay out the current rationale: 1. The happy-path one-time-key normally acts as a sufficient blinding = factor for the program. 2. If the program needs a blinding factor, it can be embedded as a = ` drop`. 3. The combo of "sign + programmatic constraints" is done by having = instructions inside the program that wrap the value(s) in a transient = contract with the required pubkey and leaving it on the stack. ## References [1] https://github.com/interstellar/zkvm [2] = https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/01561= 4.html [3] = https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.h= tml [4] = https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signature= s/