How to do document timestamping with the block chain?

[cjp]

I don't understand what you mean with a "master document". For me, the only "master document" is the chain of Bitcoin block headers, and these are verified in a quite unique, decentralized way, which I'm sure you're all familiar with.

Each block header contains (IIRC) a timestamp, which is verified by future miners, and a hash value, which forms the root of a Merkle tree. For normal Bitcoin usage, the "leaves" of the Merkle tree are Bitcoin transactions, but for my timestamping concept I will create a special type of transaction which contains a hash value, and this way, I am able to extend the Merkle tree with my own Merkle sub-tree. The "leaves" of my own sub-tree are the documents that need to be timestamped.

The block headers, together with the part of the Merkle tree that leads to a leave, are a timestamp proof for that leave. The block headers are distributed among all Bitcoin users. For Bitcoin transactions, the Merkle tree and the transactions themselves are also distributed among all Bitcoin users, since they are part of the block data, but they may be "pruned" in the future as soon as the transaction outputs are spent. The "Merkle sub-tree" of my timestamping concept is not distributed among all Bitcoin users, and the same is true for the timestamped documents themselves. The person who has an interest in timestamping a document needs to take care of keeping a copy of the document and a timestamp certificate that contains the missing information. Or he can choose to publish both of them in any way he likes.

In my timestamping concept, you can provide timestamping proof if you have the following:

• The original document
• The Bitcoin block headers (get them from any Bitcoin user and verify them)
• The timestamp certificate, generated by my service (for contents see earlier post)

The certificate will be machine-readable, and you can use an open source and publicly reviewed script to see whether the certificate is valid. The script needs the above items as input.

[1714037411]

1714037411

[1714037411]

1714037411

[1714037411]

1714037411

[mila]

well you mention somewhere that you'll be timestamping twice a day. that means either you'll timestamp two documents or two collective documents with a list of timestamped documents. if the later is the case, the list of timestamped docs is the master document. did my clarification help?

[cjp]

well you mention somewhere that you'll be timestamping twice a day. that means either you'll timestamp two documents or two collective documents with a list of timestamped documents. if the later is the case, the list of timestamped docs is the master document. did my clarification help?

I'll timestamp twice per day, and each timestamp can apply to multiple documents. So, in that sense, my concept follows your second option. However, there is no "list of timestamped documents": instead of a list, I use a Merkle tree structure. I don't know whether this makes a big difference for you. The similarity with your second option is that, yes, you need that Merkle tree structure to do the verification. That's why it(*) will be included in the certificate document. The difference is that you don't need the entire Merkle tree to verify a single document: you only need the branch that leads to the document you're interested in.

Are you familiar with Merkle trees?

(*) actually, only the relevant branch of the Merkle tree will be included in the certificate. Each timestamped document will have its own certificate, even if there are multiple documents to be timestamped at the same moment.

[phelix]

have you considered namecoin for your purposes? it actually is a generic name/value pair accounting system.

you can register a fixed name of ~255 bytes and a value of 1023 bytes. not sure if the value is locked in the chain forever but I think at least the name is.

[cjp]

have you considered namecoin for your purposes? it actually is a generic name/value pair accounting system.

you can register a fixed name of ~255 bytes and a value of 1023 bytes. not sure if the value is locked in the chain forever but I think at least the name is.

Yes, but I don't believe in the concept of using separate block chains for separate purposes:

• I think it is essential to have a monetary reward for block chain miners, to keep the difficulty high and
  to keep the block chain hard-to-counterfeit. So, it is not only "Bitcoin needs the block chain", but also "the block chain needs Bitcoin".
• Because of the inherent networking effect of payment methods, I think it is very important to keep everybody committed to the same crypto-currency. Either everybody should switch to Namecoin, or we should all stick to Bitcoin. Since Bitcoin is currently more popular, I'll keep using that.
• The method I use poses only a minimal overhead to the Bitcoin network. Instead of saying "every purpose should have its own block chain", I propose "every purpose should have its own Merkle tree, rooted in the Bitcoin Merkle tree". Only if the Bitcoin currency rules prove to be broken, there is a justification for creating a new block chain with a new currency.

[phelix]

have you considered namecoin for your purposes? it actually is a generic name/value pair accounting system.

you can register a fixed name of ~255 bytes and a value of 1023 bytes. not sure if the value is locked in the chain forever but I think at least the name is.

Yes, but I don't believe in the concept of using separate block chains for separate purposes:

• I think it is essential to have a monetary reward for block chain miners, to keep the difficulty high and
  to keep the block chain hard-to-counterfeit. So, it is not only "Bitcoin needs the block chain", but also "the block chain needs Bitcoin".
• Because of the inherent networking effect of payment methods, I think it is very important to keep everybody committed to the same crypto-currency. Either everybody should switch to Namecoin, or we should all stick to Bitcoin. Since Bitcoin is currently more popular, I'll keep using that.
• The method I use poses only a minimal overhead to the Bitcoin network. Instead of saying "every purpose should have its own block chain", I propose "every purpose should have its own Merkle tree, rooted in the Bitcoin Merkle tree". Only if the Bitcoin currency rules prove to be broken, there is a justification for creating a new block chain with a new currency.

I sure agree to your first point but imho merged mining resolves the second. gold miners also make use of secondary ores.

[cjp]

I sure agree to your first point but imho merged mining resolves the second. gold miners also make use of secondary ores.

I want to understand how that "merged mining" works. Can you please explain it, or provide a good link?

To my understanding, mining for block chain X works as follows:

Code:

nonce = 0
while True:
    template = X.getLatestBlockTemplate() #transactions and/or parent block can be updated
    block = makeBlockWithNonce(template, nonce)
    hash = calculateHeaderHash(block)
    if(X.meetsDifficulty(hash))
        X.publishBlock(block)
    nonce++

I have no idea how mining for two block chains X and Y can be merged.
BTW, I created a certificate:
http://timestamp.ultimatestunts.nl/certificateExample.pdf

Are there any errors in this? I am particularly interested in:

• English / legalese errors
• Errors in my description of Bitcoin
• Hacker challenge: Errors in my verification code (can you create false positives / false negatives?)

[phelix]

I sure agree to your first point but imho merged mining resolves the second. gold miners also make use of secondary ores.

I want to understand how that "merged mining" works. Can you please explain it, or provide a good link?

To my understanding, mining for block chain X works as follows:

Code:

nonce = 0
while True:
    template = X.getLatestBlockTemplate() #transactions and/or parent block can be updated
    block = makeBlockWithNonce(template, nonce)
    hash = calculateHeaderHash(block)
    if(X.meetsDifficulty(hash))
        X.publishBlock(block)
    nonce++

I have no idea how mining for two block chains X and Y can be merged.
[...]

the namecoin block hash is included in the bitcoin block. namecoin accepts a bitcoin block hash at namecoin difficulty level.

http://bitcoin.stackexchange.com/questions/273/how-does-merged-mining-work
http://dot-bit.org/Merged_Mining

[cjp]

http://bitcoin.stackexchange.com/questions/273/how-does-merged-mining-work

Thanks, that is a good explanation.

An interesting thing to see is that merged mining (as described on that page) also works by inserting a hash value into a Bitcoin block. Someone suggests this is done with a 0 BTC transaction (to an address that encodes the hash??). Since this is done by the miners themselves, I can imagine they have more freedom to use non-standard transactions for this.

The comments on that page make me a bit worried about the future of Bitcoin, since competing crypto-currencies that do merged mining with Bitcoin can get the same block chain security, while offering much lower transaction fees than Bitcoin. Effectively, they don't pay for what they're using, which will destroy the system for all of us. I hope somebody knows a solution.

In the mean time, my Bitcoin-based implementation is already 90% finished, so from this point, it seems simpler to just continue using Bitcoin directly, instead of indirectly through Namecoin.

[DeathAndTaxes]

http://bitcoin.stackexchange.com/questions/273/how-does-merged-mining-work

Thanks, that is a good explanation.

An interesting thing to see is that merged mining (as described on that page) also works by inserting a hash value into a Bitcoin block. Someone suggests this is done with a 0 BTC transaction (to an address that encodes the hash??). Since this is done by the miners themselves, I can imagine they have more freedom to use non-standard transactions for this.

The comments on that page make me a bit worried about the future of Bitcoin, since competing crypto-currencies that do merged mining with Bitcoin can get the same block chain security, while offering much lower transaction fees than Bitcoin. Effectively, they don't pay for what they're using, which will destroy the system for all of us. I hope somebody knows a solution.

In the mean time, my Bitcoin-based implementation is already 90% finished, so from this point, it seems simpler to just continue using Bitcoin directly, instead of indirectly through Namecoin.

Merged mining is done by putting the child chain in the coinbase field.

Merged chains can't get something for nothing.  If there fees are low they why will miners mine them?  Ultimately each miner will decide which chains to mine.  No current chain with the exception of namecoin has any significant merge mining.

[cjp]

Merged mining is done by putting the child chain in the coinbase field.

Ah, thanks. I can't find much documentation about the coinbase field, but the Wiki mentions "The data in "coinbase" can be anything; it isn't used.", which explains enough for me.

Merged chains can't get something for nothing.  If there fees are low they why will miners mine them?  Ultimately each miner will decide which chains to mine.  No current chain with the exception of namecoin has any significant merge mining.

I've been thinking about this, and I haven't figured out yet how this is going to work. In fact, I don't think I understand the mining economics of a future Bitcoin-system that is dominated by transaction fees instead of coin generation. What would prevent a "race to the bottom", where miners ask lower and lower fees, to out-compete competitors?

The few miners who happen to have the most efficient computers and the lowest electricity prices will be able to out-compete all others. Once others leave the game, the difficulty decreases, but the ratio between the remaining miners doesn't change. The few successful ones can continue lowering the transaction fee, so that the game remains unprofitable for the other ones. In the end, there is a real danger of a 51% attack.

I think that, currently, the only thing that keeps difficulty high is the high value of the generated bitcoins per block. With the generated coin value dropping to zero, I think difficulty will also drop to zero, and the system will fail.

Luckily, it will take several decades before this happens, and most in-between lowerings of the amount of generated bitcoins will probably be over-compensated by the increase in value due to increased usage.

[kjj]

Merged mining is done by putting the child chain in the coinbase field.

Ah, thanks. I can't find much documentation about the coinbase field, but the Wiki mentions "The data in "coinbase" can be anything; it isn't used.", which explains enough for me.

Merged chains can't get something for nothing.  If there fees are low they why will miners mine them?  Ultimately each miner will decide which chains to mine.  No current chain with the exception of namecoin has any significant merge mining.

I've been thinking about this, and I haven't figured out yet how this is going to work. In fact, I don't think I understand the mining economics of a future Bitcoin-system that is dominated by transaction fees instead of coin generation. What would prevent a "race to the bottom", where miners ask lower and lower fees, to out-compete competitors?

The few miners who happen to have the most efficient computers and the lowest electricity prices will be able to out-compete all others. Once others leave the game, the difficulty decreases, but the ratio between the remaining miners doesn't change. The few successful ones can continue lowering the transaction fee, so that the game remains unprofitable for the other ones. In the end, there is a real danger of a 51% attack.

I think that, currently, the only thing that keeps difficulty high is the high value of the generated bitcoins per block. With the generated coin value dropping to zero, I think difficulty will also drop to zero, and the system will fail.

Luckily, it will take several decades before this happens, and most in-between lowerings of the amount of generated bitcoins will probably be over-compensated by the increase in value due to increased usage.

That's an awful lot of assumptions between now and the system failing in a few decades.

[phelix]

Merged mining is done by putting the child chain in the coinbase field.

Ah, thanks. I can't find much documentation about the coinbase field, but the Wiki mentions "The data in "coinbase" can be anything; it isn't used.", which explains enough for me.

Merged chains can't get something for nothing.  If there fees are low they why will miners mine them?  Ultimately each miner will decide which chains to mine.  No current chain with the exception of namecoin has any significant merge mining.

I've been thinking about this, and I haven't figured out yet how this is going to work. In fact, I don't think I understand the mining economics of a future Bitcoin-system that is dominated by transaction fees instead of coin generation. What would prevent a "race to the bottom", where miners ask lower and lower fees, to out-compete competitors?

The few miners who happen to have the most efficient computers and the lowest electricity prices will be able to out-compete all others. Once others leave the game, the difficulty decreases, but the ratio between the remaining miners doesn't change. The few successful ones can continue lowering the transaction fee, so that the game remains unprofitable for the other ones. In the end, there is a real danger of a 51% attack.

I think that, currently, the only thing that keeps difficulty high is the high value of the generated bitcoins per block. With the generated coin value dropping to zero, I think difficulty will also drop to zero, and the system will fail.

Luckily, it will take several decades before this happens, and most in-between lowerings of the amount of generated bitcoins will probably be over-compensated by the increase in value due to increased usage.

That's an awful lot of assumptions between now and the system failing in a few decades.

but sharp assumptions.

the effect you are talking about is discussed as "tragedy of the commons" for example here: https://bitcointalk.org/index.php?topic=67900 

and here: http://bitcoin.stackexchange.com/questions/3111/will-bitcoin-suffer-from-a-mining-tragedy-of-the-commons-when-mining-fees-drop-t/3129#3129

In the mean time, my Bitcoin-based implementation is already 90% finished, so from this point, it seems simpler to just continue using Bitcoin directly, instead of indirectly through Namecoin.

oh noes

but with namecoin there is not much to be done about this anyway - it works just like that.

name_new / name_firstupdate stamp/myhashh789dhh7