MaddieM4
commented
10 years ago I believe that covers everything. If we need anything else, we can add it later. Closing.
Closed MaddieM4 closed 10 years ago
MaddieM4
commented
10 years ago I believe that covers everything. If we need anything else, we can add it later. Closing.
I think I've finally figured out a way to dispense with quorums once and for all, which I had always considered a necessary evil. It involves moving the Acceptor logic completely out of the document contents, and into the external timestamping service. This means that the set of permissions for Acceptor List modification is set in stone for all documents, which provides consistency, speed, and simplicity, at the expense of some flexibility that I do not expect anyone to use.
Problems with current design
As long as the acceptor list is stored in the content of the document, there is a circular relationship between timestamp logic, quorum logic, and event logic. That's a lot of stuff to keep an account of, for every iteration of the loop that slowly resolves the current tip - definitely pushing the limits of my own mental stack, and I designed the damn thing.
Not only does this screw with correctness, portability, and optimization. It also creates a social problem, by introducing a separation between the group of Acceptors, and the group of Learners, the latter being "nodes that record to the external timestamping service, and provide reliable peer relationships".
Phasing
One of the biggest benefits of this change is that it allows us resolve tip as a series of basically distinct phases:
The separation of concerns is a big deal, and may help improve the lower-level APIs we can provide.
Acceptor List Operations
We need to be able to encode more operations into the external timestamping service (concretely, the Bitcoin blockchain). This increases complexity here, but the ordering logic can be shared between many timestamper implementations.
Establish an Acceptor
To establish a new Acceptor, you need a majority consensus among current Acceptors within a single block. This means num_votes > floor(num_members/2), only counting valid votes and members per the existing set of members at that time. Initially, the set of members is empty, of course, so any potential member may elect herself. In the event of multiple self-elections, all are valid, but self-elections are of course only valid when the set of current members is nil (it can become nil again later, for example).
These rights take effect during the following block, of course. So the set of Acceptors established in block N have authority in block N+1.
Remove an Acceptor
An Acceptor may be stripped of her role, if a majority consensus agrees on it. This follows the same consensus rules as establishing an Acceptor.
Promote an event
An event may be promoted once per block, by each valid Acceptor during that block. Multiple votes by the same identity are treated as one vote, so voting multiple times is just a waste of cryptocurrency, not a disqualification.
Events in the timeline are ordered according to three qualities, with each sort applying at a different level of scope. You can imagine a nested loop implementation of this:
And of course, when this single list is iterated later, we can safely ignore ancestors of the current tip as we go, as well as any events that are forkwise incompatible with it. Thus, using only heritage and timestamp data, we can get the current tip hash.
Implementation in Bitcoin Blockchain
TBD, but that's not an immediate concern anyways. It will be awhile before we rely on blockchain data for real, and we will get there through incremental steps, only the last few of which require any details on how the transactions will be encoded.
Consequences of this ticket
We'll want to close some tickets that are now irrelevant/wrongtrack. We want to add some tickets for the way that things will work, for example, content-ignorant tip discovery. Once the issue tracker is up to date with this design, this ticket may be closed without any source code changes.