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 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 >