Decentralized Timestamp

[mczarnek]

So I was discussing this with a friend was wondering if you guys had any input, how would you go about creating a decentralized system that agrees on the current time?

Preferably not Proof of Work.

Thanks.

[1715124889]

1715124889

[1715124889]

1715124889

[1715124889]

1715124889

[1715124889]

1715124889

[telepatheic]

It is virtually impossible due to Sybil attacks. Bitcoin is as close to a decentralised timestamp system as you will get.

[gmaxwell]

Using hash-chain mediated common view time transfer, as I wrote in 2011: https://people.xiph.org/~greg/decentralized-time.txt

Preferably not Proof of Work.

Your question stops being interesting when you start removing the only known solution for strong decentralized consensus— even in the proof of work model an effort to do consensus time probably fails for incentive reasons, but no one knows how to do decenteralized consensus absent the expenditure of work.

[jonald_fyookball]

So I was discussing this with a friend was wondering if you guys had any input, how would you go about creating a decentralized system that agrees on the current time?

Preferably not Proof of Work.

Thanks.

Why can't nodes simply use their own server time, adjust to GMT, and reject messages from other
nodes that are not matching (within a margin of error)?

[bluemeanie1]

It is virtually impossible due to Sybil attacks. Bitcoin is as close to a decentralised timestamp system as you will get.

nope, can be done.  I have a working model.  see:  http://www.stanford.edu/class/cs240/readings/lamport.pdf

if you review that paper maybe we can discuss how to do this, otherwise I'll save it for later.

later friends!  -bm

[bluemeanie1]

Using hash-chain mediated common view time transfer, as I wrote in 2011: https://people.xiph.org/~greg/decentralized-time.txt

Preferably not Proof of Work.

Your question stops being interesting when you start removing the only known solution for strong decentralized consensus— even in the proof of work model an effort to do consensus time probably fails for incentive reasons, but no one knows how to do decenteralized consensus absent the expenditure of work.

Participating nodes would sample RF noise on some agreed band(s) being
emitted by the Sun and continually record it, with their sampling clock
being driven by their stable local oscillator. Nodes would then publish
timestamped recent fragments of this signal. Peers would then perform a
cross-correlation between the fragments and their own timestamped recordings
in order to find the offset. Only nodes which can concurrently observe the
sun can actively participate in the agreement, but because the local
oscillators are relatively stable this should not prevent good long term
stability. (Effectively your clock would be corrected in the daytime and
free run at night).

Greg, I usually like your ideas... but wow.

-bm

[bluemeanie1]

oh and decentralized timestamping CAN BE DONE and it CAN BE ADDED TO NXT.     

-bm

[jonald_fyookball]

re: specialized hardware that uses the sun.

interesting... but this sounds way harder to implement
than running ASICs farms....possibly so much so that
it would be hard to gain traction at least presently...right?

[bluemeanie1]

re: specialized hardware that uses the sun.

interesting... but this sounds way harder to implement
than running ASICs farms....possibly so much so that
it would be hard to gain traction at least presently...right?

you could use some sort of atomic clock to determine objective time and this solves the problem if inaccuracy, but does not solve the problem of FRAUD.

-bm

[jonald_fyookball]

from an adoption point of view, atomic clocks arent that much better.
anyone can run a bitcoin node from an ordinary computer
and i think might be important.

[bluemeanie1]

a commercially available atomic clock chip:  http://www.microsemi.com/products/timing-synchronization-systems/embedded-timing-solutions/components/sa-45s-chip-scale-atomic-clock

so we don't need the sun.  The problem is very specific to our application because in finance there is an incentive to defraud, it's not just a matter of coordination(a problem that has been solved in many different ways) but also a problem of certification.  It's a bit difficult but my concept descends from Vector Clocks.  http://en.wikipedia.org/wiki/Vector_clock

it's not top secret or anything just would rather discuss with an audience who has some familiarity with these problems.

-bm

[bluemeanie1]

In NXT for instance they are going to add a BOND system.  Bonds are the basic elementary component of credit systems and they have fairly simple qualities:  A PRINCIPAL, INTEREST, and MATURITY.

If the borrower fails to repay PRINCIPAL + INTEREST at time specified at MATURITY, then you have a DEFAULT.  So naturally how do we measure this event in a block chain?  In some cases loans might have a maturity of a few minutes, how can we make sure that the payment is made before the maturity time?  Can we express maturity in block depth?  Currently our discussions seem to indicate that there are no functional issues with having a loan maturity expressed in terms of block depth, the only drawback is that the borrower or lender might find these terms difficult to manage, but generally they work.

-bm

[jonald_fyookball]

a commercially available atomic clock chip:  http://www.microsemi.com/products/timing-synchronization-systems/embedded-timing-solutions/components/sa-45s-chip-scale-atomic-clock

so we don't need the sun.  The problem is very specific to our application because in finance there is an incentive to defraud, it's not just a matter of coordination(a problem that has been solved in many different ways) but also a problem of certification.  It's a bit difficult but my concept descends from Vector Clocks.  http://en.wikipedia.org/wiki/Vector_clock

it's not top secret or anything just would rather discuss with an audience who has some familiarity with these problems.

-bm

Sure.... You meanies only take no for an answer   

[mczarnek]

It is virtually impossible due to Sybil attacks. Bitcoin is as close to a decentralised timestamp system as you will get.

nope, can be done.  I have a working model.  see:  http://www.stanford.edu/class/cs240/readings/lamport.pdf

if you review that paper maybe we can discuss how to do this, otherwise I'll save it for later.

later friends!  -bm

Very nice!  Will have to further review this paper later.

oh and decentralized timestamping CAN BE DONE and it CAN BE ADDED TO NXT.     

-bm

Read my mind

In fact I think it was one of your posts that lead mthcl to start talking about it with us.. which lead to this post.

[gmaxwell]

nope, can be done.  I have a working model.  see:  http://www.stanford.edu/class/cs240/readings/lamport.pdf

I'm familiar with that paper and have linked to it on the forum before. Note that Lamport is talking about a distributed system, not a decenteralized one.  As I recall process he describes is not byzantine robust, requires a jamming proof broadcast network, and does not have anonymous membership (the players must be selected in advance, so it cannot meet our definitions of decenteralized— in particular it needs a consensus arbitrary ordering of player identities to break ties).

As far as POS goes, I've not seen anyone tender a solution to the nothing at stake problem, and so I still consider it non-viable for a decentralized consensus. PPC makes it work by requiring POW and using centralized block signatures. NXT was previously making it 'work' by not releasing the complete source to their software, I haven't checked lately.  So far POS schemes all suffer from attacks like former quorums (e.g. people who held coins at some point in the past) can costlessly replace the history by forking off from a point where they did have a quorum after they no longer do, and from things like the optimal income producing mining strategy is to mine all forks (because there is ~0 marginal cost in mining a fork) instead of a single one. Schemes like honesty bonds do not help a node decide between two different networks— the real one and a simulated one, and cannot punish someone if they perform the attack after exiting the network completely.

[bluemeanie1]

gmaxwell,

  could you point us to some sort of an official statement on the 'nothing-at-stake problem'?  No one seems to really be all that clear on what this problem actually is.  From what I was told the person who first proposed it took it down?  So far I've heard many different takes on this particular subject.

  a big problem for NXT is that the stakeholders in the project are very decentralized, so their 'PR' seems a bit off at times.  There's really no one to handle these kinds of questions and an adopter/investor really has no where to get to them resolved.

thanks, -bm

[ArnoldChippy]

Don't the GPS satellites transmit an accurate time signal that could be used for this purpose?


Martin

[gmaxwell]

could you point us to some sort of an official statement on the 'nothing-at-stake problem'?  No one seems to really be all that clear on what this problem actually is.  From what I was told the person who first proposed it took it down?

You've been told some pretty weird stuff then. Nothing has been taken down, and it's not that complicated a point.

In POW to contribute to a consensus you must burn a resource, which means you must make an exclusive choice among all the possible consensus you could contribute to, to the exclusion of all others... and for your effort to not be wasted you should be spending it on the chain you think most likely to survive.  In pure POS schemes, there is no such exclusivity created.  This leads to fun outcomes like old stake holders can exit the system (sell their coins) and then sell their old keys to people go fork off the chain at a point in the past, at no cost to themselves. Someone who is later handed two histories— the real one and the simulated one— cannot distinguish them, they can tell— perhaps— that someone was naughty, but that doesn't help them decide which chain is the good one.  There are a number of other related implications.  A number of different modifications have been proposed, but so far all of them seem to be obfuscation and not actually fix the underlying issue, which seems a bit fundamental.

You can read more about this in Section 5 of https://download.wpsoftware.net/bitcoin/asic-faq.pdf

PPC was attacked utilizing this fact the moment POS mining became possible on it— a savvy miner tried all possible forks finding a sequence of forks which selected their stake as the winning stake as much as possible. PPC prevented this with block signing and discouraged it by hard forking the protocol so that POW blocks were required.

Don't the GPS satellites transmit an accurate time signal that could be used for this purpose?

GPS is unauthenticated. Any local-to-you jammer can spoof it with nothing more complex than a USRP and some software. It's also run by US space command, and the US has been quite up front that they are willing to manipulate or disrupt the signal to achieve military objectives, they're able to perform geo-targeted alterations of the signal too.  It's pretty useful on average, but it's not a secure solution by itself.

[jonald_fyookball]

DeathandTaxes has been schooling us on the same issue in the last 24 hours, I believe.
He makes some good distinctions, as usual:

see here:  
 
https://bitcointalk.org/index.php?topic=27787.80

[Cryddit]

gmaxwell,

  could you point us to some sort of an official statement on the 'nothing-at-stake problem'?  No one seems to really be all that clear on what this problem actually is.  From what I was told the person who first proposed it took it down? 

The central issue with proof-of-stake is that when the chain forks, the stakeholders on the left side of the fork, with very few exceptions, are also stakeholders on the right side of the fork.  Whichever fork wins, they still have their stake.  In fact, they have an incentive to use it to mine both sides of the fork at once.  There's literally no rational reason for them not to; whichever fork eventually fails is eliminated from history, but until they know for sure which one that's going to be, why would they stop mining it?  And as a result of that dysfunction, why does a choice between forks ever get made at all?

Proof-of-work is the expenditure of a finite resource (hashing power) in real time.  You cannot use the same hashing power to support both sides of a fork; you are forced by physics to choose one side or the other, and therefore a decision on the local level perforce actually gets made - leading to a decision on the wider level.

The nothing-at-stake problem can be overcome by GHOST protocol or similar; it must not be possible to support one side of a fork without your repudiation or withdrawal of support being visible to the other.