Bit-thereum

[Rampion]

Gavin just posted an interesting post on his blog about implemeting ethereum-like features on top of the Bitcoin blockchain.

It seems like a logical step, but Gavin tells us that in order to make it, we should replace "verified by the entire network" with "verified by a set of semi-trusted 'oracles'."

How big of a trade off would that be? It seems to me that reaching the minimum amount of trust inherently possible in each type of contract is absolutely necessary.

Here goes the full post by Gavin (source: http://gavintech.blogspot.de/2014/06/bit-thereum.html)

I've been thinking about ethereum a bit recently. Parts of it are pretty interesting.

Some of it seems like needless re-engineering (like creating a new proof-of-work or a new currency). And in general, I suspect they're trying to do too much-- "complexity is the enemy of security"-- and will end up either radically reducing the scope of what they're trying to do or will get tired of playing whack-a-mole with security and DoS vulnerabilities.

But I might be wrong; maybe I'm just an old, cynical curmudgeon who has played a lot of whack-a-mole with security and DoS vulnerabilities.

Anyway, one of the ideas in ethereum I do find interesting is a contract that has funds associated with it, arbitrary code and state. Verified by the network instead of a central authority. And with transactions as a pseudo-anonymous way of triggering evaluation of the contract, paying funds held in escrow with the contract, and updating its state.

So... could we take that interesting idea and map it onto Bitcoin? Could somebody create "Bit-thereum" on top of Bitcoin as it exists today?

The answer is "yes," if we're willing to replace "verified by the entire network" with "verified by a set of semi-trusted 'oracles'."

That's cheating, though, isn't it? We're not entirely decentralized if we are trusting eleven contract-verifying-services not to collude (or all get hacked) to violate conditions encoded in some contract(s).

It is cheating a bit... but all of the really interesting complex contracts I can think of require data from outside the blockchain. Like the BTC/USD exchange rate on some future date (for blockchain-enforced futures contracts).

ethereum doesn't have some magic solution to the "data outside the blockchain" issue: as their whitepaper says, "a trusted source is still needed to provide the price ticker."  And there is already at least one startup working on a solution to the "data outside the Bitcoin blockchain" problem (Reality Keys).

Moving from one trusted source to M-of-N semi-trusted sources would be an improvement.

So I'll start there, and imagine that there are semi-trusted 'oracles' that compete to be the most reliable and trustworthy verifiers of contracts. People involved in contracts choose N of them, and then require that contract conditions be validated by one or more of them before the contract pays out. Pick more than one so no single oracle can steal the contract's funds, but less than N in case some of them go out of business or just aren't around to validate contracts when it is time for the contract to pay out.

These oracles need an agreed-upon, machine-readable contract language, but that shouldn't be hard. There are lots of interesting design decisions on what information contract scripts have access to (and lots of not-so-interesting-to-me design decisions on the language itself; is it stack-based, register-based, high-level, low-level bytecode, etc etc etc). Copying most of the ethereum contract language design (and maybe re-using lots of their code) might be a good way to go.

Maybe off-blockchain data would fetched from the web via URI. The tricky bit would be how to handle error conditions like "This contract is about average temperature in Aruba according to the World Bank, but the World Bank is no longer publishing that information."

They also need a way to store some value in escrow, associated with the contract, so that M-of-N of them must agree to any release of funds. Bitcoin multi-signature transactions could be used for that:

1. Whoever is involved in the contract gives the contract code to each of the N oracles and gets back N public keys.
2. The oracles would store the contract code and the private key, and should be willing to give out the public key to anybody who knows the contract code.
3. Anybody can then add funds to the contract by sending bitcoins into the M-of-N multisig made up of the public keys. And maybe associate some data with the escrowed funds by hashing it and include a prune-able OP_RETURN output with the hash.

So far, nothing tricky either on the Bitcoin side or the oracle's side. But what happens when it is time for the oracles to evaluate the contract and disburse some or all of the funds? What triggers the oracles to evaluate the contract (and update any state associated with the contract), and who creates and broadcasts the disburse-funds-from-escrow transaction?

Those are interesting design decisions. I'd probably have whoever is getting paid be responsible for creating the disbursement transaction, contacting M of N oracles to get signatures and then broadcast the transaction. When I say "whoever" I really mean some contract software running either in the cloud or on somebody's machine.

When to update the state associated with a contract is another interesting design decision. My intuition is a contract's state should be tied to Bitcoin transaction confirmations and the state of the transaction outputs being spent. So a contract could be in several states at once if one or more of its inputs are double-spends. Once blockchain confirmations choose one side of the double-spend or another the state of the contract would also be resolved.

I imagine the contract code would have access to all of the unspent transaction outputs (and associated OP_RETURN data, plus metadata like how many confirmations they have, which block they appeared in, maybe their merkle branch...) plus the disbursement transaction outputs. Another interesting design decision is how to handle unconfirmed transaction outputs; I suspect that letting contracts respend zero-confirmation outputs, combined with a promise from the oracles that they will never sign the same output twice might be incredibly powerful and allow all sorts of interesting applications.

Oracles could be vulnerable to denial-of-service attacks-- e.g. an attacker requesting an endless number of public keys for contracts they have no intention of fulfilling. Or an attacker requesting an endless number of contract evaluations (and signatures).

To solve the first problem, oracles could require a small up-front payment to establish a contract. And to solve the second, oracles could require that any escrow disbursement also include a small payment (they would simply refuse to sign any escrow disbursement transaction that did not include a payment to their public key). All that makes economic sense, and gives oracle operators a clear business model.

Leveraging Bitcoin transactions for the escrow/funding parts of the problem protects oracles from a whole other set of possible denial-of-service attacks; for example, "penny-flooding" a contract to make it very CPU-expensive for the oracle to evaluate would cost the attacker a significant amount of Bitcoin transaction fees.

Oracles might also put limits in their terms of service to fend off potential attackers, and collaborate to confiscate escrowed funds if an attacker created a very expensive-to-validate contract.: "Any contract that uses more than one CPU-microsecond to validate may be terminated with the funds disbursed in equal amounts to the N validating oracles."  They would maintain their reputations by publishing all of the information about the rogue contract.

But... but... doesn't it have to be more complicated than that? New Bitcoin Script opcodes? Contract code in the blockchain? A merged-mined chain or new colored coin or something?

I don't think so. Bitcoin already provides a global currency and distributed ledger-- there is no need to re-invent those wheels. Combining real-world information with Bitcoin is where things start to get really interesting.

[1713305280]

1713305280

[1713305280]

1713305280

[1713305280]

1713305280

[1713305280]

1713305280

[1713305280]

1713305280

[1713305280]

1713305280

[kolinko]

It's funny that we just published a whitepaper explaining the technical details of such a solution.

http://github.com/orisi/wiki/wiki/Orisi-White-Paper

There's also a basic implementation in the works, to be released today evening, or tomorrow.

Our team has been working on that for the past three weeks

[onemorebtc]

I think Gavin is right that any usefull contract needs outside input and this is something which requires trust.

so i do like his idea

[Peter R]

I think Gavin is right that any usefull contract needs outside input and this is something which requires trust.

so i do like his idea

I've been giving contracts a lot of thought lately and everything interesting and useful that I've come up with to date needs outside information anyways.  And that's always been the problem: right now there is no service that I can pay to sign a transaction if, for example, the London Gold fix drops below $1000 / oz in the next 12 months.  So it seems that having Oracles that compete in a "market for trust" would be very useful.

I really like Gavin's idea.  

[gmaxwell]

This subject has been a frequent one in #bitcoin-wizards.

The point I like to make is that anything you can do with script or a sufficiently enhanced script you can do with N of M oracles plus additional things (E.g. things which need secrecy or trusted I/O).   So putting something in the consensus network is merely a security improvement.   It would seem reasonable to me to expect any grand application that wants a significant script change to _first_ be implemented as N of M oracles to hammer out the use case before making the consensus system changes.

One thing I've had in mind would be to use such a system to stage any new Script2.0 for bitcoin— e.g. the oracles can just run the proposed new script directly.

There are some enhancements we could make in the Bitcoin system to facilitate oracles— for example, our multisignature system has good loose coupling, but it scales poorly: the signatures are linear in N+M. A threshold signature would be constant size— making things like 16 of 30 oracles completely practical. Though the ECDSA threshold cryptography proposed might be adequate, though it requires more communications rounds between the signers.

I have a science project grade implementation of an oracle system that I've been slowly toying with.  In mine I use the Moxie virtual machine plus some special handling for fast crypto functions, I used moxie because it's GCC targetable and an implementation of the VM is just a 1kloc switch statement— easy to audit.  My design works by the user having one or more scripts (binary inputs for the VM), which they commit to in a hash-tree. The root of the hash-tree is the ID of the script-set.   When you ask the oracle to run a script, you give it the script, it's index, and the tree fragments connecting it to the root— and also a cycle count limit which determines how much you have to pay.  Outside of the secure execution environment the oracle computes HMAC(root_hash, oracle_secret_key)  and makes the resulting value available to the script, along with the time, and other inputs provided by the user.  The script is free to then do things like generate and return a pubkey, or sign messages.  The use of the tree means that you don't have to waste the oracle's bandwidth with contingency code you never run (or lose privacy about those branches).

I didn't allow any script directed I/O in my design at all, instead, I planned on having IO done as a pre-processing stage and provided as inputs to the scripts— they're pure functions.  Turns out it's a lot easier to handle the VM security when it does no IO, it's also easier to handle resource usage when the script won't be blocking to wait on the network.

Part of my concern with resource control and IO complexity is that ultimately I'd like to have this virtual machine running inside an IBM cryptocard, with remote attestation... not just to protect the users from a cheating operator, but to protect the operator from being threatened by users that might want to try to coerce them.

I imagined the way payment would work is that you could purchase (with bitcoin) chaum tokens from the oracles for units of compute... then supply them with your scripts when you want to run them.  The oracle could maintain a work queue, constantly working on the script with the best tokens per max_cycle remaining... if you're unhappy with how long your script is taking to make it to the head of the line, you could add more tokens to it after the fact.  Though I don't know how valuable this would be to implement out of the gate— being taxed for resource would be a huge success.

There are some extra neat things you can do along these lines— Oracles are already more private than using the consensus network (absent rocket science like script-in-ZK), but you can do even better:  For a script arbitrating a transaction has a binary winner and loser where the winner takes all, you can make the script release private keys instead of signing.  By summing a public key from the oracle prior to the contract and summing the private keys after you can cryptographically blind the oracle so that it doesn't know which transaction it was deciding the fate for...

[onemorebtc]

I think Gavin is right that any usefull contract needs outside input and this is something which requires trust.

so i do like his idea

I've been giving contracts a lot of thought lately and everything interesting and useful that I've come up with to date needs outside information anyways.  And that's always been the problem: right now there is no service that I can pay to sign a transaction if, for example, the London Gold fix drops below $1000 / oz in the next 12 months.  So it seems that having Oracles that compete in a "market for trust" would be very useful.

I really like Gavin's idea. 

one trustless contract could be a just-dice copy (including bankroll investing). would be fun (i think i mentioned this in another thread as an example a while back)

but: everthying for usefull you are right: outside information is the key

[onemorebtc]

This subject has been a frequent one in #bitcoin-wizards.

I didn't allow any script directed I/O in my design at all, instead, I planned on having IO done as a pre-processing stage and provided as inputs to the scripts— they're pure functions.  Turns out it's a lot easier to handle the VM security when it does no IO, it's also easier to handle resource usage when the script won't be blocking to wait on the network.

as usual: a wonderful post to read

i like the idea of pre-staging inputs: but there can be dependencies (contract says: when weather in berlin and munich is the same compare current btc price).

the datasets may also be large (proof cpos tamper proof logs and count lines [sorry bad example])

i think the pre-staging has to be priced also.

[ThePurplePlanet]

It's funny that we just published a whitepaper explaining the technical details of such a solution.

http://github.com/orisi/wiki/wiki/Orisi-White-Paper

There's also a basic implementation in the works, to be released today evening, or tomorrow.

Our team has been working on that for the past three weeks

Nice work. Can you have ratings for oracles?

[bluemeanie1]

is it peer-to-peer?

-bm

[jl2012]

It's funny that we just published a whitepaper explaining the technical details of such a solution.

http://github.com/orisi/wiki/wiki/Orisi-White-Paper

There's also a basic implementation in the works, to be released today evening, or tomorrow.

Our team has been working on that for the past three weeks

If OP_ADD is allowed, the bulky 8-of-11 multisig is not necessary and some block space is saved

[HeliKopterBen]

is it peer-to-peer?

-bm

It sounds like more of a hybrid solution, but if you have to access external data (which adds elements of centralization anyway) then this is probably the best way to do it.  My question is how are oracles chosen?  Are they chosen dynamically, by a group of peers, or are they chosen in a more centralized way?  How oracles are chosen would probably make a big difference.

Edit:  looks like they can be chosen by users.

[benjyz]

The goal of ethereum is to replace the Internet (DNS, email, facebook, ...). It's not even remotely comparable to the goals of Bitcoin. I very much doubt that Bitcoin can move in this direction, for many reasons. I mean, for example the accounting system is a mess and is going to be removed. If not even something which is in the core can be fixed, how could one take one such large goals? The last 16 bips of 39 bips are in draft mode. The last feature update of Bitcoin is now 20 months ago.

[BetMoose]

I've been giving contracts a lot of thought lately and everything interesting and useful that I've come up with to date needs outside information anyways.  And that's always been the problem: right now there is no service that I can pay to sign a transaction if, for example, the London Gold fix drops below $1000 / oz in the next 12 months.  So it seems that having Oracles that compete in a "market for trust" would be very useful.

I really like Gavin's idea.  

We came up with a solution with the recent launch of BetMoose: we have hosts who make a commission % from correctly resolving bets. Any incorrect bets are held for payout and are currently resolved by neutral 3rd parties. We do have a centralized site but that's not necessarily a bad thing, especially when we're trying to grow the popularity and accessibility of making money from being right.

~Avalon

[Anotheranonlol]

It's funny that we just published a whitepaper explaining the technical details of such a solution.

http://github.com/orisi/wiki/wiki/Orisi-White-Paper

There's also a basic implementation in the works, to be released today evening, or tomorrow.

Our team has been working on that for the past three weeks

Very interesting. Bookmarked for later reading.
I wonder though, why not implement something like https://wiki.counterparty.co/w/Bets_and_Broadcasts#Broadcasts instead of Bitmessage?

http://blockscan.com/broadcast.aspx
http://xcpfeeds.info/search/?q=

one trustless contract could be a just-dice copy (including bankroll investing

There are some early implementations of decentralised betting applications existing, built upon the counterparty protocol you may wish to check out:
https://bitcointalk.org/index.php?topic=395761.msg7217426 Certainly sports betting is just one application.

[Mike Hearn]

Part of my concern with resource control and IO complexity is that ultimately I'd like to have this virtual machine running inside an IBM cryptocard, with remote attestation... not just to protect the users from a cheating operator, but to protect the operator from being threatened by users that might want to try to coerce them.

I think the IBM cards are basically dead, at this point. TC is now all about Intel TXT (sort of crappy) or SGX (not here yet but seems to have a much better design).

[jl2012]

Part of my concern with resource control and IO complexity is that ultimately I'd like to have this virtual machine running inside an IBM cryptocard, with remote attestation... not just to protect the users from a cheating operator, but to protect the operator from being threatened by users that might want to try to coerce them.

I think the IBM cards are basically dead, at this point. TC is now all about Intel TXT (sort of crappy) or SGX (not here yet but seems to have a much better design).

There are many discussion on TC here but I can't see any real implementation. Are all modern INTEL CPU capable to do TC?

[jgarzik]

Fundamentally, two big problems to solve are rendezvous and communication, both user/agent and agent/agent.  BitMessage attempts to solve these problems, but BitMessage has its own scaling and other code problems.

Users need to be able to find agents (oracles) in a vendor-neutral, open market manner, where one vendor may not DoS other vendors off the market.  (vendor == agent's owner/operator)

And agents need to communicate with other agents in the market.

Once we have a good, decentralized chat room for market players to congregate and communicate, it is trivial to implement M-of-N oracles.

[onemorebtc]

Fundamentally, two big problems to solve are rendezvous and communication, both user/agent and agent/agent.  BitMessage attempts to solve these problems, but BitMessage has its own scaling and other code problems.

Users need to be able to find agents (oracles) in a vendor-neutral, open market manner, where one vendor may not DoS other vendors off the market.  (vendor == agent's owner/operator)

And agents need to communicate with other agents in the market.

Once we have a good, decentralized chat room for market players to congregate and communicate, it is trivial to implement M-of-N oracles.

i think a p2p-chat could be possible if we dont try to order messages properly.
if every node just announces his contracts/services with his https-cert i dont think there is any need for ordering at all.

what do you think?

edit: for clarification:

I want to setup a contract:
 - i setup a node and write my contract
 - i specify which data i need (eg weather info)
 - i look for other nodes providing trust-info (eg an audit company or wot, even more than one)
 - weather info is only fetched from nodes which are trusted by the nodes above
 - i (optional) look for other nodes providing "contract providing"-service and copy my contract there
 - all fees must be calculated now.
 - i promote my contract and tell other people to look for this service

i want to participate in a contract:
 - i setup a node
 - i look for other nodes providing trust-info (eg an audit company or wot, even more than one)
 - i see if any of my trust-list-nodes does provide the contract i want to have (this extends as if any of the sub-services retrieves data from a source not trusted by me i cannot join)

[jgarzik]

Yes, the WoT is a common solution.  In order to scale well, WoT usually requires one or several centralizing entities that act as large signature hubs.

And even so, you still need a useful rendezvous mechanism.

[bluemeanie1]

Yes, the WoT is a common solution.  In order to scale well, WoT usually requires one or several centralizing entities that act as large signature hubs.

And even so, you still need a useful rendezvous mechanism.

LOL, a common solution?

in what exactly?

-bm