Nostr Web Client

You can use 128 bit challenge for the PoK (give up batch verification)

Oh that’s interesting. You reveal the bytes *with* the PoK. Ok then I raise you: We use BLS where the PoK is deterministic.

waxwing 1mo ago 💬 3

First, check the recent discussion on the mailing list (on inability to embed data in schnorr), a few interesting thoughts about this model there (i was limiting discussion to P, R, s outputs, i claimed secret key revelation is inevitable if you do publish, ajtowns point in particular (but not only) is very interesting that you can actually get round that limitation in practice, on bitcoin, even if not in theory).

Currently I'm writing up a small presentation on this topic and got to thinking about the deeper point: ZK (pok or w/e) requires blinding, which requires randomness. Data can be embedded in that but the devil's in the details. A funny example: imagine choosing to do RFC6979 with a ZKP of correctness, so the randomness is deterministic and constrained; but here, if say the ZKP is Groth16 (just an e.g.), it itself contains randomness that could be similarly misused (I think? not sure yet).

As for your BLS example: good point. It's not a ZKP system, it relies on a computational assumption, it's one-shot so you do, I agree, get the property you need: deterministic without wiggle room for data embedding (I think!). But ... there's actually no way that could or would be implemented on bitcoin (btw were you imagining *only* the PoK as BLS? that seems messy).

Reply to this note

Please Login to reply.

Discussion

waxwing 1mo ago

https://eprint.iacr.org/2022/1263 looks like a relevant paper!

Zero-Knowledge Goof 1mo ago

Thanks for pointing me to the mailing list post. I don’t know what you mean by there’s no way BLS could be implemented on Bitcoin — you could introduce a BLS12-381 address very easily in a soft fork. This would make data sub-exponential data embedding impossible. Also the BLS PoK (ok technically a PoP) can be constructed non-interactively for aggregated BLS multisig.

waxwing 1mo ago

Re: BLS is "impractical": fair push back, it's not like it's totally out of the question. I have at least one practical reason why I'm super skeptical, in addition to the obvious "new crypto in btc" reason, and that is quantum. It is going to be a Herculean task to implement any form of PQC on Bitcoin, and so I'd struggle to see how the energy would be found to do this, considering it's not PQ. Still, shrug, you're right that it's possible.

I suppose it's worth mentioning at this point that I'm very against this idea, lol. (I've taken to calling it "Purecoin", do you like it?). It makes utxos massively burdensome, stops public derivation, makes L2s basically not work (when you were saying lightning could still work with adaptors, i guess you imagine a model with still having timelocks (relative in particular!)? In my "purecoin" concept I removed timelocks as well since you can embed data in them).

waxwing 1mo ago 💬 3

Also you didn't answer but I'm surmising you mean BLS for *everything* not only PoK? Because the alternative is bad in two ways, first the obvious of mapping privkeys between groups and second because if schnorr in transaction signatures you can still leak a large amount of data as per ajtowns' idea.

Zero-Knowledge Goof 1mo ago 💬 2

Haha BLS everything of course. I can’t even imagine how you could do it only for the PoK. Any equivalence proof between curves will be a PoK so there’d be no point in the BLS in the first place.

I like “purecoin”. Although I also think it’s not a great direction. It’d still make way more sense than bip444. It would be interesting to present a possible if not realistic soft fork that actually would significantly reduce the amount of data embedding that could be achieved per vbyte. Then a rational debate could be had.

Point taken about locktimes. I don’t think anyone would be in favour of disabling lightning. You’d probably have to leave the spammers with that one.

Zero-Knowledge Goof 1mo ago

Oh also public derivation could work with the BLS scheme I think. Just don’t commit to the public key in the hash to curve for the PoK and it becomes malleable.

waxwing 1mo ago 💬 2

OK. But my gut would tell me that malleable (not pubkey prefixed) BLS sigs would be unsafe. I'm assuming by PoK you do mean BLS sigs. Wouldn't you be able to forge sigs on related keys?

Zero-Knowledge Goof 1mo ago

Yeah that’s a feature. You can forge the PoK on related keys. If a key has a known key then you can’t sub-exponential data with it or any related keys either.

waxwing 1mo ago 💬 1

I think I agree.

(Apart from 'key has a known key' 😁)

Zero-Knowledge Goof 1mo ago

Haha that sentence was extremely slurred but it sounds like you got the idea!

waxwing 1mo ago

I agree it would be nice to prevent this somewhat formally, because I think there's some quite woolly thinking about "it's impossible to prevent data" without concrete analysis. Btw, even purecoin suffers also from amount fields being plaintext: though it's tough, a well funded 'spammer' can probably get a number of bytes of data on chain with a "split and then recombine a large single utxo" strategy. It's an extremely low data embedding rate on a per tx basis, but it's not nothing, assuming we succeeded in getting rid of locktimes, and pubkey and sig embedding. If we encrypted amounts we might hit the old 'zk implies randomness implies embedding' problem again.

waxwing 1mo ago 💬 2

'present' not 'prevent'

Zero-Knowledge Goof 1mo ago

Cool. I think a first step is just to figure out the actual data embedding rate for a few different approaches/assumptions. Has anyone even figured this out for BIP444?

waxwing 1mo ago

Good Q. But i fear the other side of the debate has already conceded the basic point, while arguing 'contiguous' somehow matters...

I think a Schnorr based purecoin has anything from 25 to 50%+ embedding rate depending on a bunch of stuff. BLS it'd be super small. Unless we missed a trick.