diff options
| author | Jeremy Rubin <jeremy.l.rubin@gmail.com> | 2022-09-14 11:31:55 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2022-09-14 18:32:13 +0000 |
| commit | 415e251ca66e26163a11827e629698ef9ed11300 (patch) | |
| tree | 4454f568d6d173e610fc54b024e36dbb04006438 | |
| parent | e908faac3aca413a3e0b9fe797774eb4d067e140 (diff) | |
| download | pi-bitcoindev-415e251ca66e26163a11827e629698ef9ed11300.tar.gz pi-bitcoindev-415e251ca66e26163a11827e629698ef9ed11300.zip | |
[bitcoin-dev] Spookchains: Drivechain Analog with One-Time Trusted Setup & APO
| -rw-r--r-- | 7b/124c23a50e1023b70522cdc3316f5caae46fda | 684 |
1 files changed, 684 insertions, 0 deletions
diff --git a/7b/124c23a50e1023b70522cdc3316f5caae46fda b/7b/124c23a50e1023b70522cdc3316f5caae46fda new file mode 100644 index 000000000..1d06b6966 --- /dev/null +++ b/7b/124c23a50e1023b70522cdc3316f5caae46fda @@ -0,0 +1,684 @@ +Return-Path: <jeremy.l.rubin@gmail.com> +Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 69FB5C002D + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 14 Sep 2022 18:32:13 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp3.osuosl.org (Postfix) with ESMTP id 30D9660D6C + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 14 Sep 2022 18:32:13 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 30D9660D6C +Authentication-Results: smtp3.osuosl.org; + dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com + header.a=rsa-sha256 header.s=20210112 header.b=DAA25KjN +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -2.098 +X-Spam-Level: +X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, + DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, + HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, + SPF_PASS=-0.001] autolearn=ham autolearn_force=no +Received: from smtp3.osuosl.org ([127.0.0.1]) + by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id Op1U2kw7Hms1 + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 14 Sep 2022 18:32:10 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.8.0 +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 1257C60C0A +Received: from mail-yw1-x1134.google.com (mail-yw1-x1134.google.com + [IPv6:2607:f8b0:4864:20::1134]) + by smtp3.osuosl.org (Postfix) with ESMTPS id 1257C60C0A + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 14 Sep 2022 18:32:10 +0000 (UTC) +Received: by mail-yw1-x1134.google.com with SMTP id + 00721157ae682-3450990b0aeso191013747b3.12 + for <bitcoin-dev@lists.linuxfoundation.org>; + Wed, 14 Sep 2022 11:32:09 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; + h=to:subject:message-id:date:from:mime-version:from:to:cc:subject + :date; bh=8Q+B74+orACw28jXFt2CY6lo4QcklS5PBpmyUjGcYhk=; + b=DAA25KjNC/FVZVk537XqB+MQ9NvM7VbrXCQmjYjD2tfa9wwRuZMasgIjGb3ndVUuad + GfWEyRoHkQNnmbPSPf/Nl1k5+ADRPEyFMxvKHgozMj2URdC6u+FfogYRyHQieGhpKGvt + nZa2G1Wd0PPRqMaVauNwjfjJ/tUiO/kCj+5V6xxWR2PFQPKb00tlGMtNyXylwPRW9gqQ + U6eFWRNM2LjHcOmBIdF5m8ffxU+TiJEpXTQwTMXApZw7Wj0o8P8faa90L5gTUf9j2bHf + g7FVUmlL8edbu1YLZqX5PzbsROEqOcersS+dStS8FWFL2H6nk2UCckIop8GWNxOEZQmP + esgA== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20210112; + h=to:subject:message-id:date:from:mime-version:x-gm-message-state + :from:to:cc:subject:date; + bh=8Q+B74+orACw28jXFt2CY6lo4QcklS5PBpmyUjGcYhk=; + b=VvslCmDG7j20WrBkTUk4yuQM246aH7shRIaDjwH1ogPIuEFtJKVlX3w8S0oUjQMkzN + QvuI5HFifvcBghZ10lMvtpZoags8bSOeSkdDPRJoqb4xkeeX61y4GNBQQEcH/V8MV793 + J+5lXTITpNyaGwhObegBW89jEZI17mu5IfcgD+IwsXLP5+1ozFvMUbLSg7qP1d2pb7hr + snA+8rJnKaWR1AktEMDU6oR3mFAJx09zLe2R7S/TmDIu5x3cSxO5+Nw/ddo2xqWN46Ej + fS8yP6Mutv6Aia9iTyv/DW8wNpdSMPYfkrdRXLvcRf2m3pqNkwsvMKYU8Gq9lMTGOh42 + swNw== +X-Gm-Message-State: ACgBeo227T2Ywo8QAeo0Gd7tPoo6vBDvWzqDiYp3VV920xyCn1bfcepk + OHN7k8m3/pIV9tYfiz4rnNqNeoYGcn+RTXigJd7PjtWVSyQ= +X-Google-Smtp-Source: AA6agR7ZzArvRxW7IA62r8msawAc3dN4rkZJFyVH1X9SnXuYMS4uCAeQ1s8ImYQGbS5DTKAm+nfQxHNA/lZfRmQK5+k= +X-Received: by 2002:a81:10c3:0:b0:349:8b81:9fb0 with SMTP id + 186-20020a8110c3000000b003498b819fb0mr7735833ywq.269.1663180327504; Wed, 14 + Sep 2022 11:32:07 -0700 (PDT) +MIME-Version: 1.0 +From: Jeremy Rubin <jeremy.l.rubin@gmail.com> +Date: Wed, 14 Sep 2022 11:31:55 -0700 +Message-ID: <CAD5xwhgKGMx79+RLpb-hjd3Gc=EKxTVzkpME-=KuM_C5+d7mRQ@mail.gmail.com> +To: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="0000000000009e509e05e8a75803" +Subject: [bitcoin-dev] Spookchains: Drivechain Analog with One-Time Trusted + Setup & APO +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.15 +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: Wed, 14 Sep 2022 18:32:13 -0000 + +--0000000000009e509e05e8a75803 +Content-Type: text/plain; charset="UTF-8" + +*also available here on my blog with nicer +formatting: https://rubin.io/bitcoin/2022/09/14/drivechain-apo/ +<https://rubin.io/bitcoin/2022/09/14/drivechain-apo/>* + +This post draws heavily from Zmnscpxj's fantastic post showing how to +make drivechains with recursive covenants. In this post, I will show +similar tricks that can accomplish something similar using ANYPREVOUT +with a one time trusted setup ceremony. + +This post presents general techniques that could be applied to many +different types of covenant. + +# Peano Counters + +The first component we need to build is a Peano counter graph. Instead +of using sha-256, like in Zmnscpxj's scheme, we will use a key and +build a simple 1 to 5 counter that has inc / dec. + +Assume a key K1...K5, and a point NUMS which is e.g. +HashToCurve("Spookchains"). + +Generate scripts as follows: + +``` +<1 || K1> CHECKSIG +... +<1 || K5> CHECKSIG +``` + +Now generate 2 signatures under Ki with flags `SIGHASH_SINGLE | +SIGHASH_ANYONECANPAY | SIGHASH_ANYPREVOUT`. + + +## Rule Increment +For each Ki, when `i < 5`, create a signature that covers a +transaction described as: + +``` +Amount: 1 satoshi +Key: Tr(NUMS, {<1 || K{i+1}> CHECKSIG}) +``` + +## Rule Decrement +For each Ki, when `i > 1` The second signature should cover: +``` +Amount: 1 satoshi +Key: Tr(NUMS, {<1 || K{i-1}> CHECKSIG}) +``` + + + +_Are these really Peano?_ Sort of. While a traditional Peano numeral +is defined as a structural type, e.g. `Succ(Succ(Zero))`, here we +define them via a Inc / Dec transaction operator, and we have to +explicitly bound these Peano numbers since we need a unique key per +element. They're at least spiritually similar. + +## Instantiation +Publish a booklet of all the signatures for the Increment and +Decrement rules. + +Honest parties should destroy the secret key sets `k`. + + +To create a counter, simply spend to output C: + +``` +Amount: 1 satoshi +Key: Tr(NUMS, {<1 || K1> CHECKSIG}) +``` + + +The signature from K1 can be bound to C to 'transition' it to (+1): + +``` +Amount: 1 satoshi +Key: Tr(NUMS, {<1 || K2> CHECKSIG}) +``` + +Which can then transition to (+1): + +``` +Amount: 1 satoshi +Key: Tr(NUMS, {<1 || K3> CHECKSIG}) +``` + +Which can then transition (-1) to: + +``` +Amount: 1 satoshi +Key: Tr(NUMS, {<1 || K2> CHECKSIG}) +``` + +This can repeat indefinitely. + + +We can generalize this technique from `1...5` to `1...N`. + + + +# Handling Arbitrary Deposits / Withdrawals + + +One issue with the design presented previously is that it does not +handle arbitrary deposits well. + +One simple way to handle this is to instantiate the protocol for every +amount you'd like to support. + +This is not particularly efficient and requires a lot of storage +space. + +Alternatively, divide (using base 2 or another base) the deposit +amount into a counter utxo per bit. + +For each bit, instead of creating outputs with 1 satoshi, create +outputs with 2^i satoshis. + +Instead of using keys `K1...KN`, create keys `K^i_j`, where i +represents the number of sats, and j represents the counter. Multiple +keys are required per amount otherwise the signatures would be valid +for burning funds. + +## Splitting and Joining + +For each `K^i_j`, it may also be desirable to allow splitting or +joining. + +Splitting can be accomplished by pre-signing, for every `K^i_j`, where +`i!=0`, with `SIGHASH_ALL | SIGHASH_ANYPREVOUT`: + +``` +Input: 2^i sats with key K^i_j +Outputs: + - 2^i-1 sats to key K^{i-1}_j + - 2^i-1 sats to key K^{i-1}_j +``` + +Joining can be accomplished by pre-signing, for every `K^i_j`, where +`i!=MAX`, with `SIGHASH_ALL | SIGHASH_ANYPREVOUT`: + +``` +Inputs: + - 2^i sats with key K^i_j + - 2^i sats with key K^i_j +Outputs: + - 2^i+1 sats to key K^{i+1}_j +``` + +N.B.: Joining allows for third parties to deposit money in externally, +that is not a part of the covenant. + + +The splitting and joining behavior means that spookchain operators +would be empowered to consolidate UTXOs to a smaller number, while +allowing arbitrary deposits. + + +# One Vote Per Block + +To enforce that only one vote per block mined is allowed, ensure that +all signatures set the input sequence to 1 block. No CSV is required +because nSequence is in the signatures already. + +# Terminal States / Thresholds + +When a counter reaches the Nth state, it represents a certain amount +of accumulated work over a period where progress was agreed on for +some outcome. + +There should be some viable state transition at this point. + +One solution would be to have the money at this point sent to an +`OP_TRUE` output, which the miner incrementing that state is +responsible for following the rules of the spookchain. Or, it could be +specified to be some administrator key / federation for convenience, +with a N block timeout that degrades it to fewer signers (eventually +0) if the federation is dead to allow recovery. + +This would look like, from any `K^i_j`, a signature for a transaction +putting it into an `OP_TRUE` and immediately spending it. Other +spookchain miners would be expected to orphan that miner otherwise. + + +# Open States / Proposals + +From a state `K^i_1`, the transaction transitioning to `K^i_2` can be +treated as 'special' and the `OP_RETURN` output type can be used to +commit to, e.g., the outputs that must be created in when the Terminal +State is reached. This clarifies the issue of "what is being voted +on". + +This method does not *lock in* at a consensus layer what Terminal +State is being voted on. + +In certain circumstances, without violating the one-time-setup +constraint, if a fixed list of withdrawer's addresses is known in +advance, the Open States could cover withdrawals to specific +participants, which then must collect a certain number of votes from +miners. However, it seems impossible, without new primitives, for an +arbitrary transaction proposal to be voted on. + +# Setup Variants + +## xpubs + +Instead of using randomly generated keys for each state, define each +to be an xpub and derive a path where it is k/i/j for each +state/satoshi amount. This saves some data, and also requires less +entropy. + +### Trustless Data Commit: + +commit to the hash of the entire program spec as a tweak to the xpub, +so that someone can quickly verify if they have all the signatures you +are expected to generate if honest. + +One way to do this is to convert a hash to a list of HD Child Numbers +(9 of them) deterministically, and tweak the xpub by that. This is a +convenient, yet inefficient, way to tweak an xpub because the child +has a normal derivation path for signing devices. + +## Single Party + +A single party pre-signs all the transactions for the spookchain, and +then deletes their xpriv. + +You trust them to have deleted the key, and signed properly, but you +do not trust whoever served you the spookchain blob to have given you +all the state transitions because of the trustless data commitment. + +## MuSig Multi-Party + +Define a MuSig among all participants in the setup ceremony, N-of-N. + +Now you simply trust that any one person in the one-time-setup was +honest! Very good. + +## Unaggregated Multi-Party + + +Allow for unaggregated multi-sig keys in the spec. This grows with +O(signers), however, it means that a-la-carte you can aggregate setups +from random participants who never interacted / performed setup +ceremonies independently if they signed the same specs. + +Can also combine multiple MuSig Multi-Parties in this way. + +This is nice because MuSig inherently implies the parties colluded at +one point to do a MuSig setup, whereas unaggregated multi-sig could be +performed with no connectivity between parties. + +## Soft Forking Away Trust + +Suppose a spookchain becomes popular. You could configure your client +to reject invalid state transitions, or restrict the spookchain keys +to only sign with the known signatures. This soft fork would smoothly +upgrade the trust assumption. + +## Symmetry of State Transition Rules & DAG Covenants + +We could have our increment state transitions be done via a trustless +covenant, and our backwards state transitions be done via the setup. + +This would look something like the following for state i: + +``` +Tr(NUMS, { + `<sig for state K_{i+1}> <1 || PK_nonsecret> CHECKSIG`, + `<1 || Ki> CHECKSIG` +}) +``` + +The advantage of such an optimization is theoretically nice because it +means that *only* the non-destructuring recursive part of the +computation is subject to the one-time-setup trust assumption, which +might be of use in various other protocols, where recursivity might +only be unlocked e.g. after a timeout (but for spookchains it is used +at each step). + +A compiler writer might perform this task by starting with an +arbitrary abstract graph, and then removing edges selectively (a +number of heuristics may make sense, e.g., to minimize reliance on +one-time-setup or minimize costs) until the graph is a Directed +Acyclic Graph, consisting of one or more components, compiling those +with committed covenants, and then adding the removed edges back using +the one-time-setup key materials. + + +# Commentary on Trust and Covenantiness + +Is this a covenant? I would say "yes". When I defined covenants in my +_Calculus of Covenants_ post, it was with a particular set of +assumptions per covenant. + +Under that model, you could, e.g., call a 7-10 multi-sig with specific +committed instructions as 4-10 honest (requires 4 signatories to be +honest to do invalid state transition) and 4-10 killable (requires 4 +signatories to die to have no way of recovering). + +For emulations that are pre-signed, like the varieties used to emulate +CTV, it is a different model because if your program is correct and +you've pre-gotten the signatures for N-N it is 1-N honest (only 1 +party must be honest to prevent an invalid state transition) and +unkillable (all parties can safely delete keys). + +I model these types of assumptions around liveness and honesty as +different 'complexity classes' than one another. + +What I would point out is that with the counter model presented above, +this is entirely a pre-signed 1-N honest and unkillable covenant that +requires no liveness from signers. Further, with APO, new instances of +the covenant do not require a new set of signers, the setup is truly +one-time. Therefore this type of covenant exists in an even lower +trust-complexity class than CTV emulation via presigneds, which +requires a new federation to sign off on each contract instance. + + +With that preface, let us analyze this covenant: + + +1) A set of sets of transaction intents (a family), potentially +recursive or co-recursive (e.g., the types of state transitions that +can be generated). These intents can also be represented by a +language that generates the transactions, rather than the literal +transactions themselves. We do the family rather than just sets at +this level because to instantiate a covenant we must pick a member of +the family to use. + + +The set of sets of transaction intents is to increment / decrement to +a successor or predecessor, or to halve into two instances or double +value by adding funds. Each successor or predecessor is the same type +of covenant, with the excetion of the first and last, which have some +special rules. + + +2) A verifier generator function that generates a function that +accepts an intent that is any element of one member of the family of +intents and a proof for it and rejects others. + +The verifier generator is the simple APO CHECKSIG script. + +3) A prover generator function that generates a function that takes an +intent that is any element of one member of the family and some extra +data and returns either a new prover function, a finished proof, or a +rejection (if not a valid intent). + +The prover generator is the selection of the correct signature from a +table for a given script. + +Run the prover generator with the private keys present *once* to +initialize over all reachable states, and cache the signatures, then +the keys may be deleted for future runs. + +4) A set of proofs that the Prover, Verifier, and a set of intents are +"impedance matched", that is, all statements the prover can prove and +all statements the verifier can verify are one-to-one and onto (or +something similar), and that this also is one-to-one and onto with one +element of the intents (a set of transactions) and no other. + +At a given key state the only things that may happen are signed +transactions, no other data is interpreted off of the stack. Therefore +there is perfect impedance match. + + +5) A set of assumptions under which the covenant is verified (e.g., a +multi-sig covenant with at least 1-n honesty, a multisig covenant with +any 3-n honesty required, Sha256 collision resistance, Discrete Log +Hardness, a SGX module being correct). + +Uniquely, that during the setup phase at least one of the keys +were faithfully deleted. + +The usual suspects for any bitcoin transaction are also assumed for +security. + + +6) Composability: + +The Terminal State can pay out into a pre-specified covenant if +desired from any other family of covenants. +-- +@JeremyRubin <https://twitter.com/JeremyRubin> + +--0000000000009e509e05e8a75803 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he= +lvetica,sans-serif;font-size:small;color:#000000"><b><span style=3D"font-fa= +mily:Arial,Helvetica,sans-serif;color:rgb(34,34,34)">also available here on= + my blog with nicer formatting:=C2=A0</span><span style=3D"font-family:Aria= +l,Helvetica,sans-serif;color:rgb(34,34,34)"><a href=3D"https://rubin.io/bit= +coin/2022/09/14/drivechain-apo/">https://rubin.io/bitcoin/2022/09/14/drivec= +hain-apo/</a></span></b></div><div class=3D"gmail_default" style=3D"font-fa= +mily:arial,helvetica,sans-serif;font-size:small;color:#000000"><span style= +=3D"font-family:Arial,Helvetica,sans-serif;color:rgb(34,34,34)"><br></span>= +</div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,san= +s-serif;font-size:small;color:#000000"><span style=3D"font-family:Arial,Hel= +vetica,sans-serif;color:rgb(34,34,34)">This post draws heavily from Zmnscpx= +j's fantastic post showing how to</span><br></div>make drivechains with= + recursive covenants. In this post, I will show<br>similar tricks that can = +accomplish something similar using ANYPREVOUT<br>with a one time trusted se= +tup ceremony.<br><br>This post presents general techniques that could be ap= +plied to many<br>different types of covenant.<br><br># Peano Counters<br><b= +r>The first component we need to build is a Peano counter graph. Instead<br= +>of using sha-256, like in Zmnscpxj's scheme, we will use a key and<br>= +build a simple 1 to 5 counter that has inc / dec.<br><br>Assume a key K1...= +K5, and a point NUMS which is e.g.<br>HashToCurve("Spookchains").= +<br><br>Generate scripts as follows:<br><br>```<br><1 || K1> CHECKSIG= +<br>...<br><1 || K5> CHECKSIG<br>```<br><br>Now generate 2 signatures= + under Ki with flags `SIGHASH_SINGLE |<br>SIGHASH_ANYONECANPAY | SIGHASH_AN= +YPREVOUT`.<br><br><br>## Rule Increment<br>For each Ki, when `i < 5`, cr= +eate a signature that covers a<br>transaction described as:<br><br>```<br>A= +mount: 1 satoshi<br>Key: Tr(NUMS, {<1 || K{i+1}> CHECKSIG})<br>```<br= +><br>## Rule Decrement<br>For each Ki, when `i > 1` The second signature= + should cover:<br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {<1 || K{i-1= +}> CHECKSIG})<br>```<br><br><br><br>_Are these really Peano?_ Sort of. W= +hile a traditional Peano numeral<br>is defined as a structural type, e.g. `= +Succ(Succ(Zero))`, here we<br>define them via a Inc / Dec transaction opera= +tor, and we have to<br>explicitly bound these Peano numbers since we need a= + unique key per<br>element. They're at least spiritually similar.<br><b= +r>## Instantiation<br>Publish a booklet of all the signatures for the Incre= +ment and<br>Decrement rules.<br><br>Honest parties should destroy the secre= +t key sets `k`.<br><br><br>To create a counter, simply spend to output C:<b= +r><br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {<1 || K1> CHECKSIG})= +<br>```<br><br><br>The signature from K1 can be bound to C to 'transiti= +on' it to (+1):<br><br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {<1= + || K2> CHECKSIG})<br>```<br><br>Which can then transition to (+1):<br><= +br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {<1 || K3> CHECKSIG})<br= +>```<br><br>Which can then transition (-1) to:<br><br>```<br>Amount: 1 sato= +shi<br>Key: Tr(NUMS, {<1 || K2> CHECKSIG})<br>```<br><br>This can rep= +eat indefinitely.<br><br><br>We can generalize this technique from `1...5` = +to `1...N`.<br><br><br><br># Handling Arbitrary Deposits / Withdrawals<br><= +br><br>One issue with the design presented previously is that it does not<b= +r>handle arbitrary deposits well.<br><br>One simple way to handle this is t= +o instantiate the protocol for every<br>amount you'd like to support.<b= +r><br>This is not particularly efficient and requires a lot of storage<br>s= +pace.<br><br>Alternatively, divide (using base 2 or another base) the depos= +it<br>amount into a counter utxo per bit.<br><br>For each bit, instead of c= +reating outputs with 1 satoshi, create<br>outputs with 2^i satoshis.<br><br= +>Instead of using keys `K1...KN`, create keys `K^i_j`, where i<br>represent= +s the number of sats, and j represents the counter. Multiple<br>keys are re= +quired per amount otherwise the signatures would be valid<br>for burning fu= +nds.<br><br>## Splitting and Joining<br><br>For each `K^i_j`, it may also b= +e desirable to allow splitting or<br>joining.<br><br>Splitting can be accom= +plished by pre-signing, for every `K^i_j`, where<br>`i!=3D0`, with `SIGHASH= +_ALL | SIGHASH_ANYPREVOUT`:<br><br>```<br>Input: 2^i sats with key K^i_j<br= +>Outputs:<br>=C2=A0 =C2=A0 - 2^i-1 sats to key K^{i-1}_j<br>=C2=A0 =C2=A0 -= + 2^i-1 sats to key K^{i-1}_j<br>```<br><br>Joining can be accomplished by p= +re-signing, for every `K^i_j`, where<br>`i!=3DMAX`, with `SIGHASH_ALL | SIG= +HASH_ANYPREVOUT`:<br><br>```<br>Inputs:<br>=C2=A0 =C2=A0 - 2^i sats with ke= +y K^i_j<br>=C2=A0 =C2=A0 - 2^i sats with key K^i_j<br>Outputs:<br>=C2=A0 = +=C2=A0 - 2^i+1 sats to key K^{i+1}_j<br>```<br><br>N.B.: Joining allows for= + third parties to deposit money in externally,<br>that is not a part of the= + covenant.<br><br><br>The splitting and joining behavior means that spookch= +ain operators<br>would be empowered to consolidate UTXOs to a smaller numbe= +r, while<br>allowing arbitrary deposits.<br><br><br># One Vote Per Block<br= +><br>To enforce that only one vote per block mined is allowed, ensure that<= +br>all signatures set the input sequence to 1 block. No CSV is required<br>= +because nSequence is in the signatures already.<br><br># Terminal States / = +Thresholds<br><br>When a counter reaches the Nth state, it represents a cer= +tain amount<br>of accumulated work over a period where progress was agreed = +on for<br>some outcome.<br><br>There should be some viable state transition= + at this point.<br><br>One solution would be to have the money at this poin= +t sent to an<br>`OP_TRUE` output, which the miner incrementing that state i= +s<br>responsible for following the rules of the spookchain. Or, it could be= +<br>specified to be some administrator key / federation for convenience,<br= +>with a N block timeout that degrades it to fewer signers (eventually<br>0)= + if the federation is dead to allow recovery.<br><br>This would look like, = +from any `K^i_j`, a signature for a transaction<br>putting it into an `OP_T= +RUE` and immediately spending it. Other<br>spookchain miners would be expec= +ted to orphan that miner otherwise.<br><br><br># Open States / Proposals<br= +><br>From a state `K^i_1`, the transaction transitioning to `K^i_2` can be<= +br>treated as 'special' and the `OP_RETURN` output type can be used= + to<br>commit to, e.g., the outputs that must be created in when the Termin= +al<br>State is reached. This clarifies the issue of "what is being vot= +ed<br>on".<br><br>This method does not *lock in* at a consensus layer = +what Terminal<br>State is being voted on.<br><br>In certain circumstances, = +without violating the one-time-setup<br>constraint, if a fixed list of with= +drawer's addresses is known in<br>advance, the Open States could cover = +withdrawals to specific<br>participants, which then must collect a certain = +number of votes from<br>miners.=C2=A0 However, it seems impossible, without= + new primitives, for an<br>arbitrary transaction proposal to be voted on.<b= +r><br># Setup Variants<br><br>## xpubs<br><br>Instead of using randomly gen= +erated keys for each state, define each<br>to be an xpub and derive a path = +where it is k/i/j for each<br>state/satoshi amount. This saves some data, a= +nd also requires less<br>entropy.<br><br>### Trustless Data Commit:<br><br>= +commit to the hash of the entire program spec as a tweak to the xpub,<br>so= + that someone can quickly verify if they have all the signatures you<br>are= + expected to generate if honest.<br><br>One way to do this is to convert a = +hash to a list of HD Child Numbers<br>(9 of them) deterministically, and tw= +eak the xpub by that. This is a<br>convenient, yet inefficient, way to twea= +k an xpub because the child<br>has a normal derivation path for signing dev= +ices.<br><br>## Single Party<br><br>A single party pre-signs all the transa= +ctions for the spookchain, and<br>then deletes their xpriv.<br><br>You trus= +t them to have deleted the key, and signed properly, but you<br>do not trus= +t whoever served you the spookchain blob to have given you<br>all the state= + transitions because of the trustless data commitment.<br><br>## MuSig Mult= +i-Party<br><br>Define a MuSig among all participants in the setup ceremony,= + N-of-N.<br><br>Now you simply trust that any one person in the one-time-se= +tup was<br>honest! Very good.<br><br>## Unaggregated Multi-Party<br><br><br= +>Allow for unaggregated multi-sig keys in the spec. This grows with<br>O(si= +gners), however, it means that a-la-carte you can aggregate setups<br>from = +random participants who never interacted / performed setup<br>ceremonies in= +dependently if they signed the same specs.<br><br>Can also combine multiple= + MuSig Multi-Parties in this way.<br><br>This is nice because MuSig inheren= +tly implies the parties colluded at<br>one point to do a MuSig setup, where= +as unaggregated multi-sig could be<br>performed with no connectivity betwee= +n parties.<br><br>## Soft Forking Away Trust<br><br>Suppose a spookchain be= +comes popular. You could configure your client<br>to reject invalid state t= +ransitions, or restrict the spookchain keys<br>to only sign with the known = +signatures. This soft fork would smoothly<br>upgrade the trust assumption.<= +br><br>## Symmetry of State Transition Rules & DAG Covenants<br><br>We = +could have our increment state transitions be done via a trustless<br>coven= +ant, and our backwards state transitions be done via the setup.<br><br>This= + would look something like the following for state i:<br><br>```<br>Tr(NUMS= +, {<br>=C2=A0 =C2=A0 `<sig for state K_{i+1}> <1 || PK_nonsecret&g= +t; CHECKSIG`,<br>=C2=A0 =C2=A0 `<1 || Ki> CHECKSIG`<br>})<br>```<br><= +br>The advantage of such an optimization is theoretically nice because it<b= +r>means that *only* the non-destructuring recursive part of the<br>computat= +ion is subject to the one-time-setup trust assumption, which<br>might be of= + use in various other protocols, where recursivity might<br>only be unlocke= +d e.g. after a timeout (but for spookchains it is used<br>at each step).<br= +><br>A compiler writer might perform this task by starting with an<br>arbit= +rary abstract graph, and then removing edges selectively (a<br>number of he= +uristics may make sense, e.g., to minimize reliance on<br>one-time-setup or= + minimize costs) until the graph is a Directed<br>Acyclic Graph, consisting= + of one or more components, compiling those<div>with committed covenants, a= +nd then<span class=3D"gmail_default" style=3D"font-family:arial,helvetica,s= +ans-serif;font-size:small;color:rgb(0,0,0)"> </span>adding the removed edge= +s back using</div><div>the one-time-setup key materials.<br><br><br># Comme= +ntary on Trust and Covenantiness<br><br>Is this a covenant? I would say &qu= +ot;yes". When I defined covenants in my<br>_Calculus of Covenants_ pos= +t, it was with a particular set of<br>assumptions per covenant.<br><br>Unde= +r that model, you could, e.g., call a 7-10 multi-sig with specific<br>commi= +tted instructions as 4-10 honest (requires 4 signatories to be<br>honest to= + do invalid state transition) and 4-10 killable (requires 4<br>signatories = +to die to have no way of recovering).<br><br>For emulations that are pre-si= +gned, like the varieties used to emulate<br>CTV, it is a different model be= +cause if your program is correct and<br>you've pre-gotten the signature= +s for N-N it is 1-N honest (only 1<br>party must be honest to prevent an in= +valid state transition) and<br>unkillable (all parties can safely delete ke= +ys).<br><br>I model these types of assumptions around liveness and honesty = +as<br>different 'complexity classes' than one another.<br><br>What = +I would point out is that with the counter model presented above,<br>this i= +s entirely a pre-signed 1-N honest and unkillable covenant that<br>requires= + no liveness from signers. Further, with APO, new instances of<br>the coven= +ant do not require a new set of signers, the setup is truly<br>one-time. Th= +erefore this type of covenant exists in an even lower<br>trust-complexity c= +lass than CTV emulation via presigneds, which<br>requires a new federation = +to sign off on each contract instance.<br><br><br>With that preface, let us= + analyze this covenant:<br><br><br>1) A set of sets of transaction intents = +(a family), potentially<br>recursive or co-recursive (e.g., the types of st= +ate transitions that<br>can be generated).=C2=A0 These intents can also be = +represented by a<br>language that generates the transactions, rather than t= +he literal<br>transactions themselves. We do the family rather than just se= +ts at<br>this level because to instantiate a covenant we must pick a member= + of<br>the family to use.<br><br><br>The set of sets of transaction intents= + is to increment / decrement to<br>a successor or predecessor, or to halve = +into two instances or double<br>value by adding funds. Each successor or pr= +edecessor is the same type<br>of covenant, with the excetion of the first a= +nd last, which have some<br>special rules.<br><br><br>2) A verifier generat= +or function that generates a function that<br>accepts an intent that is any= + element of one member of the family of<br>intents and a proof for it and r= +ejects others.<br><br>The verifier generator is the simple APO CHECKSIG scr= +ipt.<br><br>3) A prover generator function that generates a function that t= +akes an<br>intent that is any element of one member of the family and some = +extra<br>data and returns either a new prover function, a finished proof, o= +r a<br>rejection (if not a valid intent).<br><br>The prover generator is th= +e selection of the correct signature from a<br>table for a given script.<br= +><br>Run the prover generator with the private keys present *once* to<br>in= +itialize over all reachable states, and cache the signatures, then<br>the k= +eys may be deleted for future runs.<br><br>4) A set of proofs that the Prov= +er, Verifier, and a set of intents are<br>"impedance matched", th= +at is, all statements the prover can prove and<br>all statements the verifi= +er can verify are one-to-one and onto (or<br>something similar), and that t= +his also is one-to-one and onto with one<br>element of the intents (a set o= +f transactions) and no other.<br><br>At a given key state the only things t= +hat may happen are signed<br>transactions, no other data is interpreted off= + of the stack. Therefore<br>there is perfect impedance match.<br><br><br>5)= + A set of assumptions under which the covenant is verified (e.g., a<br>mult= +i-sig covenant with at least 1-n honesty, a multisig covenant with<br>any 3= +-n honesty required, Sha256 collision resistance, Discrete Log<br>Hardness,= + a SGX module being correct).<br><br>Uniquely, that during the setup phase = +at least one of the keys<br>were faithfully deleted.<br><br>The usual suspe= +cts for any bitcoin transaction are also assumed for<br>security.<br><br><b= +r>6) Composability:<br><br>The Terminal State can pay out into a pre-specif= +ied covenant if<br>desired from any other family of covenants.<br clear=3D"= +all"><div><div dir=3D"ltr" class=3D"gmail_signature" data-smartmail=3D"gmai= +l_signature"><div dir=3D"ltr">--<br><a href=3D"https://twitter.com/JeremyRu= +bin" target=3D"_blank">@JeremyRubin</a><br></div></div></div></div></div> + +--0000000000009e509e05e8a75803-- + |