Bitcoin Forum

I’m hoping people would have some feedback on a project I’ve been working on.  The issue I was trying to solve was scalability: transactions per second and confirmation speed.  What I ended up with is a system similar to side-chains except it’s taken to the extreme where each account manages its own chain and all chains are replicated to all nodes.  What happens with this system is there are virtually no distributed agreements because each account has authoritative control over its own chain.  With the account owner having authoritative control over their own chain, transactions don’t need to be mined for validity so confirmation time drops to near zero and transactions speed is as fast as they can be published.

I was looking for some comments, good, bad, indifferent on what people think.

For gritty details I did a writeup here https://github.com/clemahieu/raiblocks/wiki/Block-lattice which includes information about double-spending

From what I have understood so far, this is not really a blockchain, or even crypto related concept, in fact it sounds to me like you have proposed a new standalone transaction system. I don't really see why you think that this concept is similar to sidechains, it rather sounds like a disitributed transaction server, with no need of a native currency. I saw you don't have comments in the source code, so I won't be spending much time for now to figure out what goes where.
How is this different from any off chain transactions?
You claim this is double spending proof, how do you collect proof form what you call an account, that he is overseeing his chain in a way the network deems ethical?
 

I called parts of it a block chain since the send/receive blocks contain a hash of the previous block and it has a one-follows-another order.  It's different than other cryptos in that one block is one transaction, a send or a receive, where others contain many transactions.

Thanks for spending the time you did looking at it, sorry about the lack of comments that's admittedly in poor style.

These differ from off-chain transactions in that each chain is replicated to all peers so all account actions are observed and validated by everyone.  Rather than packing all transactions in to a single chain, all transactions for a single account are in a single chain.

On the double spending front, since all blocks for each chain are replicated to everyone, nodes can ask and publish their view of signed Y-follows-X blocks.  If anyone instead sees a signed Z-follows-X block this is a fork and needs resolution.  Unlike monolithic blockchains, a fork in this system only affects a single account instead of everyone, again working toward scalability where we don't stall everyone because one section has an issue.

Resolution is done through a weighted vote system where losing blocks and dependents are rolled back.  Senders can be sure they're not receiving a double spend by observing votes and tallying them, if they observe no forks or a resolved fork they can safely accept the transaction in to their chain. Notice though that resolution is never needed in the normal, well-behaved case.  Forks only happen with signed, conflicting blocks; only accounts that are misbehaving by intentionally creating forks will every be put up for resolution.

Let me know if any of what I wrote doesn't make sense.

So a block is taken as a single tx id with timestamp? If so this seems to fall into the category of Transactions as Proof of Work. I still see a  number of challenges with this system. First up of course consensus; at what point can a transaction block be viewed as verified and have an acceptable level of cryptographic confirmations inside a network with an unknown number of peers. I actually see hard-coded rounds of confirmations as a possibility for this. Secondly, how do you make the attack you have just described as costly as possible. Since the Bitcoin community is always very passionate about strong security, that is so far unmatched by anything else, I am actually particularly intrigued by this point. Of course we can look at typical solutions like including a transaction fee, expanding the proofhash to multiple layers and reward good actors for their work.

I looked at this yesterday, and I'm glad to finally see a real thinking, stepping away from damn blockchains and wasteful Proof of Work!   So well done, and immediate respect!

Your "Block Lattice" is similar to our channeled ledger aka Transaction Forest, except you have many chains of transactions, we have many trees of transactions.  The name you chose is confusing though, as if each transaction acts in the same manner as in ours, there are no need for blocks at all.  If so, drop the blocks reference, step away from the crowd, it's confusing :)

At that point the similarities stop, perhaps because its a young project, or perhaps because you haven't hit a number of issues yet that you WILL need to solve.  

First and foremost, you NEED a consensus algorithm!  Nodes that are claiming the delta, will be susceptible to bad actors at each end of the network attempting to claim the same spend twice, and unless you have managed to find a way around network latencies et all and ensure that ALL nodes forward transactions honestly, you will have 2 transactions in the network attempting to claim the same spend twice.  

Secondly, you NEED a consensus algorithm!  Nodes that are spending, will be susceptible to bad actors at each end of the network attempting to spend past a zero balance, and unless you have managed to find a way around network latencies et all and ensure that ALL nodes forward transactions honestly, you will have 2 transactions in the network attempting to spend past zero.

Unless I missed something when I looked at the code (admittedly, I skimmed through), this is something you haven't solved IMO, you mention voting but this isn't really explained, and you can not rely on the transactions creating X->Y links themselves to be the authority when resolving forks/double claims and similar attacks.  Also, who signs these block and how are they selected?

That said, very commendable!  Anyone that thinks out of the box (like me :) ) I have a lot of respect for, and I'd love to chat to you more in a private manner.  eMunie is going to need some additional smart thinkers soon, maybe there is a place for you on the team.

Thanks for taking a second look guys, I took your questions to heart and thought the best way to explain was to create a couple graphics of how things work.

https://raw.githubusercontent.com/clemahieu/raiblocks/master/images/transaction.gif

The transaction animation shows the typical, non-attack scenario how transfer of balances occurs.  The contents of these blocks are almost exactly how it's done in the code, minus signatures.

The animation is:
1) Create send block linking previous head block and with a new account balance < old balance
2) Create receive block linking previous head and linking source block ensuring source hasn't been received already.

https://raw.githubusercontent.com/clemahieu/raiblocks/master/images/fork.gif

The fork animation shows what most seem to be interested in, consensus of bad-actors.
1) One or more signed blocks pointing to the same previous blocks are created and distributed to different nodes in the network
2) Nodes redistribute blocks they've just seen and soon everyone in the network has observed a fork
3) Nodes initiate voting by broadcasting their vote and tallying the votes of others
4) Nodes who are voting for a block with <50% of the tally change their vote
5) Consensus is achieved after a few rounds of voting

Going with the theme of efficiency and scalability we tried to making resolution as easy and efficient as possible.  We notice people marked as a receiver can keep their own chain separate from a bad actor trying to send forks to them, this way only the bad actor is stalled and the receiver can wait out the resolution until it's definitive.  This goes to the scalability where we stall only the people doing things the wrong way.

It's important to note the time window for a fork block getting anything other than a 0% vote is less than one network propagation interval.  Nodes in RaiBlocks rebroadcast their transactions so once everyone has received a copy, any new fork will get no votes.

I added the animations to the main description pages in the wiki
https://github.com/clemahieu/raiblocks/wiki/Block-lattice
https://github.com/clemahieu/raiblocks/wiki/Double-spending-and-confirmation

Thanks for the images, it clears up and confirms what I was thinking.

I understand totally how the transfer of balances occur, as I said before, its very similar to our method.

You consensus method is also how I expected, and I don't believe your method will work for 2 reasons:

1.  Sybil attacks:  It seems very trivial for me to create a large quantity of nodes that can vote on whatever I like, and there doesn't seem to be any mechanism to prevent it, every node seems to have a vote, period.  ( I notice REP in your animation tho, what is this, node reputation?  If so where does that reputation come from?)   So I pay someone at one end of the network, it gets accepted, I also pay someone at the other end of the network, which *may* gets accepted if I'm quick enough.  Voting happens, all of my nodes then vote for the 2nd transaction and that is the one that is honored.  In real world, Ive may have just spent them twice, as the first payment was initially accepted and the merchant/receiver/whatever gave me what I paid for ( assume I was at a store paying for some goods and left immediately).

2.  Efficiency:  Perhaps I misunderstood, but when voting happens, these votes are broadcast around the network?  How can you be sure that everyone receives (and honors) the votes they receive, and broadcasts them on to the nodes they are connected to so that they can also do the tally?  This seems like a mammoth task orchestrating all those votes over and over, and will certainly push bandwidth use up if that really is the case.

Thanks again

Also this line:

4) Nodes who are voting for a block with <50% of the tally change their vote

What if they don't?  And why are they forced to do so?  What if the block they are voting for is the correct block, and everyone else voting up the incorrect one are dishonest?

If the incorrect block makes it through naturally then so be it, but I dont think you should force nodes to change their vote just because they aren't batting for the majority block.  Plus you can't even be sure that nodes are changing their vote, unless you have every node review all votes of all nodes in the system.  Then you get into the realms of O(n) work/bandwidth loads.

Thanks for the kindness, much appreciated :) 

But lets not derail this thread from the good work this chap is also doing  8)

Hey hey, don't forget simcoin.

To prevent a Sybil attack, votes are weighted based on account balance, the only way to have a larger vote is to have more value stored in the the protocol. People voting against the protocol are voting to destroy the value they hold in the network I.e. Burning your own money.

Rep in this context is representative. The concept is to address your good second point, votes flying around the network. Each account can designate another account as their representative and the rep can vote with but not spend with their balance weight. Also note that voting is not initiated unless a fork is actually observed.

Nodes not flipping their votes is analogous to Bitcoin nodes not taking the longest branch, it's not really Bitcoin anymore. Nodes trying to publish blocks from orphaned forks will be rejected because the previous hash value is not a valid block and receivers won't accept these blocks because then their chain would be invalid.

Ok, so the weight of a vote is as per the stake of the voter, makes sense, that will work to a degree.

I'm not getting the representative part (or the point of it):

Alice has a balance of 10
Bob has a balance of 20
Tom has a balance of 100

Do Alice, Bob and Tom pick one of the other to be the representative of their vote?  So for example, Alice picks Tom, and Tom picks Alice, then Alice's vote holds more weight than Toms?  What if everyone picks Tom?  Alice and Bob could be dishonest, pick Tom as their rep, they control the network, even though Tom is the honest one but cant vote with his weight.

Perhaps I'm wrong in my understanding of this representative voting due to lack of detail.


You'll get forks, and plenty of them, there will always be some asshole trying to cheat :)

I think you're describing it accurately.   Any account can be a representative and accounts can change their rep at any time.   If accounts named each other as you described they would have vote weight as you described.

*edit* I think the description of representation was backwards. If Alice and bob name Tom as their rep, Tom has all the vote strength and Alice and bob have none even though Alice and bob have a balance. Representation is giving weight equal to your balance.

One thing to note is that voting only happens if there is a signed conflict so the easiest way for your account to not be susceptible to collusive votes is to not sign forks; only cheaters are voted on. Collusion of voting is analogous to collusion of miners in Bitcoin. The difference is how much does it cost. With mining the cost of getting >50% strength is the capital investment in hardware to mine that fast. With voting collusion the cost of getting >50% control is the market cap of the entire currency.  Market cap of currency > capital investment of mining hardware and it isn't susceptible to technology advances e.g. Gpu -> asic so I feel this is a stronger guarantee than mining.

Read most of your stuff, this is indeed very similar to Simcoin, down to UDP, Ed25519, C++ code and even some function names, like app_path() ;D Spooky.

Anyway, this part got me confused:

"Unlike existing cryptocurrency systems, this rollback only affects the account involved in the fork instead of affecting all transactions during a time period."

If Alice creates a block to send to Bob. And then Bob creates a block to accept it, you now can't rollback Alice's block without also rolling back Bob's.

Now, what if Bob already sent money to Charlie? Does this mean that his second transaction must be rolled back too, simply because his account chain is now broken?

It's a good observation. The "accounts involved" in the context you described would roll back the send to Charlie in bob's chain as well as the receive from Alice in bob's chain. And finally the losing fork in Alice's chain.

Two things to notice here is that all the thousands of other accounts uninvolved aren't affected at all, this is the advantage of the individual chains.

The other thing to notice is bob could guard against having his chain rolled back by allowing time for him to observe possible forks. How long does he have to wait?  About one network propagation period because by then, someone somewhere would have rebroadcast the block and if they haven't, the fork will have a very low vote percentage because everyone's already agreed on the first block.

The worst case scenario for forks is creating n forks and distributing it to n representatives with close to equal vote strength simultaneously. Then bob should wait until the vote total is statistically definitive in his direction, >95% or a heuristic before accepting it.

Bob can still continue accepting from non-forks and sending to others even if he is named as the recipient of a forked block. Bob could also choose to never accept the forked block if he wanted.

Yeah, all the other stuff was already clear :)

It's just that that particular statement should probably be rephrased - the rollback is not limited to a single account in a strict sense.

I will think more about all this, but for now one thing seems clear - a system like this has a very low tolerance for problems that cause rollbacks. I understand all your points about network propagation, I've been working on a similar system for 9 months after all :)

What you need to account for is attacks and network problems. What if half of your representative nodes got DDoSed? What if a large part of the network gets disconnected?

Under perfect conditions it's easy to make things work, even Ripple thought they had it. And now they admit their consensus is broken.

Decentralized consensus is hard :(

Here here, we've been through 3 different algorithms in the past 18 months before we found the right one that meets our needs and is solid!

These are great points. One thing nodes will be able to do is track the total weight of votes that have been received for a forked block. If this is noticeably lower than the total supply indicating disconnection of representatives, nodes can leave forked sends unreceived until they're satisfied the block has enough integrity for them to accept it.  This would be analogous to observing hash rate significantly dropping indicating miners being disconnected. If representatives are being DDOSed they can choose to not touch forks so well behaved accounts have no problems and accounts generating forks are unable to transact.  

If the network gets partitioned I think the problem would be equivalent to if the Bitcoin network somehow got partitioned. The partitioned segments would be continuing on their own sections until the networks merge and one side gets evicted. One thing to notice though is all it takes is one node connected to both partitions for them to begin to merge.

It would be incredibly hard though hypothetically feasible for the network to be perfectly disjointly partitioned and one fork to be placed in exactly one partition. In this case we'd have to fall back on observing vote totals dropping indicating massive disconnection.

Heuristic suggestions are welcomed!

It's recommended that people pick reliable and diverse representatives, universities, enthusiast groups, corporations, placed on platforms designed to deal with all the problems any popular network service needs to deal with.

;D

You didn't forget to cross your fingers while saying it, did you? :)

--

@clemahieu, as much as I doubt Fuserleer's sanity, one thing he was spot on is that the core of your system is not how exactly you arrange your ledger or how accounts will interact with each other.

The core is consensus - it's an age-old and difficult problem, that's why everybody praises Satoshi so much - he was able to find an original solution for that problem.

We, the 2nd and dare I say 3rd generation coins, are trying to solve it via PoS and some clever trickery.

Right now you don't seem to understand that consensus is the main problem and think of it more as a secondary feature to help you solve some border cases.

It isn't. It's a thing that will drive you mad in 3 months.

--

"It's recommended that people pick reliable and diverse representatives, universities, enthusiast groups, corporations"

Right... Now you're reinventing Ripple with their Unique Node Lists. We've already been there :)

Sorry to kinda rain on your parade, but the sooner you realize what your main enemy is, the sooner you will be able to focus on it and start looking for solutions.

Hey, leave my sanity (or lack of) out of this will ya :p

I do believe that our consensus is (now) solid, we've been through it many times (as a group), smart members of our community have spent extended periods of time with me at my home and we've ripped it to pieces trying to find a hole, we've even had some external input and theory review from a number of sources.  Paper will be available publicly soon that gets into most of that, so you can forge your own conclusion :)

But yes, I also agree with NxtChg, creating a novel transaction system is hard, and you've gotta be smart to do it.  Creating a novel consensus, that holds up under ALL attack vectors is quite another beast unto itself.


Ahh......perhaps I am insane after all.....  ??? ::)

I like where you are going with this RaiBlocks, but please please please, don't do what the rest do and rush it....take your time and review and refactor as many times as you need to get it RIGHT!

I'm glad you're skeptical, there are a lot of people with incorrect ideas out there and I don't want to propagate another.

One thing I think is worth pointing out is the focus on decreasing the number of consensuses that need to be agreed on. With existing cryptos every transaction for everyone is subject to consensus and as you correctly pointed out, consensus is hard.

The attempt was to arrange the protocol in a way where consensus is almost never needed.   If we can change the system so we need to do the hard problem a lot less, we've hit scalability.  In fact it's arranged so only bad actors are punished by the slow path of consensus and I think that's the value.

Thanks for the ongoing critique guys, I appreciate smart people working to break thing :)

Nice, especially if other people worked on it ;)

I don't see it as a competition or organ-waving contest, so if you, guys, invented something new and working, that would be great.

--

@clemahieu, scalability is not having O(n*n), which you do, same as everybody else, including Simcoin :)

But that's philosophical...

I don't think you managed to limit the number of consensus actions in any way. Everybody must agree on all blocks, right? Practically twice for each transaction versus once per 1 Mb block in Bitcoin or once per 255 transactions in NXT.

If anything, blockchain-less design increases the complexity enormously! I dream about having a single blockchain, like NXT! :(

eMunie attempts to achieve the same thing, where consensus in the traditional sense is only required in certain scenarios.  For everything else there are (for want of a better term) "trust but verify" algorithms which run on everything that comes in (and out) of a node.

Resolving a fork is difficult, preventing a fork is easier if you are smart and have algorithms in place that can detect the potential for fork activity BEFORE it even happens.

A lot of people think of a consensus algorithm as a single beast of an entity when in actual fact it doesn't have to be that way.  Consensus can be many smaller algorithms, running at different times for different events, but as long as the end goal is that all nodes agree on "something" it doesn't matter.

For example, eMunie runs a UVTX (unverified transaction) check on every transaction that comes in, it checks the balance, it checks the proof, it checks if the proof is a singleton proof (can only be used once), and if so checks the ledger to see if its been used before.....another example are "chargables", where a transaction is made to pay for some service.  A different piece of validation code runs a slightly different algorithm for that, which builds on the default...etc etc

Point is, all these mini-concensus algorithms can run, without any interaction with the network at all until a potential issue is found.  Most of these issues are found even BEFORE the culprit transactions are even in the ledger, and all honest nodes detect the same issues, so the transaction just gets ignored.  Result is you avoid having to do work on many more fork resolution cases than you otherwise might.  Down side is you need a lot of architecture handling all kinds of functionality to detect and react to these pre-emptive fork signals.

In the case of RaiBlocks, unless you haven't detailed it, your only consensus detection is the block links X -> Y  /  X -> Z  at that point you are already forked, and you have to do potentially disruptive roll backs to resolve it.

Of course not :) I just wanted to make that statement in the public domain, but mainly to give clemahieu some idea on how much work we've had to put into consensus.


*pah* Blockchains are easy :p .... us and clemahieu are playing with the devil  ;D

Blockchain-less designs are more complicated, and you do need a lot of extra "stuff", but the benefits FAR outweigh the cons IMO.....proof is in the pudding too, I posted some stats on our tests yesterday and they are VERY encouraging.

But that doesn't sound like 'consensus'. It's a normal check, which each node obviously would have to do. Same in my case.

Consensus starts where multiple nodes are involved and need to agree. And they need to agree on legit transactions most of the time.

The fact that you can filter clearly bogus transactions before that, doesn't make it much easier...

EDIT: Anyway, I will just wait for your paper :)

I disagree, consensus IMO is any activity which results in a set of actors coming to the same conclusion, a general agreement.  These "trust but verify" actions do just that, so long as you are an honest node you'll come to the same general agreement as everyone else.  

Consensus in Bitcoin is the same, no nodes actually speak to each other and say "hey Tom, which of these 2 blocks is the right one??"  it is achieved via a set of rules, which produce a result depending on the data provided and the data already collected.

Once you take mining out of the equation, which act as the inputs, then you either need to replace it with some other form of globally verifiable input, OR you need to start talking to each other in critical situations to determine what is legit and what isn't, but for the most part "lazy" consensus does the job just fine.

This requires an important assumption that they all received identical input.

And then you are back to the same problem of agreeing what exactly that holy input is :)

The code defines the properties of the expected inputs, honest nodes have the same code, so they are already in agreement.  They all agree what inputs are good, and what inputs are bad, for ALL inputs, ever, even before they exist because of the rules of the code.

Honest nodes ALWAYS have consensus with each other whether they know it or not...its the dishonest nodes that upset the balance.  

Example:

you think Satoshi is a genius
i think Satoshi is a genius
we have never spoke
we meet and I mention Satoshi is a genius
you agree
did we come to a consensus then, or did we always have a consensus?

This doesn't make any sense. No matter what the rules for validating input are, if you run 2 programs on 2 different sets of data, they will produce different results.

Example 1: Node Alice received particular legit tx, node Bob hasn't (network problems).
Example 2: Node Alice received properly signed tx to send to address 1, node Bob received properly signed tx to send to address 2.

Unless they talk to each other they won't reach the same view of balances. And when they talk, they have to agree.

Satoshi's solution made it possible to have the "same input" by making sure that producing alternatives is extremely costly.

And even that is not completely bulletproof. You still need to talk to each other to see if there is a longer chain available and the system is open to 51% attack.

But anyway, let's not hijack this thread :)

If you managed to solve it, I will read it in the paper. I don't pretend to know all the answers, maybe I am wrong.

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.

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?

The order is only part of the problem.

Account owner is not authoritative. Why are you saying that

"The only time consensus is needed is if the account owner publishes more than one possible order."

as if it will be some small obvious cases only? Don't you realize that it's not "only time", it's "every time"?

Because nodes have no way of knowing, whether each block is unique or an attempt to double-spend.

That's why they have to agree on each block, that there are no double-spends.

So instead of everybody agreeing once per big block, now everybody needs to agree per transaction.

--

And another question - how do you plan to deal with bootstrapping? Let's say I am a node and I was offline for an hour. At 100 TPS it will be 360,000 x 2 = 720,000 new blocks for me to download.

And I need to get consensus on all accounts involved!

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.

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.

Yeah, that's why I deleted the message, I realized you can start synchronizing on the next tx if you detect a gap.

But I thought a bit more about it today, so here is another scenario:

Let's say for simplicity we have 10 representative nodes with the best case of evenly distributed stake.

First of all, forget those crazy consensus numbers, like 95%, because then it would only take me to own 6% of the stake to be able to block any transaction I want. So the consensus will be more like 70/30.

Now imagine that I, as an attacker, have an ability to DDoS (and thus put offline) any 2 of the nodes.

I start an attack on nodes #1 and #2 and continue it for 4 hours. So those nodes miss a couple of million transactions (at 100 TPS). The rest of the network will work ok, since the quorum is still reached (80%) and all transactions are processed successfully and chained to each other.

After 4 hours have passed, I switch my attack to nodes #3 and #4. And - boom! - suddenly no one who did transactions in the previous 4 hours is able to use the system! Why? Because 2 nodes are offline and 2 nodes missed our previous transactions. So now we only have 6 nodes (60% of votes), which is not enough.

And who does transactions constantly? The big sites! Exchanges, shops, etc. So I was able to effectively paralyze the whole Rai world :)

Those who haven't been using the system in the past 4 hours will continue to work. But after 4 hours I can switch to another pair of servers, fragmenting the system even more.

At this point it becomes difficult for me to analyze, but I think you can eventually get to the state where none of the participants have enough correct information to be able to jump start the system ever again :(

--

And that's not all.

At some point I can activate my own nodes to start broadcasting a double-spent block.

Since now there is no consensus on my previous transaction, I can add a little stake to sway the vote to accept my other double-spent block.

If this happens, then the fork invalidates all transactions for whomever had a bad luck of accepting money from me, like, uhm, a big exchange for example - now it lost 4 hours or more of all transactions just because of my little prank. It won't be happy.

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.

Yeah, it would be great to find a way to make chains in such a way that a single block doesn't invalidate the rest of it. Preferably without using trees :)

In case of incoming txs it's relatively easy: the account owner just needs to re-accept them and will gladly do so. With outgoing, on the other hand, it's not that clear...

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.

this is a nice project. :)

Thanks BTCspace!

We just released version 5 which included a lot of improvements to the wallet and core.  https://github.com/clemahieu/raiblocks/releases/tag/V5.0.0

For those interested in the earlier discussion about attacks I created a wiki page outlining possible attacks and built in safeguards https://github.com/clemahieu/raiblocks/wiki/Attacks

Any updates on this? Long time nothing new here  :(