Essentially what we are trying to achieve boils down to a single question: what is the

small typo: i think <a target="_blank" rel="noopener noreferrer nofollow" href="https:

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

small typo: i think <a target="_blank" rel="noopener noreferrer nofollow"

Deciding on the applied Blind Signature Scheme about wabisabi HOT 12 CLOSED

walletwasabi commented on July 17, 2024

Deciding on the applied Blind Signature Scheme

from wabisabi.

Comments (12)

nothingmuch commented on July 17, 2024 1

small typo: i think $\sigma'$ is supposed to be $\overline{\sigma}$ (also TIL about this hack for math in github, and... wat. why like this github?!)

this seems like a simpler blind signature scheme than randomizable signature scheme we discussed.

however, i do think double spending is still a problem:

Alice obtains signatures for $m_1, m_2, m_3$ (by registering one or more inputs, doesn't matter)
Alice registers outputs for up to 6 different signatures, each with an unlinkable blinding factor

$\sigma_1\sigma_2, r_1 + r_2$ for $m_1 + m_2$
$\sigma_1\sigma_3, r_1 + r_3$ for $m_1 + m_3$
$\sigma_2\sigma_3, r_2 + r_3$ for $m_1 + m_2$
$\sigma_1, r_1$ for $m_1$
$\sigma_2, r_2$ for $m_2$
$\sigma_3, r_3$ for $m_3$

so i think we need some sort of accumulator for the blinding factors, and to prove that each sum is due to a combination of previously unused blinding factors, similar to zcash nullifiers.

as for range proofs - since these are Pedersen commitments isn't that exactly the same as what's used in confidential transactions?

from wabisabi.

nopara73 commented on July 17, 2024 1

Maybe this can be solved with some clever padding scheme...

Plan ZS could be to add a bunch of random sub-satoshi amounts, so the message space would be sufficiently large. In that case there can be number of commitments * 1 satoshi error in the final sum, so we have to make sure it's handled properly in software.

from wabisabi.

nopara73 commented on July 17, 2024

Shouldn't also be requirement for the homomorphic commitment scheme be that rangeproofs can be applied to it, or it's always given?

It's somewhat outside the scope of this conversation, but resolving the double spending issue is also a requirement, but that may be possible to resolve later.

Now that I got to the end, isn't both of my issue got resolved, even the double spend? Since the blind sigs can only be used once we can verify that signatures aren't reused when we prove the sum!

from wabisabi.

seresistvanandras commented on July 17, 2024

Yeah, indeed! 120% agree! These are two crucial additional requirements.

We need to prevent double-spending!
The commitment scheme should also support some efficient range proof system!

from wabisabi.

nothingmuch commented on July 17, 2024

sorry, that's not correct, since if alice reveals all the r values the coordinator can subtract them to identify this behaviour. but alice can just generate 6 more commitments to value 0 and add them to each registration.

from wabisabi.

nopara73 commented on July 17, 2024

@nothingmuch just to confirm. Your conclusion is that double spending is prevented this way, too, right?

from wabisabi.

nothingmuch commented on July 17, 2024

no, ~~not without accumulators~~ (but that should be a solved problem, zcash accomplishes it in a more complicated setting, and 2 of the divisible e-cash papers we shortlisted for review are based on accumulators and are likely to be a bit simpler than how zcash does it)

edit: i jumped to conclusion there, obviously accumulators are not the only way

from wabisabi.

seresistvanandras commented on July 17, 2024

small typo: i think $\sigma'$ is supposed to be $\overline{\sigma}$

Indeed. Thanks Yuval! Should be fixed now!

however, i do think double spending is still a problem:

Alice obtains signatures for $m_1, m_2, m_3$ (by registering one or more inputs, doesn't matter)

Alice registers outputs for up to 6 different signatures, each with an unlinkable blinding factor

$\sigma_1\sigma_2, r_1 + r_2$ for $m_1 + m_2$

$\sigma_1\sigma_3, r_1 + r_3$ for $m_1 + m_3$

$\sigma_2\sigma_3, r_2 + r_3$ for $m_1 + m_2$

$\sigma_1, r_1$ for $m_1$

$\sigma_2, r_2$ for $m_2$

$\sigma_3, r_3$ for $m_3$

This is a great and important observation! An important attack vector, we need to mitigate! I show below an easy fix!

so i think we need some sort of accumulator for the blinding factors, and to prove that each sum is due to a combination of previously unused blinding factors, similar to zcash nullifiers.

I think we do not even need that heavy cryptographic machinery, like accumuators. Don't forget that Simplicity is the ultimate design goal! Just a quick reminder that $g$ and $h$ are generators in the used elliptic curve group $\mathbb{G}$ and only the coordinator knows the discrete logarithm between $g$ and $h$ , in other words they don't know $x_i \lor x_j$ such that $g^{x_i}=h \lor h^{x_j}=g$ . Maybe neither coordinator knows, the only important thing is that mixing participants should not know, otherwise they could cheat. The secret key of the coordinator is $x$ , while the public key of the coordinator is $g^x$ . Whenever a user would like to merge two UTXOs the user encloses the hashes of the UTXO values and coordinator's signatures on them: $(H(m_1),\sigma(m_1),H(m_2),\sigma(m_2))=(h^{m_1},h^{m_{1}x},h^{m_2},h^{m_{2}x})$ . Since $m_1+m_2$ is public, the coordinator can check whether $h^{x(m_1+m_2)}=h^{xm_1}h^{xm_2}=\sigma(m_1)\sigma(m_2)$ . Coordinator accepts each signatures only once, therefore double-spending is effectively and elegantly solved. Note that coordinator does not learn the underlying messages, coordinator only learns that these are valid signatures on the hashes of SOME message. However small message space might cause problems...

Still, we have other difficulties arising from the small message space, ie. coordinator knows that m is less than, say 10BTC, which amounts to $10^9$ Satoshi. Hence when the coordinator sees the hash of some message $m$ , i.e. $H(m)$ , it could figure out simply the underlying message just by bruteforcing the exponent, put differently, solving the DLOG with a simple and efficient brute-force due to the constrained message space. Maybe this can be solved with some clever padding scheme...should think about this more!

as for range proofs - since these are Pedersen commitments isn't that exactly the same as what's used in confidential transactions?

They're the same, so it should not be a problem! :) We'll surely find appropriate range proof systems if we decide to use BLS with the modular exponentiation hash function

from wabisabi.

seresistvanandras commented on July 17, 2024

This is superb! You are right! I had a way more complicated solution in mind but yours is the most elegant and simplest we can come up with, I think!

from wabisabi.

nopara73 commented on July 17, 2024

Oh, actually just make the 0.1 and 0.01 satoshi decimal places constant zeros and then the software won't even need to care about it anymore.

from wabisabi.

nothingmuch commented on July 17, 2024

something to consider that i thought I'd mention since it's now buried in the slack log:

suppose we align the amount so that the bottom ~128 bits of the m are completely random and never represent a quantity more than say a millisatoshi (to prevent them summing to more than 1 sat), this means the top bits of m would be strongly biased.

this bias in the field elements might mean that the coordinator could use e.g. lattice based attacks to uncover the amounts

from wabisabi.

nopara73 commented on July 17, 2024

Summary of this conversation: #5

Closing this issue, @nothingmuch's attack is addressed there.

from wabisabi.

Deciding on the applied Blind Signature Scheme about wabisabi HOT 12 CLOSED

Comments (12)

Related Issues (20)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent