Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: Realpra on July 17, 2014, 09:40:34 PM



Title: Very very simple yet powerful 51% solution
Post by: Realpra on July 17, 2014, 09:40:34 PM
Hi.

I am the "technical speaker" for the Danish Bitcoin Foundation. I am also currently programming my own project directly interfacing with the Bitcoin protocol.

This is my proposed solution to 51% attacks, centralization issues, selfish mining and any such. This simple solution takes care of them all.
Someone could do this very quickly and I am willing to personally pledge 2000$ towards it.

The reason I don't do it is that I'm already swamped with two "public good" Bitcoin projects, a full time job and a family.

Layman's terms
1. Establish a way mining pools can document they made a block - pool IDs.
2. Let individual full nodes add or remove pool IDs to/from a "trust list".
3. A full node will not relay untrusted/unknown blocks  for ~1 hour IF 40% of the past 100 blocks were from unknown/untrusted pool IDs/ +50% from one single trusted ID.
4. A full node will not accept blocks if 99% of past 100 blocks were from unknown/untrusted pool IDs.
(exact percentages do not matter that much)

What it will do
Basically as the network is now it wouldn't do anything. Everything would be fine.

Once ~10% of full nodes upgrade miners would have an incentive to ID their blocks - simply for faster block propagation.

IF the network however came under attack such as:
A Many targeted double spends by a corrupt pool.
B Selfish mining escalation.
C No transactions in blocks.

THEN the solution would elegantly force the attacker to include at least some few blocks that could not be rolled back by the attacker and that contained transactions.
If the attacker DID not allow for other's blocks the attackers blocks would simply be ignored.

Once a "trusted" block was found the attacker can work on that and again make 99 blocks, so this is NOT a white/black list solution.

Ok so there's a catch right? It's a hard fork? Slow? Bullshit extra chains? Exotic crypto? Tatiana coin infusion? (no offense Tatiana)
No, none of the above.
There are literally ZERO drawbacks.

Technical detail
1. The protocol allows for a coinbase transaction script to have arbitrary data.
2. We can use this to let pools sign blocks with an "ID".
3. A pool would sign say the hashes of non coinbase transactions with their ID (w. SECP256k1).
4. Put the signature bytes in the coinbase transaction script.
5. This should be easy to put and read in blocks.
6. Only the pool has the PRIVATE_ID_KEY and the contents of the block are now signed.
7. The ID_PUBKEY can then be used as an ID.
8. No changes in protocol, zip, nada. Just an optional check for certain data.
9. Add the largest 20 pools to the trust list and no one ever has to talk about 51% again.
10. Its totally organic too, anyone can start a new pool and create an ID for themselves. Even botnets are still in, they just can't take over.

What it would really do:
Skeptic: I heard Bitcoin is under attack and will die?
You: Naw that can't happen because miners would then kill the coin and then... bla bla bla incentives... maybe ... bla bla bla and besides tree chains could fix it.... bla bla.
Skeptic: Huh?

--> To this -->

Skeptic: I heard Bitcoin is under attack and will die?
You: Nodes would reject that and kill it because all blocks would come from like the same dude.
Skeptic: Ah ok... is it still a ponzi though?


Title: Re: Very very simple yet powerful 51% solution
Post by: ncsupanda on July 17, 2014, 09:45:17 PM
2. Let individual full nodes add or remove pool IDs to/from a "trust list".

What's to prevent an attacker from running a full node that has them added to their "trust list"?

This could mean the entire network could prevent a pool from getting blocks just because they don't like them, unless we assume these protocols only come into place if the block finder has 51% of the network hashrate?


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 17, 2014, 09:50:38 PM
2. Let individual full nodes add or remove pool IDs to/from a "trust list".

What's to prevent an attacker from running a full node that has them added to their "trust list"?
Nothing.
Same way I can create a node where I have all 21 million coins.

It's a question of consensus, if the majority of Bitcoiners want a decentrallized Bitcoin during an attack that BECOMES the real Bitcoin.

Quote
This could mean the entire network could prevent a pool from getting blocks just because they don't like them, unless we assume these protocols only come into place if the block finder has 51% of the network hashrate?
Pools are not blocked. Its just their blocks that will not be accepted if they make all the blocks.

Its not a blacklist.

The reason it is okay to have "untrusted" blocks in the chain is that you don't care as long as you don't have frequent rollbacks and your transaction goes through.

This is why this solution ONLY cares if ALL the blocks are from an untrusted source.


Title: Re: Very very simple yet powerful 51% solution
Post by: gmaxwell on July 17, 2014, 09:58:04 PM
If you're going to remove the non-membership of mining and require certified (and ... presumably licensed by states, since the process will make it easy to pin them down) you might as well eliminate the mining, use signatures, and call it SWIFT.

There are perfectly legitimate uses for signature based systems— they have useful security/performance tradeoffs— but they're very much at odds with Bitcoin's security model. In Bitcoin mining is anonymous (in the sense that it has no membership) as part of the process of making it decenteralized and somewhat censorship resistant.

Anything that lets you tell if blocks are from the "same dude" creates hooks to force miners to only mine particular transactions.

(WRT "protocol changes", the coins produced by the coinbase transaction cannot be spent for 100 blocks)


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 17, 2014, 10:15:00 PM
If you're going to remove the non-membership of mining and require certified (and ... presumably licensed by states, since the process will make it easy to pin them down) you might as well eliminate the mining, use signatures, and call it SWIFT.

There are perfectly legitimate uses for signature based systems— they have useful security/performance tradeoffs— but they're very much at odds with Bitcoin's security model. In Bitcoin mining is anonymous (in the sense that it has no membership) as part of the process of making it decenteralized and somewhat censorship resistant.

Anything that lets you tell if blocks are from the "same dude" creates hooks to force miners to only mine particular transactions.
You are 100% incorrect you need to go up and read my post again.

I propose nothing close to what you are describing.
Anyone can mine even with no ID in my system - that includes sole mining. You have quite simply misunderstood like all of it.

Quote
(WRT "protocol changes", the coins produced by the coinbase transaction cannot be spent for 100 blocks)
I'm confused, I'm pretty sure coinbase coins are the same as other coins and I propose no change to that.. plz read before posting/voting.


Title: Re: Very very simple yet powerful 51% solution
Post by: cr1776 on July 17, 2014, 10:35:08 PM


Quote
(WRT "protocol changes", the coins produced by the coinbase transaction cannot be spent for 100 blocks)
I'm confused, I'm pretty sure coinbase coins are the same as other coins and I propose no change to that.. plz read before posting/voting.

Coinbase coins are not the same as gmaxwell stated.
You said "3. A pool would send some BTC from the coinbase to TRUST_ADDRESS.
4. In the SAME block the pool sends from TRUST_ADDRESS to where-ever."

They can't be "spent" for 100 blocks as was stated to do so would require a protocol change.


Title: Re: Very very simple yet powerful 51% solution
Post by: kolinko on July 17, 2014, 10:40:33 PM
Quote
You are 100% incorrect you need to go up and read my post again.

Actually, he's correct. It's you who should reread what you wrote. Seriously.



Title: Re: Very very simple yet powerful 51% solution
Post by: gmaxwell on July 17, 2014, 10:43:49 PM
You are 100% incorrect you need to go up and read my post again.
I read it multiple times as I did not find it clear at all.  Communications is hard. You could help me out by picking apart why some of the things I cited do not apply and that might help my understanding.

Quote
Anyone can mine even with no ID in my system - that includes sole mining. You have quite simply misunderstood like all of it.
If anyone can mine with no ID and no disadvantage what prevents every miner (including the attacker) from using a unique ID in every single block, and thus being indistinguishable?  

Alternatively, if you pin blocks based on the decisions of some of these "optional" IDs to the detriment of IDless miners, what prevents the ID-ed miners from pinning a particular otherwise-non-consensus blockchain (e.g. to enforce some economic policy in excess of the system's rules).

Quote
I'm pretty sure coinbase coins are the same as other coins and I propose no change to that.. plz read before posting/voting.
Coinbase outputs cannot be spent until they mature 100 blocks later. This addresses some incentive concerns related to miner honest and prevents a fungibility difference from the fact that recently generated coins are at greater risk of irreversible loss since they cannot be restored if they fall out of the chain in a reorg.

This is a fairly basic part of the Bitcoin system.


Title: Re: Very very simple yet powerful 51% solution
Post by: kolinko on July 17, 2014, 10:48:10 PM
(To elaborate on why gmaxwell is right)
Your solution requires "pool trust lists", or "pool ids". If I want to become a new independent miner, or a new pool, I need to get on that list. Obviously, those lists need to be exactly the same for all the bitcoin users - if a bitcoin node has a different list, then it will be running a hard fork of bitcoin, because anything after a first block mined by a pool that the node trusts, and the other nodes don't, will be a different blockchain.

Ergo, your solution requires that there be a single list of trusted pools, and that list is what people define as "Bitcoin". And if you have a closed list of pools, you can as well retire the whole proof of work, and just say that everyone on the list gets one vote on accepting/rejecting the next block.

It's not a stupid solution really - aside from SWIFT, also Ripple uses it if I'm not mistaken.


Title: Re: Very very simple yet powerful 51% solution
Post by: gmaxwell on July 17, 2014, 10:52:26 PM
It's not a stupid solution really - aside from SWIFT, also Ripple uses it if I'm not mistaken.
Right— well ripple has seemed to leave the membership process undefined (as this proposal seems to have done as well) which is probably a huge liability. ... but the whole notion of a federation of semi-trusted parties isn't a bad one— it's one I've recycled many times myself as an example of a way to do high throughput low value transactions with scale no truly decentralized system can provide. ... But I don't think that kind of the system can really be the underlying basis of a complete worldwide currency because it is still fundamentally based on trust. If it could: we would have had it already long ago— multiple-signer federation isn't a new idea relative to digital-cash.


Title: Re: Very very simple yet powerful 51% solution
Post by: kolinko on July 17, 2014, 11:01:04 PM
Quote
But I don't think that kind of the system can really be the underlying basis of a complete worldwide currency

A loose thought - what if such a system were a "sidechain" to Bitcoin?

Let's say that we run N of M oracles that hold keys to a multisig address. And oracles are running an alternate transaction system (modelled on SWIFT or Ripple, or whatever). That system would be using bitcoin as a currency (so bitcoin would still be basis for the value), but would not be blockchain based.

So now - people would trust in Bitcoin because blockchain guarantees impartiality, and security, but would use that other system for performing most transactions.

Kinda like Coinbase really, but hosted on distributed oracles :) You could imagine a day when there are a couple such competing transaction systems, and bitcoin is sent between them only when really necessary. Just like with dollar, and many banking systems holding it.

The question would be - if such a situation were to occur, and block reward was close to zero, how would the network survive? In other words - what if a majority of transactions in future happen outside of blockchain?

Another question - if by chance, one of such transaction systems, had a majority of volume, wouldn't bitcoin become a sidechain to that system really? (e.g. 99% merchants use x-bitcoin for transactions, and most people keep their bitcoin within x-coin. What happens if x-bitcoin decides to mint new bitcoins?)


Title: Re: Very very simple yet powerful 51% solution
Post by: gmaxwell on July 17, 2014, 11:23:26 PM
Let's say that we run N of M oracles that hold keys to a multisig address. And oracles are running an alternate transaction system (modelled on SWIFT or Ripple, or whatever). That system would be using bitcoin as a currency (so bitcoin would still be basis for the value), but would not be blockchain based.
Sure, this is what I'd hoped ripple would become— back before opencoin bought it and turned in into yet-another-alt-coin. (and I had to go and revise a bunch of my posts to remove recommendations to look at the ripple system when it changed entirely).  (And one of the reasons I've been concerned about proposals to raise the block size limits— a world where much of the txn volume moved to fast txn processing systems might look a lot different from ours now and may need lower limits— or very different ones— to retain security in the long term).


Title: Re: Very very simple yet powerful 51% solution
Post by: kolinko on July 17, 2014, 11:26:16 PM
Quote
Sure, this is what I'd hoped ripple would become— back before opencoin bought it and turned in into yet-another-alt-coin. (and I had to go and revise a bunch of my posts to remove recommendations to look at the ripple system when it changed entirely).

Wow, interesting :)


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 18, 2014, 07:08:23 AM
Coinbase coins are not the same as gmaxwell stated.
You said "3. A pool would send some BTC from the coinbase to TRUST_ADDRESS.
4. In the SAME block the pool sends from TRUST_ADDRESS to where-ever."

They can't be "spent" for 100 blocks as was stated to do so would require a protocol change.

Very well this is not critical. There are a multitude of ways to put data such as a signature in the blocks:
1. Coinbase transactions allow arbitrary data in their script.
2. OP_RETURN (experimental though)

I have edited my post to use coinbase data instead.

Quote from: kolinko
Actually, he's correct. It's you who should reread what you wrote. Seriously.
See above.

I apologize for my tone, I thought he had skimmed my post.

Quote from: gmaxwell
If you're going to remove the non-membership of mining and require certified (and ... presumably licensed by states, since the process will make it easy to pin them down) ...
1. I will not.
2. No state license, JUST a cryptographic signature that "TRUST_ADDRESS"-owner created this block - who-ever he is.

Quote
... but they're very much at odds with Bitcoin's security model. In Bitcoin mining is anonymous (in the sense that it has no membership)
1. Yes anonymity is important. That is why no membership is required and its just a signature the pool makes.
2. You can STILL mine with my solution as untrusted. My idea would ONLY really do something if all the blocks came from a single trusted party or from various unknown/untrusted sources.
3. It is not a proof of trust, but just proof a certain perhaps anonymous source made the block and you only care in extreme cases.

Quote
Anything that lets you tell if blocks are from the "same dude" creates hooks to force miners to only mine particular transactions.
1. Since it is only a cryptographic signature you don't know WHO it is. It could be a botnet that no one knows anything about but they just happen to make fairly normal blocks
so they get added to the trust list.
2. Miners can still mine whatever they like, this makes no change to that at all. You can still make 100% empty blocks. Only if it becomes an issue people will remove you from the trust list.

Quote
(WRT "protocol changes", the coins produced by the coinbase transaction cannot be spent for 100 blocks)
Ok so we put a signature of the block or block height into the coinbase script or somewhere else.

Quote
If anyone can mine with no ID and no disadvantage what prevents every miner (including the attacker) from using a unique ID in every single block, and thus being indistinguishable?
1. The ones adding the IDs to trust lists would be users and client developers. Random new IDs would not be in the lists. Yet there is no central authority.
2.  However if 50-60% of the network is mining with known and trusted IDs then it doesnt matter if a new pool or "attacker" makes blocks with unknown IDs/no IDs they will still be accepted.

Quote
Alternatively, if you pin blocks based on the decisions of some of these "optional" IDs to the detriment of IDless miners, what prevents the ID-ed miners from pinning a particular otherwise-non-consensus blockchain

1. You still have to follow protocol, it would be impossible to change rules.
2. There is ONLY detriment to ID less miners if they combined make 40% + of all blocks otherwise all are equal.
3. Again users choose which IDs their client should trust so who is ID-ed/trusted miners can change instantly during an attack.


Title: Re: Very very simple yet powerful 51% solution
Post by: heartbit on July 18, 2014, 07:41:56 AM
Anyone can mine even with no ID in my system - that includes sole mining.

So... if a miner had 51% of the network, couldn't a "bad" mining pool simply set the ID on half of their miners to be "no ID" - so then it would look like they only controlled 25% of the network... when in fact, they would control over 50%.

Which would be effectively the same as the current situation where GHash publicly controls 40% of hashrate - and I've read claims (not saying true or false, just that some people claim) they also control another 10-15% of "unknown" miners.

Sorry if I've misunderstood.


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 18, 2014, 08:11:31 AM
Anyone can mine even with no ID in my system - that includes sole mining.

So... if a miner had 51% of the network, couldn't a "bad" mining pool simply set the ID on half of their miners to be "no ID" - so then it would look like they only controlled 25% of the network... when in fact, they would control over 50%.

Which would be effectively the same as the current situation where GHash publicly controls 40% of hashrate - and I've read claims (not saying true or false, just that some people claim) they also control another 10-15% of "unknown" miners.

Sorry if I've misunderstood.
No, because if they are removed from the trust lists then their blocks and all other untrusted / no ID blocks would be counted as one partition w. +50% and these new clients would start to not relay their blocks.

You can still do some double spend attacks in my solution, but there is an upper limit introduced and total control becomes impossible.


Title: Re: Very very simple yet powerful 51% solution
Post by: kolinko on July 18, 2014, 10:24:05 AM
What happens if some clients have a trust-list different than some other clients? There will be two separate and incompatible blockchains then, right?

E.g. some nodes/clients include a pool A, but not B. Some nodes/clients include B, but not A. But everyone includes C, and nobody includes D.

After a short while there's a situation like this:

ABCD (so, first block mined by A, second by B, third by C..)

Then "A" mines a block. Part of the network accepts it, part of the network doesn't trust A, and rejects it, because it was right after D which is also untrusted. So now we have:

ABCDA - some clients consider this the longest block
ABCD - some clients consider this the longest block

But then "B" delivers a new block to "ABCD" (because "B" doesn't trust "A" either, so it doesn't consider "ABCDA" the longest blockchain), so it's now:

ABCDA - some clients believe this is the only valid blockchain
ABCDB - some clients believe this is the only valid blockchain

aaaand we have a hard fork. Some clients use one blockchain, some clients use another blockchain.

In other words still - clients having different trust lists would lead to a hard fork of blockchain.


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 18, 2014, 03:16:07 PM
What happens if some clients have a trust-list different than some other clients? There will be two separate and incompatible blockchains then, right?
Yes and no.

This concern is why my solution would have two different "punish modes":
1. At ~40% of blocks untrusted the client will just not relay another untrusted block for 1 hour.
So longest chain is in this case still accepted even if it is 90% untrusted. However propagation would be slower for the untrusted pools in this case.
2. Outright rejection that you mention. It would ONLY happen if something like ~99% of the last ~100 blocks are untrusted.

So the hardfork situation you describe could happen, but ONLY if the majority of nodes A Do not have ANY trust overlap and B 99% of blocks are untrusted by both partition 1 and 2 clients using your own example.

Mode 1 makes centralization harder and mode 2 prevents a total denial of service by a single player preventing all transactions.


Title: Re: Very very simple yet powerful 51% solution
Post by: jl2012 on July 18, 2014, 04:00:10 PM
Anyone can mine even with no ID in my system - that includes sole mining.

So... if a miner had 51% of the network, couldn't a "bad" mining pool simply set the ID on half of their miners to be "no ID" - so then it would look like they only controlled 25% of the network... when in fact, they would control over 50%.

Which would be effectively the same as the current situation where GHash publicly controls 40% of hashrate - and I've read claims (not saying true or false, just that some people claim) they also control another 10-15% of "unknown" miners.

Sorry if I've misunderstood.
No, because if they are removed from the trust lists then their blocks and all other untrusted / no ID blocks would be counted as one partition w. +50% and these new clients would start to not relay their blocks.

You can still do some double spend attacks in my solution, but there is an upper limit introduced and total control becomes impossible.

You didn't answer the question. A miner holding 60% of hashing power could pretend to be 10 independent miners with 6% power each.


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 18, 2014, 04:38:18 PM
You didn't answer the question. A miner holding 60% of hashing power could pretend to be 10 independent miners with 6% power each.
Yes he could.

However the assumption is that if he either
A. Started to do doublespends via chain rollbacks.
B. Started to only allow his own blocks.
It would become obvious that these 10 fake pools were in fact colluding and people would remove them from their trust lists and start to delay them/reject them.
(The clients today already have automatic alarms for 2+ blockchain forks I believe)

In other words one single honest entity could control 100% of the mining power in my system and no one would necessarily know about it.
However as long as no attacks are taking place we don't care.


Title: Re: Very very simple yet powerful 51% solution
Post by: Nicolas Dorier on July 19, 2014, 10:22:02 AM
Quote
1. The ones adding the IDs to trust lists would be users and client developers. Random new IDs would not be in the lists. Yet there is no central authority.
2.  However if 50-60% of the network is mining with known and trusted IDs then it doesnt matter if a new pool or "attacker" makes blocks with unknown IDs/no IDs they will still be accepted.

So, in your system each individual decides what ID is trusted, which is good.
But the question is : with millions of potential different node at a single point of time, how do you keep track of your "trusted" nodes.

To fix the problem, such individual will be tempted to use a list provided by someone else, who will decide who is trusted on its behalf.
When sufficient people give right to "act on its behalf" we will tend to a centralized repo of trusted ID.  If he does not use a centralized repo of trusted ID, then he will be able to keep track of only a small number of them.
Also making a new node would be impossible, because you would need to convince everybody to put you in the trust list. (especially when, as you said in your example, there is only 20 of them)
This is a major barrier of entrance that keep competition out, and thus protect current mining pools. Your solution, in my mind, protect mining pools instead of increasing decentralization.

I would opt for another idea, the untrusted list. If a pool get 51% you put it in untrusted to shrink its profit and thus processing power.
However, such solution can be so easily worked around by a mining pool by hidding everything that can identify itself, that it is not worth implementing. (But could do easily if you really want)



Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 19, 2014, 03:19:41 PM
1. Establish a way mining pools can document they made a block - pool IDs.

This tweet (https://twitter.com/adam3us/status/484295259439243264) by @adam3us (Adam Back) may interest you.
Quote
@coindesk @jgarzik @BitPay miners anonymity needed to protect payment neutrality policy, this gives irrevocability hence low tx cost we want


Title: Re: Very very simple yet powerful 51% solution
Post by: Carlton Banks on July 19, 2014, 05:59:03 PM
Sounds pretty much like a way of giving nodes the ability to do a DOS attack against miners arbitrarily.

And it's much worse than the hashing share 51% attack, as the resources you need to do it and succeed are: as many copies of bitcoin core running as possible, attaching untrusted status against miner IDs that are behaving in the interests of the network. It makes an attack against the network much much cheaper, especially if your flooding attack distrusts every single miner, then there's no blocks.


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 19, 2014, 10:32:12 PM
So, in your system each individual decides what ID is trusted, which is good.
But the question is : with millions of potential different node at a single point of time, how do you keep track of your "trusted" nodes.
My system would keep track of pools not nodes. There are about 8000 nodes, but only 20 pools have the vast majority of hashing power.

Quote
This tweet (https://twitter.com/adam3us/status/484295259439243264) by @adam3us (Adam Back) may interest you.

BitPay miners anonymity needed to protect payment neutrality policy, this gives irrevocability hence low tx cost we want
A cryptographic reputation ID is not the same as knowing who the miner is.

Miners would still be as anonymous as ever in this system.

Quote
And it's much worse than the hashing share 51% attack, as the resources you need to do it and succeed are: as many copies of bitcoin core running as possible, attaching untrusted status against miner IDs that are
This wouldn't do anything. The normal network would just continue.

Even if I run a thousand nodes today saying have 1 million the network would ignore me and this is no different.


Ok I'm a little annoyed that no one understands this/have found any flaws in it, yet they are confident to vote it wouldn't work. I think I came to the wrong place with this.


Title: Re: Very very simple yet powerful 51% solution
Post by: temen on July 19, 2014, 11:20:02 PM
Don't give up ;)

resisting of change is just human and every great thinker and visionary has suffered from public opinion. If people vote for no it doesn't mean that you're wrong about this.

I think this as good idea but my script blockers dont show any voting system on screen


Title: Re: Very very simple yet powerful 51% solution
Post by: taylortyler on July 20, 2014, 04:31:33 AM
2. Let individual full nodes add or remove pool IDs to/from a "trust list".

What's to prevent an attacker from running a full node that has them added to their "trust list"?

This could mean the entire network could prevent a pool from getting blocks just because they don't like them, unless we assume these protocols only come into place if the block finder has 51% of the network hashrate?

You in Raleigh?


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 20, 2014, 01:41:09 PM
A cryptographic reputation ID is not the same as knowing who the miner is.
Miners would still be as anonymous as ever in this system.
...
Ok I'm a little annoyed that no one understands this/have found any flaws in it, yet they are confident to vote it wouldn't work. I think I came to the wrong place with this.
Hi Realpra,

No intent on my side to sabotage your work and I think it's the same for the others commentators. I truly apologize if you felt things that way. Comments/critics can sometimes be done in a very positive spirit, in order to strengthen an idea.

WRT to my quote, I think you misunderstand what gmaxwell & adam3us mean by anonymity. I think it's not about knowing the name of a miner (or whatever personal data) but it's related to anything which identifies the miner (even if it's just a reputation id). Well, I'm not an expert and I may be wrong in my interpretation. May be you should submit this idea to adam3us.

Anyway, I fully support your effort to address a difficult and important subject. Keep up the good work !


Title: Re: Very very simple yet powerful 51% solution
Post by: gmaxwell on July 21, 2014, 06:12:48 AM
WRT to my quote, I think you misunderstand what gmaxwell & adam3us mean by anonymity. I think it's not about knowing the name of a miner (or whatever personal data) but it's related to anything which identifies the miner (even if it's just a reputation id).
Right "anonymous" in this context is about participation having "membership", not about privacy (though anonymous and anonymous do sometimes go hand in hand).  Sorry about that, it's a bit of terminology overload that occurs in the literature.


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 21, 2014, 05:11:45 PM
Realpra's proposal has activated the "thought experiment" mode in my brain.  ::)

For now, there's nothing in the protocol like the pool id suggested by OP.
But we can see that addresses used by mining pools for coinbases outputs play a very similar role, since most mining pools reuse the same address.
I guess that bc.i builds its statistics with a heuristic based on this behavior.

From this observation, we could imagine that some full nodes decide to use their custom version, implementing custom rules to broadcast blocks (like those proposed by OP) according to the address appearing in the coinbase.

One could argue that mining pools could defeat this strategy by using a new address for each block.

That point leads me to a weird idea.

Could we imagine that some actors decide to create pools of full nodes (PFN) organized with the following principles:
  • some nodes in the pool have a special role: they're also member of a mining pool and act like "trojan horses". They broadcast informations to the PFN, allowing to identify future blocks created by the mining pool (like the new address used by the mining pool -or anything that can be used to identify the block-).
  • a central node could be used to gather informations retrieved by first nodes and notify others nodes about the policy (which blocks must be broadcast or "penalized").
  • the others nodes are just here to apply the policy by broadcasting or not the blocks. PFNs with large number of nodes are more powerfull since they have more impact on the propagation of blocks*

What kind of policy these kinds of pools would apply ?
  • "Regulation" of mining pools as proposed by the OP
  • "Pay for broadcast" fee: the number of PFN nodes which broadcast a block is proportional to a fee paid by the mining pool to the PFN. This fee could appear in the block as an output of the coinbase transaction sent to a given address**. This fee would be used by the PFN to fund the running nodes and get some profits.
  • A mining pool funds a PFN to penalize its concurrents (that's bad).
  • ...

Don't get me wrong. I don't say this is a good idea. May be it just opens the Pandora's box.
I just wonder if this kind of model could emerge and what are the possible outcomes (positive or negative).
The advantage of thought experiments is they don't break anything.


*: If I'm right, cost of running a full node is estimated to 20$/yr. I don't know what is the threshold for a PFN to be considered as having a significant impact but 80k$/yr to own 50% of the actual network doesn't seem like a huge cost for a funded company expecting some profits from this activity.

**: The agreement between the mining pool and the PFN could also be hidden. The fees being periodically paid, using normal transactions.


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 24, 2014, 06:53:04 AM
Hi Realpra,

No intent on my side to sabotage your work and I think it's the same for the others commentators. I truly apologize if you felt things that way. Comments/critics can sometimes be done in a very positive spirit, in order to strengthen an idea.
I welcome all the comments and the technical feedback. Its the votes I don't understand who seemingly know some technical detail the rest of us do not.

I suppose I should not put too much weight to random votes on a forum.

WRT to my quote, I think you misunderstand what gmaxwell & adam3us mean by anonymity. I think it's not about knowing the name of a miner (or whatever personal data) but it's related to anything which identifies the miner (even if it's just a reputation id). Well, I'm not an expert and I may be wrong in my interpretation. May be you should submit this idea to adam3us.
If the ID is created by the miner signing the transactions except the coinbase transaction then you could have "Signers" who would only create blocks and sign them.
Then they would publish this block of transactions and the signature.

Then any miner could become "trusted" by just mining these same transactions and including the signature. A single trusted "Signer" would mean that every miner could mine entirely anonymously.

I don't know if you are wrong in your interpretations, but I do not think my system would cause any problems with anonymity of miners. They used reputation IDs on Silk Road and Bitcoin itself is "only" pseudonymous.


But here is the thing: My idea is possible NOW, no changes required. I think we established that much in the thread though I had to change things a little. So if we have a group tomorrow running this kind of "reputation client" and another running the normal clients no one would notice.
There could only be two outcomes:
1. The reputation client works the best during an attack and everyone switches.
2. The normal clients work the best during an attack and everyone switches.

2000$ to whoever codes it. (Contact me for "it" details)


Title: Re: Very very simple yet powerful 51% solution
Post by: gmaxwell on July 24, 2014, 08:08:29 AM
If widely used this "solution" would be hazardous to the network: in cases where it would do anything at all it would cause severe consensus splits (and the resulting reorganizations of length long enough to permit successful double-spending), without some centralized process to ensure complete uniformity of the "approved list" even users of this approach could become consensus-split and it would encourage miner consolidation and registration with an approval authority to avoid being on the losing side of such a split / or suffering block delay 'punishment'. It would almost certantly result in taking the currently broken status-quo where there are only a few miners at all and nearly setting it in stone, and it would set us up for an ugly path where miners now had identities and it was interesting to start talking about other restrictions for them.

Ignoring the wrongheadedness of the overall design for a moment, the actual proposed implementation is still broken:
Quote
Ok so we put a signature of the block or block height into the coinbase script or somewhere else.
You cannot include a signature of the block into the coinbase because the block (which includes the coinbase) cannot be modified once it is mined. If you include a signature of the height than once a block has been released at that height an attacker can just move it into a new block they mine at that height— impersonating them with the rebinding.  ... this sort of thing can be fixed, but if you cannot get right even some of the boring details why do you think you have a overall design that does anything except causes harm?

While I fully support someone taking realpra's money, if he keeps insisting after having these things explained to him, do so with no expectation of adoption. I certantly would have nothing to do with any project distributing an approved miner ID list, since influence over would be a risk to my personal health and welfare (not to mention that of the Bitcoin system), and I'm confident that very few people would be foolish enough to run such software.


Title: Re: Very very simple yet powerful 51% solution
Post by: azeteki on July 24, 2014, 09:48:07 AM
I don't think this can work at all.
If it even can work, what you'd have at the end would no longer be Bitcoin.

First of all, everyone needs the same trust list.
'it only takes effect if 99% of blocks are untrusted' is the case you're actually defending against.
So it needs to work and not cause consensus failure, however rare it may be.

Same deal for relaying. You would have to block acceptance in addition to relaying.
Otherwise, you'll have a local chain that you refuse to share with anyone else, orphaning yourself from portions of the network.
Even if you do so, you'll still end up with disagreement on the latest blockhash.
The network would gather into forks with similar enough 'trust lists', until a disagreement is found and it splinters even further.
Adding or removing items would require going back over the entire chain, since you could have refused a block that you've now decided to trust.
Unless you have rules like 'only trust ID x after date x'.

Secondly, assuming the above wasn't an issue somehow:
I don't see how anyone (whether it's an individual user, or a group acting on behalf) could maintain a reasonable trust list.
Allow too many ID's, and that could potentially mean a single mining entity has tons available to them.
Allow too few, and you block legitimate miners from the network (ultimately centralising Bitcoin even further).

Both of the above issues ignore the issue of how to uniquely identify users over the network (basically, one vote one miner).
If you can solve that, you don't really even need PoW. Just have a distributed vote.


Title: Re: Very very simple yet powerful 51% solution
Post by: azeteki on July 24, 2014, 10:12:47 AM
Also, as gmaxwell alludes to above; arguably a consensus failure is worse than a short-ish miner-induced reorg.

While you have two competing chains, anyone with a small amount of technical know-how is able to spend on both chains, abusing anyone who hasn't figured out there's a fork yet.


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 24, 2014, 02:16:43 PM
But here is the thing: My idea is possible NOW, no changes required. I think we established that much in the thread though I had to change things a little. So if we have a group tomorrow running this kind of "reputation client" and another running the normal clients no one would notice.
There could only be two outcomes:
1. The reputation client works the best during an attack and everyone switches.
2. The normal clients work the best during an attack and everyone switches.
2000$ to whoever codes it. (Contact me for "it" details)
It does not sound to me like a good strategy for several reasons:
  • I like your enthusiasm but you can't simply erase the concerns voiced by others commentors about the risk of consensus splits.
  • main network is a production environment. I'm not sure that 51% problem can be tested in testnet and testing ideas in prod. env. is EVIL
  • I think that you define a wrong objective for your test (which client works the best). The objective should be to determine if the network works better when it includes a proportion of your client. Question: which proportion of your client is required in the network before we start observing its influence ?

On my side, I think the proposed solution has several flaws, but if you want to go forward with this idea, your first step should be to create a network simulator which proves that the concept doesn't harm the network. This kind of simulator should be open, allowing anybody to check and validate that assumptions are correct and that the solution doesn't harm the network.

A network simulator (https://github.com/ebfull/ebfull.github.io) has already been developed in javascript. May be you can reuse it for your needs. There's also netlogo (https://ccl.northwestern.edu/netlogo/) which is a nice environment to prototype simulations.



Title: Re: Very very simple yet powerful 51% solution
Post by: azeteki on July 24, 2014, 02:28:31 PM
Question: which proportion of your client is required in the network before we start observing its influence ?

Without some sort of additional bootstrap condition? Until miners begin to include an ID, nothing happens and anyone using this client is twiddling their thumbs.

3. A full node will not relay untrusted/unknown blocks  for ~1 hour IF 40% of the past 100 blocks were from unknown/untrusted pool IDs/ +50% from one single trusted ID.

'ID clients' would simply act as dumb receivers because blocks do not have ID's yet.

4. A full node will not accept blocks if 99% of past 100 blocks were from unknown/untrusted pool IDs.

'ID clients' would sit at block 100 forever. Or at 'checkpoint_block' + 100.

With a bootstrap condition and assuming miners actually began to include ID's then you enter all of the issues listed earlier re: consensus falling apart.

It's at the brainstorm level; it's not a proposal yet.


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 24, 2014, 03:33:59 PM
@azeteki

Indeed. My question was more related to the 2nd scenario (miners include IDs in blocks).
The main effect of OP's idea is to slow down the propagation of blocks. Thus, it seems logical that for a given network topology, the strength of this effect would depend on the number of 'Ids nodes' using OP's solution.

Connections among peers in bitcoin network are evenly distributed to create an expander graph and to avoid hub nodes which are prone to targeted attacks (see part of this thread (https://bitcointalk.org/index.php?topic=632124.msg7056252#msg7056252) related to bitcoin network topology). If we imagine a solution which doesn't break the consensus, I think it would require a given proportion of 'Ids nodes' to reach the initial goal (rejection of blocks by the whole network).


Title: Re: Very very simple yet powerful 51% solution
Post by: DeathAndTaxes on July 24, 2014, 03:56:17 PM
@azeteki

Indeed. My question was more related to the 2nd scenario (miners include IDs in blocks).
The main effect of OP's idea is to slow down the propagation of blocks. Thus, it seems logical that for a given network topology, the strength of this effect would depend on the number of 'Ids nodes' using OP's solution.

Connections among peers in bitcoin network are evenly distributed to create an expander graph and to avoid hub nodes which are prone to targeted attacks (see part of this thread (https://bitcointalk.org/index.php?topic=632124.msg7056252#msg7056252) related to bitcoin network topology). If we imagine a solution which doesn't break the consensus, I think it would require a given proportion of 'Ids nodes' to reach the initial goal (rejection of blocks by the whole network).

Miners don't really care about the propagation of blocks to all nodes (users).  What matters is the propagation of blocks to other miners.  If 51% of the miners opted out of such a "delay system" it would have no effect on the extension of the longest chain.  It would however be exploitable by attackers because the nodes of users would falsely be showing a chain which is inferior to the longest chain.  This is very similar to an isolated attack except this would be one that users opt in to be exploited.  It is cliche but information IS power.  Information asymmetry is even more powerful (I know something you don't know) and exploitable in lots of ways.   Optimally nodes should be well connected so they gain access to as much information about the network as possible.  Anything which puts up barriers to the flow of information reduces security.

Somewhat meta but it may be useful to formally write out the assumptions in the security system used by Bitcoin.  All security systems are based on assumptions.  For example an assumption of ECC and thus ECDSA and thus Bitcoin is that the discrete logarithm problem is and will continue to be intractable.  Putting all these assumptions on paper would lead to some information sharing and hopefully improve the thought process of "solutions".  You can't improve on a system until you understand the system.


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 24, 2014, 04:13:20 PM
@DeathAndTaxes
Sure, you're right but the fact is that OP (or someone else) could implement a similar solution which does not require miners opt in. Right now, the easy solution would be to use the fact that many mining pools reuse the same bitcoin address in coinbase transactions. Of course, miners could defeat this strategy by changing their behavior. But we can imagine that OP (or someone else) adapts his strategy by using what I called "Pools of full nodes" in a previous post (https://bitcointalk.org/index.php?topic=699135.msg7955411#msg7955411).

Somewhat meta but it may be useful to formally write out the assumptions in the security system used by Bitcoin.  All security systems are based on assumptions.  For example an assumption of ECC and thus ECDSA and thus Bitcoin is that the discrete logarithm problem is and will continue to be intractable.  Putting all these assumptions on paper would lead to some information sharing and hopefully improve the thought process of "solutions".  You can't improve on a system until you understand the system.
+1
The more I know about bitcoin, the more I feel I don't know anything about it. There's a lot of very subtle choices which have been made, which are very important for network security but too often outside the radar of many devs.

@gmaxwell: WRT to mining pools reusing bitcoin addresses in coinbase transactions, shouldn't we consider that it goes against "anonymous mining" principle ?


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 24, 2014, 05:34:17 PM
... could become consensus-split and it would encourage miner consolidation and registration with an approval authority to avoid being on the losing side of such a split / or suffering block delay 'punishment'. It would almost certantly result in taking the currently broken status-quo where there are only a few miners at all and nearly setting it in stone, and it would set us up for an ugly path where miners now had identities and it was interesting to start talking about other restrictions for them.
This is basically exactly the barrel you are looking down RIGHT now.

1. Pools and their operators are mostly known and a handful controls everything.
2. Government finds them and takes over (or evil pool does).
3. Now only government approved transactions occur, NO transactions occur or chargebacks could become standard.

Once an attack occurs and no solution is in place, multiple solutions will take place, but too slowly and too many and Bitcoin is fragmented to death.
It would not survive this, even if patched later.

People would switch to the first coin with a solution which would likely be an altcoin or an alt of Bitcoin.

... or we could just boot up my client idea.

Quote
Ignoring the wrongheadedness of the overall design for a moment, the actual proposed implementation is still broken:
Quote
Ok so we put a signature of the block or block height into the coinbase script or somewhere else.
You cannot include a signature of the block into the coinbase because the block
I have later stated and in my edit of the first post that you could sign the transactions minus the coinbase only. Thus you are NOT signing the "block" but contents.

I have been in too many forum debates to put up with someone who wants me to be wrong no matter what - even when solutions are obvious.
So I will focus on technicals from here on and not entirely opinion based argumentation.

Quote from: DeathAndTaxes
Miners don't really care about the propagation of blocks to all nodes (users).  What matters is the propagation of blocks to other miners.
This is not entirely correct. No one gives a damn about miners. It is the users and acceptors of Bitcoin that give it value and if 90% of them use a client that protects them against selfish and centralized miners then that IS Bitcoin.

But yes the usually well-connected miners would not notice this new type of node for a long time.

Quote from: azeteki
Without some sort of additional bootstrap condition? Until miners begin to include an ID, nothing happens and anyone using this client is twiddling their thumbs.
This is wrong.
The hardfork punish mode for 100% untrusted blocks could be disabled in the beginning. Then the clients would only delay the normal blocks. It would be no different than someone closing their normal fullnode and opening it the next day.

[quote author"people"]consensus falling apart + my idea is evil yada yada unified lists, anonoymity
[/quote]
1. Consensus falling apart: Since my idea would ONLY and I repeat ONLY hardfork in the event of 100 untrusted blocks in a row (if enabled) it would require a significant amount of nodes (>+10%) to ONLY have 1% trust overlap for any consensus issues.
Since "trust" JUST means "anyone who spits out okish blocks" this would be insanely unlikely and the client could warn the user to trust more WELL before that happened.

I want to elaborate on this case: ~90+ blocks from untrusted sources what could that mean? It would literally NEVER happen UNLESS the network was deep in an attack!

2. Evil: My idea follows protocol, are you seriously saying I found a lethal hole in the Bitcoin code? :o  ::)

3. Unified lists: My solution only requires 1% trust overlap ok?
That means if you trust ANY of the pools you know of today.. you have consensus.. congrats.

4. Anonymity: I have outlined several ways someone could mine anonymously in my system. (using someone elses block content/signature, not using IDs at all and the fact that the trust IDs are pseudonymous just like Bitcoin for Christ sake!)

I'm sorry but saying "I'm wrong because I'm wrong" just doesn't work.
Saying its "not anonymous because its not anonymous" also doesn't work. It is not true.
Etc..
I've been in this kind of forum debate a billion times.


What are YOUR solutions to the 51% attack?
We have a situation where bigger=better/more economic so what exactly stops pools just growing and growing until we have "GovPool" and nothing else?
I'm waiting...
Oh you just have unfounded criticism duly noted, bye bye.


Title: Re: Very very simple yet powerful 51% solution
Post by: azeteki on July 24, 2014, 05:56:51 PM
3. Unified lists: My solution only requires 1% trust overlap ok?
That means if you trust ANY of the pools you know of today.. you have consensus.. congrats.

I see now. So you intend the main feature to be slowed block propagation.
Block propagation can cause a fork too, though. In fact it already does (re: the fact we ever have orphaned blocks at all).
It is resolved quickly enough because we have no barriers.

What are YOUR solutions to the 51% attack?

I can come up with lots of solutions that would involve violating core assumptions. I'm sure gmaxwell and others can do much better than me.
None of us _want_ to see the network go down. But the solution, if one exists, must have upsides greater than its' downsides.
I don't believe yours does. It's not intended as an insult.

That is even if it did work; it doesn't seem to. I fail to see what stops miners from gaining multiple cryptographic identities and bypassing the whole thing. You even allude to this yourself. So why bother?


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 24, 2014, 06:01:41 PM
2. Evil: My idea follows protocol, are you seriously saying I found a lethal hole in the Bitcoin code? :o  ::)
@realpra

I didn't say that your idea is evil, I said that running a untested idea in production environment is evil.
This is a basic principle of software engineering. If we can't agree on that, I fear it's going to be difficult to have a constructive discussion.

By the way, considering that :
- any node respecting a few rules can join the network without being excluded,
- for now, many mining pools can be identified thanks to the address appearing in coinbase txs,
- running a bunch of full node is not so expensive if attacker is motivated and has some fundings,
I would say that, yes, there's lethal holes, if not for the whole network, at least for mining pools.
According to me, problem is not in bitcoin code but in current mining pools' behavior (address reuse). But may be I missed something and I'm wrong.

Anyway, I keep thinking that if you're serious about your idea (i.e. you want to implement it and you want to convince people to use it) the first step is to show that it does not harm the network with a simulation. This is without any doubt the cheapest way to come up with an effective and deployed solution.


Title: Re: Very very simple yet powerful 51% solution
Post by: Realpra on July 24, 2014, 08:20:21 PM
2. Evil: My idea follows protocol, are you seriously saying I found a lethal hole in the Bitcoin code? :o  ::)
I didn't say that your idea is evil, I said that running a untested idea in production environment is evil.
This is a basic principle of software engineering. If we can't agree on that, I fear it's going to be difficult to have a constructive discussion.
I am a programmer and I have worked for a professional software company for almost two years. This company is the best in the world in its field.

If you think untested/partially tested code never happens in production I'm guessing you can't have much software experience.

Its undesireable, calling it evil is crazy talk.

Quote
I would say that, yes, there's lethal holes, if not for the whole network, at least for mining pools.
Forget my idea. I think you don't understand Bitcoins P2P protocol. No offense, but the worst thing some new node type can do is get itself ignored/kicked off.

I would love to test my idea and develop it, but unfortunately I don't have those resources so I have put up a bounty for a simple fix and described it.

Quote from: azeteki
That is even if it did work; it doesn't seem to. I fail to see what stops miners from gaining multiple cryptographic identities and bypassing the whole thing. You even allude to this yourself. So why bother?
Yes that would be possible, but they would HAVE to be trusted ids if they wanted more than 50% control - trust which they would loose it again if they started misusing said trust by severely pissing off users enough to get kicked off the trust lists.

So trust me there is a point and that is to put Bitcoin in the hands of the USERS.


Title: Re: Very very simple yet powerful 51% solution
Post by: laurentmt on July 24, 2014, 08:57:36 PM
I am a programmer and I have worked for a professional software company for almost two years. This company is the best in the world in its field.
If you think untested/partially tested code never happens in production I'm guessing you can't have much software experience.
Its undesireable, calling it evil is crazy talk.
Well, well, well.
I'm a software engineer (for more than 15 years) and I repeat it : "untested code put in production is evil" (understand "bad" or "faulty" but not "malicious" or "vicious"). The fact that it happens does not mean it's a good practice. Never. Just ask yourself if you would like to fly in a plane while knowing that its system embeds some untested code. Period.

Quote
Forget my idea. I think you don't understand Bitcoins P2P protocol. No offense, but the worst thing some new node type can do is get itself ignored/kicked off.
If you test your idea with a unique node in the network, for sure you'll be able to check that your node doesn't crash but you won't be able to check its effects at network level because it won't have any visible effect. I don't pretend to be a p2p expert but I know a few things about networks / network dynamics and the difference between what you can check at node level and what you can check at network level (emergent behaviors).

3. Unified lists: My solution only requires 1% trust overlap ok?
That means if you trust ANY of the pools you know of today.. you have consensus.. congrats.

I see now. So you intend the main feature to be slowed block propagation.
Block propagation can cause a fork too, though. In fact it already does (re: the fact we ever have orphaned blocks at all).
It is resolved quickly enough because we have no barriers.
I fear that it's the point on which Realpra disagrees with all of us. Considering that none of us is able to convince him, my last best effort is to recommend the reading of this paper from microsoft research (http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf).

Quote
In the case of transactions, stopping the propagation is a reasonable trade off, that protects the network from transaction spam, at the expense of individual users. However, in the case of blocks, stopping the propagation is not reasonable.

I was trying to be constructive, but Realpra's free to burn 2k$. This is his money.

At last, a well known story, to meditate
Quote
A little bird was flying south for the winter.  It was so cold; the bird froze up and fell to the ground in a large field. While it was lying there, a cow came by and dropped some dung on it.  As the frozen bird lay there in the pile of cow dung, it began to realize how warm it was. He lay there all warm and happy, and soon began to sing for joy. A passing cat heard the bird singing and came to investigate. Following the sound, the cat discovered the bird under the pile of cow dung, and promptly dug him out and ate him.