blind symmetric commitment for stronger byzantine voting resilience

[adam3us]

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.

If the destination address is re-used that might be guessable, but people are discouraged from re-using addresses. 

I am not sure about scripts - I suppose scripts contain addresses or they become insecure also so the same applies?

Adam

[1715157445]

1715157445

[1715157445]

1715157445

[mmeijeri]

I'm not against including addresses, I'm just trying to figure out if they are necessary, and if so, why. Suppose I hold a bunch of BTC and when I check with blockchain.info I see that they are tainted. Let's say that 30% of it indirectly came from the Mt Gox heist and I'm worried that the forces of evil will try to censor future transactions I might want to make with those coins. Let's say I gather all UTXOs in my wallet, both tainted and untainted, and divide them into a set of convenient denominations in a single transaction. Before I send the transaction, I commit to the hash of this transaction. Are you saying the bad guys could guess that my transaction, once unblinded, will reveal itself as involving tainted coins?

[adam3us]

I'm not against including addresses, I'm just trying to figure out if they are necessary, and if so, why. Suppose I hold a bunch of BTC and when I check with blockchain.info I see that they are tainted. Let's say that 30% of it indirectly came from the Mt Gox heist and I'm worried that the forces of evil will try to censor future transactions I might want to make with those coins. Let's say I gather all UTXOs in my wallet, both tainted and untainted, and divide them into a set of convenient denominations in a single transaction. Before I send the transaction, I commit to the hash of this transaction. Are you saying the bad guys could guess that my transaction, once unblinded, will reveal itself as involving tainted coins?

Well I am saying the dishonest miners must not be able to guess with good confidence that the transaction involves tainted coins or other information like who is paying or receiving, or they can reject them even though they are blinded, ie if that happens the blinding was ineffective.

About necessity of using addresses & public keys: one clear requirement is that double spending must be prevented, and the way that works is that if you double spend a non-blind version of an unspent output then a signature is provided to prove ownership of the output.  And a signature always includes the public key to allow the signature to be verified.  The public key was previously unknown (before spending) and so could serve as a blinding factor

So the main trick is that if the public key is used as the only non-public blinding factor, then double spending in non-blind form will unblind and expose double spend attempts.

We cant use eg the recipients address in as the blinding-factor because we want one recipient to be able to tell that the sender tried to double spend an output with another recipient.  If the recipient doesnt know the other recipients address, he would be unable to detect double-spending.

So the commitment looks like

(com1,com2) = SHA1( SHA256( pub ) ), AES-CCM( key, transaction )

where key = SHA256( pub ).

There has to be separate blinding per unspent output used because the UTXOs could be double-spent separately.  So a blind transaction could include a list of blind commitments and a plaintext fee to pay for the processing of the blind transaction.  The fee should be extremely taint free.  The fee may optionally be paid by the recipient.

Adam

[mmeijeri]

Is the intended behaviour of a blind commit followed by a conflicting unblinded transaction that the latter should be rejected as a double spend? I can see why you would want this if you want to chain blinded transactions off the block chain as you described previously, but wouldn't it be useful already if the reveal of the first transaction were rejected instead? That by itself would thwart censorship by miners, wouldn't it?

[adam3us]

Is the intended behaviour of a blind commit followed by a conflicting unblinded transaction that the latter should be rejected as a double spend? I can see why you would want this if you want to chain blinded transactions off the block chain as you described previously, but wouldn't it be useful already if the reveal of the first transaction were rejected instead? That by itself would thwart censorship by miners, wouldn't it?

I tried to retain the existing bitcoin semantic that first spend is valid, later double-spends are invalid and rejected (whether the spend is blind or non-blind).

I think what you said was that it could be possible to have unblind transactions take priority over blind transactions.  You could define it that way but it might create problems I think.  Eg say you accept  a blind transaction after one confirmation then you pay it to someone else.  But the second block has a double-spend with a non-blind transaction in it.  Now according to the one block confirmation view the blind transaction is valid, but according to the two block confirmation view the non-blind transaction is valid (and the blind one invalid).  What if you try to spend it with someone who expects two block confirmations, and goes and looks and sees that according to that definition the blind coin should be rejected?

Its somewhat but not quite analogous with the confirmations required in bitcoin now, because those can only be undone by orphans which are expected to be increasingly rare (longer orphan chain is increasingly less likely) or require a lot of resources by a dishonest entity to create.

Conversely revealing a non-blind transaction has no cost and can be done at any time for no cost by the original owner.  Maybe it has no effect if it happens after a given number of confirmations.  eg if everyone agreed that six confirmations were always required, then it could work, as the recipient can just check that there are no overriding non-blind transactions during the six blocks that came after the blind transaction.  So I think the problem is if people have differing preferences for how many blocks of confirmation they require (of no double-spend event happening) then one type of transaction (non-blind) overriding another type of transaction (blind) becomes a problem.

Adam

[mmeijeri]

Yeah, I was thinking about not making any promises about transactions conducted off the block chain. But on reflection even that probably doesn't work, because while you have succeeded in getting the hash into the block chain, dishonest miners can still keep the revealing transaction off. Maybe there is a way to signal that a transaction has been censored, and then blocking validation until a block that includes the revealing transaction is found, but I haven't been able to think of one.

But then I wonder how your solution actually prevents miners from censoring revealing transactions. In part it is because people will accept peer to peer off-chain revealing transactions provided they have seen the commitment in the block chain. But what if dishonest miners still reject these revealing transactions when they're published eventually, rewriting recent history for those blocks produced by honest miners that contain them? Wallets would become longer and longer. Wouldn't this eventually become impractical?

[adam3us]

I wonder how your solution actually prevents miners from censoring revealing transactions. In part it is because people will accept peer to peer off-chain revealing transactions provided they have seen the commitment in the block chain.

Yes, I think censoring transaction reveals matters less because the transaction has actually already completed in blind form, and can continue to be spent in blind form.

But what if dishonest miners still reject these revealing transactions when they're published eventually, rewriting recent history for those blocks produced by honest miners that contain them?

If the dishonest miners have a lot more power than honest miners so that they could forcibly make any acceptance of honest reveals into orphans yes.  Though payments can continue.

Also I notice that there is no actual need for mining of reveals, they were already mined in blind form.  They can simply be made available p2p for download by user clients.  They can easily be verified as correct with out need for high hashing power confirmations, the only validation needed is that they hash to a previous blind commit in the block chain.

Wallets would become longer and longer. Wouldn't this eventually become impractical?

I think the wallet storage for a blind transaction even after a long chain is simply the set of public keys for the addresses in the last hop unspent output set.  That is because you can validate a blind coin by iterating backwards if you have the last hop public keys, you can decrypt the commitment.  Then you see the public key of the previous hop, so you fetch the previous committed transaction, decrypt it and get keys for next hop etc until you reach a mined coin or a non-blind transaction.  So the wallet itself doesnt really grow. 

The validation procedure becomes longer and eventually the privacy eroded if many users are party to it (each user only has visibility of the transactions before, not after; but a user being the last hop in a long chain sees a lot of history).  No worse than now, just not helping privacy that much long term.

Yeah, I was thinking about not making any promises about transactions conducted off the block chain. But on reflection even that probably doesn't work, because while you have succeeded in getting the hash into the block chain, dishonest miners can still keep the revealing transaction off.

I think the answer maybe above, to not require reveals to be hashed a second time into the block. 
Just have peers make them available for download, there is no DoS as they can be validated back to their hash which is already cemented into the block chain in blind form.  If no mining is required on reveals, then there is no need to trust miners to process them.  And users can reveal at their convenience without the need for cooperation from miners.

Maybe there is a way to signal that a transaction has been censored, and then blocking validation until a block that includes the revealing transaction is found, but I haven't been able to think of one.

Its hard to allocate blame.  The dishonest miner may say it is the revealer that dropped the connection part way through and so falsely claim he never received it.

Adam

[mmeijeri]

Interesting. We could do this for all transactions, and keep only transaction hashes in the block chain. The availibility of individual transactions doesn't have to be less than in block form, does it? Only the fees would need to stay in the block chain itself.

[mmeijeri]

Hmm, come to think of it, not even the fees need to be in the block, as long as the miner has seen the actual transactions.

[adam3us]

Interesting. We could do this for all transactions, and keep only transaction hashes in the block chain. The availibility of individual transactions doesn't have to be less than in block form, does it? Only the fees would need to stay in the block chain itself.

It seems at that point that all the block chain and miners are doing is helping users order transactions that it doesnt know much about.

come to think of it, not even the fees need to be in the block, as long as the miner has seen the actual transactions.

Well thats true, however anyone can be a miner, so all full clients need the fee information, and the fee is used in the broadcast to prevent flooding/spamming, so probably the information that is broadcast needs to carry its own fee information.  It would not however have to go into the block, that is just to prevent spamming.

It does seem to be true that not much needs to go into the block (eg just the blind commitment in a merkle tree) and when you're validating information about a specific payment it is just a few small pieces of info that you need, not a whole block worth of validatable information.  For commitments it seems that its better not to require reveals go in the block as then there is no conflict with miners trying to exclude them.

Adam

[mmeijeri]

So, if ordering is all the miners are doing, then validation isn't even necessary, because individual clients could do it. Double spends could silently bounce, as I understand they do in the Ripple ledger. I hadn't thought about flooding / spamming, which is an important point.

[adam3us]

So, if ordering is all the miners are doing, then validation isn't even necessary, because individual clients could do it. Double spends could silently bounce, as I understand they do in the Ripple ledger. I hadn't thought about flooding / spamming, which is an important point.

One issue I was noticing with committed coins is you cant send to someone who is offline as you need to direct-send them the decommittment.

Here's  a way to fix that while retaining compact addresses.  The address public key becomes no longer secret and not used for direct receiving, rather for self-signing further sub-keys only.  Then an encryption (public) sub-key can be signed with the address public key.  And a separate receive sub-address = H( receive-pub-key ) relating to corresponding (unpublished) receiv sub-pub-key. 
The self-signed set of sub-keys is broadcast and available for download from all peers, keyed by address (hash of public key). 

(This is quite analogous to looking up someone's PGP/GPG key based on fingerprint, where a PGP key includes a top-level DSA key and then one or more sub-keys for Elgamal etc.)

So in that way you still keep the compact address, and the sender can lookup:

pub-key, sig( enc-pub-key, receive-addr )

keyed by addr = H( pub-key )

Then blind committed transactions become:

receive-addr, PKE( enc-pub-key, sender-receive-pub-key ),
H( sender-receive-pub-key), E( sender-receive-pub-key, transaction )

PKE is public key encrypt, E is authenticated symmetric cipher mode.

probably could be optimized in some ways, but a proof of concept.  The
recipient is identified, which is a loss, but optionally can be fixed with
stego, at some cost; and recipient can and is encouraged to create new
recipient addresses is another defense.


Probably you could reuse the sig pub key as an encryption pub key, but as a
design principle that adds risk.

Both committed and non-committed transactions would have to use the receive-addr.

The mechanism of self-signed sub-keys could allow self-certified identity (eg put your email address as one of the attributes), and could allow you to change your receive-address, or update a set of receive addresses gradually without changing your identity and base address.

Adam

[solracx]

It seems at that point that all the block chain and miners are doing is helping users order transactions that it doesnt know much about.

In Bitcoin the miners are responsible for creating the block and therefore ensuring the transaction inputs and outputs all balance out and performing other validation checks prior to inclusion into a block.   Are you saying that there are no validation checks for a transaction to be included in a block?

[adam3us]

It seems at that point that all the block chain and miners are doing is helping users order transactions that it doesnt know much about.

In Bitcoin the miners are responsible for creating the block and therefore ensuring the transaction inputs and outputs all balance out and performing other validation checks prior to inclusion into a block.   Are you saying that there are no validation checks for a transaction to be included in a block?

I am saying it is possible to leave the validation to the transacting parties.  The spender just reveals the input transactions to the recipient, the recipient checks the validation and that the transactions are on the block chain (in hashed form) accepts or not accordingly as usual.

You shouldnt ideally be relying on a few powerful miners to do validation anyway if the miner is dishonest or more likely hacked you can accept fictitious bitcoins that weren't mined.  SPV clients do rely on this because they dont have enough bandwidth.

You can decommit the hashed coins to help SPV clients as then most transactions can be validate by the miners (all the old decommitted ones).  The only coins that cannot be miner validated are the ones that have not yet been decommitted.  (How many times user respend in committed form without decommitting is up to them, though such coins are a bit less SPV friendly.)

Adam

[mmeijeri]

Don't you still need to validate enough to be able to collect the fees and stop spammers?

[adam3us]

Don't you still need to validate enough to be able to collect the fees and stop spammers?

Yes the miners need to validate for double-spends and collect the anti-spam related fees that are not hashed/not encrypted (in the clear on the outside).

Adam

[solracx]

It seems at that point that all the block chain and miners are doing is helping users order transactions that it doesnt know much about.

In Bitcoin the miners are responsible for creating the block and therefore ensuring the transaction inputs and outputs all balance out and performing other validation checks prior to inclusion into a block.   Are you saying that there are no validation checks for a transaction to be included in a block?

I am saying it is possible to leave the validation to the transacting parties.  The spender just reveals the input transactions to the recipient, the recipient checks the validation and that the transactions are on the block chain (in hashed form) accepts or not accordingly as usual.

You shouldnt ideally be relying on a few powerful miners to do validation anyway if the miner is dishonest or more likely hacked you can accept fictitious bitcoins that weren't mined.  SPV clients do rely on this because they dont have enough bandwidth.

You can decommit the hashed coins to help SPV clients as then most transactions can be validate by the miners (all the old decommitted ones).  The only coins that cannot be miner validated are the ones that have not yet been decommitted.  (How many times user respend in committed form without decommitting is up to them, though such coins are a bit less SPV friendly.)

Adam

As I understand it, miners validate each other's work in the bitcoin network.  So even if a powerful miner builds the block, other miners verify the block after creation.   So in your scenario, how do the miners keep a check on each other?  That is, if there is nothing to validate, what then do they check to see if nobody is attacking the network?

[adam3us]

As I understand it, miners validate each other's work in the bitcoin network.  So even if a powerful miner builds the block, other miners verify the block after creation.   So in your scenario, how do the miners keep a check on each other?  That is, if there is nothing to validate, what then do they check to see if nobody is attacking the network?

miners validate 3 things about other miners work:

a) that previous coins have the correct difficulty at the time of mining
b) that none of the transactions are double spends of previous transactions
c) that the input values are >= the output values (input > output means balance is fees)

with committed coins the last validation c) is delayed until the coin is decommitted (which could be 6 blocks later, or years later, after 0-follow-on transactions or 100s of follow-on transactions).  However the recipients receive the decommitment for all committed coins and so can validate it immediately for themselves in order to know whether they should accept.  Thats a bit more complicated for SPV clients, as they also need to see the committed coin decommitments which requires a bit more network activity and computation.

The other two validations a) and b) are still validatable by miners even though the coins are committed.

Adam

[marcus_of_augustus]

Followiing.

[solracx]

As I understand it, miners validate each other's work in the bitcoin network.  So even if a powerful miner builds the block, other miners verify the block after creation.   So in your scenario, how do the miners keep a check on each other?  That is, if there is nothing to validate, what then do they check to see if nobody is attacking the network?

miners validate 3 things about other miners work:

a) that previous coins have the correct difficulty at the time of mining
b) that none of the transactions are double spends of previous transactions
c) that the input values are >= the output values (input > output means balance is fees)

with committed coins the last validation c) is delayed until the coin is decommitted (which could be 6 blocks later, or years later, after 0-follow-on transactions or 100s of follow-on transactions).  However the recipients receive the decommitment for all committed coins and so can validate it immediately for themselves in order to know whether they should accept.  Thats a bit more complicated for SPV clients, as they also need to see the committed coin decommitments which requires a bit more network activity and computation.

The other two validations a) and b) are still validatable by miners even though the coins are committed.

Adam

Not clear to me how you can do (b) when you can't see the input and output values.