cbitcoin - Bitcoin implementation in C. Currently in development.

[jgarzik]

Oh, yes, I should clarify.  VeriFones use a persistent battery-backed RAM-based file system, so disk space essentially equals RAM.  I am referring to the size of the library, not how much memory it allocates.   And some of the other devices I've developed for have very limited flash storage where fitting the entire compiled openssl lib takes up significant space.

Then link statically.  Or use one of the many embedded tools out there that ensures your lib has only the code your filesystem actually uses.

This is a solved problem, and does not exclude OpenSSL use in any way.

Also for the VeriFones they don't use GCC so sometimes things take refactoring for their dinosaur compiler to be able to handle it (and makefiles in particular).  Of course I understand having outdated tools is sucky, but that's also why you can find these things on eBay for so cheap.  The Omni 3200 model has an even older DOS-based compiler, but someone who bites the bullet and makes a working app for it suddenly breathes new life into a $30-on-eBay all-in-one-computer with a printer to boot.

And OpenSSL likely supports outdated OS's and tools...  they maintain support for MS-DOS to this day because that remains a common embedded target.

[1714843464]

1714843464

[1714843464]

1714843464

[1714843464]

1714843464

[2112]

Would people be more universally happy if my library required developers using the library to pass cryptographic functionality to the library using function pointers?
Good idea?

No, nobody is planning on swapping the low-level crypto layer at runtime. If you want to abstract it do so using preprocessor macros. I have two other important suggestions for a from-the-scratch implementation:

1) at all times maintain the code as endian-neutral and with proper alignment. If you don't have a Macintosh OSX 10.[456], then build yourself a Hackintosh with Rosetta and test your code using "gcc -arch ppc"
2) resolve the critical inversion of control issue that is present in the Satoshi client. I wrote an post about this a while back. I'll put the link directly to it once I find it. Here they are:

https://bitcointalk.org/index.php?topic=44330.msg538044#msg538044
https://bitcointalk.org/index.php?topic=55842.msg664634#msg664634

Good luck.

[jothan]

It is rarely a good idea to reinvent the wheel, when it comes to security-sensitive, time-tested, well-reviewed-by-experts cryptography code.

This.  Also why is avoiding dependency on OpenSSL important?  Something I am missing?

If you ripped the code from OpenSSL it would work fine.  The devices just don't have gobs of memory for libraries and they have their own compiler that has idiosyncrasies that make it not compile everything that can be compiled in Linux.  Cause it is not Linux.

This would be a 32 bit CPU, no need for 8 bits.

Would Nettle fill the bill ? Crypto routines only, no SSL/TLS. I think GnuTLS has a Nettle extension for ECC/ECDSA.

http://www.lysator.liu.se/~nisse/nettle/

[MatthewLM]

Would people be more universally happy if my library required developers using the library to pass cryptographic functionality to the library using function pointers?
Good idea?

No, nobody is planning on swapping the low-level crypto layer at runtime. If you want to abstract it do so using preprocessor macros. I have two other important suggestions for a from-the-scratch implementation:

1) at all times maintain the code as endian-neutral and with proper alignment. If you don't have a Macintosh OSX 10.[456], then build yourself a Hackintosh with Rosetta and test your code using "gcc -arch ppc"
2) resolve the critical inversion of control issue that is present in the Satoshi client. I wrote an post about this a while back. I'll put the link directly to it once I find it. Here they are:

https://bitcointalk.org/index.php?topic=44330.msg538044#msg538044
https://bitcointalk.org/index.php?topic=55842.msg664634#msg664634

Good luck.

1. So you are saying test my code works on both x86-64 and ppc architectures? Well I'm writing it in C with no dependencies or assembly so no reason why not as long as I follow the usual guidelines for programming portable C code.

2. You mean to keep all the components separated? Well this is the plan and I was asking if I should completely separate the cryptography code. With function pointers dependency injection can be done. I'll likely do something like that for threading functionality, without having a dependency on a threading library. I could include the cryptography with the library but it seems it might cause controversy and leaving the cryptography code outside the library satisfies portability and flexibility concerns.

Would Nettle fill the bill ? Crypto routines only, no SSL/TLS. I think GnuTLS has a Nettle extension for ECC/ECDSA.

http://www.lysator.liu.se/~nisse/nettle/

I don't see why not allow people to choose what they want. It cannot be hard to create wrapper functions around these libraries to pass these functions with functionality like void (*sha256)(u_int8_t *, u_int16_t ,u_int8 [32]) or something similar.

[doldgigger]

Would people be more universally happy if my library required developers using the library to pass cryptographic functionality to the library using function pointers?
Good idea?

No, nobody is planning on swapping the low-level crypto layer at runtime. If you want to abstract it do so using preprocessor macros.

Even though swapping the crypto layer at runtime is unlikely, function pointers are the more flexible alternative as they allow the developer to choose his crypto layer without having to recompile the bitcoin library.

Just have a look at the OpenSSL library: When you want to swap the memory allocator there, you also do it through function pointers, not preprocessor macros. Still, for obvious reasons nobody will want to switch the allocator at runtime...

[MatthewLM]

It is perhaps conceivable that there are some one set of cryptography functions that provide better performance but less security and another set that are slower but provide greater security. A programmer may switch the functions to use the increased security when it is needed or whatever.

But this is not the point in using function pointers, by using function pointers the cryptography functions can be chosen by the programmer using the library and can be configured when the program starts. This is the primary reason. With great flexibility the library can be used as a single dynamic library across various applications; indeed the library will not need to be recompiled for changing requirements.

[2112]

1. So you are saying test my code works on both x86-64 and ppc architectures? Well I'm writing it in C with no dependencies or assembly so no reason why not as long as I follow the usual guidelines for programming portable C code.

What I meant to convey is the following: the Bitcoin protocol itself contains a multitude of design errors related to byte-order and word-alignment. Those errors are compounded by additional errors in the Satoshi client implementation. If you really plan on writing a portable code you'll need to fix those errors in implementation and work around the errors in protocol to maintain the wire compatibility. This is a nontrivial undertaking. If you don't have access to a native big-endian platform like SPARC or z/Arch, then the cheapest way to debug those problem is by working under OS/X.

2. You mean to keep all the components separated? Well this is the plan and I was asking if I should completely separate the cryptography code. With function pointers dependency injection can be done. I'll likely do something like that for threading functionality, without having a dependency on a threading library. I could include the cryptography with the library but it seems it might cause controversy and leaving the cryptography code outside the library satisfies portability and flexibility concerns.

What I meant to convery is the following: the Satoshi client implementation is  non-deterministic and non-testable (even while single-threaded) due to to horrible architectural choice of wrapping a stochastic knapsack solver for coin selection and fee calculation inside a control-inverted subroutine that is used in sendtoaddress() API. You'll need to seriously re-architect the API to come up with a deterministic library that will produce deterministic fees with non-trivial wallets.

[2112]

Even though swapping the crypto layer at runtime is unlikely, function pointers are the more flexible alternative as they allow the developer to choose his crypto layer without having to recompile the bitcoin library.

For any platform where the above would be useful, the following is sufficient:
1) declare the appropriate entry points as "extern";
2) use the platform's native dynamic linking apparatus.

Using additional layer of indirection is completely pointless and has the following disadvantages:
1) it defeats many optimizations that the tool-chain could apply.
2) it defeats many automatic static-analysis and debugging tools.
3) slows down the resulting code (especially if the CPU doesn't have a branch predictor) and increases the energy consumption during execution (more CPU instructions and more cache misses).

[jgarzik]

Even though swapping the crypto layer at runtime is unlikely, function pointers are the more flexible alternative as they allow the developer to choose his crypto layer without having to recompile the bitcoin library.

For any platform where the above would be useful, the following is sufficient:
1) declare the appropriate entry points as "extern";
2) use the platform's native dynamic linking apparatus.

Using additional layer of indirection is completely pointless and has the following disadvantages:
1) it defeats many optimizations that the tool-chain could apply.
2) it defeats many automatic static-analysis and debugging tools.
3) slows down the resulting code (especially if the CPU doesn't have a branch predictor) and increases the energy consumption during execution (more CPU instructions and more cache misses).

All true.

Nevertheless, a wide swath of very fundamental libs provide hooks for similarly fundamental services, most notably memory allocation and m-t locking primitives.

...regardless, all this is really discussing useless details.  The main focus, I hope, should be that cbitcoin is actually doing something unique to bitcoin like parsing blocks and talking network, and not simply wasting a lot of time reimplementing basic software services like crypto or hash or data codec.

[MatthewLM]

Remember, anyone would be free to put in cryptography code directly into their own modified versions of the library. Makes sense, at least for now, to use function pointers I think.

[MatthewLM]

The base 58 conversion is working, time to move on. Could do with some more varied testing but for now the tests will do (Contributions to testing are more than welcome).

I'm all ears to suggestions. Now is the best time to pass suggestions to me as it's early on in development.

[realnowhereman]

Development has kind of stalled lately, but in case it's of any use to you..

https://github.com/andyparkins/additup

It's C++ so won't be copy-and-pastable.  But it talks enough of the protocol to receive and parse blocks and transactions and has base58 (or anything else if you wanted it) support; plus a small test app to manipulate keys and addresses.

[MatthewLM]

Thanks. It may be useful to refer to parts that I can't get from bitcoinj such as the script interpreter. 

It seems I've made a little problem. I'm storing bitcoin addresses backwards at the moment since my base-58 conversion code works with little-endian data. Probably makes sense to reverse the result of the base-58 conversion so they are stored the right way around instead of reversing hashes and whatever.

etotheipi was right about the endianness issue! :-)

I have to make some interesting decisions. Should I have a reference counted string structure? It might help with the bitcoin address strings.

[realnowhereman]

Thanks. It may be useful to refer to parts that I can't get from bitcoinj such as the script interpreter. 

Yep; the interpreter is there and most of the ops; except (of course) for the difficult ones that actually check signatures :-)

It seems I've made a little problem. I'm storing bitcoin addresses backwards at the moment since my base-58 conversion code works with little-endian data. Probably makes sense to reverse the result of the base-58 conversion so they are stored the right way around instead of reversing hashes and whatever.

etotheipi was right about the endianness issue! :-)

Ain't that the truth.

I have to make some interesting decisions. Should I have a reference counted string structure? It might help with the bitcoin address strings.

Just abstract your string access to a set of routines, then you can make that decision later.  First pass: just use library code.

[MatthewLM]

Well I decided the easiest and most sensible thing to do was indeed make a new structure inheriting CBObject named CBString as a wrapper for strings which does reference counting. Then it is also consistent with everything else.

Addresses work! I think I'll start working on the script interpreter next.

[Haplo]

If you're going to rewrite C++ in C (by building virtual function tables yourself), why not code it in C++ in the first place? If compatibility is a problem, you can always expose a C interface to the code.

Because C++ has craptastic performance and tramples all over C conventions, both for no reason. -The Linux Kernel Dev Team

Also why gnome decided to start from scratch with gobject, although I can't vouch for gobject's characteristics either.

That said, I approve of this project, and will probably donate to that end soonish.

Thanks. It may be useful to refer to parts that I can't get from bitcoinj such as the script interpreter. 

It seems I've made a little problem. I'm storing bitcoin addresses backwards at the moment since my base-58 conversion code works with little-endian data. Probably makes sense to reverse the result of the base-58 conversion so they are stored the right way around instead of reversing hashes and whatever.

etotheipi was right about the endianness issue! :-)

I have to make some interesting decisions. Should I have a reference counted string structure? It might help with the bitcoin address strings.

I don't see what reference counting has to do with endianness, but generally it's only useful for memory management of long-lived objects. Are you really writing your own memory management code? o.0

[GroundRod]

A project after my own heart, will be checking in from time to time, see if I can make sense of some of the things your talking about. 

Wish I had more time this summer, this would be a fun one for me too...if by chance I get to the point of being helpful, will let you know MatthewLM!

[MatthewLM]

If you're going to rewrite C++ in C (by building virtual function tables yourself), why not code it in C++ in the first place? If compatibility is a problem, you can always expose a C interface to the code.

Because C++ has craptastic performance and tramples all over C conventions, both for no reason. -The Linux Kernel Dev Team

"you can write object-oriented code (useful for filesystems etc) in C, _without_ the crap that is C++." That made me smile.

People tell me C++ can be just as efficient as C. Whether or not there is a performance issue, I don't care. I don't like C++, I like C.

That said, I approve of this project, and will probably donate to that end soonish.

Well that would be very kind, thank you. 

I don't see what reference counting has to do with endianness, but generally it's only useful for memory management of long-lived objects. Are you really writing your own memory management code? o.0

In my post I was talking about two separate issues. The endianness is a bit annoying but it's fine and I did decide to use reference counting for strings in the end.

The memory management is a simple reference counter. It is nothing complicated and makes the library much more straight-forward when passing objects everywhere, as no-doubt will be the case with a library like this. You can see what I've done by looking at the CBObject files. Look at the testCBAddress.c file for an example of using a CBAddress object with memory management included.

A project after my own heart, will be checking in from time to time, see if I can make sense of some of the things your talking about. 

Wish I had more time this summer, this would be a fun one for me too...if by chance I get to the point of being helpful, will let you know MatthewLM!

Thanks! PM me anytime or send an email to cbitcoin@thelibertyportal.com.

Next I'm going to implement the script interpreter. A lot of op-codes to do and some complexities here and there but I think it wont be too difficult. I will probably start on saturday since I'm busy until then with other things.

[Haplo]

I don't see what reference counting has to do with endianness, but generally it's only useful for memory management of long-lived objects. Are you really writing your own memory management code? o.0

In my post I was talking about two separate issues. The endianness is a bit annoying but it's fine and I did decide to use reference counting for strings in the end.

The memory management is a simple reference counter. It is nothing complicated and makes the library much more straight-forward when passing objects everywhere, as no-doubt will be the case with a library like this. You can see what I've done by looking at the CBObject files. Look at the testCBAddress.c file for an example of using a CBAddress object with memory management included.

Ah gotcha. I feel that though, retain/release is at least 10 times easier than trying to place deallocs correctly (which is sometimes impossible). You mightcould use an already-been-designed C garbage collector instead and save yourself the trouble in that case. Refcounting is very inefficient when many objects die, and overall doesn't perform any better than a GC, which is zero effort and no chance of screwing anything up .

Honestly, weak-typed imperative languages suck for memory management x.x

[MatthewLM]

Using a tracing garbage collector might increase performance a tiny amount but at the cost of portability. It would add a dependency to the library that I don't want. The reference counting is simple enough in my opinion. Reference counting can be optimised by removing redundant retain/release calls and in fact might make the library easier to use. Here is an example of what I might do:

At the moment, as shown in the testCBAddress code, you make a CBAddress object like this:

Code:

CBString * addstr = CBNewStringByCopyingCString("1D5A1q5d192j5gYuWiP3CSE5fcaaZxe6E9");
CBAddress * add = CBNewAddressFromString(addstr, false, &events, &dep);
CBGetObjectVT(addstr)->release(&addstr);

As you can see the CBString is no longer needed by the calling function, so it is released. This is a redundant release. The CBNewAddressFromString constructor can be modified so that it assumes control over the reference of the calling function. That means the constructor no longer retains the object. This removes the need for a retain and a release call. THe code could be written like this:

Code:

CBAddress * add = CBNewAddressFromString(CBNewStringByCopyingCString("1D5A1q5d192j5gYuWiP3CSE5fcaaZxe6E9"), false, &events, &dep);

The CBAddress object makes a reference to the CBString, assuming the calling function no longer needs it. However in the cases where the function will need the CBString, something like this is needed:

Code:

CBString * addstr =  CBNewStringByCopyingCString("1D5A1q5d192j5gYuWiP3CSE5fcaaZxe6E9");
CBGetObjectVT(addstr)->retain(addstr);
CBAddress * add = CBNewAddressFromString(addstr, false, &events, &dep);
// Continue using CBString

In fact if caching is enabled by passing true to the second argument in CBNewAddressFromString, then the calling function doesn't need to call retain on the CBString until the CBAddress is released, since the CBAddress would keep the CBString. This level of optimisation is of-course more confusing and probably practically worthless. It could also introduce problems with future compatibility. I don't want my library to guarantee that an object will hold another object for it's lifetime.

But the method of making the calling function responsible for retaining an object if it needs it after passing it to another object could make some things easier. Perhaps I could make special constructors like CBNewAddressByTakingString which assumes the calling function no longer needs the reference. And these constructors can be made for particular objects where it may be common that another object will no longer be needed after passing it to the object. So you'd have something like this:

Code:

CBAddress * add = CBNewAddressByTakingString(CBNewStringByCopyingCString("1D5A1q5d192j5gYuWiP3CSE5fcaaZxe6E9"), false, &events, &dep);

Maybe calling it CBNewAddressByStealingString would avoid any confusion. I will of-course make such things as clear as possible in the documentation.

So question: Should all constructors and methods that take objects not retain them so that the calling function needs to have a retain if necessary, should it only be some methods/constructors (Clearly named to avoid confusion), or none like it is now?