privatesend: Implement Random Round Mixing #3661
Conversation
Signed-off-by: pasta <[email protected]>
This value is used to deterministically pick a random number of rounds to mix, between N and N + GetRandomRounds. A salt is needed in addition to the inputs hash to ensure that an attacker learns nothing from looking at the blockchain. Signed-off-by: pasta <[email protected]>
This implements "Random Round Mixing." Previously, attempted attacks on PrivateSend assumed that all inputs had been mixed for the same number of rounds. Noramlly assuming 2,4,8 or 16. While none of these attacks have been successful, they still teach what we can do to make our system more robust, and one of those ways is to implement "Random Round Mixing". Under the previous system, inputs were mixed up until N rounds (configured by user). At this point, the input was considered mixed, and could be private-sent. Under this new system, an input will be mixed to N rounds like prior. However, at this point, Sha256d(input, salt) will be calculated (note: this likely could be a more efficient hash function than double sha256, but that can be done in another PR / version if needed). If (hash % 2 == 0), then the input will be mixed again. This results in an exponential decay where if you mix a set of inputs, half of those inputs will be mixed for N rounds, 1/4 will be mixed N+1, 1/8 will be mixed N+2, etc. This current implementation caps it at N+2. This results in mixing an average of N+0.875 rounds. If you removed the cap, you would mix on average N+1 rounds. Signed-off-by: pasta <[email protected]>
PastaPastaPasta
changed the title
PastaPastaPasta
changed the title
…mparing rounds directly to ensure consistency between coin selection logic, balance calculations and gui
Signed-off-by: pasta <[email protected]>
Signed-off-by: pasta <[email protected]>
|
Added your commits, plus some modifications @UdjinM6 |
Signed-off-by: pasta <[email protected]>
Signed-off-by: pasta <[email protected]>
PastaPastaPasta
force-pushed
the
randomize-ps-rounds
branch
from
09d2ff3 to
e64de32
Compare
|
Nice 👍 Didn't test it yet but looks good at a first glance.
What about at least adding c1b7027 to this PR? Another thought i had which i didn't implemented yet because i don't think its absolutely needed is: We could dump the salt to the dump-file in |
I didn't use single Sha256 cause it adds ~7 LOC and makes it a bit less readable imo, and I don't know if that's actually valuable... Maybe in the future we could modify the |
|
Good point on Could also add "ps_salt" entry in |
So you prefer to have some less lines of code (which aren't hard to read in any way imo) and therefor run SHA256 twice instead of just running once which basically cuts execution time for hashing in
Oh right, adding it as comment there + RPC sounds good imo. I think i like the idea of having |
|
@PastaPastaPasta re hashing in |
Uses just 1 sha256 instead of 3 (1 in SerializeHash + 2 in Hash)
Done |
Signed-off-by: pasta <[email protected]>
* Use GetRealOut... instead of Capped Signed-off-by: pasta <[email protected]> * Add "ps_salt" value to walletdb This value is used to deterministically pick a random number of rounds to mix, between N and N + GetRandomRounds. A salt is needed in addition to the inputs hash to ensure that an attacker learns nothing from looking at the blockchain. Signed-off-by: pasta <[email protected]> * Implement Random Round Mixing This implements "Random Round Mixing." Previously, attempted attacks on PrivateSend assumed that all inputs had been mixed for the same number of rounds. Noramlly assuming 2,4,8 or 16. While none of these attacks have been successful, they still teach what we can do to make our system more robust, and one of those ways is to implement "Random Round Mixing". Under the previous system, inputs were mixed up until N rounds (configured by user). At this point, the input was considered mixed, and could be private-sent. Under this new system, an input will be mixed to N rounds like prior. However, at this point, Sha256d(input, salt) will be calculated (note: this likely could be a more efficient hash function than double sha256, but that can be done in another PR / version if needed). If (hash % 2 == 0), then the input will be mixed again. This results in an exponential decay where if you mix a set of inputs, half of those inputs will be mixed for N rounds, 1/4 will be mixed N+1, 1/8 will be mixed N+2, etc. This current implementation caps it at N+2. This results in mixing an average of N+0.875 rounds. If you removed the cap, you would mix on average N+1 rounds. Signed-off-by: pasta <[email protected]> * Make PS salt a private member of CWallet, tweak the way it's initialized * Introduce `CWallet::IsFullyMixed` and use it everywhere instead of comparing rounds directly to ensure consistency between coin selection logic, balance calculations and gui * Tweak `GetRealOutpointPrivateSendRounds` to respect random rounds * Tweak IsFullyMixed to make decision on a per-outpoint basis instead of a per-tx one * make a comment doxygen Signed-off-by: pasta <[email protected]> * Rename GetPrivateSendSalt InitPrivateSendSalt, since it is not a getter Signed-off-by: pasta <[email protected]> * move the comment below GetRounds call Signed-off-by: pasta <[email protected]> * don't use GetCappedOutpointPrivateSendRounds when printing to RPC Signed-off-by: pasta <[email protected]> * Simplify hashing in IsFullyMixed Uses just 1 sha256 instead of 3 (1 in SerializeHash + 2 in Hash) * undo comment change Signed-off-by: pasta <[email protected]> Co-authored-by: UdjinM6 <[email protected]>
* Use GetRealOut... instead of Capped Signed-off-by: pasta <[email protected]> * Add "ps_salt" value to walletdb This value is used to deterministically pick a random number of rounds to mix, between N and N + GetRandomRounds. A salt is needed in addition to the inputs hash to ensure that an attacker learns nothing from looking at the blockchain. Signed-off-by: pasta <[email protected]> * Implement Random Round Mixing This implements "Random Round Mixing." Previously, attempted attacks on PrivateSend assumed that all inputs had been mixed for the same number of rounds. Noramlly assuming 2,4,8 or 16. While none of these attacks have been successful, they still teach what we can do to make our system more robust, and one of those ways is to implement "Random Round Mixing". Under the previous system, inputs were mixed up until N rounds (configured by user). At this point, the input was considered mixed, and could be private-sent. Under this new system, an input will be mixed to N rounds like prior. However, at this point, Sha256d(input, salt) will be calculated (note: this likely could be a more efficient hash function than double sha256, but that can be done in another PR / version if needed). If (hash % 2 == 0), then the input will be mixed again. This results in an exponential decay where if you mix a set of inputs, half of those inputs will be mixed for N rounds, 1/4 will be mixed N+1, 1/8 will be mixed N+2, etc. This current implementation caps it at N+2. This results in mixing an average of N+0.875 rounds. If you removed the cap, you would mix on average N+1 rounds. Signed-off-by: pasta <[email protected]> * Make PS salt a private member of CWallet, tweak the way it's initialized * Introduce `CWallet::IsFullyMixed` and use it everywhere instead of comparing rounds directly to ensure consistency between coin selection logic, balance calculations and gui * Tweak `GetRealOutpointPrivateSendRounds` to respect random rounds * Tweak IsFullyMixed to make decision on a per-outpoint basis instead of a per-tx one * make a comment doxygen Signed-off-by: pasta <[email protected]> * Rename GetPrivateSendSalt InitPrivateSendSalt, since it is not a getter Signed-off-by: pasta <[email protected]> * move the comment below GetRounds call Signed-off-by: pasta <[email protected]> * don't use GetCappedOutpointPrivateSendRounds when printing to RPC Signed-off-by: pasta <[email protected]> * Simplify hashing in IsFullyMixed Uses just 1 sha256 instead of 3 (1 in SerializeHash + 2 in Hash) * undo comment change Signed-off-by: pasta <[email protected]> Co-authored-by: UdjinM6 <[email protected]>
5943c93 feat: introduce `coinjoinsalt` RPC to allow manipulating per-wallet salt (Kittywhiskers Van Gogh) 4fa3d39 wallet: refactor `InitCoinJoinSalt()` to allow for setting a custom salt (Kittywhiskers Van Gogh) Pull request description: ## Motivation CoinJoin utilizes a salt to randomize the number of rounds used in a mixing session (introduced in [dash#3661](#3661)). This was done to frustrate attempts at deobfuscating CoinJoin mixing transactions but also has the effect of deciding the mixing threshold at which a denomination is considered "sufficiently mixed", which in turn is tied this salt, that is in turn, tied to the wallet. With wallets that utilized keypool generation, this was perfectly acceptable as each key was unrelated to the other and any meaningful attempts to backup/restore a wallet would entail backing up the entire wallet database, which includes the salt. Meaning, on restore, the wallet would show CoinJoin balances as reported earlier. With the default activation of HD wallets in legacy wallets (and the introduction of descriptor wallets that construct HD wallets by default), addresses are deterministically generated and backups no longer _require_ a backup of the wallet database wholesale. Users who export their mnemonic and import them into a new wallet will find themselves with a different reported CoinJoin balance (see below). https://github.com/dashpay/dash/assets/63189531/dccf1b17-55af-423d-8c36-adea6163e060 ## Demo **Based on [`c00a3665`](kwvg@c00a366578354810908e4034c5a73ab3782f2cc6)** https://github.com/dashpay/dash/assets/63189531/c60c10e3-e414-46af-a64e-60605a4e6d07 ## Checklist: - [x] I have performed a self-review of my own code - [x] I have commented my code, particularly in hard-to-understand areas - [x] I have added or updated relevant unit/integration/functional/e2e tests - [x] I have made corresponding changes to the documentation - [x] I have assigned this pull request to a milestone _(for repository code-owners and collaborators only)_ ACKs for top commit: UdjinM6: ACK 5943c93 Tree-SHA512: 8e5bdd18ecce4c14683fbeb1812b0b683a5a5b38405653655c3a14b1ab32a22b244b198087876cd53ca12447c2027432afe4259ef3043be7fddf640911d998f0
3 participants
The first commit simply uses "GetRealOutpointPrivateSendRounds" in a few behind the scenes places where I saw it
The second commit:
Add "ps_salt" value to walletdb
This value is used to deterministically pick a random number of rounds to mix, between N and N + GetRandomRounds. A salt is needed in addition to the inputs hash to ensure that an attacker learns nothing from looking at the blockchain.
Third Commit:
Implement Random Round Mixing
This implements "Random Round Mixing." Previously, attempted attacks on PrivateSend assumed that all inputs had been mixed for the same number of rounds. Normally assuming 2,4,8 or 16.
While none of these attacks have been successful, they still teach what we can do to make our system more robust, and one of those ways is to implement "Random Round Mixing".
Under the previous system, inputs were mixed up until N rounds (configured by user). At this point, the input was considered mixed, and could be private-sent. Under this new system, an input will be mixed to N rounds like prior. However, at this point, Sha256d(input, salt) will be calculated (note: this likely could be a more efficient hash function than double sha256, but that can be done in another PR / version if needed). If (hash % 2 == 0), then the input will be mixed for one more round.
This results in an exponential decay where if you mix a set of inputs, half of those inputs will be mixed for N rounds, 1/4 will be mixed N+1, 1/8 will be mixed N+2, etc. This current implementation caps it at N+3. This results in mixing an average of N+0.875 rounds. If you removed the cap, you would mix on average N+1 rounds.
I tested this by starting three wallets mixing, and the distribution (while not perfect) was exactly how I would expect with about 50%, 25%, 12.5%, 12.5%. This also fixes #3525