Topic: Bitcoin source from November 2008. - page 3. (Read 15362 times)

// Copyright (c) 2008 Satoshi Nakamoto
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

#include "headers.h"
#include 

void ThreadMessageHandler2(void* parg);
void ThreadSocketHandler2(void* parg);
void ThreadOpenConnections2(void* parg);






//
// Global state variables
//
bool fClient = false;
uint64 nLocalServices = (fClient ? 0 : NODE_NETWORK);
CAddress addrLocalHost(0, DEFAULT_PORT, nLocalServices);
CNode nodeLocalHost(INVALID_SOCKET, CAddress("127.0.0.1", nLocalServices));
CNode* pnodeLocalHost = &nodeLocalHost;
bool fShutdown = false;
array vfThreadRunning;
vector vNodes;
CCriticalSection cs_vNodes;
map, CAddress> mapAddresses;
CCriticalSection cs_mapAddresses;
map mapRelay;
deque > vRelayExpiration;
CCriticalSection cs_mapRelay;
map mapAlreadyAskedFor;






bool AddAddress(CAddrDB& addrdb, const CAddress& addr)
{
    CRITICAL_BLOCK(cs_mapAddresses)
    {
        map, CAddress>::iterator it = mapAddresses.find(addr.GetKey());
        if (it == mapAddresses.end())
        {
            // New address
            mapAddresses.insert(make_pair(addr.GetKey(), addr));
            addrdb.WriteAddress(addr);
            return true;
        }
        else
        {
            CAddress& addrFound = (*it).second;
            if ((addrFound.nServices | addr.nServices) != addrFound.nServices)
            {
                // Services have been added
                addrFound.nServices |= addr.nServices;
                addrdb.WriteAddress(addrFound);
                return true;
            }
        }
    }
    return false;
}





void AbandonRequests(void (*fn)(void*, CDataStream&), void* param1)
{
    // If the dialog might get closed before the reply comes back,
    // call this in the destructor so it doesn't get called after it's deleted.
    CRITICAL_BLOCK(cs_vNodes)
    {
        foreach(CNode* pnode, vNodes)
        {
            CRITICAL_BLOCK(pnode->cs_mapRequests)
            {
                for (map::iterator mi = pnode->mapRequests.begin(); mi != pnode->mapRequests.end();)
                {
                    CRequestTracker& tracker = (*mi).second;
                    if (tracker.fn == fn && tracker.param1 == param1)
                        pnode->mapRequests.erase(mi++);
                    else
                        mi++;
                }
            }
        }
    }
}









CNode* FindNode(unsigned int ip)
{
    CRITICAL_BLOCK(cs_vNodes)
    {
        foreach(CNode* pnode, vNodes)
            if (pnode->addr.ip == ip)
                return (pnode);
    }
    return NULL;
}

CNode* FindNode(CAddress addr)
{
    CRITICAL_BLOCK(cs_vNodes)
    {
        foreach(CNode* pnode, vNodes)
            if (pnode->addr == addr)
                return (pnode);
    }
    return NULL;
}

CNode* ConnectNode(CAddress addrConnect, int64 nTimeout)
{
    if (addrConnect.ip == addrLocalHost.ip)
        return NULL;

    // Look for an existing connection
    CNode* pnode = FindNode(addrConnect.ip);
    if (pnode)
    {
        if (nTimeout != 0)
            pnode->AddRef(nTimeout);
        else
            pnode->AddRef();
        return pnode;
    }

    // Connect
    SOCKET hSocket = socket(AF_INET, SOCK_STREAM, 0);
    if (hSocket == INVALID_SOCKET)
    {
        printf("socket failed\n");
        return NULL;
    }

    struct sockaddr_in sockaddr;
    sockaddr.sin_family = AF_INET;
    sockaddr.sin_addr.s_addr = addrConnect.ip;
    sockaddr.sin_port = addrConnect.port;

        /// debug print
        static map mapPrintLimit;
        if (mapPrintLimit[addrConnect.ip] % 20 == 0)
            printf("connecting to %d.%d.%d.%d\n", ((unsigned char*)&sockaddr.sin_addr.s_addr)[0], ((unsigned char*)&sockaddr.sin_addr.s_addr)[1], ((unsigned char*)&sockaddr.sin_addr.s_addr)[2], ((unsigned char*)&sockaddr.sin_addr.s_addr)[3]);

    if (connect(hSocket, (struct sockaddr*)&sockaddr, sizeof(sockaddr)) != SOCKET_ERROR)
    {
            /// debug print
            mapPrintLimit[addrConnect.ip] = 0;
            printf("connected %d.%d.%d.%d\n", ((unsigned char*)&sockaddr.sin_addr.s_addr)[0], ((unsigned char*)&sockaddr.sin_addr.s_addr)[1], ((unsigned char*)&sockaddr.sin_addr.s_addr)[2], ((unsigned char*)&sockaddr.sin_addr.s_addr)[3]);

        // Add node
        CNode* pnode = new CNode(hSocket, addrConnect);
        if (nTimeout != 0)
            pnode->AddRef(nTimeout);
        else
            pnode->AddRef();
        CRITICAL_BLOCK(cs_vNodes)
            vNodes.push_back(pnode);
        return pnode;
    }
    else
    {
        //// todo: need to set last failed connect time, and increment a failed to connect counter
        /// debug print
        if ((mapPrintLimit[addrConnect.ip]++) % 20 == 0)
            printf("connection failed %d\n", WSAGetLastError());
        return NULL;
    }
}

void CNode::Disconnect()
{
    printf("disconnecting node %s\n", addr.ToString().c_str());

    closesocket(hSocket);

    // All of a nodes broadcasts and subscriptions are automatically torn down
    // when it goes down, so a node has to stay up to keep its broadcast going.

    // Cancel and delete unsourced broadcasts
    CRITICAL_BLOCK(cs_mapTables)
        for (map::iterator mi = mapTables.begin(); mi != mapTables.end();)
            AdvertRemoveSource(this, MSG_TABLE, 0, (*(mi++)).second);
    CRITICAL_BLOCK(cs_mapProducts)
        for (map::iterator mi = mapProducts.begin(); mi != mapProducts.end();)
            AdvertRemoveSource(this, MSG_PRODUCT, 0, (*(mi++)).second);

    // Cancel subscriptions
    for (unsigned int nChannel = 0; nChannel < vfSubscribe.size(); nChannel++)
        if (vfSubscribe[nChannel])
            CancelSubscribe(nChannel);
}













void ThreadSocketHandler(void* parg)
{
    IMPLEMENT_RANDOMIZE_STACK(ThreadSocketHandler(parg));

    loop
    {
        vfThreadRunning[0] = true;
        CheckForShutdown(0);
        try
        {
            ThreadSocketHandler2(parg);
        }
        CATCH_PRINT_EXCEPTION("ThreadSocketHandler()")
        vfThreadRunning[0] = false;
        Sleep(5000);
    }
}

void ThreadSocketHandler2(void* parg)
{
    printf("ThreadSocketHandler started\n");
    SOCKET hListenSocket = *(SOCKET*)parg;
    list vNodesDisconnected;
    int nPrevNodeCount = 0;

    loop
    {
        //
        // Disconnect nodes
        //
        CRITICAL_BLOCK(cs_vNodes)
        {
            // Disconnect duplicate connections
            map mapFirst;
            foreach(CNode* pnode, vNodes)
            {
                unsigned int ip = pnode->addr.ip;
                if (mapFirst.count(ip) && addrLocalHost.ip < ip)
                {
                    // In case two nodes connect to each other at once,
                    // the lower ip disconnects its outbound connection
                    CNode* pnodeExtra = mapFirst[ip];

                    if (pnodeExtra->GetRefCount() > (pnodeExtra->fNetworkNode ? 1 : 0))
                        swap(pnodeExtra, pnode);

                    if (pnodeExtra->GetRefCount() <= (pnodeExtra->fNetworkNode ? 1 : 0))
                    {
                        printf("(%d nodes) disconnecting duplicate: %s", vNodes.size(), pnodeExtra->addr.ToString().c_str());
                        if (pnodeExtra->fNetworkNode && !pnode->fNetworkNode)
                        {
                            pnode->AddRef();
                            swap(pnodeExtra->fNetworkNode, pnode->fNetworkNode);
                            pnodeExtra->Release();
                        }
                        pnodeExtra->fDisconnect = true;
                    }
                }
                mapFirst[ip] = pnode;
            }

            // Disconnect unused nodes
            vector vNodesCopy = vNodes;
            foreach(CNode* pnode, vNodesCopy)
            {
                if (pnode->ReadyToDisconnect() && pnode->vRecv.empty() && pnode->vSend.empty())
                {
                    // remove from vNodes
                    vNodes.erase(remove(vNodes.begin(), vNodes.end(), pnode), vNodes.end());
                    pnode->Disconnect();

                    // hold in disconnected pool until all refs are released
                    pnode->nReleaseTime = max(pnode->nReleaseTime, GetTime() + 5 * 60);
                    if (pnode->fNetworkNode)
                        pnode->Release();
                    vNodesDisconnected.push_back(pnode);
                }
            }

            // Delete disconnected nodes
            list vNodesDisconnectedCopy = vNodesDisconnected;
            foreach(CNode* pnode, vNodesDisconnectedCopy)
            {
                // wait until threads are done using it
                if (pnode->GetRefCount() <= 0)
                {
                    bool fDelete = false;
                    TRY_CRITICAL_BLOCK(pnode->cs_vSend)
                     TRY_CRITICAL_BLOCK(pnode->cs_vRecv)
                      TRY_CRITICAL_BLOCK(pnode->cs_mapRequests)
                       TRY_CRITICAL_BLOCK(pnode->cs_inventory)
                        fDelete = true;
                    if (fDelete)
                    {
                        vNodesDisconnected.remove(pnode);
                        delete pnode;
                    }
                }
            }
        }
        if (vNodes.size() != nPrevNodeCount)
        {
            nPrevNodeCount = vNodes.size();
            MainFrameRepaint();
        }


        //
        // Find which sockets have data to receive
        //
        struct timeval timeout;
        timeout.tv_sec  = 0;
        timeout.tv_usec = 50000; // frequency to poll pnode->vSend

        struct fd_set fdsetRecv;
        struct fd_set fdsetSend;
        FD_ZERO(&fdsetRecv);
        FD_ZERO(&fdsetSend);
        SOCKET hSocketMax = 0;
        FD_SET(hListenSocket, &fdsetRecv);
        hSocketMax = max(hSocketMax, hListenSocket);
        CRITICAL_BLOCK(cs_vNodes)
        {
            foreach(CNode* pnode, vNodes)
            {
                FD_SET(pnode->hSocket, &fdsetRecv);
                hSocketMax = max(hSocketMax, pnode->hSocket);
                TRY_CRITICAL_BLOCK(pnode->cs_vSend)
                    if (!pnode->vSend.empty())
                        FD_SET(pnode->hSocket, &fdsetSend);
            }
        }

        vfThreadRunning[0] = false;
        int nSelect = select(hSocketMax + 1, &fdsetRecv, &fdsetSend, NULL, &timeout);
        vfThreadRunning[0] = true;
        CheckForShutdown(0);
        if (nSelect == SOCKET_ERROR)
        {
            int nErr = WSAGetLastError();
            printf("select failed: %d\n", nErr);
            for (int i = 0; i <= hSocketMax; i++)
            {
                FD_SET(i, &fdsetRecv);
                FD_SET(i, &fdsetSend);
            }
            Sleep(timeout.tv_usec/1000);
        }
        LARGE_INTEGER PerformanceCount;
        QueryPerformanceCounter(&PerformanceCount);
        RAND_add(&PerformanceCount.LowPart, sizeof(PerformanceCount.LowPart), 1.0);

        //// debug
        //foreach(CNode* pnode, vNodes)
        //{
        //    printf("vRecv = %-5d ", pnode->vRecv.size());
        //    printf("vSend = %-5d    ", pnode->vSend.size());
        //}
        //printf("\n");


        //
        // Accept new connections
        //
        if (FD_ISSET(hListenSocket, &fdsetRecv))
        {
            struct sockaddr_in sockaddr;
            int len = sizeof(sockaddr);
            SOCKET hSocket = accept(hListenSocket, (struct sockaddr*)&sockaddr, &len);
            CAddress addr(sockaddr.sin_addr.s_addr, sockaddr.sin_port);
            if (hSocket == INVALID_SOCKET)
            {
                if (WSAGetLastError() != WSAEWOULDBLOCK)
                    printf("ERROR ThreadSocketHandler accept failed: %d\n", WSAGetLastError());
            }
            else
            {
                printf("%s accepted connection from %s\n", addrLocalHost.ToString().c_str(), addr.ToString().c_str());
                CNode* pnode = new CNode(hSocket, addr);
                pnode->AddRef();
                pnode->fInbound = true;
                CRITICAL_BLOCK(cs_vNodes)
                    vNodes.push_back(pnode);
            }
        }


        //
        // Service each socket
        //
        vector vNodesCopy;
        CRITICAL_BLOCK(cs_vNodes)
            vNodesCopy = vNodes;
        foreach(CNode* pnode, vNodesCopy)
        {
            CheckForShutdown(0);
            SOCKET hSocket = pnode->hSocket;

            //
            // Receive
            //
            if (FD_ISSET(hSocket, &fdsetRecv))
            {
                TRY_CRITICAL_BLOCK(pnode->cs_vRecv)
                {
                    CDataStream& vRecv = pnode->vRecv;
                    unsigned int nPos = vRecv.size();

                    // typical socket buffer is 8K-64K
                    const unsigned int nBufSize = 0x10000;
                    vRecv.resize(nPos + nBufSize);
                    int nBytes = recv(hSocket, &vRecv[nPos], nBufSize, 0);
                    vRecv.resize(nPos + max(nBytes, 0));
                    if (nBytes == 0)
                    {
                        // socket closed gracefully
                        if (!pnode->fDisconnect)
                            printf("recv: socket closed\n");
                        pnode->fDisconnect = true;
                    }
                    else if (nBytes < 0)
                    {
                        // socket error
                        int nErr = WSAGetLastError();
                        if (nErr != WSAEWOULDBLOCK && nErr != WSAEMSGSIZE && nErr != WSAEINTR && nErr != WSAEINPROGRESS)
                        {
                            if (!pnode->fDisconnect)
                                printf("recv failed: %d\n", nErr);
                            pnode->fDisconnect = true;
                        }
                    }
                }
            }

            //
            // Send
            //
            if (FD_ISSET(hSocket, &fdsetSend))
            {
                TRY_CRITICAL_BLOCK(pnode->cs_vSend)
                {
                    CDataStream& vSend = pnode->vSend;
                    if (!vSend.empty())
                    {
                        int nBytes = send(hSocket, &vSend[0], vSend.size(), 0);
                        if (nBytes > 0)
                        {
                            vSend.erase(vSend.begin(), vSend.begin() + nBytes);
                        }
                        else if (nBytes == 0)
                        {
                            if (pnode->ReadyToDisconnect())
                                pnode->vSend.clear();
                        }
                        else
                        {
                            printf("send error %d\n", nBytes);
                            if (pnode->ReadyToDisconnect())
                                pnode->vSend.clear();
                        }
                    }
                }
            }
        }


        Sleep(10);
    }
}










void ThreadOpenConnections(void* parg)
{
    IMPLEMENT_RANDOMIZE_STACK(ThreadOpenConnections(parg));

    loop
    {
        vfThreadRunning[1] = true;
        CheckForShutdown(1);
        try
        {
            ThreadOpenConnections2(parg);
        }
        CATCH_PRINT_EXCEPTION("ThreadOpenConnections()")
        vfThreadRunning[1] = false;
        Sleep(5000);
    }
}

void ThreadOpenConnections2(void* parg)
{
    printf("ThreadOpenConnections started\n");
    unsigned int nTries = 0;
    loop
    {
        //// number of connections may still need to be increased before release
        // Initiate network connections
        if (vNodes.size() < 5 && vNodes.size() < mapAddresses.size())
        {
            // Make a list of unique class C's
            unsigned char pchIPCMask[4] = { 0xff, 0xff, 0xff, 0x00 };
            unsigned int nIPCMask = *(unsigned int*)pchIPCMask;
            vector vIPC;
            CRITICAL_BLOCK(cs_mapAddresses)
            {
                vIPC.reserve(mapAddresses.size());
                unsigned int nPrev = 0;
                foreach(const PAIRTYPE(vector, CAddress)& item, mapAddresses)
                {
                    const CAddress& addr = item.second;
                    if (!addr.IsIPv4())
                        continue;

                    // Taking advantage of mapAddresses being in sorted order,
                    // with IPs of the same class C grouped together.
                    unsigned int ipC = addr.ip & nIPCMask;
                    if (ipC != nPrev)
                        vIPC.push_back(nPrev = ipC);
                }
            }

            //
            // The IP selection process is designed to limit vulnerability to address flooding.
            // Any class C (a.b.c.?) has an equal chance of being chosen, then an IP is
            // chosen within the class C.  An attacker may be able to allocate many IPs, but
            // they would normally be concentrated in blocks of class C's.  They can hog the
            // attention within their class C, but not the whole IP address space overall.
            // A lone node in a class C will get as much attention as someone holding all 255
            // IPs in another class C.
            //
            bool fSuccess = false;
            int nLimit = vIPC.size();
            while (!fSuccess && nLimit-- > 0)
            {
                // Choose a random class C
                uint64 nRand;
                RAND_bytes((unsigned char*)&nRand, sizeof(nRand));
                unsigned int ipC = vIPC[nRand % vIPC.size()];

                // Organize all addresses in the class C by IP
                map > mapIP;
                CRITICAL_BLOCK(cs_mapAddresses)
                {
                    for (map, CAddress>::iterator mi = mapAddresses.lower_bound(CAddress(ipC, 0).GetKey());
                         mi != mapAddresses.upper_bound(CAddress(ipC | ~nIPCMask, 0xffff).GetKey());
                         ++mi)
                    {
                        const CAddress& addr = (*mi).second;
                        mapIP[addr.ip].push_back(addr);
                    }
                }

                // Choose a random IP in the class C
                RAND_bytes((unsigned char*)&nRand, sizeof(nRand));
                map >::iterator mi = mapIP.begin();
                advance(mi, nRand % mapIP.size());

                // Once we've chosen an IP, we'll try every given port before moving on
                foreach(const CAddress& addrConnect, (*mi).second)
                {
                    if (addrConnect.ip == addrLocalHost.ip || !addrConnect.IsIPv4() || FindNode(addrConnect.ip))
                        continue;

                    CNode* pnode = ConnectNode(addrConnect);
                    if (!pnode)
                        continue;
                    pnode->fNetworkNode = true;

                    // Advertise our address
                    vector vAddrToSend;
                    vAddrToSend.push_back(addrLocalHost);
                    pnode->PushMessage("addr", vAddrToSend);

                    // Get as many addresses as we can
                    pnode->PushMessage("getaddr");

                    ////// should the one on the receiving end do this too?
                    // Subscribe our local subscription list
                    const unsigned int nHops = 0;
                    for (unsigned int nChannel = 0; nChannel < pnodeLocalHost->vfSubscribe.size(); nChannel++)
                        if (pnodeLocalHost->vfSubscribe[nChannel])
                            pnode->PushMessage("subscribe", nChannel, nHops);

                    fSuccess = true;
                    break;
                }
            }

            nTries++;
        }

        // Wait
        vfThreadRunning[1] = false;
        Sleep(100 + nTries * 5);
        vfThreadRunning[1] = true;
        CheckForShutdown(1);
    }
}








void ThreadMessageHandler(void* parg)
{
    IMPLEMENT_RANDOMIZE_STACK(ThreadMessageHandler(parg));

    loop
    {
        vfThreadRunning[2] = true;
        CheckForShutdown(2);
        try
        {
            ThreadMessageHandler2(parg);
        }
        CATCH_PRINT_EXCEPTION("ThreadMessageHandler()")
        vfThreadRunning[2] = false;
        Sleep(5000);
    }
}

void ThreadMessageHandler2(void* parg)
{
    printf("ThreadMessageHandler started\n");
    loop
    {
        // Poll the connected nodes for messages
        vector vNodesCopy;
        CRITICAL_BLOCK(cs_vNodes)
            vNodesCopy = vNodes;
        foreach(CNode* pnode, vNodesCopy)
        {
            pnode->AddRef();

            // Receive messages
            TRY_CRITICAL_BLOCK(pnode->cs_vRecv)
                ProcessMessages(pnode);

            // Send messages
            TRY_CRITICAL_BLOCK(pnode->cs_vSend)
                SendMessages(pnode);

            pnode->Release();
        }

        // Wait and allow messages to bunch up
        vfThreadRunning[2] = false;
        Sleep(200);
        vfThreadRunning[2] = true;
        CheckForShutdown(2);
    }
}









//// todo: start one thread per processor, use getenv("NUMBER_OF_PROCESSORS")
void ThreadBitcoinMiner(void* parg)
{
    vfThreadRunning[3] = true;
    CheckForShutdown(3);
    try
    {
        bool fRet = BitcoinMiner();
        printf("BitcoinMiner returned %s\n\n\n", fRet ? "true" : "false");
    }
    CATCH_PRINT_EXCEPTION("BitcoinMiner()")
    vfThreadRunning[3] = false;
}











bool StartNode(string& strError)
{
    strError = "";


    // Sockets startup
    WSADATA wsadata;
    int ret = WSAStartup(MAKEWORD(2,2), &wsadata);
    if (ret != NO_ERROR)
    {
        strError = strprintf("Error: TCP/IP socket library failed to start (WSAStartup returned error %d)", ret);
        printf("%s\n", strError.c_str());
        return false;
    }

    // Get local host ip
    char pszHostName[255];
    if (gethostname(pszHostName, 255) == SOCKET_ERROR)
    {
        strError = strprintf("Error: Unable to get IP address of this computer (gethostname returned error %d)", WSAGetLastError());
        printf("%s\n", strError.c_str());
        return false;
    }
    struct hostent* pHostEnt = gethostbyname(pszHostName);
    if (!pHostEnt)
    {
        strError = strprintf("Error: Unable to get IP address of this computer (gethostbyname returned error %d)", WSAGetLastError());
        printf("%s\n", strError.c_str());
        return false;
    }
    addrLocalHost = CAddress(*(long*)(pHostEnt->h_addr_list[0]),
                             DEFAULT_PORT,
                             nLocalServices);
    printf("addrLocalHost = %s\n", addrLocalHost.ToString().c_str());

    // Create socket for listening for incoming connections
    SOCKET hListenSocket = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
    if (hListenSocket == INVALID_SOCKET)
    {
        strError = strprintf("Error: Couldn't open socket for incoming connections (socket returned error %d)", WSAGetLastError());
        printf("%s\n", strError.c_str());
        return false;
    }

    // Set to nonblocking, incomming connections will also inherit this
    u_long nOne = 1;
    if (ioctlsocket(hListenSocket, FIONBIO, &nOne) == SOCKET_ERROR)
    {
        strError = strprintf("Error: Couldn't set properties on socket for incoming connections (ioctlsocket returned error %d)", WSAGetLastError());
        printf("%s\n", strError.c_str());
        return false;
    }

    // The sockaddr_in structure specifies the address family,
    // IP address, and port for the socket that is being bound
    int nRetryLimit = 15;
    struct sockaddr_in sockaddr;
    sockaddr.sin_family = AF_INET;
    sockaddr.sin_addr.s_addr = addrLocalHost.ip;
    sockaddr.sin_port = addrLocalHost.port;
    if (bind(hListenSocket, (struct sockaddr*)&sockaddr, sizeof(sockaddr)) == SOCKET_ERROR)
    {
        int nErr = WSAGetLastError();
        if (nErr == WSAEADDRINUSE)
            strError = strprintf("Error: Unable to bind to port %s on this computer. The program is probably already running.", addrLocalHost.ToString().c_str());
        else
            strError = strprintf("Error: Unable to bind to port %s on this computer (bind returned error %d)", addrLocalHost.ToString().c_str(), nErr);
        printf("%s\n", strError.c_str());
        return false;
    }
    printf("bound to addrLocalHost = %s\n\n", addrLocalHost.ToString().c_str());

    // Listen for incoming connections
    if (listen(hListenSocket, SOMAXCONN) == SOCKET_ERROR)
    {
        strError = strprintf("Error: Listening for incoming connections failed (listen returned error %d)", WSAGetLastError());
        printf("%s\n", strError.c_str());
        return false;
    }


    //
    // Start threads
    //
    if (_beginthread(ThreadSocketHandler, 0, new SOCKET(hListenSocket)) == -1)
    {
        strError = "Error: _beginthread(ThreadSocketHandler) failed";
        printf("%s\n", strError.c_str());
        return false;
    }

    if (_beginthread(ThreadOpenConnections, 0, NULL) == -1)
    {
        strError = "Error: _beginthread(ThreadOpenConnections) failed";
        printf("%s\n", strError.c_str());
        return false;
    }

    if (_beginthread(ThreadMessageHandler, 0, NULL) == -1)
    {
        strError = "Error: _beginthread(ThreadMessageHandler) failed";
        printf("%s\n", strError.c_str());
        return false;
    }

    return true;
}

bool StopNode()
{
    printf("StopNode()\n");
    fShutdown = true;
    nTransactionsUpdated++;
    while (count(vfThreadRunning.begin(), vfThreadRunning.end(), true))
        Sleep(10);
    Sleep(50);

    // Sockets shutdown
    WSACleanup();
    return true;
}

void CheckForShutdown(int n)
{
    if (fShutdown)
    {
        if (n != -1)
            vfThreadRunning[n] = false;
        _endthread();
    }
}

// Copyright (c) 2008 Satoshi Nakamoto
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

class CMessageHeader;
class CAddress;
class CInv;
class CRequestTracker;
class CNode;



static const unsigned short DEFAULT_PORT = htons(2222);
static const unsigned int BROADCAST_HOPS = 5;
enum
{
    NODE_NETWORK = (1 << 0),
};







bool AddAddress(CAddrDB& addrdb, const CAddress& addr);
CNode* FindNode(unsigned int ip);
CNode* ConnectNode(CAddress addrConnect, int64 nTimeout=0);
void AbandonRequests(void (*fn)(void*, CDataStream&), void* param1);
bool AnySubscribed(unsigned int nChannel);
void ThreadBitcoinMiner(void* parg);
bool StartNode(string& strError=REF(string()));
bool StopNode();
void CheckForShutdown(int n);









//
// Message header
//  (4) message start
//  (12) command
//  (4) size

// The message start string is designed to be unlikely to occur in normal data.
// The characters are rarely used upper ascii, not valid as UTF-8, and produce
// a large 4-byte int at any alignment.
static const char pchMessageStart[4] = { 0xf9, 0xbe, 0xb4, 0xd9 };

class CMessageHeader
{
public:
    enum { COMMAND_SIZE=12 };
    char pchMessageStart[sizeof(::pchMessageStart)];
    char pchCommand[COMMAND_SIZE];
    unsigned int nMessageSize;

    CMessageHeader()
    {
        memcpy(pchMessageStart, ::pchMessageStart, sizeof(pchMessageStart));
        memset(pchCommand, 0, sizeof(pchCommand));
        pchCommand[1] = 1;
        nMessageSize = -1;
    }

    CMessageHeader(const char* pszCommand, unsigned int nMessageSizeIn)
    {
        memcpy(pchMessageStart, ::pchMessageStart, sizeof(pchMessageStart));
        strncpy(pchCommand, pszCommand, COMMAND_SIZE);
        nMessageSize = nMessageSizeIn;
    }

    IMPLEMENT_SERIALIZE
    (
        READWRITE(FLATDATA(pchMessageStart));
        READWRITE(FLATDATA(pchCommand));
        READWRITE(nMessageSize);
    )

    string GetCommand()
    {
        if (pchCommand[COMMAND_SIZE-1] == 0)
            return string(pchCommand, pchCommand + strlen(pchCommand));
        else
            return string(pchCommand, pchCommand + COMMAND_SIZE);
    }

    bool IsValid()
    {
        // Check start string
        if (memcmp(pchMessageStart, ::pchMessageStart, sizeof(pchMessageStart)) != 0)
            return false;

        // Check the command string for errors
        for (char* p1 = pchCommand; p1 < pchCommand + COMMAND_SIZE; p1++)
        {
            if (*p1 == 0)
            {
                // Must be all zeros after the first zero
                for (; p1 < pchCommand + COMMAND_SIZE; p1++)
                    if (*p1 != 0)
                        return false;
            }
            else if (*p1 < ' ' || *p1 > 0x7E)
                return false;
        }

        // Message size
        if (nMessageSize > 0x10000000)
        {
            printf("CMessageHeader::IsValid() : nMessageSize too large %u\n", nMessageSize);
            return false;
        }

        return true;
    }
};







static const unsigned char pchIPv4[12] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xff, 0xff };

class CAddress
{
public:
    uint64 nServices;
    unsigned char pchReserved[12];
    unsigned int ip;
    unsigned short port;

    // disk only
    unsigned int nTime;

    CAddress()
    {
        nServices = 0;
        memcpy(pchReserved, pchIPv4, sizeof(pchReserved));
        ip = 0;
        port = DEFAULT_PORT;
        nTime = GetAdjustedTime();
    }

    CAddress(unsigned int ipIn, unsigned short portIn, uint64 nServicesIn=0)
    {
        nServices = nServicesIn;
        memcpy(pchReserved, pchIPv4, sizeof(pchReserved));
        ip = ipIn;
        port = portIn;
        nTime = GetAdjustedTime();
    }

    explicit CAddress(const char* pszIn, uint64 nServicesIn=0)
    {
        nServices = nServicesIn;
        memcpy(pchReserved, pchIPv4, sizeof(pchReserved));
        ip = 0;
        port = DEFAULT_PORT;
        nTime = GetAdjustedTime();

        char psz[100];
        if (strlen(pszIn) > ARRAYLEN(psz)-1)
            return;
        strcpy(psz, pszIn);
        unsigned int a, b, c, d, e;
        if (sscanf(psz, "%u.%u.%u.%u:%u", &a, &b, &c, &d, &e) < 4)
            return;
        char* pszPort = strchr(psz, ':');
        if (pszPort)
        {
            *pszPort++ = '\0';
            port = htons(atoi(pszPort));
        }
        ip = inet_addr(psz);
    }

    IMPLEMENT_SERIALIZE
    (
        if (nType & SER_DISK)
        {
            READWRITE(nVersion);
            READWRITE(nTime);
        }
        READWRITE(nServices);
        READWRITE(FLATDATA(pchReserved));
        READWRITE(ip);
        READWRITE(port);
    )

    friend inline bool operator==(const CAddress& a, const CAddress& b)
    {
        return (memcmp(a.pchReserved, b.pchReserved, sizeof(a.pchReserved)) == 0 &&
                a.ip   == b.ip &&
                a.port == b.port);
    }

    friend inline bool operator<(const CAddress& a, const CAddress& b)
    {
        int ret = memcmp(a.pchReserved, b.pchReserved, sizeof(a.pchReserved));
        if (ret < 0)
            return true;
        else if (ret == 0)
        {
            if (ntohl(a.ip) < ntohl(b.ip))
                return true;
            else if (a.ip == b.ip)
                return ntohs(a.port) < ntohs(b.port);
        }
        return false;
    }

    vector GetKey() const
    {
        CDataStream ss;
        ss << FLATDATA(pchReserved) << ip << port;
        return vector((unsigned char*)&ss.begin()[0], (unsigned char*)&ss.end()[0]);
    }

    bool IsIPv4() const
    {
        return (memcmp(pchReserved, pchIPv4, sizeof(pchIPv4)) == 0);
    }

    unsigned char GetByte(int n) const
    {
        return ((unsigned char*)&ip)[3-n];
    }

    string ToString() const
    {
        return strprintf("%u.%u.%u.%u:%u", GetByte(3), GetByte(2), GetByte(1), GetByte(0), ntohs(port));
    }

    void print() const
    {
        printf("CAddress(%s)\n", ToString().c_str());
    }
};







enum
{
    MSG_TX = 1,
    MSG_BLOCK,
    MSG_REVIEW,
    MSG_PRODUCT,
    MSG_TABLE,
};

static const char* ppszTypeName[] =
{
    "ERROR",
    "tx",
    "block",
    "review",
    "product",
    "table",
};

class CInv
{
public:
    int type;
    uint256 hash;

    CInv()
    {
        type = 0;
        hash = 0;
    }

    CInv(int typeIn, const uint256& hashIn)
    {
        type = typeIn;
        hash = hashIn;
    }

    CInv(const string& strType, const uint256& hashIn)
    {
        int i;
        for (i = 1; i < ARRAYLEN(ppszTypeName); i++)
        {
            if (strType == ppszTypeName[i])
            {
                type = i;
                break;
            }
        }
        if (i == ARRAYLEN(ppszTypeName))
            throw std::out_of_range(strprintf("CInv::CInv(string, uint256) : unknown type '%s'", strType.c_str()));
        hash = hashIn;
    }

    IMPLEMENT_SERIALIZE
    (
        READWRITE(type);
        READWRITE(hash);
    )

    friend inline bool operator<(const CInv& a, const CInv& b)
    {
        return (a.type < b.type || (a.type == b.type && a.hash < b.hash));
    }

    bool IsKnownType() const
    {
        return (type >= 1 && type < ARRAYLEN(ppszTypeName));
    }

    const char* GetCommand() const
    {
        if (!IsKnownType())
            throw std::out_of_range(strprintf("CInv::GetCommand() : type=% unknown type", type));
        return ppszTypeName[type];
    }

    string ToString() const
    {
        return strprintf("%s %s", GetCommand(), hash.ToString().substr(0,6).c_str());
    }

    void print() const
    {
        printf("CInv(%s)\n", ToString().c_str());
    }
};





class CRequestTracker
{
public:
    void (*fn)(void*, CDataStream&);
    void* param1;

    explicit CRequestTracker(void (*fnIn)(void*, CDataStream&)=NULL, void* param1In=NULL)
    {
        fn = fnIn;
        param1 = param1In;
    }

    bool IsNull()
    {
        return fn == NULL;
    }
};





extern bool fClient;
extern uint64 nLocalServices;
extern CAddress addrLocalHost;
extern CNode* pnodeLocalHost;
extern bool fShutdown;
extern array vfThreadRunning;
extern vector vNodes;
extern CCriticalSection cs_vNodes;
extern map, CAddress> mapAddresses;
extern CCriticalSection cs_mapAddresses;
extern map mapRelay;
extern deque > vRelayExpiration;
extern CCriticalSection cs_mapRelay;
extern map mapAlreadyAskedFor;





class CNode
{
public:
    // socket
    uint64 nServices;
    SOCKET hSocket;
    CDataStream vSend;
    CDataStream vRecv;
    CCriticalSection cs_vSend;
    CCriticalSection cs_vRecv;
    unsigned int nPushPos;
    CAddress addr;
    int nVersion;
    bool fClient;
    bool fInbound;
    bool fNetworkNode;
    bool fDisconnect;
protected:
    int nRefCount;
public:
    int64 nReleaseTime;
    map mapRequests;
    CCriticalSection cs_mapRequests;

    // flood
    vector vAddrToSend;
    set setAddrKnown;

    // inventory based relay
    vector vInventoryToSend;
    set setInventoryKnown;
    CCriticalSection cs_inventory;
    multimap mapAskFor;

    // broadcast and subscription
    vector vfSubscribe;


    CNode(SOCKET hSocketIn, CAddress addrIn)
    {
        nServices = 0;
        hSocket = hSocketIn;
        vSend.SetType(SER_NETWORK);
        vRecv.SetType(SER_NETWORK);
        nPushPos = -1;
        addr = addrIn;
        nVersion = 0;
        fClient = false; // set by version message
        fInbound = false;
        fNetworkNode = false;
        fDisconnect = false;
        nRefCount = 0;
        nReleaseTime = 0;
        vfSubscribe.assign(256, false);

        // Push a version message
        unsigned int nTime = GetAdjustedTime();
        PushMessage("version", VERSION, nLocalServices, nTime);
    }

    ~CNode()
    {
        if (hSocket != INVALID_SOCKET)
            closesocket(hSocket);
    }

private:
    CNode(const CNode&);
    void operator=(const CNode&);
public:


    bool ReadyToDisconnect()
    {
        return fDisconnect || GetRefCount() <= 0;
    }

    int GetRefCount()
    {
        return max(nRefCount, 0) + (GetTime() < nReleaseTime ? 1 : 0);
    }

    void AddRef(int64 nTimeout=0)
    {
        if (nTimeout != 0)
            nReleaseTime = max(nReleaseTime, GetTime() + nTimeout);
        else
            nRefCount++;
    }

    void Release()
    {
        nRefCount--;
    }



    void AddInventoryKnown(const CInv& inv)
    {
        CRITICAL_BLOCK(cs_inventory)
            setInventoryKnown.insert(inv);
    }

    void AskFor(const CInv& inv)
    {
        // We're using mapAskFor as a priority queue,
        // the key is the earliest time the request can be sent
        int64& nRequestTime = mapAlreadyAskedFor[inv];
        printf("askfor %s  %I64d\n", inv.ToString().c_str(), nRequestTime);
        nRequestTime = max(nRequestTime + 2 * 60, GetTime());
        mapAskFor.insert(make_pair(nRequestTime, inv));
    }



    void BeginMessage(const char* pszCommand)
    {
        EnterCriticalSection(&cs_vSend);
        if (nPushPos != -1)
            AbortMessage();
        nPushPos = vSend.size();
        vSend << CMessageHeader(pszCommand, 0);
        printf("sending: %-12s ", pszCommand);
    }

    void AbortMessage()
    {
        if (nPushPos == -1)
            return;
        vSend.resize(nPushPos);
        nPushPos = -1;
        LeaveCriticalSection(&cs_vSend);
        printf("(aborted)\n");
    }

    void EndMessage()
    {
        if (nPushPos == -1)
            return;

        // Patch in the size
        unsigned int nSize = vSend.size() - nPushPos - sizeof(CMessageHeader);
        memcpy((char*)&vSend[nPushPos] + offsetof(CMessageHeader, nMessageSize), &nSize, sizeof(nSize));

        printf("(%d bytes)  ", nSize);
        //for (int i = nPushPos+sizeof(CMessageHeader); i < min(vSend.size(), nPushPos+sizeof(CMessageHeader)+20U); i++)
        //    printf("%02x ", vSend[i] & 0xff);
        printf("\n");

        nPushPos = -1;
        LeaveCriticalSection(&cs_vSend);
    }

    void EndMessageAbortIfEmpty()
    {
        if (nPushPos == -1)
            return;
        int nSize = vSend.size() - nPushPos - sizeof(CMessageHeader);
        if (nSize > 0)
            EndMessage();
        else
            AbortMessage();
    }

    const char* GetMessageCommand() const
    {
        if (nPushPos == -1)
            return "";
        return &vSend[nPushPos] + offsetof(CMessageHeader, pchCommand);
    }




    void PushMessage(const char* pszCommand)
    {
        try
        {
            BeginMessage(pszCommand);
            EndMessage();
        }
        catch (...)
        {
            AbortMessage();
            throw;
        }
    }

    template
    void PushMessage(const char* pszCommand, const T1& a1)
    {
        try
        {
            BeginMessage(pszCommand);
            vSend << a1;
            EndMessage();
        }
        catch (...)
        {
            AbortMessage();
            throw;
        }
    }

    template
    void PushMessage(const char* pszCommand, const T1& a1, const T2& a2)
    {
        try
        {
            BeginMessage(pszCommand);
            vSend << a1 << a2;
            EndMessage();
        }
        catch (...)
        {
            AbortMessage();
            throw;
        }
    }

    template
    void PushMessage(const char* pszCommand, const T1& a1, const T2& a2, const T3& a3)
    {
        try
        {
            BeginMessage(pszCommand);
            vSend << a1 << a2 << a3;
            EndMessage();
        }
        catch (...)
        {
            AbortMessage();
            throw;
        }
    }

    template
    void PushMessage(const char* pszCommand, const T1& a1, const T2& a2, const T3& a3, const T4& a4)
    {
        try
        {
            BeginMessage(pszCommand);
            vSend << a1 << a2 << a3 << a4;
            EndMessage();
        }
        catch (...)
        {
            AbortMessage();
            throw;
        }
    }


    void PushRequest(const char* pszCommand,
                     void (*fn)(void*, CDataStream&), void* param1)
    {
        uint256 hashReply;
        RAND_bytes((unsigned char*)&hashReply, sizeof(hashReply));

        CRITICAL_BLOCK(cs_mapRequests)
            mapRequests[hashReply] = CRequestTracker(fn, param1);

        PushMessage(pszCommand, hashReply);
    }

    template
    void PushRequest(const char* pszCommand, const T1& a1,
                     void (*fn)(void*, CDataStream&), void* param1)
    {
        uint256 hashReply;
        RAND_bytes((unsigned char*)&hashReply, sizeof(hashReply));

        CRITICAL_BLOCK(cs_mapRequests)
            mapRequests[hashReply] = CRequestTracker(fn, param1);

        PushMessage(pszCommand, hashReply, a1);
    }

    template
    void PushRequest(const char* pszCommand, const T1& a1, const T2& a2,
                     void (*fn)(void*, CDataStream&), void* param1)
    {
        uint256 hashReply;
        RAND_bytes((unsigned char*)&hashReply, sizeof(hashReply));

        CRITICAL_BLOCK(cs_mapRequests)
            mapRequests[hashReply] = CRequestTracker(fn, param1);

        PushMessage(pszCommand, hashReply, a1, a2);
    }



    bool IsSubscribed(unsigned int nChannel);
    void Subscribe(unsigned int nChannel, unsigned int nHops=0);
    void CancelSubscribe(unsigned int nChannel);
    void Disconnect();
};










inline void RelayInventory(const CInv& inv)
{
    // Put on lists to offer to the other nodes
    CRITICAL_BLOCK(cs_vNodes)
        foreach(CNode* pnode, vNodes)
            CRITICAL_BLOCK(pnode->cs_inventory)
                if (!pnode->setInventoryKnown.count(inv))
                    pnode->vInventoryToSend.push_back(inv);
}

template
void RelayMessage(const CInv& inv, const T& a)
{
    CDataStream ss(SER_NETWORK);
    ss << a;
    RelayMessage(inv, ss);
}

template<>
inline void RelayMessage<>(const CInv& inv, const CDataStream& ss)
{
    CRITICAL_BLOCK(cs_mapRelay)
    {
        // Save original serialized message so newer versions are preserved
        mapRelay[inv] = ss;

        // Expire old relay messages
        vRelayExpiration.push_back(make_pair(GetTime() + 10 * 60, inv));
        while (!vRelayExpiration.empty() && vRelayExpiration.front().first < GetTime())
        {
            mapRelay.erase(vRelayExpiration.front().second);
            vRelayExpiration.pop_front();
        }
    }

    RelayInventory(inv);
}

//////////////////////////////////////////////////////////////////////////////
//
// Messages
//


bool AlreadyHave(const CInv& inv)
{
    switch (inv.type)
    {
    case MSG_TX:        return mapTransactions.count(inv.hash);
    case MSG_BLOCK:     return mapBlockIndex.count(inv.hash) || mapOrphanBlocks.count(inv.hash);
    case MSG_REVIEW:    return true;
    case MSG_PRODUCT:   return mapProducts.count(inv.hash);
    case MSG_TABLE:     return mapTables.count(inv.hash);
    }
    // Don't know what it is, just say we already got one
    return true;
}







bool ProcessMessages(CNode* pfrom)
{
    CDataStream& vRecv = pfrom->vRecv;
    if (vRecv.empty())
        return true;
    printf("ProcessMessages(%d bytes)\n", vRecv.size());

    //
    // Message format
    //  (4) message start
    //  (12) command
    //  (4) size
    //  (x) data
    //

    loop
    {
        // Scan for message start
        CDataStream::iterator pstart = search(vRecv.begin(), vRecv.end(), BEGIN(pchMessageStart), END(pchMessageStart));
        if (vRecv.end() - pstart < sizeof(CMessageHeader))
        {
            if (vRecv.size() > sizeof(CMessageHeader))
            {
                printf("\n\nPROCESSMESSAGE MESSAGESTART NOT FOUND\n\n");
                vRecv.erase(vRecv.begin(), vRecv.end() - sizeof(CMessageHeader));
            }
            break;
        }
        if (pstart - vRecv.begin() > 0)
            printf("\n\nPROCESSMESSAGE SKIPPED %d BYTES\n\n", pstart - vRecv.begin());
        vRecv.erase(vRecv.begin(), pstart);

        // Read header
        CMessageHeader hdr;
        vRecv >> hdr;
        if (!hdr.IsValid())
        {
            printf("\n\nPROCESSMESSAGE: ERRORS IN HEADER %s\n\n\n", hdr.GetCommand().c_str());
            continue;
        }
        string strCommand = hdr.GetCommand();

        // Message size
        unsigned int nMessageSize = hdr.nMessageSize;
        if (nMessageSize > vRecv.size())
        {
            // Rewind and wait for rest of message
            ///// need a mechanism to give up waiting for overlong message size error
            printf("MESSAGE-BREAK 2\n");
            vRecv.insert(vRecv.begin(), BEGIN(hdr), END(hdr));
            break;
        }

        // Copy message to its own buffer
        CDataStream vMsg(vRecv.begin(), vRecv.begin() + nMessageSize, vRecv.nType, vRecv.nVersion);
        vRecv.ignore(nMessageSize);

        // Process message
        bool fRet = false;
        try
        {
            fRet = ProcessMessage(pfrom, strCommand, vMsg);
        }
        CATCH_PRINT_EXCEPTION("ProcessMessage()")
        if (!fRet)
            printf("ProcessMessage(%s, %d bytes) from %s to %s FAILED\n", strCommand.c_str(), nMessageSize, pfrom->addr.ToString().c_str(), addrLocalHost.ToString().c_str());
    }

    vRecv.Compact();
    return true;
}




bool ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
{
    static map > mapReuseKey;
    CheckForShutdown(2);
    printf("received: %-12s (%d bytes)  ", strCommand.c_str(), vRecv.size());
    for (int i = 0; i < min(vRecv.size(), (unsigned int)25); i++)
        printf("%02x ", vRecv[i] & 0xff);
    printf("\n");


    if (strCommand == "version")
    {
        // Can only do this once
        if (pfrom->nVersion != 0)
            return false;

        unsigned int nTime;
        vRecv >> pfrom->nVersion >> pfrom->nServices >> nTime;
        if (pfrom->nVersion == 0)
            return false;

        pfrom->vSend.SetVersion(min(pfrom->nVersion, VERSION));
        pfrom->vRecv.SetVersion(min(pfrom->nVersion, VERSION));

        pfrom->fClient = !(pfrom->nServices & NODE_NETWORK);
        if (pfrom->fClient)
        {
            pfrom->vSend.nType |= SER_BLOCKHEADERONLY;
            pfrom->vRecv.nType |= SER_BLOCKHEADERONLY;
        }

        AddTimeData(pfrom->addr.ip, nTime);

        // Ask the first connected node for block updates
        static bool fAskedForBlocks;
        if (!fAskedForBlocks && !pfrom->fClient)
        {
            fAskedForBlocks = true;
            pfrom->PushMessage("getblocks", CBlockLocator(pindexBest), uint256(0));
        }
    }


    else if (pfrom->nVersion == 0)
    {
        // Must have a version message before anything else
        return false;
    }


    else if (strCommand == "addr")
    {
        vector vAddr;
        vRecv >> vAddr;

        // Store the new addresses
        CAddrDB addrdb;
        foreach(const CAddress& addr, vAddr)
        {
            if (AddAddress(addrdb, addr))
            {
                // Put on lists to send to other nodes
                pfrom->setAddrKnown.insert(addr);
                CRITICAL_BLOCK(cs_vNodes)
                    foreach(CNode* pnode, vNodes)
                        if (!pnode->setAddrKnown.count(addr))
                            pnode->vAddrToSend.push_back(addr);
            }
        }
    }


    else if (strCommand == "inv")
    {
        vector vInv;
        vRecv >> vInv;

        foreach(const CInv& inv, vInv)
        {
            printf("  got inventory: %s  %s\n", inv.ToString().c_str(), AlreadyHave(inv) ? "have" : "new");

            CRITICAL_BLOCK(pfrom->cs_inventory)
                pfrom->setInventoryKnown.insert(inv);

            if (!AlreadyHave(inv))
                pfrom->AskFor(inv);
            else if (inv.type == MSG_BLOCK && mapOrphanBlocks.count(inv.hash))
                pfrom->PushMessage("getblocks", CBlockLocator(pindexBest), GetOrphanRoot(mapOrphanBlocks[inv.hash]));
        }
    }


    else if (strCommand == "getdata")
    {
        vector vInv;
        vRecv >> vInv;

        foreach(const CInv& inv, vInv)
        {
            printf("received getdata for: %s\n", inv.ToString().c_str());

            if (inv.type == MSG_BLOCK)
            {
                // Send block from disk
                map::iterator mi = mapBlockIndex.find(inv.hash);
                if (mi != mapBlockIndex.end())
                {
                    CBlock block;
                    block.ReadFromDisk((*mi).second, !pfrom->fClient);
                    pfrom->PushMessage("block", block);
                }
            }
            else if (inv.IsKnownType())
            {
                // Send stream from relay memory
                CRITICAL_BLOCK(cs_mapRelay)
                {
                    map::iterator mi = mapRelay.find(inv);
                    if (mi != mapRelay.end())
                        pfrom->PushMessage(inv.GetCommand(), (*mi).second);
                }
            }
        }
    }


    else if (strCommand == "getblocks")
    {
        CBlockLocator locator;
        uint256 hashStop;
        vRecv >> locator >> hashStop;

        // Find the first block the caller has in the main chain
        CBlockIndex* pindex = locator.GetBlockIndex();

        // Send the rest of the chain
        if (pindex)
            pindex = pindex->pnext;
        for (; pindex; pindex = pindex->pnext)
        {
            CBlock block;
            block.ReadFromDisk(pindex, !pfrom->fClient);
            if (block.GetHash() == hashStop)
                break;
            pfrom->PushMessage("block", block);
        }
    }


    else if (strCommand == "getmywtxes")
    {
        CBlockLocator locator;
        vector vPubKeyHashes;
        vRecv >> locator >> vPubKeyHashes;

        // Find the owner's new transactions
        int nHeight = locator.GetHeight();
        CTxDB txdb("r");
        foreach(uint160 hash160, vPubKeyHashes)
        {
            vector vtx;
            if (txdb.ReadOwnerTxes(hash160, nHeight, vtx))
            {
                foreach(const CTransaction& tx, vtx)
                {
                    // Upgrade transaction to a fully supported CWalletTx
                    CWalletTx wtx(tx);
                    wtx.AddSupportingTransactions(txdb);

                    pfrom->PushMessage("wtx", wtx);
                }
            }
        }
    }


    else if (strCommand == "wtx")
    {
        CWalletTx wtx;
        vRecv >> wtx;

        if (!wtx.AcceptWalletTransaction())
            return error("message wtx : AcceptWalletTransaction failed!");
        AddToWallet(wtx);
    }


    else if (strCommand == "tx")
    {
        CDataStream vMsg(vRecv);
        CTransaction tx;
        vRecv >> tx;

        CInv inv(MSG_TX, tx.GetHash());
        pfrom->AddInventoryKnown(inv);

        if (tx.AcceptTransaction())
        {
            AddToWalletIfMine(tx, NULL);
            RelayMessage(inv, vMsg);
            mapAlreadyAskedFor.erase(inv);
        }
    }


    else if (strCommand == "block")
    {
        auto_ptr pblock(new CBlock);
        vRecv >> *pblock;

        //// debug print
        printf("received block:\n"); pblock->print();

        CInv inv(MSG_BLOCK, pblock->GetHash());
        pfrom->AddInventoryKnown(inv);

        if (ProcessBlock(pfrom, pblock.release()))
            mapAlreadyAskedFor.erase(inv);
    }


    else if (strCommand == "getaddr")
    {
        pfrom->vAddrToSend.clear();
        //// need to expand the time range if not enough found
        int64 nSince = GetAdjustedTime() - 60 * 60; // in the last hour
        CRITICAL_BLOCK(cs_mapAddresses)
        {
            foreach(const PAIRTYPE(vector, CAddress)& item, mapAddresses)
            {
                const CAddress& addr = item.second;
                if (addr.nTime > nSince)
                    pfrom->vAddrToSend.push_back(addr);
            }
        }
    }


    else if (strCommand == "checkorder")
    {
        uint256 hashReply;
        CWalletTx order;
        vRecv >> hashReply >> order;

        /// we have a chance to check the order here

        // Keep giving the same key to the same ip until they use it
        if (!mapReuseKey.count(pfrom->addr.ip))
            mapReuseKey[pfrom->addr.ip] = GenerateNewKey();

        // Send back approval of order and pubkey to use
        CScript scriptPubKey;
        scriptPubKey << OP_CODESEPARATOR << mapReuseKey[pfrom->addr.ip] << OP_CHECKSIG;
        pfrom->PushMessage("reply", hashReply, (int)0, scriptPubKey);
    }


    else if (strCommand == "submitorder")
    {
        uint256 hashReply;
        CWalletTx wtxNew;
        vRecv >> hashReply >> wtxNew;

        // Broadcast
        if (!wtxNew.AcceptWalletTransaction())
        {
            pfrom->PushMessage("reply", hashReply, (int)1);
            return error("submitorder AcceptWalletTransaction() failed, returning error 1");
        }
        AddToWallet(wtxNew);
        wtxNew.RelayWalletTransaction();
        mapReuseKey.erase(pfrom->addr.ip);

        // Send back confirmation
        pfrom->PushMessage("reply", hashReply, (int)0);
    }


    else if (strCommand == "reply")
    {
        uint256 hashReply;
        vRecv >> hashReply;

        CRequestTracker tracker;
        CRITICAL_BLOCK(pfrom->cs_mapRequests)
        {
            map::iterator mi = pfrom->mapRequests.find(hashReply);
            if (mi != pfrom->mapRequests.end())
            {
                tracker = (*mi).second;
                pfrom->mapRequests.erase(mi);
            }
        }
        if (!tracker.IsNull())
            tracker.fn(tracker.param1, vRecv);
    }


    else
    {
        // Ignore unknown commands for extensibility
        printf("ProcessMessage(%s) : Ignored unknown message\n", strCommand.c_str());
    }


    if (!vRecv.empty())
        printf("ProcessMessage(%s) : %d extra bytes\n", strCommand.c_str(), vRecv.size());

    return true;
}









bool SendMessages(CNode* pto)
{
    CheckForShutdown(2);

    // Don't send anything until we get their version message
    if (pto->nVersion == 0)
        return true;


    //
    // Message: addr
    //
    vector vAddrToSend;
    vAddrToSend.reserve(pto->vAddrToSend.size());
    foreach(const CAddress& addr, pto->vAddrToSend)
        if (!pto->setAddrKnown.count(addr))
            vAddrToSend.push_back(addr);
    pto->vAddrToSend.clear();
    if (!vAddrToSend.empty())
        pto->PushMessage("addr", vAddrToSend);


    //
    // Message: inventory
    //
    vector vInventoryToSend;
    CRITICAL_BLOCK(pto->cs_inventory)
    {
        vInventoryToSend.reserve(pto->vInventoryToSend.size());
        foreach(const CInv& inv, pto->vInventoryToSend)
            if (!pto->setInventoryKnown.count(inv))
                vInventoryToSend.push_back(inv);
        pto->vInventoryToSend.clear();
    }
    if (!vInventoryToSend.empty())
        pto->PushMessage("inv", vInventoryToSend);


    //
    // Message: getdata
    //
    vector vAskFor;
    int64 nNow = GetTime();
    while (!pto->mapAskFor.empty() && (*pto->mapAskFor.begin()).first <= nNow)
    {
        const CInv& inv = (*pto->mapAskFor.begin()).second;
        printf("getdata %s\n", inv.ToString().c_str());
        if (!AlreadyHave(inv))
            vAskFor.push_back(inv);
        pto->mapAskFor.erase(pto->mapAskFor.begin());
    }
    if (!vAskFor.empty())
        pto->PushMessage("getdata", vAskFor);



    return true;
}














//////////////////////////////////////////////////////////////////////////////
//
// BitcoinMiner
//

int FormatHashBlocks(void* pbuffer, unsigned int len)
{
    unsigned char* pdata = (unsigned char*)pbuffer;
    unsigned int blocks = 1 + ((len + 8) / 64);
    unsigned char* pend = pdata + 64 * blocks;
    memset(pdata + len, 0, 64 * blocks - len);
    pdata[len] = 0x80;
    unsigned int bits = len * 8;
    pend[-1] = (bits >> 0) & 0xff;
    pend[-2] = (bits >> 8) & 0xff;
    pend[-3] = (bits >> 16) & 0xff;
    pend[-4] = (bits >> 24) & 0xff;
    return blocks;
}

using CryptoPP::ByteReverse;
static int detectlittleendian = 1;

void BlockSHA256(const void* pin, unsigned int nBlocks, void* pout)
{
    unsigned int* pinput = (unsigned int*)pin;
    unsigned int* pstate = (unsigned int*)pout;

    CryptoPP::SHA256::InitState(pstate);

    if (*(char*)&detectlittleendian != 0)
    {
        for (int n = 0; n < nBlocks; n++)
        {
            unsigned int pbuf[16];
            for (int i = 0; i < 16; i++)
                pbuf[i] = ByteReverse(pinput[n * 16 + i]);
            CryptoPP::SHA256::Transform(pstate, pbuf);
        }
        for (int i = 0; i < 8; i++)
            pstate[i] = ByteReverse(pstate[i]);
    }
    else
    {
        for (int n = 0; n < nBlocks; n++)
            CryptoPP::SHA256::Transform(pstate, pinput + n * 16);
    }
}


bool BitcoinMiner()
{
    printf("BitcoinMiner started\n");

    SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_LOWEST);



    CBlock blockPrev;
    while (fGenerateBitcoins)
    {
        CheckForShutdown(3);

        //
        // Create coinbase tx
        //
        CTransaction txNew;
        txNew.vin.resize(1);
        txNew.vin[0].prevout.SetNull();
        CBigNum bnNonce; // this nonce is so multiple processes working for the same keyUser
        BN_rand_range(&bnNonce, &CBigNum(INT_MAX));  // don't cover the same ground
        txNew.vin[0].scriptSig << bnNonce;
        txNew.vout.resize(1);
        txNew.vout[0].scriptPubKey << OP_CODESEPARATOR << keyUser.GetPubKey() << OP_CHECKSIG;
        txNew.vout[0].posNext.SetNull();


        //
        // Create new block
        //
        auto_ptr pblock(new CBlock());
        if (!pblock.get())
            return false;

        // Add our coinbase tx as first transaction
        pblock->vtx.push_back(txNew);

        // Collect the latest transactions into the block
        unsigned int nTransactionsUpdatedLast = nTransactionsUpdated;
        int64 nFees = 0;
        CRITICAL_BLOCK(cs_mapTransactions)
        {
            CTxDB txdb("r");
            set setInThisBlock;
            vector vfAlreadyAdded(mapTransactions.size());
            bool fFoundSomething = true;
            unsigned int nSize = 0;
            while (fFoundSomething && nSize < MAX_SIZE/2)
            {
                fFoundSomething = false;
                unsigned int n = 0;
                for (map::iterator mi = mapTransactions.begin(); mi != mapTransactions.end(); ++mi, ++n)
                {
                    if (vfAlreadyAdded[n])
                        continue;
                    CTransaction& tx = (*mi).second;
                    if (!tx.IsFinal() || tx.IsCoinBase())
                        continue;

                    // Find if all dependencies are in this or previous blocks
                    bool fHaveAllPrev = true;
                    int64 nValueIn = 0;
                    foreach(const CTxIn& txin, tx.vin)
                    {
                        COutPoint prevout = txin.prevout;
                        CTransaction txPrev;
                        if (setInThisBlock.count(prevout.hash))
                        {
                            txPrev = mapTransactions[prevout.hash];
                        }
                        else if (!txdb.ReadDiskTx(prevout.hash, txPrev))
                        {
                            fHaveAllPrev = false;
                            break;
                        }
                        if (prevout.n >= txPrev.vout.size())
                        {
                            fHaveAllPrev = false;
                            break;
                        }
                        nValueIn += txPrev.vout[prevout.n].nValue;
                    }
                    int64 nTransactionFee = nValueIn - tx.GetValueOut();
                    if (nTransactionFee < 0) // could require a tx fee here
                        continue;

                    // Add tx to block
                    if (fHaveAllPrev)
                    {
                        fFoundSomething = true;
                        pblock->vtx.push_back(tx);
                        nSize += ::GetSerializeSize(tx, SER_NETWORK);
                        nFees += nTransactionFee;
                        vfAlreadyAdded[n] = true;
                        setInThisBlock.insert(tx.GetHash());
                    }
                }
            }
        }

        // Update last few things
        pblock->vtx[0].vout[0].nValue = GetBlockValue(nFees);
        pblock->hashMerkleRoot = pblock->BuildMerkleTree();


        printf("\n\nRunning BitcoinMiner with %d transactions in block\n", pblock->vtx.size());


        //
        // Prebuild hash buffer
        //
        struct unnamed1
        {
            struct unnamed2
            {
                uint256 hashPrevBlock;
                uint256 hashMerkleRoot;
                unsigned int nTime;
                unsigned int nBits;
                unsigned int nNonce;
            }
            block;
            unsigned char pchPadding0[64];
            uint256 hash1;
            unsigned char pchPadding1[64];
        }
        tmp;

        const CBlockIndex* pindexPrev = pindexBest;
        tmp.block.hashPrevBlock = pblock->hashPrevBlock = hashTimeChainBest;
        tmp.block.hashMerkleRoot = pblock->hashMerkleRoot;

        // Get time of previous block
        if (pindexPrev)
        {
            if (blockPrev.GetHash() != pblock->hashPrevBlock)
                blockPrev.ReadFromDisk(pindexPrev, false);
            if (blockPrev.GetHash() != pblock->hashPrevBlock)
            {
                printf("pindexBest and hashTimeChainBest out of sync\n");
                continue;
            }
        }
        tmp.block.nTime = pblock->nTime = max(blockPrev.nTime+1, (unsigned int)GetAdjustedTime());
        tmp.block.nBits = pblock->nBits = GetNextWorkRequired(pindexPrev);
        tmp.block.nNonce = 1;

        unsigned int nBlocks0 = FormatHashBlocks(&tmp.block, sizeof(tmp.block));
        unsigned int nBlocks1 = FormatHashBlocks(&tmp.hash1, sizeof(tmp.hash1));


        //
        // Search
        //
        uint256 hashTarget = (~uint256(0) >> pblock->nBits);
        uint256 hash;
        while (nTransactionsUpdated == nTransactionsUpdatedLast)
        {
            BlockSHA256(&tmp.block, nBlocks0, &tmp.hash1);
            BlockSHA256(&tmp.hash1, nBlocks1, &hash);

            if (hash <= hashTarget)
            {
                pblock->nNonce = tmp.block.nNonce;
                assert(hash == pblock->GetHash());

                    //// debug print
                    printf("BitcoinMiner:\n");
                    printf("supercoin found  \n  hash: %s  \ntarget: %s\n", hash.GetHex().c_str(), hashTarget.GetHex().c_str());
                    pblock->print();

                // Process this block the same as if we had received it from another node
                if (!ProcessBlock(NULL, pblock.release()))
                    printf("ERROR in BitcoinMiner, ProcessBlock, block not accepted\n");
                break;
            }

            // Update nTime every few seconds
            if ((++tmp.block.nNonce & 0xfffff) == 0)
            {
                if (tmp.block.nNonce == 0)
                    break;
                tmp.block.nTime = pblock->nTime = max(blockPrev.nTime+1, (unsigned int)GetAdjustedTime());
            }
        }
    }

    return true;
}


















//////////////////////////////////////////////////////////////////////////////
//
// Actions
//


int64 CountMoney()
{
    int64 nTotal = 0;
    CRITICAL_BLOCK(cs_mapWallet)
    {
        for (map::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
        {
            CWalletTx* pcoin = &(*it).second;
            if (!pcoin->IsFinal() || pcoin->fSpent)
                continue;
            nTotal += pcoin->GetCredit();
        }
    }
    return nTotal;
}



bool SelectCoins(int64 nTargetValue, set& setCoinsRet)
{
    setCoinsRet.clear();

    // List of values less than target
    int64 nLowestLarger = _I64_MAX;
    CWalletTx* pcoinLowestLarger = NULL;
    vector > vValue;
    int64 nTotalLower = 0;

    CRITICAL_BLOCK(cs_mapWallet)
    {
        for (map::iterator it = mapWallet.begin(); it != mapWallet.end(); ++it)
        {
            CWalletTx* pcoin = &(*it).second;
            if (!pcoin->IsFinal() || pcoin->fSpent)
                continue;
            int64 n = pcoin->GetCredit();
            if (n < nTargetValue)
            {
                vValue.push_back(make_pair(n, pcoin));
                nTotalLower += n;
            }
            else if (n == nTargetValue)
            {
                setCoinsRet.insert(pcoin);
                return true;
            }
            else if (n < nLowestLarger)
            {
                nLowestLarger = n;
                pcoinLowestLarger = pcoin;
            }
        }
    }

    if (nTotalLower < nTargetValue)
    {
        if (pcoinLowestLarger == NULL)
            return false;
        setCoinsRet.insert(pcoinLowestLarger);
        return true;
    }

    // Solve subset sum by stochastic approximation
    sort(vValue.rbegin(), vValue.rend());
    vector vfIncluded;
    vector vfBest(vValue.size(), true);
    int64 nBest = nTotalLower;

    for (int nRep = 0; nRep < 1000 && nBest != nTargetValue; nRep++)
    {
        vfIncluded.assign(vValue.size(), false);
        int64 nTotal = 0;
        for (int i = 0; i < vValue.size(); i++)
        {
            if (rand() % 2)
            {
                nTotal += vValue[i].first;
                vfIncluded[i] = true;
                if (nTotal >= nTargetValue)
                {
                    if (nTotal < nBest)
                    {
                        nBest = nTotal;
                        vfBest = vfIncluded;
                    }
                    nTotal -= vValue[i].first;
                    vfIncluded[i] = false;
                }
            }
        }
    }

    // If the next larger is still closer, return it
    if (pcoinLowestLarger && nLowestLarger - nTargetValue <= nBest - nTargetValue)
        setCoinsRet.insert(pcoinLowestLarger);
    else
        for (int i = 0; i < vValue.size(); i++)
            if (vfBest[i])
                setCoinsRet.insert(vValue[i].second);
    return true;
}



bool CreateTransaction(CScript scriptPubKey, int64 nValue, CWalletTx& wtxNew)
{
    wtxNew.vin.clear();
    wtxNew.vout.clear();
    if (nValue < TRANSACTIONFEE)
        return false;

    // Choose coins to use
    set setCoins;
    if (!SelectCoins(nValue, setCoins))
        return false;
    int64 nValueIn = 0;
    foreach(CWalletTx* pcoin, setCoins)
        nValueIn += pcoin->GetCredit();

    // Fill vout[0] to the payee
    int64 nValueOut = nValue - TRANSACTIONFEE;
    wtxNew.vout.push_back(CTxOut(nValueOut, scriptPubKey));

    // Fill vout[1] back to self with any change
    if (nValueIn - TRANSACTIONFEE > nValueOut)
    {
        // Use the same key as one of the coins
        vector vchPubKey;
        CTransaction& txFirst = *(*setCoins.begin());
        foreach(const CTxOut& txout, txFirst.vout)
            if (txout.IsMine())
                if (ExtractPubKey(txout.scriptPubKey, true, vchPubKey))
                    break;
        if (vchPubKey.empty())
            return false;

        // Fill vout[1] to ourself
        CScript scriptPubKey;
        scriptPubKey << OP_CODESEPARATOR << vchPubKey << OP_CHECKSIG;
        wtxNew.vout.push_back(CTxOut(nValueIn - TRANSACTIONFEE - nValueOut, scriptPubKey));
    }

    // Fill vin
    foreach(CWalletTx* pcoin, setCoins)
        for (int nOut = 0; nOut < pcoin->vout.size(); nOut++)
            if (pcoin->vout[nOut].IsMine())
                SignSignature(*pcoin, nOut, wtxNew, -1, "all");

    // Fill vtxPrev by copying from previous transactions vtxPrev
    wtxNew.AddSupportingTransactions();

    // Add tx to wallet, because if it has change it's also ours,
    // otherwise just for transaction history.
    wtxNew.nTime = GetAdjustedTime();
    AddToWallet(wtxNew);

    // Mark old coins as spent
    foreach(CWalletTx* pcoin, setCoins)
    {
        pcoin->fSpent = true;
        pcoin->WriteToDisk();
        vWalletUpdated.push_back(make_pair(pcoin->GetHash(), false));
    }

    return true;
}



bool SendMoney(CScript scriptPubKey, int64 nValue, CWalletTx& wtxNew)
{
    if (!CreateTransaction(scriptPubKey, nValue, wtxNew))
        return false;

    // Broadcast
    if (!wtxNew.AcceptTransaction())
    {
        // This must not fail. The transaction has already been signed and recorded.
        throw runtime_error("SendMoney() : wtxNew.AcceptTransaction() failed\n");
        return false;
    }
    wtxNew.RelayWalletTransaction();

    return true;
}

// Copyright (c) 2008 Satoshi Nakamoto
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

#include "headers.h"
#include "sha.h"





//
// Global state
//

map mapTransactions;
CCriticalSection cs_mapTransactions;
unsigned int nTransactionsUpdated = 0;
/// mapNextTx is only used anymore to track disk tx outpoints used by memory txes
map mapNextTx;

map mapBlockIndex;
const uint256 hashGenesisBlock("0x000006b15d1327d67e971d1de9116bd60a3a01556c91b6ebaa416ebc0cfaa646");
CBlockIndex* pindexGenesisBlock = NULL;
int nBestHeight = -1;
uint256 hashTimeChainBest = 0;
CBlockIndex* pindexBest = NULL;

map mapOrphanBlocks;
multimap mapOrphanBlocksByPrev;

map mapWallet;
vector > vWalletUpdated;
CCriticalSection cs_mapWallet;

map, CPrivKey> mapKeys;
map > mapPubKeys;
CCriticalSection cs_mapKeys;
CKey keyUser;

int fGenerateBitcoins;












//////////////////////////////////////////////////////////////////////////////
//
// mapKeys
//

bool AddKey(const CKey& key)
{
    CRITICAL_BLOCK(cs_mapKeys)
    {
        mapKeys[key.GetPubKey()] = key.GetPrivKey();
        mapPubKeys[Hash160(key.GetPubKey())] = key.GetPubKey();
    }
    return CWalletDB().WriteKey(key.GetPubKey(), key.GetPrivKey());
}

vector GenerateNewKey()
{
    CKey key;
    key.MakeNewKey();
    if (!AddKey(key))
        throw runtime_error("GenerateNewKey() : AddKey failed\n");
    return key.GetPubKey();
}




//////////////////////////////////////////////////////////////////////////////
//
// mapWallet
//

bool AddToWallet(const CWalletTx& wtxIn)
{
    uint256 hash = wtxIn.GetHash();
    CRITICAL_BLOCK(cs_mapWallet)
    {
        // Inserts only if not already there, returns tx inserted or tx found
        pair::iterator, bool> ret = mapWallet.insert(make_pair(hash, wtxIn));
        CWalletTx& wtx = (*ret.first).second;
        bool fInsertedNew = ret.second;

        //// debug print
        printf("AddToWallet %s  %d\n", wtxIn.GetHash().ToString().c_str(), fInsertedNew);

        if (!fInsertedNew)
        {
            // Merge
            bool fUpdated = false;
            if (wtxIn.hashBlock != 0 && wtxIn.hashBlock != wtx.hashBlock)
            {
                wtx.hashBlock = wtxIn.hashBlock;
                fUpdated = true;
            }
            if (wtxIn.fFromMe && wtxIn.fFromMe != wtx.fFromMe)
            {
                wtx.fFromMe = wtxIn.fFromMe;
                fUpdated = true;
            }
            if (wtxIn.fSpent && wtxIn.fSpent != wtx.fSpent)
            {
                wtx.fSpent = wtxIn.fSpent;
                fUpdated = true;
            }
            if (!fUpdated)
                return true;
        }

        // Write to disk
        if (!wtx.WriteToDisk())
            return false;

        // Notify UI
        vWalletUpdated.push_back(make_pair(hash, fInsertedNew));
    }

    // Refresh UI
    MainFrameRepaint();
    return true;
}

bool AddToWalletIfMine(const CTransaction& tx, const CBlock* pblock)
{
    if (tx.IsMine())
    {
        CWalletTx wtx(tx);
        if (pblock)
        {
            wtx.hashBlock = pblock->GetHash();
            wtx.nTime = pblock->nTime;
        }
        else
        {
            wtx.nTime = GetAdjustedTime();
        }
        return AddToWallet(wtx);
    }
    return true;
}

void ReacceptWalletTransactions()
{
    // Reaccept any txes of ours that aren't already in a block
    CRITICAL_BLOCK(cs_mapWallet)
    {
        CTxDB txdb("r");
        foreach(PAIRTYPE(const uint256, CWalletTx)& item, mapWallet)
        {
            CWalletTx& wtx = item.second;
            if (!txdb.ContainsTx(wtx.GetHash()))
                wtx.AcceptWalletTransaction(txdb, false);
        }
    }
}

void RelayWalletTransactions()
{
    static int64 nLastTime;
    if (GetTime() - nLastTime < 15 * 60)
        return;
    nLastTime = GetTime();

    // Rebroadcast any of our txes that aren't in a block yet
    CRITICAL_BLOCK(cs_mapWallet)
    {
        CTxDB txdb("r");
        foreach(PAIRTYPE(const uint256, CWalletTx)& item, mapWallet)
            item.second.RelayWalletTransaction(txdb);
    }
}











//////////////////////////////////////////////////////////////////////////////
//
// CTransaction
//

bool CTxIn::IsMine() const
{
    map::iterator mi = mapWallet.find(prevout.hash);
    if (mi != mapWallet.end())
    {
        const CWalletTx& prev = (*mi).second;
        if (prevout.n < prev.vout.size())
            if (prev.vout[prevout.n].IsMine())
                return true;
    }
    return false;
}

int64 CTxIn::GetDebit() const
{
    map::iterator mi = mapWallet.find(prevout.hash);
    if (mi != mapWallet.end())
    {
        const CWalletTx& prev = (*mi).second;
        if (prevout.n < prev.vout.size())
            if (prev.vout[prevout.n].IsMine())
                return prev.vout[prevout.n].nValue;
    }
    return 0;
}




int CMerkleTx::SetMerkleBranch()
{
    if (fClient)
    {
        if (hashBlock == 0)
            return 0;
    }
    else
    {
        // Load the block this tx is in
        CDiskTxPos pos;
        if (!CTxDB("r").ReadTxPos(GetHash(), pos))
            return 0;
        CBlock block;
        if (!block.ReadFromDisk(pos.nFile, pos.nBlockPos, true))
            return 0;

        // Update the tx's hashBlock
        hashBlock = block.GetHash();

        // Locate the transaction
        for (nIndex = 0; nIndex < block.vtx.size(); nIndex++)
            if (block.vtx[nIndex] == *(CTransaction*)this)
                break;
        if (nIndex == block.vtx.size())
        {
            vMerkleBranch.clear();
            nIndex = -1;
            printf("ERROR: SetMerkleBranch() : couldn't find tx in block\n");
            return 0;
        }

        // Fill in merkle branch
        vMerkleBranch = block.GetMerkleBranch(nIndex);
    }

    // Is the tx in a block that's in the main chain
    map::iterator mi = mapBlockIndex.find(hashBlock);
    if (mi == mapBlockIndex.end())
        return 0;
    CBlockIndex* pindex = (*mi).second;
    if (!pindex || !pindex->IsInMainChain())
        return 0;

    return pindexBest->nHeight - pindex->nHeight + 1;
}

void CWalletTx::AddSupportingTransactions(CTxDB& txdb)
{
    vtxPrev.clear();

    const int COPY_DEPTH = 3;
    if (SetMerkleBranch() < COPY_DEPTH)
    {
        vector vWorkQueue;
        foreach(const CTxIn& txin, vin)
            vWorkQueue.push_back(txin.prevout.hash);

        map mapWalletPrev;
        set setAlreadyDone;
        for (int i = 0; i < vWorkQueue.size(); i++)
        {
            uint256 hash = vWorkQueue[i];
            if (setAlreadyDone.count(hash))
                continue;
            setAlreadyDone.insert(hash);

            CMerkleTx tx;
            if (mapWallet.count(hash))
            {
                tx = mapWallet[hash];
                foreach(const CMerkleTx& txWalletPrev, mapWallet[hash].vtxPrev)
                    mapWalletPrev[txWalletPrev.GetHash()] = &txWalletPrev;
            }
            else if (mapWalletPrev.count(hash))
            {
                tx = *mapWalletPrev[hash];
            }
            else if (!fClient && txdb.ReadDiskTx(hash, tx))
            {
                ;
            }
            else
            {
                printf("ERROR: AddSupportingTransactions() : unsupported transaction\n");
                continue;
            }

            int nDepth = tx.SetMerkleBranch();
            vtxPrev.push_back(tx);

            if (nDepth < COPY_DEPTH)
                foreach(const CTxIn& txin, tx.vin)
                    vWorkQueue.push_back(txin.prevout.hash);
        }
    }

    reverse(vtxPrev.begin(), vtxPrev.end());
}










bool CTransaction::DisconnectInputs(CTxDB& txdb, map& mapTestPool, bool fTest)
{
    // Relinquish previous transactions' posNext pointers
    if (!IsCoinBase())
    {
        foreach(const CTxIn& txin, vin)
        {
            COutPoint prevout = txin.prevout;

            CAutoFile fileout = NULL;
            CTransaction txPrevBuf;
            CTransaction& txPrev = (fTest ? mapTestPool[prevout.hash] : txPrevBuf);
            if (txPrev.IsNull())
            {
                // Get prev tx from disk
                // Version -1 tells unserialize to set version so we write back same version
                fileout.SetVersion(-1);
                if (!txdb.ReadDiskTx(prevout.hash, txPrev, &fileout))
                    return false;
            }

            if (prevout.n >= txPrev.vout.size())
                return false;

            // Relinquish posNext pointer
            txPrev.vout[prevout.n].posNext.SetNull();

            // Write back
            if (!fTest)
                fileout << txPrev;
        }
    }

    if (fTest)
    {
        // Put a blocked-off copy of this transaction in the test pool
        CTransaction& txPool = mapTestPool[GetHash()];
        txPool = *this;
        foreach(CTxOut& txout, txPool.vout)
            txout.posNext = CDiskTxPos(1, 1, 1);
    }
    else
    {
        // Remove transaction from index
        if (!txdb.EraseTxPos(*this))
            return false;

        // Resurect single transaction objects
        if (!IsCoinBase())
            AcceptTransaction(txdb, false);
    }

    return true;
}


bool CTransaction::ConnectInputs(CTxDB& txdb, map& mapTestPool, CDiskTxPos posThisTx, int nHeight,
                                 bool fTest, bool fMemoryTx, bool fIgnoreDiskConflicts, int64& nFees)
{
    // Take over previous transactions' posNext pointers
    if (!IsCoinBase())
    {
        int64 nValueIn = 0;
        for (int i = 0; i < vin.size(); i++)
        {
            COutPoint prevout = vin[i].prevout;

            CAutoFile fileout = NULL;
            CTransaction txPrevBuf;
            CTransaction& txPrev = (fTest ? mapTestPool[prevout.hash] : txPrevBuf);
            if (txPrev.IsNull() && fTest && fMemoryTx && mapTransactions.count(prevout.hash))
            {
                // Get prev tx from single transactions in memory
                txPrev = mapTransactions[prevout.hash];
            }
            else if (txPrev.IsNull())
            {
                // Get prev tx from disk
                // Version -1 tells unserialize to set version so we write back same version
                fileout.SetVersion(-1);
                if (!txdb.ReadDiskTx(prevout.hash, txPrev, &fileout))
                    return error("ConnectInputs() : prev tx not found");

                // If tx will only be connected in a reorg,
                // then these outpoints will be checked at that time
                if (fIgnoreDiskConflicts)
                    foreach(CTxOut& txout, txPrev.vout)
                        txout.posNext.SetNull();
            }

            if (prevout.n >= txPrev.vout.size())
                return false;

            // Verify signature
            if (!VerifySignature(txPrev, *this, i))
                return error("ConnectInputs() : VerifySignature failed");

            // Check for conflicts
            if (!txPrev.vout[prevout.n].posNext.IsNull())
                return error("ConnectInputs() : prev tx already used");

            // Flag outpoints as used
            txPrev.vout[prevout.n].posNext = posThisTx;

            // Write back
            if (!fTest)
                fileout << txPrev;

            nValueIn += txPrev.vout[prevout.n].nValue;
        }

        // Tally transaction fees
        int64 nTransactionFee = nValueIn - GetValueOut();
        if (nTransactionFee < 0)
            return false;
        nFees += nTransactionFee;
    }

    if (fTest)
    {
        // Add transaction to test pool
        mapTestPool[GetHash()] = *this;
    }
    else
    {
        // Add transaction to disk index
        if (!txdb.WriteTxPos(*this, posThisTx, nHeight))
            return false;

        // Delete redundant single transaction objects
        CRITICAL_BLOCK(cs_mapTransactions)
        {
            foreach(const CTxIn& txin, vin)
                mapNextTx.erase(txin.prevout);
            mapTransactions.erase(GetHash());
        }
    }

    return true;
}




bool CTransaction::AcceptTransaction(CTxDB& txdb, bool fCheckInputs)
{
    // Coinbase is only valid in a block, not as a loose transaction
    if (IsCoinBase())
        return error("AcceptTransaction() : coinbase as individual tx");

    if (!CheckTransaction())
        return error("AcceptTransaction() : CheckTransaction failed");

    uint256 hash = GetHash();
    if (mapTransactions.count(hash))
        return false;

    // Check for conflicts with in-memory transactions
    // and allow replacing with a newer version of the same transaction
    CTransaction* ptxOld = NULL;
    for (int i = 0; i < vin.size(); i++)
    {
        COutPoint outpoint = vin[i].prevout;
        if (mapNextTx.count(outpoint))
        {
            if (ptxOld == NULL)
            {
                ptxOld = mapNextTx[outpoint].ptx;
                if (!IsUpdate(*ptxOld))
                    return false;
            }
            else if (ptxOld != mapNextTx[outpoint].ptx)
                return false;
        }
    }

    // Check against previous transactions
    map mapTestPool;
    int64 nFees = 0;
    if (fCheckInputs)
        if (!TestConnectInputs(txdb, mapTestPool, true, false, nFees))
            return error("AcceptTransaction() : TestConnectInputs failed");

    // Store transaction in memory
    CRITICAL_BLOCK(cs_mapTransactions)
    {
        if (ptxOld)
        {
            printf("mapTransaction.erase(%s) replacing with new version\n", ptxOld->GetHash().ToString().c_str());
            mapTransactions.erase(ptxOld->GetHash());
        }
        //printf("mapTransaction.insert(%s)\n  ", hash.ToString().c_str());
        //print();
        mapTransactions[hash] = *this;
        for (int i = 0; i < vin.size(); i++)
            mapNextTx[vin[i].prevout] = CInPoint(&mapTransactions[hash], i);
    }

    // If updated, erase old tx from wallet
    if (ptxOld)
        CRITICAL_BLOCK(cs_mapWallet)
            mapWallet.erase(ptxOld->GetHash());

    nTransactionsUpdated++;
    return true;
}





int CMerkleTx::IsInMainChain() const
{
    if (hashBlock == 0)
        return 0;

    // Find the block it claims to be in
    map::iterator mi = mapBlockIndex.find(hashBlock);
    if (mi == mapBlockIndex.end())
        return 0;
    CBlockIndex* pindex = (*mi).second;
    if (!pindex || !pindex->IsInMainChain())
        return 0;

    // Get merkle root
    CBlock block;
    if (!block.ReadFromDisk(pindex, false))
        return 0;

    // Make sure the merkle branch connects to this block
    if (CBlock::CheckMerkleBranch(GetHash(), vMerkleBranch, nIndex) != block.hashMerkleRoot)
        return 0;

    return pindexBest->nHeight - pindex->nHeight + 1;
}



bool CMerkleTx::AcceptTransaction(CTxDB& txdb, bool fCheckInputs)
{
    if (fClient)
    {
        if (!IsInMainChain() && !ClientConnectInputs())
            return false;
        return CTransaction::AcceptTransaction(txdb, false);
    }
    else
    {
        return CTransaction::AcceptTransaction(txdb, fCheckInputs);
    }
}



bool CWalletTx::AcceptWalletTransaction(CTxDB& txdb, bool fCheckInputs)
{
    foreach(CMerkleTx& tx, vtxPrev)
    {
        uint256 hash = tx.GetHash();
        if (!mapTransactions.count(hash) && !txdb.ContainsTx(hash))
            tx.AcceptTransaction(txdb, fCheckInputs);
    }
    return AcceptTransaction(txdb, fCheckInputs);
}


void CWalletTx::RelayWalletTransaction(CTxDB& txdb)
{
    foreach(CMerkleTx& tx, vtxPrev)
    {
        uint256 hash = tx.GetHash();
        if (!txdb.ContainsTx(hash))
            RelayMessage(CInv(MSG_TX, hash), (CTransaction)tx);
    }
    uint256 hash = GetHash();
    if (!txdb.ContainsTx(hash))
        RelayMessage(CInv(MSG_TX, hash), (CTransaction)*this);
}










//////////////////////////////////////////////////////////////////////////////
//
// CBlock and CBlockIndex
//

bool CBlock::ReadFromDisk(const CBlockIndex* pblockindex, bool fReadTransactions)
{
    return ReadFromDisk(pblockindex->nFile, pblockindex->nBlockPos, fReadTransactions);
}

int64 GetBlockValue(int64 nFees)
{
    int64 nSubsidy = 10000 * CENT;
    for (int i = 100000; i <= nBestHeight; i += 100000)
        nSubsidy /= 2;
    return nSubsidy + nFees;
}

unsigned int GetNextWorkRequired(const CBlockIndex* pindexLast)
{
    const unsigned int nTargetTimespan = 30 * 24 * 60 * 60;
    const unsigned int nTargetSpacing = 15 * 60;
    const unsigned int nIntervals = nTargetTimespan / nTargetSpacing;

    // Cache
    static const CBlockIndex* pindexLastCache;
    static unsigned int nBitsCache;
    static CCriticalSection cs_cache;
    CRITICAL_BLOCK(cs_cache)
        if (pindexLast && pindexLast == pindexLastCache)
            return nBitsCache;

    // Go back 30 days
    const CBlockIndex* pindexFirst = pindexLast;
    for (int i = 0; pindexFirst && i < nIntervals; i++)
        pindexFirst = pindexFirst->pprev;
    if (pindexFirst == NULL)
        return MINPROOFOFWORK;

    // Load first and last block
    CBlock blockFirst;
    if (!blockFirst.ReadFromDisk(pindexFirst, false))
        throw runtime_error("GetNextWorkRequired() : blockFirst.ReadFromDisk failed\n");
    CBlock blockLast;
    if (!blockLast.ReadFromDisk(pindexLast, false))
        throw runtime_error("GetNextWorkRequired() : blockLast.ReadFromDisk failed\n");

    // Limit one change per timespan
    unsigned int nBits = blockLast.nBits;
    if (blockFirst.nBits == blockLast.nBits)
    {
        unsigned int nTimespan = blockLast.nTime - blockFirst.nTime;
        if (nTimespan > nTargetTimespan * 2 && nBits >= MINPROOFOFWORK)
            nBits--;
        else if (nTimespan < nTargetTimespan / 2)
            nBits++;
    }

    CRITICAL_BLOCK(cs_cache)
    {
        pindexLastCache = pindexLast;
        nBitsCache = nBits;
    }
    return nBits;
}

uint256 GetOrphanRoot(const CBlock* pblock)
{
    // Work back to the first block in the orphan chain
    while (mapOrphanBlocks.count(pblock->hashPrevBlock))
        pblock = mapOrphanBlocks[pblock->hashPrevBlock];
    return pblock->hashPrevBlock;
}









bool CBlock::TestDisconnectBlock(CTxDB& txdb, map& mapTestPool)
{
    foreach(CTransaction& tx, vtx)
        if (!tx.TestDisconnectInputs(txdb, mapTestPool))
            return false;
    return true;
}

bool CBlock::TestConnectBlock(CTxDB& txdb, map& mapTestPool)
{
    int64 nFees = 0;
    foreach(CTransaction& tx, vtx)
        if (!tx.TestConnectInputs(txdb, mapTestPool, false, false, nFees))
            return false;

    if (vtx[0].GetValueOut() != GetBlockValue(nFees))
        return false;
    return true;
}

bool CBlock::DisconnectBlock()
{
    CTxDB txdb;
    foreach(CTransaction& tx, vtx)
        if (!tx.DisconnectInputs(txdb))
            return false;
    return true;
}

bool CBlock::ConnectBlock(unsigned int nFile, unsigned int nBlockPos, int nHeight)
{
    //// issue here: it doesn't know the version
    unsigned int nTxPos = nBlockPos + ::GetSerializeSize(CBlock(), SER_DISK) - 1 + GetSizeOfCompactSize(vtx.size());

    CTxDB txdb;
    foreach(CTransaction& tx, vtx)
    {
        CDiskTxPos posThisTx(nFile, nBlockPos, nTxPos);
        nTxPos += ::GetSerializeSize(tx, SER_DISK);

        if (!tx.ConnectInputs(txdb, posThisTx, nHeight))
            return false;
    }
    txdb.Close();

    // Watch for transactions paying to me
    foreach(CTransaction& tx, vtx)
        AddToWalletIfMine(tx, this);

    return true;
}



bool Reorganize(CBlockIndex* pindexNew, bool fWriteDisk)
{
    // Find the fork
    CBlockIndex* pfork = pindexBest;
    CBlockIndex* plonger = pindexNew;
    while (pfork != plonger)
    {
        if (!(pfork = pfork->pprev))
            return false;
        while (plonger->nHeight > pfork->nHeight)
            if (!(plonger = plonger->pprev))
                return false;
    }

    // List of what to disconnect
    vector vDisconnect;
    for (CBlockIndex* pindex = pindexBest; pindex != pfork; pindex = pindex->pprev)
        vDisconnect.push_back(pindex);

    // List of what to connect
    vector vConnect;
    for (CBlockIndex* pindex = pindexNew; pindex != pfork; pindex = pindex->pprev)
        vConnect.push_back(pindex);
    reverse(vConnect.begin(), vConnect.end());

    // Pretest the reorg
    if (fWriteDisk)
    {
        CTxDB txdb("r");
        map mapTestPool;

        foreach(CBlockIndex* pindex, vDisconnect)
            if (!pindex->TestDisconnectBlock(txdb, mapTestPool))
                return false;

        bool fValid = true;
        foreach(CBlockIndex* pindex, vConnect)
        {
            fValid = fValid && pindex->TestConnectBlock(txdb, mapTestPool);
            if (!fValid)
            {
                // Invalid block, delete the rest of this branch
                CBlock block;
                block.ReadFromDisk(pindex, false);
                pindex->EraseBlockFromDisk();
                mapBlockIndex.erase(block.GetHash());
                delete pindex;
            }
        }
        if (!fValid)
            return false;
    }

    // Disconnect shorter branch
    foreach(CBlockIndex* pindex, vDisconnect)
    {
        if (fWriteDisk && !pindex->DisconnectBlock())
            return false;
        if (pindex->pprev)
            pindex->pprev->pnext = NULL;
    }

    // Connect longer branch
    foreach(CBlockIndex* pindex, vConnect)
    {
        if (fWriteDisk && !pindex->ConnectBlock())
            return false;
        if (pindex->pprev)
            pindex->pprev->pnext = pindex;
    }

    return true;
}


bool CBlock::AddToBlockIndex(unsigned int nFile, unsigned int nBlockPos, bool fWriteDisk)
{
    uint256 hash = GetHash();

    // Add to block index
    CBlockIndex* pindexNew = new CBlockIndex(nFile, nBlockPos);
    if (!pindexNew)
        return false;
    mapBlockIndex[hash] = pindexNew;
    map::iterator mi = mapBlockIndex.find(hashPrevBlock);
    if (mi != mapBlockIndex.end())
    {
        pindexNew->pprev = (*mi).second;
        pindexNew->nHeight = pindexNew->pprev->nHeight + 1;
    }

    // New best
    if (pindexNew->nHeight > nBestHeight)
    {
        if (pindexGenesisBlock == NULL && hash == hashGenesisBlock)
        {
            pindexGenesisBlock = pindexNew;
        }
        else if (hashPrevBlock == hashTimeChainBest)
        {
            // Adding to current best branch
            if (fWriteDisk)
                if (!pindexNew->ConnectBlock())
                    return false;
            pindexNew->pprev->pnext = pindexNew;
        }
        else
        {
            // New best branch
            if (!Reorganize(pindexNew, fWriteDisk))
                return false;
        }

        // New best link
        nBestHeight = pindexNew->nHeight;
        hashTimeChainBest = hash;
        pindexBest = pindexNew;
        nTransactionsUpdated++;

        // Relay wallet transactions that haven't gotten in yet
        if (fWriteDisk && nTime > GetAdjustedTime() - 30 * 60)
            RelayWalletTransactions();
    }

    MainFrameRepaint();
    return true;
}





template
bool ScanMessageStart(Stream& s)
{
    // Scan ahead to the next pchMessageStart, which should normally be immediately
    // at the file pointer.  Leaves file pointer at end of pchMessageStart.
    s.clear(0);
    short prevmask = s.exceptions(0);
    const char* p = BEGIN(pchMessageStart);
    try
    {
        loop
        {
            char c;
            s.read(&c, 1);
            if (s.fail())
            {
                s.clear(0);
                s.exceptions(prevmask);
                return false;
            }
            if (*p != c)
                p = BEGIN(pchMessageStart);
            if (*p == c)
            {
                if (++p == END(pchMessageStart))
                {
                    s.clear(0);
                    s.exceptions(prevmask);
                    return true;
                }
            }
        }
    }
    catch (...)
    {
        s.clear(0);
        s.exceptions(prevmask);
        return false;
    }
}

FILE* OpenBlockFile(unsigned int nFile, unsigned int nBlockPos, const char* pszMode)
{
    if (nFile == -1)
        return NULL;
    FILE* file = fopen(strprintf("blk%04d.dat", nFile).c_str(), pszMode);
    if (!file)
        return NULL;
    if (nBlockPos != 0 && !strchr(pszMode, 'a') && !strchr(pszMode, 'w'))
    {
        if (fseek(file, nBlockPos, SEEK_SET) != 0)
        {
            fclose(file);
            return NULL;
        }
    }
    return file;
}

static unsigned int nCurrentBlockFile = 1;

FILE* AppendBlockFile(unsigned int& nFileRet)
{
    nFileRet = 0;
    loop
    {
        FILE* file = OpenBlockFile(nCurrentBlockFile, 0, "ab");
        if (!file)
            return NULL;
        if (fseek(file, 0, SEEK_END) != 0)
            return NULL;
        // FAT32 filesize max 4GB, fseek and ftell max 2GB, so we must stay under 2GB
        if (ftell(file) < 0x7F000000 - MAX_SIZE)
        {
            nFileRet = nCurrentBlockFile;
            return file;
        }
        fclose(file);
        nCurrentBlockFile++;
    }
}

bool LoadBlockIndex(bool fAllowNew)
{
    //
    // Load from disk
    //
    for (nCurrentBlockFile = 1;; nCurrentBlockFile++)
    {
        CAutoFile filein = OpenBlockFile(nCurrentBlockFile, 0, "rb");
        if (filein == NULL)
        {
            if (nCurrentBlockFile > 1)
            {
                nCurrentBlockFile--;
                break;
            }
            if (!fAllowNew)
                return false;

            //// debug
            // Genesis Block:
            // GetHash()      = 0x000006b15d1327d67e971d1de9116bd60a3a01556c91b6ebaa416ebc0cfaa646
            // hashPrevBlock  = 0x0000000000000000000000000000000000000000000000000000000000000000
            // hashMerkleRoot = 0x769a5e93fac273fd825da42d39ead975b5d712b2d50953f35a4fdebdec8083e3
            // txNew.vin[0].scriptSig      = 247422313
            // txNew.vout[0].nValue        = 10000
            // txNew.vout[0].scriptPubKey  = OP_CODESEPARATOR 0x31D18A083F381B4BDE37B649AACF8CD0AFD88C53A3587ECDB7FAF23D449C800AF1CE516199390BFE42991F10E7F5340F2A63449F0B639A7115C667E5D7B051D404 OP_CHECKSIG
            // nTime          = 1221069728
            // nBits          = 20
            // nNonce         = 141755
            // CBlock(hashPrevBlock=000000, hashMerkleRoot=769a5e, nTime=1221069728, nBits=20, nNonce=141755, vtx=1)
            //   CTransaction(vin.size=1, vout.size=1, nLockTime=0)
            //     CTxIn(COutPoint(000000, -1), coinbase 04695dbf0e)
            //     CTxOut(nValue=10000, nSequence=4294967295, scriptPubKey=51b0, posNext=null)
            //   vMerkleTree: 769a5e

            // Genesis block
            CTransaction txNew;
            txNew.vin.resize(1);
            txNew.vout.resize(1);
            txNew.vin[0].scriptSig     = CScript() << 247422313;
            txNew.vout[0].nValue       = 10000;
            txNew.vout[0].scriptPubKey = CScript() << OP_CODESEPARATOR << CBigNum("0x31D18A083F381B4BDE37B649AACF8CD0AFD88C53A3587ECDB7FAF23D449C800AF1CE516199390BFE42991F10E7F5340F2A63449F0B639A7115C667E5D7B051D404") << OP_CHECKSIG;
            CBlock block;
            block.vtx.push_back(txNew);
            block.hashPrevBlock = 0;
            block.hashMerkleRoot = block.BuildMerkleTree();
            block.nTime  = 1221069728;
            block.nBits  = 20;
            block.nNonce = 141755;

                //// debug print
                printf("%s\n", block.GetHash().ToString().c_str());
                printf("%s\n", block.hashMerkleRoot.ToString().c_str());
                printf("%s\n", hashGenesisBlock.ToString().c_str());
                txNew.vout[0].scriptPubKey.print();
                block.print();
                assert(block.hashMerkleRoot == uint256("0x769a5e93fac273fd825da42d39ead975b5d712b2d50953f35a4fdebdec8083e3"));

            assert(block.GetHash() == hashGenesisBlock);

            // Start new block file
            unsigned int nFile;
            unsigned int nBlockPos;
            if (!block.WriteToDisk(true, nFile, nBlockPos))
                return false;
            if (!block.AddToBlockIndex(nFile, nBlockPos, true))
                return false;
            break;
        }

        int nFilesize = GetFilesize(filein);
        if (nFilesize == -1)
            return false;
        filein.nType |= SER_BLOCKHEADERONLY;

        while (ScanMessageStart(filein))
        {
            // Read index header
            unsigned int nSize;
            filein >> nSize;
            if (nSize > MAX_SIZE || ftell(filein) + nSize > nFilesize)
                continue;

            // Read block header
            int nBlockPos = ftell(filein);
            CBlock block;
            filein >> block;

            // Skip transactions
            if (fseek(filein, nBlockPos + nSize, SEEK_SET) != 0)
                break; //// is this all we want to do if there's a file error like this?

            // Add to block index without updating disk
            if (!block.AddToBlockIndex(nCurrentBlockFile, nBlockPos, false))
                return false;
        }
    }
    return true;
}



void PrintTimechain()
{
    // precompute tree structure
    map > mapNext;
    for (map::iterator mi = mapBlockIndex.begin(); mi != mapBlockIndex.end(); ++mi)
    {
        CBlockIndex* pindex = (*mi).second;
        mapNext[pindex->pprev].push_back(pindex);
        // test
        //while (rand() % 3 == 0)
        //    mapNext[pindex->pprev].push_back(pindex);
    }

    vector > vStack;
    vStack.push_back(make_pair(0, pindexGenesisBlock));

    int nPrevCol = 0;
    while (!vStack.empty())
    {
        int nCol = vStack.back().first;
        CBlockIndex* pindex = vStack.back().second;
        vStack.pop_back();

        // print split or gap
        if (nCol > nPrevCol)
        {
            for (int i = 0; i < nCol-1; i++)
                printf("| ");
            printf("|\\\n");
        }
        else if (nCol < nPrevCol)
        {
            for (int i = 0; i < nCol; i++)
                printf("| ");
            printf("|\n");
        }
        nPrevCol = nCol;

        // print columns
        for (int i = 0; i < nCol; i++)
            printf("| ");

        // print item
        printf("%d (%u,%u)\n", pindex->nHeight, pindex->nFile, pindex->nBlockPos);

        // put the main timechain first
        vector& vNext = mapNext[pindex];
        for (int i = 0; i < vNext.size(); i++)
        {
            if (vNext[i]->pnext)
            {
                swap(vNext[0], vNext[i]);
                break;
            }
        }

        // iterate children
        for (int i = 0; i < vNext.size(); i++)
            vStack.push_back(make_pair(nCol+i, vNext[i]));
    }
}






bool CBlock::CheckBlock() const
{
    // Size limits
    if (vtx.empty() || vtx.size() > MAX_SIZE || ::GetSerializeSize(*this, SER_DISK) > MAX_SIZE)
        return error("CheckBlock() : size limits failed");

    // Check timestamp
    if (nTime > GetAdjustedTime() + 36 * 60 * 60)
        return error("CheckBlock() : block timestamp out of range");

    // Check proof of work matches claimed amount
    if (nBits < MINPROOFOFWORK)
        return error("CheckBlock() : nBits below minimum");
    if (GetHash() > (~uint256(0) >> nBits))
        return error("CheckBlock() : hash doesn't match nBits");

    // First transaction must be coinbase, the rest must not be
    if (vtx.empty() || !vtx[0].IsCoinBase())
        return error("CheckBlock() : first tx is not coinbase");
    for (int i = 1; i < vtx.size(); i++)
        if (vtx[i].IsCoinBase())
            return error("CheckBlock() : more than one coinbase");

    // Check transactions
    foreach(const CTransaction& tx, vtx)
        if (!tx.CheckTransaction())
            return error("CheckBlock() : CheckTransaction failed");

    // Check merkleroot
    if (hashMerkleRoot != BuildMerkleTree())
        return error("CheckBlock() : hashMerkleRoot mismatch");

    return true;
}

bool CBlock::AcceptBlock()
{
    // Check for duplicate
    uint256 hash = GetHash();
    if (mapBlockIndex.count(hash))
        return false;

    // Get prev block index
    map::iterator mi = mapBlockIndex.find(hashPrevBlock);
    if (mi == mapBlockIndex.end())
        return false;
    CBlockIndex* pindexPrev = (*mi).second;

    // Check timestamp against prev
    CBlock blockPrev;
    if (!blockPrev.ReadFromDisk(pindexPrev, false))
        return false;
    if (nTime <= blockPrev.nTime)
        return false;

    // Check proof of work
    if (nBits != GetNextWorkRequired(pindexPrev))
        return false;

    // Check transaction inputs and verify signatures
    {
        CTxDB txdb("r");
        map mapTestPool;
        bool fIgnoreDiskConflicts = (hashPrevBlock != hashTimeChainBest);
        int64 nFees = 0;
        foreach(CTransaction& tx, vtx)
            if (!tx.TestConnectInputs(txdb, mapTestPool, false, fIgnoreDiskConflicts, nFees))
                return error("AcceptBlock() : TestConnectInputs failed");
        if (vtx[0].GetValueOut() != GetBlockValue(nFees))
            return false;
    }

    // Write block to history file
    unsigned int nFile;
    unsigned int nBlockPos;
    if (!WriteToDisk(!fClient, nFile, nBlockPos))
        return false;
    if (!AddToBlockIndex(nFile, nBlockPos, true))
        return false;

    if (hashTimeChainBest == hash)
        RelayInventory(CInv(MSG_BLOCK, hash));

    // Add atoms to user reviews for coins created
    vector vchPubKey;
    if (ExtractPubKey(vtx[0].vout[0].scriptPubKey, false, vchPubKey))
    {
        uint64 nRand = 0;
        RAND_bytes((unsigned char*)&nRand, sizeof(nRand));
        unsigned short nAtom = nRand % (USHRT_MAX - 100) + 100;
        vector vAtoms(1, nAtom);
        AddAtomsAndPropagate(Hash(vchPubKey.begin(), vchPubKey.end()), vAtoms, true);
    }

    return true;
}

bool ProcessBlock(CNode* pfrom, CBlock* pblock)
{
    // Check for duplicate
    uint256 hash = pblock->GetHash();
    if (mapBlockIndex.count(hash) || mapOrphanBlocks.count(hash))
        return false;

    // Preliminary checks
    if (!pblock->CheckBlock())
    {
        printf("CheckBlock FAILED\n");
        delete pblock;
        return false;
    }

    // If don't already have its previous block, shunt it off to holding area until we get it
    if (!mapBlockIndex.count(pblock->hashPrevBlock))
    {
        mapOrphanBlocks.insert(make_pair(hash, pblock));
        mapOrphanBlocksByPrev.insert(make_pair(pblock->hashPrevBlock, pblock));

        // Ask this guy to fill in what we're missing
        if (pfrom)
            pfrom->PushMessage("getblocks", CBlockLocator(pindexBest), GetOrphanRoot(pblock));
        return true;
    }

    // Store to disk
    if (!pblock->AcceptBlock())
    {
        printf("AcceptBlock FAILED\n");
        delete pblock;
        return false;
    }
    delete pblock;

    // Now process any orphan blocks that depended on this one
    for (multimap::iterator mi = mapOrphanBlocksByPrev.lower_bound(hash);
         mi != mapOrphanBlocksByPrev.upper_bound(hash);
         ++mi)
    {
        CBlock* pblockOrphan = (*mi).second;
        pblockOrphan->AcceptBlock();
        mapOrphanBlocks.erase(pblockOrphan->GetHash());
        delete pblockOrphan;
    }
    mapOrphanBlocksByPrev.erase(hash);

    return true;
}

// Copyright (c) 2008 Satoshi Nakamoto
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

class COutPoint;
class CInPoint;
class CDiskTxPos;
class CCoinBase;
class CTxIn;
class CTxOut;
class CTransaction;
class CBlock;
class CBlockIndex;
class CWalletTx;
class CKeyItem;

static const unsigned int MAX_SIZE = 0x02000000;
static const int64 COIN = 1000000;
static const int64 CENT = 10000;
static const int64 TRANSACTIONFEE = 1 * CENT; /// change this to a user options setting, optional fee can be zero
///static const unsigned int MINPROOFOFWORK = 40; /// need to decide the right difficulty to start with
static const unsigned int MINPROOFOFWORK = 20;  /// ridiculously easy for testing







extern map mapBlockIndex;
extern const uint256 hashGenesisBlock;
extern CBlockIndex* pindexGenesisBlock;
extern int nBestHeight;
extern CBlockIndex* pindexBest;
extern unsigned int nTransactionsUpdated;
extern int fGenerateBitcoins;







FILE* OpenBlockFile(unsigned int nFile, unsigned int nBlockPos, const char* pszMode="rb");
FILE* AppendBlockFile(unsigned int& nFileRet);
bool AddKey(const CKey& key);
vector GenerateNewKey();
bool AddToWallet(const CWalletTx& wtxIn);
void ReacceptWalletTransactions();
void RelayWalletTransactions();
bool LoadBlockIndex(bool fAllowNew=true);
bool BitcoinMiner();
bool ProcessMessages(CNode* pfrom);
bool ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv);
bool SendMessages(CNode* pto);
int64 CountMoney();
bool CreateTransaction(CScript scriptPubKey, int64 nValue, CWalletTx& txNew);
bool SendMoney(CScript scriptPubKey, int64 nValue, CWalletTx& wtxNew);











class CDiskTxPos
{
public:
    unsigned int nFile;
    unsigned int nBlockPos;
    unsigned int nTxPos;

    CDiskTxPos()
    {
        SetNull();
    }

    CDiskTxPos(unsigned int nFileIn, unsigned int nBlockPosIn, unsigned int nTxPosIn)
    {
        nFile = nFileIn;
        nBlockPos = nBlockPosIn;
        nTxPos = nTxPosIn;
    }

    IMPLEMENT_SERIALIZE( READWRITE(FLATDATA(*this)); )
    void SetNull() { nFile = -1; nBlockPos = 0; nTxPos = 0; }
    bool IsNull() const { return (nFile == -1); }

    friend bool operator==(const CDiskTxPos& a, const CDiskTxPos& b)
    {
        return (a.nFile     == b.nFile &&
                a.nBlockPos == b.nBlockPos &&
                a.nTxPos    == b.nTxPos);
    }

    friend bool operator!=(const CDiskTxPos& a, const CDiskTxPos& b)
    {
        return !(a == b);
    }

    void print() const
    {
        if (IsNull())
            printf("null");
        else
            printf("(nFile=%d, nBlockPos=%d, nTxPos=%d)", nFile, nBlockPos, nTxPos);
    }
};




class CInPoint
{
public:
    CTransaction* ptx;
    unsigned int n;

    CInPoint() { SetNull(); }
    CInPoint(CTransaction* ptxIn, unsigned int nIn) { ptx = ptxIn; n = nIn; }
    void SetNull() { ptx = NULL; n = -1; }
    bool IsNull() const { return (ptx == NULL && n == -1); }
};




class COutPoint
{
public:
    uint256 hash;
    unsigned int n;

    COutPoint() { SetNull(); }
    COutPoint(uint256 hashIn, unsigned int nIn) { hash = hashIn; n = nIn; }
    IMPLEMENT_SERIALIZE( READWRITE(FLATDATA(*this)); )
    void SetNull() { hash = 0; n = -1; }
    bool IsNull() const { return (hash == 0 && n == -1); }

    friend bool operator<(const COutPoint& a, const COutPoint& b)
    {
        return (a.hash < b.hash || (a.hash == b.hash && a.n < b.n));
    }

    friend bool operator==(const COutPoint& a, const COutPoint& b)
    {
        return (a.hash == b.hash && a.n == b.n);
    }

    friend bool operator!=(const COutPoint& a, const COutPoint& b)
    {
        return !(a == b);
    }

    void print() const
    {
        printf("COutPoint(%s, %d)", hash.ToString().substr(0,6).c_str(), n);
    }
};




//
// An input of a transaction.  It contains the location of the previous
// transaction's output that it claims and a signature that matches the
// output's public key.
//
class CTxIn
{
public:
    COutPoint prevout;
    CScript scriptSig;

    CTxIn()
    {
    }

    CTxIn(COutPoint prevoutIn, CScript scriptSigIn)
    {
        prevout = prevoutIn;
        scriptSig = scriptSigIn;
    }

    CTxIn(uint256 hashPrevTx, unsigned int nOut, CScript scriptSigIn)
    {
        prevout = COutPoint(hashPrevTx, nOut);
        scriptSig = scriptSigIn;
    }

    IMPLEMENT_SERIALIZE
    (
        READWRITE(prevout);
        READWRITE(scriptSig);
    )

    bool IsPrevInMainChain() const
    {
        return CTxDB("r").ContainsTx(prevout.hash);
    }

    friend bool operator==(const CTxIn& a, const CTxIn& b)
    {
        return (a.prevout == b.prevout && a.scriptSig == b.scriptSig);
    }

    friend bool operator!=(const CTxIn& a, const CTxIn& b)
    {
        return !(a == b);
    }

    void print() const
    {
        printf("CTxIn(");
        prevout.print();
        if (prevout.IsNull())
        {
            printf(", coinbase %s)\n", HexStr(scriptSig.begin(), scriptSig.end(), false).c_str());
        }
        else
        {
            if (scriptSig.size() >= 6)
                printf(", scriptSig=%02x%02x", scriptSig[4], scriptSig[5]);
            printf(")\n");
        }
    }

    bool IsMine() const;
    int64 GetDebit() const;
};




//
// An output of a transaction.  It contains the public key that the next input
// must be able to sign with to claim it.
//
class CTxOut
{
public:
    int64 nValue;
    unsigned int nSequence;
    CScript scriptPubKey;

    // disk only
    CDiskTxPos posNext;  //// so far this is only used as a flag, nothing uses the location

public:
    CTxOut()
    {
        nValue = 0;
        nSequence = UINT_MAX;
    }

    CTxOut(int64 nValueIn, CScript scriptPubKeyIn, int nSequenceIn=UINT_MAX)
    {
        nValue = nValueIn;
        scriptPubKey = scriptPubKeyIn;
        nSequence = nSequenceIn;
    }

    IMPLEMENT_SERIALIZE
    (
        READWRITE(nValue);
        READWRITE(nSequence);
        READWRITE(scriptPubKey);
        if (nType & SER_DISK)
            READWRITE(posNext);
    )

    uint256 GetHash() const { return SerializeHash(*this); }

    bool IsFinal() const
    {
        return (nSequence == UINT_MAX);
    }

    bool IsMine() const
    {
        return ::IsMine(scriptPubKey);
    }

    int64 GetCredit() const
    {
        if (IsMine())
            return nValue;
        return 0;
    }

    friend bool operator==(const CTxOut& a, const CTxOut& b)
    {
        return (a.nValue       == b.nValue &&
                a.nSequence    == b.nSequence &&
                a.scriptPubKey == b.scriptPubKey);
    }

    friend bool operator!=(const CTxOut& a, const CTxOut& b)
    {
        return !(a == b);
    }

    void print() const
    {
        if (scriptPubKey.size() >= 6)
            printf("CTxOut(nValue=%I64d, nSequence=%u, scriptPubKey=%02x%02x, posNext=", nValue, nSequence, scriptPubKey[4], scriptPubKey[5]);
        posNext.print();
        printf(")\n");
    }
};




//
// The basic transaction that is broadcasted on the network and contained in
// blocks.  A transaction can contain multiple inputs and outputs.
//
class CTransaction
{
public:
    vector vin;
    vector vout;
    unsigned int nLockTime;


    CTransaction()
    {
        SetNull();
    }

    IMPLEMENT_SERIALIZE
    (
        if (!(nType & SER_GETHASH))
            READWRITE(nVersion);

        // Set version on stream for writing back same version
        if (fRead && s.nVersion == -1)
            s.nVersion = nVersion;

        READWRITE(vin);
        READWRITE(vout);
        READWRITE(nLockTime);
    )

    void SetNull()
    {
        vin.clear();
        vout.clear();
        nLockTime = 0;
    }

    bool IsNull() const
    {
        return (vin.empty() && vout.empty());
    }

    uint256 GetHash() const
    {
        return SerializeHash(*this);
    }

    bool AllPrevInMainChain() const
    {
        foreach(const CTxIn& txin, vin)
            if (!txin.IsPrevInMainChain())
                return false;
        return true;
    }

    bool IsFinal() const
    {
        if (nLockTime == 0)
            return true;
        if (nLockTime < GetAdjustedTime())
            return true;
        foreach(const CTxOut& txout, vout)
            if (!txout.IsFinal())
                return false;
        return true;
    }

    bool IsUpdate(const CTransaction& b) const
    {
        if (vin.size() != b.vin.size() || vout.size() != b.vout.size())
            return false;
        for (int i = 0; i < vin.size(); i++)
            if (vin[i].prevout != b.vin[i].prevout)
                return false;

        bool fNewer = false;
        unsigned int nLowest = UINT_MAX;
        for (int i = 0; i < vout.size(); i++)
        {
            if (vout[i].nSequence != b.vout[i].nSequence)
            {
                if (vout[i].nSequence <= nLowest)
                {
                    fNewer = false;
                    nLowest = vout[i].nSequence;
                }
                if (b.vout[i].nSequence < nLowest)
                {
                    fNewer = true;
                    nLowest = b.vout[i].nSequence;
                }
            }
        }
        return fNewer;
    }

    bool IsCoinBase() const
    {
        return (vin.size() == 1 && vin[0].prevout.IsNull());
    }

    bool CheckTransaction() const
    {
        // Basic checks that don't depend on any context
        if (vin.empty() || vout.empty())
            return false;

        // Check for negative values
        int64 nValueOut = 0;
        foreach(const CTxOut& txout, vout)
        {
            if (txout.nValue < 0)
                return false;
            nValueOut += txout.nValue;
        }

        if (IsCoinBase())
        {
            if (vin[0].scriptSig.size() > 100)
                return false;
        }
        else
        {
            foreach(const CTxIn& txin, vin)
                if (txin.prevout.IsNull())
                    return false;
        }

        return true;
    }

    bool IsMine() const
    {
        foreach(const CTxOut& txout, vout)
            if (txout.IsMine())
                return true;
        return false;
    }

    int64 GetDebit() const
    {
        int64 nDebit = 0;
        foreach(const CTxIn& txin, vin)
            nDebit += txin.GetDebit();
        return nDebit;
    }

    int64 GetCredit() const
    {
        int64 nCredit = 0;
        foreach(const CTxOut& txout, vout)
            nCredit += txout.GetCredit();
        return nCredit;
    }

    int64 GetValueOut() const
    {
        int64 nValueOut = 0;
        foreach(const CTxOut& txout, vout)
        {
            if (txout.nValue < 0)
                throw runtime_error("CTransaction::GetValueOut() : negative value");
            nValueOut += txout.nValue;
        }
        return nValueOut;
    }



    bool ReadFromDisk(CDiskTxPos pos, FILE** pfileRet=NULL)
    {
        CAutoFile filein = OpenBlockFile(pos.nFile, 0, pfileRet ? "rb+" : "rb");
        if (!filein)
            return false;

        // Read transaction
        if (fseek(filein, pos.nTxPos, SEEK_SET) != 0)
            return false;
        filein >> *this;

        // Return file pointer
        if (pfileRet)
        {
            if (fseek(filein, pos.nTxPos, SEEK_SET) != 0)
                return false;
            *pfileRet = filein.release();
        }
        return true;
    }


    friend bool operator==(const CTransaction& a, const CTransaction& b)
    {
        return (a.vin       == b.vin &&
                a.vout      == b.vout &&
                a.nLockTime == b.nLockTime);
    }

    friend bool operator!=(const CTransaction& a, const CTransaction& b)
    {
        return !(a == b);
    }


    void print() const
    {
        printf("CTransaction(vin.size=%d, vout.size=%d, nLockTime=%d)\n",
            vin.size(),
            vout.size(),
            nLockTime);
        for (int i = 0; i < vin.size(); i++)
        {
            printf("    ");
            vin[i].print();
        }
        for (int i = 0; i < vout.size(); i++)
        {
            printf("    ");
            vout[i].print();
        }
    }



    bool TestDisconnectInputs(CTxDB& txdb, map& mapTestPool)
    {
        return DisconnectInputs(txdb, mapTestPool, true);
    }

    bool TestConnectInputs(CTxDB& txdb, map& mapTestPool, bool fMemoryTx, bool fIgnoreDiskConflicts, int64& nFees)
    {
        return ConnectInputs(txdb, mapTestPool, CDiskTxPos(1, 1, 1), 0, true, fMemoryTx, fIgnoreDiskConflicts, nFees);
    }

    bool DisconnectInputs(CTxDB& txdb)
    {
        static map mapTestPool;
        return DisconnectInputs(txdb, mapTestPool, false);
    }

    bool ConnectInputs(CTxDB& txdb, CDiskTxPos posThisTx, int nHeight)
    {
        static map mapTestPool;
        int64 nFees;
        return ConnectInputs(txdb, mapTestPool, posThisTx, nHeight, false, false, false, nFees);
    }

private:
    bool DisconnectInputs(CTxDB& txdb, map& mapTestPool, bool fTest);
    bool ConnectInputs(CTxDB& txdb, map& mapTestPool, CDiskTxPos posThisTx, int nHeight,
                       bool fTest, bool fMemoryTx, bool fIgnoreDiskConflicts, int64& nFees);

public:
    bool AcceptTransaction(CTxDB& txdb, bool fCheckInputs=true);
    bool AcceptTransaction() { CTxDB txdb("r"); return AcceptTransaction(txdb); }
    bool ClientConnectInputs();
};





//
// A transaction with a merkle branch linking it to the timechain
//
class CMerkleTx : public CTransaction
{
public:
    uint256 hashBlock;
    vector vMerkleBranch;
    int nIndex;

    CMerkleTx()
    {
        Init();
    }

    CMerkleTx(const CTransaction& txIn) : CTransaction(txIn)
    {
        Init();
    }

    void Init()
    {
        hashBlock = 0;
        nIndex = -1;
    }

    IMPLEMENT_SERIALIZE
    (
        nSerSize += SerReadWrite(s, *(CTransaction*)this, nType, nVersion, ser_action);
        if (!(nType & SER_GETHASH))
            READWRITE(nVersion);
        READWRITE(hashBlock);
        READWRITE(vMerkleBranch);
        READWRITE(nIndex);
    )


    int SetMerkleBranch();
    int IsInMainChain() const;
    bool AcceptTransaction(CTxDB& txdb, bool fCheckInputs=true);
    bool AcceptTransaction() { CTxDB txdb("r"); return AcceptTransaction(txdb); }
};




//
// A transaction with a bunch of additional info that only the owner cares
// about.  It includes any unrecorded transactions needed to link it back
// to the timechain.
//
class CWalletTx : public CMerkleTx
{
public:
    vector vtxPrev;
    map mapValue;
    vector > vOrderForm;
    unsigned int nTime;
    char fFromMe;
    char fSpent;

    //// probably need to sign the order info so know it came from payer

    CWalletTx()
    {
        Init();
    }

    CWalletTx(const CMerkleTx& txIn) : CMerkleTx(txIn)
    {
        Init();
    }

    CWalletTx(const CTransaction& txIn) : CMerkleTx(txIn)
    {
        Init();
    }

    void Init()
    {
        nTime = 0;
        fFromMe = false;
        fSpent = false;
    }

    IMPLEMENT_SERIALIZE
    (
        /// would be nice for it to return the version number it reads, maybe use a reference
        nSerSize += SerReadWrite(s, *(CMerkleTx*)this, nType, nVersion, ser_action);
        if (!(nType & SER_GETHASH))
            READWRITE(nVersion);
        READWRITE(vtxPrev);
        READWRITE(mapValue);
        READWRITE(vOrderForm);
        READWRITE(nTime);
        READWRITE(fFromMe);
        READWRITE(fSpent);
    )

    bool WriteToDisk()
    {
        return CWalletDB().WriteTx(GetHash(), *this);
    }


    void AddSupportingTransactions(CTxDB& txdb);
    void AddSupportingTransactions() { CTxDB txdb("r"); AddSupportingTransactions(txdb); }

    bool AcceptWalletTransaction(CTxDB& txdb, bool fCheckInputs=true);
    bool AcceptWalletTransaction() { CTxDB txdb("r"); return AcceptWalletTransaction(txdb); }

    void RelayWalletTransaction(CTxDB& txdb);
    void RelayWalletTransaction() { CTxDB txdb("r"); RelayWalletTransaction(txdb); }
};






//
// Nodes collect new transactions into a block, hash them into a hash tree,
// and scan through nonce values to make the block's hash satisfy proof-of-work
// requirements.  When they solve the proof-of-work, they broadcast the block
// to everyone and the block is added to the timechain.  The first transaction
// in the block is a special one that creates a new coin owned by the creator
// of the block.
//
// Blocks are appended to blk0001.dat files on disk.  Their location on disk
// is indexed by CBlockIndex objects in memory.
//
class CBlock
{
public:
    // header
    uint256 hashPrevBlock;
    uint256 hashMerkleRoot;
    unsigned int nTime;
    unsigned int nBits;
    unsigned int nNonce;

    // network and disk
    vector vtx;

    // memory only
    mutable vector vMerkleTree;


    CBlock()
    {
        SetNull();
    }

    IMPLEMENT_SERIALIZE
    (
        if (!(nType & SER_GETHASH))
            READWRITE(nVersion);
        READWRITE(hashPrevBlock);
        READWRITE(hashMerkleRoot);
        READWRITE(nTime);
        READWRITE(nBits);
        READWRITE(nNonce);

        // ConnectBlock depends on vtx being last so it can calculate offset
        if (!(nType & (SER_GETHASH|SER_BLOCKHEADERONLY)))
            READWRITE(vtx);
        else if (fRead)
            const_cast(this)->vtx.clear();
    )

    void SetNull()
    {
        hashPrevBlock = 0;
        hashMerkleRoot = 0;
        nTime = 0;
        nBits = 0;
        nNonce = 0;
        vtx.clear();
        vMerkleTree.clear();
    }

    bool IsNull() const
    {
        return (nBits == 0);
    }

    uint256 GetHash() const
    {
        return Hash(BEGIN(hashPrevBlock), END(nNonce));
    }

    uint256 BuildMerkleTree() const
    {
        vMerkleTree.clear();
        foreach(const CTransaction& tx, vtx)
            vMerkleTree.push_back(tx.GetHash());
        int j = 0;
        for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
        {
            for (int i = 0; i < nSize; i += 2)
            {
                int i2 = min(i+1, nSize-1);
                vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vMerkleTree[j+i]),
                                           BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
            }
            j += nSize;
        }
        return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
    }

    vector GetMerkleBranch(int nIndex) const
    {
        if (vMerkleTree.empty())
            BuildMerkleTree();
        vector vMerkleBranch;
        int j = 0;
        for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
        {
            int i = min(nIndex^1, nSize-1);
            vMerkleBranch.push_back(vMerkleTree[j+i]);
            nIndex >>= 1;
            j += nSize;
        }
        return vMerkleBranch;
    }

    static uint256 CheckMerkleBranch(uint256 hash, const vector& vMerkleBranch, int nIndex)
    {
        foreach(const uint256& otherside, vMerkleBranch)
        {
            if (nIndex & 1)
                hash = Hash(BEGIN(otherside), END(otherside), BEGIN(hash), END(hash));
            else
                hash = Hash(BEGIN(hash), END(hash), BEGIN(otherside), END(otherside));
            nIndex >>= 1;
        }
        return hash;
    }


    bool WriteToDisk(bool fWriteTransactions, unsigned int& nFileRet, unsigned int& nBlockPosRet)
    {
        // Open history file to append
        CAutoFile fileout = AppendBlockFile(nFileRet);
        if (!fileout)
            return false;
        if (!fWriteTransactions)
            fileout.nType |= SER_BLOCKHEADERONLY;

        // Write index header
        unsigned int nSize = fileout.GetSerializeSize(*this);
        fileout << FLATDATA(pchMessageStart) << nSize;

        // Write block
        nBlockPosRet = ftell(fileout);
        if (nBlockPosRet == -1)
            return false;
        fileout << *this;

        return true;
    }

    bool ReadFromDisk(unsigned int nFile, unsigned int nBlockPos, bool fReadTransactions)
    {
        SetNull();

        // Open history file to read
        CAutoFile filein = OpenBlockFile(nFile, nBlockPos, "rb");
        if (!filein)
            return false;
        if (!fReadTransactions)
            filein.nType |= SER_BLOCKHEADERONLY;

        // Read block
        filein >> *this;

        // Check the header
        if (nBits < MINPROOFOFWORK || GetHash() > (~uint256(0) >> nBits))
            return error("CBlock::ReadFromDisk : errors in block header");

        return true;
    }



    void print() const
    {
        printf("CBlock(hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%u, nNonce=%u, vtx=%d)\n",
            hashPrevBlock.ToString().substr(0,6).c_str(),
            hashMerkleRoot.ToString().substr(0,6).c_str(),
            nTime, nBits, nNonce,
            vtx.size());
        for (int i = 0; i < vtx.size(); i++)
        {
            printf("  ");
            vtx[i].print();
        }
        printf("  vMerkleTree: ");
        for (int i = 0; i < vMerkleTree.size(); i++)
            printf("%s ", vMerkleTree[i].ToString().substr(0,6).c_str());
        printf("\n");
    }



    bool ReadFromDisk(const CBlockIndex* blockindex, bool fReadTransactions);
    bool TestDisconnectBlock(CTxDB& txdb, map& mapTestPool);
    bool TestConnectBlock(CTxDB& txdb, map& mapTestPool);
    bool DisconnectBlock();
    bool ConnectBlock(unsigned int nFile, unsigned int nBlockPos, int nHeight);
    bool AddToBlockIndex(unsigned int nFile, unsigned int nBlockPos, bool fWriteDisk);
    bool CheckBlock() const;
    bool AcceptBlock();
};






//
// The timechain is a tree shaped structure starting with the
// genesis block at the root, with each block potentially having multiple
// candidates to be the next block.  pprev and pnext link a path through the
// main/longest chain.  A blockindex may have multiple pprev pointing back
// to it, but pnext will only point forward to the longest branch, or will
// be null if the block is not part of the longest chain.
//
class CBlockIndex
{
public:
    CBlockIndex* pprev;
    CBlockIndex* pnext;
    unsigned int nFile;
    unsigned int nBlockPos;
    int nHeight;


    CBlockIndex()
    {
        pprev = NULL;
        pnext = NULL;
        nFile = 0;
        nBlockPos = 0;
        nHeight = 0;
    }

    CBlockIndex(unsigned int nFileIn, unsigned int nBlockPosIn)
    {
        pprev = NULL;
        pnext = NULL;
        nFile = nFileIn;
        nBlockPos = nBlockPosIn;
        nHeight = 0;
    }

    bool IsInMainChain() const
    {
        return (pnext || this == pindexBest);
    }

    bool EraseBlockFromDisk()
    {
        // Open history file
        CAutoFile fileout = OpenBlockFile(nFile, nBlockPos, "rb+");
        if (!fileout)
            return false;

        // Overwrite with empty null block
        CBlock block;
        block.SetNull();
        fileout << block;

        return true;
    }



    bool TestDisconnectBlock(CTxDB& txdb, map& mapTestPool)
    {
        CBlock block;
        if (!block.ReadFromDisk(nFile, nBlockPos, true))
            return false;
        return block.TestDisconnectBlock(txdb, mapTestPool);
    }

    bool TestConnectBlock(CTxDB& txdb, map& mapTestPool)
    {
        CBlock block;
        if (!block.ReadFromDisk(nFile, nBlockPos, true))
            return false;
        return block.TestConnectBlock(txdb, mapTestPool);
    }

    bool DisconnectBlock()
    {
        CBlock block;
        if (!block.ReadFromDisk(nFile, nBlockPos, true))
            return false;
        return block.DisconnectBlock();
    }

    bool ConnectBlock()
    {
        CBlock block;
        if (!block.ReadFromDisk(nFile, nBlockPos, true))
            return false;
        return block.ConnectBlock(nFile, nBlockPos, nHeight);
    }



    void print() const
    {
        printf("CBlockIndex(nprev=%08x, pnext=%08x, nFile=%d, nBlockPos=%d, nHeight=%d)\n",
            pprev, pnext, nFile, nBlockPos, nHeight);
    }
};

void PrintTimechain();







//
// Describes a place in the timechain to another node such that if the
// other node doesn't have the same branch, it can find a recent common trunk.
// The further back it is, the further before the branch point it may be.
//
class CBlockLocator
{
protected:
    vector vHave;
public:

    CBlockLocator()
    {
    }

    explicit CBlockLocator(const CBlockIndex* pindex)
    {
        Set(pindex);
    }

    explicit CBlockLocator(uint256 hashBlock)
    {
        map::iterator mi = mapBlockIndex.find(hashBlock);
        if (mi != mapBlockIndex.end())
            Set((*mi).second);
    }

    IMPLEMENT_SERIALIZE
    (
        if (!(nType & SER_GETHASH))
            READWRITE(nVersion);
        READWRITE(vHave);
    )

    void Set(const CBlockIndex* pindex)
    {
        vHave.clear();
        int nStep = 1;
        while (pindex)
        {
            CBlock block;
            block.ReadFromDisk(pindex, false);
            vHave.push_back(block.GetHash());

            // Exponentially larger steps back
            for (int i = 0; pindex && i < nStep; i++)
                pindex = pindex->pprev;
            if (vHave.size() > 10)
                nStep *= 2;
        }
    }

    CBlockIndex* GetBlockIndex()
    {
        // Find the first block the caller has in the main chain
        foreach(const uint256& hash, vHave)
        {
            map::iterator mi = mapBlockIndex.find(hash);
            if (mi != mapBlockIndex.end())
            {
                CBlockIndex* pindex = (*mi).second;
                if (pindex->IsInMainChain())
                    return pindex;
            }
        }
        return pindexGenesisBlock;
    }

    uint256 GetBlockHash()
    {
        // Find the first block the caller has in the main chain
        foreach(const uint256& hash, vHave)
        {
            map::iterator mi = mapBlockIndex.find(hash);
            if (mi != mapBlockIndex.end())
            {
                CBlockIndex* pindex = (*mi).second;
                if (pindex->IsInMainChain())
                    return hash;
            }
        }
        return hashGenesisBlock;
    }

    int GetHeight()
    {
        CBlockIndex* pindex = GetBlockIndex();
        if (!pindex)
            return 0;
        return pindex->nHeight;
    }
};












extern map mapTransactions;
extern map mapWallet;
extern vector > vWalletUpdated;
extern CCriticalSection cs_mapWallet;
extern map, CPrivKey> mapKeys;
extern map > mapPubKeys;
extern CCriticalSection cs_mapKeys;
extern CKey keyUser;