Intercoin Technology: Consensus


#1

People can set up a line of credit among themselves without the permission of any third party.
The problem with this mechanism, known as trustlines, is that when A and B agree that A will owe B, B doesn’t know how many other debts A has outstanding. Attempts to solve this problem have given rise to centralized credit agencies and credit ratings, sometimes with disastrous consequences for privacy.

Thus there is a need to have a third party system that can reliably record who owns what. The recipient B of a token T should be able to query this system to make sure that A owns the token, post the transaction and verify that B has become the new owner. This system must have Consistency and Durability.

Over the last decade, innovative solutions have been proposed and implemented to move from centralized systems to ones that distribute the work among many different computers. These new systems are typically referred to as Distributed Ledger Technologies (DLT) and the process by which they move from one consistent state to the next is referred to as Consensus.

Voting vs Disproving

Any process by which computers arrive at the same answer can be called Consensus, but there is a major distinction to be made. Consensus can either be based on Voting, or Disproving. Voting-based consensus is about agreeing on an arbitrary outcome (such as a number between 1 and 10, the location of a beehive, or which valid transaction was first), or about disproving a claim (such as done in science and math). This will hit home for many people when they consider how is truth determined in the current political climate. If enough people believe something, does it become true? In science and math, it takes even one participant to publish a disproof of a claim, to compel everyone who sees the disproof to realize the claim is false. When the book A hundred authors against Einstein, came out, he is reported to have said, “If my theory was wrong, one would have been enough.”

That kind of approach to determining truth has very desirable properties. For one thing, it is resilient in the face of 33% or even more malicious validators. This means the network can tolerate a higher amount of interference from large scale Sybil attacks, computer viruses, etc. that other projects also worry about.

Sharding

Most popular crypto-currencies today (see the next section) need the network to reach a global consensus about every transaction in the world. This can be slow and expensive. In principle, one could distribute the workload among many computers, creating an embarrassingly parallel network capable of handling more transactions the larger it grows.

A mathematical analysis from 2009 shows that the probability of double-spending can be reduced to nearly zero even when consensus groups are fairly small, as long as they are strongly interconnected. This is even true if the group can be predicted in advance from a token id, and even in the face of a coordinated attack on a certain proportion of nodes in the group. Of course, such possibilities themselves can be mitigated by having the network consist of computers under the control of many different parties, that all link together into a giant decentralized “cloud”.

Intercoin Consensus Process

Thus, Intercoin Consensus Process is not based on voting about which transactions went first, as is done by Hashgraph and XRP Consensus Process. In that case, too many malicious participants could either undermine the consensus by casting contradictory votes, or prevent the system from making forward progress, as explained here.

Under the Intercoin Consensus Process, when two conflicting transactions are submitted close in time to one another, both are rejected, instead of voting on which one was first and gets to be honored. The Process works like this:

  1. A token T is watched by a set of Watchers, computers in the decentralized cloud. These Watchers only care about the hash of the latest state of T, as it goes from person to person.

  2. The transaction is a message that is posted to the token’s stream. The “head” hash of T becomes h(a, b) where a is the hash of its previous state and b is the hash of the transaction.

  3. Each Validator for T validates the transaction (that the sender owns T, that T was validly issued and has a valid history, and so on). Validators that don’t find any problems sign that the transaction is Valid. A validator that finds anything wrong will gossip a Claim of Violation, and if the recipient B agrees with this claim, they will reject the transaction. (B can only hurt themselves by ignoring a valid Claim of Violation, because they will likely not be able to get more conscientious recipients later to accept T as payment).

  4. Participants (Validators, Watchers, etc.) which submit spurious Claims will get subsequently ignored by those who find the claims to be false.

  5. If a transaction is Valid, the Watchers go to work making sure there was no conflicting transactions that would fork the stream. (This might happen if the token holder was attempting to double-spend, creating two valid but conflicting histories.) Each Watcher is sent the transaction and has to check whether it has already been sent a conflicting transaction. If no, then the Watcher says it didn’t see any conflicts. Otherwise the Watcher gossips a Claim of Conflict with one or more conflicting transactions signed by A. As long as B receives a valid Claim of Conflict from even one Watcher, they will reject the transaction.

  6. Each honest Watcher will report a Conflict, and will also honestly check the Claim of Conflict from other Watchers in the consensus about transaction X on token T. If the Claim of Conflict checks out, the transaction is rejected. Thus, if conflicting transactions X1 and X2 are submitted simultaneously, both are rejected. If one is submitted well in advance of the other, then as long as a (super)majority of honest Validators and Watchers has approved it, it goes through. Something in the middle could happen, where X1 is submitted and some watchers already approved it, but then a valid (but conflicting) X2 is submitted to some of the Watchers who haven’t yet reported in. Since any two honest majorities overlap, however, only one of these transactions can ultimately succeed in getting a (super)majority of honest Watchers to approve it.

  7. The Watchers need to be strongly connected, so a malicious subset of Watchers can’t disconnect the Quorum of the honest ones, or block their gossip. Each Watcher waits to receive responses from a (super)majority of Watchers about the transaction. If any Watcher W1 approves a transaction X but also gossips a Claim of Conflict about X, then if the Claim is true, every other honest Watcher ignores the approval. However, since Watchers giving different replies to different participants is bad form, the watcher W1 may be ignored from then on, potentially changing the threshold for the (super)majority.

  8. Once a (super)majority of honest Watchers received verdicts from a (super)majority of honest Watchers, and they all reported not finding a Claim of Conflict, they group-sign their approval of the transaction X1. (Even if one or more conflicting transactions X2 are partially making their way through the Watchers, or will start to in the future, they will get rejected.) This approval, in particular, is sent to the intended sender A of the token T.

  9. The sender A then makes a decision of whether to “endorse” the transaction X1 with their signature, and give the approved, endorsed transaction to B. The reason for this extra endorsement is that the Intercoin Consensus Process about token T may have taken a very long time (e.g. due to a netsplit or too many malicious Validators or Watchers preventing an approval), and A may have changed their mind about proceeding with the transaction. A may elect to send some token T2 to B in the meantime, watched by a completely different set of Validators and Watchers and endorse whichever transaction goes through first. (This is similar to using a different credit card to pay a merchant, when the first credit card is blocked. You don’t want both transactions going through in the worst case.)

  10. The Permissionless Timestamping Network can be used to implement a timeout so if a group of Watchers cannot come to a Consensus for a while, the Token is migrated to a different group of Watchers, so as not to be “frozen” forever.

Notes About the Process

After a (super)majority of honest Watchers they haven’t seen a conflicting transaction, even if the very next Watcher finally reports a conflicting transaction (because it was slow, for example), the first transaction is still approved. Thus there can be a sudden jump from “approved” to “not approved” around the supermajority mark. This doesn’t violate Buridan’s Principle because the number of participants is finite, and in fact pretty small (under 1000) so the continuity assumption is not satisfied.

Normally, Merkle DAGs consist of hashes and do not have information about the contents of a token or transaction or claim, so they can’t make prove or disprove anything in the content. However, a Claim contains the actual content, and enough relevant (signed) context for any honest participant to come to a conclusion whether something is true or not.

Because this system of Consensus is based on Disproof rather than Voting, the end-users are ultimately deciding what truth to go with. If any Validator, Watcher or Group signs a false Claim, they can subsequently ignore those, and gossip a Claim of Malfunction to others similarly to how a Claim of Conflict or Claim of Violation is gossiped.

If groups of end-users disagree on which subset of Validators or Watchers is really right, they may end up forking the network. That can happen, for example, whenever the rules change and some clients prefer the old rules and some clients prefer the new ones.

In the particular use-case of a crypto-currency, the incentives really come from the recipients of a token (B in this case) wanting to make sure everything went through correctly, and the system recorded B as the owner of the token. That is, until they give it to another party.

Files

The question of who owns a token is a special case of access to a file. Spending a token can be considered like appending (or even replacing) content in a file representing that token. Not every node needs to store, decrypt or validate the entire contents of the file. Many nodes just want to know the latest hash of a file.

The Qbix Platform has the concept of Streams and Messages, which can be used to implement collaborative activities of any kind. One or more people can take “actions” in a stream, and “messages” are the result of a successful “action”. When implemented in a distributed system, Watchers are used to look for forks in a stream, and report this to end-users. Thus, Consensus about forward progress is achieved by end-users who all agree to honor valid, conflict-free transactions. Disagreement among end-users manifests in a fork of the entire back-end Consensus underlying that particular stream.

Streams can have different types, and “Intercoin/token” would be just one of those types. Others can include chatrooms, games, collaborative documents, social network / scuttlebutt feeds, and much more.

Validation is done by adding and removing rules about which actions are valid. The action of adding and removing rules is itself validated against the previous rules in the history. Rules are expressed in deterministic Javascript run in a VM. In initial implementations, the VM is given a limited timeout to run, and rules succeed if they return true before the timeout. Later, v2 of the language may be restricted to be loop-free so as to be guaranteed to halt, eliminating the occasional non-deterministic race condition with the timeout.

Rules are run by Validators and Participants who can decrypt the stream. Watchers and others storing the stream encrypted at rest have no idea what is is in it. What this means is that Intercoin Tokens (and other types of group activity) could be able to be sent completely anonymously, where only only the sender and recipient know each other’s identity.

Other Well-Known Approaches

Some early systems, like Bitcoin and Ethereum, use a form of leader-based consensus based on Proof of Work. Every so often, a leader is found that is then incentivized and empowered to append transactions to an ever-growing ledger. All new transactions on the entire system need to be sent to this leader. If this leader is known in advance, it could be blocked by a DDoS attack. However, with Proof of Work, leaders are computers which finds a solution to a Proof of Work problem (like partially reversing a hash), so by the time a leader reveals the next block, it’s too late to stop the gossip. However, now every potential transaction has to be sent to every potential leader in case they become the next leader (the “miner”). Proof of Work systems have extreme scalability problems, but they do have one nice property: as the network grows, it becomes extremely hard to rewrite history very far back in time, because doing so would require doing at least as much work as the network has collectively already done.

Proof of Stake and Delegated Proof of Stake replace the work element with a “stake” element, in an effort to reduce the amount of work needed to be done to find a leader. All these approaches, however, still require a leader, and thus have a bottleneck.

The XRP Consensus Process avoids this problem, but still needs every node to validate every transaction. In 2018, Ripple has made speed improvements to their Consensus protocol, making it more asynchronous. It can even be [sharded in the future](https://twitter.com/GregMozart/status/937836892661444610. However, it is still vulnerable to more than 33% (perhaps even 20% in fact) malicious nodes. To protect against Sybil attacks and other malicious nodes, Ripple Inc. publishes (and signs) a Unique Node List, making them a centralized gatekeeper of who can participate in the network. This approach is far more scalable at the cost of permissionless participation of nodes in the network (i.e. not just anyone can start running their own miner).

Since Intercoin (and Qbix) aim to create a resilient and reliable system for group activities implementing various rules, including those for cryptocurrency payments, we need small and fast consensus groups. Using Kademlia, we can also hide the IP addresses of the validators, preventing any given actor from finding and blocking all the nodes in the network. We are building a network where people can transact quickly and reliably, in full confidence that no one except those they authorized can tamper with their data, take it down, or even access it. People will be able to participate in all kinds of online group activities without having to trust a specific “landlord” to host those group activities.

Previous Topics:
Intercoin Technology: Background
Intercoin Technology: Architecture
Intercoin Technology: The Tokens
Intercoin Technology: The Ledger

Next Topics:
Intercoin Technology: Mitigation
Intercoin Technology: Recovery


About the Technology category
Intercoin Technology: Overview
Intercoin Technology: Architecture
Intercoin Technology: The Ledger
#2

If two conflicting transactions are both rejected, then there is no cost to issuing conflicting transactions. It would seem that an attacker can produce an unlimited supply of conflicting transactions and they would all be relayed by the network and the attacker would never pay any fee at all since none of them would succeed.

This consensus scheme also places very serious limits on what transactions do. For example, consider a cross-currency payment transaction. How do you agree on which offers were consumed by the transaction? Or if it’s a smart contract, how do you agree on what the contract state was at the time the transaction executed? Suppose dozens of people can issue transactions that use the same smart contract. What stops someone from issuing conflicting transactions to all of my transactions and thus jamming them?

This might work on a very trivial transaction design, but it seems to make flexible transactions impossible because there’s no actual consensus mechanism to agree on the time when a transaction executed.


#3

Why would this necessarily be the case? If someone submits a transaction, but doesn’t own the token, the transaction is rejected early on. Anyone can send a malformed request and spam the network - such requests need to be dealt with and ignored as early as possible.

Since all requests are required to be signed, the entities which process the request can charge that person’s corresponding account, whether or not the transaction is ultimately rejected. These two things are independent. It is a bit how Ripple requires people to have 20 XRP in their account in order to even start a transaction.

In the Intercoin network, each currency is a sidechain of the ITR network. ITR tokens are simply stored on reserve and claimed in atomic swaps with the local currency tokens. Cross-currency payments are simply two such atomic swaps from X to ITR and then ITR to Y. The X and Y are just claims on ITR tokens.

How do you define a “smart contract” here? See the Files section above. The tokens are just a special case of general purpose activities, called Streams in the Qbix Platform. The activities have rules written in deterministic Javascript. This architecture would seem to have enough flexibility to implement everything from cryptocurrencies to contracts to multiplayer games.

What stops someone from issuing conflicting transactions to your transactions with token T that you own, is that they can’t prove they own T. More generally, S can be a Stream with arbitrary rules and many participants with varying access controls and various types of actions and rules in its schema. We have years of experience building that kind of thing at Qbix.


#4

Okay, I guess if you’re only interested in a single use case, then the limitations of this consensus scheme might be acceptable. But you fundamentally misunderstand my criticism of the spam risk.

Conflicting transactions each appear valid individually. If your scheme for dealing with conflicting transactions is to ensure that neither of them execute, then I can produce billions of transactions that individually appear valid but will never execute. This permits me to impose unbounded costs on the network at no cost.

A scheme that ensures one of any set of conflicting transactions executes promptly does not have this property. A scheme that does not rely on relaying of conflicting transactions does not have this property.

Your claim that you can charge an account without a consensus is simply not true. You need a consensus to charge an account. And if you’re going to reach a consensus to charge an account, you might as well reach a consensus to execute a particular transaction. Both tasks are equally easy or difficult. If you’re going to assume you can reach a consensus to do a particular, exact thing in the face of conflicting transactions, why make that thing executing none of the transactions rather than one of them?

If you’re going to argue that you can react to conflicting transactions by executing a particular thing that you can only do when you have a consensus, then you could just as easily make it executing one of the conflicting transactions. You get absolutely no benefit whatsoever from your decision to prove invalidity as opposed to ordering transactions. But you do pay heavy costs – you can only execute trivially simple transactions, fundamentally limiting what your system can do.


#5

Yeah, for now the main use case is community currencies that you can confidently transfer between people. We want the system to be massively parallel (no singletons) and resilient even in the face of 33% of nodes being compromised, if possible.

Perhaps! The question is, why do you think we need consensus in order to charge transaction fees?

Transactions fees are a funny thing. You are right, if the fees are zero to a use a resource, then someone can abuse that resource. But there are many solutions for this, e.g. each particular resource provider can enforce quotas for each client they know about. This is already done by services on the web for decades, e.g. authenticated sessions. Of course, the actual check for the client’s capability to access the resource has to be done, and that itself consumes some resources. You could have a sybil attack from a botnet that each computer will register an account and later spam the network with invalid transactions and traffic. (Invalid in the sense that the data is garbage or they don’t really own the token, not even getting to the point of two valid conflicting transactions.) How would Ripple prevent that?

If you allow anyone to join the network and transact at any time, then yes, access to the resource may itself have to be a cryptocurrency. But it doesn’t have to be so nice as to prevent a double-spend. If your “gas” account has X amount in it, and you issue Y in transactions, then at the end you end up with X-Y in “gas”, because all your signed transactions (even invalid or conflicting ones) were gossiped, so everyone knows you have X-Y. Will you be able to spend Y > X if you issue them “real fast” before the validators and watchers realize what’s going on? Yes. But you’ll be only be able to do it once, before you are banned. Or expressed in other words, if you issue multiple transactions, in this case all your “gas” deductions count, instead of none, and your “gas” balance becomes negative.

You’re going to need some ledger to store that “user A used resource B” but you don’t need to have consensus in the sense of voting for that, either. If all you’re trying to do is deduct fees, and you are OK with giving every user one “burst” of (valid or invalid) signed transactions to overdraw their “gas” account, it won’t matter what order they do them in.

Sybil attacks are tough to prevent. Ripple’s network would still need to parse a request, realize it’s not garbage, check the signature, and check that someone has 20 XRP in their account. At any point in that process, the network can be DDOSed. How would you prevent Sybil attacks while at the same time allowing anyone to create an account?


#6

If you want to design a system where security relies on trusted nodes deciding to ban people without a consensus, then it’s not a decentralized, censorship resistant system. I guess I don’t understand what your requirements are, but if you need a consensus scheme for very simple transactions that doesn’t have to be censorship resistant, then perhaps this might work.

The lack of any actual consensus on the state of the system also worries me. Systems like bitcoin and XRP Ledger have full public state. With this scheme, there’s lots of internal state that’s not actually agreed on. This makes it very hard for any individual to predict what the system as a whole will eventually do. We haven’t had systems with this property, so it’s hard to know what consequences it will have.

For example, consider a node that loses its database. It won’t know what conflicting transactions it has seen. So when it sees a new transaction that conflicts with prior transactions that didn’t execute, how will it know not to approve it? A spammer can not only require unlimited relaying but also unlimited storage and the only control is unilateral suppression decisions. That assumes you can tie actions back to the actor and requires nodes to keep a secret blacklist. How can you identify malicious nodes when nodes are supposed to have secret blacklists?

Don’t blindly compare this scheme to consensus schemes like the one the XRP Ledger uses that solve much more difficult problems and provide features like censorship resistance and execution of complex transactions with rich public state.


#7

I understand that XRP Ledger solves much more difficult problems than just changing the ownership of non-divisible tokens. But you’ve basically said this system works to accomplish that limited use case, even while being resistant to 33% malicious nodes unlike “voting” based consensus approaches. You’ve basically said the downside is that someone can DDOS part of the system by spamming valid but conflicting transactions. So I don’t understand how that’s any different than what happens in Ripple. What happens if someone has 40K XRP and submits 20,000,000 “valid” but conflicting transactions to various nodes and gateways, each spending 30K XRP?

How does Ripple prevent DDOS of the phases of a request where a node has to:

  1. parse the request
  2. realize it’s not garbage
  3. check the signature
  4. check that someone has 20 XRP in the account

Wouldn’t #4 require each node to keep everyone’s account balance anyway, and have to engage in consensus to get it?

In XRP Consensus, every node would just aggregate every transaction from everyone anyway, charge the account, and then approve the “first” ones. That’s just as much work as aggregating the T-related transactions, charging the account, and denying the conflicting ones. If anything, it’s actually less work to deny them because as soon as you see even one report of a conflicting transaction, you’re done worrying about it for a while. So when it comes to DDOS specifically I don’t see why this system is worse.

It’s not about whether it’s easy or difficult, but which is more secure. If 49% of the nodes are compromised, the system can still make forward progress and stay consistent. That’s the entire point. If 99% of the nodes are compromised, there can still be ways to recover. If you have a UNL this is less of an issue but if anyone can join the network then you have to be prepared to mitigate the possibility of viruses, sybil attacks, collusion, etc. So you can’t have nodes voting on stuff. (Well, you can have voting with PoW or PoS etc. but then the nodes with a lot of power can totally undo the recent history.)


#8

Two things happen. First, nodes don’t relay conflicting transactions. Second, they will wind up dropping their reserve to zero. So even if they did manage to get all 20,000,000 transactions relayed (which they wouldn’t) they’d still wind up paying around 20 XRP, which is about the rate. So the attack would do nothing serious at all.

Yes, that’s why we use a consensus protocol that ensures all state is public and agreed on. Nobody would even relay a transaction that’s not likely to succeed. And nobody relays a transaction that they know conflicts. So even if you luck out and get wide distribution of more than one transaction, you still pay at least one fee. And since no node will relay more than one of any set of conflicting transactions, you can’t actually get any amplification.

Transactions aren’t aggregated in any meaningful sense. When you see a transaction, you look at the state of the network and relay it if, and only if, you think it’s likely to succeed. Each node will only relay one of any set of conflicting transactions and one such transaction will eventually succeed. These properties make the XRP Ledger DDoS resistant. Your scheme doesn’t have any of these properties.

Since anyone who wants to can start up as many nodes as they want, you can’t base security on nodes at all.

I agree, you can’t have nodes voting. And trying to get a particular percentage of nodes doesn’t make much sense. An attacker can trivially be 99.9% of nodes if they want to be. You need something that advantages legitimate users. But you also need to make DDos protection a priority if you want a stable network, and relaying conflicting transactions to execute none of them and requiring every node to permanently keep track of all conflicting transactions it has approved/rejected seems like a really bad design to me. Again, maybe you have the problem that this approach solves, but it’s definitely not a censorship resistant design.

It also seems like your algorithm requires an agreement on what nodes there are. How is that accomplished?


#9

Just about this last part: Intercoin Technology: The Ledger


#10

3 posts were merged into an existing topic: Intercoin Technology: The Ledger