Pages:
Author

Topic: blind symmetric commitment for stronger byzantine voting resilience (Read 12256 times)

sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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)

[...] validations a) and b) are still validatable by miners even though the coins are committed.

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

It was described how that works somewhere in this thread.  The short version is that the commitment contains SHA1(SHA256(public-key)) and a normal address is a different hash addr=RIPEMD160(SHA256(public-key)) and any public (non-committed) transaction reveals the public key (because that is necessary to validate signatures, and transactions contain a signature from the address public key), then if a public spend is done anyone can calculate the commitment based on the public key.

If another committed transaction is made RIPEMD160(SHA256(public-key)) is reused.

The actual details are a bit more complicated to prevent various attacks and corner cases but the above explains why you could prevent double spending of something you cant even correlate unless it is double-spent.

Adam
sr. member
Activity: 294
Merit: 250
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.
legendary
Activity: 3920
Merit: 2349
Eadem mutata resurgo
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
sr. member
Activity: 294
Merit: 250

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?
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
hero member
Activity: 714
Merit: 500
Martijn Meijering
Don't you still need to validate enough to be able to collect the fees and stop spammers?
sr. member
Activity: 404
Merit: 362
in bitcoin we trust

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
sr. member
Activity: 294
Merit: 250

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?
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
hero member
Activity: 714
Merit: 500
Martijn Meijering
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.
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
hero member
Activity: 714
Merit: 500
Martijn Meijering
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.
hero member
Activity: 714
Merit: 500
Martijn Meijering
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.
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
hero member
Activity: 714
Merit: 500
Martijn Meijering
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?
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
hero member
Activity: 714
Merit: 500
Martijn Meijering
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?
sr. member
Activity: 404
Merit: 362
in bitcoin we trust
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
hero member
Activity: 714
Merit: 500
Martijn Meijering
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?
Pages:
Jump to: