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 |
|
|
|
|
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.
|
|
|
|
|
They shouldn't be malleable; lack of canonicalization was an oversight.
|
|
|
|
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. |
|
|
|
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-MiningIs 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. |
|
|
|
We have a section on Sybil attacks in the attacks documentation https://github.com/clemahieu/raiblocks/wiki/AttacksThe 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. |
|
|
|
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-latticeThe 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. |
|
|
|
For the largest amount of decentralization we'd want to distribute to people rather than hardware so if we could find a method that can differentiate people from automation we could have better decentralization. Web programmers have a similar problem and they invented captchas to solve this problem. For https://raiblocks.net/ we're distributing 100% through a captcha hoping this is a more egalitarian way to distribute rather than skewing toward enthusiasts. |
|
|
|
|
Point taken. I'll think on it some more.
|
|
|
|
<textwall> I think making changes that allows the community effort and focus to move off of technical quirks and on to working with initial adopters is key. So much effort and brain power by enthusiasts is being burned trying to work around issues of making the protocol sustainable and making it act like normal currency that they're not able to work on making it solve problems which in the end is what the mainstream wants. I think the practical focus points of crypto that aren't achieved by fiat is global instantaneous transfers, no fees, and non-reversible transfers. Unfortunately fees are starting to go up a bit making the no-fee thing go away a bit, the transfers are quick compared to an international wire transfer but they're slower compared to a credit card charge, even an international one. On the non-reversible aspect you have to find people who are comfortable with that situation. When there's a trade and crypto is on one leg, usually there's a tangible good coming through on the other end so the crypto sender is taking the risk whereas with credit cards the receiver is taking a risk of chargebacks. From the standpoint of someone sending crypto, you want a social assurance that the person on the other end will hold up their end of the bargain or the deal is in sufficiently small quantities than any loss can be written off. This means you're either doing micro payments or you're dealing with a large, reputable company that's more concerned with their image and will do anything to make the buyer happy than trying to steal one payment. So we're looking for early adopters that either take small payments or they're large reputable companies dealing in goods internationally or cross currency. Large companies want simple things their tech guys can plug in to their data center and their software can easily communicate with it. RaiBlocks has a docker container on dockerhub that anyone with Linux can safely run inside a data center with one command. https://github.com/clemahieu/raiblocks/wiki/Docker-nodes There's a simple http RPC protocol that people can hit with any web language or curl from a command line https://github.com/clemahieu/raiblocks/wiki/RPC-protocolLarge companies also may not do their own processing at all so peering with payment processors is a more likely goal but they'd make use of container nodes as well. Small transfers where there's no real loss if the return leg doesn't follow through is directly at competition with high fees, if you have high fees you loose this user. Small transfers like tipping or other micropayments would be good adopters and with RaiBlocks the no fee overhead makes that possible. </textwall> |
|
|
|
Where do you see Raiblocks in 10 years.
It could be dead in a ditch though I think the ability to be adopted by the mainstream is higher compared to all the bitcoin clones out there. The thing I think it brings to the table is utter simplicity. It does one job and it does it in a simple, efficient manner. To enthusiasts like us bitcoin et. al. makes sense but a layman it's highly confusing, it has a lot of nobs and dials and tries to do a lot of things. Then tack on some of the bleeding edge things some people are trying to do like exchanges, multisig, and true anonymity and pretty much no one knows what this is about anymore. What RaiBlocks doesn't have is adoption since it's brand new and that's incredibly important. It's up in the air what'll happen but I think it solves the distributed ledger problem well. |
|
|
|
From a computer science point of view mining is the act of negotiating contention of a shared resource, the block chain. Sidechains divides the contention down by a constant factor but creates a coherence issue between the separate chains because the protocol wasn't designed to communicate between them directly. A project I'm working on RaiBlocks https://raiblocks.net/ eliminates the contention issue by having 1 sidechain per address and is designed to communicate transfers between chains. This means consensus is only needed for double-spending attacks rather than for every transaction always. |
|
|
|
|
The issue is more in how it's used rather than the core itself. There's a reason why banks hire security experts and buy hardware to secure their infrastructure. Letting a startup hold your money is probably not a good idea.
|
|
|
|
Wait, this raises another question  How can you tell if somebody already accepted a particular incoming tx? Does this mean that you have to keep all transactions forever? Internally when a send is accepted in to the ledger, it's hash is put in to the receivables table and this entry is deleted when a receive uses it. Subsequent receives for the same send are rejected because there's no entry in the receivables table anymore. The relevant code is in rai/secure.cpp ledger_processor::receive_block, the error code is 'overreceive'. The source block might exist and have been already used or the creator might have pointed to a source block that doesn't even exist, either way it's invalid and forgotten. |
|
|
|
|
I agree we definitely don't want massive block-flip scenarios going on. The first priority would be to make sure non-malicious users aren't rolled back and the second priority would be to make sure we can always come to consensus.
I'll examine what you described and how the code would handle it and make sure we never reach a deadlock state where the system can't synchronize. It should definitely be resilient to what I agree is the realistic scenario you described.
|
|
|
|
Another example: let's say node Alice had a temporary network jam and didn't receive a particular block from Bob.
After some time Bob sends another block, linked to the block that Alice doesn't have.
What is Alice's action?
Reject second block? If so then it will also reject all the transactions that will depend on it and the network becomes fragmented and disintegrates after some time, with transactions being confirmed/rejected randomly by different nodes.
Should Alice ask the network for the previous block? Probably. But what if Bob is malicious and there is no legit previous block? Now every node on the network is feverishly asking each other "Have you seen this block?". Since Bob can produce any number of invalid blocks for any number of public keys, he can load the network significantly, maybe even completely paralyze it.
This is a great question. There's a bootstrap process for synchronizing but as you noticed it's an obvious opportunity for a network amplify DOS attack if people aggressively try to use the bootstrap process for every missed block they see. One situation is out of order block delivery where B2 depends on, and arrives before B1. The node will remember a small number of blocks outside the ledger called the gap_cache. These block are not in the ledger but give a jitter interval for out of order delivery. Every time a block is accepted in to the ledger, the node will check the gap_cache to see if this inserted block satisfies the dependency of another block. The other situation is where through some means, network connectivity drop, laptop sleep, etc, we missed block broadcasts. If a node receives a non-voting republish that seems to be unlinked from anything, it puts it in the gap cache and does nothing. If it receives a vote that contains an unlinked block, it will add it to the gap_cache and start a tally counting votes for this block. If the vote tally is appreciable, maybe >25% of supply, we're out of sync and it initiates a bootstrap session to synchronize. |
|
|
|
I think I am starting to understand the concept now thanks to the graphics, explanation and further discussion. If this system really would host a larger majority of good actors this sounds like it could work really well. However, when we are looking at a possible large minority of bad actors, the conflict resolution seems somewhat slow. Bitcoin was made to attack proof until really the network is being compromised, but instead sacrificed on scalability. To me this system looks like it has full scalability, but lacks efficient protection and quick solution against an all out attack.
Could you expand on how you envision stake being counted into solving the consensus problem?
I'll list some of my thoughts and feel free to ask or suggest if you want more detail in another area. With Bitcoin, forks and rollbacks are a moderately common occurrence due to race conditions of multiple miners finding a solution or transactions being publish near a block solution boundary. Unfortunately this rollback affects everyone during the block interval to some degree though it's mitigated. With RaiBlocks there aren't these race conditions so need for agreements due to benign situations is eliminated. There only time an agreement is ever needed is when there is a definite malicious actor. This opens up some policy decisions where we can treat accounts with forks as second-class citizens and accounts without forks with priority and be sure we're not accidentally penalizing good people. The exact stake counting algorithm is as follows: * A published block arrives from the network, is checked for validity on the signature, balance delta etc. * If block was not rejected for invalidity * If we're not a representative, publish the block to everyone we're aware of without our signature. * Else if we're representative, sign a vote from our representative account including the block we're voting for and broadcast to everyone we know. * Else if the block was rejected for a definitive reason, bad signature, account balance is invalid e.g. greater, or we don't have the previous block in our ledger at all, drop the block and do nothing * Else if the block was rejected for a non-definitive reason i.e. some other block in the ledger already claimed this "previous" block meaning this is a fork signed by the account owner * If we're not a representative, wait and listen for votes and rollback and replace our block if some other block receives a majority tally * Else if we are a representative * Loop until one block has >95% of the vote tally and the total tallied vote weight > 95% of total supply * Tally the votes we have, if the winning block is different than our block, rollback and replace our block with the winner * Increase our vote sequence count and rebroadcast our view of the winning block * Wait a time period before doing another voting round For receivers the algorithm is extended a little: * A valid published send block is received that names an account we have signing keys for as the recipient. * Start tallying votes and wait a couple network propagation periods. * Every time a publish from a non-representative or a vote from a representative arrives, add it to the tally * After our wait time has expired: * If no conflicts have been observed i.e. no one anywhere has published a conflicting block, receive the send in to our chain * Else if there's a conflict, wait until the tally is > 95% in favor of our block before accepting or do not accept if the block is rejected by votes From this algorithm flow we can see that if no fork is observed only the receiver will tally votes. We can also see that non-representative don't sign votes or run a voting loop. Since everyone who inserts a block in to their local ledger rebroadcasts it to everyone they know, we can be sure blocks will be propagated quickly. If a receiver waits a couple propagation periods and receives no conflicting block broadcast, they can be sure if a conflict ever is broadcast, it will be quickly rejected because all the representatives have already made their decision and nodes only change their block if a majority says otherwise but we've already settled 100% one way. |
|
|
|
|
I think a good way to describe the consensus minimization is by looking at the example of how BitCoin and RaiBlocks deal with two transactions Alice sendto Bob and Alice sendto Charlie.
If both these transactions were included in a Bitcoin block, two valid solutions would be: B1 (AtoB, AtoC) and B2 (AtoC, AtoB) which would hash differently. No matter if a miner picks B1 ordering or B2 ordering, all balances after this block would remain the same. Bitcoin needs consensus on which order to pick because AtoB is not ordered with respect to AtoC so someone needs to fairly pick the order, a miner.
RaiBlocks has the account owner decide the order of these transactions before they're published to the network by the fact that they control the chain for their own account. The only time consensus is needed is if the account owner publishes more than one possible order.
RaiBlocks has a partially ordered ledger graph where it's a set of subgraphs for each account where the subgraph total order is decided by the account owner.
Bitcoin has a total order on all transactions which is a valid though stronger restriction.
As you observed, RaiBlocks doesn't have an N/x divisor for conflicts so bad actors will need far more agreements on their malicious transactions. The benefit is for good actors the number of agreements is 0 and conflicts in each subgraph have a degree of isolation between them.
|
|
|
|
|
Show Posts
