Hash based confidential txn chains..

[spartacusrex]

I originally posted this in General.. but it went down as well as a pulled pork sandwich at a vegan convention..

Hope it's OK to post here.

..

This is something I've been thinking about since gmaxwell blew all our brains out with his homomorphic confidential txn implementation.

It is a very simple idea and NOT as powerful as CT, but it does hide the values when you make a spend (from most people). And is quantum secure as well, as it only relies on hash functions.

Basically - when you create a TXN, you also generate a random number.

You then hash the outputs with that random number. You and the receiver know what the random number is, and so can decode what the outputs of the txn are, and so can check that the sum of the inputs equals the sum of the outputs. A valid txn.

When you want to spend a hidden output, you would need to provide the complete txn chain for each input (random value+outputs), going all the way back to a coinbase txn, which is never hidden. You would not need to provide the complete txn tree from the coinbase, just the branch that your input/output is on.

This means that everyone spending an output, would know the complete history that led to it. But on the chain, all that would be stored is a mass of hash values.

You can't cheat the system, as the receiver would not accept a txn that had an invalid history as valid, and since the txn would be mined as usual whether it was valid or not, since the miners can't tell (and mine the txn regardless), if you did try and cheat all you would do is lock up the funds in a spendable-yet-invalid output. That no one would accept as payment.

If, for now, txns had 1 input and 2 outputs, you would need to store the random value(32 bytes), and the value of both outputs, (32 * 3 bytes) for each TXN in the chain leading back to the coinbase. Multiple inputs could, and probably would, go back to different coinbase txns. So if there were 10 txns in all in the chain, that's an extra 960 bytes.

I am not sure how many txn's on average are in the chain going back to the coinbase.. Anyone ?

This data would start small but could grow to be quite large. Unless you are 'hodling' the coins.

I was thinking that at some point in the future you could 'cash-in' an output, by providing the complete history to the miners, and that would then create a NOT hidden output to you in the coinbase. This would remove the anonymity for that chain of txns of course, but could be done years later. You would then have a spendable output that required no txn chain as proof, as it's not a hidden value.

I really don't know if this is actually useful / practical / doable, but wanted to throw it in the 'bit-pit', in case anyone can see something cool that I've missed..

( For instance - can you prove the output and it's value are valid without exposing all the hidden data in the chain ? )

[1714834940]

1714834940

[1714834940]

1714834940

[1714834940]

1714834940

[1714834940]

1714834940

[1714834940]

1714834940

[lottoshares]

How do you propose generating a random number? Unless your computer is hooked up to a hardware random number generator it could be producing pseudorandom numbers which are unsuitable for sensitive applications like cryptography.

[kevin08]

I am not sure how many txn's on average are in the chain going back to the coinbase.. Anyone ?

You need 100 confirmations before you can spend coinbase coins. Today most blocks are full, and have between 1000 and 3000 transactions in each block. If we take an average of 1500 transactions in each full block, then spending a coinbase coin as fast as possible would require waiting for 100 blocks with an average of 1500 transactions in each block. That makes 100 x 1500 = 150000 transactions in the chain going back to the coinbase of freshly mined coins spent as soon as they possibly can be.

[Remember remember the 5th of November]

How do you propose generating a random number? Unless your computer is hooked up to a hardware random number generator it could be producing pseudorandom numbers which are unsuitable for sensitive applications like cryptography.

And how do you think generating private keys happens on a computer?

[spartacusrex]

I am not sure how many txn's on average are in the chain going back to the coinbase.. Anyone ?

You need 100 confirmations before you can spend coinbase coins. Today most blocks are full, and have between 1000 and 3000 transactions in each block. If we take an average of 1500 transactions in each full block, then spending a coinbase coin as fast as possible would require waiting for 100 blocks with an average of 1500 transactions in each block. That makes 100 x 1500 = 150000 transactions in the chain going back to the coinbase of freshly mined coins spent as soon as they possibly can be.

No - I didn't explain well enough. That's not what I mean.

I mean when you spend an output, how many 'spends' are there going back to a coinbase txn.

So - the first time you spend the coinbase, is 1, then the next txn that uses those outputs, is 2, etc etc..

[callynyan]

I would buy and hodl lots of an altcoin if it implemented this.

[lottoshares]

How do you propose generating a random number? Unless your computer is hooked up to a hardware random number generator it could be producing pseudorandom numbers which are unsuitable for sensitive applications like cryptography.

And how do you think generating private keys happens on a computer?

According to Stackexchange Bitcoin core uses RAND_bytes from OpenSSL.

http://bitcoin.stackexchange.com/questions/24722/what-kind-of-random-numbers-source-does-getnewaddress-in-bitcoin-core-api-bitco

It uses RAND_bytes from OpenSSL. The relevant call is CKey::MakeNewKey.

getnewaddress is in rpcwallet.cpp. It tries to get a key from the pool, and if the pool is

empty it allocates a new one which is populated using RAND_bytes

As others mentioned Bitcoin core uses OpenSSL random sources.

This means that it uses any random source available, like:

the operation system, i.e. interrupts
random sources of the CPU or the chip set
dedicated hardware for entropy generation
So in order to make sure your hardware random generator works with Bitcoin you must make sure it works with OpenSSL.

RAND_bytes from OpenSSL uses OS specific calls to various random sources. However that system can sometimes fail silently according to some of the Bitcoin core devs.

https://github.com/bitcoin/bitcoin/pull/5885#issuecomment-78611027

We've seen operating system RNG's fail silently in really frightening ways several times over the last few years, a belt-and-suspenders approach where silent failure at least gets a best effort bit of entropy-snake-oil (or maybe not so snakeoil: after going and writing a bunch of entropy collecting code I'm more impressed with the performance than I expected) seems to be a clear improvement. OpenSSL's (and libressl's) system entropy randomness generator is also pretty scary (it can fail silently back to snakeoil entropy much weaker than what this code does).

That's why the core devs have been developing their own random number generating system, which is slated to replace OpenSSL RNG use in core version 0.13,


https://github.com/bitcoin/bitcoin/pull/5885#issuecomment-161609639

Slated for 0.13 (with the goal of getting rid of OpenSSL dependency by then), opened #7162 to track this

However, the core devs say the weaknesses they identified in OpenSSL RNG do not significantly undermine Bitcoin's security because Bitcoin Core hardens the RNG input with additional timing information.


https://www.reddit.com/r/Bitcoin/comments/3ccb7w/bitcoin_core_uses_rand_bytes_from_openssl_to/csu885c

There are many theoretical concern related to OpenSSL's operation as well as Linux's /dev/random (and other operating systems) behavior in general-- and there is a long term project underway to replace it: https://github.com/bitcoin/bitcoin/pull/5885 (and you can see from the comments there, we're well aware of how it works, more so than even the concerns you've expressed here).

That said, these are theoretical weaknesses. In Linux /dev/random and /dev/urandom are the same rng, but /dev/random uses an entropy estimator. The estimator provides basically no value and is often misunderstood. This page has an excellent and correct debunking: http://www.2uo.de/myths-about-urandom/

The "aren't very random" you're quoting is taken out of context-- the context is "The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy, "--- e.g. context that matter a lot for generating SSH keys, but not so much for Bitcoin.

Beyond the basic operation there, OpenSSL and Bitcoin Core further harden the input with additional timing information.

Finally, the bit of concern you're sowing there doesn't make a relative comparison. It would be no good to chase someone from using Bitcoin Core due to niche and speculative issues to something that was practically less secure.

For a simple random number generation as proposed by spartacusrex I would find a better alternative than an OpenSSL RNG.

There is a thread full of posts by heavyweights discussing the best way to manually generate a truly random private key by repeatedly throwing dice. The reason they generate keys that way is to avoid 100% of all BS regarding computer-generated entropy sources & algorithms.

Anyway a lot of the heavy weights are in this thread. I would have thought that generating private keys manually might be termed a little extreme.

Depends on your definition of cost-to-benefit ratio:

Cost:  Spending 20 minutes, one time, to create entropy and convert it to a wallet
Benefit: Avoiding 100% of all BS regarding computer-generated entropy sources & algorithms, until the end of time

If you're holding a "lot" of money, some people would rather just remove all doubt.  And the cost of doing so really isn't that high.

[spartacusrex]

... Thanks lottoshares. 'Truely' Random numbers are hard to come by. Got it.

..

Thinking about this scheme a few of the issues that arise are :

How are the txn fees paid to the miner?

How is the information about the chain proofs shared securely between the sender and receiver?

[DannyHamilton]

Thinking about this scheme a few of the issues that arise are :

How are the txn fees paid to the miner?

How is the information about the chain proofs shared securely between the sender and receiver?

There is also the problem that a single satoshi could theoretically trace back to dozens of coinbase transactions.  If you wanted to send an entire bitcoin to someone, you might be needing to send the entire history back to hundreds or even thousands of coinbase transactions.

[spartacusrex]

Yep.

Which is why I thought 'cashing in', by providing the proof to the miners, at some point to remove all the required data might be necessary. And thus provide you with a non-hidden output.

As I mentioned this would make that chain of data public, but it could be many moons after the fact.

Maybe once the proof reaches a certain size, say 50k, you should think about it.

[OnkelPaul]

What about the ability of nodes and miners to decide whether transactions are valid or invalid? If they can't do that, wouldn't it be possible to spam the blockchain?
If you want to prevent that by requiring mandatory miner fees, you need to add the miner fee part of the transaction without randomization, as you don't know which miner is going to add your transaction to a block. Would that be feasible?

Or did I misunderstand your proposal thoroughly? I must admit that I did not analyze it in depth.

Onkel Paul

[spartacusrex]

What about the ability of nodes and miners to decide whether transactions are valid or invalid? If they can't do that, wouldn't it be possible to spam the blockchain?

No - The miners don't validate the txn. They simply take some inputs with random values and give it to some outputs with random values (as far as they know). All the validation is done by the users.

You can't cheat the system, as the receiver would not accept a txn that had an invalid history as valid, and since the txn would be mined as usual whether it was valid or not, since the miners can't tell (and mine the txn regardless), if you did try and cheat all you would do is lock up the funds in a spendable-yet-invalid output. That no one would accept as payment.

The miners are still used to prevent double spends. They won't let you spend the same output twice, but they won't know how much it is for.

..

The miners would need to be paid a fee though, and as you say, that would need to be un-hidden as you don't know which miner will find the block..  Or some new as-yet-un-envisaged system..

[s2]

I do however like the idea of a coin owning it's history (probably with ZKP if possible)... I've been considering this as well and mixed with Gavin's inverse bloom filter approach it feels like there's something there.

I know I'm probably adding confusion rather than clarity here but if the miners can't see the values of the transaction what stops a malicious user spending coins to themselves with a negative amount?  I.e. creating more coins in one output than they originally had and now they can legitimately spend these invented coins?

I thought one of the great things of ZKPs was that you could prove the value was positive but wouldn't be able to tell what that value was... using a hash and random salt makes me scratch my head how it is validated?
(I genuinely think it's just a case of me misunderstanding it but have to ask!)

[callynyan]

I do however like the idea of a coin owning it's history (probably with ZKP if possible)... I've been considering this as well and mixed with Gavin's inverse bloom filter approach it feels like there's something there.

I know I'm probably adding confusion rather than clarity here but if the miners can't see the values of the transaction what stops a malicious user spending coins to themselves with a negative amount?  I.e. creating more coins in one output than they originally had and now they can legitimately spend these invented coins?

I thought one of the great things of ZKPs was that you could prove the value was positive but wouldn't be able to tell what that value was... using a hash and random salt makes me scratch my head how it is validated?
(I genuinely think it's just a case of me misunderstanding it but have to ask!)

Well sending a negative amount or more than what you have is impossible. With the current platform of bitcoin you can only send what's there and negative amounts literally don't exist.

Bitcoin is a closed system, energy(bitcoin amount) never changes. It just changes hands.

[spartacusrex]

Can't stop this idea creeping back into my daily thoughts..

..

Having thought about it more, there is a 'nicer' way of reducing the size of the proofs.

To recap :

1) I want to send Jim some coin.

2) I create a txn that sends him the money.

3) Then I create a random number and hash all the outputs with this value. These outputs could start with an 'H' or whatever, and the miners would have to allow these types of txns. (They can validate that the inputs are being spent correctly, but they cannot check that 'sum of inputs'=='sum of outputs' )

4) I share this random value with Jim and also ALL the random values for ALL the txns that lead up to the hidden inputs in the txn, until you reach an unhidden input. Coinbase are always unhidden.

This way Jim now has a proof chain of txns, which lead from the original txn all the way back to unhidden values. Jim now knows 100% that the txn is valid (even though the miners can't tell).

The problem is the size of the proofs can grow quite large. How to make the proofs smaller ?

Originally I thought you would publish the entire proof chain of the txn, miners would verify (check the random number gives a txn where the inputs==outputs), unhide the values, and the txn would now have a tiny proof chain.

Instead, only publish the first txn in the proof chain by revealing the random numbers for that txn. And repeat up the chain until the proof is small enough.

This way the endpoints of the proof chain remain hidden at all times, and remain several hidden txns deep, and all that is revealed is txns that occurred 'some time ago'.

..

On-going issues :

1) How do you pay fees.. ? ( how is this done in gmaxwell's CT - I think he says he does it explicitly, so we would need to use an unhidden input )

2) How do you share the proof with the receiver.. ? (Face to face works, but how do you do it over the network.. needs to be encrypted for the receiver, and we would want it to be quantum secure - that's the whole point)

[tonych]

Size is a big issue indeed.  If not addressed properly, the size of coin histories will grow exponentially.

I think I have a better solution: https://bitcointalk.org/index.php?topic=1574508.0

Rather than expiring the privacy (as your last post suggests), it works by disallowing merges and limiting coin divisibility.  There is a small set of fixed denominations (e.g. 1, 2, 5, 10, 20, 50, 100, 200, 500, ...), and every output must be divisible by its denomination, then you combine outputs of different denominations to compose any amount you want.  Everybody is already familiar with this system because that's how cash money works.  As a result, coin histories grow only lineary, which is manageable.

[spartacusrex]

Size is a big issue indeed.  If not addressed properly, the size of coin histories will grow exponentially.

I think I have a better solution: https://bitcointalk.org/index.php?topic=1574508.0

Rather than expiring the privacy (as your last post suggests), it works by disallowing merges and limiting coin divisibility.  There is a small set of fixed denominations (e.g. 1, 2, 5, 10, 20, 50, 100, 200, 500, ...), and every output must be divisible by its denomination, then you combine outputs of different denominations to compose any amount you want.  Everybody is already familiar with this system because that's how cash money works.  As a result, coin histories grow only lineary, which is manageable.

Nice, a very similar idea..  

Makes me think that maybe it might just work.. (hope you won't mind me continuing in this thread..)

1) I'm missing something - why do the amounts have to be of the specific fixed denominations ? Since you can split, and have 2 outputs, with one being the change.

2) Yes, limiting the input set to 1 input would mean that the history grows linearly, but as you say, you may then have to make multiple spends to send someone the correct amount. Does this not defeat the point ?

3) In my version, since the txn is basically exactly the same as a normal txn, just that the outputs are 'hashed-with-the-random-number' the proofs per txn are tiny, you just need to know the random number used in that txn. In your system the proof needs to store the whole txn, if I understand correctly ?

4) At some point I do envisage having to 'expire-the-privacy', to reduce the proof size, but the coins are then reverted to regular bitcoins, unlike in yours where you have to 'burn' coins to get the system started. Can I return the bbc coins back to bitcoins ? And I don't see that revealing a txn that happened a couple of months ago, as that bad..

5) Do you envisage ever shortening the proofs in your system ?

Good luck with your coin! (I too am ..err.. composing..)
 

[tonych]

1) To avoid ultimate splitting into the dust.  Otherwise, to transfer 100 satoshi you'll have to move 100 coins, 1 satoshi each.
2) You do have to make more spends to send the desired amount but I don't think it is going to be a big problem -- we are already doing it when we pay in cash.
3) I don't think you can prove anything with just one random number, you do need full transaction data to be able to verify everything that miners no longer can verify: that the amounts sum up correctly, that the payment was to you and not somebody else; then you need the data to regenerate the spend proof to make sure the output was not spent twice.
4) I think, in such a system, people want to be reasonably assured that their privacy won't be dumped by somebody else down the line, that's why BBC cannot be converted back to bitcoins (but it can be exchanged, of course).  If revealing 2-months old transactions is ok for you, somebody else might wish at least 2 years, or even a lifetime.  We might run several coins with different "privacy expiration" periods in parallel and have people choose the right coin for each type of activity they are engaged in, but I don't think we need this complexity when we can just always have no-expiration privacy.
5) I don't think linear growth is a concern.  With exponential growth of computing resources, these coin histories will actually look small.

Good luck with your coin! (I too am ..err.. composing..)

I'm going to announce it in a few days)

[spartacusrex]

Yep - you are correct..you do need the amounts + random number.

Got a little 'dizzy' there, since that's how I spell it out in the OP..  

..

In conclusion - your coin uses this system, but with the set-denominations / only-single-input-allowed to fix the exponential growth of the proofs, which you never reveal. Sweet. (Although I am still not 100% that this method will create smaller proofs - given that you will need multiple txns)

so..

1) How do you manage the fees ?

2) How do you share the proofs ?

[tonych]

In conclusion - your coin uses this system, but with the set-denominations / only-single-input-allowed to fix the exponential growth of the proofs, which you never reveal. Sweet. (Although I am still not 100% that this method will create smaller proofs - given that you will need multiple txns)

Correct, and don't forget about spend proofs.  Without them, there is no way to know that a previous owner didn't spend the coin twice.

1) How do you manage the fees ?

There are two parallel currencies in the system: an "open" one and a hidden one.  The fees are paid in the open currency within the same transaction.

2) How do you share the proofs ?

There is a p2p messaging protocol, see the white paper I published today https://byteball.org/Byteball.pdf (scroll closer to the end).