Bitcoin Forum

So in a previous mail

https://bitcointalk.org/index.php?topic=205533.msg2149057#msg2149057

I described a simple, extremely efficient and easy to implement symmetric
key commitment that is unlinkable until reveal time (at bottom).  I think
this can help improve the byzantine generals problem, that bitcoin only
defends to simple majority (with one vote per CPU power), and so assumes
most nodes by cpu power are honest.  With this simple protocol change you
dont need any honest nodes, just some honest clients to spend to, to have
your transaction accepted.

You can think of this in terms of a (somewhat distributed) server performing
validations, but in a way that it sufficiently blind to the details of the
validations that it can not selectively enforce a policy, it power is
limited to random DoS.

There are other situations where you can rely on a server for one property
but not another - eg a somewhat distributed encrypted backup (like Tahoe
LAFS) you rely on for availability, but not integrity nor confidentiality
(because you encrypt those, and some sharing scenarios still work.) So this
is in that class of protocols - zero-trust in server, but can extract
service and some guarantees from the (optionally distributed) server anyway.

(Bitcoin does not use known better than majority results for byzantine
generals based on fair coin toss, relying instead on simple majority and an
assumed largely unjammable network.  I notice Nick Szabo was complaining
about this on his blog and saying bitcoins majority is not even a standard
or proven byzantine voting protocol - something adhoc.  I think the bitcoin
unjammable network assumption is a false at the limit so that someone with
strong network hacking capabilities can create network splits long enough to
even overcome the network majority vote without having any compute power of
their own.  All they need is to have a split with enough power to plausibly
quickly get the victims their desired number of (split) confirmations.)

Anyway this should be a clear voting improvement, that is efficient.

Imagine a couple of big pools or ASIC miners started enforcing some
arbitrary coin policy, eg say coins must not have some taint according to
its list of black coins, or coins must be certified by some entity, be
traceable to some type of event etc.  Well call these miners/voters
"dishonest", in that they are not following the intended zero-policy
protocol.

If the coins dont match their chosen policy, the dishonest miners will
refuse to include transactions in blocks they issue.  If they see a
transaction which does not match their policy in a block by someone else
they will ignore it and try to make it into an orphan.  As they have say 75%
of the network power they can do that successfully.  Even with current
validation protocols in the clients, so the "but clients wont accept the
change" argument does not apply - the existing clients will accept the
policy change, because they cant detect it, nor prove it, and dont have the
voting power to impose honest policies.

(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.  This is a coming to fruition of the concentration of
power issue I was talking about in my first bitcoin forum post.  People who
have that kind of power in reserve have clearly invested millions of
dollars, which probably makes them more vulnerable to political influence.)
Alright so the solution.  Use the commitment protocol (below) which even
though it is symmetric key strongly hides the committed transaction public
key.  (Symmetric in the sense that the validation steps are all highly
efficient symmetric key based).  Now send the transaction (which includes
the public key) direct to the receiver, over a secure channel, or an assumed
non-eavesdropped direct channel, with no p2p flood of the transaction.  The
receiver can check the hash to the commitment, and decide how many
confirmtions he needs.  Once he has eg 6 confirmations he reveals the
commitment to the transaction (by publishing it).  The sender may also send
the reveal/transaction to the network directly himself, if the recipient is
offline.  However there is no advantage to publishing early so it seems
better to let the recipient do it when he is ready to incorporate the
payment into his wallet.

Now the powerful dishonest voters if they try to apply their policy when
they see the reveal triggers it, must redo the work of the 6-commitments
that they computed themselves.  This is like starting 6-steps behind in the
statstical gamblers ruin game that Nakamoto describes in the bitcoin
paper. Consequently even with 75%, they will find it very hard to outcompete
their own prior work, to create a 6 chain long orphan while the 25% is moving
forward on the honest chain.  Each time they see transactions which violate
their policy, they have to restart their chain recalculation again from
scratch.  Often if simple lower powered intermittent recipient sends the
coin will be burried hundreds of blocks back.  In addition 6 chain long
branches are extremely unlikely with honest payers, so clients can (and
maybe already do?) act with suspicion of they see one.


Going further, I said for best security, the recipient should never even
reveal (to the network) until he is actually about to spend, but futher he
does not even have to reveal publicly ever, he can choose to reveal only to
the recipient with a direct connection (no p2p flood fill of transaction.)
And the direct spend argument composes, ie the 2nd recipient can not do the
same thing again.  (public key A sends to public key B sends to public key
C: B publishes COM( transaction B->C ), sends the reveal of COM( transaction
A->B ), and COM transaction B->C ) to C.  C waits 6 confirmations and is
convinced.  So its the approach is composable, and in fact the network
doesnt learn the size of the transaction even, though the spend grows each
time.  Eventually presumably someone will publish will the confirmations to
the network to trim the tansaction size, though it is not strictly
necessary, and the transaction flow is small and direct (no network scaling
issues), so that it wouldnt be a huge problem to have a 1MB payment
representing 1000s of hops of network blind transactions.  (For the
composable network blind respending the commitment has to commit publicly to
both the sender and next hop recipient keys, so the network can see how long
the chain is).

Probably you can cope with multiple inputs and outputs, and maybe given even
you can work with a 100% dishonest network mining network (all the dishonest
miner can do is selectively DoS transactions if they are all network blind
except the mining), maybe the mining can even be decoupled from the voting,
as you no longer demand much from the voting process.  That admits more
interesting things like pool free direct mining, low variance hashcash
coins, probably.  Many things to think through.

I suppose the commitment could be described as a blind symmetric commitment.

Adam

Here's two of my replies to comments on the above on on the dev mailing list.


Protocol voting is a vote per user policy preference, not a CPU vote, which
is the point.  Current bitcoin protocol is vulnerable to hard to prove
arbitrary policies being imposable by a quorum of > 50% miners.  The blind
commitment proposal fixes that, so even an 99% quorum cant easily impose
policies, which leaves the weaker protocol vote attack as the remaining
avenue of attack.  That is a significant qualitative improvement.

The feasibility of protocol voting attacks is an open question, but you
might want to consider the seeming unstoppability of p2p protocols for a
hint.


Bit-commitments are based on deterministic one-way functions eg like SHA1(
SHA256( public key ) ) Obviously it has to be a different one-way function
to the coin address calculation which is RIPEMD( SHA256( public key ) ) as
that is already public.  Alternatively it can be a different serialization
using the same hash eg RIPEMD( SHA256( 1 || public key ) ).

There is only one commitment possible per public key - so you can only
create one commitment that would validate to a receiver, or to the
network. The network checks that there are no non-blind double spends
of committed
coins which it can do as spends require disclosure of the public key, which
allows existing commitments to be verified, and it similarly qchecks that
there are no blind double-commitments.

Each committed coin would be:

commit = Com( spender pub ), Com( transaction )

where Com is implemented as the above hash.  The network just places the
commitments in order as with conventional transactions.

The committed coins are not linkable to your non-blind coin because you did
not reveal your public key in the (largely passive) act of receiving to a
coin address.


The temporary unlinkability (until commitment reveal) is a necessary side
effect, not a cryptographic anonymity feature like zerocoin.  The
transactions are identical to bitcoins once revealed.  How long the
committed transaction chains can be between reveals is an implementation
choice could be 1 hop, or as long as you like.  (Actually it appears to be
up to the individual users how long the maximum chain they accept is - the
network itself, though ordering the committed spends (if there are multiple
spends on the same key) cant even tell how long the commitment payment
chains are).

Obviously the first coins in the network ordered committed coins on the same
key up to the coin value are spends as verified by the recipient, the rest
are double-spend and ignored.  If someone wants to waste fees by sending
more spends than there inputs thats up to them.

Probably the typical user doesnt care about long committed chains  other
than their wallet will bloat if the chains are too long, so probably they
would periodically compact it by revealing the long chains.  Committed coins
are probably a bit less SPV client friendly, though with correct formatting
in the merkle trees between blocks, probably a committed coin holder can
provide enough proof to an SPV client to verify even multi-spend committed
coins directly (without a network feed).

About privacy, up to the entire commitment chain can be opened at any time
(to other people or to the bitcoin network in general) with the cooperation
of any user on the chain (up to the point they saw it), so while the blind
commitment protocol is not vulnerable to a > 50% power quorum unilaterally
imposed policy (without even needing client updates), it is fully dependent
on the good will of the recipients for its temporary unlinkability.  Thats
the point: it puts policy control in the users hands not in the > 50% power
quorum.

If you want cryptographic anonymity its better to look to zerocoin.  You may
have noticed zero coin talked about optional fraud tracing.  Its usually
trivial to add tracing to an otherwise privay preserving protocol.

The blind commitment if implemented as described (and its not obvious how to
get more privacy from it) offers somewhat like community policing.  Users on
the chain can still themselves do fraud tracing, or any policy they choose,
on any blind committed coins that they receive.  If they dont like the
colour of them they can refund them.  The point is to enforce that this is a
free uncoerced community choice, by individual end users, not a > 50% cpu
power quorum choice surreptitiously imposed.

Adam

Or, you could just always pay to a _new_ address as the system was intended and specified and you achieve the same effect with no overhead, unless you propose to blind inputs and then miners cannot check _validity_, thus opening up tons of attacks.

Paying to a new address doesnt protect you from arbitrary policies being imposed by fiat by big miners based on the coin source or taint.  I described the example policies which users may find unsatisfactory but be powerless to robustly detect nor prevent with current protocols.  This is a solution to that "(cpu) might makes right" current problem.

The inputs are blinded (revealing SHA1( SHA256( public key ) ) and that does not associate with the public key hashed in the input transaction, until the commit is revealed.  There are no attacks because miners can check the validity because when a normal transaction is made the public key is revealed and can be verified against the committed key.  If multiple committed spends are made, the network just serves to order them.  How many of them are needed to add up to the input amount is verified by the recipient.  It is the spenders job to provide the revealed commitment (the committed transaction) to allow them to verify.  When the commitment is revealed back to the network, eg after 6-blocks, or when the recipient spends, or after a few commitment based spends, the network itself can do the value based validation also.  I dont see any attacks.

Adam

Why wouldn't the big miners cartel still be able to impose their greedy/malicious policies and deny your transaction, simply by refusing to put the commitment that you reveal in the blocks that they generate (and they'd reject blocks that others generate if your commitment is included). Do you mean that the commitments don't reside inside the blockchain and therefore there isn't any need to do PoW computation on them? If so, where would the commitments reside? If you don't see any attacks then you're highly optimistic.

The commitment is blind - the miner, nor anyone else other than the spender can tell which input the committed (blind) transaction relates to, nor who the sender is, nor who the recipient is, nor the amount.  When there is no information miners cant apply a selective policy - all they can do is random DoS which loses them fees.  If this is part of the protocol, which I argue it should be, and all payments happen this way they have no choice - they either have to play honestly or fork the protocol.  (Go form an alt-coin with a revised protocol, otherwise network continues without them.)

So the blind commitment goes into the block chain.  It sits there until the recipient discloses it, which will be after 6-blocks, or longer if they wait until they come to re-spend it, or maybe never even, because they can re-spend coins in committed form equally well.  If the recipient chooses to reveal the commitment (send the committed transaction) to the network, the network can either include it in later blocks or not.  If they do not, it does not alter the validity and irrevocability of the transaction, as the recipient can still re-spend committed transactions in the same way.  The only motive to even reveal commitments to the block chain is to compact your wallet (otherwise you have to keep the committed transaction chain as coins grow on each committed coin spend, you have to reveal the whole transaction history to the next recipient so they can check it relative to the commitments on the block chain for double spending).

Note committed transactions are more compact than regular transactions - they are just two hashes, so they reduce network bandwidth and make bitcoin more scalable to the extent that transaction reveals stay off network.  (As well as more secure against centralization policy risks).


The commitments do reside on the block chain, but they are blind.  So no selective policy can be applied to them.

The point is the transaction once revealed is already done in the eyes of the recipient, and everyone else, including the miner cartel.  You dont even need to reveal it to the network, thats just optional committed coin transaction chain compaction.

The only way for the cartel to undo a subsequently revealed committed transaction it is to redo all the work that piled on top of the commitment (which the cartel did the bulk of themselves!).  That might be 6-blocks or 100-blocks or 1000-blocks (a week).  Even if a cartel with 75% of the network power tried to do that its difficult.  In the time they compute a fresh 6-blocks, the rest of the network has 2-more blocks.  Also each time a new committed transaction is revealed that they wish to remove, they have to redo the work from scratch starting another chain fork.  I think it becomes hopeless for them fast, someone can commit a few hundred part payments, and reveal one every time the mining pool gets near 6-block chain fork.  The miners earn no new fees for this work.  I think its game over - they can be trivially made to fight their own compute power perpetually and unprofitably.  Users would become suspicious if a 6-block or 8-block fork formed, they may just reject it outright, or investigate manually to observe that whats going on is some revealed coins are deleted, and whats common about the coins.

A user who was concerned could wait thousands of blocks before revealing, or simply live perpetually with a bigger coin (eg a year, you can still re-spend it in its committed form).  Having to frequently fork a year of block work is untenable as a way to impose a policy.  The threat is minimal at this point, and the effort to revoke transactions herculean and un-winnable at volume.

Adam

Suppose Alice has some (e.g. tainted) coins and she wishes to buy a product from Bob, so she sends her txn as blind input to Bob's address. If Bob sends her the product before he decommits, then Alice could double-spend that input by broadcasting a non-blind regular txn and the network would respect Alice's secondary txn and reject future attempts by Bob to decommit and spend those coins, because the network would see Alice's secondary txn while the commitment that Bob possessed was still blind, right? On the other hand, if Bob wishes to decommit and spend the coins before sending the product to Alice, then the big miners cartel can decide whether it fits their policies, and reject Bob's attempts if they'd like. Therefore Bob won't accept Alice's tainted coins in the first place, and we fail to achieve your objective because the big miners cartel still has control?

Right. Now I, GriefferMcEndYourCoin, produce 100 terabytes a second of junk commitment transactions with blinded inputs for you to mine.

Because they're blinded you cannot distinguish them from valid spends of existing coins, so you include them in the chain. (and if you can, then you can impose policy).

No because an attempt to pre-spend a committed transaction, via a normal transaction, can be validated against committed transactions.  That is because a normal transaction necessarily includes the address public key, for validation of the ECDSA signature on the transaction.  Then the network can see that the hash of the public key has already been spent via an earlier commitment and so the pre-spend attempt is rejected.


As soon as the commit has reached 6-blocks the coin is spent, whether or not its revealed publicly.  That is because a recipient can spend it in committed form via a second commitment (with the address he received it with).  If Bob uses the same commit protocol with Carol, he can send her both the committed tx he received from Alice, and his own new committed tx.

Revealing the commitment to the network at all, ever is just to compact the committed coin size which grows with each committed spend. 

So even if or when the transaction is revealed to the network, the dishonest mining cartel has a choice: either ignore the compaction request (which doesnt stop it, just delays the owners attempt to compact his coin... eventually another mine will accept it),  or he can include it (desired outcome), or finally and very difficult the dishonest miner has to recompute the chain and create a fork back to the initial commitment which is at this point likely some weeks under.  That seems quite impractical and people can play games with the dishonest miner to waste all his compute fighting his own power by revealing fresh policy bait coins frequently enough that the dishonest miner never completes a fork.  He has to restart the fork attempt from the oldest coin depth each time!

You might think the coin growing each time is bad, but actually its saving the network bandwidth.  Consider if you are able to compact your coin, by having he miners accept it, all full  nodes in the network must receive it and process it.  If you spend it in committed fashion only the new commitment goes to the network, the payment happens direct between nodes.  Note the commitment is 2-3x smaller than an actual transaction.

Adam

The committed transactions have to include fees (in the clear outside of he commitment), like normal transactions, then if you do that the miners get rich and you get poor.

Clearly the spender needs to use coins that he thinks the miners are not going to have a policy against for his fees.

(Ideally we would have direct mineable shares, so that fees could be low enough you can mine them on your GPU without linking, and have them earn direct reward.  However that is a different topic.)

Adam

All of them have either the problem of quadratic scaling or not being able to tolerate parties entering or leaving the process, or both. As soon as you have asynchronous processing can tolerate new parties being added the concept of beyond majority security starts becoming nonsensical: If most of the users say consensus X is right, and a minority says Y and your protocol could ever choose Y then it permits a _minority_ attack.

The Bitcoin consensus algorithim's properties are intuitively clear, but if you prefer a more a more formal description one is available (https://socrates1024.s3.amazonaws.com/consensus.pdf).

Interesting notion that you'd mix blinded and unbinded inputs in order to create atomic transactions which still resists the most trivial DOS attacks.... but at the same time it seems a bit ugly: you'd effectively have two kinds of currency with different values, and policy could still be imposed by simply only mining coins which you've seen completely unblinded.  I'll have to digest that for a bit, but its interesting.

complicated scalability challenges there... and I don't really know that this helps: as you point out, a super-majority cabal can reject blocks. So I really do think thats totally orthogonal to policy behavior.

You wrote that the blind commitment is H(input-pub)H(transaction), what does that mean exactly? If the network can see Alice's hashed address just by looking at H(input-pub)H(transaction) before it's decommitted, then how is it blind? Meaning that if the regular hashed address of Alice was blacklisted as tainted, the network would see it and wouldn't allow Alice to spend her coins, with or without a blind commitment, no?

It was too abbreviated there.  The more accurate version was in a later post in this thread:


The idea is to use a different, but also one-way hash. Which can be the same hash function with a fixed prefix concatenated to make it different eg string "1" ( eg 1||public key ).  Then even though you see H( pub-key ) you cant compute H( 1||pub-key ) without computing the hash preimage which is hard.  And the coin address is just H( pub )  (actually RIPEMD160( SHA256( pub ) )) so you dont know pub until someone spends the coin either conventional transaction or committed transaction.  In both cases you can then verify double spend against normal transactions and committed transactions.

Also on the dev list I thought of and fixed a minor insider attack so it really needs to include also a MAC of the tx-commit value or someone can create fake committed transactions that look like you made, but you cant disprove (because you cant compute the hash preimage on junk).  The MAC allows you to believably disavow them because their MAC will be wrong.


And it looks like I forgot to define K = SHA-256( pub ).

Also I suggested a public key variant, however the above is faster to verify for validators.


Adam

As an aside: You should take care to not assume any specific signature mechanism. Bitcoin outputs are specified by 'script' and are signed by 'script'. The underlying asymmetric techniques used in script are flexible and can be replaced in a forward compatible way in the future. There are no assumptions about ECDSA anywhere in the blockchain protocol, except that our two existing CHECKSIG opcodes implement ECDSA over a particular curve right now. Baking in an assumption about ECDSA into how the blockchain works would be a major step backwards in terms of generality... and any better-bitcoin stuff should avoid doing so.

The thing is you cant use blinded transactions for fees, because you dont know who the miner will be and the recipient needs to see the revealed transaction.  That could be fixable, but also you cant tell the value of a blinded transaction (nor validate the value even if it were public in the format) unless you're a party to the transaction.  Otherwise I would have liked to say you can use blinded fees also.


I think the solution is to change the protocol pre-emptively so only blind coins are valid, other than for reward.  Then if dishonest miners block all transactions, they are not participating in the network, they are just DoSing it for no reward, expending massive amounts of compute and forgone profit, just to jam all transactions by releasing a chain of no-transaction blocks (or dummy transactions to self).  If that were their aim they might just more cheaply and effectively DDoS nodes. 

Non-blind for reward only should be client enforceable eg require pay from address to same address with balance to fee. If clients reject and dont forward non-blind transactions which try to abuse fee for payment, the miner cant do anything other than DoS the network.  Note the miner can already do that to the current network (someone with money to burn, >50% of network and no concern for profit or loss relating to his hardware can do a lot of damage).


I just meant that a hypothetical direct-mined share (if we could somehow figure out how to make them scale) is a low value reward coin so it has no input and no taint by definition as it has no input and no history.  Its completely anonymous and so not subjectable to policy.  Also as fees are low in relation to payments, it should be cheap enough that you could mine it yourself on demand on GPU or maybe even CPU.

Adam

So if a maclicious attacker somehow managed to obtain some pubkey pk0 of Alice, he could compute H(pk0)=SHA1(SHA256(pk0)) and create a blind commitment txn H(pk0)H(junk) and lock Alice's coins forever, because as you said here the network will detect and respect the SHA1(SHA256(pk0)) hash when Alice reveals pk0 as she attempts to spend her coins. In terms of security this will be a total disaster, because the pubkeys are stored unencrypted in walllet.dat

Actually (public) commit to junk was an attack that I fixed with this modification:


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 I mentioned:


and there x is already protected in the wallet.  However gmaxwell has a valid point that one cannot assume ECDSA because the CHECKSIG script action is generalized, pluggable and upgradeable.  And analogs of that particular trick may not be available for other signature schemes.  I guess that rather means that this blind coin has to involve a new script operation that provides the semantics which can then be implemented in a given way, and potentially themselves be upgraded.

Adam

I don't see how you fixed anything in the context that I described. 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. 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) ? If when just the pubkey is exposed the network could somehow detect the difference between Alice's H(pubkey)H(txn) and the attacker's H(pubkey)H(whatever), then this isn't blind, in the sense that the pubkey is enough to un-blind it, which shouldn't be the case.

As far as I can see, if Alice wishes to buy a product from Bob in exchange for her tainted coins, then either the coins will be worthless to Bob because the network will reject Bob's attempts to decommit and spend those coins, or Alice can double-spend her (non-tainted) coins after receiving the product from Bob, or the network will prevent Alice from spending her tainted coins in the first place. If I'm wrong, please elaborate with exact details of your protocol on how the exchange of tainted coins for the product would work?

correct.

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).


The point is the coins are already spent by the time of the decommit, because Bob can opt to spend them in committed form, and they are confirmed (eg left for 6-blocks of confirmation before decommitting).


Note the coin address of the recipient is all that is seen before the commit by the network.  The coin address is

addr = RIPEMD-160( SHA-256( pub key )

that does not allow the network to calculate the committed value which is commit = SHA1( SHA-256( pub key ) ) because you cant do that without inverting the hash, which is hard to do.
Therefore the network (and anyone) can not correlate txout coin addresses with committed spends until the reveal (or a double spend).

However on a normal transaction spending from the address, the spenders actual pub key is revealed in order for the ECDSA signature to be verified as part of the existing bitcoin transaction format.  Because of that at that point, the committment (of txin pub key) can be reproduced by the network, and validated against both double spending, and committed double spending.


So as I said Bob could spend in committed form and so could Carol, Dave etc indefinitely. 

However if Bob decommits and a dishonest miner does not include the decommit, by doing that he has still not revealed his public key (only his coin address).  Consequently he can react to the dishonest miner and still spend his coin in committed form.  However he should probably wait until the decommit is accepted and confirmed in the block chain by some number of blocks (eg 6) until spending because by spending he reveals his public key, and loses the ability to spend in committed form because as soon as his public key is known to the dishonest miner, the miner can recognize the committed form payment.

Part of Bobs reason to commit is to compact his coin.  I suggested another variant on the bitcoin dev list in response to other comments which keeps the committed coin at 64 bytes, however many times it is respent in committed form.  In this way it is simpler for Bob and everyone else to just keep respending the coin in committed form indefinitely.  There maybe SPV costs associated with that however .


Adam

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.

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


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


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.


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

Adam

@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?

Hello Adam,

The plan is actually to move in the opposite direction soon (link (https://bitcointalk.org/index.php?topic=19137.msg2119935#msg2119935)), 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.


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?

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?

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.)


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

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.


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

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


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?

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.

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


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.


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.


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).


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.


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.


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

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:


also:


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

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


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

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.

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

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?


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

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.


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

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

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

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

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

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?

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.


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.


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.


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.


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

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.

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.

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.


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

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

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

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

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

Followiing.

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