* [bitcoindev] BitVMX: A Virtual CPU to optimistically execute arbitrary programs on Bitcoin
@ 2024-05-13 1:51 Sergio Demian Lerner
0 siblings, 0 replies; only message in thread
From: Sergio Demian Lerner @ 2024-05-13 1:51 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 3025 bytes --]
Hi!
I'd like to share with you a paper we published a few weeks ago, and was
presented in BTC++. Here is the abstract:
BitVMX is a new design for a virtual CPU to optimistically execute
arbitrary programs on Bitcoin based on a challenge/response game introduced
in BitVM. Similar to BitVM1 we create a general-purpose CPU to be verified
in Bitcoin script. Our design supports common architectures, such as RISC-V
or MIPS. Our main contribution to the state of the art is a design that
uses hash chains of program traces, memory mapped registers, and a new
challenge-response protocol. We present a new message linking protocol as a
means to allow authenticated communication between the participants. This
protocol emulates stateful smart contracts by sharing state between
transactions. This provides a basis for our verification game which uses a
graph of pre-signed transactions to support challenge-response
interactions. In case of a dispute, the hash chain of program trace is used
with selective pre-signed transactions to locate (via n-ary search) and
then recover the precise nature of errors in the computation. Unlike
BitVM1, our approach does not require the creation of Merkle trees for CPU
instructions or memory words. Additionally, it does not rely on signature
equivocations. These differences help avoid complexities associated with
BitVM1 and make BitVMX a compelling alternative to BitVM2. Our approach is
quite flexible, BitVMX can be instantiated to balance transaction cost vs
round complexity, prover cost vs verifier cost, and precomputations vs
round complexity. (1)
https://bitvmx.org/files/bitvmx-whitepaper.pdf
Note that since the paper publication we have already improved the protocol
and halved the number of rounds required, and a new paper presenting these
improvements will be published soon.
With our latest optimizations, verifying a SNARK would require ~19 rounds
(38 transactions) in the worst case, consuming ~400K weight units (WU) in
total (spread over all the transactions). This is as a back-of-the-envelope
estimation, as we're still researching, and the exact resources consumed
depend on many trade-offs that can be chosen by users.
Also, if we can set an upper bound on the money a party would be willing
sacrifice (and force the other parties to sacrifice too in equal amount) to
force the protocol to be extended one more round, then we can further
reduce both the round complexity or transaction cost (~50%).
regards, Sergio.
(1) Paper authors are Sergio Demian Lerner, Ramon Amela, Shreemoy Mishra,
Martin Jonas, and Javier Alvarez Cid-Fuentes
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/5189939b-baaf-4366-92a7-3f3334a742fdn%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 3433 bytes --]
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2024-05-13 1:54 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-05-13 1:51 [bitcoindev] BitVMX: A Virtual CPU to optimistically execute arbitrary programs on Bitcoin Sergio Demian Lerner
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox