Block lattice project

[clemahieu]

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

[NxtChg]

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

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!

[Fuserleer]

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

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.

[Fuserleer]

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

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.

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.

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

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

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.

[NxtChg]

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

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

[Fuserleer]

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

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...

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.

[NxtChg]

I disagree, consensus IMO is any activity which results in a set of actors coming to the same conclusion, a general agreement.

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

[Fuserleer]

I disagree, consensus IMO is any activity which results in a set of actors coming to the same conclusion, a general agreement.

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?

[NxtChg]

The code defines the properties of the expected inputs, honest nodes have the same code, so they are already in agreement. 

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

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.

[clemahieu]

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.

[DrGrid]

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?

[NxtChg]

RaiBlocks has the account owner decide the order of these transactions...

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!

[clemahieu]

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.

[clemahieu]

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.

[NxtChg]

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.

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.

[clemahieu]

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.

[NxtChg]

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...

[NxtChg]

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?

[clemahieu]

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.

[BTCspace]

this is a nice project.