Intercoin Technology: The Ledger

[Greg]

People have to trust that their money is safe within a community. Requiring each community to provide its own local infrastructure will be both inconvenient and introduce friction. It will also drastically reduce security: if a community has only 10 computers running validation, it’s much easier to undermine. You can, for example, blow up all 10 computers and make it forget who owns what. This is a problem for Proof of Work and Proof of Stake as well.

That is why each community starts out using validators on the larger network. These validators collectively maintain a ledger about all coins in all communities. However, the ledger is horizontally partitioned down to the coin! Each token is a non-divisible entity that is watched by several computers on the ledger.

There are some positive theoretical results about decentralizing the ledger for a crypto-currency.

An academic paper from 2009 shows that even if the network maintaining the ledger is partitioned into different subsets (referred to as sharding), the probability of a double-spend quickly approaches zero as the number of nodes in each subset grows, becoming extremely small when each subset has 30 nodes. There is no need to have the whole network watch every coin or process every transaction.

A system called Kademlia described in 2002 by Petar Maymounkov (one of our advisors) has been used in Distributed Hash Table systems from Bittorrent to SAFE Network.

Our approach is similar to the one SAFE Network uses in that it uses Kademlia to choose the groups of validators to watch over each token, and each transaction. The latter group is unpredictable in advance, but the former group is predictable given the token ID, so we also implement “churn”, effectively reassigning validators to different groups from time to time in a process they cannot control. This, along with other measures like strong cryptography, prevents a whole host of attacks. The main attacks to be mindful of in that framework are eclipse and sybil attacks.

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

Next Topics:
Intercoin Technology: Consensus
Intercoin Technology: Mitigation
Intercoin Technology: Recovery

[joelkatz]

That really doesn’t answer it. It just says we select the nodes from a group of nodes. But then how do we all know the identifies of every node in that group of nodes? If you’re going to assume that we all agree on the set of nodes we’re choosing from, a set that must change over time, you need some outer consensus protocol to ensure universal agreement on that group of nodes, otherwise we won’t agree on the assignment of subgroups. It’s easy to think you’ve solved a problem when you’ve actually just pushed it elsewhere.

[Greg]

This is the Kademlia DHT protocol. Have you read through https://www.maidsafe.net/docs/Safe%20Network%20Primer.pdf ?

Our approach is the same as that project. They have been at this since 2006. See also https://safenetforum.org/t/kademlia-nodeid/9832/2

[Greg]

Kademlia can be used for building anonymous and uncensorable networks like SAFEnet because the IP addresses are not propagated past one hop. So the IPs of the network can’t be enumerated and blocked. Also Kademlia means no one has to store a global view of the network.

And then each token is watched by the nodes close in XOR space. Or even better, have A and B contribute nonces for a random input to the transaction. They commit to a value by sending its hash, then they post the values in the next transaction. This random input makes the group unpredictable in advance so you can’t collude with it.

However you can still theoretically find the nodes storing old history about T, so that’s where “churn” comes in. Nodes watching T sometimes change, while T’s id remains the same.

Another totally different implementation can directly cache the XOR space ids or the IP addresses of Watchers / Validators for the token, in the token history itself. And after every new transaction on that token a new Watcher joins (whose ID matches some predicate involving the random nonces) and replicates that hash stream, and an old Watcher stops watching. This avoids Kademlia entirely, but has the disadvantage that nodes storing old history stay the same so in theory Mallory may find them and collude with them to fork the history, or they may just go offline. Then you have to recover from that, and for that reason Kademlia may be better.

[Intercoin]

Guys, we migrated your posts here because they’re talking about the Intercoin Ledger and routing / selecting nodes, so it would be more relevant to this topic.