BitcoinTalk

Not a suggestion

174
Satoshi-only
BitcoinTalk
#1
From:
Red
Subject:
Not a suggestion
Date:
As some might have noticed, one of the things that bugs me about bitcoin is that the entire history of transactions is completely public. I totally understand the benefits of how this simplifies things and makes it easy for everyone to prove coins are valid.

So this is not a suggestion for a change to bitcoin. Rather it is a question about what could be possible, and what couldn't be possible.

The general question is, could the block list be/have been implemented in a way that didn't store the full transactions in the list? Specifically, *perhaps* it would be possible to store only hashes of the in-points, out-points in the block list. These would be time stamped (notarized) in the blocklist exactly as is being done now.

The major difference is that it would be the coin receiver's responsibility to store the full transaction. And perhaps he might have to store previous transactions (X) deep to show history.

Then when he wanted to transfer the coins to the next party, he would create a transaction exactly as is being done now, except he would have to submit the antecedents to the transaction for validation as well. For validation, each antecedent of the in-points would be hashed and validated as existing in the block list. The in-points would be hashed and identified in the blocklist as not yet spent. Then the transaction would be validated as is currently done.

If everything validated correctly, the additional in/out-point hashes would be added to the block. This closes the transaction's in-points, and marks the new out-point hashes as unspent.

Once a node completes the block (by winning the hashing contest), he then broadcasts the block of hashes and the related transactions+plus antecedents to the other nodes for confirmation and acceptance.

as a rough example:

{block-9
 hash-a, hash-b, hash-c, hash-x
}
{block-12
 hash-a, hash-y, hash-c, hash-d
}
{block-17
 hash-b, hash-d, hash-e, hash-z, hash-f
}

{Transaction
 {in-points: hash-x, hash-y, hash-z}
 {address, signature and other transactions stuff}
 {out-points: hash-payed, hash-change
}
 
{generating-block
 hash-x, hash-y, hash-z, hash-payed, hash-change
}

So basically, if the i/o-point hash existed twice in the block list, it has been spent. If it exists only once it has not been spent.

So in after block-17:
  a, b, c & d are spent.
  e, f, x, y, z are unspent.

The transaction spends x, y & z and creates hash-payed & hash-change, so the transaction is valid.

After the generating-block:
  a, b, c, d, x, y, & z are spent.
  e, f, payed, change are unspent.


====
The Goal:

The goal is to provide all the same security of the existing system, but to avoid creating a public graph of every transaction that is easily correlated. In this case, the hashes don't even have to associate in the block. The block could simply sort all hashes in ascending order.

In effect, I want to create real gold coins. I can give my coins to you, but everyone in the world doesn't know I did. You can give them to the next guy and prove they are pure gold coins, because you have the pedigree of the coins AND every generation in the pedigree was notarized in the public record.

====
The Question:

Satoshi showed that you can remove transactions from the block list through the Merkle tree structure, without compromising security. I guess my real question is:

"What is the earliest you can remove the transactions?"

You could argue that nodes could remember everything anyway (the web never forgets). But if you structured the protocol so that new nodes would only receive a block list of hashes, they could only remember from this moment forward. That would give a little additional privacy. (Maybe)

====
Any thoughts? Is there an obvious way that people could cheat and get rich?

BitcoinTalk
#2
From:
Insti
Subject:
Re: Not a suggestion
Date:

In your system, Rather than just getting transactions from the block chain  I just have to watch every transaction (which I'll see anyway) and log them to my secret server.

You're just advocating security through obscurity.
BitcoinTalk
#3
From:
throughput
Subject:
Re: Not a suggestion
Date:
By the way, doesn't the idea of
Quote
the coin receiver's responsibility to store the full transaction. And perhaps he might have to store previous transactions (X) deep to show history.
make the limitation on the minimal value of transaction redundant?
Thus making micropayments use case more feasible.
BitcoinTalk
#4
From:
Red
Subject:
Re: Not a suggestion
Date:
Quote from: Insti on August 10, 2010, 09:34:14 AM
You're just advocating security through obscurity.

I did mention that. I wouldn't count on this for monetary security. I would like the system to be equivalent to the current one.

However, privacy obscurity is known to add value. Your neighbors, or the FBI could me watching everything you do all day long. But they probably aren't. If you happen to become "of interest", sure they could start watching you now and from this time forward.

But the most asked for additional legal powers seems to be, "let me examine everyone's logs!" (phone calls, cell towers, email connections, facebook connections, credit/debit card transactions, Google history, browser history.) The other systems are "security though authority." Bitcoin doesn't have that.

====

By the way, I'd rather not broadcast every transaction to every node either. But that is for another thread.
BitcoinTalk
#5
From:
Red
Subject:
Re: Not a suggestion
Date:
By the way, this is the way most digital notary services work. You send them a hash of a signed document and they log it permanently. Then they create a hash chain like bitcoin does. They periodically publish the current hash chain value in a newspaper or other offline redundant record.

You don't have to send your private documents/transaction to the notary for them to be time stamped and recorded. The notary is just certifying that something that matched this hash existed at this point in time.
BitcoinTalk
#6
From:
Insti
Subject:
Re: Not a suggestion
Date:
Quote from: Red on August 10, 2010, 02:22:09 PM
By the way, this is the way most digital notary services work. You send them a hash of a signed document and they log it permanently. Then they create a hash chain like bitcoin does. They periodically publish the current hash chain value in a newspaper or other offline redundant record.

You don't have to send your private documents/transaction to the notary for them to be time stamped and recorded. The notary is just certifying that something that matched this hash existed at this point in time.


You also don't have to prove to the notary that you have X BTC in your account to spend.

Although I was recently reading about Zero-knowledge proofs if you could use something like that to prove that your account had X BTC in it without revealing anything else it might be what you're looking for.

I'm just worried what you want is theoretically impossible.
BitcoinTalk
#7
From:
Red
Subject:
Re: Not a suggestion
Date:
Quote from: Insti on August 10, 2010, 03:06:16 PM
Although I was recently reading about Zero-knowledge proofs

Interesting idea to revisit! Thanks. Hadn't thought of them in a while.
BitcoinTalk
#8
From:
satoshi
Subject:
Re: Not a suggestion
Date:
This is a very interesting topic.  If a solution was found, a much better, easier, more convenient implementation of Bitcoin would be possible.

Originally, a coin can be just a chain of signatures.  With a timestamp service, the old ones could be dropped eventually before there's too much backtrace fan-out, or coins could be kept individually or in denominations.  It's the need to check for the absence of double-spends that requires global knowledge of all transactions.

The challenge is, how do you prove that no other spends exist?  It seems a node must know about all transactions to be able to verify that.  If it only knows the hash of the in/outpoints, it can't check the signatures to see if an outpoint has been spent before.  Do you have any ideas on this?

It's hard to think of how to apply zero-knowledge-proofs in this case.

We're trying to prove the absence of something, which seems to require knowing about all and checking that the something isn't included.
BitcoinTalk
#9
From:
Red
Subject:
Re: Not a suggestion
Date:
Satoshi: I know you know the first part of what I'm writing, but I want others to be able to follow and for you to correct any misconceptions I might have.

I was looking at the current Merkle tree implementation trying to figure out when transactions could be removed without losing security.

In transaction graph terms, the transactions represent the nodes. The edges of the transaction graph are represented by the in-points which point to previous transactions using a BlockHash->TransHash->OutPoint kind of structure. It is the existence of an in-point that marks a previous out-point spent.

So for a transaction to be valid, you most show for every in-point in a transaction that BOTH, a previous out-point exists AND no previous in-point exists that references that out-point. So for every out-point, there are zero or one in-points referring to it. zero = unspent. one = spent.

That also means that no transaction can be culled from the block list, until both its out-points are spent. Otherwise coins will disappear.
You can however, delete all double-bound transactions as soon as you are confident the 2nd binding block will stick around. (earliest possibility)

However, as you delete transactions and replace them with their tree hashes, you lose the graph structure present in the block list. In effect, all transactions undeleted from the block list have unspent value purely because they still exist. They can no longer prove validity by ancestry since that part of the graph was culled.

Which got me thinking, is there a way to prove validity if you never put the whole transactions into the graph to begin with?

Quote from: satoshi on August 11, 2010, 12:14:22 AM
The challenge is, how do you prove that no other spends exist?  It seems a node must know about all transactions to be able to verify that.  If it only knows the hash of the in/outpoints, it can't check the signatures to see if an outpoint has been spent before.  Do you have any ideas on this?


The key is to hash the transaction information as part of the out-point hash. So instead of creating a single transaction hash, you represent the transaction as two out-point hashes. (I originally considered an in-point/transaction/out-point structure using hashes, but that proved unnecessary.)

Only transaction validators need to know the bitcoin address associated with a recorded out-point hash. That comes from the submitted antecedent transaction for an in-point of the current transaction. The antecedent transaction and out-point is hashed and presumed BOTH valid and unspent if that hash appears one-and-only-one time in the block list.

The current transaction must be signed by the key for the address in the antecedent transactions of course. If this proves valid, two new out-point hashes are generated and inserted in the current block. The in-point hashes are marked spent by including them in the current block as well. (If a hash exists twice it is spent.) If you want to represent the transaction as a unit (and the currently visible transaction graph), the in-point hashes and out-point hashes could be grouped. However, this is not strictly necessary to prove validity.

Quote from: satoshi on August 11, 2010, 12:14:22 AM
We're trying to prove the absence of something, which seems to require knowing about all and checking that the something isn't included.

In this case we are trying to prove the presence of ONE matching hash and the absence of TWO matching hashes. It does require knowing all of them to prove.

I think the prohibitions against double spending are as strong as in the current version.


==== CAUTION! ====

However, you have to consider the case where a node causes mischief by deliberate adding random "canceling hashes". In this case, the node wouldn't be able to gain access to the coins, as he has no signed transaction hashing to a valid unspent out-point hash. However, the current owner wouldn't be able to spend the coins either. The in-point would be presumed already spent.

That means the validation conditions are EXACTLY THE SAME as with the current implementation. All validating nodes must examine and validate all transactions represented in a block before accepting it and building on it.

If there exist any hashes in the proposed block that are not represented by valid transactions, the block must be rejected.
That is exactly the same as the current system's, if any transaction doesn't validate, the block must be rejected.

I had hoped the condition to pass all transactions to all validators could be weakened but I can't see how (yet) without relying on trusted delegation.

----------

An interesting feature is that this simplifies the validation process. All that needs to be done is to parse the block list (of hashes) once. As each hash is parsed you simply look it up in a hash-set. If it doesn't exist you add it. If it does exist you delete it. When you are done parsing the block list, you will have the minimal set of valid and unspent out-points. You might even be able to keep the whole set in memory. (at least for a while!)


BitcoinTalk
#10
From:
Red
Subject:
Re: Not a suggestion
Date:
Quote from: satoshi on August 11, 2010, 12:14:22 AM
It's hard to think of how to apply zero-knowledge-proofs in this case.

It's hard for me too! :-) Was interesting to re-read though!

Was hoping it would spawn some insight on a way for nodes to demonstrate that they "always follow" the block generating rules, in absence of everyone needing to have the set of all transactions to double check.

It didn't. :-)
BitcoinTalk
#11
From:
satoshi
Subject:
Re: Not a suggestion
Date:
Still thinking this idea through...

The only job the network needs to do is to tell whether a spend of an outpoint is the first or not.

If we're willing to have clients keep the history for their own money, then some of the information may not need to be stored by the network, such as:
- the value
- the association of inpoints and outpoints in one transaction

The network would track a bunch of independent outpoints.  It doesn't know what transactions or amounts they belong to.  A client can find out if an outpoint has been spent, and it can submit a satisfying inpoint to mark it spent.  The network keeps the outpoint and the first valid inpoint that proves it spent.  The inpoint signs a hash of its associated next outpoint and a salt, so it can privately be shown that the signature signs a particular next outpoint if you know the salt, but publicly the network doesn't know what the next outpoint is.

I believe the clients would have to keep the entire history back to the original generated coins.  Someone sending a payment would have to send data to the recipient, as well as still communicating with the network to mark outpoints spent and check that the spend is the first spend.  Maybe the data transfer could be done as an e-mail attachment.

The fact that clients have to keep the entire history reduces the privacy benefit.  Someone handling a lot of money still gets to see a lot of transaction history.  The way it retrospectively fans out, they might end up seeing a majority of the history.  Denominations could be made granular to limit fan-out, but a business handling a lot of money might still end up seeing a lot of the history.
BitcoinTalk
#12
From:
Red
Subject:
Re: Not a suggestion
Date:
Quote from: satoshi on August 11, 2010, 09:07:59 PM
Still thinking this idea through...

It's a bit of a brain twisting idea isn't it. :-)

It turns out the notion of a cancelable notarization generalizes nicely.

For example this system is not limited to bitcoin transactions. Since the signed contracts are kept externally, with additional validation/notarization rules, you could easily implement things like IOUs/claim checks.

If someone gave you $5, you could give him a $5 IOU. Its IOU hash would be notarized into the blocks list (of hashes). When you pay them back you could have them sign the IOU for confirmation. Then have the notary insert an IOU hash cancellation. Then no one could show back up with a copy of the IOU and demand double payment.


Quote from: satoshi on August 11, 2010, 09:07:59 PM
I believe the clients would have to keep the entire history back to the original generated coins.  The fact that clients have to keep the entire history reduces the privacy benefit. 

I thought this too at first. But then I convinced myself otherwise.

It is really a matter of how much trust you place in the verifiers and the process of verification. People like the warm fuzzys that having every transaction available lets them trace the roots of their money back to its creation. However that is not required.

If you are confident in the process that validated the transactions during block creation (> 50% CPU agreement). And if you are confident the previous blocks can't be changed (you proved this). Then you only need to check that related out-points have not been spent. The security features remain in the block list and procedure, even if the transactions themselves are stored externally and the predecessors are not stored at all. You showed this yourself by proving old transactions can be deleted using the Merkle tree to maintain consistency.

Quote from: satoshi on August 11, 2010, 09:07:59 PM
Someone handling a lot of money still gets to see a lot of transaction history.  The way it retrospectively fans out, they might end up seeing a majority of the history.  Denominations could be made granular to limit fan-out, but a business handling a lot of money might still end up seeing a lot of the history.

True, privacy is directly related to observability. If there is a central party like a money changer, he can relate a lot of out-points. But if we get away from the notion that every coin must be traced back to creation, the observation horizons will be much closer.

----
It's really weird getting used to the notion that this coin is valid simply because the process wouldn't let it be included otherwise. But really, that is exactly how bitcoin generation works. The transaction has no inputs, but everyone decides the out-point must be valid purely because otherwise, it wouldn't be in the block at all. :-)

BitcoinTalk
#13
From:
satoshi
Subject:
Re: Not a suggestion
Date:
Quote from: Red on August 12, 2010, 01:10:19 AM
Quote from: satoshi on August 11, 2010, 09:07:59 PM
I believe the clients would have to keep the entire history back to the original generated coins.  The fact that clients have to keep the entire history reduces the privacy benefit.  

I thought this too at first. But then I convinced myself otherwise.
Are you back to talking about the existing Bitcoin system here?

I was talking about in the hypothetical system I was describing, if the network doesn't know the values and lineage of the transactions, then it can't verify them and vouch for them, so the clients would have to keep the history all the way back.

If a client wasn't present until recently, the two ways to convince it that a transaction has a valid past is:
1) Show it the entire history back to the original generated coin.
2) Show it a history back to a thoroughly deep block, then trust that if so many nodes all said the history up to then was correct then it must be true.

But if the network didn't know all the values and lineage of the transactions, it couldn't do 2), I don't think.
BitcoinTalk
#14
From:
Red
Subject:
Re: Not a suggestion
Date:
Quote from: satoshi on August 12, 2010, 02:46:56 AM
Quote from: Red on August 12, 2010, 01:10:19 AM
I thought this too at first. But then I convinced myself otherwise.
Are you back to talking about the existing Bitcoin system here?

Yes, I am talking about the hypothetical system.

The way I proposed the system, each time a block gets generated every validating node must accept or reject that block by validating the transactions and confirming the hashes in the block. In effect, the same work that is being done with the current system, plus the out-point hash checks. Since the other validators were already competing to generate the block, they already have (at least most of) the transactions.

As with the current system, if the transactions don't validate (plus match included out-point hashes) the other nodes will reject the block. If the block doesn't get acceptance by at least 50% of the CPU power, it doesn't make the block list.

So the presence of the hashes in the block list, signifies that at least 50% of the existing validators at that time saw and validated all the containing transactions and out-point hashes.

Therefore (barring hash crashes) if someone submits an antecedent transaction that matches an unspent out-point, it must be valid.

That antecedent's antecedent must have been valid as well, otherwise the antecedent would have been rejected. And so on and so on.

For that not to be the case, you have to postulate that there was a period in time where blocks weren't being validated against out-point hashes. But that's plausibly implausible with the CPU competition system.


Quote from: satoshi on August 12, 2010, 02:46:56 AM
If a client wasn't present until recently, the two ways to convince it that a transaction has a valid past is:
1) Show it the entire history back to the original generated coin.
2) Show it a history back to a thoroughly deep block, then trust that if so many nodes all said the history up to then was correct then it must be true.

If a client joined the network recently, it did so presuming that prior validators followed the rules and all pre-existing blocks are valid. (No one would join a known corrupt network)

Sure, in the current system, if transactions were never purged, a new node could validate all prior blocks for self consistency. But they still couldn't prove absolute truth. A bot net could have taken over and erased some transactions leaving "a new truth" and unhappy users. Equivalent to case 1) above.

In the current system, if transactions were Merkle tree purged then you have case 2) above. New comers must trust in the process. Anything missing, they don't need to worry about. Everyone must presume it was valid.

The unique thing I'm saying is that, if you have confidence in the bitcoin validation competition process (and we do!), then you really don't need "a 2) thoroughly deep block" to be very deep at all. Someone said in another thread that clients reject any changes to blocks more than two hours old. So we can have absolute confidence in all blocks buried 12 deep.

So if a transaction is unspent and buried 12 deep, we can purge all it's ancestors. They add warm fuzzies but no additional validation. We have to rely on them. There is simply no way to back up and change course.

After that, every succeeding block presumes all the preceding blocks are true. Otherwise it would be a fork and not a succeeding block. So for any transaction validated against out-points in a preceding block, if those out-points exist and are unspent, they must be presumed valid. If those are presumed valid, their ancestors must be presumed valid even if purged.

---
In the proposed system, exactly the same things are true.

If an antecedent out-point hash is unspent and buried 12 blocks deep, then it is absolutely unspent. Nothing can change that fact. No point in checking its ancestors. You can finish validating the transaction, cancel the in-points hashes and create new out-point hashes.

Interestingly, if an antecedent out-point hash is unspent and buried LESS THAN 12 blocks deep, then it is RELATIVELY unspent. Curiously, there is still no point in checking its ancestors. The only thing that could change the antecedent's validity is a branch swap to a longer chain. If an ancestor of the antecedent you are validating this transaction against was swapped out, this transaction would be swapped out as well.

It's one of those cheesy time machine movie plots. Someone when back in time and spent my ancestor. Now I don't exist!

=====

So what I'm saying is that in BOTH systems (existing and proposed) the only thing validators need to do is to validate that the antecedent out-points exist and are unspent (for the current block chain). The process assures that everything else remains relatively or absolutely valid.

The rest is just warm fuzzies.

-- PS --

I know this is too long and redundant, but I'm to tired to edit. :-)
BitcoinTalk
#15
From:
satoshi
Subject:
Re: Not a suggestion
Date:
I'm not grasping your idea yet.  Does it hide any information from the public network?  What is the advantage?

If at least 50% of nodes validated transactions enough that old transactions can be discarded, then everyone saw everything and could keep a record of it.

Can public nodes see the values of transactions?  Can they see which previous transaction the value came from?  If they can, then they know everything.  If they can't, then they couldn't verify that the value came from a valid source, so you couldn't take their generated chain as verification of it.

Does it hide the bitcoin addresses?  Is that it?  OK, maybe now I see, if that's it.

Crypto may offer a way to do "key blinding".  I did some research and it was obscure, but there may be something there.  "group signatures" may be related.

There's something here in the general area:
http://www.users.zetnet.co.uk/hopwood/crypto/rh/

What we need is a way to generate additional blinded variations of a public key.  The blinded variations would have the same properties as the root public key, such that the private key could generate a signature for any one of them.  Others could not tell if a blinded key is related to the root key, or other blinded keys from the same root key.  These are the properties of blinding.  Blinding, in a nutshell, is x = (x * large_random_int) mod m.

When paying to a bitcoin address, you would generate a new blinded key for each use.

Then you need to be able to sign a signature such that you can't tell that two signatures came from the same private key.  I'm not sure if always signing a different blinded public key would already give you this property.  If not, I think that's where group signatures comes in.  With group signatures, it is possible for something to be signed but not know who signed it.

As an example, say some unpopular military attack has to be ordered, but nobody wants to go down in history as the one who ordered it.  If 10 leaders have private keys, one of them could sign the order and you wouldn't know who did it.