BIP39 describes how to generate a multi-word phrase and then how to convert it to a seed. It states that phrase is directly hashed into a binary seed, so it gives us plausible deniability ("any phrase can work"), but at the same time the phrase contains the checksum, so I can't provide "any" phrase. If I tell some guys another phrase that happens to have a broken checksum, that will easily notice that. Should I understand that "plausible deniability" applies only to a set of all "valid" phrases, i.e. those with valid checksum? Maybe this should be clarified better in the BIP.

First, an initial entropy of ENT bits is generated. A checksum is generated by taking the first (ENT / 32) bits of its SHA256 hash. This checksum is appended to the end of the initial entropy.

Described method also provides plausible deniability, because every passphrase generates a valid seed (and thus deterministic wallet) but only the correct one will make the desired wallet available.

https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki

I want to start a discussion about deterministic signatures in the context of RNG failures, hardware wallets' auditability, malleability and CompactSignature. And wrap everything in a single canonical specification.

Here's the proposal. It specifies how to produce k deterministically from the message hash and a private key. Also specifies canonical format for the signature and CompactSignature algorithm. This is an opportunity to have a single BIP to cover everything regarding signatures that we need in Bitcoin, so it is easy for developers to understand signatures, learn about hazards and embrace best practice.
https://github.com/oleganza/bips/blob/master/bip-oleganza-detsig.mediawiki

Previous discussion on the topic: https://bitcointalk.org/index.php?topic=285142.0

Hi,

My name is Oleg Andreev, I work on iOS/OSX wallet and CoreBitcoin - a clean and well-documented Bitcoin toolkit in Objective-C.

As you all know, wallets are typically encrypted with a password (using some key stretching algorithm like PBKDF2 or Scrypt). Since the password is weaker than a purely random 128+ bit key, it's better if the user keeps their wallet in some private location that is relatively hard to access. Such backup is better not to be thrown around on popular hosting services like Gmail or Dropbox. HD wallets (BIP32) improve user experience by requiring to secure only the master key and only once. The rest of the keys can be derived later to retrieve the funds.

The problem is, wallets may have extra metadata which cannot be derived from the master key. E.g. user notes, invoice info, or even more importantly, multisig pubkeys and P2SH scripts. To redeem a P2SH payment one needs to know original script which must be stored somewhere and securely backed up before any transaction is made involving that script. Asking the user to backup his password-protected wallet before each such transaction would be cumbersome.

I suggest additional backup scheme where the user's wallet is encrypted using a truly unpredictable AES key derived from the wallet's master key. If the master key itself is not derived from a weak passphrase, but has 128+ bits on entropy, the AES key would be equally strong. Therefore the wallet can be automatically encrypted and uploaded to one or more backup services without any user action. When the user needs to restore the backup, he will have to restore the original master key first and then make his wallet connect to backup servers and retrieve the most recent backup of full wallet contents. Backup servers cannot possibly decrypt wallets with bruteforce, they only need to allow reliable retrieval. User's wallet may download the backup at regular intervals to detect if one of the servers lost his data or went offline. In such case, another server may be used or the user may be warned to make a manual backup as soon as possible.

Proposal:
https://github.com/oleganza/bips/blob/master/bip-0081.mediawiki
UPD: https://github.com/oleganza/bips/blob/master/bip-oleganza-backups.mediawiki
UPD2: https://github.com/oleganza/bitcoin-papers/blob/master/AutomaticEncryptedWalletBackups.md

PS. I didn't want to create a pull request as the text might change and I don't want to have troubles with rebase (and accidentally lose connection to a pull request). Github Issues seem to be disabled in the bitcoin/bips repo. So lets discuss it here for now.

I was searching how to make blind signatures based on standard ECDSA and couldn't find anything useful. I found a 10-year old paper with a proposal, but it proposes a formula incompatible with the standard ECDSA signature that is used in Bitcoin: http://mshwang.ccs.asia.edu.tw/www/myjournal/P191.pdf

My goal is to lock funds in a usual multisig transaction where private keys belong to N friends. When they sign my transaction, they should not be able to see what is being spent or where it goes from and to. Splitting the key using SSSS ("Shamir's Secret Sharing Scheme") is not the perfect option as the recovered secret must be applied on a single machine that may not be trusted (think regular Win PC). When multisig transaction is being signed by every participant, no machine is able to spend the funds arbitrarily.

My question to experts is whether the following algorithm that uses a simple multiplication factor is workable:

TL;DR:

1. You send money to x*pubkey instead of pubkey. (x is your secret integer - "blinding factor")
2. You ask third party to sign (hash/x) instead of hash of tx itself.
3. You use x*signature to redeem funds.

More specifically:

Part 1. Sending the funds:

1. Trusted party gives you their public key D (D = d*G, d — private key, G — standard generator point).
2. You choose secret random integer x ("blinding factor")
3. Compute public key D2 = x*D
4. Send money to D2 (it could be one of the keys in multisig script).
5. Store in your encrypted wallet info about x, D and the transaction to spend it later.

Part 2. Redeeming funds:

1. Compute the hash h = signatureHash(tx).
2. Compute h2 = (h / x) mod n (n — order of our curve secp256k)
3. Send to the third party h2 to be signed with their private key d.
4. Third party sends back to you a usual ECDSA signature (r,s) where s = (k^-1)(h2 + d*r)
5. You multiply s by x and get s2 = x*s = (k^-1)(x*h2 + x*d*r)
6. This new signature (r,s2) is equivalent to a signature of h signed with a private key x*d.
7. Neither you, nor third party knows x*d (only you know x, only they know d), but you know x*d*G = x*D = D2 — a public key derived from their public key.
8. So the signature (r,s2) is a valid signature of message h verifiable by public key D2=x*D.
9. You publish your transaction with signature (r,s2) and the third party cannot know that it was signed by them.

Is there a fault somewhere? What do you think?

Thanks.

EDIT: This scheme fails. As gmaxwell pointed out below, r is not blinded and will be recognized by the signing party.

Sorry for the repost from here: https://bitcointalk.org/index.php?topic=321819.0

Who is in Vienna this weekend? I planned a visit in March when Unsystem was announced, but it was cancelled and I am going anyway.

Would like to meet some folks in Vienna.

Hi there,

I'm spending 4 days in Vienna from 31st of October till 3rd of November. Who's in Vienna these days and wants to chat about futuristic tech stuff related to Bitcoin? I planned a trip for Unsystem conference, but it was cancelled. So I thought, how about a meet up instead?

Edit-2: this scheme is completely broken as pointed out by Mike Hearn below (allows double spending).


If it was already proposed somewhere, I'll appreciate the link.

Problem: as more people use Bitcoin, number of spendable transactions inevitably grows (UTXO set). Today full nodes must maintain full UTXO set ("previous transactions") to verify incoming transactions. This is a duplicated effort which would be nice to distribute more fairly. (Also, full efficient UTXO index today takes >100 Gb, so miners have to simply scan blockchain to find parents.)

Solution:

1. Each full node only stores all block headers that it considers valid (not simply most POW-ed, but really valid).

2. Users send not only a transaction, but all parent transactions and their merkle branches.

3. Full node does not need to lookup UTXO to check if the parents are valid. This part of UTXO is already provided by the sender. Node needs only to check that merkle branches are valid and point to a block that was already validated.

4. Mining nodes collect all incoming transactions this way. When the block is mined, they don't need to keep those transactions in UTXO.

5. Some nodes still need to store full blocks to send to users — so users know if their transactions are included and where. So they can further send parent txs for each new tx.

As a result, UTXO is proportionally distributed among all users with insignificant overhead for network bandwidth. (At least, now users pay for that overhead, not miners for scanning the blockchain.)

This does not address the blockchain storage. Someone should store all or some blocks so users can know about merkle branches for their spendable transactions. But block storage does not require high-performance indexing like UTXO.

Block storage can be further reduced by having nodes store random portions of old history or not having old blocks at all - only blocks for the last month (so that receiving clients have enough time to catch up and find their new spendable txs). Full history could be provided for payment by specialized services.


Edit: this behavior can be an extension to a protocol which can be promoted by lower transaction fees. If the miner needs to lookup your parent transactions, you'd have to pay for that. If you send them along your own, it'll be cheaper. In other words, your tx priority is lower if it incurs extra validation costs.

Edit-2: as pointed out by Mike Hearn below, this scheme allows double-spending as node does not check if the inputs were already spent.

There are generally 3 options that people speculate about: either Satoshi works for something like NSA (in US, UK or other country), or he/she is an academic, or some independent cypherpunk. Option about NSA is two-sided: either Bitcoin is an evil conspiracy against mankind, or it's a creation to save the world by someone in the knowledge within a well-funded government agency.

What's your speculation?

While writing documentation to CoreBitcoin (Objective-C implementation) I tend to explain some terms over and over again. To avoid repetition, I decided to come up with one more-or-less complete glossary of all technical Bitcoin terms from "difficulty" to "scriptPubSig". This glossary immediately answers a lot of questions that I myself had while learning how Bitcoin works. I hope it will greatly help newcomers to understand what people are talking about.

Here's the latest version of the glossary:
https://github.com/oleganza/CoreBitcoin/blob/master/GLOSSARY.md

Feel free to comment or even edit it on Github if you find mistakes. Thanks!

I'm looking at script.h in BitcoinQT, in a definition of ValueString() and see this:

Code:

inline std::string ValueString(const std::vector<unsigned char>& vch)
{
    if (vch.size() <= 4)
        return strprintf("%d", CBigNum(vch).getint());
    else
        return HexStr(vch);
}

Which creates some ambiguity: it can output 1002003004 for both decimal number 1002003004 (which fits in 4-byte int) and for hex representation of 5-byte data 10 02 00 30 04.

Is it okay? Do we have some other non-ambiguous encoding of data? I don't see any string parser in BitcoinQT, so maybe it's a non-issue, but bitcoin-ruby has a parser. In case of bitcoin-ruby, it only parses 2, 3, ... 16 as OP_<n>, while 17 would be parsed as 0x17==23. And data 0x16 (==22) would be encoded as "16" and then interpreted as 0x10 (== 16).

In CoreBitcoin (objc implementation) I'd like to avoid ambiguity and be able to correctly parse human-readable scripts.

Hey, I've written on my idea how to make contracts with people who don't really know each other with low cost, no third party.

Ideas based on NashX.com service. Special thanks to Mike Hearn for "Contracts" page on the wiki.

http://blog.oleganza.com/post/58240549599/contracts-without-trust-and-without-a-third-party

TLDR:

1. Two parties independently lock some amount of money in a single Bitcoin transaction without meeting in person or trusting anyone.
2. This money can be unlocked only when both agree with that. If at least one party does not want to unlock the deposit, another party cannot do anything about it.
3. Both parties can unlock deposit only atomically, for both of them. No one can unlock just for himself.
4. No one else has access to the deposits and neither party can access other party’s money.

Output scripts:

txout1: AlicePubkey CHECKSIGVERIFY SHA256 HashA EQUALVERIFY SHA256 HashB EQUALVERIFY

txout2: BobPubkey CHECKSIGVERIFY SHA256 HashA EQUALVERIFY SHA256 HashB EQUALVERIFY

HashA, HashB are hashes of the secret numbers of each participant. Numbers are revealed when they want to unlock the money.

Amount of deposit should be 200-300% of the price. E.g. if the deal is about 1 BTC worth of merchandise, the deposit should be at least 2 BTC.

NashX ask seller for smaller deposit (100%) because he sends first, but this doesn't seem "fair" for many people. So lets have 300% each, so it does not really matter who sends first. Parties can negotiate how much they lock up, of course.

Ideas?

I don't understand why the wiki says (https://en.bitcoin.it/wiki/Script):

OP_VERIF (0x65) Transaction is invalid even when occuring in an unexecuted OP_IF branch
OP_VERNOTIF (0x66) Transaction is invalid even when occuring in an unexecuted OP_IF branch

From the BitcoinQT code I see that OP_VERIF and OP_VERNOTIF are undefined in the same way as OP_VER or OP_RESERVED. Meaning, if OP_VER is skipped in the if branch, then OP_VERIF is skipped as well.

But the wiki says that tx will be valid if OP_VER is not executed, but will be invalid even if OP_VERIF is not executed. Is it a mistake in the wiki or I miss something here?

Hi there,

I'm building my own wallet app for Mac and iOS. The app will be open source when it's ready. Before that, to do things more efficiently, I open source CoreBitcoin, a clean implementation of Bitcoin protocol in Objective-C (with bits of OpenSSL).

The library is not complete yet, but with a help of volunteers I may finish it faster. It is also meant to be cleaner and easier to read by newbies than Satoshi code, bitcoin-ruby or libbitcoin. I try to make every step explicit, documented and simple.

https://github.com/oleganza/CoreBitcoin

Feedback is welcome. Thanks.

Today I've timestamped a git commit ID of my project using brainwallet.org without any effort.

Here's how to do it:
http://blog.oleganza.com/post/52237596486/today-ive-timestamped-my-secret-source-code-with

TLDR:

My commit: e09d665d7ffd70d5d6b672305e744916c3c827e9

To verify the timestamp, do the following:

1. Go to brainwallet.org
2. Select “Secret Exponent” and paste there commit ID e09d665…
3. See the resulting address: 1AAX6PJEm2FLXT6RoRAUzNFmFHnueFGGs1.
4. Go to blockchain.info and find this address.
5. Select the very first transaction: 687c24d…
6. Check that transaction is included in block 239851. Timestamp is 2013-06-05 07:46:41.

I will release the source when it's ready to be tested, some time later this year. Meanwhile I make sure that no one will claim that I picked someone's idea if they happen to come up with the same idea as me later, but before I release my app.

I'm reading Bitcoin-QT source code and don't quite understand the difference between CPrivKey and CSecret.

key.h has some explanation:

// CPrivKey is a serialized private key, with all parameters included (279 bytes)
typedef std::vector<unsigned char, secure_allocator<unsigned char> > CPrivKey;
// CSecret is a serialization of just the secret parameter (32 bytes)
typedef std::vector<unsigned char, secure_allocator<unsigned char> > CSecret;

Looks like what we usually call a private key is a short 32 byte "secret parameter". But then I see code that uses CPrivKey in wallet.cpp. I would go to OpenSSL to study the difference between EC_KEY_get0_private_key (used in CKey::GetSecret) and i2d_ECPrivateKey (used in CKey::GetPrivKey), but OpenSSL .h documentation does not really explain much.

Why do we need a big CPrivKey when you can always generate key pair from just a secret? Where can I learn more about practical aspects of ECDSA (I already have a good theoretical guide)?

Thanks.

Interesting. I have a transaction that sends around 0.1 BTC from a single 0.4 BTC output that was confirmed >100 blocks before. It is not included in any block for 7 hours already. I've been sending similar transactions with zero fees before from the same blockchain.info iPhone app and it was always confirmed quickly enough. What could be the reason for the problem? Is it just the mining fee that is suddenly required, or we are hitting block size limit, or one of the addresses could be banned? (Destination addresses are a new one, not SatoshiDice, and the same my address for the change.)

Wouldn't it be nice if we could know how diverse is bitcoin software? Like when we consult web browser User-Agent distribution when deciding which new features to support and which old browsers to ignore. This could help miners see if they are in a risky position when 50% are running one software and 50% the other. Or if you are running a software which represents only 10% of the blocks and probably should be compatible with others to avoid accidental losses. This also could help developers see how quickly new updates are propagated, so new features can be rolled out more reliably.

My suggestion is to put a name of the software, release version and a partial git commit id.

E.g. "bitcoind 0.7.2 32a928e1" would mean Satoshi client version 0.7.2. Commit id would identify specific commit (possibly a patch to the released version). It would be nice if patched versions were published somewhere on Github, so people could see what exact changes should be taken into account.

This is not meant to be a strict machine-readable format (like "block version" from BIP 34, or protocol version from API), only an identifier for statistical purposes.

What do you think?

It's not a novel idea, Gavin and others already mentioned it in other threads. Just wanted to gather your opinions in one place.

We have roughly two types of wallets: either store the full blockchain ("full node"), or only keep the password/private keys and trust other full nodes about transaction confirmation status ("light node"). All full nodes have to validate all the transactions themselves and keep the whole history. This is essential to miners (to rearrange transactions for the next block), but not so much to the rest of us. Regular folks don't like storing gigabytes of blockchain, but might be interested in having extra security for low cost.

Imagine a wallet which has a setting "amount of storage allowed for transactions" with values like 50 Mb, 100 Mb, 200 Mb. The wallet will store all the block headers, but receive full blocks and only store some random portion of transactions and validate them against what it has in the storage already (and, as an option, store all transactions involved in his own addresses). If the wallet detects an invalid block, it can be announced to the peers immediately, so they can validate it fully themselves (by downloading missing transactions from others). This is in contrast to a server which may maliciously or by accident present incorrect history to its clients for some time.

Lets say the blockchain occupies 100 Gb a couple of years from now and every user wants to store around 100 Mb. This will make him validate 0.1% of all transactions (p=0.001). If N clients are using such clients, the lowest probability of catching the bad transaction in a bad block is (1–(1–p)^N). To make it 99,995% only 10000 clients should use the app. If a number of clients increases 10 times, the percentage of validated transactions can be divided by 10 and the same security level will remain.

Another way to do it: validate only your transactions. E.g. if you are a shop owner, you may only keep histories of transactions that are important to you and prune those that are no longer relevant (can be re-downloaded again when needed). If every shop owner does that, they collectively will still validate the whole blockchain, but wasting much less computational resources.

Today this scheme is not really needed because the blocks are fast to validate, and the whole blockchain is relatively small. But when Bitcoin gets mass adoption and people would want it to scale, this might one of the ways to do it. (Especially if blockchain grows faster than the hardware.)

What do you think?

Mining is based on finding partial collision of SHA-256(SHA256(block header)). Bitcoins get more expensive, creating incentives to develop cheaper and faster hardware that finds these partial collisions. Another way to make profit is to make a cryptanalysis of double SHA256 in order to figure out a faster way to produce a partial collision. I wonder how many people would try to do that in order to gain more hashing power for themselves.

I myself don't have much idea of the complexity of this task, but for those who understand hash functions better, it could be an interesting question to ponder. Imagine, you find a way to get partial collision 2 times faster: you can increase productivity of the existing GPU farm by a factor of 2 (unfortunately, ASICs will need to be changed since the algorithm would be different, but it's not your problem). Discuss.

I've wrote on my blog about various economic forces behind block size limit. Here's the most important part:

If the miners hit the block limit, it would only mean one thing: there is a desire to process more transactions, but historical untested agreement does not allow it. Then miners will either raise the limit (the smaller the increment, the bigger support it will have), or transaction fees will go up as people compete for the space in blocks. As transaction fees go up, not only miners, but also regular users and service companies using the full blockchain would desire to raise the limit. So it will be easier to make a consensus as demand grows.

My prediction is that the block size limit will probably never be abolished, but will be constantly pushed up by a factor of two as amount of transactions approaches the limit. Maybe after a couple of updates, people would decide that it’s safe to abolish the limit completely if it is cheaper to account for it, than to have uncertainty of a hard fork.

Other concerns are addressed in the full post:
http://blog.oleganza.com/post/43677417318/economics-of-block-size-limit

I did not go deep into analyzing complex schemes like adjustable size limit. Please feel free correct me where I am wrong.