path: root/0c/73008a54c87b2207ff8401b0dbdc00c8243673

Return-Path: <antoine.riard@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id D980DC002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 30 Sep 2022 02:00:47 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id AB75C61207
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 30 Sep 2022 02:00:47 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org AB75C61207
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=R5gnA5Jp
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 gBmDUHTxZdCE
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 30 Sep 2022 02:00:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 3E40961206
Received: from mail-il1-x12a.google.com (mail-il1-x12a.google.com
 [IPv6:2607:f8b0:4864:20::12a])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 3E40961206
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 30 Sep 2022 02:00:43 +0000 (UTC)
Received: by mail-il1-x12a.google.com with SMTP id i9so1329639ilv.9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 29 Sep 2022 19:00:43 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :from:to:cc:subject:date;
 bh=avcU9keNmwPPKOsRN69fD8Qcqmw0e8VYvM1gsnk/UKs=;
 b=R5gnA5JpcRqyiNPwDxc5nTMJCzyosw0HQNdqfk1sOfo3dpllKQG1JSI+Ye3HWPYmF8
 CiYtCm/xdB/MKanijjs4qJD7sdwEAJF0IDBI3AMPXO6L06Tgh+u3fV/dVE+uBV+aBFZT
 kOw7u6RW97AAuBDXuykQZECgA4iIuJ/elz7Ffq0Kl4k0SrxH4T8QmWB18JWdYG3wHtn9
 Si3cKgCtr1fnNBkiTT2107aOVFCd96YOeW2CUbXQ+spBUZ4bK4TR8xNxIHGnC+F96WNp
 slDiNVp9RgfO6V8qPb1dqtch4v9fGUSeDkcBX9PrGma3FRPC39C+AHpzOppDzNYKixG1
 uB6Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=to:subject:message-id:date:from:in-reply-to:references:mime-version
 :x-gm-message-state:from:to:cc:subject:date;
 bh=avcU9keNmwPPKOsRN69fD8Qcqmw0e8VYvM1gsnk/UKs=;
 b=xh9Scr3Pn4axUBye4nAdASiFv26lmGKDuUCiw5oYjbkQEMUaf0kdTEr1yneoxfeqIb
 vS/Rht2HXbrzt14mo3EOguGX1MlL9YGhxnydpiJaalbr3+GZ6nLjDp+73/Qek1NnomFX
 rw5pNzrqdf/0TCzfq59S23z3B/k1xWxZ0yAUPRdvfyf1Kkx80mktLvkA8Pw3Ia6EqVEP
 /3z2gaYE4PF3hs/qkMCFqmpIixKSu4Xp5/g54R/EkxTMC+VROaFEZU6yidq+LFfsdiwC
 UjiuicmaUuxui/gThII4mSPe+6Ey2s5xeoBB6582vK0vWW6Cq7pbpxbIyCn3WLqpKfkI
 iH1Q==
X-Gm-Message-State: ACrzQf1fj67Ha0XL+vnmetTIGsgFLl6e44RgLyjj+wGm/+PAvNXjBqTD
 RsofkwVzej383sBz8cSObnq15qV5Skr3USQwcDeIugjzsoEvmA==
X-Google-Smtp-Source: AMsMyM4lw0S8cbupCFdIlDeLY1RQ4JBsOAvGYm4n3IjbDoeMDyp3gUTFAP3aRZUMgBWNvh60SxG7bgqchcPCGZhGxfw=
X-Received: by 2002:a92:3652:0:b0:2df:4133:787 with SMTP id
 d18-20020a923652000000b002df41330787mr3188715ilf.39.1664503242260; Thu, 29
 Sep 2022 19:00:42 -0700 (PDT)
MIME-Version: 1.0
References: <CAD5xwhgKGMx79+RLpb-hjd3Gc=EKxTVzkpME-=KuM_C5+d7mRQ@mail.gmail.com>
In-Reply-To: <CAD5xwhgKGMx79+RLpb-hjd3Gc=EKxTVzkpME-=KuM_C5+d7mRQ@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Thu, 29 Sep 2022 22:00:30 -0400
Message-ID: <CALZpt+E6KeyvAp-nBUdO3J79dKRKHEZJkUpcSasJ4TH9h=sU7g@mail.gmail.com>
To: Jeremy Rubin <jeremy.l.rubin@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000007b864205e9db5c7b"
X-Mailman-Approved-At: Fri, 30 Sep 2022 02:18:09 +0000
Subject: Re: [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: Fri, 30 Sep 2022 02:00:48 -0000

--0000000000007b864205e9db5c7b
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Jeremy,

Thanks for bringing back to awareness covenant-based drivechain designs
again!

I'm not super familiar with the thousands shades of sidechains, and
especially how the variants of pegging mechanisms influence the soundness
of the game-theory backing up the functionaries execution. However it could
be interesting to give security bounds to the defect of any trusted
component, such as the one-time trusted setup, and the impacts on funds. If
it's a full-blown loss, a timevalue loss, a privacy leak, etc...

Started at least an entry for the ZmnSCPxj design:
https://github.com/ariard/bitcoin-contracting-primitives-wg/pull/9

One interesting point from the OG post:
> The recursive covenant could, with the help of `OP_CAT` and
> `OP_CTV`, check that every transaction spending the UTXO has a
> second output that is an `OP_RETURN` with a commitment to the
> sidechain block.
> We can ensure that only one such transaction exists in each
> mainchain block by adding a `<1> OP_CSV`, ensuring that only one
> sidechain-commitment transaction can occur on each mainchain
> block.

Such recursive-covenant "embedded" sidechains could be used as solution to
the double-spend of payment pools and channel factories partitions, as an
instantiation of a "on-chain authoritative board" for partitions statement,
as described earlier this year, in a quest to solve the high interactivity
issue affecting those constructions [0].

Best,
Antoine

[0]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020370.h=
tml

Le mer. 14 sept. 2022 =C3=A0 14:32, Jeremy Rubin via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :

> *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!=3D0`, 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!=3DMAX`, 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>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

--0000000000007b864205e9db5c7b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi Jeremy,<br><br>Thanks for bringing back to awareness co=
venant-based drivechain designs again!<br><br>I&#39;m not super familiar wi=
th the thousands shades of sidechains, and especially how the variants of p=
egging mechanisms influence the soundness of the game-theory backing up the=
 functionaries execution. However it could be interesting to give security =
bounds to the defect of any trusted component, such as the one-time trusted=
 setup, and the impacts on funds. If it&#39;s a full-blown loss, a timevalu=
e loss, a privacy leak, etc...<br><br>Started at least an entry for the Zmn=
SCPxj design:<br><a href=3D"https://github.com/ariard/bitcoin-contracting-p=
rimitives-wg/pull/9">https://github.com/ariard/bitcoin-contracting-primitiv=
es-wg/pull/9</a><br><br>One interesting point from the OG post:<br>&gt; The=
 recursive covenant could, with the help of `OP_CAT` and<br>&gt; `OP_CTV`, =
check that every transaction spending the UTXO has a<br>&gt; second output =
that is an `OP_RETURN` with a commitment to the<br>&gt; sidechain block.<br=
>&gt; We can ensure that only one such transaction exists in each<br>&gt; m=
ainchain block by adding a `&lt;1&gt; OP_CSV`, ensuring that only one<br>&g=
t; sidechain-commitment transaction can occur on each mainchain<br>&gt; blo=
ck.<br><br>Such recursive-covenant &quot;embedded&quot; sidechains could be=
 used as solution to the double-spend of payment pools and channel factorie=
s partitions, as an instantiation of a &quot;on-chain authoritative board&q=
uot; for partitions statement, as described earlier this year, in a quest t=
o solve the high interactivity issue affecting those constructions [0].<br>=
<br>Best,<br>Antoine<br><br>[0] <a href=3D"https://lists.linuxfoundation.or=
g/pipermail/bitcoin-dev/2022-April/020370.html">https://lists.linuxfoundati=
on.org/pipermail/bitcoin-dev/2022-April/020370.html</a><br></div><br><div c=
lass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0mer. 14 =
sept. 2022 =C3=A0=C2=A014:32, Jeremy Rubin via bitcoin-dev &lt;<a href=3D"m=
ailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundat=
ion.org</a>&gt; a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204=
);padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"=
font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)"><b=
><span style=3D"font-family:Arial,Helvetica,sans-serif;color:rgb(34,34,34)"=
>also available here on my blog with nicer formatting:=C2=A0</span><span st=
yle=3D"font-family:Arial,Helvetica,sans-serif;color:rgb(34,34,34)"><a href=
=3D"https://rubin.io/bitcoin/2022/09/14/drivechain-apo/" target=3D"_blank">=
https://rubin.io/bitcoin/2022/09/14/drivechain-apo/</a></span></b></div><di=
v class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;f=
ont-size:small;color:rgb(0,0,0)"><span style=3D"font-family:Arial,Helvetica=
,sans-serif;color:rgb(34,34,34)"><br></span></div><div class=3D"gmail_defau=
lt" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:r=
gb(0,0,0)"><span style=3D"font-family:Arial,Helvetica,sans-serif;color:rgb(=
34,34,34)">This post draws heavily from Zmnscpxj&#39;s fantastic post showi=
ng how to</span><br></div>make drivechains with recursive covenants. In thi=
s post, I will show<br>similar tricks that can accomplish something similar=
 using ANYPREVOUT<br>with a one time trusted setup ceremony.<br><br>This po=
st presents general techniques that could be applied to many<br>different t=
ypes of covenant.<br><br># Peano Counters<br><br>The first component we nee=
d to build is a Peano counter graph. Instead<br>of using sha-256, like in Z=
mnscpxj&#39;s scheme, we will use a key and<br>build a simple 1 to 5 counte=
r that has inc / dec.<br><br>Assume a key K1...K5, and a point NUMS which i=
s e.g.<br>HashToCurve(&quot;Spookchains&quot;).<br><br>Generate scripts as =
follows:<br><br>```<br>&lt;1 || K1&gt; CHECKSIG<br>...<br>&lt;1 || K5&gt; C=
HECKSIG<br>```<br><br>Now generate 2 signatures under Ki with flags `SIGHAS=
H_SINGLE |<br>SIGHASH_ANYONECANPAY | SIGHASH_ANYPREVOUT`.<br><br><br>## Rul=
e Increment<br>For each Ki, when `i &lt; 5`, create a signature that covers=
 a<br>transaction described as:<br><br>```<br>Amount: 1 satoshi<br>Key: Tr(=
NUMS, {&lt;1 || K{i+1}&gt; CHECKSIG})<br>```<br><br>## Rule Decrement<br>Fo=
r each Ki, when `i &gt; 1` The second signature should cover:<br>```<br>Amo=
unt: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 || K{i-1}&gt; CHECKSIG})<br>```<br><=
br><br><br>_Are these really Peano?_ Sort of. While a traditional Peano num=
eral<br>is defined as a structural type, e.g. `Succ(Succ(Zero))`, here we<b=
r>define them via a Inc / Dec transaction operator, and we have to<br>expli=
citly bound these Peano numbers since we need a unique key per<br>element. =
They&#39;re at least spiritually similar.<br><br>## Instantiation<br>Publis=
h a booklet of all the signatures for the Increment and<br>Decrement rules.=
<br><br>Honest parties should destroy the secret key sets `k`.<br><br><br>T=
o create a counter, simply spend to output C:<br><br>```<br>Amount: 1 satos=
hi<br>Key: Tr(NUMS, {&lt;1 || K1&gt; CHECKSIG})<br>```<br><br><br>The signa=
ture from K1 can be bound to C to &#39;transition&#39; it to (+1):<br><br>`=
``<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 || K2&gt; CHECKSIG})<br>```=
<br><br>Which can then transition to (+1):<br><br>```<br>Amount: 1 satoshi<=
br>Key: Tr(NUMS, {&lt;1 || K3&gt; CHECKSIG})<br>```<br><br>Which can then t=
ransition (-1) to:<br><br>```<br>Amount: 1 satoshi<br>Key: Tr(NUMS, {&lt;1 =
|| K2&gt; CHECKSIG})<br>```<br><br>This can repeat 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 de=
sign presented previously is that it does not<br>handle arbitrary deposits =
well.<br><br>One simple way to handle this is to instantiate the protocol f=
or every<br>amount you&#39;d like to support.<br><br>This is not particular=
ly efficient and requires a lot of storage<br>space.<br><br>Alternatively, =
divide (using base 2 or another base) the deposit<br>amount into a counter =
utxo per bit.<br><br>For each bit, instead of creating outputs with 1 satos=
hi, create<br>outputs with 2^i satoshis.<br><br>Instead of using keys `K1..=
.KN`, create keys `K^i_j`, where i<br>represents the number of sats, and j =
represents the counter. Multiple<br>keys are required per amount otherwise =
the signatures would be valid<br>for burning funds.<br><br>## Splitting and=
 Joining<br><br>For each `K^i_j`, it may also be desirable to allow splitti=
ng or<br>joining.<br><br>Splitting can be accomplished 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 pre-signing, for every `K^i_j=
`, where<br>`i!=3DMAX`, with `SIGHASH_ALL | SIGHASH_ANYPREVOUT`:<br><br>```=
<br>Inputs:<br>=C2=A0 =C2=A0 - 2^i sats with key 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 mone=
y in externally,<br>that is not a part of the covenant.<br><br><br>The spli=
tting and joining behavior means that spookchain operators<br>would be empo=
wered to consolidate UTXOs to a smaller number, 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 inpu=
t sequence to 1 block. No CSV is required<br>because nSequence is in the si=
gnatures already.<br><br># Terminal States / Thresholds<br><br>When a count=
er reaches the Nth state, it represents a certain 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 sol=
ution would be to have the money at this point sent to an<br>`OP_TRUE` outp=
ut, which the miner incrementing that state is<br>responsible for following=
 the rules of the spookchain. Or, it could be<br>specified to be some admin=
istrator key / federation for convenience,<br>with a N block timeout that d=
egrades 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_TRUE` and immediately spending =
it. Other<br>spookchain miners would be expected to orphan that miner other=
wise.<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 &#39;special&#39=
; and the `OP_RETURN` output type can be used to<br>commit to, e.g., the ou=
tputs that must be created in when the Terminal<br>State is reached. This c=
larifies the issue of &quot;what is being voted<br>on&quot;.<br><br>This me=
thod does not *lock in* at a consensus layer what Terminal<br>State is bein=
g voted on.<br><br>In certain circumstances, without violating the one-time=
-setup<br>constraint, if a fixed list of withdrawer&#39;s addresses is know=
n in<br>advance, the Open States could cover withdrawals to specific<br>par=
ticipants, which then must collect a certain number of votes from<br>miners=
.=C2=A0 However, it seems impossible, without new primitives, for an<br>arb=
itrary transaction proposal to be voted on.<br><br># Setup Variants<br><br>=
## xpubs<br><br>Instead of using randomly generated keys for each state, de=
fine 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, and also requires less<br>entro=
py.<br><br>### Trustless Data Commit:<br><br>commit to the hash of the enti=
re program spec as a tweak to the xpub,<br>so that someone can quickly veri=
fy if they have all the signatures you<br>are expected to generate if hones=
t.<br><br>One way to do this is to convert a hash to a list of HD Child Num=
bers<br>(9 of them) deterministically, and tweak the xpub by that. This is =
a<br>convenient, yet inefficient, way to tweak an xpub because the child<br=
>has a normal derivation path for signing devices.<br><br>## Single Party<b=
r><br>A single party pre-signs all the transactions for the spookchain, and=
<br>then deletes their xpriv.<br><br>You trust them to have deleted the key=
, and signed properly, but you<br>do not trust whoever served you the spook=
chain blob to have given you<br>all the state transitions because of the tr=
ustless data commitment.<br><br>## MuSig Multi-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-setup 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(signers), however, it means that=
 a-la-carte you can aggregate setups<br>from random participants who never =
interacted / performed setup<br>ceremonies independently if they signed the=
 same specs.<br><br>Can also combine multiple MuSig Multi-Parties in this w=
ay.<br><br>This is nice because MuSig inherently implies the parties collud=
ed at<br>one point to do a MuSig setup, whereas unaggregated multi-sig coul=
d be<br>performed with no connectivity between parties.<br><br>## Soft Fork=
ing Away Trust<br><br>Suppose a spookchain becomes popular. You could confi=
gure your client<br>to reject invalid state transitions, or restrict the sp=
ookchain keys<br>to only sign with the known signatures. This soft fork wou=
ld smoothly<br>upgrade the trust assumption.<br><br>## Symmetry of State Tr=
ansition Rules &amp; DAG Covenants<br><br>We could have our increment state=
 transitions be done via a trustless<br>covenant, and our backwards state t=
ransitions 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 `&lt;sig =
for state K_{i+1}&gt; &lt;1 || PK_nonsecret&gt; CHECKSIG`,<br>=C2=A0 =C2=A0=
 `&lt;1 || Ki&gt; CHECKSIG`<br>})<br>```<br><br>The advantage of such an op=
timization is theoretically nice because it<br>means that *only* the non-de=
structuring recursive part of the<br>computation is subject to the one-time=
-setup trust assumption, which<br>might be of use in various other protocol=
s, where recursivity might<br>only be unlocked e.g. after a timeout (but fo=
r spookchains it is used<br>at each step).<br><br>A compiler writer might p=
erform this task by starting with an<br>arbitrary abstract graph, and then =
removing edges selectively (a<br>number of heuristics may make sense, e.g.,=
 to minimize reliance on<br>one-time-setup or minimize costs) until the gra=
ph is a Directed<br>Acyclic Graph, consisting of one or more components, co=
mpiling those<div>with committed covenants, and then<span class=3D"gmail_de=
fault" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;colo=
r:rgb(0,0,0)"> </span>adding the removed edges back using</div><div>the one=
-time-setup key materials.<br><br><br># Commentary on Trust and Covenantine=
ss<br><br>Is this a covenant? I would say &quot;yes&quot;. When I defined c=
ovenants in my<br>_Calculus of Covenants_ post, it was with a particular se=
t of<br>assumptions per covenant.<br><br>Under that model, you could, e.g.,=
 call a 7-10 multi-sig with specific<br>committed instructions as 4-10 hone=
st (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 recov=
ering).<br><br>For emulations that are pre-signed, like the varieties used =
to emulate<br>CTV, it is a different model because if your program is corre=
ct and<br>you&#39;ve pre-gotten the signatures for N-N it is 1-N honest (on=
ly 1<br>party must be honest to prevent an invalid state transition) and<br=
>unkillable (all parties can safely delete keys).<br><br>I model these type=
s of assumptions around liveness and honesty as<br>different &#39;complexit=
y classes&#39; than one another.<br><br>What I would point out is that with=
 the counter model presented above,<br>this is entirely a pre-signed 1-N ho=
nest and unkillable covenant that<br>requires no liveness from signers. Fur=
ther, with APO, new instances of<br>the covenant do not require a new set o=
f signers, the setup is truly<br>one-time. Therefore this type of covenant =
exists in an even lower<br>trust-complexity class than CTV emulation via pr=
esigneds, which<br>requires a new federation to sign off on each contract i=
nstance.<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>rec=
ursive or co-recursive (e.g., the types of state transitions that<br>can be=
 generated).=C2=A0 These intents can also be represented by a<br>language t=
hat generates the transactions, rather than the literal<br>transactions the=
mselves. We do the family rather than just sets 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 t=
o<br>a successor or predecessor, or to halve into two instances or double<b=
r>value by adding funds. Each successor or predecessor is the same type<br>=
of covenant, with the excetion of the first and last, which have some<br>sp=
ecial rules.<br><br><br>2) A verifier generator function that generates a f=
unction that<br>accepts an intent that is any element of one member of the =
family of<br>intents and a proof for it and rejects others.<br><br>The veri=
fier generator is the simple APO CHECKSIG script.<br><br>3) A prover genera=
tor function that generates a function that takes an<br>intent that is any =
element of one member of the family and some extra<br>data and returns eith=
er a new prover function, a finished proof, or a<br>rejection (if not a val=
id intent).<br><br>The prover generator is the selection of the correct sig=
nature from a<br>table for a given script.<br><br>Run the prover generator =
with the private keys present *once* to<br>initialize over all reachable st=
ates, and cache the signatures, then<br>the keys may be deleted for future =
runs.<br><br>4) A set of proofs that the Prover, Verifier, and a set of int=
ents are<br>&quot;impedance matched&quot;, that is, all statements the prov=
er can prove and<br>all statements the verifier can verify are one-to-one a=
nd onto (or<br>something similar), and that this also is one-to-one and ont=
o with one<br>element of the intents (a set of transactions) and no other.<=
br><br>At a given key state the only things that may happen are signed<br>t=
ransactions, no other data is interpreted off of the stack. Therefore<br>th=
ere is perfect impedance match.<br><br><br>5) A set of assumptions under wh=
ich the covenant is verified (e.g., a<br>multi-sig covenant with at least 1=
-n honesty, a multisig covenant with<br>any 3-n honesty required, Sha256 co=
llision 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>we=
re faithfully deleted.<br><br>The usual suspects for any bitcoin transactio=
n are also assumed for<br>security.<br><br><br>6) Composability:<br><br>The=
 Terminal State can pay out into a pre-specified covenant if<br>desired fro=
m any other family of covenants.<br clear=3D"all"><div><div dir=3D"ltr"><di=
v dir=3D"ltr">--<br><a href=3D"https://twitter.com/JeremyRubin" target=3D"_=
blank">@JeremyRubin</a><br></div></div></div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000007b864205e9db5c7b--