blind symmetric commitment for stronger byzantine voting resilience

[iddo]

You said here that the network won't allow Alice to double-spend because when Alice tries to double-spend she exposes her pubkey and then the network will detect and respect the earlier H(pubkey)H(txn) blind commitment transaction.

correct.

So what's the difference between an attacker who knows the pubkey and creates H(pubkey)H(whatever), and Alice who creates the legitimate H(pubkey)H(txn) ?

The attacker doesnt know Alice's pubkey - Alice and Bob keep it secret until the transaction is committed.  Alice & Bob should store it securely (eg encrypt it in their wallets).

So I take it that you now agree with what I wrote in post #17 here, and that your auth=HMAC-SHA256-128(K,tx-commit) isn't relevant here and therefore doesn't fix anything in this context. This means that any malicious attacker who obtained any of Alice's pubkeys can broadcast H(pubkey)H(whatever) and instantly lock Alice's coins forever. We don't store the pubkeys encrypted in wallet.dat, otherwise the client would have to prompt for the AES passphrase all the time. So far it seems to me that this blind commitments scheme is totally impractical, in the sense that if we'd hardfork and roll out this scheme then huge amounts of coins will get destroyed in rapid rates by malicious attackers, or even greedy attackers who wish to deflate the total money supply.

I claim that there's an inherent contradiction between blind commitments which prevent the majority of the hashpower from imposing their policies, and protection from double-spendings. If Alice sends her coins to Bob in a blind fashion, then either the hashpower majority can impose their policies on Bob because he must decommit before sending his merchandise to Alice, or Alice can double-spend and defraud Bob.

[1714129358]

1714129358

[1714129358]

1714129358

[1714129358]

1714129358

[1714129358]

1714129358

[adam3us]

So I take it that you now agree with what I wrote in post #17 here, and that your auth=HMAC-SHA256-128(K,tx-commit) isn't relevant here and therefore doesn't fix anything in this context.

Yes I said that myself also in the post you're referring to:

however that doesnt change the picture that you need to keep your public key secure for committed transactions, and use it once only also.  So either the client needs to encrypt them, or you could consider the public key alternative

(It was an aside more about the size of committed payments).

We don't store the pubkeys encrypted in wallet.dat, otherwise the client would have to prompt for the AES passphrase all the time. So far it seems to me that this blind commitments scheme is totally impractical, in the sense that if we'd hardfork and roll out this scheme then huge amounts of coins will get destroyed in rapid rates by malicious attackers, or even greedy attackers who wish to deflate the total money supply.

I dont think it creates  backwards compatibility issue.  If the client is changed to store the public key in the encrypted section as if it were part of the private key, but  the coin address would be stored still in the public section, that would fix the problem in a backwards compatible way, because receiving coins only uses the coin address, not the public key.  Old keys (prior to a client upgrade) that had already had their public keys somewhat exposed by storage on the un-encrypted part of the wallet would need to be marked as not suitable for committed transactions (unless the user is convinced he never spent with the public keys, which the network or his tx log can tell him, and that his backups and machine are secure enough for his purposes without the encryption.)  The only threat from the old keys not being secret is unavailability of the policy defense of committed transactions for the affected coins, and that is the status quo without the fix dishonest miner power centralization fix provided by committed transactions.  If the user is unsure he can try a committed spend.  If it doesnt work as the miner is blocking it, he already had a problem because the miner would've blocked his uncommitted transaction.  He can still try again uncommitted but clearly that is also likely to be blocked.  His only remaining bet is to wait until another miner wins the lottery, includes his payment, and hope the dishonest but >50% miner isnt motivated enough to try to orphan the transaction; he might like to spend the coins in many small parts just to make life difficult for the dishonest miner (so he has to waste power creating many orphans). 

I think that might be fixable, but I am not sure it is worth the effort because the verify is slightly slower and if people dont like the problem, they should implement and deploy the solution, not focus on the boundary condition for legacy coins.   It might be possible to create a second different type of commitment that anyone who has seen both the public key and at least one a signature from the public key can verify, but someone who has seen only the public key can not.  That would still be safe because the coin can not be spent without revealing a signature.  That would be a secret key commitment (after secret key certificates that Stefan Brands credentials are based on).  Let me have a play with that it sounds interesting.  I am not sure yet if you can do it deterministically (ie so the recipient doesnt have to scan all secret key commitments is the issue.)  One problem is DSA sigs needlessly complicated Schnorr's base protocol, NIST/NSA did it to avoid paying Schnorr for his patent.  In most ways Schnorr signatures are superior and more flexible than DSA, eg it is easy to make threshold and split key where that gets quite complicated with DSA.  (The Schnorr patent expired in 2008.)

Anyway thats the problem committed transactions are trying to fix, that it doesnt work with as much assurance before people upgraded cant really be blamed on the protocol.

Also the committed coin cant be locked by someone malicious who knows the public key, because the fake committer doesnt know the private key so the transaction will be bogus.  The real owner of the private key can unlock the fake committed transactions to a committed payment receiver or to the list via decomitting, by posting his public key in a normal signature, which will immediately show there is no committed double spend as the only committed transactions are unsigned fakes.

I claim that there's an inherent contradiction between blind commitments which prevent the majority of the hashpower from imposing their policies, and protection from double-spendings. If Alice sends her coins to Bob in a blind fashion, then either the hashpower majority can impose their policies on Bob because he must decommit before sending his merchandise to Alice, or Alice can double-spend and defraud Bob.

See above, I think all attackers are powerless.  If you see a flaw I'll be interested to discuss it.

Adam

[mmeijeri]

@Adam:

Can you give more details about how you would encode the commitment within the existing transaction format? Or are you proposing a new format as well as new logic for dealing with it?

[iddo]

Hello Adam,

The plan is actually to move in the opposite direction soon (link), by supporting deterministic wallets with type-2 derivation by default in the Satoshi client (as well as other clients). With type-2, the user doesn't need to access his privkeys (so there's no need to prompt for AES passphrase) when generating new receiving addresses, only when the user wishes to actually spend coins, which is the safest client behavior, and there are other advantages as well (e.g. delegating pubkeys-only derivation to untrusted 3rd-party). In order to do the type-2 derivation, we use the key homomorphism property of ECDSA, and we need to access the pubkey itself (not its hash).
Even without deterministic wallets, maybe you and I could maintain our pubkeys as secret data in our current random-independent wallets, but for the average user the risk is much too extreme, if it were the case that a leakage of any pubkey that falls into the hands of some greedy/malicious attacker would mean that the attacker can instantly lock forever the coins that are associated with that pubkey.

Also the committed coin cant be locked by someone malicious who knows the public key, because the fake committer doesnt know the private key so the transaction will be bogus.  The real owner of the private key can unlock the fake committed transactions to a committed payment receiver or to the list via decomitting, by posting his public key in a normal signature, which will immediately show there is no committed double spend as the only committed transactions are unsigned fakes.

The fake commit is just a blind hash, if Alice can revoke a fake commit by broadcasting a signature that she created with her corresponding privkey, then she can double-spend in case Bob sends her his merchandise before he decommits, no?

[iddo]

For simplicity, if we set aside compatibility with Bitcoin and consider designing a new protocol from scratch that's based on your idea (though I still think that it'd be totally impractical in the real world, there's a reason behind the word "public" in pubkey), here are two issues:

1) The spammy txns concerns that gmaxwell raised are even more pronounced: if we spam (or use legitimately) the blockchain with many blind commitments, then when Alice (or anyone) tries to spend her coins, all the nodes have to take the pubkey that Alice now revealed and do SHA1(SHA256()) on it and compare this hash with all the unspent blind commitments in the blockchain, to make sure that Alice didn't attempt to double-spend? Wouldn't that be infeasible?

2) How to guarantee that no one will even send coins to the same hashed pubkey address more than once?

[adam3us]

The plan is actually to move [to] type-2 derivation [...] the user doesn't need to access his privkeys

That does make sense I see.  I get that you understand this but to note the committed value is the senders public key not the recipients.  [ Com( sender-pub ), Com( transaction ) ].  So the sender necessarily has to have access to his private key, and anyway at that point the sender-pub is fixed because it was a former recipient address.

The issue between committed coins and type-2 address generation you mention is with the recipient address generation.  Arent there already a pool of pre-generated addresses in the client design?  Or maybe the point is you dont need that with type-2.  You do need to store the random value r from P' = rP = rxG.  However so far with normal coins it is not security sensitive.  With committed coins it becomes semi-important (leak pub key, someone can link your committed coins).  However you can solve that with public key encryption of the r values.  ie generate random r, compute addr = RIPEMD160( SHA256( P' = rP ) ); store PKENC( pub, r ), delete r, P'.  PKENC some public key encryption.  You need to be be able to efficiently associate it with the address.  If there is an aspect of deterministically derive rather than encrypt (eg so no wallet backups need to be made or for brain wallets) then just generate r using that scheme and do not store it.  (You will need your seed then, or maybe you can store the head of a hash chain, and replace seed_{i+1} = H( seed_i ) and use r = seed_i.)

The fake commit is just a blind hash, if Alice can revoke a fake commit by broadcasting a signature that she created with her corresponding privkey, then she can double-spend in case Bob sends her his merchandise before he decommits, no?

No because Bob can distinguish fake from real as for Bob to accept the transaction he will expect to receive the decommitted transaction.  Note to protect against fake commits needs the variant with a MAC of something eg the tx commit (so you can prove the fake is a fake, and not a double spend you refuse to disclose the pre-image of - you cant prove a negative ie that you dont know a pre-image).

Adam

[adam3us]

2) How to guarantee that no one will even send coins to the same hashed pubkey address more than once?

I dont think you need to prevent reuse.  It just means you have to allow duplicates (same committed send address).  And the recipient has to get reveals for all of the associated spends to validate.

If you wanted to it should be enough to have clients reject any other than the first on validation, and senders randomize it for you.

1) if we spam (or use legitimately) the blockchain with many blind commitments, then when Alice (or anyone) tries to spend her coins, all the nodes have to take the pubkey that Alice now revealed and do SHA1(SHA256()) on it and compare this hash with all the unspent blind commitments in the blockchain, to make sure that Alice didn't attempt to double-spend? Wouldn't that be infeasible?

The recipient of the de-committed tx will have to go look at all of the matching inputs.  I think the recipients client needs to store and index by committed pub key all of the payments to him.  He can do that as they arrive (doesnt need to do it afterwards) looking backwards.  So he has like a pool of not yet decomitted received transactions.  Ones that he has processed he can probably combine into his UTXO if I get that concept.

Adam

[coastermonger]

Your solution brings up interesting ideas as it attempts to solve a difficult problem.  I was interested in this portion of your post however.  

(For realism of this risk, note that according to Kaminsky there already
exist multiple entities with reserve ASIC power each exceeding current
network difficulty who are holding part of their power in reserve for profit
maximisation reasons.

Could you provide any backing/proof/links to support this claim?  

And regardless of whatever solutions we put into place on the bitcoin network, if a mining group truly did have that much hashpower, couldn't they always just fork the blockchain and take all their coins/computer power over to another network where they can enforce their protocol?

[iddo]

Also the committed coin cant be locked by someone malicious who knows the public key, because the fake committer doesnt know the private key so the transaction will be bogus.  The real owner of the private key can unlock the fake committed transactions to a committed payment receiver or to the list via decomitting, by posting his public key in a normal signature, which will immediately show there is no committed double spend as the only committed transactions are unsigned fakes.

The fake commit is just a blind hash, if Alice can revoke a fake commit by broadcasting a signature that she created with her corresponding privkey, then she can double-spend in case Bob sends her his merchandise before he decommits, no?

No because Bob can distinguish fake from real as for Bob to accept the transaction he will expect to receive the decommitted transaction.

That's not the issue, obviously Bob received from Alice that decommitted txn, privately (i.e. not broadcasted to the network). So now you're saying that Alice broadcasts the blind commitment to the network, then Bob doesn't decommit and just sends Alice the merchandise, then Alice tries to double-spend her input with a secondary non-blind txn and networks respects Alice's secondary txn, and then Bob decommits and reveals to the network that Alice actually double-spent her input, so the network nodes reverse their earlier decision and now respect Bob's decommitted txn and dismiss Alice's secondary txn?
If that's what you meant, it wouldn't work either, because Alice could instead secretly create blind txn that spends her input and broadcast it to the network, then spend this input to Bob's address with a regular non-blind txn, and then after Bob sends her the merchandise she would decommit her secret blind txn to double-spend and defraud Bob. And there'd be other kinds attacks as well, that involve reversing very old txns that are buried in much earlier blocks.
Therefore, as far as I can see, your statement here that "committed coin cant be locked by someone malicious who knows the public key" is false. The only way that you demonstrated that prevents double-spending by Alice, unless I'm missing something, is not to allow what you said here and instead use your previous suggestion so that when Alice attempts to double-spend she reveals her pubkey and then the network nodes compute the secondary deterministic hash e.g. SHA1(SHA256(pubkey)) and verify that there are no earlier blind txns with this pubkey. If what I claim is true, then an attacker who obtains a pubkey can instantly lock the corresponding coins forever, and we must guarantee that no one will even send coins to the same hashed pubkey address more than once. If I'm wrong, please demonstrate how Bob could send his merchandise to Alice before decommitting in public (which means that the hashpower majority can impose their policies), without giving Alice the opportunity to double-spend.

[adam3us]

Going back to the commit definition (symmetric version, with defense against insider commit to junk):

(blind-sender, auth-tag, encrypted-tx-commit)

        blind-sender = SHA1( SHA256( 1, pub ) )
        auth = HMAC-SHA256-128( K, encrypted-tx-commit )
        encrypted-tx-commit = AES( K, tx-commit )
        K = SHA-256( pub )

The point of the use of K = SHA-256( pub ) is that anyone in possession of the public key can decrypt, and verify the mac.  That means direct spend-to-junk is not possible by someone without knowledge of pub.  Now of course anyone with knowledge of pub could superficially spend to junk, however as pub allows decrypt and mac check, superficial junk is fast to detect and remove, just by validating the mac.  And a more subtle spend to junk (by someone knowing pub) cant work as the coin is ignored as junk unless the MAC passes, and unless the decrypted tx contains a valid signature from pub.

you're saying that Alice broadcasts the blind commitment to the network, then Bob doesn't de-commit and just sends Alice the merchandise

yes Bob accepts the blind commitment payment after waiting however many confirmations he requires.   He does have the decommitted value Alice sent him directly (without broadcasting) so he can validate.

then Alice tries to double-spend her input with a secondary non-blind txn and networks respects Alice's secondary txn

if Alice double spends non-blind she definitionally reveals her public key, and so allows anyone to correlate with any blind commitments with the same key, and validate them, and so presuming the blind commitments are not all fakes, the secondary txn is rejected unless there are remaining sufficient funds on the address to fulfill it also.

Alternatively if Alice tried to double spend in blind committed form, the committed sender address would be the same and the recipient who needs to validate would receive the decomitted value over a private channel, and be able to validate the committed transactions.  (Validation includes discarding junk commitments).

and then Bob decommits and reveals to the network that Alice actually double-spent her input, so the network nodes reverse their earlier decision and now respect Bob's decommitted txn and dismiss Alice's secondary txn?

No reversing.  See above the secondary (double-spent non-blind) txn is rejected.  So decommiting the first (committed) transaction just optionally exposes more details about the committed transaction.

Overall the picture with blind and non-blind transactions however you mix them and whichever comes first and how much money is left on the input address after processing, is just like standard transactions.  First is accepted, later are rejected as double spends.  Despite the blinding you can still tell because two blind committed transactions with the same input address are hashed deterministically so SHA1( SHA256( pub ) ) is the same in both cases.  If you send a non-blind transaction that is also correlatable to blind addresses because the public key is revealed as part of the signature.

Therefore, as far as I can see, your statement here that "committed coin cant be locked by someone malicious who knows the public key" is false. The only way that you demonstrated that prevents double-spending by Alice, unless I'm missing something, is not to allow what you said here and instead use your previous suggestion so that when Alice attempts to double-spend she reveals her pubkey and then the network nodes compute the secondary deterministic hash e.g. SHA1(SHA256(pubkey)) and verify that there are no earlier blind txns with this pubkey. If what I claim is true, then an attacker who obtains a pubkey can instantly lock the corresponding coins forever, and we must guarantee that no one will even send coins to the same hashed pubkey address more than once.

OK this is a second issue - an insider who knows pub, was an issue with the straight hash-based commitment of the transaction.  This is why I said in a later mail (as quoted at the top of this message) encrypting and use of a MAC is more robust, and safely allows multiple use addresses, because it defends against that issue.

As you indicate preventing other users sending multiple times to the same address is problematic.

If I'm wrong, please demonstrate how Bob could send his merchandise to Alice before decommitting in public (which means that the hashpower majority can impose their policies), without giving Alice the opportunity to double-spend.

so lets say Alice is malicious, Eve is malicious but doesnt know pub, Mallory is malicious and does know pub (eg because she gave the committed coin to Alice) but Bob wants to send Alice her goods after 1 confirmation anyway provided there is no double spending within that time-period.

Com( pub, tx-commit ) = (blind-sender, auth, encrypted-tx-commit)

        blind-sender = SHA1( SHA256( pub ) )
        auth = HMAC-SHA256-128( K, encrypted-tx-commit )
        encrypted-tx-commit = AES( K, tx-commit )
        K = SHA-256( pub )

(A: indicates A broadcasts, A->B: indicates A sends to B private channel)

Alice: Com( A, "A spends 1BTC to B" )
Alice -> Bob: pub
Alice: Com( A, "A spends 1BTC to A" )
Eve: blind-sender, auth, junk    [blind-sender & auth copied from Alice commit]
Mallory: Com( A, "A spends 1BTC to M" )
Eve -> Bob     [cant send pub as doesnt know it]
Mallory -> Bob: pub

Bob can validate Alice's first spend as he has the pub.

Bob can also validate Alice's attempted double spend to herself.  However so long as the confirmation rejects the second one, it doesnt matter.  Normal bitcoin double spend semantics: first spend to reach the winning miner is valid.

now Bob can see that Eve's message is junk because the junk doesnt match the auth tag.

Bob cant tell as easily with Mallory's message as she has pub and so K; but still the tx-commit
decrypted from Mallory's message has no valid signature, as Mallory can not forge signature with Alice's key.

Bob waits 1 confirmation, and as the double spend from Alice to herself was not hashed by the winning miner, and the two fake commits from Eve and Mallory are the only other transactions relating to Alice's input, he accepts and sends the goods.

Bob nor Alice have to reveal.  They may opt to decommit after the transaction is long confirmed.

Bob can pay Carol who can pay Dave etc all without necessarily decommitting.

Each person in the chain of committed spends must see all transaction details earlier in the chain to verify its validity.  They learn this conveniently because they see the public key of the tx-commit, and from that can see the public key of the sender.  That in turn allows them to lookup the SHA1( SHA256( pub ) ) of the sender, and from that transaction learn the pub key of the previous sender and so on until they see a non-committed transaction, or a mined coin.

Adam

[adam3us]

@Adam:

Can you give more details about how you would encode the commitment within the existing transaction format? Or are you proposing a new format as well as new logic for dealing with it?

I dont know the bitcoin script language well enough to have a good answer for that.  Someone on the dev list did comment on that aspect:

I think what you're trying to do is *almost* possible now (ab)using BIP-0016
In the output of the previous tx you put:

OP_HASH160 [20-byte-hash-value] OP_EQUAL

and in the next tx you use a new type of input which specifies it's value but
not the output which is spent. In the input script you place:

OP_DUP OP_1ADD OP_HASH160 [20-byte-hash-value] OP_EQUALVERIFY

Then a serialized script containing the normal stuff as well as the last
transaction hash and output index would be passed around out of band and the
validating nodes would execute each script with a shared stack, beginning with
the out of band one, then the input one (the OP_EQUALVERIFY) then the output.
When the serialized sigscript reaches the bottom of the stack, having been
verified twice, it will now be evaluated as per the rules of P2SH.

None of this probably works in the real world since I'm not familiar with the
actual implementation of P2SH and it probably has quite a number of things
which will break if used this way but it is interesting to see that in theory
it is possible with little change to the protocol (just a new input format).

also:

Perhaps an extreme version of the idea is easier to understand. Ignore
DOS attacks for a moment and pretend there is never any address reuse:

Everyone creates txouts paying a P2SH addresses that have a OP_PUSH
nonce in them and tell you recipient the nonce out of band.

When the recipients spend those coins they provide the script but not the nonce.

The recipient knows what coins he's spending, but the public does not.

The public can tell there is no double spend though, because they'd
see the same script twice. The person he's paying may be skeptical
that he actually has any coin and didn't just mine some gibberish, but
our spender tells that their receiver the nonce, and that person can
see the coin available for spending in the chain and also see that
there are no double spends.

I guess the next step unless iddo finds a flaw is to write up a BIP and get help with the simplest way to integrate from people who understand the script language well.  (And learn the script language myself!)  Well maybe a short white paper describing the detail wouldnt hurt before that even as so far the detail is spread out over a few posts on this thread.

Adam

[adam3us]

(For realism of this risk, note that according to Kaminsky there already
exist multiple entities with reserve ASIC power each exceeding current
network difficulty who are holding part of their power in reserve for profit
maximisation reasons.

Could you provide any backing/proof/links to support this claim?  

It was made by Dan Kaminsky in the comments section of his wired article.  See this thread:

https://bitcointalk.org/index.php?topic=194554.msg2078882#msg2078882

And regardless of whatever solutions we put into place on the bitcoin network, if a mining group truly did have that much hashpower, couldn't they always just fork the blockchain and take all their coins/computer power over to another network where they can enforce their protocol?

My view they cant do that.  If the client accepts only blind coins, or has a switch in it that can be toggled to only do so, then the dishonest miner either has to follow the protocol and mine blind coins, or leave and form their own alt-coin without blind coins (or join an existing alt-coin without blind coins).  It might be lonely and unprofitable on that network however if there are no users who want their coins subjected to dishonest miner policy

Lots of hash power doesnt mean an alt-coin becomes popular nor profitable to mine after all.  Popularity comes from the users, and profitability from the interest of users to buy the coins.

You can consider a network with miners that reject coins based on centrally applied policy as like a file sharing network that wont let you share files that have given hashes as enforced by a few big players for whatever reason.  Presumably people wont like that and will stick to the less restricted network.

Adam

[iddo]

Going back to the commit definition (symmetric version, with defense against insider commit to junk):

(blind-sender, auth-tag, encrypted-tx-commit)

        blind-sender = SHA1( SHA256( 1, pub ) )
        auth = HMAC-SHA256-128( K, encrypted-tx-commit )
        encrypted-tx-commit = AES( K, tx-commit )
        K = SHA-256( pub )

The point of the use of K = SHA-256( pub ) is that anyone in possession of the public key can decrypt, and verify the mac.  That means direct spend-to-junk is not possible by someone without knowledge of pub.  Now of course anyone with knowledge of pub could superficially spend to junk, however as pub allows decrypt and mac check, superficial junk is fast to detect and remove, just by validating the mac.  And a more subtle spend to junk (by someone knowing pub) cant work as the coin is ignored as junk unless the MAC passes, and unless the decrypted tx contains a valid signature from pub.

Ahh, I see, in post #19 I responded to an earlier variation where you were using the OWF txcommit=SHA256(tx) rather than the reversible txcommit=AES(K,tx) with K=SHA256(pub), so with this variation if an attacker somehow obtains a pubkey then he can unblind/decommit a blind txn that's on the blockchain, but he cannot lock coins forever with junk txn data. Therefore if Alice tries to double-spend, she reveals the pubkey and then the network can fully examine the earlier blind txn and see that it's valid, and reject Alice's double-spend attempt.

I guess that the main issues are:
(1) attackers could spam the chain with blind commitments that consist of junk (random hash of supposed pubkey), and all the nodes would have to perform extra work on an ever-increasing set of blind-UTXO for verification whenever a legitimate pubkey is decommitted.
(2) as follows from (1), the txn-fees for blind commitments will probably be much higher than regular txns?
(3) if some pubkey leaks then an attacker can immediately un-blind the relevant txn. I'm not sure what are the negative implications here. If I understand correctly then you claim that it's fine to un-blind when the blind commitment is already buried under enough PoW blocks, because the recipient can create a new blind commitment that spends those coins (since the recipient hashed address that appeared in the first blind commitment will be different than the secondary e.g. SHA1(SHA256()) hash that would appear in the following blind commitment, so even if the first txn gets un-blinded and revealed as tainted, the network cannot detect that the following blind txn is linked to it) ?
(4) the extra layers of complexity for the symmetric encryption and MAC, though it's not really a big deal I suppose.

[mmeijeri]

I don't understand the proposed protocol yet, but I'm wondering why we want to include an address in the commit rather than a specific UTXO. Don't we just want to blind a single transaction? Maybe this is a stupid question, but I'm trying to understand.

[adam3us]

I don't understand the proposed protocol yet, but I'm wondering why we want to include an address in the commit rather than a specific UTXO. Don't we just want to blind a single transaction? Maybe this is a stupid question, but I'm trying to understand.

I think it maybe that it should more accurately commit an unspent transaction output and the address in control of it.  How would you identify or serialize that?

(I am taking it that balance is not on the address as such, but that each not yet spent transaction output is owned by an address, and can be spent in its entirety in a transaction?)

I think for privacy bitcoin discourages address reuse so it maybe that the difference is not much.  eg hash of transaction identifier, output number and public key (that is the basis for the address).  It is only the public key that is not already public, and something non-public has to go into the commitment.

Adam

[mmeijeri]

(I am taking it that balance is not on the address as such, but that each not yet spent transaction output is owned by an address, and can be spent in its entirety in a transaction?)

I'm not sure if I understand your question. That's indeed how it works now, except that the output is really owned by a script, not an address. In the most common case the script is unlockable by a signature corresponding to a given address, so what you said is almost correct. Or were you asking a more subtle question?

I think for privacy bitcoin discourages address reuse so it maybe that the difference is not much.  eg hash of transaction identifier, output number and public key (that is the basis for the address).  It is only the public key that is not already public, and something non-public has to go into the commitment.

Why is that non-public information needed? To disallow a subsequent unblinded double spend of the same UTXO?

[adam3us]

(I am taking it that balance is not on the address as such, but that each not yet spent transaction output is owned by an address, and can be spent in its entirety in a transaction?)

That's indeed how it works now, except that the output is really owned by a script, not an address. In the most common case the script is unlockable by a signature corresponding to a given address, so what you said is almost correct.

If there are legitimate situations where scripts do not contain an address (that is disclosed by the corresponding signature during a spend) it maybe difficult to blind those scenarios.

I think for privacy bitcoin discourages address reuse so it maybe that the difference is not much.  eg hash of transaction identifier, output number and public key (that is the basis for the address).  It is only the public key that is not already public, and something non-public has to go into the commitment.

Why is that non-public information needed? To disallow a subsequent unblinded double spend of the same UTXO?

Well if there is no non-public info (like the public key is not public even though the address which is the hash of it is public) then people can guess which transaction is hashed to form the commitment, and then they will not be effectively blind.  We want the transactions to be blind so that dishonest miners can not make taint or sender/recipient based policy decisions. 

The other key part is that the public key becomes public unavoidably as part of a non-blind spend.  Those two features are necessary seemingly to make blind commitments work and yet prevent double spending.

Adam

[mmeijeri]

Well if there is no non-public info (like the public key is not public even though the address which is the hash of it is public) then people can guess which transaction is hashed to form the commitment, and then they will not be effectively blind.  We want the transactions to be blind so that dishonest miners can not make taint or sender/recipient based policy decisions.  

How could miners guess the UTXOs, or guess the transaction that spends them, based on just the hash of that spending transaction?

[adam3us]

Well if there is no non-public info (like the public key is not public even though the address which is the hash of it is public) then people can guess which transaction is hashed to form the commitment, and then they will not be effectively blind.  We want the transactions to be blind so that dishonest miners can not make taint or sender/recipient based policy decisions.  

How could miners guess the UTXOs, or guess the transaction that spends them, based on just the hash of that spending transaction?

Well they could iterate over UTXOs and amounts looking for a permutation and amount that results in that hash.  It might take a bit of computation but if you're talking about attacks you have to consider eg 2^50 operations and such things  the miner has a lot of CPU power as it is.

If there are one-use addresses in the commitment that becomes basically impossible.

Adam

[mmeijeri]

Well they could iterate over UTXOs and amounts looking for a permutation and amount that results in that hash.

But the hash also includes the destination addresses (or scripts), which could be previously unknown, and at any rate are basically arbitrary. I don't see how guessing this is feasible.