From: Salvatore Ingala <salvatore.ingala@gmail•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Thu, 10 Nov 2022 10:42:30 +0100 [thread overview]
Message-ID: <CAMhCMoErkp_i3Ho482B91Vects=r98jT_6hyy7F84CVw8f=79A@mail.gmail.com> (raw)
In-Reply-To: <Vbb1PZfBzm6JBddqNIfikVE2G1fDmObt0BBt2BqhmHV_Tx7KLGU5SSQPPp0OaLZHAKrkKobA2f60tX4TOl996aE9ds1tZWaGAHbSr9wu5r0=@protonmail.com>
[-- 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 --]
next prev parent reply other threads:[~2022-11-10 9:42 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-08 9:17 Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
2022-11-10 9:42 ` Salvatore Ingala [this message]
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAMhCMoErkp_i3Ho482B91Vects=r98jT_6hyy7F84CVw8f=79A@mail.gmail.com' \
--to=salvatore.ingala@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox