Ideas / Possible SOLUTION to NEVER-ENDING BLOCKCHAIN..

[spartacusrex]

Hello,

I wanted to mention an idea for fixing the Never Ending Blockchain conundrum that hangs over us all. Simply assuming we'll be able to handle a 50 quintillion TB file, doesn't fill me, as a developer, with confidence..

I understand the protocol, I think, and so I came up with this.

Satoshi Dice is NOT A PROBLEM. He generates a lot of transactions, and miners get paid for processing tx's. That's what they do.! The fact that there is all this dust etc, is quite frankly irrelevant. The protocol allows it, so it's good.

The PROBLEM - as I see it - is that if we want to keep a record of every transaction ever, this is a BIG task. What if we changed the perpective and kept the ONLY really important piece of information.. How much each account has in unspent output txs.. ?

What I mean is this.

The Blockchain is made up of blocks, mined by the miners. I say, that the only useful blocks, are ones with UNSPENT TX outputs. If a block is only full of SPENT tx outputs, other than for the sake of posterity, and as a checking reference, that block is not really essential.

So - What if a miner could perform a special transaction, that spends UNSPENT tx outputs from earlier blocks, all from the same account, scoops them ALL UP, to say 1000 blocks behind the current block, and outputs 1 UNSPENT tx output in the latest block, for the SAME USER.?

This would sweep up all the Satoshi Dust, and all the unused spends and make, one useable SPENDABLE output tx for the same account.

You would simply remove the earlier blocks from the blockchain as they were cleared of spendable outputs..

Actually, maybe a special block that simple stores a list of [ account, IN amount, OUT amount, ] so that for reference we know the basic info, could be used to replace the much larger block which holds ALL the info.. hmm..

The blockchain would then still have the correct amount of fixed coins in it, but it would be a 'ROLLING-CHAIN' that would sacrifice it's history, but maintain balances accurately. Can a blockchain with only 1000 blocks still be verifiable ? It woud be just as hard to hack it, no?

This would make its size orders of magnitude smaller.. actually manageable by todays hardware..

The Miners would love it because they benefit from a smaller blockchain, AND they could get paid for processing that SCOOP-UP transaction.

You could say that ONLY blocks 1000 deep or more can be mined for UNSPENT txs..

This would also, rightly I think, bring in a very small, 1 Tx fee every so on, say 6 months, to keep your balance in the blockchain. As it gets shuffled up to a newer block.

I don't know if this is easily possible, but I know that nothing is impossible..

This idea may be full of holes, but may spur some lateral thinking.

Thoughts !?

[Come-from-Beyond]

Thoughts !?

Enemies of Bitcoin won't merge their coins, they'll do exactly opposite thing, so we must be able to handle the worst case scenario.

[spartacusrex]

"..merge their Coins.."

They won't have a choice.. The miners do it. And get paid, so that is the incentive..

[Killdozer]

You should develop that idea to make a more exact technical proposal. (The idea seems possible and reasonable technically, I mean.)
There are a number of solutions for the ever-growing blockchain problem, I think it is also a little alarming, how many people seem to think that it's not a problem, that it will grow forever and everyone will be happy.
A hard fork is of course inevitable for this, but this only means that the solution can perhaps be as good as it needs, since the fork will be done anyway.
But we need more exact solutions, not "basic thougths" about this, since there are a lot of them floating around.

[spartacusrex]

Absolutely..

I think we'll see a lot more 'code' action when BitcoinJ , the java library for bitcoin, is able to actually mine for blocks like the C boys. It's coming along nicely. Excellent work by Andreas..

The truth is, I think, there are a lot of good JAVA programmers who would love to get stuck in, at a protocol level.. :-)

Also - having looked around the forums, it seems that pruning spent tx outputs is a common idea.

The only EXTRA bit is the 'Clean-up' (launder?) transaction that moves all the remaining UNSPENT tx outputs to the one SPENDABLE tx output. Then we can remove whole blocks.

And you could say you can only remove blocks, if all previous blocks are removed.

Then it's starts rolling..

[calian]

Isn't this just the idea called pruning around here that's been discussed a bunch already?

[spartacusrex]

Almost..

As I said - The only EXTRA bit is the Scoop up tx, which would combine all the unspent satoshi dust.. Just pruning unspent tx's won't do that.
 

[midnightlightning]

This sounds interesting! At the basic level, you could define it thusly:

When preparing transactions for inclusion in a block, a miner will use up to N kb of the block space of the block to "refresh" old, unspent outputs: Search the blockchain, starting at the genesis block, and progressing to no further than the current height minus 52,560 (skipping blocks less than one year old: 1 block every 10 minutes => 144 blocks/day => 52,560 blocks/year), search for outputs that are unspent. If one is found, find all other outputs to that same address that are unspent anywhere in the blockchain (and have the same script as the original unspent output; non-standard script transactions wouldn't be combined with any others) up to the current height minus 1,008 (don't process blocks less than a week old, in case there's a blockchain fork at the moment). Create a new "refresh" transaction that uses all those unspent outputs as input, and assigns them a single new output.

The "refresh" transaction would have to be a new type of transaction, since the miner doesn't know the private key of the address in question, they can't fulfill the requirements to spend those outputs (even to spend it back to the same address). So a normal transaction could use the transaction ID of the "refresh" transaction as an input, but in order for clients to validate a spend of a "refresh" output, they go look up the block that has the refresh transaction, and from that, look up the inputs of that transaction individually to make sure the Script of the new transaction fulfills the requirements of the multiple inputs. In that way, the "refresh" transaction is simply an alias to several other outputs.

The N kb would have to be adjusted such that it covers all the unspent transactions of the prior year in ~25,000 blocks (half a year's worth of blocks; gives enough breathing room to ensure all transactions that need to be refreshed are refreshed in 52,000 blocks).

Using this as a guide, the goal would be that no output would be more than a year old. Non-standard Script transactions, or old adresses with only one unspent input would still get refreshed each year, to keep them up-to-date. Then a client only needs to grab the most recent year's worth of blocks (faster and less hard-drive-space-intensive than caching the whole blockchain in order to be up-to-date). If then a new transaction shows up that uses a refresh transaction as input, only then does the client need to go back to the P2P pool and request the missing block.

Using this model, someone has to have the full blockchain on hand, but most people's clients would only need to cache the most recent year's worth of blocks to be up-to-date.

If we wanted to make it where no one would have to keep the full blockchain around, that would take more thought, since what would happen if some corruption happend in the "live" blockchain that required going back to the "archived" origin of the blockchain that no one had around any more? It would be best if the clients had logic to hang on to any blocks that had transactions for addresses in the client's wallet, so they could be the peer node to share that block whenever another node needed it.

So, if Alice has address A, and in 2010 she had 10 transactions that each gave her 1 BTC, she now has 10 BTC. If Alice were then hit by a bus (sorry Alice) and falls into a coma, address A will have 10 BTC sitting in it for a while. In 2011, miners would sweep the 10 transactions to address A into one output (let's call it RO_2011 for "refresh output 2011"). In 2012, some block would take RO_2011 as input and create RO_2012. In subsequent years, this would be repeated (RO_2012 becomes RO_2013, RO_2014, etc.).

If Alice never wakes up, the blockchain now has one transaction worth of "plaque" that gets carried along year after year. Miners still have to carry it along, but no client cares about it, since it's not getting spent, so they don't have to look up the former transactions to validate it. But let's say Alice does wake up in 2015, and pays for her hospital stay with her 10 BTC (who thinks the exchange rate in 2015 will be enough to cover a 5 year coma care with 10 BTC? Anyone?). Her bitcoin client collects the most recent year's worth of blocks, and sees that RO_2015 gives address A 10 BTC, and so shows Alice that she does have 10 BTC on-hand. Alice creates a new transaction spending RO_2015 to the hospital's bitcoin address H, and sends that to the mempool. Now, whoever wants to mine that transaction needs to query the network for the block that contained RO_2014 (which RO_2015 references), RO_2013, RO_2012, and backward to the original 10 transactions that gave Alice her BTC. That action would be a slight strain on the network to validate all that, but once that completes, a new transaction that spends RO_2015 and turns it into a new (normal) output to address H. RO_2015 and back will never be needed again, and will not be refreshed any more. The new output to address H will be refreshed in 2016 if the hospital doesn't spend it, though.

Note, this falls apart if while Alice was in a coma, no client kept the blocks with RO_2011 through RO_2014. If Alice left her computer on and her Bitcoin client running, it would keep those blocks, since it knew address A was important. But if no client in the network kept those blocks, she's SOL in this proposed model. This could possibly be avoided if the Script from the original transactions were included in the Refresh transactions (standard transactions to the same bitcoin address all have the same Script, right? So only one script is needed to represent the 10 transactions originally combined), which would allow Alice to prove she can solve that Script and claim the outputs. That would add a little more bloat to the refresh transactions; is that worth it?

[spartacusrex]

Yep. Definitely prefer your choice of word..

The 'Refresh' transaction. Much better than 'scoop'.. ;-)

Very nice breakdown.

It seems the issue is the fact that no-one but the owner of the address, who has the private keys, can perform the refresh transaction. This is what causes the litter, as we wait for the original tx output to be verified.

Well, no problem.. Why not say that YOU - the owner of the address MUST perform one refresh transaction a year. I know , I know.. this will mean you can't just lock your coins in cold storage.. (unless we could forward date some tx's, that would fire if the outputs were unspent?)..

It is definitely is a little harsh, but NOT totally UNACCEPTABLE, to expect people to log in ONCE a year to "refresh their affairs" as it were. If it meant the whole network now worked, from a protocol level within definable limits, well I'm in..

Also - I think the point is, once the data is not part of the valid year long blockchain anymore, it is very hard to prove who is right when looking stuff up.. Only the current ROLLING chain is valid. I personally think this would be best, so everyone could just run the year long chain, on their PHONE, and that was it.. No records.. No History.. Scary! :-)

What happens if there are errors.. well it will have to be about 10,000 blocks deep, and I suppose stringent requirements would be placed on the validity of all the blocks together, as a whole. I think it would be just as hard/easy to screw up in either.. Getting the old transactions may be more problematic, but we would have all the transactions that mattered thousands of blocks deep to check with, not totally blind!

Need another way of simulating a user logging on once a year, to perform the 'Refresh' transaction.. hmm..

[Sukrim]

Well, a "refresh" could be viewed as audited as well, since a block with an invaild refresh transaction would be considered invalid by other miners.

Alice can (after her few years in a coma) then just use the latest client and spend the 2015 refresh transaction just like any of her unspent outputs before. Anyone else is only allowed to create another refresh transaction to the same address - but she can sign a "real" transaction with her private key and use the refresh TX as input.

I only think there would be issues with more complex transactions (depending on several signatures, revocable or whatnot), if there are only N inputs to M outputs involved, I don't see why miners shouldn't be able to use N outputs as input to a special transaction that can only have inputs from the same address and can only output to this very same address. If the 2011 "refresh" wouldn't have been valid, it wouldn't have been included in the longest chain in the first place...?

[bitfreak!]

The blockchain would then still have the correct amount of fixed coins in it, but it would be a 'ROLLING-CHAIN' that would sacrifice it's history, but maintain balances accurately.

Fascinating, I started a thread the other day which suggests a solution to this problem which is based on the same sort of concept. However my idea would require a new alt coin to be made and it works a bit differently to bitcoin in a few areas to solve this problem. I didn't really think it would be possible to alter the blockchain in such a drastic way, but your solution for discarding the stuff we don't need and "scooping" up the "dust" does provide a viable solution (assuming we accept the consequences of changing the protocol in such a way). The solution I came up with sort of avoids having "dust" in the first place because it would use a decentralized database to track the balance of all non-empty addresses, as well as using a "mini-blockchain" (what you might call a "rolling-chain" but in a slightly different sense) to provide that layer of security the blockchain provides. I'd be interested to hear your thoughts on the idea: linky. The opening post is fairly half-assed and you need to read through the 1st page to understand how the concept of a mini-blockchain developed.

[bitfreak!]

Well, no problem.. Why not say that YOU - the owner of the address MUST perform one refresh transaction a year. I know , I know.. this will mean you can't just lock your coins in cold storage.. (unless we could forward date some tx's, that would fire if the outputs were unspent?).

No no... the "special transaction" would allow miners to perform these transactions without needing the private key, but this would be the only type of transaction which the protocol would allow this to happen. It would be safe to allow it in this case since the coins wont be sent to a different address than where they originated, and they must also be of a specified age. So you don't need to bring any of this other stuff about people needing to refresh their coins (a highly controversial topic you will find), it can be done in an automated fashion by using the refresh transaction within the mining process, as you have described. I guess you could almost call it "defragging the blockchain".

EDIT: Well actually the fee does present a legitimate problem, and it would be hard to make this system work without any incentive like that. Hmm...

[whitenight639]

Interesting, I don't quite understand how miners would be able to take ownerships of the Dust addresses in the firstplace, in order for the miners to hoover up the dust and put it into spendable amounts the miners would need to be able to spend other peoples money, whats to say they could'nt do this with larger amounts?


Another Idea could be to limit spend TX's to maybe 4 decimal places? wouldn't this kill of SDs' dust creation, they can use some other method of notifying users of loosing bets (that email thing is kinda big now), I know people use micro transactions but really do we need payments to be that micro? as the currency becomes more valueble then there may be an argument for changing this but right now Bitcoin is trying to be all things to all people and its not gonna happen, we either have to increase the blocksize or reduce the dust by capping the decimals.


I don't know how hard this would be to do, but it could be encouraged by the client wallet software only being able to spend amounts to that many decimal places.

[midnightlightning]

Something I realized is that finding those "refresh"/"defragging" transactions would be a non-trivial amount of work, so it probably would be best to define them such that anyone could add them to the mempool for miners to incorporate. I'd propose the following new verification rule for submitted transactions to the mempool:

If the submitted transaction has an input that does not have a "scriptSig" (normally would be an invalid transaction), it shall be valid if ALL of the following are true (and it is otherwise a normal, valid transaction):
1. ALL the inputs have no "scriptSig" set
2. ALL the outputs that the inputs reference to have EXACTLY the same Script
3. ALL the outputs that the inputs reference are unspent
4. There is EXACTLY one output
5. The output has EXACTLY the same Script as the inputs
6. AT LEAST one input is over 52,000 blocks old
7. NO input is less than 1,000 blocks old

The first two points indicate this a "refresh" transaction, and the node submitting the transaction does not have the private key needed to unlock the Script of the input(s) being referred to. Point two allows multiple unspent outputs to be combined into one. If they are all standard transactions, they'll have the same Script to assign them to a particular Bitcoin address. If it's a custom Script transaction, it probably won't be combined with other outputs, but it can at least get refreshed. The fourth point is to prevent deviants from using this function for the opposite effect (to more fragment the inputs). Point 5 is there to progress the validation Script forward. If that continues to the new blocks in the chain, when the owner wants to spend it, it's just like spending the original transaction(s). The last two points are the time ranges for valid inputs, to prevent someone from spamming the same refresh transaction over and over (refreshing an output, then refreshing that output, etc.).

One additional piece that may be needed is to add the block hash to the definition of a transaction input. Currently it defines which output is being referred to by transaction hash and output index number. That's fine if your client cached all the blocks up to that point; you can query your local cache to find that transaction hash. But if we're now working backwards from current (rather from genesis up), there's no way to know what block that transaction was part of. To make it easier for clients, we probably need to add a block hash to the transaction input definition, so if the client doesn't have that transaction, they can know what block to ask for to get it.

Then there can be designed several "flavors" of clients: "light" clients (phones, etc.) could download one year's worth of blocks, starting at the current height. They could delete any block older than a year to keep their file usage low. If it can't find a transaction that the rest of the blockchain seems to think is valid, it can either fetch that historic block, or just flag it as "unverified" in the client.

"desktop" clients keep AT LEAST one year's worth of blocks available. They can keep more around, and on historic blocks they can search for potential "refresh" targets in their idle time (probably giving preference to addresses in their own wallet, but could be any addresses. Address that are kept in cold storage could have their public key added, so the client would work to refresh those as well). Specific companies/individuals could take it upon themselves to be "refresh" workers (another working role, in addition to "miners" in this new system), who keep older blocks and spend their time looking for refresh possibilities.

"backbone" clients keep a given chunk of the blockchain on disk. As the blockchain grows to infinity, keeping the entire chain cached to disk will grow harder, so some can organize into dedicated nodes for a chunk of the blockchain, if someone wants to take the time to back through time and verify the entire chain. Not everyone will need to keep the whole thing cached, but it would be best if somewhere in the community some organization took on that task of being the cold storage archive nodes in the P2P network to present those old blocks if needed.

[spartacusrex]

Nice. This would require a new type of tx, the refresh, that combines the unspent output txs.  I'm not sure of the ramifications of being able to combine someone else's tx outputs? Is is safe ? Seems it but you never know..

If we wanted to maintain the fact that only the private key holder can spend the cash, how about :

1) Each address is allowed ONE, and only ONE, UNSPENT tx output past a certain block from the current. The DEAD-LINE block. Say a year in the past..

2) Whenever a user has finished 'playing/paying' with his account, THEY perform the refresh tx, there and then, to refresh his account into one valid output tx that can never be deleted. If the refresh were done by the users, it would be trivial to implement. And cold storage works again. For high volume traffic like satoshi dice, you may want to choose when to refresh.

3) If a user has 2 (or more) UNSPENT tx outputs past the 'DEAD-LINE' block, the miners can choose to claim one of the outputs. To keep the money in the system equal. This repeats until the address has only ONE UNSPENT out past the DEAD-LINE block.

We may not be able to delete all the old blocks, as the single UNSPENT refresh transaction will always remain, but that doesn't REALLY matter. Barring all the daily transactions, to maintain the network, we will either have ONE block with ONE UNSPENT output per address, or one block per address, with one UNSPENT tx per block. Both seem tiny when compared to the potential size of the BlockChain..
  
Effectively - we are making people have ONE spendable tx output at all times they are away..   

[midnightlightning]

Nice. This would require a new type of tx, the refresh, that combines the unspent output txs.  I'm not sure of the ramifications of being able to combine someone else's tx outputs? Is is safe ? Seems it but you never know..

I verified what I thought about the Scripts that are attached to transactions, to verify what I was proposing: The technical way that an output is assigned to a bitcoin address it a Script that indicates "anyone who can provide a signature that matches this public key" can spend the money. The "public key" is effectively the bitcoin address, and in order to sign it, you would need the private key. All standard transactions have that same script. Which means that all standard transactions that pay the same address have the same Script. As the wiki puts it, the standard transaction output is "OP_DUP OP_HASH160 <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG". Note the only variable in there is the "pubKeyHash", which is the bitcoin public address receiving the bitcoins.

So, a handful of transactions that all use a standard means to send bitcoins to a single address will all have the same script (that's the verification step to ensure these outputs CAN be merged). If then the Script is identical on the output, the ownership of the coins hasn't changed. We don't need a new type of transaction, we just need a modification of what's considered a valid transaction (you can omit the sigScript, if these other conditions are met). In all other ways they're treated as normal transactions.

3) If a user has 2 (or more) UNSPENT tx outputs past the 'DEAD-LINE' block, the miners can choose to claim one of the outputs. To keep the money in the system equal. This repeats until the address has only ONE UNSPENT out past the DEAD-LINE block.

Ouch! No! If while Alice was in her coma, her well-meaning next of kin turned off her computer, her Bitcoin client wouldn't do the merge/refresh actions, and when she woke up she'd only have 1 BTC from one of the original ten transactions. Unless the Bitcoin clients are modified to do that merge/refresh action immediately after the recognize a new output has been given to them. But that means you need to have your client connect to the network every-so-often, and people operating out of purely web-based wallets wouldn't (unless the web-wallet provider did those merges for them).

We may not be able to delete all the old blocks, as the single UNSPENT refresh transaction will always remain, but that doesn't REALLY matter. Barring all the daily transactions, to maintain the network, we will either have ONE block with ONE UNSPENT output per address, or one block per address, with one UNSPENT tx per block. Both seem tiny when compared to the potential size of the BlockChain..

I don't think the logic quite holds up here; say Alice was diligent and every time she received bitcoins from someone, she made sure to trigger a merge transaction to keep only one output. From my original example, she effectively created RO_2011 herself in some block in 2011. Then she gets hit by that unfeeling bus and is in a coma. Now no one is going to refresh that transaction. By your rules, it will stay in the chain (miners can't claim it as their own), but that one block from 2011 now needs to be in every Bitcoin client's local block cache in order to know how much money address A has. That severely hampers the ability to prune out which blocks can be safely removed from local cache for an individual client. So, worst-case scenario, each Bitcoin client needs to keep one block per address in local cache in order to be up-to-date. Your "Both seem tiny when compared to the potential size of the BlockChain" is where the logical flaw is: since the number of potential addresses is quite large (2^160), so you might need up to 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 blocks in your local cache to be current (and each client would have to request each block and analyze it to see if it has any unspent transactions to determine if it needs to be cached or not, so they still have to fetch every block at least once). With my solution, you only ever need to fetch and store ~52,000 blocks to be up-to-date if you wanted to be a "light" client.

[spartacusrex]

I want a server & client that runs IN FULL on my phone..  

I was thinking 10,000 blocks, with a one megabyte limit on block size is 10GB. I know the limit has grown.. but it's still TINY.

And - to be fair - if Alice did get run over when her money is in the chain it's lost whatever.

No-one would 'log-out' without refreshing. It would be the last thing you ALWAYS do after accessing your coins.

The size aspect is DEFINITELY MUCH smaller that it would be with the non-refreshing. If that many addresses are used on any system it'll be big, whatever.

As you say though - if it could be done automatically - by the miners that would be nice, but we shouldn't dismiss the client side power the network has at it's disposal..

Does leaving an empty script sig leave any possible avenues of attack ?

[midnightlightning]

Does leaving an empty script sig leave any possible avenues of attack ?

My initial take on it is, "no"; if there's no script signature, you're not claiming the output as your own. Current clients would reject the transaction as invalid. If the clients were updated to check and see if the script isn't changing, and only confirm the transaction if that held up, I don't think that has a vulnerability to it.

[spartacusrex]

Will it ever run IN FULL on my phone.. ?

This would make me happy.

[midnightlightning]

What's your definition of IN FULL? I've been using "up-to-date" as an indicator of a client who is able to accurately create a new spend transaction, since it knows how many funds are in the given address.

My suggested modifications (add a block hash to the transaction input definition) allow for a client to start caching blocks at the most current end of the chain (rather than genesis block like it is now), and they could go back in time for however long we decide the "active" blockchain is, which makes the "light"/phone client able to only cache a little and yet be at full power.

Currently the owner of an address can do a "defrag"/"refresh" action to unify several outputs, and make the most recent unspent transaction more current (and therefore more likely to be included in a phone client's recent cache). However, adding in the additional validation rules for anyone to be able to propose a refresh transaction removes the onus from the owner, and gives it to the network to keep the unspent transactions recent and unified.