Constant's avatar
Constant 2 days ago
ah, ok that explains a lot haha. If you want to understand this stuff, you will have to learn how merkle-trees and merkle-proofs work (this is how OTS and OTS-proofs work). And you have to understand Nakamoto Consensus (this is the key innovation behind Bitcoin) works. You don't really need to know a lot about Bitcoin, just the Blockchain/linked-list and Proof of work/difficulty adjustment part. Il do a brief explanation and then you can look up terms and things if stuff is unclear. A Bitcoin block, has two parts; the blockheader and the transactions. The blockheader is the meta-data of the block, and it contains: - The time at which supposedly the block was created (this is provided by the miner that created the block so is not really trust worthy, but the network has rules/margins based on averages within a miner is able to screw around with that timestamp); - The difficulty target (how much PoW the hash of this particular blockheader has to have in order to be valid) - A nonce, a variable data-field that allows miners to keep trying different hashes of the header until they find a valid one that meets the difficulty target. - A merkle-root of all the transaction data. - The previous blockhash (which is the hash of the previous blockheader) - A version number You can link all these blockheaders (header-chain), because it is a linked list (each next header references the previous header). The difficulty is adjusted over time, based on how fast the chain was created; too fast = higher difficulty, too slow = lower difficulty, trying to target 10 minutes that it takes to create a block. In order to validate this headerchain there are three parts, but for the sake of OTS, you arguably can get away with only looking at two of them. First is the linked-list and hashes; does indeed each next header reference the previous header. So lets say we have 2 headers, we look at the second header and it references the hash of the first header. So we have to hash the first header and see if that hash is indeed the same as stated in the second header. Ok great, that the linked list. The second thing you have to account for is the difficulty (or the short way to describe this is the amount of leading 0's in the hash). First this means that each header has a target, which means that the hash of that header has to meet that target (i.e. has atleast the amount of leading 0's required), this is a simple check. The second thing you have to account for is the fact that the difficulty is adjusted every 2016 blocks/headers. 2016 blocks x 10 minutes per block = 2 weeks. Using some formula that looks at the timestamps of that 2016 block period, it determines what the next difficulty should be. This means that in order to validate the header chain, you need to do it at least in these chunks of 2016 headers (otherwise you cant verify if the difficulty adjustment happened correctly). The third part you don't really have to check, is if the transactions inside the block are valid. ''Technically'' you should, but on the other hand it is kind of silly to verify something that apparently this giant network of miners that burns Gigawats of electricity already has decided was correct based on the fact it is included in the blockchain they are working on. If you use Bitcoin for its currency, you need to look at this stuff because you need to replay its history in order to figure out its current state; but we are not interested in any of that. We are only interested in 1 particular transaction inside some block, and only care that it is there. This is the transaction that the OTS-calendar did that includes the merkle-root for all the stuff it is timestamping. Because the calendar packs all the things it is proofing inside a merkle-tree, and puts its root in the blockchain; and because the block itself puts all its transactions in a merkle-tree and puts that root inside the header; you are able to create a merkle-proof that goes all the way from the hash of your document (or in our case, the hash of eventID+signature), to the transaction-merkle-root inside the blockheader. So, to verify an OTS timestamp/proof, we need the proof, and the associated blockheader (the proof tells us which blockheight we should be looking at). And to verify that blockheader, we should have verified the header chain (which is done in these 2016 block chunks). Each blockheader is 80bytes....the entire header chain up untill this point is not even 80mb. You can just connect to the p2p bitcoin network to fetch that data (all bitcoin nodes have it). You can take some shortcuts to speed downloading this stuff up (the biggest shortcut being just providing all the header data directly) because verifying that header chain is really fast anyway. So if you have this tiny database of blockheaders verified and ready, you already know what the time of each blockheight is(because that data is in the header) and verfying a proof is extremely quick and easy and you have everything you need to know locally. Ive included a nice illustration of the proof in the app to make things clear: image As you can see; the thing we are proving is at the bottom, the blockheaderhash with all those leading 0's is at the top, and in between is the OTS-proof that connects our thing to the blockheader. So here is the point: Don't trust, verify Hope this helps, if you have any questions let me know

Replies (3)

Constant's avatar
Constant 2 days ago
Oh, this OTS database i made has a nice animated version :P (so does the android app, but you have to scroll down to see it and by that time the animation is already done)
Thanks. I'll need a bit to digest, but it looks like this will be super helpful. The ability of clients to quickly and efficiently filter out events that don't have a valid OTS timestamp (where "valid" means that they don't have an OTS timestamp that falls within a specified recency window after their created_at) should be a fundamental part of the Nostr protocol. It's about as important as the ability to filter out events that don't have a valid signature in the first place. I'll likely have questions after I've had a chance to think about your explanation ...