Bitcoin Forum
April 23, 2019, 02:51:09 PM *
News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 4 5 »  All
  Print  
Author Topic: Block lattice  (Read 7945 times)
clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
October 24, 2015, 06:39:15 PM
Merited by pol5 (1)
 #1

Hey everyone, I designed a system which, for lack of a better term, is called a block lattice.

https://github.com/clemahieu/raiblocks/wiki/Block-lattice

The idea is each account in the system has a block chain that is controlled only by them, all chains are replicated to all peers in the network.

The advantage of doing this is each account can order their own transactions meaning no proof besides a digital signature is needed.

I think this goes a long way toward scalability by removing block intervals, mining, transaction fees etc and wondered what everyone thought.

RaiBlocks coin:  Instant blocks, no fees
1556031069
Hero Member
*
Offline Offline

Posts: 1556031069

View Profile Personal Message (Offline)

Ignore
1556031069
Reply with quote  #2

1556031069
Report to moderator
1556031069
Hero Member
*
Offline Offline

Posts: 1556031069

View Profile Personal Message (Offline)

Ignore
1556031069
Reply with quote  #2

1556031069
Report to moderator
1556031069
Hero Member
*
Offline Offline

Posts: 1556031069

View Profile Personal Message (Offline)

Ignore
1556031069
Reply with quote  #2

1556031069
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1556031069
Hero Member
*
Offline Offline

Posts: 1556031069

View Profile Personal Message (Offline)

Ignore
1556031069
Reply with quote  #2

1556031069
Report to moderator
1556031069
Hero Member
*
Offline Offline

Posts: 1556031069

View Profile Personal Message (Offline)

Ignore
1556031069
Reply with quote  #2

1556031069
Report to moderator
gmaxwell
Staff
Legendary
*
Offline Offline

Activity: 2702
Merit: 2156



View Profile
October 24, 2015, 08:30:15 PM
 #2

It appears (from the writeup) that you are unaware of sybil attacks?

The graph of transactions in bitcoin already functions like what you describe (except 'accounts' are single use txouts); Bram Cohen likes to call Bitcoin without the blockchain "bitpeso".  In Bitcoin the blockchain is overlaid on top of "bitpeso" to resolve "complex forks" (using your language) in a manner that allows someone to join the network and know which resolution is authoritative in a way which is both robust to sybil attacks and does not require membership (because a membership process would create control over the system).

In your description you appears to liberally conflate forks and double-spending.  In Bitcoin, double spending a traditional txout requires malicious behavior, just as you describe.  Blockchain forking in the absence of double spending is benign and no different to the "multiple resolution rounds" you mention from your resolution protocol but fail to describe detail sufficient to permit any analysis.
clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
October 24, 2015, 08:44:33 PM
 #3

We have a section on Sybil attacks in the attacks documentation https://github.com/clemahieu/raiblocks/wiki/Attacks

The resolution protocol is a balance-weighted vote by account holders in the network, this is the core of what prevents sybil attacks.  In order to attack the network, you need to have ownership in the network in proportion to your attack weight.

RaiBlocks coin:  Instant blocks, no fees
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
October 24, 2015, 11:05:16 PM
Last edit: November 14, 2015, 05:20:50 AM by TPTB_need_war
 #4

Unless every owner a token is going to be online mining all the time, then mining will need to be delegated. So some pools have more weighted-balance voting power than others. You need to offer some incentive for mining. Profits accrue to those with the most economy-of-scale if the incentives are market (competitively) priced, thus you will likely end up with the situation that Bitcoin had where a single pool or potential grouping of large pools had more than 51% of the hashrate but in your design this would be more than 51% of the voting power.

Is a cascade of intertwined inter-chained reorganizations when multiple double-spends are reverted by a fork more onerous than in a single block chain? Isn't that complexity similar to the reason you rejected multiple inputs and outputs in transactions?

The key failure in your design is the lack of incentive to have a consensus. What is the incentive for voting nodes to agree with the correct fork and for minority nodes to agree with the majority fork? Seems to me they can all disagree and no one can prove otherwise, because they can pretend to have never heard the votes of others (no way to prove receipt of a vote on the internet). This shows that without the objectivity of a PoW, then there is no objectivity and you end up in chaos.

In PoW, miners have an incentive to reach consensus because otherwise their rewards won't be honored by the longest chain. In your system the majority of the vote is the winning fork, except there is no penalty for delaying for an indefinite period acknowledging receipt of such a vote. Thus complex game theories arise. Even more critically, the majority vote may be split among multiple forks, such that there is no consensus, because you have multiple chains thus a plurality of permutations of forks.

I do want readers to note which of the three posters in this thread was able to state directly the design error. That should be instructive to investorswhich lead developer is most qualified.

clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
October 24, 2015, 11:40:20 PM
 #5

These are good, in-depth questions.

Unless every owner a token is going to be online mining all the time, then mining will need to be delegated. So some pools have more weighted-balance voting power than others. You need to offer some incentive for mining. Profits accrue to those with the most economy-of-scale if the incentives are market (competitively) priced, thus you will likely end up with the situation that Bitcoin had where a single pool or potential grouping of large pools had more than 51% of the hashrate but in your design this would be more than 51% of the voting power.

Since we don't use mining to order transactions or resolve forks, adding mining for the initial distribution would be rather vestigial.  It also seems that so far, despite everyone's best efforts to make mining more distributed and focus away from large pools or enthusiasts, we've only achieved moderate success.  In the end we want the initial distribution to go to people, not hardware so we're distributing 100% of the supply through a captcha on the site under "Get Blocks" according to a fixed distribution schedule.  https://github.com/clemahieu/raiblocks/wiki/Distribution-and-Mining

Is a cascade of intertwined inter-chained reorganizations when multiple double-spends are reverted by a fork more onerous than in a single block chain? Isn't that complexity similar to the reason you rejected multiple inputs and outputs in transactions?

The rollback does cascade though the window for a rollback is very small compared to traditional cryptos.  On a traditional crypto block_interval * confirm_count is the range of uncertainty, with RaiBlocks the range of uncertainty is ~1 network propagation interval i.e. how fast can network packets reach everyone in the network.  Once everyone has received one fork, subsequent forks would be instantly rejected.

The key failure in your design is the lack of incentive to have a consensus. What is the incentive for voting nodes to agree with the correct fork and for minority nodes to agree with the majority fork? Seems to me they can all disagree and no one can prove otherwise, because they can pretend to have never heard the votes of others (no way to prove receipt of a vote on the internet). This shows that without the objectivity of a PoW, then there is no objectivity and you end up in chaos.

Primarily this is mitigated by the fact that if a node doesn't create a fork, there is nothing to vote on, no consensus is needed.  If I have a signed block chain A0->B0->C0 and it's published, no one can vote between C0 and let's say C1 because there is no signed C1.  If you don't sign forks, no one can vote on your transactions.

In PoW, miners have an incentive to reach consensus because otherwise their rewards won't be honored by the longest chain. In your system the majority of the vote is the winning fork, except there is no penalty for delaying for an indefinite period acknowledging receipt of such a vote. Thus complex game theories arise. Even more critically, the majority vote may be split among multiple forks, such that there is no consensus, because you have multiple chains thus a plurality of permutations of forks.

I do want readers to note which of the three posters in this thread was able to state directly the design error. That should be instructive to investors.

Well-behaved nodes are configured to flip their vote if they observe their fork variant as having fewer votes than another.  The only way to vote is to have a balance tied up in the network.  To vote to confuse the network is to destroy its value which destroys your investment.  The incentive is to retain value in the system rather than accumulate rewards through inflating everyone else.

RaiBlocks coin:  Instant blocks, no fees
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
October 25, 2015, 12:06:20 AM
Last edit: November 14, 2015, 05:25:57 AM by TPTB_need_war
 #6

The key failure in your design is the lack of incentive to have a consensus. What is the incentive for voting nodes to agree with the correct fork and for minority nodes to agree with the majority fork? Seems to me they can all disagree and no one can prove otherwise, because they can pretend to have never heard the votes of others (no way to prove receipt of a vote on the internet). This shows that without the objectivity of a PoW, then there is no objectivity and you end up in chaos.

Primarily this is mitigated by the fact that if a node doesn't create a fork, there is nothing to vote on, no consensus is needed.  If I have a signed block chain A0->B0->C0 and it's published, no one can vote between C0 and let's say C1 because there is no signed C1.  If you don't sign forks, no one can vote on your transactions.

I don't comprehend your notation and its applicability, but I was just thinking conceptually that you have a these N block chains operating orthogonally, thus any one can receive the transfer of value from the other. Then you can have double-spends and what not. So then you can have different block chains disagreeing about a plurality of different orthogonal block chain states. There is no global unified state, that is the entire point since missing the global PoW block period to force timely consensus to this single objective reality. If we don't want a global state, then we must use a probabilistic forking structure such as Iota's DAG to obtain Byzantine fault tolerance. You've conflated the independence with the determinism required for global coherence. Global coherence with individual realities (relativism) can only be probabilistic. I believe this follows from Brewer's theorem which says it is impossible to have all three of consistency, availability, and partition tolerance.

In PoW, miners have an incentive to reach consensus because otherwise their rewards won't be honored by the longest chain. In your system the majority of the vote is the winning fork, except there is no penalty for delaying for an indefinite period acknowledging receipt of such a vote. Thus complex game theories arise. Even more critically, the majority vote may be split among multiple forks, such that there is no consensus, because you have multiple chains thus a plurality of permutations of forks.

I do want readers to note which of the three posters in this thread was able to state directly the design error. That should be instructive to investors.

Well-behaved nodes are configured to flip their vote if they observe their fork variant as having fewer votes than another.  The only way to vote is to have a balance tied up in the network.  To vote to confuse the network is to destroy its value which destroys your investment.  The incentive is to retain value in the system rather than accumulate rewards through inflating everyone else.

Not necessarily. They could collude to steal value from another fork by double-spending to the other fork and then disagreeing about the objective time of spending. Perhaps other complex game theory as well. Also it may not be intentional. Per my point above, the objective reality may be indeterminate and the system may have a plurality of minority realities (votes). That is what I expect to be the normal mode due to chaos theory.

clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
October 25, 2015, 05:07:34 AM
 #7

The key failure in your design is the lack of incentive to have a consensus. What is the incentive for voting nodes to agree with the correct fork and for minority nodes to agree with the majority fork? Seems to me they can all disagree and no one can prove otherwise, because they can pretend to have never heard the votes of others (no way to prove receipt of a vote on the internet). This shows that without the objectivity of a PoW, then there is no objectivity and you end up in chaos.

Primarily this is mitigated by the fact that if a node doesn't create a fork, there is nothing to vote on, no consensus is needed.  If I have a signed block chain A0->B0->C0 and it's published, no one can vote between C0 and let's say C1 because there is no signed C1.  If you don't sign forks, no one can vote on your transactions.

I don't comprehend your notation and its applicability, but I was just thinking conceptually that you have a these N block chains operating orthogonally, thus one one can receive the transfer of value from the other. Then you can have double-spends and what not. So then you can have different block chains disagreeing about a plurality of different orthogonal block chain states. There is no global unified state, that is the entire point since missing the global PoW block period to force timely consensus to this single objective reality. If we don't want a global state, then we must use a probabilistic forking structure such as Iota's DAG to obtain Byzantine fault tolerance. You've conflated the independence with the determinism required for global coherence. Global coherence with individual realities (relativism) can only be probabilistic. I believe this follows from Brewer's theorem which says it is impossible to have all three of consistency, availability, and partion tolerance.

Sure, I don't mind explaining.  Even though all accounts have their own chain, each chain consists of blocks that have a single successor and if multiple successors are published, they're arbitrated through voting.  Starting off the ledger can answer two central questions 1) Is this block hash in the ledger and 2) Is a block the head block for an account.  This functionality can be verified in https://github.com/clemahieu/raiblocks/blob/master/rai/secure.cpp ~ line 2660.  When blocks are published, they're flooded to the network, this ensures everyone observes the state change seen by other nodes.  When we receive a new block we check question 1 on the hash of this block.  If it's already in the ledger we discard the message because the block has already been processed.  If it hasn't been seen, we retrieve the hash for the previous block and check question 2 on the previous block hash.  If the previous block is the head block for that account, we can enter this in to the ledger, this is a valid state change for this account.  If the previous block is not the head block, we can check question 1 on the previous block.  If the previous block is already in the ledger we deterministically know we have observed a signed fork.  When representative nodes observe a signed fork, they start periodically broadcast their votes on a fixed interval until consensus is reached.  When any node observes a fork they listen for representative votes and change their ledger to match the vote winner.  As you can see votes are only published and blocks are only rolled back if there is is a deterministic fork.  If there is no fork, the ledger can be updated without engaging in voting because there is only one possible state change for that account.

Allowing forks to be arbitrated separately is a design feature of the system.  This system is similar to side-chains taken to an extreme.  In side-chains we break apart the block chain to allow smaller groups of accounts to be arbitrated, hopefully at a higher speed.  In this system a side chain represents one account.

In PoW, miners have an incentive to reach consensus because otherwise their rewards won't be honored by the longest chain. In your system the majority of the vote is the winning fork, except there is no penalty for delaying for an indefinite period acknowledging receipt of such a vote. Thus complex game theories arise. Even more critically, the majority vote may be split among multiple forks, such that there is no consensus, because you have multiple chains thus a plurality of permutations of forks.

I do want readers to note which of the three posters in this thread was able to state directly the design error. That should be instructive to investors.

Well-behaved nodes are configured to flip their vote if they observe their fork variant as having fewer votes than another.  The only way to vote is to have a balance tied up in the network.  To vote to confuse the network is to destroy its value which destroys your investment.  The incentive is to retain value in the system rather than accumulate rewards through inflating everyone else.

Not necessarily. They could collude to steal value from another fork by double-spending to the other fork and then disagreeing about the objective time of spending. Perhaps other complex game theory as well. Also it may not be intentional. Per my point above, the objective reality may be indeterminate and the system may have a plurality of minority realities (votes). That is what I expect to be the normal mode due to chaos theory.

I'd be interested in having you expand on this, specifically the 50% attack documented in https://github.com/clemahieu/raiblocks/wiki/Attacks I think you'd have some really good insight.

On the plurality of minorities point, nodes are configured to change their ledger to match the block with the highest amount of votes, it doesn't need to have an absolute majority, just the largest minority.  As voting rounds go on, smaller minorities will disappear until there is a single conclusion.  This assumes the incentive to vote correctly holds.  We need to remember that votes come from having a balance in Rai, accounts that don't have Rai can't vote.  Voting to collude on a fork is destructive to integrity of the system and votes only come from having a stake in the system, so voting to collude is voting to destroy the value you hold in the system.

If we used an analogy using the bitcoin market cap which is right now ~4.2b we'd be saying, a group of people with 2.1b$ invested in bitcoin are working to mine double spends in to the system which would destroy their 2.1b$ investment because people would no longer use bitcoin.  I think this is improbable.

RaiBlocks coin:  Instant blocks, no fees
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
October 30, 2015, 11:01:51 AM
 #8

Some further discussion that might be helpful:

https://bitcointalk.org/index.php?topic=1216479.msg12822716#msg12822716

https://bitcointalk.org/index.php?topic=1216479.msg12829829#msg12829829

Apologies if I hadn't had the time to focus in on the points in your reply.

clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
November 01, 2015, 05:58:09 PM
 #9

I see discussion about violating CAP though the only way someone could violate this is if they're claiming all 3 conditions can be simultaneously satisfied.  I haven't seen anyone claiming resilience against partitioning and without this they could be claiming at most 2 of the three, possibly 1 or 0, which may not be useful but doesn't violate CAP.

Getting globally consistent state is fine though it comes with two penalties, confirmation delays and transaction throughput limitations.  If we could trade off some of this global state knowledge for faster confirmation time and higher transaction throughput, this would be desirable.

There are some things we can discard and still get consistent transactions, if we start with a globally consistent state and have two transactions A sends to B and C sends to D, we don't need to know which occurs first, both would be correct applied in either order.  Bitcoin totally orders these transactions whereas RaiBlocks partially orders them.

Breaking the block chain in to a partially ordered set gives desirable performance at the expense of unneeded total ordering.

RaiBlocks coin:  Instant blocks, no fees
TPTB_need_war
Sr. Member
****
Offline Offline

Activity: 420
Merit: 255


View Profile
November 01, 2015, 07:40:27 PM
 #10

Getting globally consistent state is fine though it comes with two penalties, confirmation delays and transaction throughput limitations.  If we could trade off some of this global state knowledge for faster confirmation time and higher transaction throughput, this would be desirable.

I agree with at least this part of your post. And getting the details correct on this goal is where we are now.

clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
November 01, 2015, 09:49:09 PM
 #11

Getting globally consistent state is fine though it comes with two penalties, confirmation delays and transaction throughput limitations.  If we could trade off some of this global state knowledge for faster confirmation time and higher transaction throughput, this would be desirable.

I agree with at least this part of your post. And getting the details correct on this goal is where we are now.

This is similar to a problem in electrical engineering of solving metastability.  https://en.wikipedia.org/wiki/Metastability_in_electronics  Either make your transistors switch faster or wait more wait time to increase the probability of a correct conclusion.  RaiBlocks is analogously making the transistors switch faster by only ordering things required to make sure there aren't chain forks.

All of this is implemented in the rai::ledger_processor block visitor class https://github.com/clemahieu/raiblocks/blob/master/rai/secure.cpp

RaiBlocks coin:  Instant blocks, no fees
monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
November 02, 2015, 09:51:42 AM
Last edit: November 02, 2015, 10:46:42 AM by monsterer
 #12

Where do you store the votes for fork resolution?

From the wiki:

Quote
Unlike existing cryptocurrency systems, forks are an almost non-existent event and are designed to only affect the malicious account instead of the entire ledger

This isn't the case. Double spends affect the sender and receiver(s) of the transaction - so potentially, they could affect every single blockchain in the system.
maincoin
Full Member
***
Offline Offline

Activity: 168
Merit: 100


View Profile
November 02, 2015, 10:26:26 AM
 #13

Interesting idea, i'll check out the link
clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
November 03, 2015, 12:01:42 AM
 #14

Where do you store the votes for fork resolution?

From the wiki:

Quote
Unlike existing cryptocurrency systems, forks are an almost non-existent event and are designed to only affect the malicious account instead of the entire ledger

This isn't the case. Double spends affect the sender and receiver(s) of the transaction - so potentially, they could affect every single blockchain in the system.

Votes and conflicts are stored in memory until a winning percentage is reached and an extra amount of time has elapsed, the goal being to discard forks as fast as possible.

You're right on the description though, it should probably be "malicious accounts" since an account that breaks the protocol and accepts a fork before it's settled is effectively malicious as well, for all we know they're the same person or in collusion.  The important point is that if B is named as a recipient of a transactions that's forked, unknown to them, B can continue to process other transactions while it waits for this fork to settle.

What stops an avalanche of rollbacks is blocks are only rolled back if another block receives a majority vote and votes are weighted based on account balance.  The worst avalanche that could happen would be for the successor to the genesis block to be rolled back.  If the genesis key published this ancient fork everyone would observe this conflict and start a tally.  All the representatives would kick off their periodic vote, of which 99.99% would vote for the original block and whoever published the conflict would get the .01% vote.  No one would roll back anything because a majority was never reached.  Flipping blocks past the heuristic wait period is analogous to a >50% attack.

RaiBlocks coin:  Instant blocks, no fees
clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
November 03, 2015, 12:03:43 AM
 #15

Interesting idea, i'll check out the link

Awesome, let me know if you have any issues.

Remember, the Rai supply is distributed through a captcha so new people will be able to try it out without mining or trading.

RaiBlocks coin:  Instant blocks, no fees
monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
November 03, 2015, 09:14:50 AM
 #16

You're right on the description though, it should probably be "malicious accounts" since an account that breaks the protocol and accepts a fork before it's settled is effectively malicious as well, for all we know they're the same person or in collusion.  The important point is that if B is named as a recipient of a transactions that's forked, unknown to them, B can continue to process other transactions while it waits for this fork to settle.

Presumably raiblocks uses a UTXO system, then? Otherwise you'd be able to DOS the entire system by sending doubles spends to everybody, continuously.

Quote
What stops an avalanche of rollbacks is blocks are only rolled back if another block receives a majority vote and votes are weighted based on account balance.  The worst avalanche that could happen would be for the successor to the genesis block to be rolled back.  If the genesis key published this ancient fork everyone would observe this conflict and start a tally.  All the representatives would kick off their periodic vote, of which 99.99% would vote for the original block and whoever published the conflict would get the .01% vote.  No one would roll back anything because a majority was never reached.  Flipping blocks past the heuristic wait period is analogous to a >50% attack.

With no historical evidence of voting, how can a peer who is syncing tell a legitimate chain set from a fabricated one?

In addition, doesn't this mean that if you have enough stake, you can arbitrarily rewrite history by voting on historical forks?
clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
November 03, 2015, 05:05:48 PM
 #17

You're right on the description though, it should probably be "malicious accounts" since an account that breaks the protocol and accepts a fork before it's settled is effectively malicious as well, for all we know they're the same person or in collusion.  The important point is that if B is named as a recipient of a transactions that's forked, unknown to them, B can continue to process other transactions while it waits for this fork to settle.

Presumably raiblocks uses a UTXO system, then? Otherwise you'd be able to DOS the entire system by sending doubles spends to everybody, continuously.

Each block has an individual proof of work attached to it for simple throttling, generating forks would require generating this work as well so people could spam forks as fast as they could perform normal transactions.  Is this what you were talking about or could you elaborate a bit more?

Quote
Quote
What stops an avalanche of rollbacks is blocks are only rolled back if another block receives a majority vote and votes are weighted based on account balance.  The worst avalanche that could happen would be for the successor to the genesis block to be rolled back.  If the genesis key published this ancient fork everyone would observe this conflict and start a tally.  All the representatives would kick off their periodic vote, of which 99.99% would vote for the original block and whoever published the conflict would get the .01% vote.  No one would roll back anything because a majority was never reached.  Flipping blocks past the heuristic wait period is analogous to a >50% attack.

With no historical evidence of voting, how can a peer who is syncing tell a legitimate chain set from a fabricated one?

In addition, doesn't this mean that if you have enough stake, you can arbitrarily rewrite history by voting on historical forks?

If a node sees a fork during bootstrap it can directly request votes from peers in place of the automatically sent votes it would have received had it been online.  This sounds along the same lines as the "Bootstrap poisoning attack"  https://github.com/clemahieu/raiblocks/wiki/Attacks  I know some bitcoin wallets do a basic level of cementing to protect from malicious nodes sending a bunch of forks that aren't the tallest.

Yea, if someone owned >50% of the entire RaiBlocks marketcap they could rewrite history, that's also on the attacks page but I think the thing that puts it in to perspective is how much that would cost.  If we use bitcoin as an example, someone wouldn't need to rewrite history for it to be completely destructive, they would just need to be able to rewrite a couple days of transactions demonstrating they own >50% of the hashing power and people would flee.  I think since the cost of getting >50% of the hashing power is necessarily less than the cost of getting >50% of the entire market cap, the balance weighted votes are a stronger guarantee.

RaiBlocks coin:  Instant blocks, no fees
monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
November 03, 2015, 06:26:37 PM
 #18

Each block has an individual proof of work attached to it for simple throttling, generating forks would require generating this work as well so people could spam forks as fast as they could perform normal transactions.  Is this what you were talking about or could you elaborate a bit more?

Sure. If sending a double spend to an account requires the recipient account to wait for fork resolution before it can continue to spend funds (since the final balance is now in question), then it becomes possible to use double spends as a DOS mechanism. However, if there was a UTXO system, there are effectively many different accounts per user, so you wouldn't be able to DOS like this as you'd only cause one UTXO to be in conflict.

Quote
If a node sees a fork during bootstrap it can directly request votes from peers in place of the automatically sent votes it would have received had it been online.  This sounds along the same lines as the "Bootstrap poisoning attack"  https://github.com/clemahieu/raiblocks/wiki/Attacks  I know some bitcoin wallets do a basic level of cementing to protect from malicious nodes sending a bunch of forks that aren't the tallest.

This is another DOS angle. You could set up a lot of malicious seed nodes to just broadcast fake blockchains to everyone at no extra cost. Since the syncing node must then request for new votes to resolve the historical forks, they essentially start draining network resources. If there are enough syncing nodes, this can quickly becomes a system wide DOS.

Quote
Yea, if someone owned >50% of the entire RaiBlocks marketcap they could rewrite history, that's also on the attacks page but I think the thing that puts it in to perspective is how much that would cost.  If we use bitcoin as an example, someone wouldn't need to rewrite history for it to be completely destructive, they would just need to be able to rewrite a couple days of transactions demonstrating they own >50% of the hashing power and people would flee.  I think since the cost of getting >50% of the hashing power is necessarily less than the cost of getting >50% of the entire market cap, the balance weighted votes are a stronger guarantee.

If you look at standard POS systems, this is mitigated to some degree because the votes are recorded in the chain, so you can replay all the history. They do suffer from the keys from the past attack, but raiblocks as described doesn't even have basic protection of the vote history.
clemahieu
Full Member
***
Offline Offline

Activity: 238
Merit: 112


View Profile WWW
November 03, 2015, 09:44:49 PM
Last edit: November 03, 2015, 09:59:25 PM by clemahieu
 #19

Each block has an individual proof of work attached to it for simple throttling, generating forks would require generating this work as well so people could spam forks as fast as they could perform normal transactions.  Is this what you were talking about or could you elaborate a bit more?

Sure. If sending a double spend to an account requires the recipient account to wait for fork resolution before it can continue to spend funds (since the final balance is now in question), then it becomes possible to use double spends as a DOS mechanism. However, if there was a UTXO system, there are effectively many different accounts per user, so you wouldn't be able to DOS like this as you'd only cause one UTXO to be in conflict.

I see what you're describing now; yes there is indeed a UTXO set, we named them receivables though they're the same concept. Sending is a two phased process to defend against exactly what you're describing, some malicious attacker naming a target account and generating forks.  In the send phase a send block is created reducing the sender balance and creating a receivable which can only be claimed by the destination. The receiver needs to bring in this receivable at a later time they choose after they deem the send sufficiently settled.

With this we can see that within a couple network propagation intervals a receiver can be sure there are no forks because all normal nodes repeat the send acknowledging it. Representatives create a slightly heavier packet that includes a signed vote which observers can look up the signer, check their balance, apply a vote weight depending on their balance, and check for quarum.

They nice part about each account running their own chain is they all have a 100% vested interest in maintaining their own chain and 100% authority over what goes in it and when. If any forks are observed in the few seconds after send a receiver should immediately add more wait time before accepting a block out the pending/UTXO set.  Basically receivers have the option of receiving things out of order.

Quote
Quote
If a node sees a fork during bootstrap it can directly request votes from peers in place of the automatically sent votes it would have received had it been online.  This sounds along the same lines as the "Bootstrap poisoning attack"  https://github.com/clemahieu/raiblocks/wiki/Attacks  I know some bitcoin wallets do a basic level of cementing to protect from malicious nodes sending a bunch of forks that aren't the tallest.

This is another DOS angle. You could set up a lot of malicious seed nodes to just broadcast fake blockchains to everyone at no extra cost. Since the syncing node must then request for new votes to resolve the historical forks, they essentially start draining network resources. If there are enough syncing nodes, this can quickly becomes a system wide DOS.

I think there is some mitigation in place for this. In the attacks documentation we call this Block Gap Synchronization, it's the ambiguous state between is this a junk block or is this a valid block but I just missed something. One mitigation strategy is by virtue of the fact that during normal operation, nodes passively listen for votes and don't take preemptive action. Nodes listen for and tally votes, the only time they request votes is on startup syncing or if a block got a bunch of votes but it doesn't fit in the local ledger meaning we missed something and were pretty sure it's not junk because it got a fair amount of votes.

Quote
Quote
Yea, if someone owned >50% of the entire RaiBlocks marketcap they could rewrite history, that's also on the attacks page but I think the thing that puts it in to perspective is how much that would cost.  If we use bitcoin as an example, someone wouldn't need to rewrite history for it to be completely destructive, they would just need to be able to rewrite a couple days of transactions demonstrating they own >50% of the hashing power and people would flee.  I think since the cost of getting >50% of the hashing power is necessarily less than the cost of getting >50% of the entire market cap, the balance weighted votes are a stronger guarantee.

If you look at standard POS systems, this is mitigated to some degree because the votes are recorded in the chain, so you can replay all the history. They do suffer from the keys from the past attack, but raiblocks as described doesn't even have basic protection of the vote history.

RaiBlocks coin:  Instant blocks, no fees
monsterer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile
November 03, 2015, 10:17:54 PM
 #20

They nice part about each account running their own chain is they all have a 100% vested interest in maintaining their own chain and 100% authority over what goes in it and when. If any forks are observed in the few seconds after send a receiver should immediately add more wait time before accepting a block out the pending/UTXO set.  Basically receivers have the option of receiving things out of order.

I don't want to sound disparaging, but that's already how bitcoin's UTXO system works. Users create transactions in their wallets by linking inputs to outputs and then signing. No one can change that outside the client. The only thing which changes outside the client is the sequencing of transactions, which is provided by the blockchain.

Quote
Nodes listen for and tally votes, the only time they request votes is on startup syncing or if a block got a bunch of votes but it doesn't fit in the local ledger meaning we missed something and were pretty sure it's not junk because it got a fair amount of votes.

The trouble is because there is no historical voting evidence, any historical fork will require active effort to resolve.

In POW syncing nodes can trivially verify and resolve historical forks without any additional work from miners - the longest chain always wins and the  true elegance of this system is that is does not distinguish between a syncing node and a regular node; this makes it very robust.
Pages: [1] 2 3 4 5 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!