The swarm client proposal - Reminder: 15 BTC pledged so far, now worth 3255$!

[Realpra]

But that is as I have been saying. Trusting any public key would not do, you would need to trust the particular public keys. i.e. You need to trade public keys with your brother in person

Not in person; I just have to ask someone online or otherwise what public key their client is running with and then putting it into my local clients "check always"-list.

I could also just make a list of all my first couple of peers while assuming they are honest - rather unlikely to get attacked RIGHT after installing BTC.

It could be entirely automatic completely safely.

You can't spend inputs. The money "available to a bitcoin address"

 (Which is not a very accurate picture) is the unspent outputs that can be redeemed by the private key related to the address. You simply add up all the unspent transaction outputs that the private key can spend. Clients will form the balance by adding up all outputs spendable by the keys in the wallet. Simple stuff then really.

You can pick my words if you want and be obtuse, but I DO understand how it works.

What I am trying to tell you is that if I sign that some outputs should be moved to your address, you cannot verify whether I have ALREADY done this with another address without keeping a record of all transactions in/out of an address.

A->ME
A->ME->B
A->ME->YOU
Merchandise->YOU->ME

That is the standard doublespend.

Only way for a verifying node to do its job in this instance is to have FULL knowledge about ME.

This is achieved in then normal client by storing A, B, ME, YOU and all others.

In my client it is achieved by storing the transactions pertaining perhaps just ME. THOSE transactions (like A->ME) would have been verified when they were added to the main blockchain.

Imagine that over 50% of the mining power is owned by people who are willing to collude to reverse transactions?

That is not something I "trust" it is something that I can look up at blockchain.info or similar to check or even block by only accepting blocks from accepted IPs  while banning all others.

The real threat of a 50% attack is quite small even should it occur.

I don't know all the details, but if you have ONE router connecting to the internet through ONE phone/fiber cable then "all" I need is to cut it and splice it into my fake internet-portal-hack-machine.

Not likely to happen though, is it?

Indeed and its the only vulnerability anyone has been able to spot in my idea and then it was fixed with PKC - like the normal client should.

[MatthewLM]

Not in person; I just have to ask someone online or otherwise what public key their client is running with and then putting it into my local clients "check always"-list.

That doesn't give safety in the situation of a complete internet connection being compromised. An attacker may be able to intercept traffic with certain words. For instance a hacker could detect an unencrypted chat message or email with "This is my bitcoin node key: ". The attacker could run software that detects the words "bitcoin", "node" and "key" and allows the attacker to modify the message. Might not be easy for an attacker of-course. But the message could be modified by anyone.

You can pick my words if you want and be obtuse, but I DO understand how it works.

No, sorry. I literally did not understand you. Sorry if you do know how it works, it just seemed you thought inputs and outputs were transferring money into and out of a particular bitcoin address. It's just the way I read it.

Only way for a verifying node to do its job in this instance is to have FULL knowledge about ME.

You brought up a problem indeed. You need to check for double spends, which are outputs being used more than once. The solution I originally gave, I guess might be yours (though there seems to be a misunderstanding with terminology). My original solution was to verify particular unspent outputs.

There is a problem. You need to make sure all transactions are verified. A single person could hide a double spend in a block from the network and release it later causing either a fork or a major block-chain reorganisation. Both things would be bad. So you need a way to ensure all transactions are validated which belong to a block. Will you get all the transaction hashes and do the hashing operations for all transactions up to the root? How can you verify that all nodes are doing the same work? You may connect to a node hiding a transaction which can produce the hidden hash. It may be after receiving the hashes, you hash the hash list, and use that to verify all your nodes have the same transactions.

The question: Is getting all the hashes efficient? Maybe where nodes validate transactions which are next to each other they can hash those parts for other nodes, and then if they receive hashes from other nodes that allow them to build the tree further they start sharing hashes closer to the root to other nodes, so that effectively the work is divided. I'm not sure how that would really turn out and there are problems where nodes are given bad hashes.

With my second solution, nodes would validate parts of the block and produce Merkle roots for those regions. By sharing the roots of the sub-trees, the Merkle root of the block can be found thus validating all transactions from the block were validated.

But this means some mechanism is still needed to check for double spends.

So what is better (or none at all): Validating for unspent outputs and then verifying the Merkle root by some other mechanism? Or is it validating sub-sections of blocks (where the merkle root for the subsections can be found and shared) and then ensuring no outputs were spent more than once. Is it perhaps some sort of mixture between the two?

Not something I can answer from the top of my head (The complexity is enormous). It may be unwise to do it at all. In that case using trusted super nodes, and trusting the highest difficulty (where miners still need to be fully validating) would be the better solution. This is the solution I'm going for for now. If someone can convince me otherwise then I'll be happy to try something different.

I should perhaps stop putting time to thinking about this anymore and work on cbitcoin and my bitcoin client software. It's interesting though and I may the one to submit a solution for using secure bitcoin connections as I'll need to create an extension to the protocol for my trusted node anyway.

[Realpra]

That doesn't give safety in the situation of a complete internet connection being compromised. An attacker may be able to intercept traffic with certai...

I was assuming that there was no attacker at first. That means the first public keys you got would not be fake ones from an attacker, but real ones the attacker would be unable to communicate by.

There is a problem. You need to make sure all transactions are verified. A single person could hide a double spend in a block from the network and release it later causing either a fork or a major block-chain reorganisation.

That would require vast computing power or your block would not be the longest chain and thus ignored.

Remember a block is only accepted if its hash fits the hash of the last block on the longest blockchain.

Unless you have 51% you can't do the attack you mention and even if you do have 51% people will soon start to block you out of the system if you keep reversing the chain or any BTC you hold will become worthless.

Both things would be bad. So you need a way to ensure all transactions are validated which belong to a block. Will you get all the transaction hashes and do the hashing operations for all transactions up to the root?

In my solution you would get one or a few branch roots while cutting the others. (search "pruning merkle tree")

This means you can tell that the transactions you verify indeed belong to the block hash even without having all the transactions of that block.

How can you verify that all nodes are doing the same work?

You cannot. For all you know your BTC client is the only one in the world doing any verification and by chance everyone else is honest.

The longest valid chain is what is being worked on.

You could theoretically do my solution, but without a reporting system; the invalid chain would loose more and more computing power as individual swarm clients got an invalid block branch.

The wasted computing power would lead to the development of a reporting system rather quickly though.

With my second solution, nodes would validate parts of the block and produce Merkle roots for those regions.

The normal client already splits up the transactions into branches and branch headers.

All you need to do to create a swarm client is to modify the code to ignore some of those branches while keeping the branch header(s) you need to re-create the block hash.

But this means some mechanism is still needed to check for double spends.

An individual swarm client will ignore the longest chain if it contains an invalid transaction and start to mine on a different chain (longest valid one).

Each invalid block will make more swarm clients break away (or ALL with a simple reporting system) and eventually the longest, but invalid, chain will become shorter again.

This will lead to a minimum of transaction reversals as all valid transactions will have been carried out on the new valid chain as well.

I should perhaps stop putting time to thinking about this anymore and work on cbitcoin and my bitcoin client software.

I am myself procrastinating somewhat

[MatthewLM]

But if you do not validate with the merkle hash:

1. You cannot validate a transaction belongs to a block.
2. You cannot validate all transactions were verified.

The problems are:

1. Someone can give nodes transactions that are not double spends and are valid but do not belong in a block.
2. A miner can hide a transaction that belongs to a block and broadcast it at a later date. Depending on the nature of the software, it could cause forks, massive chain re-organisations or double spends.

So validating the merkle hash is very important.

[Realpra]

1. Someone can give nodes transactions that are not double spends and are valid but do not belong in a block.

Yes, but validating the merkle tree is very easy even for a super light client.

Lets say I have block hash "H"->branch A and branch B.

The header of branch A is "A". There are two transactions in B; "B1" and "B2", THEIR hash is "B".

So my client would verify the transactions B1 and B2 and then check that the resulting B along with A gives H.

This tells my swarm client the following:
1. There are transactions I have NOT verified, but ONLY those in branch A.
2. I have verified everything in branch B.
3. What I have verified belongs to the block with hash H.

A miner can hide a transaction that belongs to a block and broadcast it at a later date. Depending on the nature of the software, it could cause forks, massive chain re-organisations or double spends.

Now I don't know exactly how this works, but I am assuming that the branch tip headers of the merkle tree are transactions themselves* and all subsequent headers are derived from them up until the block header itself?

If so it would be impossible to hide a transaction because swarm clients watching a specific branch (say "the left one") would report the block as invalid if there was a branch header with no transaction as root.

(Remember that faking a hash is harder than the 51% by a million times at least)

* If I am wrong about this assumption then that is a massive security whole in the official client right there.

So validating the merkle hash is very important.

Yes, but if your computer device cannot do that, it cannot run even a light client:

If there is 100.000 transactions in ONE block, then that is ~17 hashes your light/swarm client needs to do with a binary tree. That would cut off everything, but one or a few transactions that could then be verified by a swarm client.

17 operations for verifying something quite close to VISA levels of activity!

[MatthewLM]

If there is 100.000 transactions in ONE block, then that is ~17 hashes your light/swarm client needs to do with a binary tree. That would cut off everything, but one or a few transactions that could then be verified by a swarm client.

"100.000" as in 100,00 it would be this to verify all transactions by transaction hashes themselves:

500,000 hashes upwards to the root. This is because the Merkle tree is a binary tree. Then 250,000 hashes. Then 125,000 and so on.

The number of hashes required will be the number of transactions minus one.

Code:

R = root hash
H = hash
T = transaction hash

  R
 /  \
 T   T

Two transactions -> One hash.

    R
   /  \
  H    T
 / \ 
 T  T 

Three transactions -> Two hashes

     R
   /    \
  H      H
 / \    / \
 T  T   T  T

Four transactions, three hashes.

You need to verify the entire tree. You can only derive the root hash from the correct transaction hashes. Missing or incorrect transaction hashes changes the root hash. You can verify with sub-tree roots if you know that the node giving you that sub-tree root knows the transactions under that root have been checked.

To try and avoid massive operations I mentioned this:

Is getting all the hashes efficient? Maybe where nodes validate transactions which are next to each other they can hash those parts for other nodes, and then if they receive hashes from other nodes that allow them to build the tree further they start sharing hashes closer to the root to other nodes, so that effectively the work is divided. I'm not sure how that would really turn out and there are problems where nodes are given bad hashes.

[Realpra]

You need to verify the entire tree. You can only derive the root hash from the correct transaction hashes. Missing or incorrect transaction hashes changes the root hash.

My solution to that was to send the hash header of the un-verified branch.

So in your second example perhaps only H would be sent instead of the two lower Ts.

This means that my swarm client can derive the correct root from the transactions it DID get and the hashes of the branches it KNOWS it is skipping (also sent along with the transaction).

The number of hashes required will be the number of transactions minus one.

Not if you are not sending the entire tree.

If you cut off the maximum number of branches, except ONE transaction, the number of hashes you need to do to verify the transaction you ARE looking at indeed belongs in the block becomes the tree height - log2(n).

[chriswen]

I have a question.

People were talking about how it costs money through bandwith, CPU and memory for the nodes to run.

Currently, though nodes are not being compensated with anything.  And even if this is a VISA network, with 1 million dollars worth of tx fees, nodes would still not be compensated.  The money would be going to the miners.

Actually this isn't a question, but if someone could explain this.  Or if nodes are ever going to get compensated.

[kjj]

I have a question.

People were talking about how it costs money through bandwith, CPU and memory for the nodes to run.

Currently, though nodes are not being compensated with anything.  And even if this is a VISA network, with 1 million dollars worth of tx fees, nodes would still not be compensated.  The money would be going to the miners.

Actually this isn't a question, but if someone could explain this.  Or if nodes are ever going to get compensated.

So far, no one has figured out a way to pay them.  Also, the costs aren't great, and they are connecting to the network for their own purposes anyway, so why bother?

[Realpra]

Actually this isn't a question, but if someone could explain this.  Or if nodes are ever going to get compensated.

Well with a swarm/light client the load on nodes is much smaller.

Additionally full non-miner nodes are not strictly needed to run the network and may only switch on when transferring their users funds. I guess you could say their compensation is getting to use BTC much like your compensation for sharing torrent files is getting files yourself.

[MatthewLM]

I was wrong about a three transaction merkle tree. It doesn't look like this:

Code:

    R
   /  \
  H   T3
 / \ 
 T1 T2 

With Bitcoin it looks like this:

Code:

     R
   /    \
  H      H
 / \    / \
 T1 T2  T3 T3

Each level in a bitcoin merkle tree is made to be even.

But anyway, a distributed validation model may make use of a protocol change I am suggesting here: https://bitcointalk.org/index.php?topic=103295.0

This will allow transfer of merkle tree levels and segments of blocks. I'll try to make a BIP to encourage more interest (Not good with Wiki things though). This protocol change will provide improved scalability and performance for fully validating nodes but may be useful in a distributed validation model, if such a model could be made to work.

[misterbigg]

2. I am a software engineer already working on an open source project that should help the world a bunch.

Adding links in your signature to your existing open source projects would certainly help your credibility.

[Realpra]

2. I am a software engineer already working on an open source project that should help the world a bunch.

Adding links in your signature to your existing open source projects would certainly help your credibility.

Done.


Anyway everyone, I am bumping this thread as my offered reward has now grown considerably in dollar value AND I have greatly updated and modified my original post. + with us hitting the 1 mb limit and Bitcoin growing like crazy this stuff is more relevant than ever. The average fee is no longer 2 cents but 14 cents after less than one year of the creation of this thread.

I am good for the money too as I am all in BTC at the moment and hold a decent amount - and of course I am not retracting my offer.

I also included the solution to connection hi-jacking arrived at at page 3 of the thread. I have also dealt with concerns as to the too many peers overloading routers by simplifying the protocol/understanding stuff AND more importantly my originally incorrect assumption that the Bitcoin network uses addresses (it uses a complex-ish script system).

I hope my explanation is a lot more clear now that I better understand how the S-nodes should divide themselves and work.


Bitcoin is backed by nothing - it has value because it is useful... so gentlemen, what happens if it is not as useful as it could be? Pledge a few microBTC along with me, you will not miss them when your BTC are worth 3 million $ each!

[MatthewLM]

Have you reconsidered my proposal to split the blocks by the merkle tree and not by addresses and by some mechanism to identify non-address outputs? I've proposed a method for splitting blocks (though I need to update it). I think this proposal should come before the swarm client proposal as the first stage in achieving it and dealing with scalability issues that may arise: https://en.bitcoin.it/wiki/User:MatthewLM/ImprovedBlockRelayingProposal

By asking for, and relaying these "block segments", as I call them, you could validate the transactions in x-of-n segments. When you find an input referencing an output that does not exist, the node may then ask peers which own earlier segments in the block, if there is a an output. This is required because inputs can reference outputs in the same block, as long as the output comes earlier.

The idea requires trust of other peers to function, though nodes can relay the invalid transaction reports they receive, so that these reports can propagate through the good nodes. The reports don't have to only come from the nodes which specifically look at that segment.

And while it seems simple in theory, it will no doubt be problematic in practise, as I foretell.

[Realpra]

Have you reconsidered my proposal to split the blocks by the merkle tree and not by addresses and by some mechanism to identify non-address outputs? I've proposed a method for splitting blocks (though I need to update it). I think this proposal should come before the swarm client proposal as the first stage in achieving it and dealing with scalability issues that may arise: https://en.bitcoin.it/wiki/User:MatthewLM/ImprovedBlockRelayingProposal

This was how I originally split up the work and I still use this method for sending data.

However the address/script hashes must be used to split the work. The reason for this was raised earlier in the thread: If you have half the block history, but incomplete history for each address/script hash you cannot validate new transactions!

This is because the data inside a block is randomly arranged, the same address may be on the right main branch in one block and the left in another so simply looking at say the right main branch of each new block would make the S-node unintelligent.

By asking for, and relaying these "block segments", as I call them, you could validate the transactions in x-of-n segments. When you find an input referencing an output that does not exist, the node may then ask peers which own earlier segments in the block, if there is a an output. This is required because inputs can reference outputs in the same block, as long as the output comes earlier.

I mention this in the first post as a new communication protocol allowing for getting branches/segments rather than blocks.

The idea requires trust of other peers to function, though nodes can relay the invalid transaction reports they receive, so that these reports can propagate through the good nodes. The reports don't have to only come from the nodes which specifically look at that segment.

No it should not:
All S-nodes have the blockchain header hashes and all reports must include the minified branch, header and TX data of the TX that already spent the funds and made the new TX invalid.

Such reports can be instantly checked, rejected and ignored, you can't make a fake TX and link it to the block header of an existing block (or ALL of Bitcoin would be broken).

The only assumption is that out of thousands of nodes some are honest and will relay all necessary information, however the other 999 can be malicious without really slowing down or messing with the honest S-nodes.

And while it seems simple in theory, it will no doubt be problematic in practise, as I foretell.

I am more sure now than ever it can be done and my explanation at least has grown more specific, shorter and hopefully more bullet proof.

[MatthewLM]

Yes, you are right. You would need the referenced outputs, which would cause problems. Yet I don't see how your idea solves this. If you are validating particular outputs through an identification system of some sort, then you would need to be given the inputs that spend the outputs you are watching. How do inputs can relayed to the appropriate nodes? Also how do you ensure that all the transactions are completely validated, including all of the inputs?

Splitting blocks by the merkle tree solves the last problem because there should be honest nodes covering the entire merkle tree, but then you have the problem of getting the outputs. There are problems to both ideas.

[Realpra]

Yes, you are right. You would need the referenced outputs, which would cause problems. Yet I don't see how your idea solves this. If you are validating particular outputs through an identification system of some sort, then you would need to be given the inputs that spend the outputs you are watching.

Yes:
1. The spender creates a new TX that spends an output script "A" (could be an address, an IP or a multisig, we don't care)
2. Miner includes it.
3. Miner gets lucky and broadcasts entire block to the network.
4. S-node gets parts of the block that has W. addrs.
5. If the output has already been spent this S-node will know because it has been tracking exactly that scripts/addresses entire history.
6. S-node reports double spend of A and the block is rejected.

How do inputs can relayed to the appropriate nodes?

Well if we have S-node group A and B a miner or a pool of miners would then send TX data concerning A script hashes to group A and TX data concerning B script hashes to group B.

A nodes would connect only to either A or A+B nodes and so on.

Also how do you ensure that all the transactions are completely validated, including all of the inputs?

If an input is a double-spend it would get reported by the S-nodes watching that redeem script.

Splitting blocks by the merkle tree solves the last problem because there should be honest nodes covering the entire merkle tree, but then you have the problem of getting the outputs. There are problems to both ideas.

I'm not sure exactly what you mean, but basically a miner could send an incomplete block out and the S-nodes would be clueless if they only watch by scripts... yes?

So basically they need to REQUIRE full branches somehow.

Well its easy to do it, but it would cause a lot of wasteful data transmission... let me think about this. It is trivial to do it (just send the whole block :-| ) but I want to make it fast.

[MatthewLM]

Yes, you understand me, nodes need to ensure the entire block is validated, and thus that the entire block is broadcast to the appropriate nodes. Miners could also include malicious transactions which force particular nodes to do all of the work.

If you took my idea, you could add metadata to the transactions. By metadata I mean data which is additional to the transactions but provides further information about that transaction. This data could include the location of transactions referenced by the inputs in the transaction, in the blockchain (ie. block hash and transaction index). Then nodes can fetch the required transactions if needed, so they can check the outputs/inputs. They can do this if there is a way of determining what nodes should own which transactions. This means there should be a consistent method in which nodes calculate which block segments to validate and store transactions for.

[Realpra]

Ok I got it now:

Satoshi already used the hash trees to prove that if you have the block you actually have the block.

You can make various hashes and chains of the root, but it would tell you nothing new.

SO the solution is for the S-nodes to demand parts of the merkle tree. Before they receive this they will not accept the block. If another block comes along and the old ones data is difficult to get, they may switch to the new block.
Further if the S-nodes cannot get a demanded part of the merkle tree after ~10 min. of successfully polling peers (but with no data returned) they will file a report.
If other S-nodes receive 2+ of these reports they will add the merkle branch in question to their own must-have-list. If they also fail after 7 min. they will also sent a report (not before).

The merkle data received will be random:
1. If it concerns the S-nodes W. addrs. the node will save the data and re-transmit it to its same group peers.
2. If it does not concern the W. addrs it will be sent to any relevant group peers the S-node may have and will then be deleted after 6 blocks.

The S-nodes will simply want to see IF they can get this data to verify the entire block is available to the network if polled for.

Each S-node would accept only a certain maximum number of such reports and would ignore further reports.

The S-nodes will thus have 2 types of reports:
1. Double-spend report (DSR)
2. Incomplete block report (IBR)

DSRs can be instantly proven to be true so using the functionality maliciously on the entire network would be impossible. You could DDOS or falsely report to individual clients you connected to, but no one else would care.

The IBRs would behave similarly if the data was in fact available it would be sent around the network. Only if the attacked clients could NOT find the data, they would repeat the reports.
You could again attack individual clients, but if they do not repeat the report it dies there, the longer chain wins and whether they were blocked or not for a while the attacked clients go to the newer chain.

IBRs would further be ignored until the newest block header was 10 min. old.

You could overload this reporting system with fake reports so that one real report got ignored, however this would require you to be connected to 51% of the network and you would still then have to deal with any running full clients.

Yes, you understand me, nodes need to ensure the entire block is validated, and thus that the entire block is broadcast to the appropriate nodes. Miners could also include malicious transactions which force particular nodes to do all of the work.

No my reporting algorithm will solve that last part.

If you took my idea, you could add metadata to the transactions. By metadata I mean data which is additional to the transactions but provides further information about that transaction. This data could include the location of transactions referenced by the inputs in the transaction, in the blockchain (ie. block hash and transaction index).

I don't think meta data will be necessary. As long as they have the full history of the addr. spend they are verifying and have proven that the network has the entire block all should work.

They can do this if there is a way of determining what nodes should own which transactions. This means there should be a consistent method in which nodes calculate which block segments to validate and store transactions for.

I determine who should own what with S-node groups divided by redeem script hashes:
If the redeem script hash could be 0-100 then group "0-25" would handle a well defined set of address histories.

As for verifying block-availability I described above how this can be done simply. For that it does not matter who downloads what part, just that somebody reports it if they CANNOT download a part.