Update 09 September, 2021


This week we’re going into a little more detail about unlinkability of DBC, and what the implications and trade-offs are for user experience and network efficiencies.

General Progress

An Elder is a special sort of node with voting rights and managerial duties, whereas an Adult stores data and delivers it on request, but to the client they look exactly the same. @chris.connelly has been working through some bugs which see a client trying to bootstrap to an Adult, which then ignores it creating a nasty loop.

Chris has also been working on improving the sn_launch tool (as some of you spotted!) and debugging the qp2p upgrade.

@JimCollinson has been looking at the issue of credentials, using multisig to be able to add more authentication options to the basic password/mnemonic, including hardware keys, extra mnemonics or seed phrases, etc. For example, the user might stipulate that any three of five credentials must be presented to unlock a Safe. Multisig also opens the door to using n trusted third parties to recover an account, if desired. Safe Network users will inevitably lose credentials, and multisig offers a route to secure account recovery allowing the user to control the balance of risk as they see fit.

@bochaco is looking at how the Client validates that the section it’s talking to is up to date via AE.

@Qi_Ma is looking at what happens when adults become full. There is currently some aberrant behaviour in how the next alternative non-full adult is chosen to store a chunk by the elders and how the Elders know where the chunk is, given that it is no longer the XOR-closest to the chunk name.

Meanwhile, @chriso has been working on modernising the API to take account of the new messaging changes, a task which is almost finished now.

@oetyng’s work with the integration of the boosted self-encryption together with chunk handling refactor has been merged in. The scope duality (public/private) has been moved from chunk level to blob level - simplifying code and node duties greatly. Also proper handling of the defacto secret key, that the self-encryption outputs together with the encrypted chunks, has been added. With this in place, work on chunk batching can now continue.

We’ve also merged our work in progress feature branch to master (or rather, moved the HEAD of main to this if you want to get into git details…). This means that the branch was more stable than main. We’re seeing more CI pass and much cleaner code in general. There’s a lot in this branch that’s been added, and we’re still testing and debugging various flows. But with AE throughout and simpler code flow in the node, this is all getting easier as we go. So while there’s no testnet just yet for folk to play with, we’re going in the right direction.

More on DBCs

Continuing our series on DBCs, this week we dig into the property of unlinkability. We discuss why it is important and review different ways that privacy focused cryptocurrencies attempt to achieve it.

Hopefully this overview can serve to provide readers with more context and background for technologies we have been exploring such as zero knowledge proofs, blind signatures, commitments, fixed denominations, and so on.

Unlinkability

So why is it important for a monetary token to be unlinkable? In short, because that is the technical means to achieve the more general and highly desirable monetary property of fungibility. Fungibility means that one token is interchangeable with another.

Think of two unmarked gold bars of equal weight. One is as good as the other. They are indistinguishable. However, if these bars are marked with serial numbers and some central entity keeps a list of all gold exchanges tracked by the serial number, then we can have a situation where one bar becomes worth less than another in the minds of potential recipients because it was associated with some “bad” activity in the past. Or another might be even more valuable because it passed through the hands of a famous person. With such a system, participants may begin to lose trust in the gold bars. They may have to check against a centralized “good/bad list” for every transaction to prevent receiving a “bad bar”, and the overall system becomes less efficient. Due to tracking, we have lost fungibility. For more on this, see the above linked article.

There are also many privacy-loss implications when receiving or making a payment with a token that has a long history attached to it. The Safe Network aspires to enable private, safe transactions for all network participants.

How can we determine if a coin is linkable or unlinkable? It’s actually pretty easy, we just look at the inputs and outputs of a pair of transactions.

Note: In the case of DBCs, we often use the words transaction and reissue interchangeably

Here is a simplified example of two reissues using our current DBC system. We can say that Bob paid 50 to Alice (1st reissue) and then Alice paid the same 50 to Jim (2nd reissue). So each reissue has just one input DBC and one output DBC. Each DBC has an associated amount, public key of the owner pubkey, and a mint signature mintsig. In this example pubkey, mintsig and hash are shortened to 3 digits for brevity. In reality they are very large unique numbers.

reissue 1 (r1):
→ input = a {amount=50, pubkey = 567, mintsig=233},  hash(a) = 223
→ output = b {amount = 50, pubkey = 725, mintsig=112}, hash(b) = 787

reissue 2 (r2):
→ input = b {amount = 50, pubkey = 725, mintsig=112 }, hash(b) = 787
→ output = c {amount = 50, pubkey = 212, mintsig=455}, hash(c) = 993

Note: a, b, and c are labels for this example. They do not appear in a reissue. Amounts are now hidden by commitments, but not relevant to this analysis.

We can easily see that input b for r2 matches output b for r1. We can link them together by any of: pubkey == 725 or mintsig == 112, or hash == 787.

This establishes that reissues r1 and r2 are linked together because they share a common DBC. Over a series of reissues this creates a chain that can be followed.

This is what is meant by linkability.

Also if the amount is a very unique value (or value commitment), it could be used to link transactions.

An important point to notice is that even if we remove the pubkey and mintsig fields and just use a random id field (to prevent double spending), the DBCs are still identifiable by their hash value. In other words, if the same data is used as an output to one reissue and as an input to another, then the reissues are linkable. This is generalizable to any cryptocurrency, substituting the word transaction for reissue.

You may ask: what if we use multiple inputs and outputs and varying amounts to split and merge tokens? Well, such techniques can make it harder to be certain of the trail of an individual token. That is the basis of CoinJoin, CoinShuffle, and similar mixing algorithms. They make more possible links to follow/evaluate. But they do not actually break any links… which are preserved indefinitely for anyone to analyze at leisure using statistical analysis, data from third parties (eg exchanges), and so on. Such techniques are generally considered “weak-sauce” by cryptographers.

You may also ask: Why have any unique identifier in the DBC at all? The answer is that an identifier is necessary to prevent double-spending. The mint must be able to record a “coin” as spent, in order to catch any future attempt to spend it again.

Once we understand linkability, we can begin thinking about ways to prevent it.

A system with the property of unlinkability would not have any such links. The big question is, how to achieve that property?

Blind Signatures

The oldest known technique was invented by David Chaum and is known as Blind Signatures. It has the advantage that it is the simplest scheme to implement, and for now at least, the most efficient, which makes it very well suited for mint operations.

Let’s review the basic concept of a blind signature. Chaum’s paper uses the example of an election conducted remotely. Here we present a condensed version, though Chaum’s is worth reading as well.

A blind signature is like putting a slip of paper with a message (eg a vote) inside an envelope which is lined with carbon. Mary sends the envelope with the slip inside and a return address to election official Charles. Charles signs the envelope (which also signs the slip inside) and sends it back. At a later date, Mary removes the vote slip and sends it back to Charles in a new envelope, but without a return address. Charles opens the envelope, removes the slip, verifies it has a valid signature by Charles, and counts the vote – without knowing who cast this particular vote or when it was signed (amongst the set of signed envelopes).

The key point is that there is no link between what is on any of the slips and what was written on any of the envelopes. So the vote cast by each of the voters is unknown to election official Charles. (excluding writing forensics, etc, etc which are not relevant for cryptographic discussions).

Ok, so lets perform our two reissues again, this time using blind signatures. Now it is the DBC Mint that blindly signs the envelope(s). For this example, we assume that all DBCs are equal in value.

reissue 1 (r1):
→ input = a.slip {pubkey = 567, mintsig=233},  hash(a.slip) = 223
→ output = b.envelope {blind(b.slip)}, hash(b.envelope) = 565

reissue 2 (r2):
→ input = b.slip {pubkey = 445, mintsig=112 }, hash(b.slip) = 787
→ output = c.envelope {blind(c.slip)}, hash(c.envelope) = 993

In words:

  • Bob presents input A (slip) to mint (with valid mint sig over A) and obtains mint’s signature over output B (envelope) with mint sig indicating that B is worth the same as A (slip).
  • Mint also marks A (slip) as spent.
  • Bob removes B (slip) from B (envelope) and gives it to Alice, who presents B (slip) to the mint and obtains mint’s sig over C (envelope) worth the same as B (slip).
  • Mint also marks B (slip) as spent.

Now, the interesting thing here is that B (envelope) has a different hash from B (slip) inside it. 565 != 787

Therefore, the hashes do not match between tx1 and tx2 and neither do any fields. Nothing connects these two transactions together so far as the mint can see. We have unlinkability!

Zero Knowledge Circuits

A more modern approach to unlinkable transactions is through the use of Zero-Knowledge (ZK) proof circuits ala ZCash.

With ZK proofs, we are attempting to convince the Mint of something without revealing some sensitive information. ZK circuit proof systems like PLONK have emerged over the last few years as general systems for engineering ZK proofs.

For example, say we implement a ZK circuit that simulates sha3_256. This circuit would allow us to prove to a third party that we know the data that hashes to some hash without revealing the data itself. We can even prove properties about this data!

Say for example that the data we are hashing is actually an entire reissue transaction.

let reissue = Reissue {
   inputs: { Dbc {amount: 9, owner: pk1,..}, Dbc {amount: 1, owner: pk2,..},
   outputs: { Dbc {amount: 10, owner: pk3,..}
   ownership_proofs: {pk1_sig, pk2_sig}
};

I could run this reissue through sha3_256 to produce a hash: tx_hash = sha3_256(reissue).
To convince the mint that this is a hash of a valid transaction, we can generate a ZK proof using our sha3_256 circuit.

A ZK circuit has private and public inputs, in this example, the reissue information will be private inputs and the tx_hash will be a public input.

private: [9, pk1, 1, pk2, 10, pk3, pk1_sig, pk2_sig]
public:  [tx_hash]

We can write down constraints on these private/public inputs, these constraints are encoded into a ZK Circuit that can then be run to produce proofs that these constraints are satisfied

/// Reissue Constraints
private[0] + private[2] = private[4]        // 9 + 1 = 10
private[1].verify(private[0..6], public[6]) // pk1 signed the transaction
private[3].verify(private[0..6], public[7]) // pk2 signed the transaction
public[0] = sha3_256(private)               // reissue data hashes to tx_hash

Note: we are referring to inputs by their index, circuits have a pre-determined size, this size limits the number of input / output DBC’s we can reissue within a single reissue transaction.

Now once we encode these constraints as a ZK circuit, we can insert the reissue details into the private input slots and the tx_hash into the public input slot of the circuit. We then turn the crank to produce a proof that all constraints are satisfied.

Importantly, this proof does not leak any information about the private inputs, we can send this proof along with the tx_hash to a Mint and it would be convinced that this tx_hash is a hash of a valid transaction. The mint could then sign tx_hash to certify the reissue.

This is very cool, but the research in this area is still young and the tooling around these ZK circuit systems still quite immature. Proofs tend to be very slow to produce and verify, especially for complicated circuits like sha3_256.

If you’d like to go deeper this series is quite good.

Ring Signatures

Ring Signatures, as used in Monero and other cryptocurrencies, are a method to obscure the transaction history by hiding in a group.

In a ring signature, Alice signs a transaction using (1) Alice’s private key, (2) Alice’s public key, and (3) other people’s public keys. Anyone can verify Alice’s signature using the set of public keys, but they’re (usually) unable to determine who the true signer was because there are multiple equivalent public keys.

As such, ring signatures are a form of automatic mixing. Links still exist, but there are so many of them, that it may be too difficult to analyze. In Monero at present, there are 11 possible signers: the real one plus 10 others. So this is like hiding in a crowd of 11 people… better than standing alone, but not super comforting if a bloodhound is sniffing around.

Amount Hiding

Amount Hiding, also known as Confidential Transactions also helps improve privacy, but it does not affect [un]linkability.

Amount Hiding is compatible with zk circuits and ring signatures but not with a blind signature approach, which typically requires the use of fixed denominations.

We discussed Amount Hiding via Pedersen commitments in a previous update.

Fixed Denominations

Fixed denominations are another form of privacy protection, similar in purpose to amount hiding. Only a certain limited number of amounts are allowed by the system. To represent any other amount, one must make change using the known amounts.

Forcing all transactions to use these fixed amounts means that all inputs and outputs to a transaction appear regular. While the total amount of a given transaction is visible, one cannot track a given input or output effectively by its amount because it merges into an ocean of other tokens worth the same amount. As such, all units of a given denomination are fungible with eachother.

It is therefore important to keep the total number of denominations small. One could for example define every integer value to its own denomination. While this would work technically, it is bad for privacy, as people will often use very unique amounts. Instead of merging into an ocean, a single drop wanders by itself.

64 Likes

First again. I do have a life honestly!

Just a lucky one :relaxed:

28 Likes

Why do they need to look the same?

I see Elder I think of Ents …
ent

I’m hoping at some point that anything that does not necessarily need to be network level become application level - so SafeID and credentials is matter for applications and the evolution of the handling of those? Of course nice if Maidsafe puts out an instance of that but if the network is simply acting on the back of a private key, then it perhaps only acts when that is presented, rather than worrying about the handling of that and the user(s) interaction.

8 Likes

Just for clarity, the Network won’t be storing or handling credentials, as per fundamental number 9.

14 Likes

Interesting to see those fundamentals again… I need to better internalise those.

Fundamental 17 direct client to client… I wonder relative to Fundamental 11 scrubbing IPs that direct contact between clients would be disclosure of IPs without any use of network… perhaps that is just accepted for that client to client use??

8 Likes

Nice write up!

General progress is going amazing as well. If that adult-elder-client loop existed in the previous Testnet along with so many other looping bugs and OMM issues then it’s amazing they lasted as long as they did. Sounds like this huge amount of updates, optimizations and bug fixes will be a massive improvement in stability and performance.

We didn’t get to hear much in denominations and whether they are performant or not.

From my uneducated view, it seems like forcing one time keys and denominations fixes the link ability issue. Blind sigs have to be used too though so Mints or elders can’t link though, correct?

If denominations are an attractive option and it’s required the number of denominations allows for obscurity then I wonder what the right amount of denominations is for unlink ability and usability.

15 Likes

Great update team as usual. I can see how this DBC and tokenomics work in general is super tricky.

As there were many alternative approaches listed, I’m guessing that these are all still in the discussion/debate hopper and could take some time yet to figure out and implement the most pragmatic (and hopefully best) options.

Thanks for the detailed overview - it demonstrates the level of research and thought everyone is putting into the problem and IMO, really sets the Safe Network apart from most other projects out there.

Of course we have the benefit of hindsight as many of the other successful projects out there have put these ideas to the fire - so much can be gleaned from that going forward.

Cheers!

11 Likes

Apologies to ask a dumb question and notwithstanding all the interesting updates on DBCs, can someone in layman’s terms explain what needs to happen to get to the next testnet.

Is it a case of refactoring? Integration of AE? Is there a fundamental issue with how everything works together that needs to be addressed?

As someone who has been following the project for the last 4 years, have been feeling a bit lost recently.

As always the updates are meticulously produced and written in great detail, and I hate to be the dumb dumb asking for the simplification of something obviously so complex…but in fact that is exactly what I asking.

Appreciate if anyone can help me out

Thanks!

10 Likes

No, it’s more like AE is quite a simplification to things, so with doing that we’ve more easily been able to see where some things were overwriting state w/o verification eg. And can generally see more easily where there is a loop or so, because there’s only AE messages going now, as opposed to a few different types doing different things.

And then with all that, we’re going through and making sure what we expect to be happening is happening (and for the most part it is).

There’s certainly nothing fundamentally off atm. It’s more simplifying and stabilising just now.

26 Likes

Just wanted to voice my opinion (not that it matters) on what I think of a couple of the other named approaches.

I think coin joins, ring sigs, are a waste of time for what little they are worth and the zk stuff though interesting, to my understanding is too computationally heavy and slow for what we would be aiming to achieve for an internet token with global use.

I’ll be reading over this many times I’m sure and hope to pick up little bits I might have missed but im already looking forward to the next write up. :slight_smile:

7 Likes

Thanks for the great work again!

What’s the situation with this key issue?

7 Likes

Thanks so much to the entire Maidsafe team for all of your hard work! The explanations above were excellent and it will be much easier to get good community support. :racehorse:

:thankyou:

11 Likes

Now this makes me excited!

11 Likes

Thx for the update Maidsafe devs.

Really like the readup on DBCs, very insightful.

Just like immutability is a time saver, unlinkability will be.

Keep hacking super ants

12 Likes

Why I can’t see Farming part on github.com?

Hard to say, been following since 2014, so would also like to know.

As the team does not give time estimates we’re probably looking at : “Its ready when it’s done kind of answer” .

1 Like

Probably still not worked on, check the roadmap, not sure the team already worked on that part.

For anyone having a hard time reading the updates for whatever reasons: I find that pasting the whole update to a chat room with the closest-like friends and acquaintances (like a channel or a group) helps me understand everything better. Even if nobody in there is actually reading it with you lol. I like how this update basically proves that gold is worthless. OK well, not worthless, at all (I feel like quite a number of people here and in general likely have a strong potential bond to the concept of gold)—but what Maidsafe is doing with money/data/Internet I keep saying is the most ideal the world can get with their money. And it helps that it’s integrated with everything else. I guess ZK and Monero are already pretty good, though they’re lacking self-authentication (I think?) and everything else that the Safe Network will bring (on top of anything else I’m missing, since I don’t know much about those cryptos whatsoever, though I’d probably be all over them if Safe Net’s ideal never got known). Great work! As always.

9 Likes

Of course with gold, one can always just melt it down and create a new bar. Then stamp any number you wish into it, or none. That’s why gold is innately fungible, and thus why a centralized tracking technique as decribed in the update would work imperfectly at best in the real world.

With digital currencies, a tracking identifier of some sort is normally a system requirement to prevent double spending and create scarcity. Because unlike gold, a digital token can be duplicated by anyone at near zero cost. So the hard part is getting gold’s innate fungibility property back. It’s hard enough that the first generation of cryptocurrencies didn’t even try.

23 Likes