Let me bring back an idea that we briefly discussed in our private conversations with Chuck and Matt, but then kind of left behind. So, why do we need a chain of blocks, and not a DAG? I mean a "one-ended" DAG, of course, so that there are sometimes parallel branches, but they eventually merge:


That's an easy question: it is because if the "parallel" branches are allowed, they may contain "conflicting" information, leading e.g. to double-spends. OK, for now.

But let me ask another question: why are we obliged to have only one blockchain, which is used for virtually everything?

Suppose that we need a place for storing some sort of information, such that no conflict between "parallel" chains may arise. For example, the accounts may "declare" or "register" something (e.g., "I've just forged a block", "I've just made an instant transaction"), wanting to later have a proof they did it (i.e., this can be particularly useful for timestamping). Then there is no problem if different "declarations" are made on different branches: this just proves that the account has declared two different things (those declarations are signed, of course). So, why not use a DAG? It can be probably built faster (the network latency is not so much a problem), and, if a restricted set of nodes is allowed to build this DAG, it can be really fast, IMHO.

So, what do you think? In my opinion, if this is viable, it can be quite useful for TF.

EDIT1: It seems I didn't express myself in a sufficiently clear way. Of course, for money transactions, there should be one and only one chain. But if we want to store some other information for which there is no possibility of conflicts similar to double-spending, we may well use another chain for that, or even a DAG.

EDIT2: I think there is a very important advantage of DAGs over chains: it is much easier to attack a chain than to attack a DAG!    As you know, there are many attack scenarios that go like this: a bad guy is doing something to create an alternative subchain, and then feeds this subchain to good guys. If the alternative subchain is "better", then the Dark Side wins. However, this kind of attack would be useless if a DAG is used instead of chain: the nodes would just store the two subchains, and that's all.
« Last Edit: June 27, 2014, 10:25:41 pm by mthcl » Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 01:25:52 pm
#1
Nice, that you brought that up again. The git idea has been floating around in my mind for a long time now. :)
Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 07:41:12 pm
#2
We r not obliged to have only 1 chain. BCNext planned to use parallel chains coz they can be forged without a lot of resources. Later he found a flaw in his design of PCs. If u invent a good scheme - great.
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 08:10:23 pm
#3
Quote from: Come-from-Beyond on June 27, 2014, 07:41:12 pm
We r not obliged to have only 1 chain. BCNext planned to use parallel chains coz they can be forged without a lot of resources. Later he found a flaw in his design of PCs. If u invent a good scheme - great.
My point (and not only my) is that a "chain" does not need necessarily be really a chain, it can be something as shown on the above picture.

Can you give a link to BCNext's desing of parallel chains?
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 08:28:06 pm
#4
The very idea of a blockchain is that you have one global clock. That clock is not accurate as possible, but fair. It is a global indestructible timestamp mechanism creating a partial order of events, see [1].

Splitting up the chain for Nxt would destroy the network. A split of the network is almost the definition of destruction - which chain is real and which is fake? chains have to be unique, like names. Otherwise: how would one node decide that the chain he is seeing is not fabricated by a malicious actor? So the answer is: no, blockchains need to be unique. I think these properties of Bitcoin and its descendants have not been discussed yet. I would be very cautious fiddling with some of the properties, as they might open up major unknown attack vectors, having to do with how traffic flows through the global network.

[1] http://en.wikipedia.org/wiki/Lamport_timestamps
Ignore   Report to moderator
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 08:45:04 pm
#5
Quote from: mthcl on June 27, 2014, 08:10:23 pm
Quote from: Come-from-Beyond on June 27, 2014, 07:41:12 pm
We r not obliged to have only 1 chain. BCNext planned to use parallel chains coz they can be forged without a lot of resources. Later he found a flaw in his design of PCs. If u invent a good scheme - great.
My point (and not only my) is that a "chain" does not need necessarily be really a chain, it can be something as shown on the above picture.

Can you give a link to BCNext's desing of parallel chains?

Sorry, I can't. It's buried somewhere on the internet.
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 08:53:14 pm
#6
Quote from: benjyz on June 27, 2014, 08:28:06 pm
The very idea of a blockchain is that you have one global clock. That clock is not accurate as possible, but fair. It is a global indestructible timestamp mechanism creating a partial order of events, see [1].

Splitting up the chain for Nxt would destroy the network. A split of the network is almost the definition of destruction - which chain is real and which is fake? chains have to be unique, like names. Otherwise: how would one node decide that the chain he is seeing is not fabricated by a malicious actor? So the answer is: no, blockchains need to be unique. I think these properties of Bitcoin and its descendants have not been discussed yet. I would be very cautious fiddling with some of the properties, as they might open up major unknown attack vectors, having to do with how traffic flows through the global network.

[1] http://en.wikipedia.org/wiki/Lamport_timestamps
1. A chain creates a total (linear) ordering of events, not only partial.

2. OK, if we allow the Nxt chain to split, this won't be good. Clearly, allowing two "similar" chains to coexist would create problems as well: effectively, it would be more difficult for nodes to decide which one is real and which one is not. But I don't see why having two quite a different "chains" (of which one is a DAG) would create any problems. Please, if you have more concrete arguments, do present them.
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
Daedelus
Hero Member
*****
Offline Offline
Posts: 3282

View Profile  Personal Message (Offline)
Karma: +230/-12
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 08:55:00 pm
#7
Quote from: Come-from-Beyond on June 27, 2014, 08:45:04 pm
Quote from: mthcl on June 27, 2014, 08:10:23 pm
Quote from: Come-from-Beyond on June 27, 2014, 07:41:12 pm
We r not obliged to have only 1 chain. BCNext planned to use parallel chains coz they can be forged without a lot of resources. Later he found a flaw in his design of PCs. If u invent a good scheme - great.
My point (and not only my) is that a "chain" does not need necessarily be really a chain, it can be something as shown on the above picture.

Can you give a link to BCNext's desing of parallel chains?

Sorry, I can't. It's buried somewhere on the internet.

You can't or you just don't have the time to find it?

I could look if it is somewhere in the megathread, for example
Ignore   Report to moderator
NXT: NXT-4CS7-S4N5-PTH5-A8R2Q
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 08:56:21 pm
#8
Quote from: mthcl on June 27, 2014, 08:10:23 pm
My point (and not only my) is that a "chain" does not need necessarily be really a chain, it can be something as shown on the above picture.

I think you're making an error here, which I've seen before when I read about the GHOST proposal. Chains exist as replicated data across nodes. There is no "chain" which exists in a Platonic realm. There are computers in a network which assume that the chain exists, because they communicate with each other in a coordinated fashion. TF is similar to GHOST in that there is the idea that nodes can operate for themselves and somehow it is assumed that other nodes know about this. This is not how it works. The Byzantine Generals Problem and Lamport's partial order are related (Lamport invented the BGP). One can also think about this is in terms of a global vs local view problem.

Quote
The proof-of-work chain is how all the synchronisation, distributed database and global view problems you've asked about are solved.

http://satoshi.nakamotoinstitute.org/emails/cryptography/11/
Ignore   Report to moderator
gs02xzz
Hero Member
*****
Offline Offline
Posts: 1101
View Profile  Personal Message (Offline)
Karma: +55/-12
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 09:00:27 pm
#9
These guys are working on custom block-chains - https://bitcointalk.org/index.php?topic=654463
Ignore   Report to moderator
Nxt Mission is to commercialize the crypto technology and build new commerce and society.
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 09:06:07 pm
#10
Quote from: benjyz on June 27, 2014, 08:56:21 pm
Chains exist as replicated data across nodes. There is no "chain" which exists in a Platonic realm.
This I understand. Of course, the object on the picture is stored in the database; also, topologically it's almost equivalent to a chain. You may think about it as a usual blockchain, but the orphaned nodes don't fall to limbo, they are still stored in the database.

Now, could you please explain why maintaining two different chains with different characteristics would destroy Nxt?
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 09:31:13 pm
#11
Quote from: mthcl on June 27, 2014, 09:06:07 pm
Now, could you please explain why maintaining two different chains with different characteristics would destroy Nxt?

All nodes have to process all transactions, or at least have to be able to (if I request information full nodes have to give me the full history).

If I operate a Nxt node and the Nxt node I operate communicates with 300 peers - how should I know which chains are valid? Say there are two valid chains A and B. If only some nodes know about chain A and not about B, then which nodes are they? It would be a split in the network which can't be sorted. Every node would have to keep track of what other nodes know (a list of "A-nodes" and "B-nodes"). On the other hand if all nodes know about chain A and B, it makes no difference. The chains are really the same: there would be a class BlockchainA and BlockchainB, and the code would be identical.  It might very well make sense to have one chain for different transaction types (moneyChain, aliasChain, ...), but I think this is not what you mean.
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 09:33:26 pm
#12
So, are there any advantages of DAGs over chains, apart from being able to generate more blocks per unit of time?

I think there is a very important one: it is much easier to attack a chain than to attack a DAG!    As you know, there are many attack scenarios that go like this: a bad guy is doing something to create an alternative subchain, and then feeds this subchain to good guys. If the alternative subchain is "better", then the Dark Side wins. However, this kind of attack would be useless if a DAG is used instead of chain: the nodes would just store the two subchains, and that's all.
« Last Edit: June 27, 2014, 09:38:20 pm by mthcl » Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 09:37:23 pm
#13
Quote from: benjyz on June 27, 2014, 09:31:13 pm
It might very well make sense to have one chain for different transaction types (moneyChain, aliasChain, ...), but I think this is not what you mean.
In fact, I mean more-or-less this.  For money transactions, of course, there should be one and only one chain. But if we want to store some other information for which there is no possibility of conflicts similar to double-spending, we may well use another chain for that, or even a DAG.  Just modified the 1st post to explain this.
« Last Edit: June 27, 2014, 09:52:51 pm by mthcl » Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 09:47:55 pm
#14
Here are some links on Parallel Chains, provided by Jimmy2011:

Jan 17th, 2014
https://bitcointalk.org/index.php?topic=345619.msg4558565#msg4558565
https://bitcointalk.org/index.php?topic=345619.msg4559456#msg4559456

Feb 3rd, 2014
https://bitcointalk.org/index.php?topic=345619.msg4916018#msg4916018

Mar 8th, 2014
https://bitcointalk.org/index.php?topic=345619.msg5584903#msg5584903

Apr 16th, 2014
https://nxtforum.org/parallel-blockchains/what-the-status-of-parallel-blockchain-for-nxt/msg9450/#msg9450

Apr 18th, 2014
https://nxtforum.org/parallel-blockchains/what-the-status-of-parallel-blockchain-for-nxt/msg9977/#msg9977
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 10:26:29 pm
#15
Quote from: Daedelus on June 27, 2014, 08:55:00 pm
I could look if it is somewhere in the megathread, for example

I have to dig thru a huge chat log to find the description.

It would be great if u found it. I didn't get the idea of PC completely so I didn't memorize it. There were such words as "master" and "slave".

Edit: mthcl already found it :) - https://bitcointalk.org/index.php?topic=345619.msg5584903#msg5584903
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 10:41:32 pm
#16
Quote from: Come-from-Beyond on June 27, 2014, 10:26:29 pm
Edit: mthcl already found it :) - https://bitcointalk.org/index.php?topic=345619.msg5584903#msg5584903
It was Jimmy2011.
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:13:02 pm
#17
The most important issue, I had in mind, when comparing Nxt to the git DAG was that we would need to think of the "merge commit" aka the block that joins several chains together.

Think of commits as blocks and vice versa. Each block/commit represents a certain state but is an emergent property. Blocks/commits only contain the delta to the previous state.

Like in git, there will be merge conflicts aka double spends. But resolving that conflict, we will result in a state that carries the set of changes from both branches (like in git).

That was basically the idea.
Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:20:45 pm
#18
Quote from: ChuckOne on June 27, 2014, 11:13:02 pm
The most important issue, I had in mind, when comparing Nxt to the git DAG was that we would need to think of the "merge commit" aka the block that joins several chains together.

Think of commits as blocks and vice versa. Each block/commit represents a certain state but is an emergent property. Blocks/commits only contain the delta to the previous state.

Like in git, there will be merge conflicts aka double spends. But resolving that conflict, we will result in a state that carries the set of changes from both branches (like in git).

That was basically the idea.

The 1st obvious attack - someone forges a chain that is not compatible with the other chains. Every block. How r u going to counteract this attack?
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:23:56 pm
#19
Quote from: ChuckOne on June 27, 2014, 11:13:02 pm
The most important issue, I had in mind, when comparing Nxt to the git DAG was that we would need to think of the "merge commit" aka the block that joins several chains together.

Think of commits as blocks and vice versa. Each block/commit represents a certain state but is an emergent property. Blocks/commits only contain the delta to the previous state.

Like in git, there will be merge conflicts aka double spends. But resolving that conflict, we will result in a state that carries the set of changes from both branches (like in git).

That was basically the idea.
What are "merge conflicts"?


Re: DAG, a generalized blockchain
June 27, 2014, 11:28:03 pm
#20
Quote from: Come-from-Beyond on June 27, 2014, 11:20:45 pm
The 1st obvious attack - someone forges a chain that is not compatible with the other chains. Every block. How r u going to counteract this attack?
The idea was to use the DAG for the storage of something, for which the "compatibility" problems don't arise. For example, an account publishes "I love Mary", so that that later he's able to prove he was in love with Mary at a certain time. If on a parallel chain the same account published "I love Alice", well, this means he was in love with Mary and Alice at the same time, there is no contradiction  :)
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:30:36 pm
#21
Quote from: Come-from-Beyond on June 27, 2014, 11:20:45 pm
Quote from: ChuckOne on June 27, 2014, 11:13:02 pm
The most important issue, I had in mind, when comparing Nxt to the git DAG was that we would need to think of the "merge commit" aka the block that joins several chains together.

Think of commits as blocks and vice versa. Each block/commit represents a certain state but is an emergent property. Blocks/commits only contain the delta to the previous state.

Like in git, there will be merge conflicts aka double spends. But resolving that conflict, we will result in a state that carries the set of changes from both branches (like in git).

That was basically the idea.

The 1st obvious attack - someone forges a chain that is not compatible with the other chains. Every block. How r u going to counteract this attack?


What do you do in case of a merge conflict?
Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:32:50 pm
#22
Quote from: mthcl on June 27, 2014, 11:23:56 pm
Quote from: ChuckOne on June 27, 2014, 11:13:02 pm
The most important issue, I had in mind, when comparing Nxt to the git DAG was that we would need to think of the "merge commit" aka the block that joins several chains together.

Think of commits as blocks and vice versa. Each block/commit represents a certain state but is an emergent property. Blocks/commits only contain the delta to the previous state.

Like in git, there will be merge conflicts aka double spends. But resolving that conflict, we will result in a state that carries the set of changes from both branches (like in git).

That was basically the idea.
What are "merge conflicts"?

Basically, if you edited a file in the same line as I did, we both committed our changes and now, we need to merge. Somehow, we would need to resolve that conflict because you wanted to have "a=4" and I wanted "a=5" in that line. Who knows what the resolution would be here?
Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:36:18 pm
#23
Quote from: ChuckOne on June 27, 2014, 11:32:50 pm
Quote from: mthcl on June 27, 2014, 11:23:56 pm
Quote from: ChuckOne on June 27, 2014, 11:13:02 pm
The most important issue, I had in mind, when comparing Nxt to the git DAG was that we would need to think of the "merge commit" aka the block that joins several chains together.

Think of commits as blocks and vice versa. Each block/commit represents a certain state but is an emergent property. Blocks/commits only contain the delta to the previous state.

Like in git, there will be merge conflicts aka double spends. But resolving that conflict, we will result in a state that carries the set of changes from both branches (like in git).

That was basically the idea.
What are "merge conflicts"?

Basically, if you edited a file in the same line as I did, we both committed our changes and now, we need to merge. Somehow, we would need to resolve that conflict because you wanted to have "a=4" and I wanted "a=5" in that line. Who knows what the resolution would be here?
The idea is that "a" could be 4 or 5 at the same time. See my previous message  :)
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:40:35 pm
#24
Quote from: mthcl on June 27, 2014, 11:36:18 pm
The idea is that "a" could be 4 or 5 at the same time. See my previous message  :)

Then, we misunderstood each other the other day. ;) I meant, I wanted something like a merge block to a reasonable extend.

But anyhow, utilizing a DAG for both seems possible as we are talking about emergent states. :)
Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 27, 2014, 11:57:22 pm
#25
This is basically the same as the side-chain idea. The question is: why should such chains be supported in the first place? Nxt has a marketcap of 60M$ and when I register an alias or buy Nxt I'm building on the economic interest. If alternative chains exist, why should they be supported? The market value provides a reliable indicator. Without the value of the money there is no interest in the data that is stored. And if there is a separate maintainer it is a different currency. A currency issuer does not need permission of Bitcoin or Nxt to start his blockchain (if he can demonstrate the system is viable).
Ignore   Report to moderator
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 12:04:50 am
#26
Currently, the point is not why (although, we already had many proposals of what could be achieved by this) but how. :)
Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 12:18:32 am
#27
Quote from: ChuckOne on June 27, 2014, 11:30:36 pm
What do you do in case of a merge conflict?

I do manual work.
Ignore   Report to moderator
ChuckOne
NRS Project Manager
Hero Member
*****
Offline Offline
Posts: 3438
[Tip Me]

☕ NXT-4BTE-8Y4K-CDS2-6TB82
View Profile  Personal Message (Offline)
Karma: +291/-17
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 12:41:42 am
#28
Quote from: Come-from-Beyond on June 28, 2014, 12:18:32 am
Quote from: ChuckOne on June 27, 2014, 11:30:36 pm
What do you do in case of a merge conflict?

I do manual work.

Right. Manual work seems impossible for currencies at least for now. Maybe, somebody has a better idea.

So, reducing the manual work to a minimum can be a key here to save economic value i.e. the loss of transactions.
« Last Edit: June 28, 2014, 12:51:37 am by ChuckOne » Ignore   Report to moderator
THE CHARITY HUB: NXT-8N9W-TN4F-YA2S-H5B7R
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 03:36:56 pm
#29
Quote from: mthcl on June 27, 2014, 08:53:14 pm
1. A chain creates a total (linear) ordering of events, not only partial.

The blocks are totally ordered, and the chain ensures that the history is complete. The events in the blocks are not totally ordered.

A blockchain is by definition a partial order (within a total order). Say you have these two transactions (case A):

tx_1: Alice sends Nxt to Bob at 00:00:00 UTC
tx_2: Charlie sends Nxt to David 00:00:11 UTC

Which one gets processed first? If Alice has a high latency connection, then tx_2 might come first. A total order would mean that all tx get processed according to their timestamps. Which is impossible because the timestamps of nodes are not known to be accurate, and the latencies between nodes are not known and not reliable etc. What matters is the relationship of latency to the blocktime (perhaps this can be modeled, but assumptions are crucial).

This is closely to connected to the double spend. Double spend has to do with tracking events in a distributed system. It's a special case of case A (case double spend):

Alice has a balance of 10 Nxt.

tx_1: Alice sends 10 Nxt to Bob at 00:00:00 UTC
tx_2: Alice sends 10 Nxt to David 00:00:11 UTC

Turns out that the solution to the double spend problem is introducing a kind of logical time. It does not matter what the latency of the 4 participants are as long as they are orders of magnitude lower than the blocktime.  This principle one can call logical broadcast. It has been almost never discussed in Bitcoin development, because of the focus on malicious actors and BGP. I think this has to do with biases in the field of cryptography which does not deal with time and distributed systems. Most of the knowledge of Bitcoin development seems to be connected to the PoW mechanism, and the complicated interactions and calculations. There were many ideas of pruning chains, loading only partial history etc. I think full nodes (in lack of a better term) should always be able to access the full history.

Lamport described the principles of partial orders first in 1978 [1] . The importance of latencies in networks is what highfrequency traders are very aware of. It's not intuitive - the recent book by Michael Lewis has described this quite clearly [2] in connection to the US stock market. Large exchanges have to have a total order (discussion beyond scope of this post).

[1] http://web.stanford.edu/class/cs240/readings/lamport.pdf
[2] http://www.theguardian.com/business/2014/apr/16/michael-lewis-flash-boys-wall-street-insane

Edit: clarify partial order.
« Last Edit: June 28, 2014, 04:09:54 pm by benjyz » Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 09:13:03 pm
#30
Within each block you can easily order the events by e.g. their ID's, so it's not difficult at all to introduce a total ordering of them as well, if needed. But my point was that on DAGs, although there is no "natural" total order, still this may not be a problem for some applications (like timestamping).
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:10:14 pm
#31
that's what I demonstrated above to be false - total order is impossible in a P2P network, because information travels at maximum of speed of light. These are nodes communicating, and there is no central actor doing ordering. the node forging the block does not know for sure when the tx was sent to him. every node can lie about his local time. the only thing a node knows is what his time is and at what time messages arrive. because if a node could lie about his time, he could re-write history and make himself rich (like the guy in back to the future).
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:20:48 pm
#32
I didn't claim you can introduce the total ordering of the events which agrees with their issue times (where did you read it?!). I only claimed that you can introduce a total ordering on which you have the consensus.
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:21:06 pm
#33
.
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:24:00 pm
#34
Quote from: mthcl on June 28, 2014, 10:21:06 pm
.

Completely agree.
Ignore   Report to moderator
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:33:19 pm
#35
Quote from: mthcl on June 28, 2014, 10:20:48 pm
I didn't claim you can introduce the total ordering of the events which agrees with their issue times (where did you read it?!). I only claimed that you can introduce a total ordering on which you have the consensus.

The current time is ca. 15:25:00 UTC. If I issue a transaction at 15:30:00 UTC, nobody will know whether that was true. So even if the node that forges the next block would know that timestamp he will not know. So the consensus consists in agreeing about the blocks. We need block times to agree on something. And because we (the P2P nodes) don't know the various latencies we use one discrete time interval - the block. If all nodes would be a graph, say of some well formed shape and all the latencies perfectly known, the problem would be very different. We could trust the local timestamps. Perhaps such a system could exist, but the Internet is not build for it.
Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:38:06 pm
#36
Quote from: benjyz on June 28, 2014, 10:33:19 pm
Quote from: mthcl on June 28, 2014, 10:20:48 pm
I didn't claim you can introduce the total ordering of the events which agrees with their issue times (where did you read it?!). I only claimed that you can introduce a total ordering on which you have the consensus.

The current time is ca. 15:25:00 UTC. If I issue a transaction at 15:30:00 UTC, nobody will know whether that was true. So even if the node that forges the next block would know that timestamp he will not know. So the consensus consists in agreeing about the blocks. We need block times to agree on something. And because we (the P2P nodes) don't know the various latencies we use one discrete time interval - the block. If all nodes would be a graph, say of some well formed shape and all the latencies perfectly known, the problem would be very different. We could trust the local timestamps. Perhaps such a system could exist, but the Internet is not build for it.
Yes, sure. Did I argue with that?..

Can you formulate precisely, what was my claim with which you don't agree?
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:45:58 pm
#37
I think we have different definitions of total order. I mean by total order that all transactions can be ordered by the time they were issued (a node stamps his tx before sending it with the local time). This is impossible for reasons given above. The blockchain order is total, but not perfectly accurate. It's accurate enough. The reason why I'm arguing this point is that for certain class of transactions a total order is needed: highly scalable exchange markets. Because the price one counterparty gets depends on the total order of transactions (arbitrage argument basically). It's the reason why I think Nxt will/would run into some issue with the AE if orders will be processed through the blockchain at scale (I haven't studied the plans in detail, just referring to the current codebase). In such an exchange blockchain the best matching price will occur at the end of a block, so it does not make sense to issue orders at the beginning of the block. This creates various "problems", at least at scale.

Edit: so for more generalized versions of blockchains which can have a total order something else is needed. I haven't seen any proposals for it  yet, which I believe can work.
« Last Edit: June 28, 2014, 10:54:27 pm by benjyz » Ignore   Report to moderator
mthcl
Hero Member
*****
Online Online
Posts: 556
[Tip Me]
View Profile  Email  Personal Message (Online)
Karma: +88/-8
applaud / spank

Re: DAG, a generalized blockchain
June 28, 2014, 10:55:05 pm
#38
Yes, I meant the "abstract" total order, in the sense of this definition. Then there is nothing to argue: of course, you cannot recover the "real" order of events w.r.t. time, but you can achieve a consensus on another total ordering, which approximates the "ideal" one reasonably well (or maybe not).

Now, let me take take a break from the forum: Brazil is gonna play!   :)
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
Come-from-Beyond
Hero Member
*****
Offline Offline
Posts: 4014

View Profile  Email  Personal Message (Offline)
Karma: +792/-670
applaud / spank

Re: DAG, a generalized blockchain
July 03, 2014, 11:25:11 pm
#39
May be worth reading:

GHOST - https://eprint.iacr.org/2013/881.pdf
DECOR - http://bitslog.wordpress.com/2014/05/02/decor/


Re: DAG, a generalized blockchain
July 04, 2014, 10:16:54 pm
#40
Quote from: Come-from-Beyond on July 03, 2014, 11:25:11 pm
May be worth reading:

GHOST - https://eprint.iacr.org/2013/881.pdf
DECOR - http://bitslog.wordpress.com/2014/05/02/decor/
Seems that these articles are more about PoW. And PoW/PoS = randomness/pseudorandomness. I would be surprised if these methods turn out to be directly applicable to PoS.
Ignore   Report to moderator
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7
mczarnek
Hero Member
*****
Offline Offline
Posts: 898
View Profile  Nxt Place - Craigslist for Nxt  Personal Message (Offline)
Karma: +68/-4
applaud / spank

Re: DAG, a generalized blockchain
July 13, 2014, 05:23:54 am
#41
Seems to me like if sidechains are possible then parallel chains should be too.. They are largely the same idea, right?  You can move your Nxt off of the main chain, process them separately, then move them back onto the main chain later to switch between chains.  Every country has it's own chain or something along those lines.  1 Nxt on any chain = 1 Nxt on any other chain.

I would say it'd be worth looking into how Bitcoin plans to implement sidechains.
Ignore   Report to moderator
NXT Organization: Tech
Donations greatly appreciated: NXT-DWVJ-G89C-RHNL-6QW6Q
benjyz
Hero Member
*****
Offline Offline
Posts: 508
View Profile  Personal Message (Offline)
Karma: +70/-4
applaud / spank

Re: DAG, a generalized blockchain
July 24, 2014, 03:48:56 pm
#42
Quote from: mthcl on July 04, 2014, 10:16:54 pm
Quote from: Come-from-Beyond on July 03, 2014, 11:25:11 pm
May be worth reading:

GHOST - https://eprint.iacr.org/2013/881.pdf
DECOR - http://bitslog.wordpress.com/2014/05/02/decor/
Seems that these articles are more about PoW. And PoW/PoS = randomness/pseudorandomness. I would be surprised if these methods turn out to be directly applicable to PoS.

GHOST is a bad idea, which really highlights what I've said above. All nodes have to have the same information at the same time. Imagine that there is a graph of say 10 nodes, and 5 of them are in close proximity and 5 are further away. The 5 nodes in close proximity can collude at the expense of the other 5 outside nodes. This is exactly the problem in financial markets, and what is known as highfrequency trading (a better term is predatory trading).