New paper:

"Efficient and Post-Quantum Zero-Knowledge Proofs for Blockchain Confidential Transaction Protocols"

Shang GAO and Tianyu ZHENG and Yu GUO and Bin XIAO

>Abstract: We propose new zero-knowledge proofs for efficient and post-quantum ring confidential transaction (RingCT) protocols based on lattice assumptions in Blockchain systems. First, we introduce an inner-product based linear equation satisfiability approach for balance proofs with a wide range (e.g. 64-bit precision). Unlike existing balance proofs that require additional proofs for some ''corrector values'' [CCS'19], our

approach avoids the corrector values for better efficiency.

>Furthermore, we design a ring signature scheme to efficiently hide a user's identity in large anonymity sets. Different from existing approaches that adopt a one-out-of-many proof [CCS'19, Crypto'19], we show that a linear sum proof suffices in ring signatures which could avoid the costly binary proof part. We further use the idea of ''unbalanced'' relations to build a logarithmic-size ring signature scheme.

> Finally, we show how to adopt these techniques in RingCT protocols and implement a prototype to compare the performance with existing approaches. The results show our solutions can reduce about 25% proof size of Crypto'19, and up to 70% proof size, 30% proving time, and 20% verification time of CCS'19. We also believe our techniques are of independent interest for other privacy-preserving applications such as secure e-voting

and are applicable in a generic setting.

"based on lattice assumptions"

Shame sarang isn't around for a quick sanity check on how speculative these are.

Can have him look at it after the holidays

I was assuming he'd already know what those (lattice assumptions) are, and what amount of scrutiny they passed already, didn't mean "plz read paper".

ie, quick reject filter ^_^

Yeah should be fine and if it isn't a quick reject should be interesting nevertheless.

My arguments for unique change addresses: gist.github.com/tevador/50160d160d2…52ae02eb3d17024#gistcomment-4006358

I think it can work. We can attribute funds in change outputs to the account of the first key image in its tx.

I think usually wallet software doesn't mix outputs from different accounts in a single tx

'usually'

I am going to write a baseline PoC for jamtis over the next couple weeks (excluding all the serialization stuff).

I already have a python script that can generate addresses

I mean a PoC integrated with seraphis, with a full account model and mock ledger.

cool

The biggest architecture conundrum I have is how to organize the account structure (with wallet tiers, merchant/nonmerchant, multisig).

"We can attribute funds in change outputs to the account of the first key image in its tx." > Oh, nvm attribution can be done via the one-time address construction.

Yes, this rule will apply not just to change outputs, but to all self-spends

How do you handle account history in that case? A change amount should be invisible, but a self-spend needs to show up as an event.

Maybe fork again with a domain separator "self-spend"? If checking change fails, check if self-spend.

how are they differentiated now?

I'm not sure... moneromooo ?

Another thing: we should modify the key k_a^i for self-spends from merchant accounts to hide them from Tier 1.5. Otherwise Tier 1.5 can still detect them via the amount commitment. I think we can use k_a^(i,j) as if it was a non-merchant account. So Tier 1.5 won't be able to see self-spends, which is fine for the inteded use case.

The sent amount is stored in the wallet cache. If the wallet cache is destroyed and recreated from the chain, it'll be deemed to be 0.

I think it can be simply differentiated by the presence of a non-owned output. If the TX has a non-owned output -> the other output is change. Otherwise it's a churn and can show up in the history. I think churns also have a zero-amount fake change output.

yes they do

tevador: you can just redefine `q = H("dh", k_vb, K_e)`, which affects the whole output.

"I think it can be simply differentiated..." IMO this leaves too many edge cases. Better to have a robust solution that always works. I think adding another branch to output generation isn't a big burden.

Could be H("dh change", k_vb, K_e) or H("dh churn", k_vb, K_e)

"self-spend" > "churn", since there are reasons other than churn to self-spend (e.g. output splitting).

It can't usually be differentiated: if you have a 10 output and send yourself 3, you'll send 10 and get back 3 and 7 (ignoring the fee for the sake of the argument). You cannot guess which one was the amount sent.

so another new feature then

it's not really a feature, since all of this is hidden from users; another design detail :)

it's a tiny feature (correct tx history listing for self-spends after wallet restore)

oh I suppose

Btw, the zero-amount change output for self-spends should go to a random address, otherwise it's another leak (both outputs having a matching view tag). Not sure how it's done now.

right not it's to a random address

now*

How many EC ops does "checking the view tag" require ? It used to be at least a mult by G IIRC, but it's just dawning on me that the current conversation implies no ops (ie, public)...

one variable base scalarmult

With what scalar ?

k_fr (new private key)

"find-received key"

OK, the third key, that resolves my sudden confusion. Thanks.

Yes, basically the current "view key" is split into two: "view-balance key" and "find-received key". Tier 1 wallet only has the latter.

Presumably (I kinda forget how the G mult is sped up), since a wallet will send that key to a third party daemon which will scan many outputs, that daemon would be able to preprocess the key to have that mult be essentially as fast as a G mult, right ?

ie, the preprocessing gets amortized if many scans are to be done ?

I guess some standard multiexponentiation algorithms could be used if you want to check multiple keys against the same base

No, I was thinking multiple bases against the same key. Like when multiplying by G. Same base, many keys.

I don't think you can optimize multiple bases for the same key, but I could be wrong

So... the speedup of multiplying by G is... hand crafted, knowing the bits ?

If so, it seems SMC might work...

Unless G just has the right bit pattern to be fast. But I think it's not chosen to have anice bit pattern.

no, multiplying by G is a fixed base and multiple keys, so it would work

if you want to calculate x B for the same point B and many different values of x, you can precalculate some table that will speed things up

moneromooo: view tags already use `generate_key_derivation()`, which can leverage supercop. Are you thinking there are further optimizations above that?

I don't know the details, I just know a*G is substantially faster than a*K, and if we reuse K a lot, some slow precalc might be amortized to make A*K fast.

Yes, if a third party has many private keys of users and wants to calculate k_fr^i K_e for each user i

I suppose if you need to compute `generate_key_derivation()` many times on the same base key, you could first deserialize to `ge_p3` representation (instead of deserializing for each call).

It would require an update to supercop

Anyway, this is just musing on possible speedups, kind of a tengent really.

Idk how costly deserializing is, compared to the scalar mult

the speed up is not just about the deserialization, it's possible to prepare some table of values like 1*B, 2*B, 4*B, 8*B, ... and then calculate x*B much faster

ah, well if you are scanning each output with 100+ keys, that might be worthwhile; would likely require a lot of expertise to code up

Scanning 10k outputs with one key.

Wait. I am an idiot.

Sigh.

Ignore me.