Is it possible to script a contract for committed savings in the blockchain?

[cunicula]

Basically, I want to create a committed savings address "*" The idea is that people pool their savings in *. No money is lost or gained in the pooling. However, people who withdraw their savings early are penalized. People who hold their savings for a long period are rewarded. It is a waiting game. People participate because they want to commit to saving for the future, but lack self-control. To compensate for their lack of self-control, they opt in to a system that offers extra rewards for waiting and extra punishments for being impatient.

For the time being assume the following (if this is possible then I'll ask about more complex situations)
a) users can only send 1 to address * and nothing else.
b) all users agree to send before anyone begins withdrawing
c) I assume that each user withdraws from a different block.


Users 1, 2, 3, ..., n send 1 from addresses "1","2","3", ...., "n" to address *. Assume their are n users to start out with. Users are ordered according to when they withdraw (though this would not be known before the withdrawal occurs).  Let 0<g<1 be a parameter governing the arrangement. Users can only withdraw once.

User 1 can withdraw g+(1-g)*(1/(n-(1-1)) from address * to address "1"  
User 2 can withdraw g+(1-g)*(1/(n-(1-1)+1/(n-(2-1)) from address * to address "2"
User 3 can withdraw g+(1-g)*(1/(n-(1-1)+1/(n-(2-1)+1/(n-(3-1)) from address * to address "3"
...
User n-1 can withdraw g+(1-g)*(1/(n-(1-1)+1/(n-(2-1)+1/(n-(3-1)+...+1/(n-((n-1)-1)) from address * to address "n-1"
User n can withdraw g+(1-g)*(1/(n-(1-1)+1/(n-(2-1)+1/(n-(3-1)+...+1/(n-((n-1)-1)+1/(n-((n)-1)) from address * to address "n"

Nothing is left behind once user n withdraws.


As an example if g=0.5 and n=10000, then user 1 withdraws about 0.5, user 6322 withdraws about 1, user 9503 withdraws about 2, user 9934 withdraws about 3, and user 9992 withdraws about 4, and user 10000 withdraws about 5.4. You can connect the dots to get the other points.

[Mike Hearn]

That seems like a rather roundabout way to achieve your goal. Why would I put any money into a pool with other people merely to lock it up for a period of time? Why should I lose money merely because some unforeseen event happened and I needed the money earlier than somebody else. I'd do better by giving control of it to a trusted third party.

It may be possible to build a system that given some money, trickles it back to you at a predefined rate. In the real world if you were willing to lose control over some money for a period of time, you'd put it into an investment fund. They usually have early exit penalties.

Anyway I'm skeptical scripts can be written that achieve the effect you want, as script has no ability to control the form of a spending transaction (and thus its value).

[cunicula]

I'm skeptical scripts can be written that achieve the effect you want, as script has no ability to control the form of a spending transaction (and thus its value).

Any other comments about whether this is possible to do or not? I am not sure what you mean by "form of a spending transaction."

Could you construct n! different n-of-n multisignature txns in advance with each txn missing one signature and distribute the entire set to the participants? Essentially, the set of n! txns accommodates every possible ordering of future events and the final signature by the nth account holder brings the event to pass. Only events that don't involve double-spends of course, so the relevant set of txns gets reduced from n! to (n-1)!, (n-2)!, ... 1 over time. There would need to be n n-of-n multisig accounts for this to work, though.

This is much too cumbersome to be practical, but it could be done for sufficiently small n. Am I wrong? Is there another way of doing this which isn't so fugly?


[Edit: Due to lack of interest, I've given up on focusing on the technical issue and ignoring the why bother question. Sorry that was arrogant of me.]

[cunicula]

Here is some info on commitment savings:

Here is a good academic review of the topic as it pertains to developing countries:
url=http://karlan.yale.edu/p/commitment-savings-product-review.pdf

Extracting one example from the article:

Jigsaw Developmentís Gold Savings account, targeted to microentrepreneurs, was
introduced in 2003 and numbers 50 accounts to date. Clients use gold as a means
of savings. Clients buy gold with a 20% downpayment, and Jigsaw lends them
the remaining 80%. They pay back with daily payment over a period of 35-70
days. Jigsaw charges an interest rate of approx. 20% for a gold loan

Note that this makes no sense from a rational perspective. The bank is holding on to the gold for the client. There is no default risk for the bank. The client could accumulate 100% of the money necessary to buy the gold and avoid paying any interest. The client pays the bank 3% of their savings [20% interest for 60 days] to have a whip held over their head.

A committed Bitcoin savings contract can achieve the same effect by taking from people who fail to meet their savings goals and distributing to people who meet their savings goals. You could pay 0% of your savings [in expectation] and still have a whip held over your head.


Making financial products cheaper by cutting out financial institutions. I thought that was what bitcoin was about. This is a simple product which could help people who have trouble saving. It is a very common problem.

It makes me sad that no one cares.

If you want to donate to help develop commitment savings programs in the developing world:
http://www.poverty-action.org/provenimpact/commitmentsavings

[Mike Hearn]

I don't think it's exactly that nobody cares, more that what you want to do is probably very complicated to implement and - as you admit - doesn't seem to make much rational sense. So if somebody has a few hours to kill and could spend those hours on various things, why should they spend it figuring out how to do what you want when there are possibly more productive things available?

[JoelKatz]

Why would I put any money into a pool with other people merely to lock it up for a period of time?

To be rewarded for your willingness to wait.

Why should I lose money merely because some unforeseen event happened and I needed the money earlier than somebody else.

Because in exchange you are rewarded if you need the money later than someone else.

I'd do better by giving control of it to a trusted third party.

How do you figure?

It may be possible to build a system that given some money, trickles it back to you at a predefined rate. In the real world if you were willing to lose control over some money for a period of time, you'd put it into an investment fund. They usually have early exit penalties.

But that won't reward you for withdrawing later, which is the whole point of this scheme.

[cunicula]

I don't think it's exactly that nobody cares, more that what you want to do is probably very complicated to implement and - as you admit - doesn't seem to make much rational sense. So if somebody has a few hours to kill and could spend those hours on various things, why should they spend it figuring out how to do what you want when there are possibly more productive things available?

a. I think this would be a very productive use of time. Look around the forum. It is filled with drug users, gamblers, speculators, and get-rich quick scheme devotees. This group bleeds money due to poor impulse control and needs impulse control technologies. I believe that a committed savings product would prove very popular.

b. Committed savings schemes are rational and welfare improving if people have time inconsistent preferences. Empirical evidence strongly supports time inconsistent preferences, but the word "rational" as used in everyday speech connotes time consistent preferences. The concept of time consistency is relevant whenever there is a tradeoff between an individual's short- and long-term objectives (e.g. going to the gym, eating, saving, attending school, avoiding addictive drugs, purchasing health insurance, etc.). When this occurs, allowing individuals to credibly commit to discipline themselves is welfare improving.

c. I imagine that you figure out the programming stuff instantaneously. My exposure to programming is limited to BASIC as a small child. To me, you're a magician, and I expect magic. Sorry about that.

[cunicula]

To be rewarded for your willingness to wait.

Thanks Joel. Even if there is very limited interest, I will feel much better knowing that someone understood.

[DannyHamilton]

Could you construct n! different n-of-n multisignature txns in advance with each txn missing one signature and distribute the entire set to the participants? Essentially, the set of n! txns accommodates every possible ordering of future events and the final signature by the nth account holder brings the event to pass. Only events that don't involve double-spends of course, so the relevant set of txns gets reduced from n! to (n-1)!, (n-2)!, ... 1 over time. There would need to be n n-of-n multisig accounts for this to work, though.

What keeps the first who withdraws from using the transaction that pays the highest amount first?  Wouldn't this create a race to be the earliest withdrawal, instead of a waiting game to be the latest? What keeps one person from signing all the multisignature transactions at once and withdrawing everything?

[cunicula]

Could you construct n! different n-of-n multisignature txns in advance with each txn missing one signature and distribute the entire set to the participants? Essentially, the set of n! txns accommodates every possible ordering of future events and the final signature by the nth account holder brings the event to pass. Only events that don't involve double-spends of course, so the relevant set of txns gets reduced from n! to (n-1)!, (n-2)!, ... 1 over time. There would need to be n n-of-n multisig accounts for this to work, though.

What keeps the first who withdraws from using the transaction that pays the highest amount first?  Wouldn't this create a race to be the earliest withdrawal, instead of a waiting game to be the latest? What keeps one person from signing all the multisignature transactions at once and withdrawing everything?

I'll go through the details which should make this clear. [tl;dr Skip to the end.]

It is easiest to start with the simplest 2x2 case, and see how it becomes fugly as people are added.

Person A and Person B have two personal addresses "Aw" and "Bw". There are two 2-of-2 multisig accounts, "a" and "b". Txns are as follows:

Aw -> 1 BTC to "a"
Bw -> 1 BTC to "b"
A signs one part of multisig txn 1 which takes inputs from "a" and "b" and sends 1.5 BTC to "Aw" and 0.5 BTC to "Bw"
B sings one part of multisig txn 2 which takes inputs from "a" and "b" and sends 0.5 BTC to "Aw" and 1.5 BTC to "Aw"
They share their partially signed txns with each other.

If A moves first, then he signs txn 2 and thus A receives 0.5 BTC and B receives 1.5 BTC.
If B moves first, then he signs txn 1 and thus A receives 1.5 BTC and B receives 0.5 BTC.

Let's look at the 3x3 case. There are now three 3-of-3 multisig accounts, "a" , "b", and "c".
Aw -> 1 BTC to "a"
Bw -> 1 BTC to "b"
Cw -> 1 BTC to "c"
A and B sign one part of 3x3 multisig txn 1.1. which takes inputs from "a", "b", "c" and sends 1.25 BTC to "a", 1.25 BTC to "b", and 0.5 BTC to Cw.
                       B and C sign one part of 3x3 multisig txn 1.2 which takes inputs from "a", "b" and sends 0.625 BTC to "Aw" and 1.875 BTC to "Bw"
                       A and C sign one part of 3x3 multisig txn 1.3 which takes inputs from "a", "b" and sends 1.875 BTC to "Aw" and 0.625 BTC to "Bw"
A and C sign one part of 3x3 multisig txn 2.1  which takes inputs from "a", "b", "c" and sends 1.25 BTC to "a", 0.5 BTC to "Bw", and 1.25 BTC to "c".
                       C and B sign one part of 3x3 multisig txn 2.2 which takes inputs from "a", "c" and sends 0.625 BTC to "Aw" and 1.875 BTC to "Cw"
                       A and B sign one part of 3x3 multisig txn 2.3 which takes inputs from "a", "c" and sends 1.875 BTC to "Aw" and 0.625 BTC to "Cw"
B and C sign one part of 3x3 multisig txn 3.1  which takes inputs from "a", "b", "c" and sends 0.5 BTC to "Aw", 1.25 BTC to "b", and 1.25 BTC to "c"
                       C and A sign one part of 3x3 multisig txn 3.2 which takes inputs from "b", "c" and sends 0.625 BTC to "Bw" and 1.875 BTC to "Cw"
                       B and A sign one part of 3x3 multisig txn 3.3 which takes inputs from "b", "c" and sends 1.875 BTC to "Bw" and 0.625 BTC to "Cw"

Note that 1.2,1.3,2.2,2.3,2.2,2.3 are all have more outputs than inputs initially, so they are not valid txns until the first move has been made. This means it is impossible to skip moves.

Outcomes are like this.
A Signs 3.1. Then either B signs 3.2 or C signs 3.3.
B Signs 2.1. Then either A signs 2.2 or C signs 2.3.
C sings 1.1. Then either A sings 1.2 or C signs 1.3.

The first signer receives 0.5, the second signer receives 0.625, and the guy who waits for others to sign gets 1.875.

For 2 participants you need 2 2x2 multisig accounts and 2*1=2 txns.
For 3 participants you need 3 3x3 multisig accounts and 3*2*1=6 txns.
For n participants you need n nxn multisig accounts and n! txns. (for n=8 that is already 40320 pre-signed txns, though only 8 of these end up in the blockchain)

My understanding of bitcoin is not very good however, so it could be that I'm breaking a rule in signing txns that aren't currently valid but may become valid in the future.

I'd like to setup something similar that is structured recursively, so that the game can be played one step at a time as a function of state variables and new participants can be added as it goes along. This would be much less fugly than having the entire game tree mapped out from the outset. But I am not sure how a recursive set-up would mesh with multisig scripting.

[Mike Hearn]

I think you have the right idea. But the way you're approaching this makes it sound like you expect some users to be offline when somebody wants to withdraw. Things get a lot simpler if you consider the fully online case first.

In a 3x scheme, if users are online and they have all paid into a multisig address then to withdraw you construct a transaction that takes the funds allocated to the 3-of-3 address, splits them into a regular payment back to yourself and then a 2-of-2 multisig output containing the rest of the value for the rest of the players. That transaction is sent to all the other players who check the size of the withdrawal, they won't sign if you're trying to withdraw too much. The players share the formula for deciding the size of withdrawals that are possible. Obviously in a real implementation you'd just send the other players your desired output script and they'd synthesize the transaction you will use and sign it, then just send back the signature, you wouldn't actually need to pass a full transaction around on the wire.

That's the online case which is easy to understand and implement. Given that so many people have always-on smartphones these days, which allow apps to be woken up remotely, the fully online case is more practical than it may seem.

If you want to allow some players to be offline, then yes, mapping out every possible route ahead of time seems like the way forward. I didn't understand what you meant when you said "There are two 2-of-2 multisig accounts, a and b". Bitcoin doesn't have accounts, and CHECKMULTISIG is order independent, so saying there are 2 different 2-of-2 multisig addresses in a system with only two players is confusing. Also nothing makes a transaction with more outputs than inputs invalid.

Let me rephrase what you're proposing. I think it's essentially the same, I'm just not quite understanding what you have written.

edit: remove discussion of SIGHASH_SINGLE as it's not necessary

It's easy to imagine that in a 3x game all 3 players create transactions for every possible permutation of withdrawals, signs them all and distributes them. The problem is that it means every player can broadcast their own choice of withdrawal transactions at any time, effectively allowing them to force other players to withdraw first and lose their money. This is a non starter.

We can fix this by having players only distribute hashes of the transactions for each level. They then distribute their signatures to the other players. The signatures are combined to create the withdrawal transaction by each player and the hashes are sent to the other players. They then co-operate in recursive subsets to create the next levels. Because they only own the hashes of the previous levels transactions it's impossible for any player to force any other player to withdraw. The act of a player broadcasting a withdrawal makes the next levels transactions spendable (non orphaned).

An example should make this clearer. They start by creating a single 3-of-3 output, say for 3 BTC.

Now each player creates a signature, for an input that connects to the 3 BTC 3-of-3 coin and a 2-of-2 output to the others, and an output to themselves:

• Player A creates sigA1 that says "only input is the 3-of-3 coin, first output is 2.5 BTC to a 2-of-2 of players B and C, second is to me".
• Player B creates sigB1 that says "only input is the 3-of-3 coin, first output is 2.5 BTC to a 2-of-2 of players A and C, second is to me".
• Player C creates sigC1 that says "only input is the 3-of-3 coin, first output is 2.5 BTC to a 2-of-2 of players A and B, second is to me".

These signatures are distributed such that player A sends sigA1 to B and C, B sends sigB1 to A and C, etc.

Now each player constructs a withdrawal transaction for round 1, assuming they withdraw:

• Player A creates txA1 that spends the 3-of-3 coin to a 2.5 BTC 2-of-2 multisig output of B and C, and a regular output for 0.5 BTC to A. He uses sigB1 and sigC1 in the input, and then adds his own signature (which covers both outputs) to complete the 3-of-3 requirement.
• Player B creates txB1 that spends the 3-of-3 coin to a 2.5 BTC 2-of-2 multisig output of A and C, and a regular output for 0.5 BTC to B. He uses sigA1 and sigC1 in the input, and then adds his own signature (which covers both outputs) to complete the 3-of-3 requirement.
• etc

Each player takes the hashes of those transactions and distributes them to the other players. Now each subset of players starts again and performs the setup procedure recursively:

• Player A and Player B co-operate to build what they need in case C withdraws first. They both create signatures that connect to the 2.5 2-of-2 (key A/B) output on HASH(txC1) and have a 1.65 BTC (?) 1-of-1 output to the other player, and one to themselves. They swap these signatures, build a transaction that spends back to themselves and then swap the hashes.
• Player A and Player C co-operate to build what they need in case B withdraws first. They both create signatures that connect to the 2.5 2-of-2 (key A/C) output on HASH(txB1) and have a 1.65 BTC (?) 1-of-1 output to the other player, and one to themselves. They swap these signatures, build a transaction that spends back to themselves and then swap the hashes.
• etc

Obviously a 1-of-1 output is equivalent to a regular output. I used the term 1-of-1 above to make the recursion clearer. Also, swapping hashes on the last level is redundant.

Eventually you bottom out of the tree and every player has all the data they need. Now they wait until somebody broadcasts a withdrawal transaction. The act of broadcasting the transaction that matches the hashes everyone else has means the transactions that connected to that withdrawal become spendable and the rest become useless.

It's pretty late and I haven't thought about this much, so it may contain errors. But I think you get the idea.

[FreeMoney]

I am interested and would possibly participate if this was actually implemented.

[keystroke]

I haven't read everything yet but I think this is an excellent idea and I would definitely participate if it existed. I would be glad to put some Bitcoins into a bounty to get this implemented.

[cunicula]

Thanks for going through the details of how to script a multistage game, Mike. It is helpful. I think that offline operation should be a goal. n! txns is too many though.

Might colored coins/smart property reduce n! to a smaller number?

Suppose that we have red, blue, and uncolored coins. Permitted operations in the multisig agreement depend on coin color. n users start out with 1 red coin. To withdraw this red coin without penalty, they need blue coins. When users withdraw red coins, they generate a penalty fee of blue coins that is sent to all other (n-1) users. Uncolored coins exit the agreement and can be freely spent.

Let {user}-i be the set of all signatories excluding i. Every type of txn is singed by the set {user}-i, so that user i can add his final signature and implement the txn at will.

Here is a list of pre-signed operations.
A) 1 (red) from i          -> 0.5 (uncolored) to i
                                -> 0.5/(n-1) (blue) to every user except i
B) 1 (red)+0.25 blue    -> 1.25 (uncolored) to i
C) x (blue) from i      -> x (uncolored) to i   (where x is any number; alternatively it could be a constant if this causes problems)

The payoffs in this game are approximately (ignoring some dependence on n):
If withdraw later than average player: 1.25
If withdraw earlier than average player: 0.75 (0.5 is obtained immediately, and 0.25 comes later from other players withdrawal penalties)

The order in which withdrawals occur no longer matters for txn scripting. It seems like you should be able to go from n! pre-signed txns to something like 3*n pre-signed txns as a result. Of course, this depends on whether scripting with colored coins is possible.

Obviously, you can generate different payoff structures by changing the numbers and types of operations.