Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-16 Thread Adam Back
On Wed, May 15, 2013 at 07:45:34PM -0700, Gregory Maxwell wrote:
[committed coins] depending on how its done, at most conceals the
transactions from people who aren't a party to them...  though as time goes
on eventually everyone becomes a party to a sufficiently old coin, and
avoiding publication creates quadratic costs in evaluating a private
clique's claims  so

I believe the coin size and verification cost is linear not quadratic, but
maybe it depends on the parameter you're measuing in.  The coin size is
linear with the number of committed (uncompacted) spends.  You can view
reveals as committed compaction.  For efficiency a recipient of a committed
coin may as well compact and spend in one transaction so no new messages are
created.

Btw I believe if one were concerned about the committed coin size, I can see
a small tweak that would keep the size of the committed coins small eg
256-bit regardless of number of spends (no longer grows), and let the block
store the encrytped  MACed commitment.  Then compaction is no longer a
concern.  However I think that is SPV - SPV client unfriendly.  (A full
client - SPV client should still be workable as the full client could
alternatively send the client the MACed data and key, rather than have him
look at it from his block history.)  (Crypto sketch below).

However I am not sure multi-spend committed coin size is really a concern
because to the extent people hold long commitments without revealing to the
network for the long term, that is a bandwidth saving to the network.

Overall about privacy it would be typically temporary, though the peers have
the technical means to react and defend themselves by using longer committed
chains if dishonest mining is detected on a significant scale.

instead an implementation would make the identities public but only once
they're burred a bit.

That was the seed idea.  The more aggressive spend lots of times in
committed form is just a technical threat that will keep dishonest mining
in check.  By definition the coin is already irrevocably spent before the
reveal (without the threat of having the dishonest miners endlessly redoing
their own deeply burried work).  The only person who could be punished by
policy by 50% dishonest miner (retroactively) is the recipient, not the
spender, and the punishment is very muted: all he can do is prevent coin
compaction.  If the committed coins are small, compact doesnt even hurt the
committed coin user, just network itself.  Therefore a dishonest miner is
wasting his time his dishonesty cant enforce his dishonest policy.

To store the commitments in the block chain replace:

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

with:

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

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

then a reveal is just to send the recipient the public key (32 bytes)
per hop, still linear but ~3x smaller.

I suggested fixed size committed coin spends, that also you can do but with
public key crypto needed probably, and so dropping to the verification
efficiency of standard transactions.  Sketch 2:

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

(pub key P = xG, G = base point)

blind-sender = cP (public key EC multiplied by constant c)
sig = ECDSA( cx, encrypted-tx-commit )
encrypted-tx-commit = AES( K, tx-commit )
K = random

as K is random, knowledge of P if stored unencrypted does not allow
committed spend-to-junk.  To reveal to a recipient just send them P and K at
each hop.  (Same K each time, anyone on the committed coin spend chain can
already chose to reveal at any time so no loss of security.)

You dont need to verify a second signature inside the tx-commit because you
already signed the encrypted-tx which binds to it (encryption with out MAC
is malleable but you cant change it at all without invalidating the
encryption).  Just need to check the input tx in the tx-commit has P as its
recipient.  P does not even need to go into tx-commit as its already bound
by cP and signature security (cant create a signature with someone elses
key).  So I think the commited coins of this form are the same size and
verification cost for the network.  And small and fixed size to spend
offline.  (32+32=64 bytes fixed).

Adam

(*) You should not as a principle re-use keys across algorithms, I omitted a
second key for simplicity.  Really K1 = SHA256( 1||pub ), K2 = SHA256(
2||pub ) encrypted-tx-commit = AES( K1, tx-commit ), auth = HMAC( K2,
encrypted-tx-committ ).  Or more simply a combined authenticated mode like
CCM or GCM and a single key managed by the mode.

--
AlienVault Unified Security Management 

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-16 Thread Adam Back
More somewhat improved crypto stuff...

On Thu, May 16, 2013 at 01:32:22PM +0200, Adam Back wrote:
I suggested fixed size committed coin spends [...]

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

(pub key P = xG, G = base point)

   blind-sender = cP (public key EC multiplied by constant c)
   sig = ECDSA( cx, encrypted-tx-commit )
   encrypted-tx-commit = AES( K, tx-commit )
   K = random

as K is random, knowledge of P if stored unencrypted does not allow
committed spend-to-junk.  To reveal to a recipient just send them P and K at
each hop.  (Same K each time, anyone on the committed coin spend chain can
already chose to reveal at any time so no loss of security.)

Actually same K every time is not so hot, as then earlier in the committed
spend chain, can force a reveal for someone later.  A clearer requirement is
that each person should only be able to reveal committed coin chains up to
the point of their direct involvement.

So that is easily fixable, just include the K for the input committed coin
in the encrypted-tx-commit, as above but:

encrypted-tx-commit = AES( K_i, K_{i-1} || tx-commit )
K_i = random

(different K for each spend).

And actually for symmetric encrypted variant the coin as specified was
already evaluatable with fixed size committed spend (of the last public key)
- I just didnt realize it in the previous mail: the input public key is
necessarily revealed when processing the decrypted tx-commit, allowing
identification and validation of the txin, and validation recursively back
to the first non-committed coin.  With symmetric verification, the
limitation is one-use coin committed addresses (and inability to remove
spend to committed junk with public validation, though there is the tx fee
as a discouragement, it does bloat a recipients verification and so maybe
frustates SPV-SPV consumption of committed coins).

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

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

Adam

ps and it would be better and clearer to read also in terms of purpose of
hashes, to use a KDF like IEEE P1363 KDF2, or PKCS#5 PBKDF2 with 1
iteration, rather than adhoc hashes for key derivation.

--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


[Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Adam Back
So in a previous mail 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 

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Peter Todd
On Wed, May 15, 2013 at 12:25:09PM +0200, Adam Back wrote:

Protocols aren't set in stone - any attacker that controls enough
hashing power to pose a 51% attack can simply demand that you use a
Bitcoin client modified to provide the attack with the full transactions
from the beginning. Any blocks containing transactions with unknown
contents will be attacked into oblivion.

On the other hand if the attacker has less than 50% of the hashing
power, they have no choice but to let other blocks through, and provided
miners are free from regulation imposed on them you can bid to get your
transactions mined with fees. Anyone using a blockchain-based
crypto-currency simply has to accept that mining is a random process and
getting a transaction confirmed is inherently unreliable.

 So in a previous mail 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.  

-- 
'peter'[:-1]@petertodd.org
01754b62829d854463fa72fe7d972a7b7d13d0c30fc86423773c


signature.asc
Description: Digital signature
--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Caleb James DeLisle
I can't see this working, if 51% of the mining power doesn't like your
coins, when you create the commitment they will reject it.
If the commitment is opaque at the time of inclusion in the block then
I will create multiple commitments and then after revealing the
commitment and spend to you I will reveal the earlier commitment which
commits the coins to an address I control.

On the topic of reversibility, I suspect in the long term the lack of
chargebacks will create issues as criminals learn that for the first
time in history, kidnap  ransom is effective. Suffice to say after the
first = $10mn kidnapping-for-bitcoin heist, governments will be forced
to decide how they view the system. It will likely fall somewhere between
arrest/question anyone identified holding tainted coins to something
nonsensical and reactionary like blocking bitcoin as Iran does TOR.

Thanks,
Caleb



On 05/15/2013 07:49 AM, Adam Back wrote:
 On Wed, May 15, 2013 at 07:19:06AM -0400, Peter Todd wrote:
 Protocols aren't set in stone - any attacker that controls enough
 hashing power to pose a 51% attack can simply demand that you use a
 Bitcoin client modified [to facilitate evaluation of his policy]
 
 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.
 
 Adam
 
 --
 AlienVault Unified Security Management (USM) platform delivers complete
 security visibility with the essential security capabilities. Easily and
 efficiently configure, manage, and operate all of your security controls
 from a single console and one unified framework. Download a free trial.
 http://p.sf.net/sfu/alienvault_d2d
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development
 


--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Adam Back
On Wed, May 15, 2013 at 08:40:59AM -0400, Caleb James DeLisle wrote:
If the commitment is opaque at the time of inclusion in the block then
I will create multiple commitments and then after revealing the
commitment and spend to you I will reveal the earlier commitment which
commits the coins to an address I control.

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:

one-spend-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.

On the topic of reversibility, I suspect in the long term the lack of
chargebacks will create issues as criminals learn that for the first
time in history, kidnap  ransom is effective. 

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

--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Caleb James DeLisle


On 05/15/2013 12:21 PM, Adam Back wrote:
 On Wed, May 15, 2013 at 08:40:59AM -0400, Caleb James DeLisle wrote:
 If the commitment is opaque at the time of inclusion in the block then
 I will create multiple commitments and then after revealing the
 commitment and spend to you I will reveal the earlier commitment which
 commits the coins to an address I control.
 
 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 ) ).


Ahh thanks for clearing that up, although it would limit the possibilities
of scripting it is silly of me not to think of it.


 
 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:
 
 one-spend-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.
 
 On the topic of reversibility, I suspect in the long term the lack of
 chargebacks will create issues as criminals learn that for the first
 time in history, kidnap  ransom is effective. 
 
 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.


That is indeed interesting. If I understand this properly Alice commits coins
to pay to Bob and gives Bob the transaction, Bob then commits to pay to Charlie
and gives him the related transaction. If Charlie wants to collect the bitcoin
he then reveals Alice's transaction and Bob's.

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

OP_HASH160 [20-byte-hash-value] OP_EQUAL

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

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

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

None of this probably works in the real world since I'm not familiar with the
actual implementation of 

Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Adam Back
btw I posted some of this thread on the dev forum:

https://bitcointalk.org/index.php?topic=206303.msg2157994#msg2157994

A related idea is occuring to me that maybe these committed transactions
could actually as a side effect make bitcoin scale slightly better by
reducing the p2p flood filled transaction size.

As I said on the forum:

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

Surely its lower bandwidth for nodes to send only committed transactions to
the p2p network, and pass committed payment chains direct to recipients.

Say committed transaction size is c (20bytes+32bytes+16bytes +header ~ 72
bytes?) And full transaction smallest size is t (txin=20bytes, amount out
4bytes, sender pub key 32bytes, recip address 20bytes, change address
20bytes, formatting 5 bytes, ECDSA signature 64bytes, script 10 byte surely
~ 175bytes)?  Thats over twice the size.  Probably average more, and it is
sent to every node.  Its always going to be lower bandwidth to send
transactions to the recipients than to send to the network, even if you have
to increase the transaction size with each respend.  The alternative is for
the entire network to see the same transaction.

I think the commitment needs to bind the two parts together eg 

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

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

Or some variantion, and you must not reuse the pub key, and must send change
if any to a different address, otherwise chain recipients or malicious
forwarders could lock your coin, by putting random junk onto the network
which would be unverifiable, and non-disclaimable - you cant prove you dont
know the preimage of some junk.  The MAC prevents it.  Maybe there's a more
compact way to do it even, but that works efficient demonstration of
security feasibility.

Other public key variants could be possible, P = xG is the ECDSA public key,
x the private key, G base point.  Sender could reveal P' = cP, c some fixed
constant (computing c from cP is ECDL problem considered oneway  hard), and
a signature by private key x' = cx over the tx-commit.  That is a publicly
auditable commitment also, but one tht can make an ECDSA signature over the
tx-commit hash, and can be revealed by revealing P later.  However that
imposes public key computation on the validation (which it already currently
does, but faster validation as above is nicer).  With that one you dont even
have to verify the transaction signature on reveal :)  You already did it,
just provide the tx that hashes to the signed hash, and P for the recipient
to verify the signature was made by cP.

Adam

--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Gregory Maxwell
On Wed, May 15, 2013 at 6:24 PM, Gavin gavinandre...@gmail.com wrote:
 Busy with pre-conference stuff, not following details of this conversation...

 ... but it sounds a lot like the guy fawkes protocol Zooko was thinking 
 about a year or so ago.

Sort of, but in a guy fawkes signature you use the commitment to hide
the preimage that proves you had authority to spend a coin.   Adam
proposes you do this in order to hide _which coin you're spending_.

This has obvious anti-DOS complications, but Adam deftly dodged my
initial attempts to shoot him down on these grounds by pointing out
that you could mix blinded and blinded inputs and have priority and
transaction fees come from only the unblinded ones.

Effectively,  it means that so long as you could convince the network
to let you spend some coins, you could also spend other ones along for
the ride and the network wouldn't know which ones those were until it
was too late for it to pretend it never saw them.

I think there are all kinds of weird economic implications to this— a
blinded payment would seem to have a different utility level to an
unblinded one: you can't use it for fees— except you can unblind it at
any time.  And the discontinuousness  (two types of inputs) and that
it would enable mining gibberish (though perhaps not data storage, if
you see my preimage solution to that) seems awkward and I think I have
to spend some time internalizing it before I can really think through
the implications.

--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Mike Hearn
Conceptually it sounds a lot like ZeroCoin (not in implementation)?

I'm not really convinced miner cartels that try to exclude transactions are
likely to be a big deal, but such schemes could I suppose be kept in a back
pocket in case one day I'm proven wrong.


On Wed, May 15, 2013 at 6:39 PM, Gregory Maxwell gmaxw...@gmail.com wrote:

 On Wed, May 15, 2013 at 6:24 PM, Gavin gavinandre...@gmail.com wrote:
  Busy with pre-conference stuff, not following details of this
 conversation...
 
  ... but it sounds a lot like the guy fawkes protocol Zooko was
 thinking about a year or so ago.

 Sort of, but in a guy fawkes signature you use the commitment to hide
 the preimage that proves you had authority to spend a coin.   Adam
 proposes you do this in order to hide _which coin you're spending_.

 This has obvious anti-DOS complications, but Adam deftly dodged my
 initial attempts to shoot him down on these grounds by pointing out
 that you could mix blinded and blinded inputs and have priority and
 transaction fees come from only the unblinded ones.

 Effectively,  it means that so long as you could convince the network
 to let you spend some coins, you could also spend other ones along for
 the ride and the network wouldn't know which ones those were until it
 was too late for it to pretend it never saw them.

 I think there are all kinds of weird economic implications to this— a
 blinded payment would seem to have a different utility level to an
 unblinded one: you can't use it for fees— except you can unblind it at
 any time.  And the discontinuousness  (two types of inputs) and that
 it would enable mining gibberish (though perhaps not data storage, if
 you see my preimage solution to that) seems awkward and I think I have
 to spend some time internalizing it before I can really think through
 the implications.


 --
 AlienVault Unified Security Management (USM) platform delivers complete
 security visibility with the essential security capabilities. Easily and
 efficiently configure, manage, and operate all of your security controls
 from a single console and one unified framework. Download a free trial.
 http://p.sf.net/sfu/alienvault_d2d
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development

--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Gregory Maxwell
On Wed, May 15, 2013 at 7:22 PM, Mike Hearn m...@plan99.net wrote:
 Conceptually it sounds a lot like ZeroCoin (not in implementation)?

Zerocoin conceals the connection from everyone forever, assuming the
underlying trapdoor problem is computational infeasible, but at great
cost.

Adamcoin, depending on how its done, at most conceals the transactions
from people who aren't a party to them... though as time goes on
eventually everyone becomes a party to a sufficiently old coin, and
avoiding publication creates quadratic costs in evaluating a private
clique's claims so instead an implementation would make the
identities public but only once they're burred a bit.

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

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

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

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

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

This could actually go on forever with no ambiguity over who owns
what, but the out of band proofs that you have to give people when you
spend coins would grow with the history of the coins.

Since there wouldn't be much privacy once a transaction was
sufficiently split up in any case, you instead just publish the
unblindings once transactions are sufficiently buried. Thus bounding
the growth of the proofs.   The reason I say I need to internalize
this more is mostly that I need to think about attacks on the
publication for 'tained' transactions being more or less isomorphic
to just refusing to allow spending of the 'tainted' coins in any case.

--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development


Re: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint unilateral revocability)

2013-05-15 Thread Caleb James DeLisle
Not only does the size of the proof grow endlessly as the coin is
passed around, the size of the UTXO set grows endlessly as more and
more of the already spent coins cannot be proven to have been spent
because the proofs are passed out-of-band. I never said the idea was
good, just interesting :)

Thanks,
Caleb


On 05/15/2013 10:45 PM, Gregory Maxwell wrote:
 On Wed, May 15, 2013 at 7:22 PM, Mike Hearn m...@plan99.net wrote:
 Conceptually it sounds a lot like ZeroCoin (not in implementation)?
 
 Zerocoin conceals the connection from everyone forever, assuming the
 underlying trapdoor problem is computational infeasible, but at great
 cost.
 
 Adamcoin, depending on how its done, at most conceals the transactions
 from people who aren't a party to them... though as time goes on
 eventually everyone becomes a party to a sufficiently old coin, and
 avoiding publication creates quadratic costs in evaluating a private
 clique's claims so instead an implementation would make the
 identities public but only once they're burred a bit.
 
 Perhaps an extreme version of the idea is easier to understand. Ignore
 DOS attacks for a moment and pretend there is never any address reuse:
 
 Everyone creates txouts paying a P2SH addresses that have a OP_PUSH
 nonce in them and tell you recipient the nonce out of band.
 
 When the recipients spend those coins they provide the script but not the 
 nonce.
 
 The recipient knows what coins he's spending, but the public does not.
 
 The public can tell there is no double spend though, because they'd
 see the same script twice. The person he's paying may be skeptical
 that he actually has any coin and didn't just mine some gibberish, but
 our spender tells that their receiver the nonce, and that person can
 see the coin available for spending in the chain and also see that
 there are no double spends.
 
 This could actually go on forever with no ambiguity over who owns
 what, but the out of band proofs that you have to give people when you
 spend coins would grow with the history of the coins.
 
 Since there wouldn't be much privacy once a transaction was
 sufficiently split up in any case, you instead just publish the
 unblindings once transactions are sufficiently buried. Thus bounding
 the growth of the proofs.   The reason I say I need to internalize
 this more is mostly that I need to think about attacks on the
 publication for 'tained' transactions being more or less isomorphic
 to just refusing to allow spending of the 'tainted' coins in any case.
 
 --
 AlienVault Unified Security Management (USM) platform delivers complete
 security visibility with the essential security capabilities. Easily and
 efficiently configure, manage, and operate all of your security controls
 from a single console and one unified framework. Download a free trial.
 http://p.sf.net/sfu/alienvault_d2d
 ___
 Bitcoin-development mailing list
 Bitcoin-development@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/bitcoin-development
 


--
AlienVault Unified Security Management (USM) platform delivers complete
security visibility with the essential security capabilities. Easily and
efficiently configure, manage, and operate all of your security controls
from a single console and one unified framework. Download a free trial.
http://p.sf.net/sfu/alienvault_d2d
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development