* [bitcoin-dev] Merkleize All The Things
@ 2022-11-08 9:17 Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
` (3 more replies)
0 siblings, 4 replies; 20+ messages in thread
From: Salvatore Ingala @ 2022-11-08 9:17 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 27496 bytes --]
Hi list,
I have been working on some notes to describe an approach that uses
covenants in order to enable general smart contracts in bitcoin. You can
find them here:
https://merkle.fun
The approach has a number of desirable features:
- small impact to layer 1;
- not application-specific, very general;
- it fits well into P2TR;
- it does not require new cryptographic assumptions, nor any construction
that has not withstood the test of time.
This content was presented at the BTCAzores unconference, where it received
the name of MATT − short for Merkleize All The Things.
In fact, no other cryptographic primitive is required, other than Merkle
trees.
I believe this construction gets close to answering the question of how
small a change on bitcoin's layer 1 would suffice to enable arbitrary smart
contracts.
It is not yet at the stage where a formal proposal can be made, therefore
the proposed specs are only for illustrative purposes.
The same content is reformatted below for the mailing list.
Looking forward to hearing about your comments and improvements.
Salvatore Ingala
==========================================
# General smart contracts in bitcoin via covenants
Covenants are UTXOs that are encumbered with restrictions on the outputs of
the transaction spending the UTXO. More formally, we can define a covenant
any UTXO such that at least one of its spending conditions is valid only if
one or more of the outputs’ scriptPubKey satisfies certain restrictions.
Generally, covenant proposals also add some form of introspection (that is,
the ability for Script to access parts of the inputs/outputs, or the
blockchain history).
In this note, we want to explore the possibilities unleashed by the
addition of a covenant with the following properties:
- introspection limited to a single hash attached to the UTXO (the
“covenant data”), and input/output amounts;
- pre-commitment to every possible future script (but not their data);
- few simple opcodes operating with the covenant data.
We argue that such a simple covenant construction is enough to extend the
power of bitcoin’s layer 1 to become a universal settlement layer for
arbitrary computation.
Moreover, the covenant can elegantly fit within P2TR transactions, without
any substantial increase for the workload of bitcoin nodes.
A preliminary version of these notes was presented and discussed at the
BTCAzores Unconference [1], on 23rd September 2022.
# Preliminaries
We can think of a smart contract as a “program” that updates a certain
state according to predetermined rules (which typically include access
control by authorizing only certain public keys to perform certain
actions), and that can possibly lock/unlock some coins of the underlying
blockchain according to the same rules.
The exact definition will be highly dependent on the properties of the
underlying blockchain.
In bitcoin, the only state upon which all the nodes reach consensus is the
UTXO set; other blockchains might have other data structures as part of the
consensus, like a key-value store that can be updated as a side effect of
transaction execution.
In this section we explore the following concepts in order to set the
framework for a definition of smart contracts that fits the structure of
bitcoin:
- the contract’s state: the “memory” the smart contract operates on;
- state transitions: the rules to update the contract’s state;
- covenants: the technical means that can allow contracts to function in
the context of a bitcoin UTXO.
In the following, an on-chain smart contract is always represented as a
single UTXO that implicitly embeds the contract’s state and possibly
controls some coins that are “locked” in it. More generally, one could
think of smart contracts that are represented in a set of multiple UTXOs;
we leave the exploration of generalizations of the framework to future
research.
## State
Any interesting “state” of a smart contract can ultimately be encoded as a
list, where each element is either a bit, a fixed-size integers, or an
arbitrary byte string.
Whichever the choice, it does not really affect what kinds of computations
are expressible, as long as one is able to perform some basic computations
on those elements.
In the following, we will assume without loss of generality that
computations happen on a state which is a list of fixed length S = [s_1,
s_2, …, s_n], where each s_i is a byte string.
### Merkleized state
By constructing a Merkle tree that has the (hashes of) the elements of S in
the leaves, we can produce a short commitment h_S to the entire list S with
the following properties (that hold for a verifier that only knows h_S):
- a (log n)-sized proof can prove the value of an element s_i;
- a (log n + |x|)-sized proof can prove the new commitment h_S’, where S’
is a new list obtained by replacing the value of a certain leaf with x.
This allows to compactly commit to a RAM, and to prove correctness of RAM
updates.
In other words, a stateful smart contract can represent an arbitrary state
in just a single hash, for example a 32-byte SHA256 output.
### State transitions and UTXOs
We can conveniently represent a smart contract as a finite state machine
(FSM), where exactly one node can be active at a given time. Each node has
an associated state as defined above, and a set of transition rules that
define:
- who can use the rule;
- what is the next active node in the FSM;
- what is the state of the next active node.
It is then easy to understand how covenants can conveniently represent and
enforce the smart contracts in this framework:
- The smart contract is instantiated by creating a UTXO encumbered with a
covenant; the smart contract is in the initial node of the FSM.
- The UTXO’s scriptPubKey specifies the current state and the valid
transitions.
- The UTXO(s) produced after a valid transition might or might not be
further encumbered, according to the rules.
Therefore, what is necessary in order to enable this framework in bitcoin
Script is a covenant that allows the enforcement of such state transitions,
by only allowing outputs that commit to a valid next node (and
corresponding state) in the FSM.
It is not difficult to show that arbitrary computation is possible over the
committed state, as long as relatively simple arithmetic or logical
operations are available over the state.
Remark: using an acyclic FSM does not reduce the expressivity of the smart
contracts, as any terminating computation on bounded-size inputs which
requires cycles can be unrolled into an acyclic one.
### Merkleized state transitions
Similarly to how using Merkle trees allows to succinctly represent
arbitrary data with a short, 32-byte long summary, the same trick allows to
succinctly represent arbitrary state transitions (the smart contract’s
code) with a single 32-byte hash. Each of the possible state transitions is
encoded as a Script which is put in a leaf of a Merkle tree; the Merkle
root of this tree is a commitment to all the possible state transitions.
This is exactly what the taptree achieves in Taproot (see BIP-0341 [2]).
Later sections in this document will suggest a possible way of how both the
contract’s state and valid transition rules could be represented in UTXOs.
## On-chain computation?!
Should the chain actually do computation?
If naively designed, the execution of a contract might require a large
number of transactions, which is not feasible.
While the covenant approach does indeed enable a chain of transactions to
perform arbitrary computation, simple economic considerations will push
protocol designers to perform any non-trivial computation off-chain, and
instead use the blockchain consensus only to verify the computation; or, if
possible, skip the verification altogether.
The fundamental fact that a blockchain’s layer 1 never actually needs to
run complex programs in order to enable arbitrary complex smart contracting
was observed in the past, for example in a 2016 post by Greg Maxwell [3].
Vitalik Buterin popularized the concept of "functionality escape velocity"
[4] to signify the minimum amount of functionality required on layer 1 in
order to enable anything else to be built on top (that is, on layer 2 and
beyond).
In the following section, we will argue that a simple covenant construction
suffices to achieve the functionality escape velocity in the UTXO model.
# Commitments to computation and fraud challenges
In this section, we explore how a smart contract that requires any
non-trivial computation f : X --> Y (that is too expensive or not feasible
with on-chain Script state transitions) can be implemented with the simple
covenants described in the previous section.
The ideas in this section appeared in literature; the reader is referred to
the references for a more comprehensive discussion.
We want to be able to build contracts that allow conditions of the type
"f(x) = y"; yet, we do not want layer 1 to be forced to perform any
expensive computation.
In the following, we assume for simplicity that Alice and Bob are the only
participants of the covenant, and they both locked some funds bond_A and
bond_B (respectively) inside the covenant’s UTXO.
1. Alice posts the statement “f(x) = y”.
2. After a challenge period, if no challenge occurs, Alice is free to
continue and unlock the funds; the statement is true.
3. At any time before the challenge period expires, Bob can start a
challenge: “actually, f(x) = z”.
In case of a challenge, Alice and Bob enter a challenge resolution
protocol, arbitrated by layer 1; the winner takes the other party’s bond
(details and the exact game theory vary based on the type of protocol the
challenge is part of; choosing the right amount of bonds is crucial for
protocol design).
The remainder of this section sketches an instantiation of the challenge
protocol.
## The bisection protocol for arbitrary computation
In this section, we sketch the challenge protocol for an arbitrary
computation f : X --> Y.
### Computation trace
Given the function f, it is possible to decompose the entire computation in
simple elementary steps, each performing a simple, atomic operation. For
example, if the domain of x and y is that of binary strings of a fixed
length, it is possible to create a boolean circuit that takes x and
produces y; in practice, some form of assembly-like language operating on a
RAM might be more efficient and fitting for bitcoin Script.
In the following, we assume each elementary operation is operating on a
RAM, encoded in the state via Merkle trees as sketched above. Therefore,
one can represent all the steps of the computation as triples tri = (st_i,
op_i, st_{i + 1}), where st_i is the state (e.g. a canonical Merkle tree of
the RAM) before the i-th operation, st_{i + 1} is the state after, and op_i
is the description of the operation (implementation-specific; it could be
something like “add a to b and save the result in c).
Finally, a Merkle tree M_T is constructed that has as leaves the values of
the individual computation steps T = {tr_0, tr_1, …, tr_{N - 1}} if the
computation requires N steps, producing the Merkle root h_T. The height of
the Merkle tree is log N. Observe that each internal node commits to the
portion of the computation trace corresponding to its own subtree.
Let’s assume that the Merkle tree commitments for internal nodes are
further augmented with the states st_{start} and st_{end}, respectively the
state before the operation of in the leftmost leaf of the subtree, and
after the rightmost leaf of the subtree.
### Bisection protocol
The challenge protocol begins with Alice posting what she claims is the
computation trace h_A, while Bob disagrees with the trace h_B != h_A;
therefore, the challenge starts at the root of M_T, and proceeds in steps
in order to find a leaf where Alice and Bob disagree (which is guaranteed
to exist, hence the disagreement). Note that the arbitration mechanism
knows f, x and y, but not the correct computation trace hash h_T.
(Bisection phase): While the challenge is at a non-leaf node of M_T, Alice
and Bob take turns to post the two hashes corresponding to the left and
right child of their claimed computation trace hash; moreover, they post
the start/end state for each child node. The protocol enforces that Alice’s
transaction is only valid if the posted hashes h_{l; A} and h_{r; A}, and
the declared start/end state for each child are consistent with the
commitment in the current node.
(Arbitration phase): If the protocol has reached the i-th leaf node, then
each party reveals (st_i, op_i, st_{i + 1}); in fact, only the honest party
will be able to reveal correct values, therefore the protocol can
adjudicate the winner.
Remark: there is definitely a lot of room for optimizations; it is left for
future work to find the optimal variation of the approach; moreover,
different challenge mechanisms could be more appropriate for different
functions f.
### Game theory (or why the chain will not see any of this)
With the right economic incentives, protocol designers can guarantee that
playing a losing game always loses money compared to cooperating.
Therefore, the challenge game is never expected to be played on-chain. The
size of the bonds need to be appropriate to disincentivize griefing attacks.
### Implementing the bisection protocol's state transitions
It is not difficult to see that the entire challenge-response protocol
above can be implemented using the simple state transitions described above.
Before a challenge begins, the state of the covenant contains the value of
x, y and the computation trace computed by Alice. When starting the
challenge, Bob also adds its claim for the correct computation trace, and
the covenant enters the bisection phase.
During the bisaction phase, the covenant contains the claimed computation
trace for that node of the computation protocol, according to each party.
In turns, each party has to reveal the corresponding computation trace for
both the children of the current node; the transaction is only valid if the
hash of the current node can be computed correctly from the information
provided by each party about the child nodes. The protocol repeats on one
of the two child nodes on whose computation trace the two parties disagree
(which is guaranteed to exist). If a leaf of M_T is reached, the covenant
enters the final arbitration phase.
During the arbitration phase (say at the i-th leaf node of M_T), any party
can win the challenge by providing correct values for tr_i = (st_i, op_i,
st_{i + 1}). Crucially, only one party is able to provide correct values,
and Script can verify that indeed the state moves from st_i to st_{i + 1}
by executing op_i. The challenge is over.
At any time, the covenant allows one player to automatically win the
challenge after a certain timeout if the other party (who is expected to
“make his move”) does not spend the covenant. This guarantees that the
protocol can always find a resolution.
### Security model
As for other protocols (like the lightning network), a majority of miners
can allow a player to win a challenge by censoring the other player’s
transactions. Therefore, the bisection protocol operates under the honest
miner majority assumption. This is acceptable for many protocols, but it
should certainly be taken into account during protocol design.
# MATT covenants
We argued that the key to arbitrary, fully general smart contracts in the
UTXO model is to use Merkle trees, at different levels:
1. succinctly represent arbitrary state with a single hash. Merkleize the
state!
2. succinctly represent the possible state transitions with a single hash.
Merkleize the Script!
3. succinctly represent arbitrary computations with a single hash.
Merkleize the execution!
(1) and (2) alone allow contracts with arbitrary computations; (3) makes
them scale.
Merkleize All The Things!
In this section we sketch a design of covenant opcodes that are
taproot-friendly and could easily be added in a soft fork to the existing
SegWitv1 Script.
## Embedding covenant data in P2TR outputs
We can take advantage of the double-commitment structure of taproot outputs
(that is, committing to both a public key and a Merkle tree of scripts) to
compactly encode both the covenant and the state transition rules inside
taproot outputs.
The idea is to replace the internal pubkey Q with a key Q’ obtained by
tweaking Q with the covenant data (the same process that is used to commit
to the root of the taptree). More precisely, if d is the data committed to
the covenant, the covenant-data-augmented internal key Q’ is defined as:
Q’ = Q + int(hashTapCovenantData(Q || h_{data}))G
where h_{data} is the sha256-hash of the covenant data. It is then easy to
prove that the point is constructed in this way, by repeating the
calculation.
If there is no useful key path spend, similarly to what is suggested in
BIP-0341 [5] for the case of scripts with no key path spends, we can use
the NUMS point:
H =
lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0).
TODO: please double check if the math above is sound.
## Changes to Script
The following might be some minimal new opcodes to add for taproot
transactions in order to enable the construction above. This is a very
preliminary proposal, and not yet complete nor correct.
- OP_SHA256CAT: returns the SHA256 hash of the concatenation of the second
and the first (top) element of the stack. (redundant if OP_CAT is enabled,
even just on operands with total length up to 64 bytes)
- OP_CHECKINPUTCOVENANTVERIFY: let x, d be the two top elements of the
stack; behave like OP_SUCCESS if any of x and d is not exactly 32 bytes;
otherwise, check that the x is a valid x-only pubkey, and the internal
pubkey P is indeed obtained by tweaking lift_x(x) with d.
- OP_INSPECTNUMINPUTS, OP_INSPECTNUMOUTPUTS, OP_INSPECTINPUTVALUE and
OP_INSPECTOUTPUTVALUE - opcodes to push number on the stack of
inputs/outputs and their amounts.
- OP_CHECKOUTPUTCOVENANTVERIFY: given a number out_i and three 32-byte hash
elements x, d and taptree on top of the stack, verifies that the out_i-th
output is a P2TR output with internal key computed as above, and tweaked
with taptree. This is the actual covenant opcode.
TODO:
- Many contracts need parties to provide additional data; simply passing it
via the witness faces the problem that it could be malleated. Therefore, a
way of passing signed data is necessary. One way to address this problem
could be to add a commitment to the data in the annex, and add an opcode to
verify such commitment. Since the annex is covered by the signature, this
removes any malleability. Another option is an OP_CHECKSIGFROMSTACK opcode,
but that would cost an additional signature check.
- Bitcoin numbers in current Script are not large enough for amounts.
Other observations:
- OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could have a
mode where x is replaced with a NUMS pubkey, for example if the first
operand is an empty array of bytes instead of a 32 byte pubkey; this saves
about 31 bytes when no internal pubkey is needed (so about 62 bytes for a
typical contract transition using both opcodes)
- Is it worth adding other introspection opcodes, for example
OP_INSPECTVERSION, OP_INSPECTLOCKTIME? See Liquid's Tapscript Opcodes [6].
- Is there any malleability issue? Can covenants “run” without signatures,
or is a signature always to be expected when using spending conditions with
the covenant encumbrance? That might be useful in contracts where no
signature is required to proceed with the protocol (for example, any party
could feed valid data to the bisection protocol above).
- Adding some additional opcodes to manipulate stack elements might also
bring performance improvements in applications (but not strictly necessary
for feasibility).
Remark: the additional introspection opcodes available in Blockstream
Liquid [6] do indeed seem to allow MATT covenants; in fact, the opcodes
OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could be
replaced by more general opcodes like the group {OP_TWEAKVERIFY,
OP_INSPECTINPUTSCRIPTPUBKEY, OP_PUSHCURRENTINPUTINDEX,
OP_INSPECTOUTPUTSCRIPTPUBKEY }.
### Variant: bounded recursivity
In the form described above, the covenant essentially allows fully
recursive constructions (an arbitrary depth of the covenant execution tree
is in practice equivalent to full recursion).
If recursivity is not desired, one could modify the covenants in a way that
only allows a limited depth: a counter could be attached to the covenant,
with the constraint that the counter must be decreased for
OP_CHECKOUTPUTCOVENANTVERIFY. That would still allow arbitrary fraud proofs
as long as the maximum depth is sufficient.
However, that would likely reduce its utility and prevent certain
applications where recursivity seems to be a requirement.
The full exploration of the design space is left for future research.
# Applications
This section explores some of the potential use cases of the techniques
presented above. The list is not exhaustive.
Given the generality of fraud proofs, some variant of every kind of smart
contracts or layer two construction should be possible with MATT covenants,
although the additional requirements (for example the capital lockup and
the challenge period delays) needs to be accurately considered; further
research is necessary to assess for what applications the tradeoffs are
acceptable.
## State channels
A state channel is a generalization of a payment channel where,
additionally to the balance at the end of each channel, some additional
state is stored. The state channel also specifies what are the rules on how
to update the channel’s state.
For example, two people might play a chess game, where the state encodes
the current configuration of the board. The valid state transitions
correspond to the valid moves; and, once the game is over, the winner takes
a specified amount of the channel’s money.
With eltoo-style updates, such a game could be played entirely off-chain,
as long as both parties are cooperating (by signing the opponent’s state
update).
The role of the blockchain is to guarantee that the game can be moved
forward and eventually terminated in case the other party does not
cooperate.
In stateful blockchain, this is simply achieved by publishing the latest
state (Merkleized or not) and then continuing the entire game on-chain.
This is expensive, especially if the state transitions require some complex
computation.
An alternative that avoids moving computations on-chain is the use of a
challenge-response protocol, as sketched above.
Similarly to the security model of lightning channels, an honest party can
always win a challenge under the honest-majority of miners. Therefore, it
is game-theoretically losing to attempt cheating in a channel.
## CoinPool
Multiparty state channels are possible as well; therefore, constructions
like CoinPool [7] should be possible, enabling multiple parties to share a
single UTXO.
## Zero knowledge proofs in L2 protocols
Protocols based on ZK-proofs require the blockchain to be the verifier; the
verifier is a function that takes a zero-knowledge proof and returns
true/false based on its correctness.
Instead of an OP_STARK operator in L1, one could think of compiling the
OP_STARK as the function f in the protocol above.
Note that covenants with a bounded “recursion depth” are sufficient to
express OP_STARK, which in turns imply the ability to express arbitrary
functions within contracts using the challenge protocol.
One advantage of this approach is that no new cryptographic assumptions are
added to bitcoin’s layer 1 even if OP_STARK does require it; moreover, if a
different or better OP_STARK2 is discovered, the innovation can reach layer
2 contracts without any change needed in layer 1.
## Optimistic rollups
John Light recently posted a research report on how Validity Rollups could
be added to bitcoin’s layer 1 [8]. While no exact proposal is pushed
forward, the suggested changes required might include a combination of
recursive covenants, and specific opcodes for validity proof verification.
Fraud proofs are the core for optimistic rollups; exploring the possibility
of implementing optimistic rollups with MATT covenants seems a promising
direction. Because of the simplicity of the required changes to Script,
this might answer some of the costs and risks analyzed in the report, while
providing many of the same benefits. Notably, no novel cryptography needs
to become part of bitcoin’s layer 1.
Optimistic Rollups would probably require a fully recursive version of the
covenant (while fraud proofs alone are possible with a limited recursion
depth).
# Acknowledgments
Antoine Poinsot suggested an improvement to the original proposed covenant
opcodes, which were limited to taproot outputs without a valid key-path
spend.
The author would also like to thank catenocrypt, Antoine Riard, Ruben
Somsen and the participants of the BTCAzores unconference for many useful
discussions and comments on early versions of this proposal.
# References
The core idea of the bisection protocol appears to have been independently
rediscovered multiple times. In blockchain research, it is at the core of
fraud proof constructions with similar purposes, although not focusing on
bitcoin or covenants; see for example:
- Harry Kalodner et al. “Arbitrum: Scalable, private smart contracts.” −
27th USENIX Security Symposium. 2018.
https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf
- Jason Teutsch and Christian Reitwiessner. “A scalable verification
solution for blockchains” − TrueBit protocol. 2017.
https://people.cs.uchicago.edu/~teutsch/papers/truebit.pdf
The same basic idea was already published prior to blockchain use cases;
see for example:
Ran Canetti, Ben Riva, and Guy N. Rothblum. “Practical delegation of
computation using multiple servers.” − Proceedings of the 18th ACM
conference on Computer and communications security. 2011.
http://diyhpl.us/~bryan/papers2/bitcoin/Practical%20delegation%20of%20computation%20using%20multiple%20servers.pdf
# Footnotes
[1] - https://btcazores.com
[2] - https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
[3] -
https://bitcointalk.org/index.php?topic=1427885.msg14601127#msg14601127
[4] - https://vitalik.ca/general/2019/12/26/mvb.html
[5] -
https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#constructing-and-spending-taproot-outputs
[6] -
https://github.com/ElementsProject/elements/blob/master/doc/tapscript_opcodes.md
[7] - https://coinpool.dev/v0.1.pdf
[8] - https://bitcoinrollups.org
[-- Attachment #2: Type: text/html, Size: 28891 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-08 9:17 [bitcoin-dev] Merkleize All The Things Salvatore Ingala
@ 2022-11-08 12:01 ` ZmnSCPxj
2022-11-10 9:42 ` Salvatore Ingala
2022-11-08 23:34 ` Bram Cohen
` (2 subsequent siblings)
3 siblings, 1 reply; 20+ messages in thread
From: ZmnSCPxj @ 2022-11-08 12:01 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion
Good morning Salvatore,
Interesting idea.
The idea to embed the current state is similar to something I have been musing about recently.
> ### Game theory (or why the chain will not see any of this)
>
> With the right economic incentives, protocol designers can guarantee that playing a losing game always loses money compared to cooperating. Therefore, the challenge game is never expected to be played on-chain. The size of the bonds need to be appropriate to disincentivize griefing attacks.
Modulo bugs, operator error, misconfigurations, and other irrationalities of humans.
> - OP_CHECKOUTPUTCOVENANTVERIFY: given a number out_i and three 32-byte hash elements x, d and taptree on top of the stack, verifies that the out_i-th output is a P2TR output with internal key computed as above, and tweaked with taptree. This is the actual covenant opcode.
Rather than get taptree from the stack, just use the same taptree as in the revelation of the P2TR.
This removes the need to include quining and similar techniques: just do the quining in the SCRIPT interpreter.
The entire SCRIPT that controls the covenant can be defined as a taptree with various possible branches as tapleaves.
If the contract is intended to terminate at some point it can have one of the tapleaves use `OP_CHECKINPUTCOVENANTVERIFY` and then determine what the output "should" be using e.g. `OP_CHECKTEMPLATEVERIFY`.
> - Is it worth adding other introspection opcodes, for example OP_INSPECTVERSION, OP_INSPECTLOCKTIME? See Liquid's Tapscript Opcodes [6].
`OP_CHECKTEMPLATEVERIFY` and some kind of sha256 concatenated hashing should be sufficient I think.
> - Is there any malleability issue? Can covenants “run” without signatures, or is a signature always to be expected when using spending conditions with the covenant encumbrance? That might be useful in contracts where no signature is required to proceed with the protocol (for example, any party could feed valid data to the bisection protocol above).
Hmm protocol designer beware?
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-08 9:17 [bitcoin-dev] Merkleize All The Things Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
@ 2022-11-08 23:34 ` Bram Cohen
2022-11-09 12:07 ` Peter Todd
2022-11-10 7:39 ` David A. Harding
2022-11-11 21:49 ` Antoine Riard
3 siblings, 1 reply; 20+ messages in thread
From: Bram Cohen @ 2022-11-08 23:34 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 1277 bytes --]
On Tue, Nov 8, 2022 at 2:13 AM Salvatore Ingala via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> I have been working on some notes to describe an approach that uses
> covenants in order to enable general smart contracts in bitcoin. You can
> find them here:
>
> https://merkle.fun/
> <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
>
Hash chained covenants in general all have about the same plateau of
functionality, which seems roughly reasonable to add to Bitcoin as it is
today but suffer from being limited and hence likely only a stepping stone
to greater functionality and unless whatever's put in now cleanly extends
to supporting more in the future it's likely to turn into a legacy
appendage which has to be supported. So my generic suggestion for this sort
of thing is that it should be proposed along with a plan for how it could
be extended to support full-blown covenants in the future.
Another probably unhelpful bit of feedback I have is that Bitcoin should
probably be taking verkle trees seriously because those can have
substantially lower size/cost/weight than merkle trees. That doesn't just
apply to this proposal, but to Bitcoin in general, which doesn't seem to
have any serious verkle tree proposals to date.
[-- Attachment #2: Type: text/html, Size: 1794 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-08 23:34 ` Bram Cohen
@ 2022-11-09 12:07 ` Peter Todd
0 siblings, 0 replies; 20+ messages in thread
From: Peter Todd @ 2022-11-09 12:07 UTC (permalink / raw)
To: Bram Cohen, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 934 bytes --]
On Tue, Nov 08, 2022 at 03:34:32PM -0800, Bram Cohen via bitcoin-dev wrote:
> Another probably unhelpful bit of feedback I have is that Bitcoin should
> probably be taking verkle trees seriously because those can have
> substantially lower size/cost/weight than merkle trees. That doesn't just
> apply to this proposal, but to Bitcoin in general, which doesn't seem to
> have any serious verkle tree proposals to date.
Verkle trees only reduce proof sizes by a factor of 6-8, and they introduce
significant implementation complexity and new cryptographic assumptions. Better
to let other crypto-systems get a few more years of experience with them before
adding them to Bitcoin. Particularly since even having merkle trees in Bitcoin
is arguably a mistake: they allow for degenerate, weak, security modes like SPV
that aren't clearly good for Bitcoin as a whole.
--
https://petertodd.org 'peter'[:-1]@petertodd.org
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-08 9:17 [bitcoin-dev] Merkleize All The Things Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
2022-11-08 23:34 ` Bram Cohen
@ 2022-11-10 7:39 ` David A. Harding
2022-11-11 21:49 ` Antoine Riard
3 siblings, 0 replies; 20+ messages in thread
From: David A. Harding @ 2022-11-10 7:39 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion
On 2022-11-07 23:17, Salvatore Ingala via bitcoin-dev wrote:
> Hi list,
Hi Salvatore!,
> I have been working on some notes to describe an approach that uses
> covenants in order to enable general smart contracts in bitcoin. You
> can find them here:
>
> https://merkle.fun
I haven't yet been able to understand everything in your post, but I'm
wondering if you can describe how your proposal significantly differs in
application from [1]? E.g., you write:
> 1. Alice posts the statement “f(x) = y”.
> 2. After a challenge period, if no challenge occurs, Alice is free to
> continue and unlock the funds; the statement is true.
> 3. At any time before the challenge period expires, Bob can start a
> challenge: “actually, f(x) = z”.
That looks to me very similar to Gregory Maxwell's script from[1]
(comments and variable name changes mine):
# Offchain, Alice posts the statement f(x) = y
# Offchain, Bob provides Ex, an encrypted form of x that can be proven
in zero knowledge to satisfy both f(x) = y and sha256(x) = Y
OP_SHA256
<Y> OP_EQUAL
OP_IF
# Bob provided the preimage for Y, that preimage being the solution,
so he can spend the funds now
<Bob Pubkey>
OP_ELSE
# The challenge period ended, so Alice can reclaim her funds
<block_height+100> OP_CHECKLOCKTIMEVERIFY OP_DROP
<Alice Pubkey>
OP_ENDIF
OP_CHECKSIG
Thanks and apologies if I'm missing something obvious!,
-Dave
[1]
https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-08 12:01 ` ZmnSCPxj
@ 2022-11-10 9:42 ` Salvatore Ingala
0 siblings, 0 replies; 20+ messages in thread
From: Salvatore Ingala @ 2022-11-10 9:42 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 6693 bytes --]
Hi ZmnSCPxj, Bram, Peter, David,
Thanks for all your comments; replies below.
On Tue, 8 Nov 2022 at 13:01, ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
> Modulo bugs, operator error, misconfigurations, and other irrationalities
> of humans.
>
I agree that making footguns impossible is a much more difficult problem to
solve!
Rather than get taptree from the stack, just use the same taptree as in the
> revelation of the P2TR.
> This removes the need to include quining and similar techniques: just do
> the quining in the SCRIPT interpreter.
>
That's a possibility; I suspect it would be less efficient for many
contracts (in particular, when the total number of states in the FSM is
relatively large, but each of them has only few valid transitions). We
could always allow both variants.
Another reason I preferred to present it in this way is to show that it is
possible to limit the design to covenants where recursion is not allowed /
limited; I don't personally think recursion is bad at this time − but the
covenants (and the protocol for fraud challenges) do not require it in
order to be useful.
Anyway, I suggested some opcodes only as a sketch. I'm not knowledgeable
enough to suggest the best design, and maybe it will be easier to compare
several variants once we implement something on top.
On Wed, 9 Nov 2022 at 00:34, Bram Cohen <bram@chia•net> wrote:
> Hash chained covenants in general all have about the same plateau of
> functionality, which seems roughly reasonable to add to Bitcoin as it is
> today but suffer from being limited and hence likely only a stepping stone
> to greater functionality and unless whatever's put in now cleanly extends
> to supporting more in the future it's likely to turn into a legacy
> appendage which has to be supported. So my generic suggestion for this sort
> of thing is that it should be proposed along with a plan for how it could
> be extended to support full-blown covenants in the future.
>
I actually struggle to find constructions that are _not_ possible using
such covenants; do you have any concrete example?
That would be very interesting in order to correctly classify the
expressive power of UTXO+Script+covenants when compared to the
"Turing-complete"+stateful models.
Another probably unhelpful bit of feedback I have is that Bitcoin should
> probably be taking verkle trees seriously because those can have
> substantially lower size/cost/weight than merkle trees. That doesn't just
> apply to this proposal, but to Bitcoin in general, which doesn't seem to
> have any serious verkle tree proposals to date.
>
I am not an expert in Verkle trees, but I think the efficiency gain (if
any) is not that interesting for many of the applications I'm suggesting,
as most Merkle trees would be quite small.
Therefore, I agree with Peter that the additional complexity might not be
worth it at this time; if applications requiring large Merkle trees arise
in practice, Verkle trees could always be added in the future as an
optimization.
Moreover, Verkle trees, or even any risky/fancy cryptography, could be used
in layer-2 solutions enabled by the covenant, without impacting any funds
not locked in the covenant in case of disasters.
On Wed, 9 Nov 2022 at 13:07, Peter Todd <pete@petertodd•org> wrote:
> Particularly since even having merkle trees in Bitcoin
> is arguably a mistake: they allow for degenerate, weak, security modes
> like SPV
> that aren't clearly good for Bitcoin as a whole.
>
I disagree, as the title of this thread suggests! :)
Thanks to Merkle trees, we'll be able to keep layer 1 extremely light, so
everyone can run a full node − while all the complexity of fancy
constructions is pushed to the application layer.
On Thu, 10 Nov 2022 at 08:39, David A. Harding <dave@dtrt•org> wrote:
> > 1. Alice posts the statement “f(x) = y”.
> > 2. After a challenge period, if no challenge occurs, Alice is free to
> > continue and unlock the funds; the statement is true.
> > 3. At any time before the challenge period expires, Bob can start a
> > challenge: “actually, f(x) = z”.
>
> That looks to me very similar to Gregory Maxwell's script from[1]
>
Zero-Knowledge contingent payments do indeed solve the problem more
elegantly in the specific case where swapping Alice's knowledge for x with
a payment from Bob is the entire smart contract.
The covenant adds the ability to carry over some sort of state. For
example, imagine Alice and Bob want to play a game of chess, and the winner
takes all the money [*]. The "state" in the covenant would be the entire
chessboard, and a valid transition is a valid chess move. The covenant
enforces that the game proceeds according to the rules, by only allowing
correct updates to the "state".
Moreover, the parties participating to a covenant don't necessarily need to
be decided in advance, which is crucial for constructions like coinpool [1].
Note that no this does not require any fraud proof, as the rules of chess
are simple enough that each "transition" is a simple enough function. In
fact, many contracts might not require fraud proofs at all.
The point of the chapter on fraud proof is to prove that full generality in
expressive power (that is: any state transition you can think of) is
possible, as whenever a complex transition is required − one could instead
replace it with the optimistic protocol (Alice makes a claim,
counterparties can challenge if the claim is wrong). That allows to remove
any expensive computation from hitting the blockchain.
A particularly interesting example might be rollups (and similar
constructions). There, the 'state' represents a separate ledger, and a
transition takes the secondary ledger from a valid state to another valid
state, using a zero-knowledge proof. In validity rollups [2], the chain is
required to actually check the validity proof, which is a very expensive
operation (plus, the state-of-the-art requires additional cryptographic
assumptions in layer 1, as far as I understand). The covenant would allow
us[**] to implement optimistic rollups, where the rollup operator just
posts the new state and the proof, and other parties have time to challenge
it if the proof is wrong.
I hope this clarifies the role of fraud proofs in the construction.
Best,
Salvatore
[*] - I'm not suggesting using the bitcoin blockchain to play chess games,
but it is a convenient academic example :)
[**] - Pending someone more expert to double check that nothing is missing!
[1] - https://coinpool.dev
[2] - https://bitcoinrollups.org
[-- Attachment #2: Type: text/html, Size: 8619 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-08 9:17 [bitcoin-dev] Merkleize All The Things Salvatore Ingala
` (2 preceding siblings ...)
2022-11-10 7:39 ` David A. Harding
@ 2022-11-11 21:49 ` Antoine Riard
2022-11-12 15:04 ` Salvatore Ingala
3 siblings, 1 reply; 20+ messages in thread
From: Antoine Riard @ 2022-11-11 21:49 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 30681 bytes --]
Hi Salvatore,
Thanks for bringing forward this MATT proposal!
Here my (rough) understanding of the protocol, the participants decompose
the entire computation into a number N of steps, each assigned a tapleaf,
each computation is a triplet (state_start, operation, state_end), the
tapleaves are built into a Merkle tree, the current state of the FSM is
also encoded in the Taproot output. The Merkle tree is committed in some
Script branch where a timelock is present to guarantee challenge (e.g "f(x)
= ?" OP_CHALLENGE + 100 OP_CSV). A funding transaction is broadcast to lock
the funds, participants can leverage this funding output to play out
off-chain the computation steps. To advance the resolution, a participant
spends the funding output with a witness embedding all the computation
trace encoded as Merkle branch and prove some statement "f(x) = y". Until
the CSV expires, another participant can contest by presenting another
witness with another computation trace. What is unclear to me is how the
contract's state issued off-chain can alter the pre-committed state
transitions. I think what could gain in clarity is the translation of the
bisection protocol steps in more complete new opcodes.
Another high-level remark, even if we assume any arbitrary computation can
be encoded in a Merkle Tree, as the computation grows in complexity, the
corresponding trace also increases in (witness) space. There might be some
economic bounds on the generalized smart contracts you can engage in, as
the worst-case scenario might be beyond your fee-bumping reserves. Less
flexible, but more templated opcodes for the same use-cases might make it
more affordable. At the same time, the ability to encode any cryptosystem
as the function f sounds really interesting.
Best,
Antoine
Le mar. 8 nov. 2022 à 05:13, Salvatore Ingala via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> a écrit :
> Hi list,
>
> I have been working on some notes to describe an approach that uses
> covenants in order to enable general smart contracts in bitcoin. You can
> find them here:
>
> https://merkle.fun
>
> The approach has a number of desirable features:
>
> - small impact to layer 1;
> - not application-specific, very general;
> - it fits well into P2TR;
> - it does not require new cryptographic assumptions, nor any construction
> that has not withstood the test of time.
>
> This content was presented at the BTCAzores unconference, where it
> received the name of MATT − short for Merkleize All The Things.
> In fact, no other cryptographic primitive is required, other than Merkle
> trees.
>
> I believe this construction gets close to answering the question of how
> small a change on bitcoin's layer 1 would suffice to enable arbitrary smart
> contracts.
>
> It is not yet at the stage where a formal proposal can be made, therefore
> the proposed specs are only for illustrative purposes.
>
> The same content is reformatted below for the mailing list.
>
> Looking forward to hearing about your comments and improvements.
> Salvatore Ingala
>
>
> ==========================================
>
>
> # General smart contracts in bitcoin via covenants
>
> Covenants are UTXOs that are encumbered with restrictions on the outputs
> of the transaction spending the UTXO. More formally, we can define a
> covenant any UTXO such that at least one of its spending conditions is
> valid only if one or more of the outputs’ scriptPubKey satisfies certain
> restrictions.
>
> Generally, covenant proposals also add some form of introspection (that
> is, the ability for Script to access parts of the inputs/outputs, or the
> blockchain history).
>
> In this note, we want to explore the possibilities unleashed by the
> addition of a covenant with the following properties:
>
> - introspection limited to a single hash attached to the UTXO (the
> “covenant data”), and input/output amounts;
> - pre-commitment to every possible future script (but not their data);
> - few simple opcodes operating with the covenant data.
>
> We argue that such a simple covenant construction is enough to extend the
> power of bitcoin’s layer 1 to become a universal settlement layer for
> arbitrary computation.
>
> Moreover, the covenant can elegantly fit within P2TR transactions, without
> any substantial increase for the workload of bitcoin nodes.
>
> A preliminary version of these notes was presented and discussed at the
> BTCAzores Unconference [1], on 23rd September 2022.
>
>
> # Preliminaries
>
> We can think of a smart contract as a “program” that updates a certain
> state according to predetermined rules (which typically include access
> control by authorizing only certain public keys to perform certain
> actions), and that can possibly lock/unlock some coins of the underlying
> blockchain according to the same rules.
>
> The exact definition will be highly dependent on the properties of the
> underlying blockchain.
>
> In bitcoin, the only state upon which all the nodes reach consensus is the
> UTXO set; other blockchains might have other data structures as part of the
> consensus, like a key-value store that can be updated as a side effect of
> transaction execution.
>
> In this section we explore the following concepts in order to set the
> framework for a definition of smart contracts that fits the structure of
> bitcoin:
>
> - the contract’s state: the “memory” the smart contract operates on;
> - state transitions: the rules to update the contract’s state;
> - covenants: the technical means that can allow contracts to function in
> the context of a bitcoin UTXO.
>
> In the following, an on-chain smart contract is always represented as a
> single UTXO that implicitly embeds the contract’s state and possibly
> controls some coins that are “locked” in it. More generally, one could
> think of smart contracts that are represented in a set of multiple UTXOs;
> we leave the exploration of generalizations of the framework to future
> research.
>
> ## State
>
> Any interesting “state” of a smart contract can ultimately be encoded as a
> list, where each element is either a bit, a fixed-size integers, or an
> arbitrary byte string.
>
> Whichever the choice, it does not really affect what kinds of computations
> are expressible, as long as one is able to perform some basic computations
> on those elements.
>
> In the following, we will assume without loss of generality that
> computations happen on a state which is a list of fixed length S = [s_1,
> s_2, …, s_n], where each s_i is a byte string.
>
> ### Merkleized state
>
> By constructing a Merkle tree that has the (hashes of) the elements of S
> in the leaves, we can produce a short commitment h_S to the entire list S
> with the following properties (that hold for a verifier that only knows
> h_S):
>
> - a (log n)-sized proof can prove the value of an element s_i;
> - a (log n + |x|)-sized proof can prove the new commitment h_S’, where S’
> is a new list obtained by replacing the value of a certain leaf with x.
>
> This allows to compactly commit to a RAM, and to prove correctness of RAM
> updates.
>
> In other words, a stateful smart contract can represent an arbitrary state
> in just a single hash, for example a 32-byte SHA256 output.
>
> ### State transitions and UTXOs
>
> We can conveniently represent a smart contract as a finite state machine
> (FSM), where exactly one node can be active at a given time. Each node has
> an associated state as defined above, and a set of transition rules that
> define:
>
> - who can use the rule;
> - what is the next active node in the FSM;
> - what is the state of the next active node.
>
> It is then easy to understand how covenants can conveniently represent and
> enforce the smart contracts in this framework:
>
> - The smart contract is instantiated by creating a UTXO encumbered with a
> covenant; the smart contract is in the initial node of the FSM.
> - The UTXO’s scriptPubKey specifies the current state and the valid
> transitions.
> - The UTXO(s) produced after a valid transition might or might not be
> further encumbered, according to the rules.
>
> Therefore, what is necessary in order to enable this framework in bitcoin
> Script is a covenant that allows the enforcement of such state transitions,
> by only allowing outputs that commit to a valid next node (and
> corresponding state) in the FSM.
>
> It is not difficult to show that arbitrary computation is possible over
> the committed state, as long as relatively simple arithmetic or logical
> operations are available over the state.
>
> Remark: using an acyclic FSM does not reduce the expressivity of the smart
> contracts, as any terminating computation on bounded-size inputs which
> requires cycles can be unrolled into an acyclic one.
>
> ### Merkleized state transitions
>
> Similarly to how using Merkle trees allows to succinctly represent
> arbitrary data with a short, 32-byte long summary, the same trick allows to
> succinctly represent arbitrary state transitions (the smart contract’s
> code) with a single 32-byte hash. Each of the possible state transitions is
> encoded as a Script which is put in a leaf of a Merkle tree; the Merkle
> root of this tree is a commitment to all the possible state transitions.
> This is exactly what the taptree achieves in Taproot (see BIP-0341 [2]).
>
> Later sections in this document will suggest a possible way of how both
> the contract’s state and valid transition rules could be represented in
> UTXOs.
>
> ## On-chain computation?!
>
> Should the chain actually do computation?
>
> If naively designed, the execution of a contract might require a large
> number of transactions, which is not feasible.
>
> While the covenant approach does indeed enable a chain of transactions to
> perform arbitrary computation, simple economic considerations will push
> protocol designers to perform any non-trivial computation off-chain, and
> instead use the blockchain consensus only to verify the computation; or, if
> possible, skip the verification altogether.
>
> The fundamental fact that a blockchain’s layer 1 never actually needs to
> run complex programs in order to enable arbitrary complex smart contracting
> was observed in the past, for example in a 2016 post by Greg Maxwell [3].
>
> Vitalik Buterin popularized the concept of "functionality escape velocity"
> [4] to signify the minimum amount of functionality required on layer 1 in
> order to enable anything else to be built on top (that is, on layer 2 and
> beyond).
>
> In the following section, we will argue that a simple covenant
> construction suffices to achieve the functionality escape velocity in the
> UTXO model.
>
>
> # Commitments to computation and fraud challenges
>
> In this section, we explore how a smart contract that requires any
> non-trivial computation f : X --> Y (that is too expensive or not feasible
> with on-chain Script state transitions) can be implemented with the simple
> covenants described in the previous section.
>
> The ideas in this section appeared in literature; the reader is referred
> to the references for a more comprehensive discussion.
>
> We want to be able to build contracts that allow conditions of the type
> "f(x) = y"; yet, we do not want layer 1 to be forced to perform any
> expensive computation.
>
> In the following, we assume for simplicity that Alice and Bob are the only
> participants of the covenant, and they both locked some funds bond_A and
> bond_B (respectively) inside the covenant’s UTXO.
>
> 1. Alice posts the statement “f(x) = y”.
> 2. After a challenge period, if no challenge occurs, Alice is free to
> continue and unlock the funds; the statement is true.
> 3. At any time before the challenge period expires, Bob can start a
> challenge: “actually, f(x) = z”.
>
> In case of a challenge, Alice and Bob enter a challenge resolution
> protocol, arbitrated by layer 1; the winner takes the other party’s bond
> (details and the exact game theory vary based on the type of protocol the
> challenge is part of; choosing the right amount of bonds is crucial for
> protocol design).
>
> The remainder of this section sketches an instantiation of the challenge
> protocol.
>
> ## The bisection protocol for arbitrary computation
>
> In this section, we sketch the challenge protocol for an arbitrary
> computation f : X --> Y.
>
> ### Computation trace
>
> Given the function f, it is possible to decompose the entire computation
> in simple elementary steps, each performing a simple, atomic operation. For
> example, if the domain of x and y is that of binary strings of a fixed
> length, it is possible to create a boolean circuit that takes x and
> produces y; in practice, some form of assembly-like language operating on a
> RAM might be more efficient and fitting for bitcoin Script.
>
> In the following, we assume each elementary operation is operating on a
> RAM, encoded in the state via Merkle trees as sketched above. Therefore,
> one can represent all the steps of the computation as triples tri = (st_i,
> op_i, st_{i + 1}), where st_i is the state (e.g. a canonical Merkle tree of
> the RAM) before the i-th operation, st_{i + 1} is the state after, and op_i
> is the description of the operation (implementation-specific; it could be
> something like “add a to b and save the result in c).
>
> Finally, a Merkle tree M_T is constructed that has as leaves the values of
> the individual computation steps T = {tr_0, tr_1, …, tr_{N - 1}} if the
> computation requires N steps, producing the Merkle root h_T. The height of
> the Merkle tree is log N. Observe that each internal node commits to the
> portion of the computation trace corresponding to its own subtree.
>
> Let’s assume that the Merkle tree commitments for internal nodes are
> further augmented with the states st_{start} and st_{end}, respectively the
> state before the operation of in the leftmost leaf of the subtree, and
> after the rightmost leaf of the subtree.
>
> ### Bisection protocol
>
> The challenge protocol begins with Alice posting what she claims is the
> computation trace h_A, while Bob disagrees with the trace h_B != h_A;
> therefore, the challenge starts at the root of M_T, and proceeds in steps
> in order to find a leaf where Alice and Bob disagree (which is guaranteed
> to exist, hence the disagreement). Note that the arbitration mechanism
> knows f, x and y, but not the correct computation trace hash h_T.
>
> (Bisection phase): While the challenge is at a non-leaf node of M_T, Alice
> and Bob take turns to post the two hashes corresponding to the left and
> right child of their claimed computation trace hash; moreover, they post
> the start/end state for each child node. The protocol enforces that Alice’s
> transaction is only valid if the posted hashes h_{l; A} and h_{r; A}, and
> the declared start/end state for each child are consistent with the
> commitment in the current node.
>
> (Arbitration phase): If the protocol has reached the i-th leaf node, then
> each party reveals (st_i, op_i, st_{i + 1}); in fact, only the honest party
> will be able to reveal correct values, therefore the protocol can
> adjudicate the winner.
>
> Remark: there is definitely a lot of room for optimizations; it is left
> for future work to find the optimal variation of the approach; moreover,
> different challenge mechanisms could be more appropriate for different
> functions f.
>
> ### Game theory (or why the chain will not see any of this)
>
> With the right economic incentives, protocol designers can guarantee that
> playing a losing game always loses money compared to cooperating.
> Therefore, the challenge game is never expected to be played on-chain. The
> size of the bonds need to be appropriate to disincentivize griefing attacks.
>
> ### Implementing the bisection protocol's state transitions
>
> It is not difficult to see that the entire challenge-response protocol
> above can be implemented using the simple state transitions described above.
>
> Before a challenge begins, the state of the covenant contains the value of
> x, y and the computation trace computed by Alice. When starting the
> challenge, Bob also adds its claim for the correct computation trace, and
> the covenant enters the bisection phase.
>
> During the bisaction phase, the covenant contains the claimed computation
> trace for that node of the computation protocol, according to each party.
> In turns, each party has to reveal the corresponding computation trace for
> both the children of the current node; the transaction is only valid if the
> hash of the current node can be computed correctly from the information
> provided by each party about the child nodes. The protocol repeats on one
> of the two child nodes on whose computation trace the two parties disagree
> (which is guaranteed to exist). If a leaf of M_T is reached, the covenant
> enters the final arbitration phase.
>
> During the arbitration phase (say at the i-th leaf node of M_T), any party
> can win the challenge by providing correct values for tr_i = (st_i, op_i,
> st_{i + 1}). Crucially, only one party is able to provide correct values,
> and Script can verify that indeed the state moves from st_i to st_{i + 1}
> by executing op_i. The challenge is over.
>
> At any time, the covenant allows one player to automatically win the
> challenge after a certain timeout if the other party (who is expected to
> “make his move”) does not spend the covenant. This guarantees that the
> protocol can always find a resolution.
>
> ### Security model
>
> As for other protocols (like the lightning network), a majority of miners
> can allow a player to win a challenge by censoring the other player’s
> transactions. Therefore, the bisection protocol operates under the honest
> miner majority assumption. This is acceptable for many protocols, but it
> should certainly be taken into account during protocol design.
>
>
> # MATT covenants
>
> We argued that the key to arbitrary, fully general smart contracts in the
> UTXO model is to use Merkle trees, at different levels:
>
> 1. succinctly represent arbitrary state with a single hash. Merkleize the
> state!
> 2. succinctly represent the possible state transitions with a single hash.
> Merkleize the Script!
> 3. succinctly represent arbitrary computations with a single hash.
> Merkleize the execution!
>
> (1) and (2) alone allow contracts with arbitrary computations; (3) makes
> them scale.
>
> Merkleize All The Things!
>
> In this section we sketch a design of covenant opcodes that are
> taproot-friendly and could easily be added in a soft fork to the existing
> SegWitv1 Script.
>
> ## Embedding covenant data in P2TR outputs
>
> We can take advantage of the double-commitment structure of taproot
> outputs (that is, committing to both a public key and a Merkle tree of
> scripts) to compactly encode both the covenant and the state transition
> rules inside taproot outputs.
>
> The idea is to replace the internal pubkey Q with a key Q’ obtained by
> tweaking Q with the covenant data (the same process that is used to commit
> to the root of the taptree). More precisely, if d is the data committed to
> the covenant, the covenant-data-augmented internal key Q’ is defined as:
>
> Q’ = Q + int(hashTapCovenantData(Q || h_{data}))G
>
> where h_{data} is the sha256-hash of the covenant data. It is then easy to
> prove that the point is constructed in this way, by repeating the
> calculation.
>
> If there is no useful key path spend, similarly to what is suggested in
> BIP-0341 [5] for the case of scripts with no key path spends, we can use
> the NUMS point:
> H =
> lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0).
>
> TODO: please double check if the math above is sound.
>
> ## Changes to Script
>
> The following might be some minimal new opcodes to add for taproot
> transactions in order to enable the construction above. This is a very
> preliminary proposal, and not yet complete nor correct.
>
> - OP_SHA256CAT: returns the SHA256 hash of the concatenation of the second
> and the first (top) element of the stack. (redundant if OP_CAT is enabled,
> even just on operands with total length up to 64 bytes)
> - OP_CHECKINPUTCOVENANTVERIFY: let x, d be the two top elements of the
> stack; behave like OP_SUCCESS if any of x and d is not exactly 32 bytes;
> otherwise, check that the x is a valid x-only pubkey, and the internal
> pubkey P is indeed obtained by tweaking lift_x(x) with d.
> - OP_INSPECTNUMINPUTS, OP_INSPECTNUMOUTPUTS, OP_INSPECTINPUTVALUE and
> OP_INSPECTOUTPUTVALUE - opcodes to push number on the stack of
> inputs/outputs and their amounts.
> - OP_CHECKOUTPUTCOVENANTVERIFY: given a number out_i and three 32-byte
> hash elements x, d and taptree on top of the stack, verifies that the
> out_i-th output is a P2TR output with internal key computed as above, and
> tweaked with taptree. This is the actual covenant opcode.
>
> TODO:
>
> - Many contracts need parties to provide additional data; simply passing
> it via the witness faces the problem that it could be malleated. Therefore,
> a way of passing signed data is necessary. One way to address this problem
> could be to add a commitment to the data in the annex, and add an opcode to
> verify such commitment. Since the annex is covered by the signature, this
> removes any malleability. Another option is an OP_CHECKSIGFROMSTACK opcode,
> but that would cost an additional signature check.
> - Bitcoin numbers in current Script are not large enough for amounts.
>
> Other observations:
>
> - OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could have
> a mode where x is replaced with a NUMS pubkey, for example if the first
> operand is an empty array of bytes instead of a 32 byte pubkey; this saves
> about 31 bytes when no internal pubkey is needed (so about 62 bytes for a
> typical contract transition using both opcodes)
> - Is it worth adding other introspection opcodes, for example
> OP_INSPECTVERSION, OP_INSPECTLOCKTIME? See Liquid's Tapscript Opcodes [6].
> - Is there any malleability issue? Can covenants “run” without signatures,
> or is a signature always to be expected when using spending conditions with
> the covenant encumbrance? That might be useful in contracts where no
> signature is required to proceed with the protocol (for example, any party
> could feed valid data to the bisection protocol above).
> - Adding some additional opcodes to manipulate stack elements might also
> bring performance improvements in applications (but not strictly necessary
> for feasibility).
>
> Remark: the additional introspection opcodes available in Blockstream
> Liquid [6] do indeed seem to allow MATT covenants; in fact, the opcodes
> OP_CHECKINPUTCOVENANTVERIFY and OP_CHECKOUTPUTCOVENANTVERIFY could be
> replaced by more general opcodes like the group {OP_TWEAKVERIFY,
> OP_INSPECTINPUTSCRIPTPUBKEY, OP_PUSHCURRENTINPUTINDEX,
> OP_INSPECTOUTPUTSCRIPTPUBKEY }.
>
> ### Variant: bounded recursivity
>
> In the form described above, the covenant essentially allows fully
> recursive constructions (an arbitrary depth of the covenant execution tree
> is in practice equivalent to full recursion).
>
> If recursivity is not desired, one could modify the covenants in a way
> that only allows a limited depth: a counter could be attached to the
> covenant, with the constraint that the counter must be decreased for
> OP_CHECKOUTPUTCOVENANTVERIFY. That would still allow arbitrary fraud proofs
> as long as the maximum depth is sufficient.
>
> However, that would likely reduce its utility and prevent certain
> applications where recursivity seems to be a requirement.
>
> The full exploration of the design space is left for future research.
>
>
> # Applications
>
> This section explores some of the potential use cases of the techniques
> presented above. The list is not exhaustive.
>
> Given the generality of fraud proofs, some variant of every kind of smart
> contracts or layer two construction should be possible with MATT covenants,
> although the additional requirements (for example the capital lockup and
> the challenge period delays) needs to be accurately considered; further
> research is necessary to assess for what applications the tradeoffs are
> acceptable.
>
> ## State channels
>
> A state channel is a generalization of a payment channel where,
> additionally to the balance at the end of each channel, some additional
> state is stored. The state channel also specifies what are the rules on how
> to update the channel’s state.
>
> For example, two people might play a chess game, where the state encodes
> the current configuration of the board. The valid state transitions
> correspond to the valid moves; and, once the game is over, the winner takes
> a specified amount of the channel’s money.
>
> With eltoo-style updates, such a game could be played entirely off-chain,
> as long as both parties are cooperating (by signing the opponent’s state
> update).
>
> The role of the blockchain is to guarantee that the game can be moved
> forward and eventually terminated in case the other party does not
> cooperate.
>
> In stateful blockchain, this is simply achieved by publishing the latest
> state (Merkleized or not) and then continuing the entire game on-chain.
> This is expensive, especially if the state transitions require some complex
> computation.
>
> An alternative that avoids moving computations on-chain is the use of a
> challenge-response protocol, as sketched above.
>
> Similarly to the security model of lightning channels, an honest party can
> always win a challenge under the honest-majority of miners. Therefore, it
> is game-theoretically losing to attempt cheating in a channel.
>
> ## CoinPool
>
> Multiparty state channels are possible as well; therefore, constructions
> like CoinPool [7] should be possible, enabling multiple parties to share a
> single UTXO.
>
> ## Zero knowledge proofs in L2 protocols
>
> Protocols based on ZK-proofs require the blockchain to be the verifier;
> the verifier is a function that takes a zero-knowledge proof and returns
> true/false based on its correctness.
>
> Instead of an OP_STARK operator in L1, one could think of compiling the
> OP_STARK as the function f in the protocol above.
>
> Note that covenants with a bounded “recursion depth” are sufficient to
> express OP_STARK, which in turns imply the ability to express arbitrary
> functions within contracts using the challenge protocol.
>
> One advantage of this approach is that no new cryptographic assumptions
> are added to bitcoin’s layer 1 even if OP_STARK does require it; moreover,
> if a different or better OP_STARK2 is discovered, the innovation can reach
> layer 2 contracts without any change needed in layer 1.
>
> ## Optimistic rollups
>
> John Light recently posted a research report on how Validity Rollups could
> be added to bitcoin’s layer 1 [8]. While no exact proposal is pushed
> forward, the suggested changes required might include a combination of
> recursive covenants, and specific opcodes for validity proof verification.
>
> Fraud proofs are the core for optimistic rollups; exploring the
> possibility of implementing optimistic rollups with MATT covenants seems a
> promising direction. Because of the simplicity of the required changes to
> Script, this might answer some of the costs and risks analyzed in the
> report, while providing many of the same benefits. Notably, no novel
> cryptography needs to become part of bitcoin’s layer 1.
>
> Optimistic Rollups would probably require a fully recursive version of the
> covenant (while fraud proofs alone are possible with a limited recursion
> depth).
>
>
> # Acknowledgments
>
> Antoine Poinsot suggested an improvement to the original proposed covenant
> opcodes, which were limited to taproot outputs without a valid key-path
> spend.
>
> The author would also like to thank catenocrypt, Antoine Riard, Ruben
> Somsen and the participants of the BTCAzores unconference for many useful
> discussions and comments on early versions of this proposal.
>
>
> # References
>
> The core idea of the bisection protocol appears to have been independently
> rediscovered multiple times. In blockchain research, it is at the core of
> fraud proof constructions with similar purposes, although not focusing on
> bitcoin or covenants; see for example:
>
> - Harry Kalodner et al. “Arbitrum: Scalable, private smart contracts.” −
> 27th USENIX Security Symposium. 2018.
> https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf
> - Jason Teutsch and Christian Reitwiessner. “A scalable verification
> solution for blockchains” − TrueBit protocol. 2017.
> https://people.cs.uchicago.edu/~teutsch/papers/truebit.pdf
>
> The same basic idea was already published prior to blockchain use cases;
> see for example:
>
> Ran Canetti, Ben Riva, and Guy N. Rothblum. “Practical delegation of
> computation using multiple servers.” − Proceedings of the 18th ACM
> conference on Computer and communications security. 2011. http://diyhpl.us/~bryan/papers2/bitcoin/Practical%20delegation%20of%20computation%20using%20multiple%20servers.pdf
>
>
>
> # Footnotes
>
> [1] - https://btcazores.com
> [2] - https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
> [3] -
> https://bitcointalk.org/index.php?topic=1427885.msg14601127#msg14601127
> [4] - https://vitalik.ca/general/2019/12/26/mvb.html
> [5] -
> https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#constructing-and-spending-taproot-outputs
> [6] -
> https://github.com/ElementsProject/elements/blob/master/doc/tapscript_opcodes.md
> [7] - https://coinpool.dev/v0.1.pdf
> [8] - https://bitcoinrollups.org
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 31719 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-11 21:49 ` Antoine Riard
@ 2022-11-12 15:04 ` Salvatore Ingala
2022-11-30 19:42 ` Rijndael
0 siblings, 1 reply; 20+ messages in thread
From: Salvatore Ingala @ 2022-11-12 15:04 UTC (permalink / raw)
To: Antoine Riard; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 9165 bytes --]
Hi Antoine,
It appears that my explanation of the relationship between the covenant and
the bisection protocol is still unclear; I'll do my best to clarify.
The bisection's Merkle tree never ends up on-chain, in any form. Therefore,
a bigger computation does not end up in a bigger witness size, which is key
to the scalability of the approach. Only in the case of a challenge, it
will result in a (logarithmically) longer chain of transactions to resolve
it. This chain of transactions could be mapped to a root-to-leaf path in
the Merkle tree of the computation trace.
The actual computation trace (and the corresponding Merkle tree) is only
computed by the parties when they execute the computation.
What's in the tapleaves is only the valid transitions at the current state
of the protocol; that is, the valid transitions in the Finite State Machine
(and possibly other valid exit conditions that remove the covenant
encumbrance, if any).
The bisection protocol only makes sense as a step in a larger protocol that
makes use of it.
Perhaps presenting the protocol in a less-than-general case might help to
understand it. So let's play a simpler game using a protocol that includes
a fraud proof.
Alice claims that she knows how to multiply by 256, while Bob doesn't
believe her. So they make a bet: they each commit 1 coin; then Bob choses a
number x; then Alice computes y = 256*x by doubling x eight times
(expensive multiplications were disabled in a tragic DDoS accident), and
publishes the result y. Bob independently computes 256 * x (he has a friend
who is a mathematician, he'll know how to do it). If the result is not y,
Bob will start a challenge; otherwise, Alice wins and takes the money.
(The example is of course artificial, as redoing the computation in Script
is cheaper than executing the fraud proof in this case!)
What follows is an actual execution of the protocol. In the following, each
[Si] is a UTXO corresponding to some possible FSM node, starting with the
S0, the UTXO with 1+1 = 2 coins. Each line with "-" is a possible
transition (script in the taptree), specifying what is the next FSM node
after the "==>" symbol; the encumbrance in the scripts enforce that the
state of the next UTXO is updated correctly (details omitted below), and
any other necessary conditions to ensure the integrity of the protocol.
=====
[S0]: Initial UTXO
- only Bob can spend, he must choose his number x ==> S1
[S1; state: x]:
- only Alice can spend, she publishes her answer y ==> S2
[S2. state: x, y]:
- after 1 day: Alice won, she can take the money // Happy case!
Usually that's the end
- Bob disagrees with the answer, post z as his answer. ==> S3
The challenge starts here! Let's put some actual numbers. x = 2; y = 508; z
= 512.
This is what Alice computed:
2 => 4 => 8 => 16 => 32 => 64 => 127 => 254 => 508
This is what Bob computed:
2 => 4 => 8 => 16 => 32 => 64 => 128 => 256 => 512
At this time, we don't know who is right. They both built a tree that looks
like this (ASCII art only working in fixed-width font):
___H18___
/ \
/ \
H14 H58
/ \ / \
/ \ / \
/ \ / \
H12 H34 H56 H78
/ \ / \ / \ / \
H1 H2 H3 H4 H5 H6 H7 H8
Remember that each internal node commits to: the state of the computation
before the leftmost leaf in the subtree, the state after the rightmost
leaf, and the hash of sub-trace for the sub-tree. Each leaf just commits to
that intermediate computation step (and the operation, which here is always
"double the input"). For example, H4 commits to "16 => 32" according to
both Alice's and Bob's computation traces.
(From our privileged point of view, we can foresee that the earliest
disagreement is on the 6th step of the computation: "64 => 127" according
to Alice, "64 => 128" according to Bob).
Let's denote h_{A;18} (resp. h_{B;18}) all the information committed to in
the node H18, according to Alice (resp. Bob). Similarly for all the other
nodes.
[S3. state: x, y, z]: Challenge starts!
- Alice posts the root of her computation trace h_{A;18} ==> S4
[S4. state: x, y, z, h_{A;18}]
- Bob posts the root of her computation trace h_{B;18} ==> S5
Since they disagree, it must be the case that h_{A;18} != h_{B;18}.
[S5. state: x, y, z, h_{A;18}, h_{B;18}]
- Alice opens the commitment h_{A;18}, by revealing H14 and H58
(according to her) ==> S6
Note that in this last transition (going to S6), the covenant enforces that
the child commitments are compatible: the transition is only valid if the
starting state of the computation according to h_{A;14} is compatible with
h_{A;18} (that is, it's equal to x); similarly the end state of the
computation in h_{A;58} must be y, and h_{A;18} can be recomputed from the
data provided (ensuring the integrity of the Merkle tree).
This is true for all the commitment openings below.
[S6. state: x, y, z, (h_{A;14}, h_{A;58}), h_{B;18}]
- Bob opens the commitment h_{B;18}, by revealing H14 and H58 (according
to him) ==> S7
[S7. state: x, y, z, (h_{A;18}, h_{A;14}, h_{A;58}), (h_{B;18}, h_{B;14},
h_{B;58})]
// We now need to choose a child where there is disagreement.
// If both children don't match, iterate on the left child.
- Anyone: if h_{A;14} == h_{B;14} ==> S8
- Anyone: if h_{A;14} != h_{B;14} ==> Continue challenge on H14 //
Non-executed FSM cases omitted for brevity
At this point, the disagreement over the root is settled: Alice and Bob
agree on the first half of the computation, but they disagree over the
second half. Therefore, in S8 the protocol continues over H58.
[S8. state: h_{A;58}, h_{B;58}]
// This is analogous to S5, just with half of the computation steps.
- Alice opens the commitment h_{A;58}, by revealing H56 and H78
(according to her) ==> S9
[S9. state: (h_{A;56}, h_{A;78}), h_{B;58}]
- Bob opens the commitment h_{B;58}, by revealing H56 and H78 (according
to him) ==> S10
[S10. state: (h_{A;56}, h_{A;78}), (h_{B;56}, h_{B;78})]
// Like S7, iterate on a disagreeing child
- Anyone: if h_{A;56} == h_{B;56} ==> continue challenge on H78 //
Non-executed FSM cases omitted for brevity
- Anyone: if h_{A;56} != h_{B;56} ==> S11
Getting there! The subtree now commits to just two computation steps.
[S11. state: h_{A;56}, h_{B;56}]
// This is analogous to S5 and S8.
- Alice opens the commitment h_{A;56}, by revealing H5 and H6 (according
to her) ==> S12
[S12. state: (h_{A;5}, h_{A;6}), h_{B;56}]
- Bob opens the commitment h_{B;56}, by revealing H5 and H6 (according to
him) ==> S13
[S13. state: (h_{A;5}, h_{A;6}), (h_{B;5}, h_{B;6})]
// Like S7 and S10, iterate on a disagreeing child
- Anyone: if h_{A;5} == h_{B;5} ==> S14
- Anyone: if h_{A;5} != h_{B;5} ==> continue challenge on H5 //
Non-executed FSM cases omitted for brevity
We are now at the crucial stage: the commitment corresponds to a leaf of
the computation trace Merkle tree.
[S14. state: h_{A;6}, h_{B;6}]
- Alice can take all the money if she can open h_{A;6} to a correct "n =>
n + n" computation step
- Bob can take all the money if he can open h_{B;6} to a correct "n => n
+ n" computation step
The challenge now ends quickly: Bob's hash commits to the computation step
"64 => 128".
Instead, Alice's step is the incorrect "64 => 127".
It's not difficult to convince oneself that, as long as the hash function
is collision-free and the computation is deterministic, only the honest
party can provide correct data for this final step.
(The bisection protocol can't do anything useful if both parties provide
incorrect data; arguably, that is not a very interesting scenario!)
Crucially, the operation in the single step is so simple that Script can
verify it.
=====
If you read until here: thank you, this was the first execution of a
challenge in MATT covenants!
Of course, there are a few things missing in the above protocol:
- Bonds should be added in order to incentivize cooperation.
- The omitted FSM steps (corresponding to branches of the challenge that
were never taken) need to be computed nonetheless when preparing the
covenant.
- Additional transitions should be added at every step (always allow
cooperative behavior; forfait after a timeout if it's the other party's
turn).
- Some of those consecutive "forced" steps can be contracted in a single
step; I felt this sequence is more logical to explain the protocol, but
implementations would want to optimize it.
Yet, _all_ the code and scripts of the bisection protocol are independent
of the actual execution, and can be precomputed (bottom up, starting from
the leaves) before the initial covenant is created - therefore, before x, y
and z are chosen and committed to.
While here each leaf is doing the same operation (doubling a number), it is
well-known that arbitrary computation can be decomposed in very simple
elementary functions (like NAND gates, if we want to be minimalistic).
I hope this helps in clarifying the role of the bisection protocol in smart
contracts using MATT covenants.
Best,
Salvatore
[-- Attachment #2: Type: text/html, Size: 10359 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-12 15:04 ` Salvatore Ingala
@ 2022-11-30 19:42 ` Rijndael
2022-11-30 22:09 ` Rijndael
0 siblings, 1 reply; 20+ messages in thread
From: Rijndael @ 2022-11-30 19:42 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion, Antoine Riard
[-- Attachment #1: Type: text/plain, Size: 10154 bytes --]
Hello Salvatore,
Really interesting idea. The walk-through of the challenge protocol helped.
In the final state:
[S14. state: h_{A;6}, h_{B;6}]
- Alice can take all the money if she can open h_{A;6} to a correct "n => n + n" computation step
- Bob can take all the money if he can open h_{B;6} to a correct "n => n + n" computation step
My understanding of your scheme for encoding execution traces is that each leaf is (previous-state, operation, post-state) So in this case when we get to the conflicting step of the execution traces, alice might reveal something like (x=64, x+x, x=127) and bob might reveal something like (x=64, x+x, x=128). So in order for the covenant to enforce which state-transition is valid (who can spend the money), that means that `x+x` needs to be evaluated in script to tell who has posted the incorrect state. Am I understanding this final step of the bisection protocol correctly?
-rijndael
On 11/12/22 10:04 AM, Salvatore Ingala via bitcoin-dev wrote:
> Hi Antoine,
> It appears that my explanation of the relationship between the covenant and the bisection protocol is still unclear; I'll do my best to clarify.
>
> The bisection's Merkle tree never ends up on-chain, in any form. Therefore, a bigger computation does not end up in a bigger witness size, which is key to the scalability of the approach. Only in the case of a challenge, it will result in a (logarithmically) longer chain of transactions to resolve it. This chain of transactions could be mapped to a root-to-leaf path in the Merkle tree of the computation trace.
>
> The actual computation trace (and the corresponding Merkle tree) is only computed by the parties when they execute the computation.
> What's in the tapleaves is only the valid transitions at the current state of the protocol; that is, the valid transitions in the Finite State Machine (and possibly other valid exit conditions that remove the covenant encumbrance, if any).
>
> The bisection protocol only makes sense as a step in a larger protocol that makes use of it.
>
> Perhaps presenting the protocol in a less-than-general case might help to understand it. So let's play a simpler game using a protocol that includes a fraud proof.
>
> Alice claims that she knows how to multiply by 256, while Bob doesn't believe her. So they make a bet: they each commit 1 coin; then Bob choses a number x; then Alice computes y = 256*x by doubling x eight times (expensive multiplications were disabled in a tragic DDoS accident), and publishes the result y. Bob independently computes 256 * x (he has a friend who is a mathematician, he'll know how to do it). If the result is not y, Bob will start a challenge; otherwise, Alice wins and takes the money.
>
> (The example is of course artificial, as redoing the computation in Script is cheaper than executing the fraud proof in this case!)
>
> What follows is an actual execution of the protocol. In the following, each [Si] is a UTXO corresponding to some possible FSM node, starting with the S0, the UTXO with 1+1 = 2 coins. Each line with "-" is a possible transition (script in the taptree), specifying what is the next FSM node after the "==>" symbol; the encumbrance in the scripts enforce that the state of the next UTXO is updated correctly (details omitted below), and any other necessary conditions to ensure the integrity of the protocol.
>
> =====
>
> [S0]: Initial UTXO
> - only Bob can spend, he must choose his number x ==> S1
>
> [S1; state: x]:
> - only Alice can spend, she publishes her answer y ==> S2
>
> [S2. state: x, y]:
> - after 1 day: Alice won, she can take the money // Happy case! Usually that's the end
> - Bob disagrees with the answer, post z as his answer. ==> S3
>
> The challenge starts here! Let's put some actual numbers. x = 2; y = 508; z = 512.
>
> This is what Alice computed:
>
> 2 => 4 => 8 => 16 => 32 => 64 => 127 => 254 => 508
>
> This is what Bob computed:
>
> 2 => 4 => 8 => 16 => 32 => 64 => 128 => 256 => 512
>
> At this time, we don't know who is right. They both built a tree that looks like this (ASCII art only working in fixed-width font):
>
> ___H18___
> / \
> / \
> H14 H58
> / \ / \
> / \ / \
> / \ / \
> H12 H34 H56 H78
> / \ / \ / \ / \
> H1 H2 H3 H4 H5 H6 H7 H8
>
> Remember that each internal node commits to: the state of the computation before the leftmost leaf in the subtree, the state after the rightmost leaf, and the hash of sub-trace for the sub-tree. Each leaf just commits to that intermediate computation step (and the operation, which here is always "double the input"). For example, H4 commits to "16 => 32" according to both Alice's and Bob's computation traces.
>
> (From our privileged point of view, we can foresee that the earliest disagreement is on the 6th step of the computation: "64 => 127" according to Alice, "64 => 128" according to Bob).
>
> Let's denote h_{A;18} (resp. h_{B;18}) all the information committed to in the node H18, according to Alice (resp. Bob). Similarly for all the other nodes.
>
> [S3. state: x, y, z]: Challenge starts!
> - Alice posts the root of her computation trace h_{A;18} ==> S4
>
> [S4. state: x, y, z, h_{A;18}]
> - Bob posts the root of her computation trace h_{B;18} ==> S5
>
> Since they disagree, it must be the case that h_{A;18} != h_{B;18}.
>
> [S5. state: x, y, z, h_{A;18}, h_{B;18}]
> - Alice opens the commitment h_{A;18}, by revealing H14 and H58 (according to her) ==> S6
>
> Note that in this last transition (going to S6), the covenant enforces that the child commitments are compatible: the transition is only valid if the starting state of the computation according to h_{A;14} is compatible with h_{A;18} (that is, it's equal to x); similarly the end state of the computation in h_{A;58} must be y, and h_{A;18} can be recomputed from the data provided (ensuring the integrity of the Merkle tree).
> This is true for all the commitment openings below.
>
> [S6. state: x, y, z, (h_{A;14}, h_{A;58}), h_{B;18}]
> - Bob opens the commitment h_{B;18}, by revealing H14 and H58 (according to him) ==> S7
>
> [S7. state: x, y, z, (h_{A;18}, h_{A;14}, h_{A;58}), (h_{B;18}, h_{B;14}, h_{B;58})]
> // We now need to choose a child where there is disagreement.
> // If both children don't match, iterate on the left child.
> - Anyone: if h_{A;14} == h_{B;14} ==> S8
> - Anyone: if h_{A;14} != h_{B;14} ==> Continue challenge on H14 // Non-executed FSM cases omitted for brevity
>
> At this point, the disagreement over the root is settled: Alice and Bob agree on the first half of the computation, but they disagree over the second half. Therefore, in S8 the protocol continues over H58.
>
> [S8. state: h_{A;58}, h_{B;58}]
> // This is analogous to S5, just with half of the computation steps.
> - Alice opens the commitment h_{A;58}, by revealing H56 and H78 (according to her) ==> S9
>
> [S9. state: (h_{A;56}, h_{A;78}), h_{B;58}]
> - Bob opens the commitment h_{B;58}, by revealing H56 and H78 (according to him) ==> S10
>
> [S10. state: (h_{A;56}, h_{A;78}), (h_{B;56}, h_{B;78})]
> // Like S7, iterate on a disagreeing child
> - Anyone: if h_{A;56} == h_{B;56} ==> continue challenge on H78 // Non-executed FSM cases omitted for brevity
> - Anyone: if h_{A;56} != h_{B;56} ==> S11
>
> Getting there! The subtree now commits to just two computation steps.
>
> [S11. state: h_{A;56}, h_{B;56}]
> // This is analogous to S5 and S8.
> - Alice opens the commitment h_{A;56}, by revealing H5 and H6 (according to her) ==> S12
>
> [S12. state: (h_{A;5}, h_{A;6}), h_{B;56}]
> - Bob opens the commitment h_{B;56}, by revealing H5 and H6 (according to him) ==> S13
>
> [S13. state: (h_{A;5}, h_{A;6}), (h_{B;5}, h_{B;6})]
> // Like S7 and S10, iterate on a disagreeing child
> - Anyone: if h_{A;5} == h_{B;5} ==> S14
> - Anyone: if h_{A;5} != h_{B;5} ==> continue challenge on H5 // Non-executed FSM cases omitted for brevity
>
> We are now at the crucial stage: the commitment corresponds to a leaf of the computation trace Merkle tree.
>
> [S14. state: h_{A;6}, h_{B;6}]
> - Alice can take all the money if she can open h_{A;6} to a correct "n => n + n" computation step
> - Bob can take all the money if he can open h_{B;6} to a correct "n => n + n" computation step
>
> The challenge now ends quickly: Bob's hash commits to the computation step "64 => 128".
> Instead, Alice's step is the incorrect "64 => 127".
>
> It's not difficult to convince oneself that, as long as the hash function is collision-free and the computation is deterministic, only the honest party can provide correct data for this final step.
> (The bisection protocol can't do anything useful if both parties provide incorrect data; arguably, that is not a very interesting scenario!)
>
> Crucially, the operation in the single step is so simple that Script can verify it.
>
> =====
>
> If you read until here: thank you, this was the first execution of a challenge in MATT covenants!
>
> Of course, there are a few things missing in the above protocol:
> - Bonds should be added in order to incentivize cooperation.
> - The omitted FSM steps (corresponding to branches of the challenge that were never taken) need to be computed nonetheless when preparing the covenant.
> - Additional transitions should be added at every step (always allow cooperative behavior; forfait after a timeout if it's the other party's turn).
> - Some of those consecutive "forced" steps can be contracted in a single step; I felt this sequence is more logical to explain the protocol, but implementations would want to optimize it.
>
> Yet, _all_ the code and scripts of the bisection protocol are independent of the actual execution, and can be precomputed (bottom up, starting from the leaves) before the initial covenant is created - therefore, before x, y and z are chosen and committed to.
>
> While here each leaf is doing the same operation (doubling a number), it is well-known that arbitrary computation can be decomposed in very simple elementary functions (like NAND gates, if we want to be minimalistic).
>
> I hope this helps in clarifying the role of the bisection protocol in smart contracts using MATT covenants.
>
> Best,
> Salvatore
[-- Attachment #2: Type: text/html, Size: 15159 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-30 19:42 ` Rijndael
@ 2022-11-30 22:09 ` Rijndael
2022-12-01 8:47 ` Salvatore Ingala
0 siblings, 1 reply; 20+ messages in thread
From: Rijndael @ 2022-11-30 22:09 UTC (permalink / raw)
To: Bitcoin Protocol Discussion, Salvatore Ingala, Antoine Riard
[-- Attachment #1: Type: text/plain, Size: 11781 bytes --]
Hello Salvatore,
I found my answer re-reading your original post:
> During the arbitration phase (say at the i-th leaf node of M_T), any party can win the challenge by providing correct values for tr_i = (st_i, op_i, st_{i + 1}). Crucially, only one party is able to provide correct values, and Script can verify that indeed the state moves from st_i to st_{i + 1} by executing op_i. The challenge is over.
That raises leads to a different question: Alice initially posts a commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees with `y` so starts the challenge protocol. Is there a commitment to `f`? In other words, the dispute protocol (as I read it) finds the leftmost step in Alice and Bob's execution traces that differ, and then rewards the coins to the participant who's "after-value" is computed by the step's operation applied to the "before value". But if the participants each present valid steps but with different operations, who wins? In other words, Alice could present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65]. Those steps don't match, but both are valid. Is there something to ensure that before the challenge protocol starts, that the execution trace that Alice posts is for the right computation and not a different computation that yields a favorable result for her (and for which she can generate a valid merkle tree)?
Thanks!
-rijndael
On 11/30/22 2:42 PM, Rijndael via bitcoin-dev wrote:
> Hello Salvatore,
>
> Really interesting idea. The walk-through of the challenge protocol helped.
>
> In the final state:
>
> [S14. state: h_{A;6}, h_{B;6}]
> - Alice can take all the money if she can open h_{A;6} to a correct "n => n + n" computation step
> - Bob can take all the money if he can open h_{B;6} to a correct "n => n + n" computation step
>
> My understanding of your scheme for encoding execution traces is that each leaf is (previous-state, operation, post-state) So in this case when we get to the conflicting step of the execution traces, alice might reveal something like (x=64, x+x, x=127) and bob might reveal something like (x=64, x+x, x=128). So in order for the covenant to enforce which state-transition is valid (who can spend the money), that means that `x+x` needs to be evaluated in script to tell who has posted the incorrect state. Am I understanding this final step of the bisection protocol correctly?
>
> -rijndael
>
> On 11/12/22 10:04 AM, Salvatore Ingala via bitcoin-dev wrote:
>
>> Hi Antoine,
>> It appears that my explanation of the relationship between the covenant and the bisection protocol is still unclear; I'll do my best to clarify.
>>
>> The bisection's Merkle tree never ends up on-chain, in any form. Therefore, a bigger computation does not end up in a bigger witness size, which is key to the scalability of the approach. Only in the case of a challenge, it will result in a (logarithmically) longer chain of transactions to resolve it. This chain of transactions could be mapped to a root-to-leaf path in the Merkle tree of the computation trace.
>>
>> The actual computation trace (and the corresponding Merkle tree) is only computed by the parties when they execute the computation.
>> What's in the tapleaves is only the valid transitions at the current state of the protocol; that is, the valid transitions in the Finite State Machine (and possibly other valid exit conditions that remove the covenant encumbrance, if any).
>>
>> The bisection protocol only makes sense as a step in a larger protocol that makes use of it.
>>
>> Perhaps presenting the protocol in a less-than-general case might help to understand it. So let's play a simpler game using a protocol that includes a fraud proof.
>>
>> Alice claims that she knows how to multiply by 256, while Bob doesn't believe her. So they make a bet: they each commit 1 coin; then Bob choses a number x; then Alice computes y = 256*x by doubling x eight times (expensive multiplications were disabled in a tragic DDoS accident), and publishes the result y. Bob independently computes 256 * x (he has a friend who is a mathematician, he'll know how to do it). If the result is not y, Bob will start a challenge; otherwise, Alice wins and takes the money.
>>
>> (The example is of course artificial, as redoing the computation in Script is cheaper than executing the fraud proof in this case!)
>>
>> What follows is an actual execution of the protocol. In the following, each [Si] is a UTXO corresponding to some possible FSM node, starting with the S0, the UTXO with 1+1 = 2 coins. Each line with "-" is a possible transition (script in the taptree), specifying what is the next FSM node after the "==>" symbol; the encumbrance in the scripts enforce that the state of the next UTXO is updated correctly (details omitted below), and any other necessary conditions to ensure the integrity of the protocol.
>>
>> =====
>>
>> [S0]: Initial UTXO
>> - only Bob can spend, he must choose his number x ==> S1
>>
>> [S1; state: x]:
>> - only Alice can spend, she publishes her answer y ==> S2
>>
>> [S2. state: x, y]:
>> - after 1 day: Alice won, she can take the money // Happy case! Usually that's the end
>> - Bob disagrees with the answer, post z as his answer. ==> S3
>>
>> The challenge starts here! Let's put some actual numbers. x = 2; y = 508; z = 512.
>>
>> This is what Alice computed:
>>
>> 2 => 4 => 8 => 16 => 32 => 64 => 127 => 254 => 508
>>
>> This is what Bob computed:
>>
>> 2 => 4 => 8 => 16 => 32 => 64 => 128 => 256 => 512
>>
>> At this time, we don't know who is right. They both built a tree that looks like this (ASCII art only working in fixed-width font):
>>
>> ___H18___
>> / \
>> / \
>> H14 H58
>> / \ / \
>> / \ / \
>> / \ / \
>> H12 H34 H56 H78
>> / \ / \ / \ / \
>> H1 H2 H3 H4 H5 H6 H7 H8
>>
>> Remember that each internal node commits to: the state of the computation before the leftmost leaf in the subtree, the state after the rightmost leaf, and the hash of sub-trace for the sub-tree. Each leaf just commits to that intermediate computation step (and the operation, which here is always "double the input"). For example, H4 commits to "16 => 32" according to both Alice's and Bob's computation traces.
>>
>> (From our privileged point of view, we can foresee that the earliest disagreement is on the 6th step of the computation: "64 => 127" according to Alice, "64 => 128" according to Bob).
>>
>> Let's denote h_{A;18} (resp. h_{B;18}) all the information committed to in the node H18, according to Alice (resp. Bob). Similarly for all the other nodes.
>>
>> [S3. state: x, y, z]: Challenge starts!
>> - Alice posts the root of her computation trace h_{A;18} ==> S4
>>
>> [S4. state: x, y, z, h_{A;18}]
>> - Bob posts the root of her computation trace h_{B;18} ==> S5
>>
>> Since they disagree, it must be the case that h_{A;18} != h_{B;18}.
>>
>> [S5. state: x, y, z, h_{A;18}, h_{B;18}]
>> - Alice opens the commitment h_{A;18}, by revealing H14 and H58 (according to her) ==> S6
>>
>> Note that in this last transition (going to S6), the covenant enforces that the child commitments are compatible: the transition is only valid if the starting state of the computation according to h_{A;14} is compatible with h_{A;18} (that is, it's equal to x); similarly the end state of the computation in h_{A;58} must be y, and h_{A;18} can be recomputed from the data provided (ensuring the integrity of the Merkle tree).
>> This is true for all the commitment openings below.
>>
>> [S6. state: x, y, z, (h_{A;14}, h_{A;58}), h_{B;18}]
>> - Bob opens the commitment h_{B;18}, by revealing H14 and H58 (according to him) ==> S7
>>
>> [S7. state: x, y, z, (h_{A;18}, h_{A;14}, h_{A;58}), (h_{B;18}, h_{B;14}, h_{B;58})]
>> // We now need to choose a child where there is disagreement.
>> // If both children don't match, iterate on the left child.
>> - Anyone: if h_{A;14} == h_{B;14} ==> S8
>> - Anyone: if h_{A;14} != h_{B;14} ==> Continue challenge on H14 // Non-executed FSM cases omitted for brevity
>>
>> At this point, the disagreement over the root is settled: Alice and Bob agree on the first half of the computation, but they disagree over the second half. Therefore, in S8 the protocol continues over H58.
>>
>> [S8. state: h_{A;58}, h_{B;58}]
>> // This is analogous to S5, just with half of the computation steps.
>> - Alice opens the commitment h_{A;58}, by revealing H56 and H78 (according to her) ==> S9
>>
>> [S9. state: (h_{A;56}, h_{A;78}), h_{B;58}]
>> - Bob opens the commitment h_{B;58}, by revealing H56 and H78 (according to him) ==> S10
>>
>> [S10. state: (h_{A;56}, h_{A;78}), (h_{B;56}, h_{B;78})]
>> // Like S7, iterate on a disagreeing child
>> - Anyone: if h_{A;56} == h_{B;56} ==> continue challenge on H78 // Non-executed FSM cases omitted for brevity
>> - Anyone: if h_{A;56} != h_{B;56} ==> S11
>>
>> Getting there! The subtree now commits to just two computation steps.
>>
>> [S11. state: h_{A;56}, h_{B;56}]
>> // This is analogous to S5 and S8.
>> - Alice opens the commitment h_{A;56}, by revealing H5 and H6 (according to her) ==> S12
>>
>> [S12. state: (h_{A;5}, h_{A;6}), h_{B;56}]
>> - Bob opens the commitment h_{B;56}, by revealing H5 and H6 (according to him) ==> S13
>>
>> [S13. state: (h_{A;5}, h_{A;6}), (h_{B;5}, h_{B;6})]
>> // Like S7 and S10, iterate on a disagreeing child
>> - Anyone: if h_{A;5} == h_{B;5} ==> S14
>> - Anyone: if h_{A;5} != h_{B;5} ==> continue challenge on H5 // Non-executed FSM cases omitted for brevity
>>
>> We are now at the crucial stage: the commitment corresponds to a leaf of the computation trace Merkle tree.
>>
>> [S14. state: h_{A;6}, h_{B;6}]
>> - Alice can take all the money if she can open h_{A;6} to a correct "n => n + n" computation step
>> - Bob can take all the money if he can open h_{B;6} to a correct "n => n + n" computation step
>>
>> The challenge now ends quickly: Bob's hash commits to the computation step "64 => 128".
>> Instead, Alice's step is the incorrect "64 => 127".
>>
>> It's not difficult to convince oneself that, as long as the hash function is collision-free and the computation is deterministic, only the honest party can provide correct data for this final step.
>> (The bisection protocol can't do anything useful if both parties provide incorrect data; arguably, that is not a very interesting scenario!)
>>
>> Crucially, the operation in the single step is so simple that Script can verify it.
>>
>> =====
>>
>> If you read until here: thank you, this was the first execution of a challenge in MATT covenants!
>>
>> Of course, there are a few things missing in the above protocol:
>> - Bonds should be added in order to incentivize cooperation.
>> - The omitted FSM steps (corresponding to branches of the challenge that were never taken) need to be computed nonetheless when preparing the covenant.
>> - Additional transitions should be added at every step (always allow cooperative behavior; forfait after a timeout if it's the other party's turn).
>> - Some of those consecutive "forced" steps can be contracted in a single step; I felt this sequence is more logical to explain the protocol, but implementations would want to optimize it.
>>
>> Yet, _all_ the code and scripts of the bisection protocol are independent of the actual execution, and can be precomputed (bottom up, starting from the leaves) before the initial covenant is created - therefore, before x, y and z are chosen and committed to.
>>
>> While here each leaf is doing the same operation (doubling a number), it is well-known that arbitrary computation can be decomposed in very simple elementary functions (like NAND gates, if we want to be minimalistic).
>>
>> I hope this helps in clarifying the role of the bisection protocol in smart contracts using MATT covenants.
>>
>> Best,
>> Salvatore
[-- Attachment #2: Type: text/html, Size: 17806 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-11-30 22:09 ` Rijndael
@ 2022-12-01 8:47 ` Salvatore Ingala
2022-12-13 6:59 ` Billy Tetrud
0 siblings, 1 reply; 20+ messages in thread
From: Salvatore Ingala @ 2022-12-01 8:47 UTC (permalink / raw)
To: Bitcoin Protocol Discussion, Rijndael
[-- Attachment #1: Type: text/plain, Size: 4652 bytes --]
Hello Rijndael,
On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail•com> wrote:
> Hello Salvatore,
>
> I found my answer re-reading your original post:
> > During the arbitration phase (say at the i-th leaf node of M_T), any
> party can win the challenge by providing correct values for tr_i = (st_i,
> op_i, st_{i + 1}). Crucially, only one party is able to provide correct
> values, and Script can verify that indeed the state moves from st_i to
> st_{i + 1} by executing op_i. The challenge is over.
>
You are correct, the computation step encoded in a leaf needs to be simple
enough for Script to verify it.
For the academic purpose of proving completeness (that is, any computation
can be successfully "proved" by the availability of the corresponding fraud
proof), one can imagine reducing the computation all the way down to a
circuit, where each step (leaf) is as simple as what can be checked with
{OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
In practice, you would want to utilize Script to its fullest, so for
example you wouldn't compile a SHA256 computation to something else – you'd
rather use OP_SHA256 directly.
> That raises leads to a different question: Alice initially posts a
> commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees
> with `y` so starts the challenge protocol. Is there a commitment to `f`? In
> other words, the dispute protocol (as I read it) finds the leftmost step in
> Alice and Bob's execution traces that differ, and then rewards the coins to
> the participant who's "after-value" is computed by the step's operation
> applied to the "before value". But if the participants each present valid
> steps but with different operations, who wins? In other words, Alice could
> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
> Those steps don't match, but both are valid. Is there something to ensure
> that before the challenge protocol starts, that the execution trace that
> Alice posts is for the right computation and not a different computation
> that yields a favorable result for her (and for which she can generate a
> valid merkle tree)?
>
The function f is already hard-coded in the contract itself, by means of
the tree of scripts − that already commits to the possible futures.
Therefore, once you are at state S14, you know that you are verifying the
6th step of the computation; and the operation in the 6th step of the
computation depends solely on f, not its inputs. In fact, you made me
realize that I could drop op_i from the i-th leaf commitment, and just
embed the information in the Script of that corresponding state.
Note that the states S0 to S14 of the 256x game are not _all_ the possible
states, but only the ones that occurred in that execution of the contract
(corresponding to a path from the root to the leaf of the Merkle tree of
the computation trace), and therefore the ones that materialized in a UTXO.
Different choices made by the parties (by providing different data, and
therefore choosing different branches) would lead to a different leaf, and
therefore to different (but in a certain sense "symmetric") states.
========
Since we are talking about the fact that f is committed to in the contract,
I'll take the chance to extend on this a bit with a fun construction on top.
It is well-known in the academic literature of state channels that you can
create contracts where even the function ("program", or "contract") is not
decided when the channel is created.
Since f is generic, we can choose f itself to be a universal Turing
machine. That is, we can imagine a function f(code, data) that executes a
program ("code") on the "data" given to it as input.
Since we can do fraud proofs on statements "f(code, data) == output", we
could build contracts where the "code" itself is chosen later.
For example, one could build a universal state channel, where parties can
enter any contract among themselves (e.g.: start playing a chess game)
entirely inside the channel. The state of this universal channel would
contain all the states of the individual contracts that are currently open
in the channel, and even starting/closing contracts can happen entirely
off-chain.
I believe these constructions are practical (the code of universal Turing
machines is not really complicated), so it might be worth exploring further
to figure out useful applications of this approach (supercharging
lightning?).
We should probably start by implementing testnet rock-paper-scissors in
MATT, though :)
Best,
Salvatore Ingala
[-- Attachment #2: Type: text/html, Size: 5624 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-12-01 8:47 ` Salvatore Ingala
@ 2022-12-13 6:59 ` Billy Tetrud
2023-04-28 8:48 ` Johan Torås Halseth
0 siblings, 1 reply; 20+ messages in thread
From: Billy Tetrud @ 2022-12-13 6:59 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 5631 bytes --]
Re Verkle trees, that's a very interesting construction that would be super
useful as a tool for something like Utreexo. A potentially substantial
downside is that it seems the cryptography used to get those nice
properties of Verkle trees isn't quantum safe
<https://vitalik.ca/general/2021/06/18/verkle.html>. While a lot of things
in Bitcoin seems to be going down the path of quantum-unsafe (I'm looking
at you, taproot), there are still a lot of people who think quantum
safety is important in a lot of contexts.
On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> Hello Rijndael,
>
>
>
> On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail•com> wrote:
>
>> Hello Salvatore,
>>
>> I found my answer re-reading your original post:
>> > During the arbitration phase (say at the i-th leaf node of M_T), any
>> party can win the challenge by providing correct values for tr_i = (st_i,
>> op_i, st_{i + 1}). Crucially, only one party is able to provide correct
>> values, and Script can verify that indeed the state moves from st_i to
>> st_{i + 1} by executing op_i. The challenge is over.
>>
> You are correct, the computation step encoded in a leaf needs to be simple
> enough for Script to verify it.
>
> For the academic purpose of proving completeness (that is, any computation
> can be successfully "proved" by the availability of the corresponding fraud
> proof), one can imagine reducing the computation all the way down to a
> circuit, where each step (leaf) is as simple as what can be checked with
> {OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
>
> In practice, you would want to utilize Script to its fullest, so for
> example you wouldn't compile a SHA256 computation to something else – you'd
> rather use OP_SHA256 directly.
>
>
>> That raises leads to a different question: Alice initially posts a
>> commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees
>> with `y` so starts the challenge protocol. Is there a commitment to `f`? In
>> other words, the dispute protocol (as I read it) finds the leftmost step in
>> Alice and Bob's execution traces that differ, and then rewards the coins to
>> the participant who's "after-value" is computed by the step's operation
>> applied to the "before value". But if the participants each present valid
>> steps but with different operations, who wins? In other words, Alice could
>> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
>> Those steps don't match, but both are valid. Is there something to ensure
>> that before the challenge protocol starts, that the execution trace that
>> Alice posts is for the right computation and not a different computation
>> that yields a favorable result for her (and for which she can generate a
>> valid merkle tree)?
>>
>
> The function f is already hard-coded in the contract itself, by means of
> the tree of scripts − that already commits to the possible futures.
> Therefore, once you are at state S14, you know that you are verifying the
> 6th step of the computation; and the operation in the 6th step of the
> computation depends solely on f, not its inputs. In fact, you made me
> realize that I could drop op_i from the i-th leaf commitment, and just
> embed the information in the Script of that corresponding state.
>
> Note that the states S0 to S14 of the 256x game are not _all_ the possible
> states, but only the ones that occurred in that execution of the contract
> (corresponding to a path from the root to the leaf of the Merkle tree of
> the computation trace), and therefore the ones that materialized in a UTXO.
> Different choices made by the parties (by providing different data, and
> therefore choosing different branches) would lead to a different leaf, and
> therefore to different (but in a certain sense "symmetric") states.
>
> ========
>
> Since we are talking about the fact that f is committed to in the
> contract, I'll take the chance to extend on this a bit with a fun
> construction on top.
> It is well-known in the academic literature of state channels that you can
> create contracts where even the function ("program", or "contract") is not
> decided when the channel is created.
>
> Since f is generic, we can choose f itself to be a universal Turing
> machine. That is, we can imagine a function f(code, data) that executes a
> program ("code") on the "data" given to it as input.
> Since we can do fraud proofs on statements "f(code, data) == output", we
> could build contracts where the "code" itself is chosen later.
>
> For example, one could build a universal state channel, where parties can
> enter any contract among themselves (e.g.: start playing a chess game)
> entirely inside the channel. The state of this universal channel would
> contain all the states of the individual contracts that are currently open
> in the channel, and even starting/closing contracts can happen entirely
> off-chain.
>
> I believe these constructions are practical (the code of universal Turing
> machines is not really complicated), so it might be worth exploring further
> to figure out useful applications of this approach (supercharging
> lightning?).
>
> We should probably start by implementing testnet rock-paper-scissors in
> MATT, though :)
>
> Best,
> Salvatore Ingala
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 6974 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2022-12-13 6:59 ` Billy Tetrud
@ 2023-04-28 8:48 ` Johan Torås Halseth
2023-05-01 13:11 ` Salvatore Ingala
0 siblings, 1 reply; 20+ messages in thread
From: Johan Torås Halseth @ 2023-04-28 8:48 UTC (permalink / raw)
To: Billy Tetrud, Bitcoin Protocol Discussion
Hi, Salvatore.
I find this proposal very interesting. Especially since you seemingly
can achieve such powerful capabilities by such simple opcodes.
I'm still trying to grok how this would look like on-chain (forget
about the off-chain part for now), if we were to play out such a
computation.
Let's say you have a simple game like "one player tic-tac-toe" with
only two tiles: [ _ | _ ]. The player wins if he can get two in a row
(pretty easy game tbh).
Could you give a complete example how you would encode one such state
transition (going from [ X, _ ] -> [ X, X ] for instance) in Bitcoin
script?
Feel free to choose a different game or program if you prefer :)
Thanks!
Johan
On Tue, Dec 13, 2022 at 2:08 PM Billy Tetrud via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> Re Verkle trees, that's a very interesting construction that would be super useful as a tool for something like Utreexo. A potentially substantial downside is that it seems the cryptography used to get those nice properties of Verkle trees isn't quantum safe. While a lot of things in Bitcoin seems to be going down the path of quantum-unsafe (I'm looking at you, taproot), there are still a lot of people who think quantum safety is important in a lot of contexts.
>
> On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>>
>> Hello Rijndael,
>>
>>
>>
>> On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail•com> wrote:
>>>
>>> Hello Salvatore,
>>>
>>> I found my answer re-reading your original post:
>>> > During the arbitration phase (say at the i-th leaf node of M_T), any party can win the challenge by providing correct values for tr_i = (st_i, op_i, st_{i + 1}). Crucially, only one party is able to provide correct values, and Script can verify that indeed the state moves from st_i to st_{i + 1} by executing op_i. The challenge is over.
>>
>> You are correct, the computation step encoded in a leaf needs to be simple enough for Script to verify it.
>>
>> For the academic purpose of proving completeness (that is, any computation can be successfully "proved" by the availability of the corresponding fraud proof), one can imagine reducing the computation all the way down to a circuit, where each step (leaf) is as simple as what can be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
>>
>> In practice, you would want to utilize Script to its fullest, so for example you wouldn't compile a SHA256 computation to something else – you'd rather use OP_SHA256 directly.
>>
>>>
>>> That raises leads to a different question: Alice initially posts a commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees with `y` so starts the challenge protocol. Is there a commitment to `f`? In other words, the dispute protocol (as I read it) finds the leftmost step in Alice and Bob's execution traces that differ, and then rewards the coins to the participant who's "after-value" is computed by the step's operation applied to the "before value". But if the participants each present valid steps but with different operations, who wins? In other words, Alice could present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65]. Those steps don't match, but both are valid. Is there something to ensure that before the challenge protocol starts, that the execution trace that Alice posts is for the right computation and not a different computation that yields a favorable result for her (and for which she can generate a valid merkle tree)?
>>
>>
>> The function f is already hard-coded in the contract itself, by means of the tree of scripts − that already commits to the possible futures. Therefore, once you are at state S14, you know that you are verifying the 6th step of the computation; and the operation in the 6th step of the computation depends solely on f, not its inputs. In fact, you made me realize that I could drop op_i from the i-th leaf commitment, and just embed the information in the Script of that corresponding state.
>>
>> Note that the states S0 to S14 of the 256x game are not _all_ the possible states, but only the ones that occurred in that execution of the contract (corresponding to a path from the root to the leaf of the Merkle tree of the computation trace), and therefore the ones that materialized in a UTXO. Different choices made by the parties (by providing different data, and therefore choosing different branches) would lead to a different leaf, and therefore to different (but in a certain sense "symmetric") states.
>>
>> ========
>>
>> Since we are talking about the fact that f is committed to in the contract, I'll take the chance to extend on this a bit with a fun construction on top.
>> It is well-known in the academic literature of state channels that you can create contracts where even the function ("program", or "contract") is not decided when the channel is created.
>>
>> Since f is generic, we can choose f itself to be a universal Turing machine. That is, we can imagine a function f(code, data) that executes a program ("code") on the "data" given to it as input.
>> Since we can do fraud proofs on statements "f(code, data) == output", we could build contracts where the "code" itself is chosen later.
>>
>> For example, one could build a universal state channel, where parties can enter any contract among themselves (e.g.: start playing a chess game) entirely inside the channel. The state of this universal channel would contain all the states of the individual contracts that are currently open in the channel, and even starting/closing contracts can happen entirely off-chain.
>>
>> I believe these constructions are practical (the code of universal Turing machines is not really complicated), so it might be worth exploring further to figure out useful applications of this approach (supercharging lightning?).
>>
>> We should probably start by implementing testnet rock-paper-scissors in MATT, though :)
>>
>> Best,
>> Salvatore Ingala
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-04-28 8:48 ` Johan Torås Halseth
@ 2023-05-01 13:11 ` Salvatore Ingala
2023-05-01 21:15 ` Salvatore Ingala
0 siblings, 1 reply; 20+ messages in thread
From: Salvatore Ingala @ 2023-05-01 13:11 UTC (permalink / raw)
To: Johan Torås Halseth, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 13099 bytes --]
Hi Johan,
Thanks for your message.
I think games where all the possible futures can be enumerated are
not ideal to showcase MATT, as one could just fully represent them
with just CTV or COCV, and not use the "data embedding" at all.
Perhaps rock-paper-scissors could be a better academic example. [1]
I'm not sure this will fully address your question; however I think
it's quite an instructive example, and I wanted to work it out for
quite some time.
It would be interesting to explore some contracts where the size
of the embedded data is substantially larger, and that could be
a natural next step to think about.
### Rock paper scissors
We want a protocol between Alice and Bob, where they bet 1 coin each:
1. Alice chooses and publishes her move;
2. Bob chooses his move, and the pot is adjudicated as per the rules.
Of course, if implemented naively, this wouldn't be a very fun game:
Bob would just wait to see Alice's move and play accordingly.
That's easy to fix, though:
1. Alice publishes a commitment to her move
2. Bob publishes his move in clear
3. Alice reveals her move, and the pot is adjudicated.
We can encode Rock = 0, Paper = 1, Scissors = 2. Let m_A, m_B be
Alice's and Bob's move, respectively. Then, it's easy to verify that:
− m_B - m_A == 0 (mod 3) ==> it's a tie
− m_B - m_A == 1 (mod 3) ==> Bob wins
− m_B - m_A == 2 (mod 3) ==> Alice wins
In order to create a hiding commitment for Alice, she can choose a
256-bit random number r_A, and compute:
c_A = SHA256(m_A || r_A)
With that in mind, the full protocol can go like this:
1. Alice chooses her move m_A and a large random number r_A;
she posts c_A computed as above;
2. Bob chooses m_B and publishes it;
3. Alice publishes m_A and r_A, then the winner is adjudicated.
### MATT playing RPS
To implement this with CICV/COCV, we can use just 3 transactions: in
fact, Alice can already compute c_A and share it with Bob before they
both commit their coins into an encumbered UTXO. That also means that
c_A can actually be hardcoded in the Scripts, rather than taking
space in the UTXO's embedded data.
Therefore, they both put one coin each, and they send to an output
whose script is the state S0 described below.
We assume that the keypath in the P2TR defined below is either a NUMS
point, or perhaps a Musig2 aggregate key that can be used to settle
the game collaboratively.
Note that there are 3 possible payout options that are fully known
when the game starts: either Alice takes all the money, or they split
evenly, or Bob takes all the money.
Similarly to the vault implementation [2], this seems to be another
case where CTV fits very well, as it allows to very efficiently
describe the three possible outcomes by their CTV hashes. Let them
be <ctv-alice-wins>, <ctv-split>, <ctv-bob-wins>, respectively.
Therefore, this avoids the need for 64-bit maths, and explicit amount
introspection − at least for these contracts.
[State S0] (Start of the game, Alice moved; Bob's turn)
Spending conditions:
- after <forfait-delay>, Alice takes the money // (Bob forfaits)
- Bob posts m_B (0, 1 or 2); the next output is [S1] with data m_B
The first script is:
// witness: []
<forfait-delay>
OP_CHECKSEQUENCEVERIFY
OP_DROP
<ctv-alice-wins>
OP_CHECKTEMPLATEVERIFY
The second is
// witness: [<bob_sig> <m_B>]
OP_DUP 0 3 OP_WITHIN // check that m_B is 0, 1 or 2
<internal_pubkey> OP_SWAP
<S1's taptree>
OP_CHECKOUTPUTCONTRACTVERIFY // check that the output is correct
<bob_pubkey>
OP_CHECKSIG
[State S1] (Alice reveals m_A and adjudicates)
- after <forfait-timeout>, Bob takes the money // (Alice forfaits)
- Alice posts correct m_A and r_A compatible with c_A;
The first script is symmetric to Bob's forfait script above.
The second condition can be split into three leaf scripts, one for
each possible value of m_B - m_A (mod 3):
// witness: [<m_B> <m_A> <r_A>]
OP_OVER OP_DUP OP_TOALTSTACK // save m_A
0 3 OP_WITHIN OP_VERIFY // check that m_A is 0, 1 or 2
// check that SHA256(m_A || r_A) equals c_A
OP_2DUP
OP_CAT OP_SHA256
<c_A>
OP_EQUALVERIFY
OP_DUP
<internal_pubkey>, OP_SWAP
OP_CHECKINPUTCONTRACTVERIFY
OP_FROMALTSTACK
OP_SUB // stack now contains m_B - m_A
OP_DUP // if the result is negative, add 3
0 OP_LESSTHAN
OP_IF
3
OP_ADD
OP_ENDIF
{0, 1, 2} // draw / Bob wins / Alice wins, respectively
OP_EQUALVERIFY
{<ctv-split>, <ctv-bob-wins>, <ctv-alice-wins>} // respectively
OP_CHECKTEMPLATEVERIFY
### Comments
In general, we would have to worry about the possible
malleability of the witness elements, when they are not signatures
or preimages themselves. Here, in particular, it might seem that's
an issue when <m_B> is provided while spending the state [S0].
However, here the value of <m_B> is also committed to in the output
thanks to COCV; therefore, Bob's signature prevents malleability
also for m_B.
In general, it seems to be the case in MATT contracts that one would
want the signature of the authorized party performing a transition to
some other state of the smart contract with contains embedded data;
this makes the malleability issue less of a problem in practice than
I initially thought.
If the internal_pubkey is a musig-aggregated key of Alice and Bob,
the game can be settled entirely offline after the first transaction.
Simply, Bob communicates his move to Alice, Alice reveals her move to
Bob, and they can settle the bet. The game would be played without
any script being executed, therefore all transactions could look like
any other P2TR, with the only possible fingerprinting being due to the
input amounts.
It should be possible to generalize the protocol so that many rounds
can be played off-chain within the same UTXO, but I didn't try to
figure out the details.
Best,
Salvatore Ingala
[1] - https://en.wikipedia.org/wiki/Rock_paper_scissors
[2] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html
On Fri, 28 Apr 2023 at 10:48, Johan Torås Halseth <johanth@gmail•com> wrote:
> Hi, Salvatore.
>
> I find this proposal very interesting. Especially since you seemingly
> can achieve such powerful capabilities by such simple opcodes.
>
> I'm still trying to grok how this would look like on-chain (forget
> about the off-chain part for now), if we were to play out such a
> computation.
>
> Let's say you have a simple game like "one player tic-tac-toe" with
> only two tiles: [ _ | _ ]. The player wins if he can get two in a row
> (pretty easy game tbh).
>
> Could you give a complete example how you would encode one such state
> transition (going from [ X, _ ] -> [ X, X ] for instance) in Bitcoin
> script?
>
> Feel free to choose a different game or program if you prefer :)
>
> Thanks!
> Johan
>
>
>
> On Tue, Dec 13, 2022 at 2:08 PM Billy Tetrud via bitcoin-dev
> <bitcoin-dev@lists•linuxfoundation.org> wrote:
> >
> > Re Verkle trees, that's a very interesting construction that would be
> super useful as a tool for something like Utreexo. A potentially
> substantial downside is that it seems the cryptography used to get those
> nice properties of Verkle trees isn't quantum safe. While a lot of things
> in Bitcoin seems to be going down the path of quantum-unsafe (I'm looking
> at you, taproot), there are still a lot of people who think quantum safety
> is important in a lot of contexts.
> >
> > On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
> >>
> >> Hello Rijndael,
> >>
> >>
> >>
> >> On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail•com>
> wrote:
> >>>
> >>> Hello Salvatore,
> >>>
> >>> I found my answer re-reading your original post:
> >>> > During the arbitration phase (say at the i-th leaf node of M_T), any
> party can win the challenge by providing correct values for tr_i = (st_i,
> op_i, st_{i + 1}). Crucially, only one party is able to provide correct
> values, and Script can verify that indeed the state moves from st_i to
> st_{i + 1} by executing op_i. The challenge is over.
> >>
> >> You are correct, the computation step encoded in a leaf needs to be
> simple enough for Script to verify it.
> >>
> >> For the academic purpose of proving completeness (that is, any
> computation can be successfully "proved" by the availability of the
> corresponding fraud proof), one can imagine reducing the computation all
> the way down to a circuit, where each step (leaf) is as simple as what can
> be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
> >>
> >> In practice, you would want to utilize Script to its fullest, so for
> example you wouldn't compile a SHA256 computation to something else – you'd
> rather use OP_SHA256 directly.
> >>
> >>>
> >>> That raises leads to a different question: Alice initially posts a
> commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees
> with `y` so starts the challenge protocol. Is there a commitment to `f`? In
> other words, the dispute protocol (as I read it) finds the leftmost step in
> Alice and Bob's execution traces that differ, and then rewards the coins to
> the participant who's "after-value" is computed by the step's operation
> applied to the "before value". But if the participants each present valid
> steps but with different operations, who wins? In other words, Alice could
> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
> Those steps don't match, but both are valid. Is there something to ensure
> that before the challenge protocol starts, that the execution trace that
> Alice posts is for the right computation and not a different computation
> that yields a favorable result for her (and for which she can generate a
> valid merkle tree)?
> >>
> >>
> >> The function f is already hard-coded in the contract itself, by means
> of the tree of scripts − that already commits to the possible futures.
> Therefore, once you are at state S14, you know that you are verifying the
> 6th step of the computation; and the operation in the 6th step of the
> computation depends solely on f, not its inputs. In fact, you made me
> realize that I could drop op_i from the i-th leaf commitment, and just
> embed the information in the Script of that corresponding state.
> >>
> >> Note that the states S0 to S14 of the 256x game are not _all_ the
> possible states, but only the ones that occurred in that execution of the
> contract (corresponding to a path from the root to the leaf of the Merkle
> tree of the computation trace), and therefore the ones that materialized in
> a UTXO. Different choices made by the parties (by providing different data,
> and therefore choosing different branches) would lead to a different leaf,
> and therefore to different (but in a certain sense "symmetric") states.
> >>
> >> ========
> >>
> >> Since we are talking about the fact that f is committed to in the
> contract, I'll take the chance to extend on this a bit with a fun
> construction on top.
> >> It is well-known in the academic literature of state channels that you
> can create contracts where even the function ("program", or "contract") is
> not decided when the channel is created.
> >>
> >> Since f is generic, we can choose f itself to be a universal Turing
> machine. That is, we can imagine a function f(code, data) that executes a
> program ("code") on the "data" given to it as input.
> >> Since we can do fraud proofs on statements "f(code, data) == output",
> we could build contracts where the "code" itself is chosen later.
> >>
> >> For example, one could build a universal state channel, where parties
> can enter any contract among themselves (e.g.: start playing a chess game)
> entirely inside the channel. The state of this universal channel would
> contain all the states of the individual contracts that are currently open
> in the channel, and even starting/closing contracts can happen entirely
> off-chain.
> >>
> >> I believe these constructions are practical (the code of universal
> Turing machines is not really complicated), so it might be worth exploring
> further to figure out useful applications of this approach (supercharging
> lightning?).
> >>
> >> We should probably start by implementing testnet rock-paper-scissors in
> MATT, though :)
> >>
> >> Best,
> >> Salvatore Ingala
> >> _______________________________________________
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists•linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists•linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 15469 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-05-01 13:11 ` Salvatore Ingala
@ 2023-05-01 21:15 ` Salvatore Ingala
2023-05-04 8:34 ` Johan Torås Halseth
0 siblings, 1 reply; 20+ messages in thread
From: Salvatore Ingala @ 2023-05-01 21:15 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 1495 bytes --]
Hi all,
I apologize for a couple of oversights in my last e-mail.
The first is that m_B can't be committed as-is in the contract's
embedded data, with the current semantics of OP_COCV, which
only allows 32-byte values. A solution could be to store its
hash SHA256(m_B), instead.
(I didn't test the Scripts, so there could be other bugs − hopefully the
general idea is clear, anyway)
On Mon, 1 May 2023 at 15:11, Salvatore Ingala <salvatore.ingala@gmail•com>
wrote:
> If the internal_pubkey is a musig-aggregated key of Alice and Bob,
> the game can be settled entirely offline after the first transaction.
> Simply, Bob communicates his move to Alice, Alice reveals her move to
> Bob, and they can settle the bet. The game would be played without
> any script being executed, therefore all transactions could look like
> any other P2TR, with the only possible fingerprinting being due to the
> input amounts.
>
This is incomplete: Alice can't trust Bob by revealing her move, as
he could then cheat on-chain and play a different move.
The fix should be straightforward, after adding the requirement that the
internal pubkey of [S1] is a musig2 of both players.
After Bob reveals his move (say, Rock), Alice will only agree to continue
the game off-chain if Bob pre-signs transactions for the state [S1] (where
m_B = Paper, and m_B = Scissors) that send all the money to Alice.
This guarantees that a cheating Bob is punished.
Best,
Salvatore Ingala
[-- Attachment #2: Type: text/html, Size: 2115 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-05-01 21:15 ` Salvatore Ingala
@ 2023-05-04 8:34 ` Johan Torås Halseth
2023-05-05 21:18 ` Salvatore Ingala
0 siblings, 1 reply; 20+ messages in thread
From: Johan Torås Halseth @ 2023-05-04 8:34 UTC (permalink / raw)
To: Salvatore Ingala, Bitcoin Protocol Discussion
Thank you for the example.
It sounds like we can generalize the description of the construct to:
Access to (the hash of) embedded data of inputs and outputs, and the
enforcement of output keys and (static) taptrees. In other words, as
long as you can dynamically compute the output embedded data in
Script, you can enforce more or less anything (since you can make the
output script enforce presenting a witness "satisfying" the embedded
data).
Does that sound about right?
For instance, I believe you could simulate coin pools pretty easily:
Commit to the set of pubkeys and amounts owned by the participants in
the pool, and an output taptree where each participant has their own
spending path. Now, to exit the pool unilaterally, the participant
must present a proof that their pubkey+amount is committed to in the
input and an output where it is no longer committed.
A question that arises is how one would efficiently (in Script) prove
the inclusion/exclusion of the data in the commitment. One could
naively hash all the data twice during script execution (once for the
input, once for the output), but that is costly. It would be natural
to show merkle tree inclusion/exclusion in script, but perhaps there
are more efficient ways to prove it?
- Johan
On Tue, May 2, 2023 at 12:44 AM Salvatore Ingala via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> Hi all,
>
> I apologize for a couple of oversights in my last e-mail.
>
> The first is that m_B can't be committed as-is in the contract's
> embedded data, with the current semantics of OP_COCV, which
> only allows 32-byte values. A solution could be to store its
> hash SHA256(m_B), instead.
>
> (I didn't test the Scripts, so there could be other bugs − hopefully the
> general idea is clear, anyway)
>
> On Mon, 1 May 2023 at 15:11, Salvatore Ingala <salvatore.ingala@gmail•com> wrote:
>>
>> If the internal_pubkey is a musig-aggregated key of Alice and Bob,
>> the game can be settled entirely offline after the first transaction.
>> Simply, Bob communicates his move to Alice, Alice reveals her move to
>> Bob, and they can settle the bet. The game would be played without
>> any script being executed, therefore all transactions could look like
>> any other P2TR, with the only possible fingerprinting being due to the
>> input amounts.
>
>
> This is incomplete: Alice can't trust Bob by revealing her move, as
> he could then cheat on-chain and play a different move.
>
> The fix should be straightforward, after adding the requirement that the
> internal pubkey of [S1] is a musig2 of both players.
> After Bob reveals his move (say, Rock), Alice will only agree to continue
> the game off-chain if Bob pre-signs transactions for the state [S1] (where
> m_B = Paper, and m_B = Scissors) that send all the money to Alice.
> This guarantees that a cheating Bob is punished.
>
> Best,
> Salvatore Ingala
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-05-04 8:34 ` Johan Torås Halseth
@ 2023-05-05 21:18 ` Salvatore Ingala
2023-05-26 11:45 ` Johan Torås Halseth
0 siblings, 1 reply; 20+ messages in thread
From: Salvatore Ingala @ 2023-05-05 21:18 UTC (permalink / raw)
To: Johan Torås Halseth; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 3056 bytes --]
On Thu, 4 May 2023 at 10:34, Johan Torås Halseth <johanth@gmail•com> wrote:
>
> It sounds like we can generalize the description of the construct to:
> Access to (the hash of) embedded data of inputs and outputs, and the
> enforcement of output keys and (static) taptrees. In other words, as
> long as you can dynamically compute the output embedded data in
> Script, you can enforce more or less anything (since you can make the
> output script enforce presenting a witness "satisfying" the embedded
> data).
>
> Does that sound about right?
Yes. Fraud proofs allow us to extend beyond what Script can do (with the
necessary tradeoffs), but there is plenty that can be done without them.
> For instance, I believe you could simulate coin pools pretty easily:
> Commit to the set of pubkeys and amounts owned by the participants in
> the pool, and an output taptree where each participant has their own
> spending path. Now, to exit the pool unilaterally, the participant
> must present a proof that their pubkey+amount is committed to in the
> input and an output where it is no longer committed.
I don't think one would want to have a tapleaf for each participant:
that would make you pay log n hashes just to reveal the tapleaf, and
then you still need to pay log n hashes to access the embedded data.
Instead, the "unilateral withdrawal Script" can be the same for all the
participants. The witness would be the Merkle proof, plus perhaps some
additional information to identify the leaf in the tree (depending on
how the Merkle tree is implemented). In a complete Merkle tree for
N = 2^n participants, the witness could contain the n hashes that allow
to prove the value of the leaf, plus n bits to identify the path to the
leaf (0/1 for 'left/right" child), since Script doesn't have enough
opcodes to extract the bits from the leaf index.
The data in the leaf can contain a commitment to all the information
relevant for that participant (e.g.: their balance and pubkey, in a
CoinPool construction).
Then, the same witness can easily be reused to compute the new Merkle
root after the data in the leaf is modified (for example, setting the
amount to 0 for one participant).
> A question that arises is how one would efficiently (in Script) prove
> the inclusion/exclusion of the data in the commitment. One could
> naively hash all the data twice during script execution (once for the
> input, once for the output), but that is costly. It would be natural
> to show merkle tree inclusion/exclusion in script, but perhaps there
> are more efficient ways to prove it?
A Merkle tree as described above commits to an entire vector that you
can index positionally. That's quite versatile, and easier to handle
than more complex constructions like accumulators with exclusion proofs.
A Merkle proof for 2^7 = 128 participants requires about 8 hashes, so
around 250 bytes in total of witness size; 2^10 = 1024 should bring that
to the ballpark of 350 bytes.
Best,
Salvatore Ingala
[-- Attachment #2: Type: text/html, Size: 3353 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-05-05 21:18 ` Salvatore Ingala
@ 2023-05-26 11:45 ` Johan Torås Halseth
2023-05-28 10:24 ` Salvatore Ingala
0 siblings, 1 reply; 20+ messages in thread
From: Johan Torås Halseth @ 2023-05-26 11:45 UTC (permalink / raw)
To: Salvatore Ingala; +Cc: Bitcoin Protocol Discussion
Hi, Salvatore.
As a further exploration of this idea, I implemented a
proof-of-concept of OP_CICV and OP_COCV in btcd[1] that together with
OP_CAT enables a set of interesting use cases.
One such use case is, as mentioned earlier, CoinPools[2]. The opcodes
let you easily check the "dynamically committed data" of an input you
are spending, and enforce a new commitment on the output. The idea is
to have the set of participants in the pool, and their balances, be
the UTXOs committed data, and use this to validate the legitimacy of
a transaction, determining whether it permits a peer to exit with a
portion of the pooled funds.
Doing what you suggested above, having the input and output commit to
a merkle tree of participants and balances, we are able to quite
elegantly verify the coin pool exit clause. Here is a working example
of how that could look like: [3]. Obviously this lacks a lot before it
is a working CoinPool implementation, but it demonstrates how
OP_C[I/O]V introduces "memory" to Bitcoin script.
Having done this exercise, I have a few suggestions on how one could
further extend the proposal:
1. In the current proposal for OP_CHECKOUTPUTCONTRACTVERIFY, the
opcodes check whether the output key Q is key X tweaked with data D
and taproot T: Q == tweak(tweak(X,D), T).
OP_CHECKINPUTCONTRACTVERIFY on the other hand, works on the input
internal key, and does not care about the taptree on the input: P ==
tweak(X,D), where Q = tweak(P, T). In most cases this is probably good
enough, since you are already executing the current script and that
way know the spender has provided the correct taproot.
However, in the coin pool script mentioned above, I found that I
wanted to re-use the same taproot for the output (recursively). I
believe this would be a quite common use case. To solve this I
committed the taproot as part of the data itself: D' = hash(T+D),
which was then verified by OP_CICV. If you are aware of more efficient
alternatives, I am eager to hear them.
A simpler way IMO, would be to make OP_CICV and OP_COCV symmetrical:
Have OP_CICV take an optional taproot and do the same check as is done
for the output: Q == tweak(tweak(X,D), T).
2.To make fully functioning CoinPools, one would need functionality
similar to OP_MERKLESUB[4]: remove some data from the merkle tree, and
remove a key from the aggregated internal key.This suggestion may
surpass the intended scope of this proposal, and would likely
necessitate the availability of multiple EC operations to accommodate
various key schemes. If we had opcodes for adding and removing keys
from the internal key this would be even more powerful.
I look forward to hearing your thoughts on these suggestions and
further exploring the possibilities of the proposal!
Cheers,
Johan
[1] https://github.com/halseth/btcd/pull/1/commits/90a4065bdcd8029fe3325514a250490cba66fddd
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017964.html
[3] https://github.com/halseth/tapsim/tree/matt-demo/examples/matt/coinpool
[4] https://github.com/ariard/bips/blob/coinpool-bips/bip-merklesub.mediawiki
On Fri, May 5, 2023 at 11:18 PM Salvatore Ingala
<salvatore.ingala@gmail•com> wrote:
>
> On Thu, 4 May 2023 at 10:34, Johan Torås Halseth <johanth@gmail•com> wrote:
> >
> > It sounds like we can generalize the description of the construct to:
> > Access to (the hash of) embedded data of inputs and outputs, and the
> > enforcement of output keys and (static) taptrees. In other words, as
> > long as you can dynamically compute the output embedded data in
> > Script, you can enforce more or less anything (since you can make the
> > output script enforce presenting a witness "satisfying" the embedded
> > data).
> >
> > Does that sound about right?
>
> Yes. Fraud proofs allow us to extend beyond what Script can do (with the
> necessary tradeoffs), but there is plenty that can be done without them.
>
>
> > For instance, I believe you could simulate coin pools pretty easily:
> > Commit to the set of pubkeys and amounts owned by the participants in
> > the pool, and an output taptree where each participant has their own
> > spending path. Now, to exit the pool unilaterally, the participant
> > must present a proof that their pubkey+amount is committed to in the
> > input and an output where it is no longer committed.
>
> I don't think one would want to have a tapleaf for each participant:
> that would make you pay log n hashes just to reveal the tapleaf, and
> then you still need to pay log n hashes to access the embedded data.
>
> Instead, the "unilateral withdrawal Script" can be the same for all the
> participants. The witness would be the Merkle proof, plus perhaps some
> additional information to identify the leaf in the tree (depending on
> how the Merkle tree is implemented). In a complete Merkle tree for
> N = 2^n participants, the witness could contain the n hashes that allow
> to prove the value of the leaf, plus n bits to identify the path to the
> leaf (0/1 for 'left/right" child), since Script doesn't have enough
> opcodes to extract the bits from the leaf index.
>
> The data in the leaf can contain a commitment to all the information
> relevant for that participant (e.g.: their balance and pubkey, in a
> CoinPool construction).
>
> Then, the same witness can easily be reused to compute the new Merkle
> root after the data in the leaf is modified (for example, setting the
> amount to 0 for one participant).
>
>
> > A question that arises is how one would efficiently (in Script) prove
> > the inclusion/exclusion of the data in the commitment. One could
> > naively hash all the data twice during script execution (once for the
> > input, once for the output), but that is costly. It would be natural
> > to show merkle tree inclusion/exclusion in script, but perhaps there
> > are more efficient ways to prove it?
>
> A Merkle tree as described above commits to an entire vector that you
> can index positionally. That's quite versatile, and easier to handle
> than more complex constructions like accumulators with exclusion proofs.
>
> A Merkle proof for 2^7 = 128 participants requires about 8 hashes, so
> around 250 bytes in total of witness size; 2^10 = 1024 should bring that
> to the ballpark of 350 bytes.
>
> Best,
> Salvatore Ingala
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-05-26 11:45 ` Johan Torås Halseth
@ 2023-05-28 10:24 ` Salvatore Ingala
2023-05-30 7:34 ` Johan Torås Halseth
0 siblings, 1 reply; 20+ messages in thread
From: Salvatore Ingala @ 2023-05-28 10:24 UTC (permalink / raw)
To: Johan Torås Halseth; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 3551 bytes --]
Hi Johan,
Exciting to finally see some merkleization, which was only confined
within the meme, up to this point!
> A simpler way IMO, would be to make OP_CICV and OP_COCV symmetrical:
> Have OP_CICV take an optional taproot and do the same check as is
> done for the output: Q == tweak(tweak(X,D), T).
I think that's an excellent suggestion, which I was already exploring
for a different purpose: bringing externally signed data onto the
stack. My goal there was to allow eltoo-style replacement.
Until recently, I thought that a clean/efficient version of eltoo
would require OP_CHECKSIGFROMSTACK or ANYPREVOUT. However, extending
OP_CHECKINPUTCONTRACTVERIFY to enable introspection of other inputs
allows a reasonable workaround: producing a separate UTXO signed with
ANYONECANPAY, with the required data embedded as usual. Spending that
UTXO together with the channel's UTXO allows one to get that data
on the stack (with its signature already checked by consensus rules).
I drafted this idea in a gist [1].
Remark: it still seems easier (and probably slightly more efficient)
to build eltoo replacement with CSFS or APO in addition to MATT
opcodes.
A possible semantics for OP_CHECKINPUTCONTRACTVERIFY could then be
exactly symmetrical to that of OP_CHECKOUTPUTCONTRACTVERIFY, with
the exception that the special input index -1 would represent the
current input.
Pushing this further, another option that could be be worth exploring
is to have a single OP_CHECK_IN_OUT_CONTRACT_VERIFY opcode, with the
same semantics as OP_CHECKOUTPUTCONTRACTVERIFY from [2], but with an
additional `flags` argument, which is a bitmap where:
- the lowest-significant bit determines if the index refers to inputs
or outputs (where input index -1 refers to the current input)
- the second bit specifies if amounts should be preserved with
deferred checks as described in [2] (only applicable to outputs)
- other bits are OP_SUCCESS and reserved for future behaviors.
This would make the opcodes 1-2 bytes larger, but might allow greater
flexibility, and keep some room for future extensions.
> 2.To make fully functioning CoinPools, one would need functionality
> similar to OP_MERKLESUB[4]: remove some data from the merkle tree,
> and remove a key from the aggregated internal key.
It seems likely that efficient use of the taproot internal pubkey with
"dynamic key aggregation" is not possible with the current semantics
(unless one ventures into the fraud proof machinery, which seems
overkill!).
However, in constructions with MATT opcodes, I would never expect the
need for data to be stored in the taptree. In particular, for the case
of CoinPools, the pubkeys of the members could also be stored in the
embedded data, having a single "unilateral withdrawal" tapleaf.
Removing a key would then amount to replacing it with a fixed NUMS key
and computing the new root (re-using the same Merkle proof).
Note that this is not a lot costlier than using a tapleaf per user:
instead of paying the cost for the Merkle proof in the control block,
you pay for it explicitly in the Script witness.
Therefore, I would expect there to be reasonable CoinPools designs
without additional opcodes − but I am only moderately confident as
this is beyond the level of sophistication I've been exploring so far.
Best,
Salvatore
[1] - https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63
[2] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html
[-- Attachment #2: Type: text/html, Size: 3962 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Merkleize All The Things
2023-05-28 10:24 ` Salvatore Ingala
@ 2023-05-30 7:34 ` Johan Torås Halseth
0 siblings, 0 replies; 20+ messages in thread
From: Johan Torås Halseth @ 2023-05-30 7:34 UTC (permalink / raw)
To: Salvatore Ingala; +Cc: Bitcoin Protocol Discussion
I should clarify: the current proposal already achieves the first part
needed for coin pools: removing some data from the merkle tree (I was
indeed referring to the embedded data, not the taptree).
The thing that is missing is removal of a public key from the taproot
internal key, but as mentioned I do agree that this is out of scope
for this proposal.
I believe you can get many of the benefits by falling back to "old
style multisig" in case someone exits the pool, by having a tap leaf
defining a multisig check amongst the remaining pubkeys.
Cheers,
Johan
> It seems likely that efficient use of the taproot internal pubkey with
> "dynamic key aggregation" is not possible with the current semantics
> (unless one ventures into the fraud proof machinery, which seems
> overkill!).
>
> However, in constructions with MATT opcodes, I would never expect the
> need for data to be stored in the taptree. In particular, for the case
> of CoinPools, the pubkeys of the members could also be stored in the
> embedded data, having a single "unilateral withdrawal" tapleaf.
> Removing a key would then amount to replacing it with a fixed NUMS key
> and computing the new root (re-using the same Merkle proof).
> Note that this is not a lot costlier than using a tapleaf per user:
> instead of paying the cost for the Merkle proof in the control block,
> you pay for it explicitly in the Script witness.
>
> Therefore, I would expect there to be reasonable CoinPools designs
> without additional opcodes − but I am only moderately confident as
> this is beyond the level of sophistication I've been exploring so far.
On Sun, May 28, 2023 at 12:24 PM Salvatore Ingala
<salvatore.ingala@gmail•com> wrote:
>
> Hi Johan,
>
> Exciting to finally see some merkleization, which was only confined
> within the meme, up to this point!
>
> > A simpler way IMO, would be to make OP_CICV and OP_COCV symmetrical:
> > Have OP_CICV take an optional taproot and do the same check as is
> > done for the output: Q == tweak(tweak(X,D), T).
>
> I think that's an excellent suggestion, which I was already exploring
> for a different purpose: bringing externally signed data onto the
> stack. My goal there was to allow eltoo-style replacement.
>
> Until recently, I thought that a clean/efficient version of eltoo
> would require OP_CHECKSIGFROMSTACK or ANYPREVOUT. However, extending
> OP_CHECKINPUTCONTRACTVERIFY to enable introspection of other inputs
> allows a reasonable workaround: producing a separate UTXO signed with
> ANYONECANPAY, with the required data embedded as usual. Spending that
> UTXO together with the channel's UTXO allows one to get that data
> on the stack (with its signature already checked by consensus rules).
> I drafted this idea in a gist [1].
>
> Remark: it still seems easier (and probably slightly more efficient)
> to build eltoo replacement with CSFS or APO in addition to MATT
> opcodes.
>
> A possible semantics for OP_CHECKINPUTCONTRACTVERIFY could then be
> exactly symmetrical to that of OP_CHECKOUTPUTCONTRACTVERIFY, with
> the exception that the special input index -1 would represent the
> current input.
>
> Pushing this further, another option that could be be worth exploring
> is to have a single OP_CHECK_IN_OUT_CONTRACT_VERIFY opcode, with the
> same semantics as OP_CHECKOUTPUTCONTRACTVERIFY from [2], but with an
> additional `flags` argument, which is a bitmap where:
> - the lowest-significant bit determines if the index refers to inputs
> or outputs (where input index -1 refers to the current input)
> - the second bit specifies if amounts should be preserved with
> deferred checks as described in [2] (only applicable to outputs)
> - other bits are OP_SUCCESS and reserved for future behaviors.
>
> This would make the opcodes 1-2 bytes larger, but might allow greater
> flexibility, and keep some room for future extensions.
>
> > 2.To make fully functioning CoinPools, one would need functionality
> > similar to OP_MERKLESUB[4]: remove some data from the merkle tree,
> > and remove a key from the aggregated internal key.
>
> It seems likely that efficient use of the taproot internal pubkey with
> "dynamic key aggregation" is not possible with the current semantics
> (unless one ventures into the fraud proof machinery, which seems
> overkill!).
>
> However, in constructions with MATT opcodes, I would never expect the
> need for data to be stored in the taptree. In particular, for the case
> of CoinPools, the pubkeys of the members could also be stored in the
> embedded data, having a single "unilateral withdrawal" tapleaf.
> Removing a key would then amount to replacing it with a fixed NUMS key
> and computing the new root (re-using the same Merkle proof).
> Note that this is not a lot costlier than using a tapleaf per user:
> instead of paying the cost for the Merkle proof in the control block,
> you pay for it explicitly in the Script witness.
>
> Therefore, I would expect there to be reasonable CoinPools designs
> without additional opcodes − but I am only moderately confident as
> this is beyond the level of sophistication I've been exploring so far.
>
> Best,
> Salvatore
>
> [1] - https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63
> [2] - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html
^ permalink raw reply [flat|nested] 20+ messages in thread
end of thread, other threads:[~2023-05-30 7:34 UTC | newest]
Thread overview: 20+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-11-08 9:17 [bitcoin-dev] Merkleize All The Things Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
2022-11-10 9:42 ` Salvatore Ingala
2022-11-08 23:34 ` Bram Cohen
2022-11-09 12:07 ` Peter Todd
2022-11-10 7:39 ` David A. Harding
2022-11-11 21:49 ` Antoine Riard
2022-11-12 15:04 ` Salvatore Ingala
2022-11-30 19:42 ` Rijndael
2022-11-30 22:09 ` Rijndael
2022-12-01 8:47 ` Salvatore Ingala
2022-12-13 6:59 ` Billy Tetrud
2023-04-28 8:48 ` Johan Torås Halseth
2023-05-01 13:11 ` Salvatore Ingala
2023-05-01 21:15 ` Salvatore Ingala
2023-05-04 8:34 ` Johan Torås Halseth
2023-05-05 21:18 ` Salvatore Ingala
2023-05-26 11:45 ` Johan Torås Halseth
2023-05-28 10:24 ` Salvatore Ingala
2023-05-30 7:34 ` Johan Torås Halseth
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox