Scaling Bitcoin workshop : Stanford 2017

Discreet log contracts

Discreet log contracts


Hello everyone. I am going to give a talk about discreet log contracts. I am from MIT DCI. I work on lightning network software and discreet log contracts. A quick intro: these are pretty new. I am not sure if they work. This presentation is part of the peer review process. Maybe the math doesn't work. Please let me know. It might also work, though.

It's a system of smart contracts using bitcoin which is similar to lightning network. Hopefully I can reuse a lot of code. People can't see the smart contracts though, that's why I use the word discreet instead of discrete. One refers to discrete log problem, the other one refers to discreet as in privacy. I will talk about smart contracts, elliptic urves, schnorr signatures, and then some other aspects.

A smart contract is a conditional payment where two people put in some money and based on some external data, that money moves. In this example, Alice and Bob are betting on tomorrow's weather. Another way to say conditional payment is betting. Insurance is similar. Like whether you crash your car-- and then the insurance company gives you money. In that context, well, we'll talk about weather since it's benign. Alice and Bob are going to bet on tomorrow's weather. If it rains, Alice gets a coin. And if it's sunny, then Bob gets a coin. We do not have an OP_WEATHER opcode. So we need a smart contract.

You need an oracle. In the case of the lightning network, there is no external data. You are just sending data back and forth between the two parties. Lightning network needed those two contracts. If we want external state to cause something to happen in bitcoin, then we need something called na oracle. People have been looking at this for a while. A simple one is 2-of-3 multisig. I'll show you why discreet log contract is better. It's just 2-of-2, that means the conflict between the two parties freezes the funds forever. So they both put in 0.5 coin, and based on the weather they want some outcome. If they agree, it's great, but if not it doesn't work. And this benefits rich people because he can just indefinitely lose the coins or give you a bad deal or something. So 2-of-2 mutlisig doesn't work because they can just indefinitely bully you into some other deal at the end.

A third party can decide in cases of conflict... you can have 3 keys, Alice, Bob and Olivia. If Alice and Bob are chill they can both agree and sign and get the outcome. If they are fighting though, or offline or unresponsive, either one of them can go to Olivia and tell her hey it rained, so sign tihs. Otherwise they say, hey, it's raining, I'll give you 0.8 BTC... and then they can collude with the oracle. The oracle is corruptible. A 2-of-3 multisig oracle.. it's interactive. Not only do they see every contract but they are also deciding the outcome. They deicde everything. And they can equivocate. They can say okay it's raining and they will sign off on that.. but give a different answer to some other contract. So these oracles have a lot of power. It would be better if an oracle couldn't equivocate, and if the oracle didn't know the contract details at all.

I'll go into this real quick. Basically, schnorr signatures are a signature system that is actually easier to understand than ECDSA which is currently used in bitcoin. A little letter is a scalar, capital letters are points on an eliptic curve, make a keypar where you come up with a random number, multiply it by G a generator point a random point that everyone agrees on, then you have the Hash function H and ... the message. In schnorr signatures, you come up with a random nonce k which is similar to lowercase a, you multiply k by the generator point G to get r. This r point is used in the signature. To sign, you compute s, which is k minus the H(message) and your R point, multiplied by your private key. In schnorr signature, there's no... there's a cpaital letter that you have to compute R from k. But there's no elliptic curve math... you multiply, then you subtract all of that from k. This is all modulo a big prime number. The signature is the pair (R, s). R is a point, s is a scalar. They are both about 32 bytes. To verify a signature, given the private key and the message, you need, ... you know what R is, because that's the signature, you know what s is, that's part of the signature. You know what their public key is, and you know the message. So you take this signing equation and multiply both sides by the generator point G. So the signature is s = k - H(m, R) a. And the signature is (R, s). And to verify, s G = kG - H(m, R) (a G). Which equals R - H(m, R) * A. So that's how schnorr signatures work.

What if instead of having the public key be A and the signature having (R, s) then what about giving the public key and also making an R value at the same time. Instea dof my public key being A and my signature (R, s) I can just say my pubkey is (A, R) and my signature is s. When i'm making a public key, I'm making ... two random scalars multiplied by the generator point G. I can do the same equation with the message, get an s, and then my pubkey is twice as large, my signature is half as large. The equations are the same. This intuitively seems ot work. It's the same thing, but you can only sign once. If you signed two of the same messages with the same public key and same k value, then you can compute someone's private key. This actually happened-- this is how playstation a number of years ago... you have to make sure you don't reuse R values. This is why you should rather commit to a single pubkey and come up with a new R value. You can only make a single signature with this new pubkey this new pair. In this case, it's a good thing.

Given a new public key, a publi key which we now call (A, R) and a message m, you can't forge a signature just like in normal schnorr signature schem. But you can compute s G which is just going to be the right-hand side of the verification equation, which is R - H(m, R) A. And s * G is computable for any given message, but you don't know what s is, that's the discrete log problem. It's an unknown scalar but you know what it is times the generator point. This seems a lot like a keypair. It's not how it's traditionally used, but it's the same thing.

You can think of Olivia's signature as a private key, and s * G is a public key. Signatures as private keys. We are going to use the oracle's signature as a private key, we don't know what it is yet, but we know what it might look like .So we can add that point to our own points. Alice's public key plus this signature times generator point, we can call it a contract public key. Alice's private key, with elliptic curve homomorphism will be out the signature plus their public key... The other part you need to sign with will be the oracle's signature.

Given this new ability to sort of combine signatures and private keys to make key pairs, you can create discreet log contracts. It looks a lot like lightning payment channels. You have a funding transaction where both parties put in coins. Then you create a bunch of double spends. In lightning, you create a bunch of sequential double spends and you enforce rules through the channel that only the recent transaction is valid and broadcastable. However, in discreet log contracts, we make all 3 transactions at once and we don't know which one will be valid. It's dependent on the oracle revealing some signature in the future. Based on what the oracle signs, these public keys are now spendable. We will know the private keys for one of these outcomes.

Say Olivia signs the message "it's rainy". Olivia's signature is ... it's the partial private key for state 2. So state 2 has now been endorsed by Olivia as the correct state. And then Alice and Bob can spend from that transaction, and the other transactions will not be spendable.

In lightning, there are timing constraints where you need to watch the network to watch for whether your counterparty tries to defraud you. There are timing constraints there. In DLCs, the same party closing the contract also sweeps the funds. So the software can do both of those simultaneously. If you go offline, you're not going to lose money. Even if you make a contract for tomorrow's weather, there's no time critical thing, you can go offline.

If you have a bad oracle or evil oracle, the oracle could sign off that the weather is something else. But this is a public event. Everyone can see these wrong signatures. The oracle cannot equivocate. Can't sign both "it's sunny" and "it's rainy" at the same time. As soon as both of those signatures are known, people can compute the oracle's private key and then sign anything and then it's a race where people do a race and it's child-pays-for-parent and the money goes entirely to miners or something as part of winning that race. Also, the oracle doesn't really know that Alice and Bob are entering into this contract. So it's a lot more safe.

Another scalability aspect of this is that you can make these contracts inside payment channels. Say you have a payment channel lightning network channel... if the parties cooperate, then nothing needs to show up on the blockchain. Say you have a 50 BTC channel-- well these numbers are kind of large now. Anyway, they want to make a contract based on tomorrow's weather.. let's say we spend the transaction sequentially.. we both reduce our balances, those 10 coins get sent into another 2-of-2 multisig output, and then we construct the contract which is those 3 outputs. Now when the oracle signs with the message "rainy", then both parties say really only state 2 is the one we know the private key for now, so what they can do is that they recognize they can broadcast this and spend this utxo with state 2 transaction and then sweep these coins. So that would result in 3 transactions to the blockchain. But if they are cooperating with each other, then they can just update the balances in the payment channel and clear out the contract, and they both sign off on the new state for their channel. There's very little incentive to try to be a jerk and close the channel. You will be able to do that, but you won't be able to interact with your counterparty at the same speed anymore I guess.

How discreet are these contracts? Nobody sees naything except the counterparties. There could be thousands of contracts during the lifetime of the channel. If the contracts are broadcasted to the network, it's still not clear that there was a contract. If it's the first thing where you send to a 2-of-2 multisig then it looks a lot like a lightning network transaction. You might be able to statistically see it's different because the code path you go through in the script, in the case of lightning network, it's the recover from fraud code, but in DLCs it's the "this is the right thing happening"-- statistically, you might be able to tell.

The oracle's key is not going to show up-- you're using a publicly known signature, but also a part that nobody uses. So unless you know what key they were going to use, you can't see... involved in any way. Don't reuse public keys, use a new one each time, can't tell what's going on that way.

Weather is great, but there's probably desires to make more than 2 or 3 outcomes. So like, prices for example. You could bet on prices for like.. $1` is 25 kilo satoshis or something. So you make 100k different outputs.. since this is off-chain and between counterparties, they might each be 100-200 bytes, so this is going to be 10 megabytes or something, or maybe 100 megabytes. That's doable. Only one of them ever shows up on the blockchain, so it's not that bad. If it's a large value, that's acceptable. But we can still optimize this.

One way to optimize this is to split the R values that the oracle commits to. The oracle can say they are going to sign the price in dollars in satoshis. So they sign an exponent and a mentica. It's the number after the decimal point in a floating point number. So you can chop it up. And if there are ranges that map from possible outcomes to the same resulting balance between the two counterparties, you can squish them together. So if the price is zero satoshi or up to 100 satoshis, just give Bob the money. And if the price is 100k sat or larger, just give Alie all the money. Those are hte same. You can optimize that a bit.

You can have multiple oracles. And without telling them, you can claculate what the s * G point will be, and you just add them. This works well. No increase in size. They have to sign the exact same thing though. All the oracles have to sign the same values. So this is a bit of a drawback. You won't have an appropriate s value because they are the wrong sum. This could be a problem. If you want to do m-of-n, then you have an increase in size of the number of transactions required. You can have the oracle sign every bit of the value or something, with binary decomposition. It's pretty small.

Some use cases... I have 2 minutes. Weather, currency features, stocks, commodities, sports, insurance. You can do whatever crazy stuff, it's just conditional payments. The oracle can sign off on stuff, it can be words, numbers. But you do have to enumerate all the possible outcomes. So if it's, let's bet on the highest grossing movie next summer. But what if it's a movie you never heard of and it gets a lot of ticket sales? You might have a nlocktime transaction so if the oracle goes offline and hten something crazy happens, then you can refund the money to the two counterparties.

So yeah I've been working on that, no ICO, no token, any questions?


Q: Why can't Bob just post to the blockchain?

A: So Bob broadcasts state 1? Well, in this case, Bob loses 1 bitcoin. If it were like zero-10 and then 10-zero here, Bob has no reason to not do that. But in this case, there's still a little bit going to Bob if he cooperates and loses. He is going to lose if he broadcasts state 1 before anything happens- if he's right, he'll be able to grab the coins. But if he's wrong, Alice will be able to grab both.