Pages:
Author

Topic: Ultimate blockchain compression w/ trust-free lite nodes - page 5. (Read 87932 times)

legendary
Activity: 1428
Merit: 1093
Core Armory Developer
Well, that's a reasoned argument I can listen to. Might I suggest then, that the key format be the following

Code:
<20 bytes> idx:var_int <...n-bytes...>

Where idx is the index in the range of [0, n] specifying where the prefixed 20 bytes should be spliced into the script. This step is skipped for scripts/keys of 20 bytes or less.

The only issue then is an unambiguous algorithm for selecting which 20-bytes to pull out for the prefix.

Hah, you just jumped all the way to the other side.  I was actually just suggesting that if we're not going to do anything fancy with the scripts, we should use the exact script as the key instead of its hash.  That way we don't have to store the script itself in the key and value of the leaf node (even though actually only the hash160(rawscript) would be in the key).
legendary
Activity: 905
Merit: 1012
Well, that's a reasoned argument I can listen to. Might I suggest then, that the key format be the following

Code:
<20 bytes> idx:var_int <...n-bytes...>

Where idx is the index in the range of [0, n] specifying where the prefixed 20 bytes should be spliced into the script. This step is skipped for scripts/keys of 20 bytes or less.

The only issue then is an unambiguous algorithm for selecting which 20-bytes to pull out for the prefix.
legendary
Activity: 1428
Merit: 1093
Core Armory Developer
I propose that we keep the UTXO index keyed by hash160(scriptPubKey) - for different reasons, primarily for the benefits of a constant key size. That would make things more difficult for your proposal. But yes, other than that we are interpreting each other correctly now.

If we're going to use "essentially" raw script, we'll save quite a bit of space by making it the key of the tree, then we don't have to store the actual script at the leaf nodes.  I am blanking on all the other data that needs to be stored, but it might be considerable savings (I haven't thought about this in a while).   Well, it would save exactly 20 bytes per leaf.  Right now I think there are 6 million UTXOs, so that would be 120 MB of savings.   

The constant keysize would be important in a trie, but in a level-compressed PATRICIA-like tree, it shouldnt' make a difference. 
legendary
Activity: 905
Merit: 1012
I propose that we keep the UTXO index keyed by hash160(scriptPubKey) - for different reasons, primarily for the benefits of a constant key size. That would make things more difficult for your proposal. But yes, other than that we are interpreting each other correctly now.

Possible? Yes. Desirable? No. It's important that miners verify that they haven't been duped onto a side chain. It is, however, okay for them to throw away those historical transactions once they have been verified and just keep the UTXO set.

Yeah, I did not mention the UTXO set because I thought it's obivous.

The reason I brought up this is, I believe a lot of us are willing to run a USB miner to secure the network, without generating any noticeable revenue, now that it's out and very power-efficient, the power cost of keeping one running is somehow negligible, but if we have to download and store the rapidly growing full chain, the cost may grow significantly.

The miner could validate the entire history or synchronize with constant storage requirements, throwing away data as it is no longer required.
hero member
Activity: 784
Merit: 1000
Possible? Yes. Desirable? No. It's important that miners verify that they haven't been duped onto a side chain. It is, however, okay for them to throw away those historical transactions once they have been verified and just keep the UTXO set.

Yeah, I did not mention the UTXO set because I thought it's obivous.

The reason I brought up this is, I believe a lot of us are willing to run a USB miner to secure the network, without generating any noticeable revenue, now that it's out and very power-efficient, the power cost of keeping one running is somehow negligible, but if we have to download and store the rapidly growing full chain, the cost may grow significantly.
legendary
Activity: 1428
Merit: 1093
Core Armory Developer
I think one of us is misunderstanding the other. Bitcoin already has code for extracting either pubkeys, hash160(pukey)'s, or hash160(script)'s from arbitrary transactions as they come in. That's how the wallet code knows whether a transaction is yours or not.

What I'm suggesting is that some full nodes remember and index these results for every transaction in the UTXO set, creating a map of hash160 -> script variants. They then expose the ability for other nodes to query this map, or proactively do so if/when they receive a UTXO query, and provide a p2p message for gossiping these mappings.

This hash160 -> script(s) map doesn't need to be deterministic or authenticated in any way. If given a script, anyone can examine it to see that yes, it does indeed have the relevant pubkey, hash160(pubkey), or p2sh embedded within it, and query the authenticated UTXO index to see that yes, there are unspent outputs using this script. Therefore we don't need to solve the possibly intractable, definitely not future-proof problem of figuring out a general way to match arbitrary scripts to “controlling addresses.” We can use bitcoind's current logic, and are free to update that logic on each release.

Okay, I was proposing a change to the way the UTXO tree was keyed, for the purposes of having a consistent way to look up balances/UTXOs for hash160 values instead of raw scripts.  You are proposing we keep it keyed/indexed by raw script, but the nodes can store their own meta data for those addresses as they see recognizable scripts.   It would not be a requirement to serve the entirety of all UTXOs spendable by someone with the private key of a given hash160, but it can still be useful. 

Is that a correct interpretation of what you're saying?

My problem with that is that it isn't determinisitc whether you will be able to find all your coins.  Maybe it doesn't matter:  "Use standard scripts if you want to be able to find all your coins efficiently.  Otherwise, you're on your own."  With the way you suggest it:  if you get lucky, nodes have the data pre-indexed for you, and have all of it.  But you can't count on it and they can't prove whether they supplied you everything.  This makes it considerably less useful, and possibly not useful (nodes need to be able to know if they have everything, or they'll do something else that guarantees it).

I think ultimately the raw script indexing is the correct answer.  I'm just exploring alternatives, that make the multi-script-single-address problem a little more efficient (and reliable).

legendary
Activity: 905
Merit: 1012
I think one of us is misunderstanding the other. Bitcoin already has code for extracting either pubkeys, hash160(pukey)'s, or hash160(script)'s from arbitrary transactions as they come in. That's how the wallet code knows whether a transaction is yours or not.

What I'm suggesting is that some full nodes remember and index these results for every transaction in the UTXO set, creating a map of hash160 -> script variants. They then expose the ability for other nodes to query this map, or proactively do so if/when they receive a UTXO query.

This hash160 -> script(s) map doesn't need to be deterministic or authenticated in any way. If given a script, anyone can examine it to see that yes, it does indeed have the relevant pubkey, hash160(pubkey), or p2sh embedded within it, and query the authenticated UTXO index to see that yes, there are unspent outputs using this script. Therefore we don't need to solve the possibly intractable, definitely not future-proof problem of figuring out a general way to match arbitrary scripts to “controlling addresses.” We can use bitcoind's current logic, and are free to update that logic on each release.
legendary
Activity: 1428
Merit: 1093
Core Armory Developer
Well it is straightforward to demonstrate to a lightweight client that such other script hashes relate to the same address. A full node could respond to a UTXO query with a the asked-for data and an attached message along the lines of "and hey btw did you know about these scripts using the same pubkey: ...?" attached at the end. The client can verify for itself that indeed, those scripts use the same pubkey or P2SH hash and then query for those outputs as well.

Obviously this isn't ideal, but it might be good enough (you wouldn't need consensus for this data, just be attached to at least 1 honest full node maintaining an index of this information). Or I suppose yet another (3rd!) index can be maintained mapping addresses to scripts actually present in the UTXO set, but as you note that wouldn't be future-proof.

There's two problems with this logic:
(1) Every request is X-fold more work for the serving peer just to catch the 0.01% of addresses that have multiple forms in the blockchain.  It has to do multiple lookups for each request.
(2) Something like " OP_DROP ..." is a serious problem for this proposal.  The task of "find all UTXOs to address/pubkey X, which have a message prefixed to it" requires a full search of the UTXO space.   Such scripts lose all benefit of this proposal.  In fact, any node using these kinds of scripts will have to use the original full-node-but-pruned logic, unless the extraneous data is totally deterministic/predictable.

Number 2 is concerning, because even if nodes somehow know all the messages they are expecting to see, the proofs of existence (or non-existence) are on isolated branches and require quite a bit more data to prove than if they were all clustered on one branch.   And if they don't know what the messages (or other data unrelated to addr/pubkey), then the peer might be expected to do the UTXO search.  They might end up adding extra metadata to their database just to accommodate these kinds of requests. 

On the other hand, since address re-use is a bad idea, maybe the argument about isolated branches are irrelevant. 

I have an idea that is beyond infeasible, but it's good food for thought.  Maybe it's useless, but what the hell:

For a given script, if it contains a single public key or single hash160 value (how do we define this?), then we use the hash160 value or compute it (from the public key) and prefix that to the script, replacing the value actually in script with a 0xff byte (or something unused).  This is okay technically (if it were possible to identify what values will be used as pubkeys/hash160s), because it's technically not a requirement for the lookup key to match the script.  The real script will still be stored at the leaf node.   So "DUP HASH160 EQUALVERIFY CHECKSIG" would be keyed:  " DUP HASH160 0xFF EQUALVERIFY CHECKSIG". 

This theoretically solves all the problems at once, because it doesn't really matter what else is in the script, as long as the "controlling address" is first.  Then it's trivial to prove inclusion or exclusion of data for a given address.    But of course, it's probably intractible to figure out how to reduce arbitrary scripts to "controlling addresses." 




legendary
Activity: 905
Merit: 1012
Possible? Yes. Desirable? No. It's important that miners verify that they haven't been duped onto a side chain. It is, however, okay for them to throw away those historical transactions once they have been verified and just keep the UTXO set.
hero member
Activity: 784
Merit: 1000
Is it possible for a miner to only download full blocks from the last checkpoint and still validate transactions?
legendary
Activity: 905
Merit: 1012
Well it is straightforward to demonstrate to a lightweight client that such other script hashes relate to the same address. A full node could respond to a UTXO query with a the asked-for data and an attached message along the lines of "and hey btw did you know about these scripts using the same pubkey: ...?" attached at the end. The client can verify for itself that indeed, those scripts use the same pubkey or P2SH hash and then query for those outputs as well.

Obviously this isn't ideal, but it might be good enough (you wouldn't need consensus for this data, just be attached to at least 1 honest full node maintaining an index of this information). Or I suppose yet another (3rd!) index can be maintained mapping addresses to scripts actually present in the UTXO set, but as you note that wouldn't be future-proof.
legendary
Activity: 1428
Merit: 1093
Core Armory Developer
legendary
Activity: 1372
Merit: 1002
While still talking about the ledger vs UTXO, I'll try to stay close to the context of this proposal, maybe the ones that prefer a ledger can be statisfied with little changes.
Let's try.
Let's look, for example, at this transaction: http://cryptocoinexplorer.com:4750/tx/8b1afc9aa2ca96c846dce3a47d577068e5f722961eff036b5792756eef28e2a0
The full public key of 18dTnNqj396jL9U98RHYEyJX2TSw6Ku7Gd and the signature is repeated in this transaction, isn't it?
We can modify the UTXO dictionary to avoid this redundancy.

The UTXO dictionary stores (scriptPubKey, balance)

But if he stored a ledger (address/scriptPubKey, balance), you would only need to sign once for 18dTnNqj396jL9U98RHYEyJX2TSw6Ku7Gd in the tx above.
Note that I'm considering an UTXO enforced by the chain and not an altchain.
The "default script" of just showing the public key

Code:
scriptPubKey: OP_DUP OP_HASH160  OP_EQUALVERIFY OP_CHECKSIG
scriptSig:

Could be assumed and ommitted, replaced by this:

Code:
scriptPubKey: 
scriptSig:

But then you would need to indicate explicitly how much you want to spend from the address in the input.
The transaction above would not have had to reference each input individually, it would only have included the address, an amount to substract, the public key and signature. Well, and the sequence number or equivalent for that address. I prefer a hash of the last transaction spending from that address. Otherwise you need to remember empty addresses ast sequence numbers forever.

Basically, this (paying to an address substracting from another address) would be the general case and the "pay to script" or contract, would be the special case. I think Ripple must do something like this for their ledger and their contract scripts.

Does this make technical sense before we start discussing whether a currency is in itself an accounting system and other philosophical matters?
LvM
full member
Activity: 126
Merit: 100
And yes,
I know that some BTC "Heroes" won't even hear evident, irrebuttable facts based on pure logic and thousand year old GAAP.

Its hard to concede we were sailing on the wrong ship all the time, isn't it.

I think it is pointless trying to convince fellow bitcoiners that their baby is poorly designed. Maybe you should support one of alt coins which plans to do exactly as you say?

https://bitcointalksearch.org/topic/white-paper-purely-p2p-crypto-currency-with-finite-mini-blockchain-195275
or
https://bitcointalksearch.org/topic/mc2-a-cryptocurrency-based-on-a-hybrid-powpos-system-169204

@aaaxn
Thank you! Will check it when my time allows.
sr. member
Activity: 359
Merit: 250
And yes,
I know that some BTC "Heroes" won't even hear evident, irrebuttable facts based on pure logic and thousand year old GAAP.

Its hard to concede we were sailing on the wrong ship all the time, isn't it.

I think it is pointless trying to convince fellow bitcoiners that their baby is poorly designed. Maybe you should support one of alt coins which plans to do exactly as you say?

https://bitcointalksearch.org/topic/white-paper-purely-p2p-crypto-currency-with-finite-mini-blockchain-195275
or
https://bitcointalksearch.org/topic/mc2-a-cryptocurrency-based-on-a-hybrid-powpos-system-169204
LvM
full member
Activity: 126
Merit: 100
And yes,
I know that some BTC "Heroes" won't even hear evident, irrebuttable facts based on pure logic and thousand year old GAAP.

Its hard to concede we were sailing on the wrong ship all the time, isn't it.
LvM
full member
Activity: 126
Merit: 100
@maaku: We are not "off topic" at all.
Proposed workarounds are the place to discuss the reasons for their (wrongly assumed) necessity.
legendary
Activity: 905
Merit: 1012
Bitcoin transactions are only low-level and potentially complex movement of coins. For accounting, you don't care about individual coins. A real-world payment may be settled by several Bitcoin transactions, or a single Bitcoin transaction may be used to fullfill several payments. But nobody needs to care about this.

You don't care how transactions between business identities are settled. You don't care which coins or dollar bills are used, only between which entities they move. Stop seeing Bitcoin as a ledger - even though many wallet clients show it as such - it is not a ledger of "payments", but of "coin movements".
So why exactly simulate things that nobody cares about?

That may be a valid discussion to have. But it's best done elsewhere: we are now very off topic.
sr. member
Activity: 359
Merit: 250
I completely disagree.

Yes, Bitcoin is exactly the same as other currencies in this respect. But we don't track serial numbers of dollar bills we get, do we? So why would we do accounting based on the currency?
Gold coin doesn't need serial number, does it?

Bitcoin transactions are only low-level and potentially complex movement of coins. For accounting, you don't care about individual coins. A real-world payment may be settled by several Bitcoin transactions, or a single Bitcoin transaction may be used to fullfill several payments. But nobody needs to care about this.

You don't care how transactions between business identities are settled. You don't care which coins or dollar bills are used, only between which entities they move. Stop seeing Bitcoin as a ledger - even though many wallet clients show it as such - it is not a ledger of "payments", but of "coin movements".
So why exactly simulate things that nobody cares about?
legendary
Activity: 1072
Merit: 1181
I completely disagree.

Yes, Bitcoin is exactly the same as other currencies in this respect. But we don't track serial numbers of dollar bills we get, do we? So why would we do accounting based on the currency?

Bitcoin transactions are only low-level and potentially complex movement of coins. For accounting, you don't care about individual coins. A real-world payment may be settled by several Bitcoin transactions, or a single Bitcoin transaction may be used to fullfill several payments. But nobody needs to care about this.

You don't care how transactions between business identities are settled. You don't care which coins or dollar bills are used, only between which entities they move. Stop seeing Bitcoin as a ledger - even though many wallet clients show it as such - it is not a ledger of "payments", but of "coin movements".

Pages:
Jump to: