Output approach vs. account balance approach

[jl2012]

Satoshi adopted the "output approach" in bitcoin, which means a transaction output must be fully spent, and different outputs of the same address must be spent separately. There are some known problems of this approach:

1. scriptSig malleability: Since reference to UTXO depends on the transaction hash, scriptSig malleability will break a chain of unconfirmed transactions.

2. Not optimal for micropayment. Since outputs are discrete, it is not economical to spend tiny outputs

Here I propose a different approach, the "account balance approach"

1. Only P2SH is accepted. The scriptPubKey is simply a script hash. People will send bitcoin to addresses, just like what we are doing now.

2. Instead of storing an index of UTXO, miner will store an index of non-zero-balance-address (NZBA). When an address receives a bitcoin, miner will either create a new entry in the NZBA set (if the address did not exist) or add the received amount to the corresponding address

3. To spend bitcoin, the private key holder has to provide a signature and a script, just like the current P2SH. In addition, the sender has to explicitly indicate the amount of bitcoin to spend

4. The sender will only indicate how many bitcoin is sent to a specified address. The sender doesn't care the final balance of the recipient.

5. When a miner sees a transaction, he will hash the script and look for the corresponding hash in the NZBA set. If the spent amount is not bigger than the balance of the address, the miner will verify the signature.

6. In evaluating the balance of an address, all unconfirmed transactions will be considered. Therefore, people could spend newly received bitcoin, as long as both receiving and spending transactions are included in the same block.

7. A block is valid as long as all scripts are valid and none of the address balance is negative

This is better than the current output approach because:

1. There is no reference to txid. scriptSig malleability won't invalidate a chain of unconfirmed transaction

2. It is optimal for micropayment. An address with 100,000,000 deposits of 1 satoshi will only occupy 1 entry in the NZBA set, and could be spent as 1 bitcoin with a single signature

3. Even without micropayment, it saves space because there won't be reference of txid (32bytes) in input. Instead, the transaction value is needed which takes 8bytes. So at least 24bytes are saved for each input.

4. Change output is not needed as a account balance could be spent partially.

5. If people do not want to reuse address for privacy reason, they can always completely spend the balance of an address and create a change, just like what we are doing now. (Space is still saved because txid is not used)

However, I'm not sure if the account balance approach is as computationally efficient as the output approach (in terms of memory use etc.) Also, I'm not sure with its implication to thin clients.

Any comments?

[jl2012]

Actually 28bytes per input is saved because the outpoint=hash+index takes 36bytes.

[Sukrim]

This would severely mess with things like colored coins, maaaybe also with stuff like more advanced scripts.

Ripple implements a system like this, in case you want to take a look at a working implementation.

[instagibbs]

Proving account balances sounds quite computationally expensive.

There are no "trusted nodes" or anything like in Ripple.

Eh, guess I'm not sure.

[Sukrim]

Well, there is not much difference between balances and creating an UTXO set, also I'm not too sure what you mean with "computationally expensive". Once a transaction is considered valid, look up the involved addresses, calculate their new balances (negative balances would make a transaction invalid) by doing addition/subtraction of their "total_satoshis" field...

Another issue might be that Bitcoin does not really operate in accounts/addresses to begin with, they were introduced later and not part of the original design.

[instagibbs]

Well, there is not much difference between balances and creating an UTXO set, also I'm not too sure what you mean with "computationally expensive". Once a transaction is considered valid, look up the involved addresses, calculate their new balances (negative balances would make a transaction invalid) by doing addition/subtraction of their "total_satoshis" field...

Another issue might be that Bitcoin does not really operate in accounts/addresses to begin with, they were introduced later and not part of the original design.

Ok. I think one big issue is that without P2SH, which is recent, this scheme can't work.

4. Change output is not needed as a account balance could be spent partially.

Well I think that's still very possible with standard Bitcoin too. Right now the implicitly left out value is simply given to the miner. If you left it implicitly here you'd have to explicitly hand txn fee to miner.

I do like the idea that it's still expensive to create "dust", but cheap to claim. Cuts the cost of microtransactions in half(outputs still have to be recorded), and puts the burden on the sender.

Last thought:
Wouldn't one issue be that the person you paid could re-play a given transaction, given that the value desired still exists at an address? 

[jl2012]

Well, there is not much difference between balances and creating an UTXO set, also I'm not too sure what you mean with "computationally expensive". Once a transaction is considered valid, look up the involved addresses, calculate their new balances (negative balances would make a transaction invalid) by doing addition/subtraction of their "total_satoshis" field...

Another issue might be that Bitcoin does not really operate in accounts/addresses to begin with, they were introduced later and not part of the original design.

Ok. I think one big issue is that without P2SH, which is recent, this scheme can't work.

4. Change output is not needed as a account balance could be spent partially.

Well I think that's still very possible with standard Bitcoin too. Right now the implicitly left out value is simply given to the miner. If you left it implicitly here you'd have to explicitly hand txn fee to miner.

I do like the idea that it's still expensive to create "dust", but cheap to claim. It'd be interesting regardless.

For each input address it will use 8 bytes to indicate the amount to spend, so the difference between total input and total output will be the fee

[instagibbs]

For each input address it will use 8 bytes to indicate the amount to spend, so the difference between total input and total output will be the fee

Well you said you would have default behavior that could allow the unspent amount stay in the address. Just pointing out it's not a benefit, outside of dropping txids.

[bitfreak!]

Take a look at the mini-blockchain scheme:
http://bitfreak.info/mbc-wiki/

By saving the balance of all non-empty addresses into a database which is secured by a proof-of-work chain, the system can be made very scalable. I think Satoshi probably contemplated an account balance approach but ultimately he saw more potential for a scripting system and he liked to do everything the hard way. You get more scalability from a design like the mini-blockchain scheme but you essentially have to give up the scripting system and only allow a predefined set of transaction types. That's acceptable though because Bitcoin really doesn't make much use of the scripting system and the multi-signature issue demonstrates that you need to clearly define the necessary types of transactions before you roll out the coin.

[jl2012]

Wouldn't one issue be that the person you paid could re-play a given transaction, given that the value desired still exists at an address? 

Yes, that's a problem but I think this could be somehow solved this way:

1. For every input, a "sequence" field is added. It is a var_int ( https://en.bitcoin.it/wiki/Protocol_specification#Variable_length_integer )

2. Sender has to sign the sequence field

3. A signature is valid only if the sequence field is exactly larger by 1 than the last sequence used by the same address (i.e., for the first time to spend money from an address, the sequence must be 0; and for the second time to spend money from the same address, the sequence must be 1, etc.)

4. The NZBA set will record the last used sequence of all addresses.

Problems:

1. Each input is 1-9 bytes bigger. In most case it'd be only 1 byte unless the address is heavily reused.

2. A bigger problem is miners have to keep the record of all used addresses in the history, even the balance is 0.

3. Another potential problem is that could cause trouble for off-line wallet and thin wallet. They need some way to know the latest sequence of an address. For off-line wallet that's similar to our current situation (e.g. Armory needs a online computer to create the un-signed transaction). For thin wallet like the Android Bitcoin Wallet, there may not be a fully trust-free way to learn the latest sequence of an address.

Any other solution?

[instagibbs]

Any other solution?

Not ones that aren't probabilistic, or don't require the sender to keep track of all the nonsense. Hmm, this seems to be the biggest issue with it. Would be nice to find a nice solution.

[kjj]

Key reuse considered harmful.

[dexX7]

Take a look at the mini-blockchain scheme:
http://bitfreak.info/mbc-wiki/

If I got that right, you suggest to use a tree which stores balances, a blockchain which stores only the last n blocks and a chain of block hashes?

[jl2012]

Any other solution?

Not ones that aren't probabilistic, or don't require the sender to keep track of all the nonsense. Hmm, this seems to be the biggest issue with it. Would be nice to find a nice solution.

I think I have a solution: to have a output-based and balance-based mixed system

There are 2 types of addresses, output-based address and balance-based address. Bitcoin sent to an output-based address will be spent like the current system (i.e. identified by txid and index), while for a balance-based address it will be spent like the system proposed in OP.

There is no restriction in the redemption of output-based bitcoin. However, balance-based bitcoin must be spent with an output-based bitcoin, using SIGHASH_ALL. Therefore, the signature is not replayable because the output-based bitcoin is already spent.