Segregated Name Values

biolizard89
Posts: 1971
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Segregated Name Values

Post by biolizard89 » Sun Jan 24, 2016 1:54 pm

I had this idea a couple years ago, but it turns out that Sipa's Segregated Witness proposal implements basically the same mechanism, so I think it's a good idea to get this idea out there.

Right now, the value field of a name is up to 520 bytes. That means that for each name, the blockchain has to permanently append up to 520 bytes at least every 36 kiloblocks. This is wasteful, because the values are not in principle needed to verify signatures, nor are they useful for most users once they've been spent or expired.

Segregated Witness moves signatures into a separate Merkle tree, so that clients that don't need them can safely ignore them. I propose doing the same for name values. This proposal is called Segregated Name Values. Instead of pushing the value to the stack prior to a name_update or name_firstupdate, the script instead pushes the hash of the value to the stack. (Double SHA-256 seems to be reasonable, although I'm open to other hashes if a good reason exists.) The full values are instead placed in a separate Merkle tree, which is committed to in the coinbase transaction. Full nodes must verify all name values for at least the past 36 kiloblocks, plus some extra safety period which I leave unspecified for this draft. Full nodes may choose to delete name values which are sufficiently old, although these will still be retrievable from any node which chooses to continue hosting them, and they will still be verifiable against the hashes forever. As an additional optimization, any values which are shorter than a SHA-256 hash should be pushed directly to the stack (same as current behavior), rather than being hashed.

Thoughts on this?
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

domob
Posts: 1100
Joined: Mon Jun 24, 2013 11:27 am
Contact:

Re: Segregated Name Values

Post by domob » Sun Jan 24, 2016 2:13 pm

Sounds like an interesting approach. One question, though: Why would you keep the values in a Merkle tree? Isn't it enough to just push the value's hash and allow for the values to be transmitted fully "out of band" with respect to the blockchain? The hash ensures that the values are still secured as they are now. In fact, such an optimisation could be implemented completely on a higher level - say, by adding a separate P2P network layer for transmitting values (not consensus relevant) and then modifying the d/ spec to require the actual values to be transmitted out-of-band and the actual d/ name value to be the hash. This could then be paired with a softfork to restrict the actual in-chain value length to 32 bytes.

Am I missing something, why is it necessary to include the actual values (not just their hashes) in a root hash? The only reason I can think of for now is that this may be used to "force" full nodes (and miners) to keep the values around for some time.
BTC: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS
Use your Namecoin identity as OpenID: https://nameid.org/

biolizard89
Posts: 1971
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Segregated Name Values

Post by biolizard89 » Sun Jan 24, 2016 2:44 pm

domob wrote:Sounds like an interesting approach. One question, though: Why would you keep the values in a Merkle tree? Isn't it enough to just push the value's hash and allow for the values to be transmitted fully "out of band" with respect to the blockchain? The hash ensures that the values are still secured as they are now. In fact, such an optimisation could be implemented completely on a higher level - say, by adding a separate P2P network layer for transmitting values (not consensus relevant) and then modifying the d/ spec to require the actual values to be transmitted out-of-band and the actual d/ name value to be the hash. This could then be paired with a softfork to restrict the actual in-chain value length to 32 bytes.

Am I missing something, why is it necessary to include the actual values (not just their hashes) in a root hash? The only reason I can think of for now is that this may be used to "force" full nodes (and miners) to keep the values around for some time.
Hmm, I think when I came up with this, I was indeed intending to force full nodes to actually verify that all of the values are correct. But now that you mention it, I'm not certain that a Merkle root commitment is needed in order to force nodes to do this. One consideration is that if that were the goal, the Merkle tree leaf nodes would probably need to be a different hash function of the value than the hash that's signed by the transaction; otherwise the Merkle root would be a function of the hashes in the transaction, which defeats the point. I think it is indeed okay to just have a blockchain validation rule that full nodes have to retrieve all the values from recent blocks and use those in blockchain validation.

I think a separate P2P network would risk adding attack vectors; the hash in the blockchain prevents falsification of data but doesn't prevent the P2P network from censoring things. The worst case of this would be a DHT, which is trivially easy to censor by small-time attackers and frequently fails even when not being attacked. I'd lean toward just adding a new wire protocol command (which I assume is what SegWit is going to do). On that note, I'd suggest that if we choose to implement this, we should closely watch how SegWit does this (at least in terms of the wire protocol) and only make changes as needed. That way we cut down on our engineering effort.
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

johnc
Posts: 89
Joined: Sun Dec 28, 2014 10:03 am

Re: Segregated Name Values

Post by johnc » Sun Jan 24, 2016 2:45 pm

Both are right, looks like bitcoin will be improved step by step, very slowly.
Eventually blocks will be composed of hashes, this is obvious, data will be on a DHT table (like bittorrent, but seeded by full nodes and users will be able to choose how many space they want to donate to the network.) and individual users will be responsible for safekeeping the data pertaining to their own coins, names, TX, as a last resort. etc.

Just how it will be implemented, i don't know, I know nothing about merkle trees, segwit etc.

Jon Snow out. :D

biolizard89
Posts: 1971
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Segregated Name Values

Post by biolizard89 » Sun Jan 24, 2016 2:51 pm

johnc wrote:Eventually blocks will be composed of hashes, this is obvious, data will be on a DHT table (like bittorrent) and individual users will be responsible for safekeeping the data pertaining to their own coins, names, TX, as a last resort. etc.

Just how it will be implemented, i don't know, I know nothing about merkle trees, segwit etc.

Jon Snow out. :D
For info on why Bitcoin people dislike DHT's, see https://bitcointalk.org/index.php?topic ... msg7521013 and https://bitcointalk.org/index.php?topic ... msg5970778 .
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

phelix
Posts: 1631
Joined: Thu Aug 18, 2011 6:59 am

Re: Segregated Name Values

Post by phelix » Wed Jan 27, 2016 4:45 pm

Very interesting idea. But there still need to be incentives in place for miners to actually distribute the value data. The only reason miners have to broadcast blocks bodies is so that others can verify them....
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

biolizard89
Posts: 1971
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Segregated Name Values

Post by biolizard89 » Wed Jan 27, 2016 9:05 pm

phelix wrote:Very interesting idea. But there still need to be incentives in place for miners to actually distribute the value data. The only reason miners have to broadcast blocks bodies is so that others can verify them....
Yes, I agree. This is why I think using a DHT, for example, is a very bad idea (among the other issues with a DHT).

I *think* that the sufficient incentive is this: all full nodes will reject any block unless they are given the full Segregated Name Values structure and can verify that the hashes match. This means that miners have an incentive to broadcast that data, otherwise their block will be rejected and they will forfeit their block reward.

We're not operating in a vacuum; Segregated Witness has the same issues, and (I think) they make the same argument for the same solution: while some lightweight users won't download the witness data, the fact that full nodes will reject a block that doesn't have accessible witness data, ensures that miners won't withhold that data.

In our case, things are *slightly* different, because my suggestion was that even full nodes or miners would be allowed to stop holding the values after some period of time. For purposes of argument, let's say 72 kiloblocks (so double the expiration period). I don't think this opens us up to attacks, unless someone can produce a chain reorg event that's 72 kiloblocks deep. And if that's the case, then we probably have bigger problems. There may be ways to reduce this (already tiny) attack surface via sharding, which Bitcoin devs are actively researching for Bitcoin use anyway. But it's not at all clear to me that this is needed. It's also entirely plausible that we could make the "drop values after this period" threshold based on block timestamps instead of block height, which I guess might reduce attack surface in the event of such a massive reorg.

Anyway -- thanks for bringing up this point, since we definitely have to make sure that this is thoroughly addressed.
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

dolphin
Posts: 16
Joined: Wed Jul 02, 2014 6:52 pm
os: windows

Re: Segregated Name Values

Post by dolphin » Wed Jul 19, 2017 5:05 am

I agree segregated name values is a great idea. In fact, I think it is a must-have for meaningful NameCoin adoption. Let's face it, it is irrational to require any name system client to download the full blockchain or even the last 36k blocks - that is prohibitively expensive from lay man user prospective, who is mostly interested in reliable name/key/cert lookups.

I've proposed something very similar a while ago in a different thread - viewtopic.php?p=13141&sid=65357b16ff602 ... 89b#p13141

The primary reason for my proposal back then was the work on end-to-end E-mail encryption solution that utilized NameCoin as the trusted key repository. Back in the day the common feedback was to hold off for migration to newer version of bitcoin core. I haven't been active here for a while due to involvement in unrelated projects, but now, having some time in hand, would be open to implement either the original proposal in the thread or any other alternative that the community would agree to.

Please, share your thoughts...

Cheers,
Dolphin
NameCoin and Security News
Chrome extension for Gmail encryption - protect your identity and E-mails using NameCoin

biolizard89
Posts: 1971
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Segregated Name Values

Post by biolizard89 » Sat Jul 29, 2017 5:05 pm

domob wrote:Sounds like an interesting approach. One question, though: Why would you keep the values in a Merkle tree? Isn't it enough to just push the value's hash and allow for the values to be transmitted fully "out of band" with respect to the blockchain? The hash ensures that the values are still secured as they are now. In fact, such an optimisation could be implemented completely on a higher level - say, by adding a separate P2P network layer for transmitting values (not consensus relevant) and then modifying the d/ spec to require the actual values to be transmitted out-of-band and the actual d/ name value to be the hash. This could then be paired with a softfork to restrict the actual in-chain value length to 32 bytes.

Am I missing something, why is it necessary to include the actual values (not just their hashes) in a root hash? The only reason I can think of for now is that this may be used to "force" full nodes (and miners) to keep the values around for some time.
So it occurred to me that there is a reason to have a Merkle tree for this: it allows us to permanently discard the value hashes too.

Under the scheme I originally described, each name output needs to store a 32-byte hash, which is kept forever. However, consider an alternative scheme where the name output contains a 0-byte value field, and the coinbase transaction commits to a Merkle tree where the leaves of the Merkle tree contain both the full value and signatures for the full value. (Presumably you could also apply SegWit to this, so that the the values and value signatures are in separate Merkle trees.) This means that you need to download twice as many signatures for the not-yet-discarded name values, but it means that you can permanently discard the value hashes (and of course their signatures) after some period of time (say, 72 kiloblocks).

Asymptotically this should be an improvement. Also, if most of the signatures for the block are Schnorr, you might be able to do some kind of signature aggregation to eliminate most of the overhead (similar to what's being proposed for Bitcoin).
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

biolizard89
Posts: 1971
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Segregated Name Values

Post by biolizard89 » Sat Jul 29, 2017 5:12 pm

dolphin wrote:I agree segregated name values is a great idea. In fact, I think it is a must-have for meaningful NameCoin adoption. Let's face it, it is irrational to require any name system client to download the full blockchain or even the last 36k blocks - that is prohibitively expensive from lay man user prospective, who is mostly interested in reliable name/key/cert lookups.

I've proposed something very similar a while ago in a different thread - viewtopic.php?p=13141&sid=50d7ba9d9fc84 ... 0f0#p13141

The primary reason for my proposal back then was the work on end-to-end E-mail encryption solution that utilized NameCoin as the trusted key repository. Back in the day the common feedback was to hold off for migration to newer version of bitcoin core. I haven't been active here for a while due to involvement in unrelated projects, but now, having some time in hand, would be open to implement either the original proposal in the thread or any other alternative that the community would agree to.

Please, share your thoughts...

Cheers,
Dolphin
It looked to me like your original proposal was for commitments of the unexpired name set that would be used by SPV nodes; this proposal is for commitments of the name set for a single block that would be used by full nodes. Am I misunderstanding your proposal? Seems to me like these are orthogonal goals (although they both improve scalability).

Anyway -- are you possibly interested in implementing Segregated Name Values (which I've nicknamed SegVal)? It would definitely be a useful thing to implement if you're interested, although it might be useful to wait a little while to confirm that SegWit will be a thing in Bitcoin (since I'm guessing a lot of SegWit can be reused for this).
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

Post Reply